loading...

Daily Challenge #182 - Arrh, grabscrab!

thepracticaldev profile image dev.to staff ・1 min read

Setup

Pirates are notoriously bad at pronunciation. For this challenge, implement a function that will accept a jumbled word and a dictionary. It should output the words that the pirate might have been saying.

Example

grabscrab( "ortsp", ["sport","parrot","ports","matey"])
=> ["sport", "ports"]

Tests

grabscrab("trisf", ["first"])
grabscrab("oob", ["bob", "baobab"])
grabscrab("ainstuomn", ["mountains", "hills", "mesa"])
grabscrab("oolp", ["donkey", "pool", "horse", "loop"])

Good luck!


This challenge comes from matstc on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
aminnairi profile image
Amin

Elm

toSortedList : String -> List Char
toSortedList string =
    List.sort <| String.toList string


equal : String -> String -> Bool
equal first second =
    toSortedList first == toSortedList second


grabscrab : String -> List String -> List String
grabscrab string list =
    List.filter (equal string) list
Collapse
candidateplanet profile image
lusen / they / them 🏳️‍🌈🥑

Python, two solutions:

Both solutions grow linearly as the number of words in the dictionary grows (we make a single pass through the dictionary and compare if it is an anagram).

Calling anagram_Onlogn multiplies O(n*log(n)) to the runtime, where n is the length of words. This is because it uses sorting to compare words ==> O(dictionary_size * word_size * log(word_size))

Calling anagram_On multiples O(word_size) to the runtime since we use hashmaps (python dicts) to compare words linearly on their size ==> O(dictionary_size * word_size)

def grabscrab(jumble,  dictionary):
  words = []
  for word in dictionary:
    if anagram_On(jumble, word):
      words.append(word)
  return words

# n*log(n) comparison -  better than n^2 but worse than n
def anagram_Onlogn(worda, wordb):
  alist = list(worda)
  blist = list(wordb)
  alist.sort()
  blist.sort()
  return (alist == blist)

# optimal comparison  - we  can't do better than linear since we have to at least read each letter
def anagram_On(worda, wordb):
  adict = make_dict(worda)
  bdict = make_dict(wordb)
  return adict == bdict

def make_dict(word):
  d = {}
  for letter in word:
    if letter not in d:
      d[letter] = 0
    d[letter] += 1
  return d

print(grabscrab("ortsp", ["sport", "parrot", "ports", "matey"]))
print(grabscrab("trisf", ["first"]))
print(grabscrab("oob", ["bob", "baobab"]))
print(grabscrab("ainstuomn", ["mountains", "hills", "mesa"]))
print(grabscrab("oolp", ["donkey", "pool", "horse", "loop"]))
Collapse
fitsum profile image
fitsum

JavaScript

const grabscrab = (garble, dict) => {
  let results = [];
  dict.forEach(entry => {
    let points = 0; 
    entry.split('').forEach(letter => {
      if (garble.indexOf(letter) !== -1) {
        points++;
        if (points === entry.length) {
          results.push(entry);
          console.log(results)
        }
      }
    })
  })
  return results;
}
Collapse
bhaumin profile image
Bhaumin Shah

JavaScript solution:

function grabscrab(word, dict) {
  const wordSorted = word.split("").sort().join("");
  const ans = [];

  for (let item of dict) {
    itemSorted = item.split("").sort().join("");
    if (itemSorted === wordSorted) {
      ans.push(item);
    }
  }

  return ans;
}
  1. Sort the input word just once outside the loop
  2. Just compare the full sorted words instead of each char to avoid false positives in comparing words like aabbbcc to aaabccc
Collapse
toanleviettiki profile image
Toan Le Viet

Quick solution in my head with JS is sorting then comparing with each anagram:

Collapse
cipharius profile image
Valts Liepiņš

Ruby

def grabscrab word, dict
    orig = word.chars.sort!
    dict.filter {|entry| entry.chars.sort.eql? orig }
end
Collapse
cipharius profile image
Valts Liepiņš

Also was in mood for some Haskell.
This time Haskell solution came out neater than Ruby's

import Data.List (sort)

grabscrab :: String -> [String] -> [String]
grabscrab word = filter $ (patt ==) . sort
    where patt = sort word
Collapse
mellen profile image
Matt Ellen

What is the expected output of the tests?