# cmccandless's solution

## to Alphametics in the C# Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Write a method 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 method 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.

## Submitting Incomplete Solutions

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

### 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;
using static MoreLinq.Extensions.PermutationsExtension;

public class Alphametics
{
private static HashSet<string> Operators = new [] {"+", "=="}.ToHashSet();
private const string ERR_START_WITH_ZERO = "word cannot start with zero";
private const string ERR_NO_SOLUTION = "no solution";

public static bool TrySolution(char[] letters, int[] solution, IEnumerable<string> words)
{
int mapLetterToDigit(char ch) => solution[letters.IndexOf(ch)];
long sub(string word) =>
word.Select(mapLetterToDigit).Aggregate((long)0, (total, digit) => total * 10 + digit);
var parts = words.Select(sub).AsStack();
return parts.Pop() == parts.Sum();
}

private static Dictionary<char, int> CreateSolutionDict(char[] letters, int[] solution) =>
letters.Zip(solution, (l, d) => (l, d)).ToDictionary(o => o.l, o => o.d);

public static Dictionary<char, int> Solve(string expr)
{
var words = expr.Split(' ').Where(w => !Operators.Contains(w)).ToArray();
var letters = expr.Where(Char.IsLetter).Distinct().ToArray();
var cannotBeZero = words.Select(w => letters.IndexOf(w[0])).ToHashSet();
var solution = Enumerable.Range(0, 10)
.Reverse()
.Permutations(letters.Length)
.Select(p => p.ToArray())
.Where(p => !cannotBeZero.Contains(p.IndexOf(0)))
.FirstOrDefault(p => TrySolution(letters, p, words));
if (solution != null) return CreateSolutionDict(letters, solution);
throw new ArgumentException(ERR_NO_SOLUTION);
}
}

public static class Extensions
{
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> col, int length)
{
if (length == 0) return new[] { new T[0] };
return col.SelectMany((e, i) => col.Skip(i + 1).Combinations(length - 1).Select(c => (new[] {e}).Concat(c)));
}

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> col, int length) =>
col.Combinations(length).SelectMany(c => c.Permutations());

public static Stack<T> AsStack<T>(this IEnumerable<T> col) => new Stack<T>(col);

public static int IndexOf<T>(this T[] arr, T x) => Array.IndexOf(arr, x);
}``````