10
\$\begingroup\$

See also: Granma loves Ana

You will be given a string of lowercase ASCII letters. Using this dictionary file (UPDATED), your task is to solve the anagram. To solve an anagram, you must output all words or groups of words that can be formed using each letter from the input string exactly once, separated by newlines. Groups of the same words in a different order are not unique and should not be output separately; however, the order of the words does not matter. The order of output solutions also does not matter. If the input cannot form a word, output nothing.

Some useful test cases:

Input:  viinlg
Output: living

Input:  fceodglo
Output: code golf

Input:  flogflog
Output: golf golf

Input:  ahwhygi
Output: highway
        high way

Input:  bbbbbb
Output: 

Rules/caveats:

  • You may access the dictionary list any way you like. Command line argument, stdin, reading from file, or reading from internet are all acceptable.

  • Input will consist of lowercase ASCII letters only. You are not required to output results in any particular case.

  • You will not be given a string that already forms a valid word (you may, however, be given a string that forms multiple words, such as bluehouse).

  • Trailing newlines are allowed but not required.

  • Standard loopholes apply.

This is . Shortest code in bytes wins. Good luck!

\$\endgroup\$
12
  • \$\begingroup\$ Sandbox post. \$\endgroup\$ Commented Jun 19, 2017 at 14:59
  • \$\begingroup\$ Should we use 1 space to separate sets of words or any non-letter separator suffices? \$\endgroup\$ Commented Jun 19, 2017 at 16:19
  • \$\begingroup\$ @EriktheOutgolfer To separate sets of words, any separator is fine; however you should still separate words within a single solution with a space. \$\endgroup\$ Commented Jun 19, 2017 at 17:21
  • \$\begingroup\$ @Christian Rules say you must separate sets of words with newlines though. \$\endgroup\$ Commented Jun 19, 2017 at 17:24
  • \$\begingroup\$ @EriktheOutgolfer Then why did you ask "Should we use 1 space to separate sets of words"? Your question confused me, and there should be no reason to prefer anything over newlines for separating sets. I'd say stick to the spec. \$\endgroup\$ Commented Jun 19, 2017 at 17:27

10 Answers 10

2
\$\begingroup\$

Python 2, 341 327 337 320 bytes

This solution assumes the dictionary is stored in a variable w as a set of strings. The first set of combinations does not need to use combinations_with_replacement, but using the latter saves bytes.

from itertools import*
d,o,j,c={},sorted,''.join,combinations_with_replacement
s,w=o(raw_input()),input()
l=len(s)
r=range(l)
for x in w:d.setdefault(j(o(x)),[]).append(x)
b=set(chain(*[d[j(x)]for y in r for x in c(s,y+1)if j(x) in d]))
print'\n'.join(' '.join(x)for y in r for x in c(b,y+1)if(len(j(x)),o(j(x)))==(l,s))

Try it online!

Input - Anagrammed word followed by the dictionary of words as a set:

anagram_word
{'entry1', 'entry2', ...., 'entryN'}

Edit: Updated Inputs.

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

Python 3, 248 202 bytes

from itertools import*
A=set()
def f(s,*G,i=1,A=A):
 if' '>s:A|={' '.join(sorted(G))}
 for _ in s:s[:i]in S and f(s[i:],s[:i],*G);i+=1
I,*S=iter(input,'')
for p in permutations(I):f(''.join(p))
print(A)

Try it online!

Input is as follows:

word_input
dic_entry_1
dic_entry_2
....
dic_entry_N
                 # <<< empty line + \n

Speeding it up:

For testing purposes, if you change from I,*S=iter(input,'') to I=input();S=set(iter(input,'')), the runtime will be reduced drastically and the output will be the same.

Explanation:

In every permutation of the input, it tries to split recursively the permutation in all possible locations, starting from left to right, without skipping letters, with words that are in the dictionary. If a split combination matches all the input permutation, the split words are sorted and added to a set that will be printed at the and of the evaluation.

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

