Solve an Anagram

Question

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 code-golf. Shortest code in bytes wins. Good luck!

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Vyxal j, 82 bits^v2, 10.25 bytes

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

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

Answer 5

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"))
  }
}

Answer 6

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

Answer 7

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")]).

Answer 8

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)

Answer 9

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"))

Answer 10

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")