# artemkorsakov's solution

## to Alphametics in the C# Track

Published at Mar 16 2019 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

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;

public static class Alphametics
{
public static IDictionary<char, int> Solve(string equation)
{
var members = GetMembers(equation);
var terms = members[0].Split("+");
var result = members[1];
CheckEquality(terms, result);
Array.Sort(terms, StringComparer.InvariantCulture);
var possibleValues = new PossibleValues(equation.Where(char.IsLetter).Distinct());
possibleValues.CheckFirstLetterInResult(terms, result);

while (!possibleValues.IsSuccess())
{
var tmpPv = possibleValues.GetPossibleValues();
var candidateChar = tmpPv.Keys.OrderByDescending(k => tmpPv[k].Count).First();
var candidateNum = tmpPv[candidateChar][0];
var tmpDics = possibleValues.GetPossibleDictionaries(candidateChar, candidateNum);
foreach (var tmpDic in tmpDics)
{
if (IsCorrect(tmpDic, terms, result))
{
return tmpDic;
}
}
possibleValues.Remove(candidateChar, candidateNum);
}

return possibleValues.IsSuccess() ? possibleValues.GetResult() : throw new ArgumentException("No solution");
}

private static bool IsCorrect(Dictionary<char, int> tmpDic, IEnumerable<string> terms, string result)
{
var numResult = result;
foreach (var key in tmpDic.Keys)
{
numResult = numResult.Replace(key + "", tmpDic[key] + "");
}
var sum = long.Parse(numResult);

var prevTerm = "";
var prevNumber = 0L;
foreach (var term in terms)
{
if (!prevTerm.Equals(term))
{
prevTerm = term;
var number = term;
foreach (var key in tmpDic.Keys)
{
number = number.Replace(key + "", tmpDic[key] + "");
}
prevNumber = long.Parse(number);
}

sum -= prevNumber;
if (sum < 0)
{
return false;
}
}
return sum == 0;
}

/// <summary>
/// Possible values for letters.
/// </summary>
internal class PossibleValues
{

internal PossibleValues(IEnumerable<char> chars)
{
_possibleValues = chars.ToDictionary(c => c, i => new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });
}

internal bool IsSuccess()
{
return _possibleValues.Values.All(v => v.Count == 1);
}

/// <summary>
/// Returns a list of possible dictionaries under the assumption that the specified character is equal to the specified value.
/// </summary>
internal List<Dictionary<char, int>> GetPossibleDictionaries(char letter, int possibleValue)
{
var result = new List<Dictionary<char, int>>();
var keysSortedByCountOfValues = _possibleValues.Keys.OrderBy(k => _possibleValues[k].Count);
foreach (var key in keysSortedByCountOfValues)
{
var values = key == letter ? new List<int> { possibleValue } : _possibleValues[key];
if (result.Count == 0)
{
foreach (var i in values)
{
result.Add(new Dictionary<char, int> { [key] = i });
}
}
else
{
var tmp = new List<Dictionary<char, int>>();
for (var j = 0; j < result.Count; j++)
{
var curDic = result[j];
var curValues = values.Where(v => !curDic.ContainsValue(v)).ToList();
if (curValues.Count == 0)
{
result.Remove(curDic);
continue;
}

foreach (var curValue in curValues)
{
if (!curDic.ContainsKey(key))
{
}
else
{
var newDictionary = curDic.ToDictionary(entry => entry.Key,
entry => entry.Value);
newDictionary.Remove(key);
}
}
}
}
}
return result
.Where(dic => dic.Keys.Count == _possibleValues.Keys.Count)
.ToList();
}

internal Dictionary<char, int> GetResult()
{
return _possibleValues.ToDictionary(c => c.Key, i => i.Value[0]);
}

internal Dictionary<char, List<int>> GetPossibleValues()
{
return _possibleValues;
}

/// <summary>
/// Set the only possible value for the character.
/// </summary>
/// <param name="ch"></param>
/// <param name="val"></param>
internal void Set(char ch, int val)
{
_possibleValues[ch] = new List<int> { val };
foreach (var key in _possibleValues.Keys.Where(k => k != ch))
{
Remove(key, val);
}
}

/// <summary>
/// Remove value from the list of possible.
/// If nothing is left then throw the exception.
/// If only one is left then remove it from the rest chars.
/// </summary>
internal void Remove(char ch, int val)
{
if (!_possibleValues[ch].Contains(val))
{
return;
}

_possibleValues[ch].Remove(val);
if (_possibleValues[ch].Count == 0)
{
throw new ArgumentException("No solution");
}

if (_possibleValues[ch].Count == 1)
{
foreach (var key in _possibleValues.Keys.Where(k => k != ch))
{
Remove(key, _possibleValues[ch][0]);
}
}
}

// The leading digit of a multi-digit number must not be zero.
internal void RemoveLeadingZero(string[] terms, string result)
{
Remove(result[0], 0);
foreach (var ch in terms.Select(t => t[0]).Distinct())
{
Remove(ch, 0);
}
}

internal void CheckFirstLetterInResult(string[] terms, string result)
{
var maxSum = terms.Select(t => (long)Math.Pow(10, t.Length)).Sum();
var maxSumStr = maxSum.ToString();
if (maxSumStr.Length > result.Length)
{
return;
}

if (maxSumStr.StartsWith("1"))
{
Set(result[0], 1);
}
else
{
for (var i = (int)char.GetNumericValue(maxSumStr[0]) + 1; i < 10; i++)
{
Remove(result[0], i);
}
}
}
}

/// <summary>
/// Get the members of the equation.
/// If there are more than 10 letters then there is no solution.
/// </summary>
private static string[] GetMembers(string equation)
{
equation = equation.Replace(" ", "");
if (equation.Where(char.IsLetter).Distinct().Count() > 10)
{
throw new ArgumentException("No solution");
}

var members = equation.Replace(" ", "").Split("==");
if (members.Length != 2)
{
throw new ArgumentException("Equality must be one");
}

return members;
}

/// <summary>
/// The length of each term on the left of the equation must not be longer than the length of the result.
/// If one member is left and right then the task has no unique solution.
/// </summary>
private static void CheckEquality(IReadOnlyList<string> terms, string result)
{
if (terms.Any(t => t.Length > result.Length))
{
throw new ArgumentException("No solution");
}

if (terms.Count == 1)
{
throw new ArgumentException(terms[0].Equals(result) ? "More than one solution" : "No solution");
}
}
}``````