April 15th, 2014

Google Code Jam 2014 Solution - Magic Trick

This is the first in a series of posts where I'm going to go in depth on how to solve the Google Code Jam questions. In most cases I'll use the raw code I submitted but I may make some editorial edits if I feel the code is particularly hacky (CodeJam favours speed mostly over beauty).

Problem

The first question revolved around a magician with a particularly easy magic trick. He arranged 16 cards in a 4 by 4 square and asked a chosen audience member to pick one card and say the row it was in. He then re-arranged the cards and asked the audience member to pick the row it was in again and revealed what the card was.

The secret was simple, the magician just put all four cards from the selected row into different rows for the second go and found the card that appeared in both. Solving the problem just meant we needed to find the intersection of the two chosen rows (the card that appears in both).

Representation

First thing that came into my head was how to represent the data in the program. The most obvious would be a 4x4 array of numbers for each time the magician shuffled. The corresponding selected rows would be held as numbers so they could be queried by accessing the array at grid1[row-1].

Using this model makes our solution easier as well as we can leverage C#'s excellent Linq libraries on our arrays and use grid1[row1-1].intersect(grid2[row2-1]) to cleanly return the intersection. If the amount of items returned is 0 then the audience member has cheated. If its 1 then the magician has guessed correctly. If its more than this then the magician has made a mistake re-arranging his cards (0 could also mean this but the specification of the problem prioritised 0 as audience cheating).

Solution

Just a quick few notes. I figured casting to numeric types wasn't needed as the comparison did not involve any sort of operators apart from equals so saved a few lines of code. The ReadLn() and ReadArray() functions you will also see alot more of in the next few solutions.

using System.IO;
using System.Linq;

namespace SDX.GCJ.MagicTrick
{
    class Program
    {

    private static StreamReader input;
    private static StreamWriter output;

    static int ReadLn()
    {
        return int.Parse(input.ReadLine());
    }

    static string[] ReadArray()
    {
        return input.ReadLine().Split(' ');
    }

    static void Main(string[] args)
    {

        input = new StreamReader("in.txt");
        output = new StreamWriter("out.txt", false);

        var cases = ReadLn();

        for (int i = 1; i <= cases; i++)
        {

            var row1 = ReadLn();

            var grid1 = new string[4][];
            var grid2 = new string[4][];

            grid1[0] = ReadArray();
            grid1[1] = ReadArray();
            grid1[2] = ReadArray();
            grid1[3] = ReadArray();

            var line1 = grid1[row1-1];

            var row2 = ReadLn();

            grid2[0] = ReadArray();
            grid2[1] = ReadArray();
            grid2[2] = ReadArray();
            grid2[3] = ReadArray();

            var line2 = grid2[row2-1];

            var intersect = line1.Intersect(line2).ToArray();

            string outputstr = "Case #" + i + ": ";

            if (intersect.Length == 1)
            {
                output.WriteLine(outputstr + intersect[0]);
            }
            else if (intersect.Length > 1)
            {
                output.WriteLine(outputstr + "Bad magician!");
            }
            else
            {
                output.WriteLine(outputstr + "Volunteer cheated!");
            }



        }

        output.Close();


    }

    }
}
comments powered by Disqus