Softwire Speed Coding Challenge – Question 1 Discussion


16 April 2012, by

previous article in series

Last time out, we set you the first question from our recent Speed Coding Challenge, giving you the opportunity to answer it yourselves and compare your efforts to our winning answer. Here’s question 1 again, just to remind you what it was!

Question 1 – Grid and row/column rotations

You have a four by four grid with a default starting configuration:

1    2    3    4
5    6    7    8
9    10   11   12
13   14   15   16

Define transformations on the grid as follows:

  • R1 means shift row 1 one space to the right, and wrap around, so starting from the original table, row 1 becomes {2, 3, 4, 1}
  • Similarly R2 changes row 2 to {6, 7, 8, 5}, etc.
  • C1-C4 do a similar thing on each column, i.e. {1, 5, 9, 13} becomes {5, 9, 13, 1}, etc.

So we have eight different transformations: R1 … R4, C1 … C4. How many distinct sequences of nine transformations result in the first column in the grid above changing from {1, 5, 9, 13} to {1, 2, 3, 4}?

Check: 102,048 sequences of nine transformations leave the first row unchanged.

Well, did you try and get a solution yourself? If you did, the answer you were looking for was 718. Here is Softwire’s winning solution, which took Matthew 24 minutes to submit!

Winning Solution – Submitted by Matthew Richards

static void Main(string[] args)
{
  int[] sequence = new[] {0,0,0,0,0,0,0,0,0};
  int checkResult = 0;
  int finalResult = 0;
  while (true)
  {
    int[][] grid = new[] {
      new[] { 1, 2, 3, 4 },
      new[] { 5, 6, 7, 8 },
      new[] { 9, 10, 11, 12 },
      new[] { 13, 14, 15, 16 }
    };

    // Apply transforms
    foreach(int transform in sequence)
    {
      if (transform < 4)
      {
        ApplyR(transform, grid);
      }
      else
      {
        ApplyC(transform - 4, grid);
      }
    }

    // Check result
    if (grid[0][0] == 1 && grid[0][1] == 2 && grid[0][2] == 3 && grid[0][3] == 4)
    {
      checkResult++;
    }
    if (grid[0][0] == 1 && grid[1][0] == 2 && grid[2][0] == 3 && grid[3][0] == 4)
    {
      finalResult++;
    }

    // Move onto the next transform
    for (int i=sequence.Length-1; i>=0; i--)
    {
      if (sequence[i] == 7)
      {
        sequence[i] = 0;

        if (i ==0)
        {
          Console.Out.WriteLine(checkResult);
          Console.Out.WriteLine(finalResult);
          Console.In.ReadLine();
          Environment.Exit(0);
        }
      }
      else
      {
        if (i==0)
        {
          Console.Out.WriteLine(sequence[i]);
        }
        sequence[i]++;
        break;
      }
    }
  }
}

static void ApplyR(int index, int[][] grid)
{
  var temp = grid[index][3];
  grid[index][3] = grid[index][2];
  grid[index][2] = grid[index][1];
  grid[index][1] = grid[index][0];
  grid[index][0] = temp;
}

static void ApplyC(int index, int[][] grid)
{
  var temp = grid[3][index];
  grid[3][index] = grid[2][index];
  grid[2][index] = grid[1][index];
  grid[1][index] = grid[0][index];
  grid[0][index] = temp;
}

Comments on the Winning Solution

There is a nice touch here which, while simple and obvious thinking about it now,isn’t so obvious in the heat of a speed coding battle! Matthew’s decision to keep the running total of the “Check” answer as well will have saved him time; about 50% if we assume that his solution worked first time! If a program is quite slow to run, that can add up to a big difference in how quickly you get a solution!

The code itself is quite simple and easy to read, method and variable names are short, but still sufficiently descriptive that you can figure out what they represent.

General Comments (C# focused)

There were two main approaches taken for this question:

  • An iterative approach, where you apply each transform to the original list and keep a running total of how many correct combinations there were
  • Apply every transform to a clone of the original grid and repeat recursively until all transformations have been performed

Of these approaches, even though the iterative solution ended up being the winner (and the more common design choice), the recursive approach produced faster (and sometimes cleaner) solutions as there are fewer operations to apply overall.

If you consider that an iterative approach is running through each operation in turn, it will be running through every possible permutation of transformations. Given there are 8 different transformation types and we are performing 9 transformations, this would mean over 134 million transformations are being performed!

In our recursive approach, we don’t need to re-apply operations where we’ve already computed the effect of a series of transformations. For example consider the following sequences of transformations – R1,R1,R1,R1,R1,R1,R1,R1,C1 and R1,R1,R1,R1,R1,R1,R1,R1,C2; only the last transformation is different.

A recursive approach can evaluate these sequences using 10 transformations; the starting 8, which are common to both sequences, and the final 2, which are different operations). The recursive approach would therefore only use just over 19 million transformations to get to a solution, a saving of around 85% in terms of processing!

Let us know how you did on this question and which approach you took in the comments!

next article in series

Tags: , , , , ,

Categories: Social, Softwire, Technical

«
»

4 Responses to “Softwire Speed Coding Challenge – Question 1 Discussion”

  1. It’s also worth noting that using “int[][]” for the grid, as Matthew did, is quite a bit slower than using “int[,]”. The difference is that accessing elements in the former requires following two pointers, whereas the latter needs only one.

  2. Rupert Wood says:

    A third approach – and the one I used on the night – is a variant on the second: rather than cloning the grid for each recursion, have each recursion undo its transform when complete i.e. apply the reverse transform to restore the grid to the state it found it in.

    This doubles the number of transforms I needed to do but means I need only one grid (or one per thread) for the whole computation, completely eliminating the memory allocation. It ended up running in about 15 seconds where cloning solutions took about a minute I think.

    All of these solutions are easily parallelisable too, and there are easy mechanisms to make loops parallel in .NET – e.g. Matthew could use Parallel.For for the first entry in his `sequence` array, allocating a separate copy per thread – but I don’t think anyone did on the night.

  3. Preeyan Parmar says:

    A meet-in-the-middle attack:

    1. Compute all possible finishing positions of (1,2,3,4) after sequences of five transformations, and how many such sequences get to each position.

    2. Compute all possible finishing positions of (1,2,3,4) after sequences of four *inverse* transformations, and how many such sequences get to each position.

    3. Count the number of matches from the results of the first two steps.

    Using Richard’s array hint and Rupert’s inversion trick, this finds the answer in under 0.1 seconds.

    (But it took me an hour to write…)

  4. Chris Harris says:

    Nice one Preeyan – that looks excellent and might well have won you a style point! And if we had asked for the answer from a larger grid then the time saved in running the program might have outweighed the extra programming time and given you all the points!


Leave a Reply

* Mandatory fields


− six = 3

Submit Comment