Avatar of hamberge

hamberge's solution

to Alphametics in the C# Track

Published at Jul 26 2019 · 1 comment
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 class Symbol
{
    public readonly char letter;
        
    private bool[] possibleValues = new bool[10];
    private int currentValue;
    private bool set;
    private bool isLeading = false;

    public bool Set { get => set; set => set = value; }
    public int CurrentValue { get => currentValue; set => currentValue = value; }

    public void SetValue(int value)
    {
        set = true;
        CurrentValue = value;
        possibleValues[value] = false;
    }

    public void SetPossible(int index, bool trueOrFalse)
    {
        if (index < 0 || index > 9) return;
        if (trueOrFalse == false) possibleValues[index] = false;
        else
        {
            if (isLeading && index == 0) return;
            else possibleValues[index] = true;
        }
    }

    public bool GetPossible(int index)
    {
        return possibleValues[index];
    }

    public Symbol(char l, bool leading)
    {
        letter = l;
        isLeading = leading;
        Reset();
    }
    public void Reset()
    {
        Set = false;
        CurrentValue = -1;
        for (int i = 0; i < 10; i++)
        {
            if (isLeading && i == 0)
                possibleValues[i] = false;
            else
                possibleValues[i] = true;
        }
    }
}

public class Column
{
    private List<Symbol> operands;
    private List<Symbol> uniqueDigits;
    private Symbol resultDigit;
    private int carry;
    private SymbolSet symbolSet;
    private bool triedZeroUniqueDigits;

    public int Carry { get => carry; set => carry = value; }

    public Column(List<Symbol> opers, Symbol resultD, List<Symbol> previouslySeenSymbols, SymbolSet sset)
    {
        triedZeroUniqueDigits = false;
        symbolSet = sset;
        operands = opers;
        resultDigit = resultD;
        Carry = 0;
        uniqueDigits = new List<Symbol>();
        foreach(Symbol s in opers)
        {
            if(!uniqueDigits.Contains(s) && !previouslySeenSymbols.Contains(s))
            {
                uniqueDigits.Add(s);
            }
        }
        if(!uniqueDigits.Contains(resultDigit) && !previouslySeenSymbols.Contains(resultDigit))
        {
            uniqueDigits.Add(resultDigit);
        }
    }

    public int SumAddsUp()
    {
        int sum = Carry;
        foreach(Symbol s in operands)
        {
            sum += s.CurrentValue;
        }

        if (sum % 10 == resultDigit.CurrentValue) return sum / 10;
        else return -1;
    }

    public bool FindNextSymbolCombination()
    { 
        if (uniqueDigits.Count == 0)
        {
            if (triedZeroUniqueDigits == false)
            {
                triedZeroUniqueDigits = true;
                return true;
            }
            if(triedZeroUniqueDigits == true)
            {
                triedZeroUniqueDigits = false;
                return false;
            }
        }

        bool allAreSet = true;
        foreach(Symbol s in uniqueDigits)
        {
            if (s.Set == false)
            {
                allAreSet = false;
                break;
            }
        }
        if(!allAreSet)
        {
            for(int i = 0; i < uniqueDigits.Count; i++)
            {
                if (!symbolSet.SetNextSymbolValue(uniqueDigits[i]))
                    throw new Exception("Incorrect column set logic -- symbols in columns not set but no digits are available.");
            }
            return true;
        }
        else
        {
            bool canMoveForwards = false;
            int forwardStart = 0;
            for(int i = uniqueDigits.Count-1; i >=0; i--)
            {
                if (symbolSet.SetNextSymbolValue(uniqueDigits[i]))
                {
                    canMoveForwards = true;
                    forwardStart = i+1;
                    break;
                }
                else
                {
                    symbolSet.ResetSymbol(uniqueDigits[i]);
                }
                    
            }
            if (canMoveForwards == false) return false;

            for(int i = forwardStart; i < uniqueDigits.Count; i++)
            {
                symbolSet.SetNextSymbolValue(uniqueDigits[i]);
            }
            return true;
        }
    }
}

public class SymbolSet
{
    private List<Symbol> symbols;

    public SymbolSet(List<Symbol> symbolsToAdd)
    {
        symbols = symbolsToAdd;
    }

    public Dictionary<char, int> GetDictionary()
    {
        Dictionary<char, int> retVal = new Dictionary<char, int>();
        foreach(Symbol s in symbols)
        {
            retVal.Add(s.letter, s.CurrentValue);
        }
        return retVal;
    }

    public Symbol GetSymbol(char letter)
    {
        foreach(Symbol s in symbols)
        {
            if (s.letter == letter)
                return s;
        }
        return null;
    }
    
    public void ResetSymbol(Symbol symbolToReset)
    {
        int symbolValue = symbolToReset.CurrentValue;
        symbolToReset.Reset();
        foreach (Symbol symbol in symbols)
        {
            if (symbol.Set == true)
            {
                symbolToReset.SetPossible(symbol.CurrentValue, false);
            }
            if(symbol.Set == false)
            {
                symbol.SetPossible(symbolValue, true);
            }
        }
    }

