 # maia13's solution

## to Alphametics in the C# Track

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

#### Note:

This exercise has changed since this solution was written.

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.

## 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.2.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_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);
}
}``````

### Alphametics.cs

``````﻿using System;
using System.Linq;
using System.Collections.Generic;

public static class Alphametics
{
public static IDictionary<char, int> Solve(string equation)
{
var equations = equation.Parse();
return equations.Resolve();
}

private static bool IsDistinct(this (Variable Var, int Value) newValue, int?[] solution, Dictionary<Variable, int> variableIndex)
{
if (!(newValue.Var is Letter))
return true;

return variableIndex
.Where(kv => kv.Key is Letter)
.All(kv => !solution[kv.Value].HasValue || solution[kv.Value].Value != newValue.Value);
}

private static Dictionary<Variable, int> ToDictionary(this int?[] solution, Dictionary<Variable, int> variableIndex)
=> variableIndex
.Where(kv => solution[kv.Value].HasValue)
.ToDictionary(kv => kv.Key, kv => solution[kv.Value].Value);

private static bool IsEqualToZero(this (int Coef, Variable Var)[] equation, int?[] solution, Dictionary<Variable, int> variableIndex)
{
var solutionDict = solution.ToDictionary(variableIndex);
return equation.Aggregate(0, (acc, curr) => acc + solutionDict[curr.Var] * curr.Coef) == 0;
}

private static int?[][] AggregatePossibleSolutions(this int?[][] solutions, (int Coef, Variable Var)[] equation, Dictionary<Variable, int> variableIndex)
{
var resultSolutions = solutions;
foreach (var member in equation)
{
var vi = variableIndex[member.Var];
if (solutions.First()[vi].HasValue)
continue;

var res = resultSolutions
.Join(member.Var.Candidates, x => true, x => true, (solution, newVal) => (solution: solution.ToArray(), newVal))
.Where(x => (member.Var, x.newVal).IsDistinct(x.solution, variableIndex))
.ToList();

res.ForEach(x => x.solution[vi] = x.newVal);

resultSolutions = res
.Select(x => x.solution)
.ToArray();
}

return resultSolutions
.Where(solution => equation.IsEqualToZero(solution, variableIndex))
.ToArray();
}

private static bool Fits(this int?[] solution, Dictionary<char, int> expectedSolution, Variable[] variables)
{
return variables
.Where(v => v is Letter)
.Cast<Letter>()
.Zip(solution, (v, s) => (letter: v, value: s))
.Where(x => x.value.HasValue)
.All(x => expectedSolution[x.letter.Chr] == x.value.Value);
}

private static IDictionary<char, int> Resolve(this IEnumerable<(int Coef, Variable Variable)[]> equations)
{
var variables = equations.SelectMany(eq => eq.Select(x => x.Variable)).Distinct().ToArray();
var variableIndex = variables.Select((v, i) => (v, i)).ToDictionary(x => x.v, x => x.i);
var solutions = new int?[][] { variables.Select(v => (int?)null).ToArray() };
equations = equations.OrderBy(eq => eq.Where(x => x.Coef > 0).Sum(x => x.Coef)).ToList();
// equations = equations.OrderBy(eq => eq.Where(x => x.Coef > 0).Count()).ToList();

foreach (var equation in equations)
{
solutions = solutions.AggregatePossibleSolutions(equation, variableIndex);

if (solutions.Length == 0)
break;
}

if (solutions.Length == 0)
throw new ArgumentException("No solution.");

if (solutions.Length > 1)
throw new ArgumentException("More than 1 solutions.");

return solutions
.First()
.Select((m, i) => (Var: variables[i], Value: m))
.Where(x => x.Var is Letter)
.ToDictionary(x => ((Letter)x.Var).Chr, x => x.Value.Value);
}

private static IEnumerable<IEnumerable<(int Coef, char Ch)>> Transform(this IEnumerable<(int Coef, char[] Word)> words)
{
var i = 0;
while (true)
{
var lst = new List<(int Coef, char Ch)>();
foreach (var x in words)
{
if (x.Word.Length > i)
}
if (!lst.Any())
yield break;

yield return lst;
i++;
}
}

private static IEnumerable<(int Coef, Variable Variable)> AppendOverflows(this IEnumerable<(int Coef, Variable Variable)> equation, List<Overflow> overflows, int i)
{
if (i < 0 || i >= overflows.Count)
return equation;

if (i < overflows.Count - 1)
equation = equation.Append((-10, overflows[i]));

i--;
if (i < 0)
return equation;

return equation.Append((1, overflows[i]));
}

private static IEnumerable<(int Coef, Variable Variable)> SetOverflowLimits(this IEnumerable<(int Coef, Variable Variable)> equation, List<Overflow> overflows, int i)
{
if (i >= overflows.Count)
return equation;

var ordered = equation.OrderByDescending(x => x.Coef).ToList();

var value = 9;
var maxOf = ordered.Aggregate(0, (acc, x) =>
{
if (x.Variable is Letter && x.Coef > 0)
return acc + x.Coef * value--;
if (x.Variable is Overflow && x.Coef > 0)
return acc + x.Variable.Candidates.Max() * x.Coef;
return acc;
}) / 10;

value = 0;
var minOf = ordered.Aggregate(0, (acc, x) =>
{
if (x.Variable is Letter)
{
if (x.Coef > 0)
return acc + x.Coef * value++;

return acc + x.Coef * x.Variable.Candidates.Max();
}
if (x.Variable is Overflow && x.Coef > 0)
return acc + x.Variable.Candidates.Min() * x.Coef;

return acc;
}) / 10;

overflows[i].SetCandidates(minOf, maxOf);
return equation;
}

private static IEnumerable<(int Coef, Variable Variable)> GroupVariables(this IEnumerable<(int Coef, Variable Variable)> equation)
=> equation.GroupBy(x => x.Variable).Select(g => (g.Sum(x => x.Coef), g.Key));

private static IEnumerable<(int Coef, Variable Letter)> ToLetters(this IEnumerable<(int Coef, char Ch)> equation, Dictionary<char, Letter> letters)
=> equation.Select(m => (m.Coef, (Variable)letters[m.Ch]));

private static IEnumerable<(int Coef, Variable Variable)[]> Parse(this string equation)
{
var words = equation
.Split(new[] { " == " }, StringSplitOptions.RemoveEmptyEntries)
.Select((side, i) => (Coef: i == 0 ? 1 : -1, Side: side))
.SelectMany(x => x.Side.Split(new[] { " + " }, StringSplitOptions.RemoveEmptyEntries).Select(word => (x.Coef, Word: word.Reverse().ToArray())))
.ToList();

var letters = words.SelectMany(x => x.Word).Distinct().ToDictionary(ch => ch, ch => new Letter(ch));
// First letter cannot be zero
words.Select(x => x.Word.Last()).Distinct().ToList().ForEach(x => letters[x].Cut(0));

var eqCount = words.Max(x => x.Word.Length);
var overflows = Enumerable.Range(0, eqCount).Select(i => new Overflow(i)).ToList();

var equations = words
.Transform()
.Select((eq, i) => eq
.ToLetters(letters)
.GroupVariables()
.Where(m => m.Coef != 0)
.AppendOverflows(overflows, i)
.SetOverflowLimits(overflows, i)
.ToArray()
)
.ToList();

return equations;
}

}``````

### Variable.cs

``````using System;
using System.Linq;
using System.Collections.Generic;

public class Variable
{
protected IEnumerable<int> candidates;

public IEnumerable<int> Candidates => this.candidates;

// Generates candidates from 0 to count-1
public Variable(int count)
=> this.candidates = Enumerable.Range(0, count).ToList();

public override string ToString()
=> \$"[{string.Join(", ", this.candidates.Select(x => x.ToString()))}]";

public void Cut(params int[] nums) => candidates = candidates.Except(nums);
}``````

### Letter.cs

``````using System;
using System.Collections.Generic;

public class Letter : Variable
{
public char Chr { get; private set; }

public Letter(char ch, int candidatesCount = 10) : base(candidatesCount) => this.Chr = ch;

public override string ToString() => \$"{this.Chr}:{base.ToString()}";
}``````

### Overflow.cs

``````using System;
using System.Linq;
using System.Collections.Generic;

public class Overflow : Variable
{
public int Num { get; private set; }

public Overflow(int num) : base(0) => this.Num = num;

public override string ToString() => \$"{this.Num}:{base.ToString()}";

public Overflow SetCandidates(int start, int end)
{
this.candidates = Enumerable.Range(start, end - start + 1);
return this;
}
}``````