ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# angelikatyborska's solution

## to Alphametics in the Ruby Track

Published at Jul 13 2018 · 1 comment
Instructions
Test suite
Solution

#### Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Write a function to solve alphametics puzzles.

Alphametics is a puzzle where letters in words are replaced with numbers.

For example `SEND + MORE = MONEY`:

``````  S E N D
M O R E +
-----------
M O N E Y
``````

Replacing these with valid numbers gives:

``````  9 5 6 7
1 0 8 5 +
-----------
1 0 6 5 2
``````

This is correct because every letter is replaced by a different number and the words, translated into numbers, then make a valid sum.

Each letter must represent a different digit, and the leading digit of a multi-digit number must not be zero.

Write a function to solve alphametics puzzles.

For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

``````gem install minitest
``````

If you would like color output, you can `require 'minitest/pride'` in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

``````ruby alphametics_test.rb
``````

To include color from the command line:

``````ruby -r minitest/pride alphametics_test.rb
``````

## Submitting Incomplete Solutions

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

### alphametics_test.rb

``````require 'minitest/autorun'
require_relative 'alphametics'

# Common test data version: 1.0.0 b9bada8
class AlphameticsTest < Minitest::Test

def test_puzzle_with_three_letters
# skip
input = 'I + BB == ILL'
expected = { 'B' => 9, 'I' => 1, 'L' => 0 }
assert_equal expected, Alphametics.solve(input)
end

def test_solution_must_have_unique_value_for_each_letter
skip
input = 'A == B'
expected = {}
assert_equal expected, Alphametics.solve(input)
end

skip
input = 'ACA + DD == BD'
expected = {}
assert_equal expected, Alphametics.solve(input)
end

def test_puzzle_with_four_letters
skip
input = 'AS + A == MOM'
expected = { 'A' => 9, 'M' => 1, 'O' => 0, 'S' => 2 }
assert_equal expected, Alphametics.solve(input)
end

def test_puzzle_with_six_letters
skip
input = 'NO + NO + TOO == LATE'
expected = { 'A' => 0, 'E' => 2, 'L' => 1, 'N' => 7,
'O' => 4, 'T' => 9 }
assert_equal expected, Alphametics.solve(input)
end

def test_puzzle_with_seven_letters
skip
input = 'HE + SEES + THE == LIGHT'
expected = { 'E' => 4, 'G' => 2, 'H' => 5, 'I' => 0,
'L' => 1, 'S' => 9, 'T' => 7 }
assert_equal expected, Alphametics.solve(input)
end

# The obvious algorithm can take a long time to solve this puzzle,
# but an optimised solution can solve it fairly quickly.
# (It's OK to submit your solution without getting this test to pass.)
def test_puzzle_with_eight_letters
skip
input = 'SEND + MORE == MONEY'
expected = { 'D' => 7, 'E' => 5, 'M' => 1, 'N' => 6,
'O' => 0, 'R' => 8, 'S' => 9, 'Y' => 2 }
assert_equal expected, Alphametics.solve(input)
end

# The obvious algorithm can take a long time to solve this puzzle,
# but an optimised solution can solve it fairly quickly.
# (It's OK to submit your solution without getting this test to pass.)
def test_puzzle_with_ten_letters
skip
input = 'AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE'
expected = { 'A' => 5, 'D' => 3, 'E' => 4, 'F' => 7,
'G' => 8, 'N' => 0, 'O' => 2, 'R' => 1,
'S' => 6, 'T' => 9 }
assert_equal expected, Alphametics.solve(input)
end

# Problems in exercism evolve over time, as we find better ways to ask
# questions.
# The version number refers to the version of the problem you solved,
#
# Define a constant named VERSION inside of the top level BookKeeping
# module, which may be placed near the end of your file.
#
# In your file, it will look like this:
#
# module BookKeeping
#   VERSION = 1 # Where the version number matches the one in the test.
# end
#
# http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html

def test_bookkeeping
skip
assert_equal 4, BookKeeping::VERSION
end
end``````
``````module BookKeeping
VERSION = 4
end

class Alphametics
class << self
def solve(expression)
letters, constitutents, sum = parse(expression)
permutations = (0..9).to_a.permutation(letters.length)

# a solution is a zip of letters and a permutation
# letters = [97, 99, 103]
# permutation = [4, 6, 9]
# solution = {97 => 4, 99 => 6, 103 => 9}

correct_permutation = permutations.find do |permutation|
check_permutation(constitutents, sum, letters, permutation)
end

format_solution(letters, correct_permutation) || {}
end

private

def parse(expression)
constitutents, sum = expression.split(/\s?==\s?/)
sum = sum.codepoints
constitutents = constitutents.split(/\s?\+\s?/).map(&:codepoints)
letters = [sum, constitutents].flatten.uniq.sort
[letters, constitutents, sum]
end

def check_permutation(constitutents, sum, letters, permutation)
first = ->(string) { string[0] }
first_letters = [
*constitutents.map(&first),
first.call(sum)
]

(0...sum.length).all? do |i|
if first_letters.all? { |letter| letter_to_digit(letters, permutation, letter) != 0 }
sum_of_constitutents = sum_column(constitutents, letters, permutation, i)
sum_of_constitutents % 10 == letter_to_digit(letters, permutation, sum[-1 - i])
else
false
end
end
end

def sum_column(constitutents, letters, permutation, index)
numbers = constitutents.map do |c|
if index < c.length
letter_to_digit(letters, permutation, c[-1 - index])
else
0
end
end

carry_over = index == 0 ? 0 : sum_column(constitutents, letters, permutation, index - 1) / 10
carry_over + numbers.reduce(&:+)
end

def format_solution(letters, permutation)
return unless permutation
solution = letters.zip(permutation.slice(0, letters.length))
solution&.map {|k_and_v| [k_and_v[0].chr, k_and_v[1]]}.to_h
end

def letter_to_digit(letters, permutation, letter)
permutation[letters.index(letter)]
end
end
end``````