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
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
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
def test_leading_zero_solution_is_invalid
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,
# not your solution.
#
# 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
#
# If you are curious, read more about constants on RubyDoc:
# 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
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.
Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments
This only fixes the comment, no actual code change from iteration 4 to iteration 5 happened.