Javascript, 139 137 129 Bytes

-2 Bytes thanks to @FelipeNardiBatista

-8 Bytes thanks to reading the docs ;)

k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])}

Takes in the dictionary as input in form of an array of strings.

var arr = ["living", "code", "golf", "highway", "high", "way"];

var _=
k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])};

console.log(_(arr)("viinlg"));
console.log(_(arr)("fceodglo"));

Explanation:

For every word in dictionary, check if every letter is contained in the chosen word, while simultaneously removing it from the word. At the end of every dictionary entry, restore the word to its unaltered state to check for further matches.

\$\endgroup\$
1
  • \$\begingroup\$ @FelipeNardiBatista You're right, I forgot to golf that name. Thanks :) \$\endgroup\$ Commented Jun 21, 2017 at 9:44
1
\$\begingroup\$

Vyxal j, 82 bitsv2, 10.25 bytes

ð+Þ×vṠ'sṠ⁰s=

Try it Online! Makes sure to output all acronyms with a single space to separate.

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

Scala, 156 bytes

Golfed version. Try it online!

(l:Seq[String],k:String)=>l.filter(w=>w.foldLeft((k,true)){case((r,b),c)=>val i=r.indexOf(c);if(i>=0)(r.substring(0,i)+r.substring(i+1),b)else(r,false)}._2)

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val arr = List("living", "code", "golf", "highway", "high", "way")

    def checkAvailability(str: String, keyword: String): Boolean = {
      keyword.foldLeft((str, true)) { case ((remaining, result), ch) =>
        val idx = remaining.indexOf(ch)
        if (idx >= 0) (remaining.substring(0, idx) + remaining.substring(idx + 1), result && true)
        else (remaining, false)
      }._2
    }

    def filterList(arr: List[String], keyword: String): List[String] = {
      arr.filter(word => checkAvailability(keyword, word))
    }

    println(filterList(arr, "viinlg"))
    println(filterList(arr, "fceodglo"))
  }
}

\$\endgroup\$
0
\$\begingroup\$

Elixir, 188 bytes

Golfed version. Try it online!

f=fn(l,k)->Enum.filter(l,fn w->elem(Enum.reduce(String.graphemes(w),{k,true},fn c,{r,b}->if String.contains?(r,c),do: {String.replace(r,c,"",global: false),b},else: {r,false}end),1)end)end

Ungolfed version. Try it online!

defmodule Main do
  def run do
    filter_strings = fn (lst, k) ->
      Enum.filter(lst, fn w ->
        str = Enum.reduce(String.graphemes(w), {k, true}, fn c, {r, b} ->
          case String.contains?(r, c) do
            true -> {String.replace(r, c, "", global: false), b}
            _ -> {r, false}
          end
        end)
        elem(str, 1)
      end)
    end

    arr = ["living", "code", "golf", "highway", "high", "way"]
    IO.inspect(filter_strings.(arr, "viinlg"))
    IO.inspect(filter_strings.(arr, "fceodglo"))
  end
end

Main.run
\$\endgroup\$
0
\$\begingroup\$

Erlang(escript), 156 bytes

Golfed version. Try it online!

f(L,K)->lists:filter(fun(W)->{_,B}=lists:foldl(fun(C,{R,A})->case lists:member(C,R)of true->{lists:delete(C,R),A};_->{R,false}end end,{K,true},W),B end, L).

Ungolfed version. Try it online!

-module(main).
-export([main/1]).

filter_strings(L, K) ->
    lists:filter(fun(W) ->
        {_, B} = lists:foldl(
            fun(C, {R, Acc}) ->
                case lists:member(C, R) of
                    true -> {lists:delete(C, R), Acc};
                    false -> {R, false}
                end
            end,
            {K, true},
            W
        ),
        B
    end, L).

