# 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")]
{
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")]
{
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 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]++;
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;
}

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);
}
}

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 (!allLetters.Contains(character))
{
}
}

}

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';
}
}``````