Avatar of roblau

roblau's solution

to Alphametics in the C# Track

Published at Oct 14 2019 · 0 comments
Instructions
Test suite
Solution

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.

Hints

  • To parse the text, you could try to use the Sprache library. You can also find a good tutorial here.
  • You can solve this exercise with a brute force algorithm, but this will possibly have a poor runtime performance. Try to find a more sophisticated solution.
  • Hint: You could try the column-wise addition algorithm that is usually taught in school.

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit Alphametics.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

AlphameticsTest.cs

// This file was auto-generated based on version 1.3.0 of the canonical data.

using System;
using System.Collections.Generic;
using Xunit;

public class AlphameticsTest
{
    [Fact]
    public void Puzzle_with_three_letters()
    {
        var actual = Alphametics.Solve("I + BB == ILL");
        var expected = new Dictionary<char, int>
        {
            ['I'] = 1,
            ['B'] = 9,
            ['L'] = 0
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Solution_must_have_unique_value_for_each_letter()
    {
        Assert.Throws<ArgumentException>(() => Alphametics.Solve("A == B"));
    }

    [Fact(Skip = "Remove to run test")]
    public void Leading_zero_solution_is_invalid()
    {
        Assert.Throws<ArgumentException>(() => Alphametics.Solve("ACA + DD == BD"));
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_two_digits_final_carry()
    {
        var actual = Alphametics.Solve("A + A + A + A + A + A + A + A + A + A + A + B == BCC");
        var expected = new Dictionary<char, int>
        {
            ['A'] = 9,
            ['B'] = 1,
            ['C'] = 0
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_four_letters()
    {
        var actual = Alphametics.Solve("AS + A == MOM");
        var expected = new Dictionary<char, int>
        {
            ['A'] = 9,
            ['S'] = 2,
            ['M'] = 1,
            ['O'] = 0
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_six_letters()
    {
        var actual = Alphametics.Solve("NO + NO + TOO == LATE");
        var expected = new Dictionary<char, int>
        {
            ['N'] = 7,
            ['O'] = 4,
            ['T'] = 9,
            ['L'] = 1,
            ['A'] = 0,
            ['E'] = 2
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_seven_letters()
    {
        var actual = Alphametics.Solve("HE + SEES + THE == LIGHT");
        var expected = new Dictionary<char, int>
        {
            ['E'] = 4,
            ['G'] = 2,
            ['H'] = 5,
            ['I'] = 0,
            ['L'] = 1,
            ['S'] = 9,
            ['T'] = 7
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_eight_letters()
    {
        var actual = Alphametics.Solve("SEND + MORE == MONEY");
        var expected = new Dictionary<char, int>
        {
            ['S'] = 9,
            ['E'] = 5,
            ['N'] = 6,
            ['D'] = 7,
            ['M'] = 1,
            ['O'] = 0,
            ['R'] = 8,
            ['Y'] = 2
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_ten_letters()
    {
        var actual = Alphametics.Solve("AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE");
        var expected = new Dictionary<char, int>
        {
            ['A'] = 5,
            ['D'] = 3,
            ['E'] = 4,
            ['F'] = 7,
            ['G'] = 8,
            ['N'] = 0,
            ['O'] = 2,
            ['R'] = 1,
            ['S'] = 6,
            ['T'] = 9
        };
        Assert.Equal(expected, actual);
    }

    [Fact(Skip = "Remove to run test")]
    public void Puzzle_with_ten_letters_and_199_addends()
    {
        var actual = Alphametics.Solve("THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + ROOFS + FOR + THEIR + SAFE == FORTRESSES");
        var expected = new Dictionary<char, int>
        {
            ['A'] = 1,
            ['E'] = 0,
            ['F'] = 5,
            ['H'] = 8,
            ['I'] = 7,
            ['L'] = 2,
            ['O'] = 6,
            ['R'] = 3,
            ['S'] = 4,
            ['T'] = 9
        };
        Assert.Equal(expected, actual);
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

public static class Alphametics
{
    public static IDictionary<char, int> Solve(string equation)
    {
        var solver = new EquationSolver(equation);
        return solver.Solve();
    }

    private class EquationSolver
    {
        private readonly string _equation;

        private readonly char[] _allLetters;

        private readonly IEnumerable<char> _leadingLetters;

        private readonly IDictionary<char, long> _formula;

        private IDictionary<char, int> _suggestion;

        private ICollection<int> _usedNumbers;

        public EquationSolver(string equation)
        {
            _equation = equation;
            (_allLetters, _leadingLetters) = ExtractLetters();
            _formula = ExtractFormulas();
        }

        public IDictionary<char, int> Solve()
        {
            _suggestion = GetInitialSuggestion();
            var solution = (IDictionary<char, int>)null;
            do
            {
                if (!IsSuggestionCorrect())
                {
                    continue;
                }

                if (solution != null)
                {
                    // no unique solution
                    throw new ArgumentException("solution is not unique");
                }

                solution = new Dictionary<char, int>(_suggestion);
            }
            while (GetNextSuggestion());

            if (solution == null)
            {
                // no solution at all found
                throw new ArgumentException("no solution found");
            }

            return solution;
        }

        private IDictionary<char, int> GetInitialSuggestion()
        {
            // fill values for each character starting with 1 for the first and following
            // digits for the others. Value 0 for the very first letter would be invalid
            var value = 1;
            _usedNumbers = Enumerable.Range(1, _allLetters.Length).ToList();
            return _allLetters.ToDictionary(character => character, _ => value++);
        }

        private bool GetNextSuggestion()
        {
            // increase values starting from last entry
            // if the value is the same as for the previous character, then switch to that one
            // if the value is smaller, then set the following characters to new values
            // if the value is 0 and the letter is a leading one, skip this value
            // if the value of the very first character is already 9, there is no solution
            for (var index = _allLetters.Length - 1; index >= 0; index--)
            {
                var letter = _allLetters[index];
                if (index == 0)
                {
                    // stop if very first value shall be increased above 9
                    if (_suggestion[letter] == 9)
                    {
                        // there is no further solution
                        return false;
                    }

                    _usedNumbers.Remove(_suggestion[letter]);
                    _suggestion[letter]++;
                    _usedNumbers.Add(_suggestion[letter]);
                    FillRemainingEntries(1);
                    return true;
                }

                // remove own entry in used numbers
                _usedNumbers.Remove(_suggestion[_allLetters[index]]);
                if (!GetNextValue(index))
                {
                    // no further value for current position found,
                    // so continue at previous position
                    // in addition the used value has to be removed
                    continue;
                }
                _usedNumbers.Add(_suggestion[_allLetters[index]]);

                FillRemainingEntries(index + 1);
                return true;
            }

            return false;
        }

        private bool GetNextValue(int index)
        {
            // increase by 1 modulo 10 and compare against previous character as abort criteria
            var value = _suggestion[_allLetters[index]];
            do
            {
                value = (value + 1) % 10;
                if (value == _suggestion[_allLetters[index - 1]])
                {
                    // switch to previous character, i.e. stop for this one
                    return false;
                }
            }
            while (_usedNumbers.Contains(value) || (value == 0 && _leadingLetters.Contains(_allLetters[index])));

            _suggestion[_allLetters[index]] = value;
            return true;
        }

        private void FillRemainingEntries(int startIndex)
        {
            for (var index = startIndex; index < _allLetters.Length; index++)
            {
                // start with value of previous letter
                _suggestion[_allLetters[index]] = _suggestion[_allLetters[index - 1]];
                GetNextValue(index);
                _usedNumbers.Add(_suggestion[_allLetters[index]]);
            }
        }

        private bool IsSuggestionCorrect() =>
            CalculateSum(_formula, _suggestion) == 0;

        private static long CalculateSum(IDictionary<char, long> formula, IDictionary<char, int> solution) =>
            formula.Values.Zip(solution.Values, (count, value) => count * value).Sum();

        private (char[], IEnumerable<char>) ExtractLetters()
        {
            var allLetters = new List<char>();
            var leadingLetters = new List<char>();
            var first = true;
            foreach (var character in _equation)
            {
                if (!IsLetter(character))
                {
                    first = true;
                    continue;
                }

                if (first)
                {
                    first = false;
                    if (!leadingLetters.Contains(character))
                    {
                        leadingLetters.Add(character);
                    }
                }

                if (!allLetters.Contains(character))
                {
                    allLetters.Add(character);
                }
            }

            return (allLetters.ToArray(), leadingLetters);
        }

        private IDictionary<char, long> ExtractFormulas()
        {
            var formulaParts = _equation.Split(" == ");
            var sumDictionary = ParseFormula(formulaParts[0]);
            var rightDictionary = ParseFormula(formulaParts[1]);
            foreach (var key in rightDictionary.Keys)
            {
                if (sumDictionary.ContainsKey(key))
                {
                    sumDictionary[key] -= rightDictionary[key];
                }
                else
                {
                    sumDictionary[key] = -rightDictionary[key];
                }
            }

            // since there is no whitespace after the last word, this is the right hand side
            // of the equation
            return sumDictionary;
        }

        private Dictionary<char, long> ParseFormula(string formula)
        {
            var sumDictionary = _allLetters.ToDictionary(letter => letter, _ => (long)0);
            var wordDictionary = new Dictionary<char, long>(sumDictionary);
            foreach (var character in formula)
            {
                if (!IsLetter(character))
                {
                    // end of a word, so add values to sum dictionary
                    // and reset word counts
                    foreach (var letter in _allLetters)
                    {
                        sumDictionary[letter] += wordDictionary[letter];
                        wordDictionary[letter] = 0;
                    }

                    continue;
                }

                // "shift" values for word by 10
                foreach (var letter in _allLetters)
                {
                    wordDictionary[letter] *= 10;
                }

                // increase value of currently detected character
                wordDictionary[character]++;
            }

            // last word needs to be added, too
            foreach (var letter in _allLetters)
            {
                sumDictionary[letter] += wordDictionary[letter];
            }

            return sumDictionary;
        }

        private static bool IsLetter(char character) => character >= 'A' && character <= 'Z';
    }
}

Community comments

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

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?