main(_) ->
    Arr = ["living", "code", "golf", "highway", "high", "way"],
    io:format("~p~n", [filter_strings(Arr, "viinlg")]),
    io:format("~p~n", [filter_strings(Arr, "fceodglo")]).
\$\endgroup\$
0
\$\begingroup\$

OCaml, 224 bytes

Golfed version. Try it online!

let f s t=List.filter(fun w->List.fold_left(fun(x,y)c->let i=String.index_opt x c in match i with Some j->String.sub x 0 j^String.sub x(j+1) (String.length x-j-1),y|None->x,false)(t,true)(String.to_seq w|>List.of_seq)|>snd)s

Ungolfed version. Try it online!

let filter_strings lst str =
  let rec filter_chars str char =
    let i = String.index_opt str char in
    match i with
    | Some idx -> String.sub str 0 idx ^ String.sub str (idx + 1) (String.length str - idx - 1), true
    | None -> str, false
  in
  List.filter (fun word ->
    let _, ok = List.fold_left (fun (str, b) c -> let str', b' = filter_chars str c in str', b && b') (str, true) (String.to_seq word |> List.of_seq) in
    ok) lst

let () =
  let arr = ["living"; "code"; "golf"; "highway"; "high"; "way"] in
  let result1 = filter_strings arr "viinlg" in
  let result2 = filter_strings arr "fceodglo" in
  print_endline (List.fold_left (fun a b -> if a = "" then b else a ^ "," ^ b) "" result1);
  print_endline (List.fold_left (fun a b -> if a = "" then b else a ^ "," ^ b) "" result2)
\$\endgroup\$
0
\$\begingroup\$

Racket, 299 bytes

Golfed version. Try it online!

(define(i s c)(let f([l(string->list s)][n 0])(if(null? l)#f(if(char=?(car l)c)n(f(cdr l)(+ 1 n))))))
(define(f l k)(filter(λ(w)(let g([r k][b #t][l(string->list w)])(if(null? l)b(let*([c(car l)][n(i r c)])(if(not(eqv? n #f))(g(string-append(substring r 0 n)(substring r(+ n 1)))b(cdr l))#f)))))l))

Ungolfed version. Try it online!

#lang racket

(define (string-index s c)
  (let loop ([s-list (string->list s)] [index 0])
    (cond
      [(null? s-list) #f]
      [(char=? (car s-list) c) index]
      [else (loop (cdr s-list) (+ 1 index))])))

(define (filter-strings l k)
  (filter (lambda (w)
            (let loop ([r k] [b #t] [wl (string->list w)])
              (if (null? wl)
                  b
                  (let* ([c (car wl)]
                         [i (string-index r c)])
                    (if (not (eqv? i #f))
                        (loop (string-append (substring r 0 i) (substring r (+ i 1))) b (cdr wl))
                        #f))))) l))

(define arr '("living" "code" "golf" "highway" "high" "way"))
(displayln (filter-strings arr "viinlg"))
(displayln (filter-strings arr "fceodglo"))
\$\endgroup\$
0
\$\begingroup\$

F#(.NET Core), 171 bytes

Golfed version. Try it online!

let f l (k:string) = l |> List.filter(fun w -> let mutable r = k in w |> Seq.forall(fun (c:char) -> match r.IndexOf(c) with | -1 -> false | i -> r <- r.Remove(i,1); true))

Ungolfed version. Try it online!

open System

let filterStrings (l: string list) (k: string) = 
    l |> List.filter(fun (w: string) ->
        let mutable r = k
        let mutable b = true
        for c in w do
            let i = r.IndexOf(c)
            if i >= 0 then
                r <- r.Remove(i, 1)
            else
                b <- false
        b)

let arr = ["living"; "code"; "golf"; "highway"; "high"; "way"]
printfn "%A" (filterStrings arr "viinlg")
printfn "%A" (filterStrings arr "fceodglo")
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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