dev.to staff

Posted on Feb 6, 2020

Daily Challenge #182 - Arrh, grabscrab!

#challenge

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!

Top comments (8)

Amin • Feb 6 '20 • Edited

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

lusen / they / them 🏳️‍🌈🥑 • Feb 7 '20

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

fitsum • Feb 6 '20 • Edited

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;
}

Bhaumin Shah • Feb 7 '20

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;
}

Sort the input word just once outside the loop
Just compare the full sorted words instead of each char to avoid false positives in comparing words like aabbbcc to aaabccc

Toan Le Viet • Feb 6 '20

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

Valts Liepiņš • Feb 6 '20

Ruby

def grabscrab word, dict
    orig = word.chars.sort!
    dict.filter {|entry| entry.chars.sort.eql? orig }
end

Valts Liepiņš • Feb 6 '20

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

Matt Ellen-Tsivintzeli • Feb 10 '20

What is the expected output of the tests?

DEV Community

Daily Challenge #182 - Arrh, grabscrab!

Setup

Example

Tests

Top comments (8)

Read next

Typescript

Preventing File Inclusion Vulnerabilities in Laravel Applications

All about React Query

Enhancing LRU Cache with Configurable Data Persistence