14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can we assume all input is in lowercase, or should we fuzzy match for upper case as well? \$\endgroup\$ – Kade Jun 22 '15 at 19:16
  • 1
    \$\begingroup\$ @Vioz- No; the search must be case-sensitive. I updated the question and the example. \$\endgroup\$ – kirbyfan64sos Jun 22 '15 at 19:24

14 Answers 14

5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ This was the exact same Pyth program as I had during my testing. :) \$\endgroup\$ – kirbyfan64sos Jun 22 '15 at 21:36
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Wow! silly me losing time preparing a test suite! \$\endgroup\$ – edc65 Jun 22 '15 at 20:02
3
\$\begingroup\$

[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.

\$\endgroup\$
  • \$\begingroup\$ Check out z and Q. Using them gives you immediately 18 bytes. And you can remove the l in VlK => 17 bytes (link) \$\endgroup\$ – Jakube Jun 22 '15 at 20:48
  • \$\begingroup\$ Btw, your code doesn't work. Try the test case: imig mig migd do Mig imig \$\endgroup\$ – Jakube Jun 22 '15 at 20:50
  • \$\begingroup\$ I have a working 9 bytes solution. If you want any help in Pyth, join the chat. \$\endgroup\$ – Jakube Jun 22 '15 at 21:03
  • \$\begingroup\$ 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) \$\endgroup\$ – cmxu Jun 22 '15 at 21:38
  • 1
    \$\begingroup\$ @Changming Gave you the point. :) \$\endgroup\$ – kirbyfan64sos Jun 23 '15 at 0:21
2
\$\begingroup\$

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>

\$\endgroup\$
2
\$\begingroup\$

ORACLE, 60

Does this count?

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

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

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...

\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Franky Jun 25 '15 at 14:32
2
\$\begingroup\$

Python 2, 69 68 66 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.

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

Check it out here.

\$\endgroup\$
1
\$\begingroup\$

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)}}
\$\endgroup\$
  • 1
    \$\begingroup\$ Same thing in 49 characters: p=->w,l{l.select{|x|x[w]}.sort_by{|e|e.index(w)}} \$\endgroup\$ – daniero Jun 26 '15 at 20:22
  • \$\begingroup\$ @daniero Please post it as your answer. I will upvote ! \$\endgroup\$ – bsd Jun 27 '15 at 3:35
  • 1
    \$\begingroup\$ 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 ;) \$\endgroup\$ – daniero Jun 27 '15 at 13:41
0
\$\begingroup\$

Racket 46 bytes

(for/list((i l)#:when(string-contains? i s))i)

Usage:

(define (f s l)
 (for/list((i l)#:when(string-contains? i s))i))

Testing:

(f "mig" '["imig" "mig" "migd" "do" "Mig"])

Output:

'("imig" "mig" "migd")
\$\endgroup\$
0
\$\begingroup\$

Groovy, 32 bytes

{a,b->a.findAll{it.contains(b)}}
\$\endgroup\$
0
\$\begingroup\$

Pip, 15 bytes

14 bytes of code, +1 for -p flag.

Yq_@?ySKyN_FIg

Takes the list as command-line args and the string from stdin. Try it online!

Explanation

Yq              Yank a line of stdin into y
           FIg  Filter array of cmdline args by this function:
        yN_       Count occurrences of y in arg
      SK        Sort the resulting list using this key function:
  _@?y            Index of y in arg
                Print the Pip representation of the list (implicit, -p flag)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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