Sign up ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by this link I found on Reddit.

A FuzzyFinder is a feature of many text editors. As you start to type a file path S, the FuzzyFinder kicks in and shows you all files in the current directory containing the string you entered, sorted by the position of S in the file.

Your task is to implement a fuzzy finder. It should be program or function that takes (via stdin, function argument, or command line) a string S and a list of strings L, formatted however you wish, and returns or prints the result of running the fuzzy finder. The search should be case-sensitive. Results where S is in the same position in multiple strings may be sorted however you wish.

Example:

Input: mig, [imig, mig, migd, do, Mig]
Output:
    [mig, migd, imig]
OR
    [migd, mig, imig]

This is code golf, so the shortest solution wins.

share|improve this question
    
Can we assume all input is in lowercase, or should we fuzzy match for upper case as well? –  Shebang Jun 22 at 19:16
1  
@Vioz- No; the search must be case-sensitive. I updated the question and the example. –  kirbyfan64sos Jun 22 at 19:24

11 Answers 11

up vote 5 down vote accepted

Pyth, 9 bytes

oxNzf}zTQ

Try it online: Demonstration

Explanation:

            implicit: z = input string, Q = input list
    f   Q   filter Q for elements T, which satisfy:
     }zT      z is substring of T
o           order the remaining strings N by:
 xNz          the index of z in N
share|improve this answer
1  
This was the exact same Pyth program as I had during my testing. :) –  kirbyfan64sos Jun 22 at 21:36

Ruby, 63

p=->(w,l){l.find_all{|x|x[w]}.sort{|a,b|a.index(w)-b.index(w)}}

Run

irb(main):022:0> p["mig", ["imig", "mig", "migd", "do", "Mig"]]
=> ["migd", "mig", "imig"]

Notes

  1. First find all matching words with find_all
  2. Sort by index position of word to be searched.

Edit (by daneiro)

Ruby, 49

p=->w,l{l.select{|x|x[w]}.sort_by{|e|e.index(w)}}
share|improve this answer
1  
Same thing in 49 characters: p=->w,l{l.select{|x|x[w]}.sort_by{|e|e.index(w)}} –  daniero Jun 26 at 20:22
    
@daniero Please post it as your answer. I will upvote ! –  bsd Jun 27 at 3:35
1  
Nah, that's ok really :) My version is just an improvement of yours, I think they are too similar to be separate answers. select is an alias for find_all, and sort and sort_by are basically the same things in slightly different wrappings. I'll upvote you instead, for thinking of the same solution as me ;) –  daniero Jun 27 at 13:41

Haskell, 129 116

116 (Thanks to Franky):

import Data.List
h s=map snd.sort.map(\x->((head[c|c<-[0..length x],isPrefixOf s(drop c x)]),x)).filter(isInfixOf s)

129:

import Data.List
f s n=map snd(sort(map(\x->((head [c|c<-[0..length x],isPrefixOf s(drop c x)]),x))(filter(\x->isInfixOf s x)n)))

Well, it's pretty long, maybe I'll find how to short it up a bit...

share|improve this answer
1  
shave off 13: h s=map snd.sort.map(\x->((head[c|c<-[0..length x],isPrefixOf s(drop c x)]),x)).filter(isInfixOf s) –  Franky Jun 25 at 14:32

ORACLE, 60

Does this count?

select * from t where a like '%mig%' order by instr(a,'mig')

share|improve this answer
    
It could count, but it would need to be an Oracle procedure that takes the data as arguments. –  kirbyfan64sos Jun 23 at 15:41
    
Whether it counts or not, I think it's cool. The first code golf solution ever that I really understand. Great work! –  Thomas Weller Jun 23 at 19:13
    
@ThomasWeller Thanks! These code golfers can certainly be very bright but sometimes KISS is all you need! –  MonkeyZeus Jun 23 at 20:09

GolfScript, 13 bytes

~{?)}+\1$,\$`

This is one of those rare occasions where GolfScript can beat CJam, by using block concatenation and taking a few liberties with the input which can be formatted however you wish.

Try it online in Web GolfScript.

I/O

Input

["imig" "mig" "migd" "do" "Mig"] {"mig"}

Output

["migd" "mig" "imig"]

How it works

~             # Evaluate the input from STDIN.
              # Pushes an array of haystacks and a needle in a block.
 {?)}         # Push a code block that computes an index and increments it.
     +        # Concatenate that block with the needle block.
      \1$     # Swap the block with the arrays of haystacks and copy the block.
         ,    # Filter: Keep only haystacks for which the code block
              #         pushed a non-zero value.
          \   # Swap the array of haystacks with the code block.
           $  # Sort: Arrange the haystacks according to the values
              #       pushed by the code block.
            ` # Inspect: Format the array for pretty printing.
share|improve this answer

CJam, 18 15 bytes

