3
\$\begingroup\$

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[0].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;
         }
      }
   }
\$\endgroup\$
  • \$\begingroup\$ What performance you are getting for let's say, a length of 10 or 8 ? \$\endgroup\$ – Denis Jul 4 '16 at 12:23
  • \$\begingroup\$ 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. \$\endgroup\$ – Slyvain Jul 4 '16 at 12:50
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – t3chb0t Jul 4 '16 at 12:58
  • \$\begingroup\$ @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! :-) \$\endgroup\$ – Slyvain Jul 5 '16 at 6:32
  • 2
    \$\begingroup\$ 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 ;-] \$\endgroup\$ – t3chb0t Jul 5 '16 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.