# CodeEval - Lucky Tickets challenge

This a solution to the CodeEval's challenge "Lucky Tickets".

After a failed attempt with brute-force calculations (no surprise here), I have tried to implement an algorithm that I found on StackOverflow.

The code runs without errors and my results match the output given in the example. However, when I submit the code for evaluation I obtain a "partially solved" status and a low score (17.5/100).

It is certain my code can be optimized (especially the use of dictionary which I believe takes a toll on the memory usage) however I have, yet, not found a better way. Also I do not understand the reason why this code only partially solves the problem.

public class LuckyTickets: ChallengeTemplate
{
/// <summary>
/// N = total ticket length (2, 4, 6, etc.)
/// Key : N/2
/// Value : Dictionary where
///             Key = calculated sum for the N/2 digits
///             Value = how many times this sum is found
/// </summary>
Dictionary<int, Dictionary<double, BigInteger>> allSums = new Dictionary<int, Dictionary<double, BigInteger>>();

public override void Execute()
{
// initialize the dictionary, f(0,0) = 1
allSums.Add(0, new Dictionary<double, BigInteger>());
allSums.Add(0, 1);

// each line contains an even number corresponding to the length of the ticket
foreach (var line in this.Lines)
{
int halflength = int.Parse(line) / 2;

if (!allSums.ContainsKey(halflength))
{
allSums.Add(halflength, new Dictionary<double, BigInteger>());
}

// calculate the maximum sum we can possibly find (eg. if ticket length = 6, max sum is 9+9+9 = 27)
double maxSumPossible = 9 * halflength;
// recursively, for each sum, find how many times we can calculate it with n digits
for (double i = maxSumPossible; i >= 0; i--)
{
GetSumCount(halflength, i);
}

BigInteger total = 0;
foreach (var kv in allSums[halflength])
{
total += (kv.Value * kv.Value);
}
Console.WriteLine(total.ToString("#"));
}
}

private BigInteger GetSumCount(int n, double sum)
{
// does this length exist?
if (!allSums.ContainsKey(n))
{
allSums.Add(n, new Dictionary<double, BigInteger>());
}

// if the count has already been calculated, return it
BigInteger count;
if (allSums[n].TryGetValue(sum, out count))
{
return count;
}
else if (n >= 1 && sum >= 0)
{
// apply algorithm:
// f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2)
count = 0;
for (int i = 0; i <= 9; i++)
{
count += GetSumCount(n - 1, sum - i);
}

allSums[n][sum] = count;

return count;
}
else
{
return 0;
}
}
}

• What performance you are getting for let's say, a length of 10 or 8 ? – Denis Jul 4 '16 at 12:23
• According to my tests, for 8 AND 10, I get results (correct and verifiable for 8) in 6ms and 117204 bytes. CodeEval and their 40 test cases give 82ms and 974848 bytes. – Slyvain Jul 4 '16 at 12:50
• I wonder why they call it a code-chalange. It's a math chalange and has not very much to do with coding. As soon as you get the right formula it's solved. – t3chb0t Jul 4 '16 at 12:58
• @t3chb0t: I would agree on most of those challenges (especially Project Euler) being basically an implementation of a mathematical formula. However in some cases (like the one I am trying to solve, imho) the challenge requires a different approach than just linear brute-force code. Here I would believe the formula is correct (given the examples and my results) but I am, honestly, sure of nothing! :-) – Slyvain Jul 5 '16 at 6:32
• To me the end of brute-force is the beginnig of math. Since to optimize it you need some formula which has to be mathematically correct or otherwise you might skip a case or two and get an invalid result we're back to math ;-] – t3chb0t Jul 5 '16 at 9:16