Google code jam qualifying round

18 minute read

The google code jam qualifying round ended a few hours ago. I will talk about it and i guess show my answers. I like doing the contest for something to think about but I am not really a algorithms wizard. I think they have posted the answers, and if your looking for the absolute correct answers this isn’t the blog. I didn’t make it to the next round (to advance to the next round you needed 25 points and I had 10). I haven’t read googles posted answers to the problems.

The contest had 4 problems

For the first problem. I thought it sounded like a graph my idea was to make a graph of all the possible pancake flips, starting with the perfect answer and working my way outwards in a breadth first search type of way. It worked for the small test case, but failed for the large test case. I was trying to think of a way of like pruning the sample space so i wouldnt have to store so many values, but I couldn’t think of a way doing it


/*
 * Hi google person reading this, 
 * how are you I hope your doing well. 
 * I think for this one i am going to try to make a graph of all the possible pancake flips , the bfs my way to answer, 
 * I think this will only work for the small test case, I have no idea how i would do the bigger case
 */

 public class PancakeFlipper
    {
        public static void Main(string[] args)
        {
            string[] lines = System.IO.File.ReadAllLines(@"C:\Users..\A-large (3).in");
            
            int testCases = int.Parse(lines[0]);
            int result;
            List<string> answers = new List<string>();
            for (int i = 0; i < testCases; i++)
            {
               
                result = getResult(lines[i + 1]);
                if (result < 0)
                {
                    answers.Add( $"Case #{i + 1}:  IMPOSSIBLE");
                }
                else
                {
                    answers.Add($"Case #{i + 1}: {result}");
                }

                System.IO.File.WriteAllLines(@"C:...p1out.txt", answers.ToList() );
            }

      }

        private static int getResult(string v)
        {
            string rowOfPancakes = v.Split(' ')[0];
            int flipperSize = int.Parse(v.Split(' ')[1]);

            string initialString = "";
            for (int i = 0; i < rowOfPancakes.Length; i++)
            {
                initialString += "+";
            }


            Queue<pancakeProgress> possibleConfigurations = new Queue<pancakeProgress>();
            HashSet<string> previouslyTriedSolution = new HashSet<string>();
            possibleConfigurations.Enqueue(new pancakeProgress(initialString, 0));
            pancakeProgress current;
            List<pancakeProgress> newStates;
            while (possibleConfigurations.Count > 0)
            {
                current = possibleConfigurations.Dequeue();

                if (current.valueOfString == rowOfPancakes)
                {
                    return current.numberOfFlips;
                }
                else if(!previouslyTriedSolution.Contains(current.valueOfString))
                {
                    previouslyTriedSolution.Add(current.valueOfString);
                    newStates = getAllPossibleNewPancakeFlips(current,flipperSize);
                    foreach (pancakeProgress p in newStates)
                    {
                        if (!previouslyTriedSolution.Contains(p.valueOfString))
                        {
                            possibleConfigurations.Enqueue(p);
                        }
                    }
                }
            }

            return -1; 
        }

        private static List<pancakeProgress> getAllPossibleNewPancakeFlips(pancakeProgress current,int flipper)
        {
            List<pancakeProgress> allPossible = new List<pancakeProgress>();
            string s = current.valueOfString;
            char[] s1 ;
            for (int i = 0; i < s.Length - flipper+1; i++)
            {
                s1 = s.ToArray();
                for (int j = 0; j < flipper; j++)
                {
                    if (s1[i + j] == '+')
                    {
                        s1[i + j] = '-';
                    }
                    else {
                        s1[i + j] = '+';
                    }

                }
                allPossible.Add(new pancakeProgress( new string(s1), current.numberOfFlips+1));
            }

            return allPossible;
        }
    }

    public class pancakeProgress
    {
        public string valueOfString { get; set; }
        public int numberOfFlips { get; set; }
        public pancakeProgress(string s, int i)
        {
            valueOfString = s;
            numberOfFlips = i;
        }
    }

For the next problem, Tidy Numbers i tried to turn it into a graph and do a depth first search on it, but again I was having to save too many values and couldn’t think of way of shrinking the sample space down enough to get it to fit in memory


/*
 * hi google person thanks for reading this one i did like dfs search on the space, i dont think it will work for the bigger case, but i guess ill try it
 */

namespace GoogleCodeJamQualifingRound2017
{
    class TidyNumbers
    {
        public static void Main(string[] args)
        {
            string[] lines = System.IO.File.ReadAllLines(@"C:...\B-large (1).in");

            int testCases = int.Parse(lines[0]);
            string result;
            List<string> answers = new List<string>();
            for (int i = 0; i < testCases; i++)
            {
                result = getResult(lines[i + 1]);
                answers.Add($"Case #{i + 1}: {result}");
               System.IO.File.WriteAllLines(@"C:\Users\Sai...\p2largeOut.txt", answers.ToList());
            }

        }

        private static string getResult(string v)
        {
          
            if (!isTidy(v))
            {

                Stack<string> listOfNums = new Stack<string>();
                string maxNum = "-1";
                string currentNum = "";
                int lastDigit = 0;
                for (int i = 1; i < 10; i++)
                {
                    listOfNums.Push(i.ToString());
                }
                BigInteger b = BigInteger.Parse(v);
                while (listOfNums.Count > 0)
                {
                    currentNum = listOfNums.Pop();
                    if (b.CompareTo(BigInteger.Parse(currentNum)) > 0)
                    {
                        lastDigit = int.Parse(currentNum[currentNum.Length - 1].ToString());
                        //lastDigit++;
                        while (lastDigit < 10)
                        {
                            listOfNums.Push(currentNum + lastDigit.ToString());
                            lastDigit++;
                        }
                    }
                    if (b.CompareTo(BigInteger.Parse(currentNum)) > 0 && BigInteger.Parse(currentNum).CompareTo(BigInteger.Parse(maxNum)) > 0)
                    {
                        maxNum = currentNum;
                    }
                }


                return maxNum;
            }
            return v;
        }

        private static bool isTidy(string v)
        {
            for (int i = 0; i < v.Length - 1; i++)
            {
                if (v[i] > v[i + 1])
                {
                    return false; 
                }
            }

            return true;
        }
    }
}

For the next Problem, Bathroom Stall I just did a brute force solution, but at this point i was tired. I thought it might have been some sort of tree problem, but I am not really sure. I actually had to do a 5k eariler in the morning, and my energy was drained, so i didn’t finish it. I dont think I would have been able to get enough points to make it to the next round

I didn’t do the last problem it seemed interesting, but i had no idea how to do it

If you competed in the contest how did you do? If you got through the qualifying round congrats.

Leave a Comment