Despite the eighty-hour weeks, the relatively low pay, and the constant threat of being whipped if you don’t code fast enough, there’s something appealing about developing videogames professionally. After all, if videogames are superfun, then being immersed in them fourteen hours a day is basically heaven.

Of course, I never had a real desire to find out and ended up sticking with “normal” programming throughout my career. While I could always code whatever I wanted to do on the side, I never thought I’d ever get paid to write a videogame. That is, until I got paid to write this:

Obviously, this mini-game is not very exciting… or even original. It’s based on old, handheld electronic puzzle called Lights Out, and is a fun way to kill a couple minutes. Which, as it so happens, is about how long it takes to install BuildMaster on a slower computer when you pick the integrated SQL Server database. And that’s why it’s the installer.

The game itself is relatively easy to program: you have a square array of Boolean-like elements (usually 25 elements) and a method to toggle the array that looks something like this:

int GRID_SIZE = 5
bool LIGHT_ARY[] = new bool[GRID_SIZE * GRID_SIZE];

void ToggleLight(int index)
{
    int colIdx = index % GRID_SIZE;
    int rowIdx = index / GRID_SIZE;

    if (colIdx > 0) LIGHT_ARY[index-1] = !LIGHT_ARY[index-1]; //top
    if (rowIdx < GRID_SIZE - 1) LIGHT_ARY[index + GRID_SIZE] = !LIGHT_ARY[index + GRID_SIZE]; //right
    if (colIdx < GRID_SIZE - 1) LIGHT_ARY[index + 1] != LIGHT_ARY[index + 1]; //bottom
    if (rowIdx > 0) LIGHT_ARY[index - GRID_SIZE] != LIGHT_ARY[index - GRID_SIZE]; //left
}

Here’s the C# code I wrote (it includes an .exe, too), though I’m sure you could whip this up in the language of your choice in a few minutes. The particular variant I wrote is always solvable in at most five moves, but that’s not always the case.

Anyway, writing a Lights-Out minigame is not the point of today’s challenge. Instead, today’s challenge is to programmatically solve one.

Bring Your Own Code

While there are certainly solutions based on linear algebra and graph theory, those tend to be pretty boring… especially if you’re not a mathematician. So, in the tradition of BYOC, the goal should not be to solve this in the most efficient manner, but in the manner that’s the most fun for you.

The input should be:

  • Easy – a Boolean array of length 25 that represent a solvable lights out game (or similar UI)
  • Medium – a Boolean array of length 25 with random values
  • Hard - a Boolean array with a square length with random values

The output should be:

  • Easy – the list of indexes needed to toggle to solve (or similar UI)
  • Medium/Hard – an indicator of whether it’s a valid solution and, if so, the list of indexes that need to be toggled

I've already included my solution in the solution zip file. It will always solve it in exactly five moves.