    public bool SetNextSymbolValue(Symbol symbol)
    {
        for(int i = 0; i < 10; i++)
        {
            if(symbol.GetPossible(i) == true) 
            {
                Set(symbol, i);
                return true;
            }
        }
        return false;
    }

    public bool Set(Symbol symbol, int value)
    {
        if(symbol.GetPossible(value) == false)
        {
            return false;
        }
        else
        {
            if (symbol.Set == true)
            {
                symbol.SetPossible(symbol.CurrentValue, false);
                foreach (Symbol s in symbols)
                {
                    if (s.Set == false)
                    {
                        s.SetPossible(symbol.CurrentValue, true);
                    }
                }
            }
            symbol.SetValue(value);
            foreach(Symbol s in symbols)
            {
                if(s.Set == false)
                {
                    s.SetPossible(value, false);
                }
            }
            return true;
        }
    }
}

public static class Alphametics
{
    public static void ParseEquation(string equation, out Column[] columns, out SymbolSet symbolSet)
    {
        string[] tokens = SplitEquations(equation);
        List<Symbol> parsedSymbols = GetUniqueCharsFromTokens(tokens);
        symbolSet = new SymbolSet(parsedSymbols);
        columns = GenerateColumnsFromTokens(tokens, symbolSet);
    }
    
    public static string[] SplitEquations (string equation)
    {
        char[] separators = new char[3] { ' ', '+', '=' };
        string[] tokens = equation.Split(separators, StringSplitOptions.RemoveEmptyEntries);
        return tokens;
    }
    public static List<Symbol> GetUniqueCharsFromTokens(string[] tokens)
    {
        List<char> symbolsChars = new List<char>();
        List<Symbol> symbols = new List<Symbol>();
        foreach (string s in tokens)
        {
            for(int i = 0; i < s.Length; i++)
            {
                if (!symbolsChars.Contains(s[i]))
                {
                    symbolsChars.Add(s[i]);
                    if(i == 0)
                        symbols.Add(new Symbol(s[i], true));
                    else
                        symbols.Add(new Symbol(s[i], false));
                }
            }
        }
        return symbols;
    }
    public static Column[] GenerateColumnsFromTokens(string[] tokens, SymbolSet symbolSet)
    {
        int numColumns = (from token in tokens select token.Length).Max();
        if (tokens.Last().Length < numColumns) throw new ArgumentException();
        Column[] columns = new Column[numColumns];
        List<Symbol> symbolsInColumn = new List<Symbol>();
        List<Symbol> previousSeenSymbols = new List<Symbol>();
        List<Symbol> alreadySeenSymbols = new List<Symbol>();
        for (int i = 0; i < numColumns; i++)
        {
            for (int j = 0; j < tokens.Length - 1; j++)
            {
                string token = tokens[j];
                Symbol symbolToAdd;
                if (tokens[j].Length - 1 >= i)
                {
                    symbolToAdd = symbolSet.GetSymbol(token[token.Length - i - 1]);
                    symbolsInColumn.Add(symbolToAdd);
                    if(!alreadySeenSymbols.Contains(symbolToAdd))
                    {
                        alreadySeenSymbols.Add(symbolToAdd);
                    }
                }
            }
            string resultToken = tokens[tokens.Length - 1];
            Symbol resultSymbol = symbolSet.GetSymbol(resultToken[resultToken.Length - i - 1]);
            if (!alreadySeenSymbols.Contains(resultSymbol))
            {
                alreadySeenSymbols.Add(resultSymbol);
            }
            columns[i] = new Column(symbolsInColumn, resultSymbol, previousSeenSymbols, symbolSet);
            symbolsInColumn = new List<Symbol>();
            previousSeenSymbols = new List<Symbol>(alreadySeenSymbols);
        }
        return columns;
    }
    

    public static bool ProcessColumns(Column[] columns, SymbolSet symbolSet)
    {
        Stack <Column> availableColumns = new Stack<Column>();
        Stack<Column> processedColumns = new Stack<Column>();
        for (int i = columns.Length - 1; i >= 0; i--)
        {
            availableColumns.Push(columns[i]);
        }

        Column currentColumn = availableColumns.Pop();
        int addUpValue = 0;
        while(true)
        {
            if(currentColumn.FindNextSymbolCombination())
            {
                addUpValue = currentColumn.SumAddsUp(); 
                if (addUpValue>-1)
                {
                    if (availableColumns.Count == 0) return true;
                    else
                    {
                        processedColumns.Push(currentColumn);
                        currentColumn = availableColumns.Pop();
                        currentColumn.Carry = addUpValue; 
                    }
                }
            }
            else 
            {
                if (processedColumns.Count == 0) return false;
                availableColumns.Push(currentColumn); 
                currentColumn = processedColumns.Pop();
            }
        }
    }

    public static IDictionary<char, int> Solve(string equation)
    {
        Column[] columns;
        SymbolSet symbolSet;
        ParseEquation(equation, out columns, out symbolSet);
        if (!ProcessColumns(columns, symbolSet)) throw new ArgumentException();
        else
        {
            return symbolSet.GetDictionary();
        }
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of hamberge
hamberge
Solution Author
commented 119 days ago

This completes all tests in 5.5 seconds.

(edited 118 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?