I love my failure - timeout code on 518 Coin change 2

June 21, 2019

Introduction

It is so easy to write a dynamic programming solution for Coin change 2. But I spent over one hour to mess with a bug and then fixed the code, my solution has timeout issue. What should I do at the very beginning? Design, show concern about time efficiency, dynamic programming bottom up, more case study on example.

Efficiency

I spent time to learn how to write basic things like copy list using C#, copy list with nested list using C#. I have so much fun to work on them, and I like to write a blog to share it as well.

But in reality I should spend time to learn more important things.

I love to solve a complicated problem. I learn a few things through my practice. Here is the post.

Every day I need to write some code to warm up, even though the code fails to pass online judge, but I enjoy to implement the idea, and learn from the failure.

Here is the link.

C# First practice with timeout issue in 2019

It is a good practice since I have to learn how to write a List<List<int>> and also make the copy list work without using same address in the nested list.

Here are highlights:

1. The idea is to brute force all possible sequences, including duplicate ones first;
2. Next step is to remove the duplicate ones by looking up hashset including all keys for each sequence.

Here are failed test cases caught by online judge, I was surprised to learn that I need to work on those issues one by one.

1. 3, [1, 2, 5], the answer should be 2, not 3
2. 0, [] should be 1, not 0

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _518_Coin_Change_2
{
    class Program
    {
        static void Main(string[] args)
        {
           // var result = Change(3, new int[]{1, 2, 5}); // should be 2
           // var result2 = Change(5, new int[] { 1, 2, 5 }); // should be 3
            var result3 = Change(3, new int[]{2});
        }

        /// <summary>
        /// 518 coin change 2
        /// first get all sequences with duplicate first, and then
        /// remove duplicate count 
        /// 
        /// Time out: 
        /// 500, [1, 2, 5]
        /// </summary>
        /// <param name="amount"></param>
        /// <param name="coins"></param>
        /// <returns></returns>
        public static int Change(int amount, int[] coins)
        {
            if (coins == null || amount < 0)
                return 0;

            if (amount == 0) // caught by online judge: 0,[] should be 1, not 0
                return 1; 

            var F = new int[amount + 1];            
            
            var sequences = new Dictionary<int, List<List<int>>>();
            F[0] = 0;
            sequences.Add(0, new List<List<int>>());

            for (int target = 1; target < amount + 1; target++)
            {
                var newList = new List<List<int>>();
                foreach (var coin in coins)
                {
                    if (coin > target)
                        continue;

                    var search = target - coin;
                    if (!sequences.ContainsKey(search))
                        continue;
                    var list = sequences[search];
                    //var copyList = new List<List<int>>(list); // caught by online judge
                    var copyList = new List<List<int>>();
                    foreach (var subList in list)
                    {
                        var copySubList = new List<int>(subList);
                        copyList.Add(copySubList);
                    }

                    if (copyList.Count == 0)
                    {
                        if (coin == target) // caught by failed test case: 3, [2] should be 0, return 1 instead
                        {
                            var subList = new List<int>(); // caught by debugger
                            subList.Add(coin);
                            copyList.Add(subList);
                        }
                    }
                    else
                    {                        
                        foreach (var sublist in copyList)
                        {
                            sublist.Add(coin);
                        }
                    }

                    newList.AddRange(copyList);
                }

                sequences.Add(target, newList);
            }

            var result = sequences[amount];
            // now it is time to remove duplicate count 
            var hashset = new HashSet<string>();
            int count = 0; 
            foreach (var subList in result)
            {
                // counting sort
                var values = new int[coins.Length];
                var lookupMap = new Dictionary<int, int>();
                for (int i = 0; i < coins.Length; i++)
                {
                    lookupMap.Add(coins[i], i);
                }

                foreach (var value in subList)
                {
                    values[lookupMap[value]]++;
                }

                var key = string.Join("-", values);
                if (hashset.Contains(key))
                    continue;
                hashset.Add(key);
                count++;
            }

            return count; 
        }
    }
}