Avatar of stevensonmt

stevensonmt's solution

to Anagram in the Crystal Track

Published at Mar 16 2020 · 1 comment
Instructions
Test suite
Solution

An anagram is a rearrangement of letters to form a new word. Given a word and a list of candidates, select the sublist of anagrams of the given word.

Given "listen" and a list of candidates like "enlists" "google" "inlets" "banana" the program should return a list containing "inlets".

Setup

Follow the setup instructions for Crystal here:

http://exercism.io/languages/crystal

More help installing can be found here:

http://crystal-lang.org/docs/installation/index.html

Making the Test Suite Pass

Execute the tests with:

$ crystal spec

In each test suite all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by changing pending to it.

Source

Inspired by the Extreme Startup game https://github.com/rchatley/extreme_startup

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

anagram_spec.cr

require "spec"
require "../src/*"

describe "Anagram" do
  it "no matches" do
    Anagram.find("diaper", ["hello", "world", "zombies", "pants"]).should eq [] of String
  end

  pending "detects two anagrams" do
    Anagram.find("master", ["stream", "pigeon", "maters"]).should eq ["stream", "maters"]
  end

  pending "does not detect anagram subsets" do
    Anagram.find("good", ["dog", "goody"]).should eq [] of String
  end

  pending "detects anagram" do
    Anagram.find("listen", ["enlists", "google", "inlets", "banana"]).should eq ["inlets"]
  end

  pending "detects three anagrams" do
    Anagram.find("allergy", ["gallery", "ballerina", "regally", "clergy", "largely", "leading"]).should eq ["gallery", "regally", "largely"]
  end

  pending "does not detect non-anagrams with identical checksum" do
    Anagram.find("mass", ["last"]).should eq [] of String
  end

  pending "detects anagrams case-insensitively" do
    Anagram.find("Orchestra", ["cashregister", "Carthorse", "radishes"]).should eq ["Carthorse"]
  end

  pending "detects anagrams using case-insensitive subject" do
    Anagram.find("Orchestra", ["cashregister", "carthorse", "radishes"]).should eq ["carthorse"]
  end

  pending "detects anagrams using case-insensitive possible matches" do
    Anagram.find("orchestra", ["cashregister", "Carthorse", "radishes"]).should eq ["Carthorse"]
  end

  pending "does not detect an anagram if the original word is repeated" do
    Anagram.find("go", ["go Go GO"]).should eq [] of String
  end

  pending "anagrams must use all letters exactly once" do
    Anagram.find("tapper", ["patter"]).should eq [] of String
  end

  pending "words are not anagrams of themselves (case-insensitive)" do
    Anagram.find("BANANA", ["BANANA", "Banana", "banana"]).should eq [] of String
  end
end
# Please implement your solution to anagram in this file
require "big"
module Anagram 
  extend self 

  #def find(src : String, candidates : Array(String))
    #srtd = src.downcase.chars.sort
    #candidates.select do |candidate|
      #candidate.downcase.chars.sort == srtd
    #end.reject do |candidate|
      #candidate.downcase == src.downcase
    #end.reduce(Array(String).new) { |acc, candidate| acc << candidate }
  #end

  def find(src : String, candidates : Array(String))
    srcbytes = src.downcase.bytes
    srcsum = srcbytes.map do |i| i.to_big_i end.sum
    srcproduct = srcbytes.map do |i| i.to_big_i end.product 

    candidates.select do |candidate|
      cnddtbytes = candidate.downcase.bytes 
      candidate_sum = cnddtbytes.map do |i| i.to_big_i end.sum 
      candidate_product = cnddtbytes.map do |i| i.to_big_i end.product
      candidate_sum == srcsum && candidate_product == srcproduct && cnddtbytes != srcbytes
    end.reduce(Array(String).new) { |acc, candidate| acc << candidate }
  end 
end

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of stevensonmt

this version works but I'm not sure it's mathematically sound. a collection of u8 values that has the same sum and the same product are likely to be identical, though not necessarily. For the provided tests it works but I think that's just luck. Not sure how to prove or disprove the math. If someone can point me in the right direction I'd like to come up with a test that disallows this approach.

(edited 139 days ago)

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?