{1$#)}q~2$,@$p;

Try it online in the CJam interpreter.

I/O

Input:

"mig" ["imig" "mig" "migd" "do" "Mig"]

Output:

["mig" "migd" "imig"]

How it works

      q~        e# Read and evaluate the input from STDIN.
                e# Pushes a needle and an array of haystacks.
{    }          e# Define a code block:
 1$             e#   Copy the needle.
   #            e#   Compute the index of the needle in the haystack.
    )           e#   Add 1 to the index.
        2$      e# Copy the block.
          ,     e# Filter: Keep only haystacks for which the code block
                e#         pushed a non-zero value.
           @    e# Rotate the block on top of the stack.
            $   e# Sort: Arrange the haystacks according to the values
                e#       pushed by the code block.
             p  e# Print the filtered and sorted haystacks.
              ; e# Discard the needle.
share|improve this answer

Python 2, 65

def f(s,l):g=lambda x:x.find(s)+1;print sorted(filter(g,l),key=g)

The expression x.find(s) returns the position of the first occurrence of s in x, giving -1 for no match. We add 1 to the result to that no-match corresponds to 0, letting us filter them out. We then sort by the match position, which is unaffected by shifting by 1.

share|improve this answer

Python 2, 69 68 Bytes

I just created a function which takes s as the string to match in a list of strings n

Edit 1: Thanks to Jakube for golfing off a byte.

f=lambda s,n:sorted([x for x in n if s in x],key=lambda x:x.find(s))

Check it out here.

share|improve this answer

[Hold] Pyth, 24 Bytes

JwKcwdVlK=G.)KI}JGaYG))Y

Try is here

I'm pretty new at Code Golfing/Pyth so I'm not sure it's optimal, but I'm working on it!

Update: I don't think I'm actually sorting correctly, and I can't seem to get it to work. I know that o is order-by, and I need to sort by position of S so I am using .:GlJ in order to find all the substrings of the length of S for the current element G and then x in order to find the index of the first occurrence of S, but I can't seem to set lambda correctly.

share|improve this answer
    
Check out z and Q. Using them gives you immediately 18 bytes. And you can remove the l in VlK => 17 bytes (link) –  Jakube Jun 22 at 20:48
    
Btw, your code doesn't work. Try the test case: imig mig migd do Mig imig –  Jakube Jun 22 at 20:50
    
I have a working 9 bytes solution. If you want any help in Pyth, join the chat. –  Jakube Jun 22 at 21:03
    
Oh, cool! I'll try to figure out how you did it tonight. Thanks for all the help! (Gonna need to earn 1 more reputation point before I can even chat :P) –  Changming Jun 22 at 21:38
    
@Changming Gave you the point. :) –  kirbyfan64sos Jun 23 at 0:21

JavaScript ES6, 68 bytes

(s,l,f=j=>j.indexOf(s))=>l.filter(w=>~f(w)).sort((a,b)=>f(a)>f(b))

This is an anonymous function that takes parameters s (file path string) and l (array of strings). The Stack Snippet below contains ungolfed code converted to ES5 so more people can test it easily. (If you have Firefox, you can use edc65's prettier test suite found in his answer.)

f=function(s,l){
  g=function(j){
    return j.search(s)
  }
  
  return l.filter(function(w){
    return ~g(w)
  }).sort(function(a,b){
    return g(a)>g(b)
  })
}

id=document.getElementById;run=function(){document.getElementById('output').innerHTML=f(document.getElementById('s').value,document.getElementById('l').value.split(', ')).join(', ')};document.getElementById('run').onclick=run;run()
<label>File path: <input type="text" id="s" value="mig" /></label><br />
<label>Files: <input type="text" id="l" value="imig, mig, migd, do, Mig" /></label><br />
<button id="run">Run</button><br />
Output: <output id="output"></output>

share|improve this answer
    
Wow! silly me losing time preparing a test suite! –  edc65 Jun 22 at 20:02

JavaScript (ES6), 68

That's almost the same of @NBM answer (even if it's not copied), so I don't expect upvotes. Enjoy the snippet anyway

A function with a string and a string array arguments, return a string array. Filter then sort.

Test runnign the snippet below (being EcmaScript 6, Firefox only)

f=(s,l,i=t=>t.indexOf(s))=>l.filter(t=>~i(t)).sort((t,u)=>i(t)-i(u))

$(function(){
  $("#S,#L").on("keyup", 
   function() { 
     $('#O').val(f(S.value,L.value.split('\n')).join('\n'))
   } );
  $("#S").trigger('keyup');
})
#S,#L,#O { width: 400px }
#L,#O { height: 100px }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Input String<br><input id=S value='mig'><br>
Input List<br><textarea id=L>
imig
mig
migd
do
Mig
</textarea><br>
Output List<br><textarea id=O readonly></textarea>

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.