Kattis Challenge: A Flea on a Chessboard
SPOILER ALERT: This post contains an answer for an online programming challenge (https://open.kattis.com/problems/fleaonachessboard). Try it yourself first :)
Today I will recount my attempt to solve a “hard”-ranked problem, from my alma mater, the University of Waterloo - of all places.
Dis gon be gud.
The problem is deceptively simple. Or maybe it really is simple and I’m overthinking it. Either way, the idea is that you have a flea sitting somewhere on a chess board, where each square on said chess board has a side length of S millimeters. Our flea jumps up and to the right by a fixed amount each hop. Our job is to figure out how many hops it takes for the flea to land on a white square.
The first question is whether there’s an analytical solution for this; Some kind of algorithm we can stick the parameters into that would tell us the right answer on the first shot. I couldn’t think of one, so I decided to do the obvious (to a programmer) thing: Make the flea jump until we detect a white square.
What colour square are we on?
The first step is to figure out what colour square the flea is on for a given position. We know that the bottom left square is black, and we know that it alternates in colour both up and across:
enum Colour
{
Black,
White
}
static bool IsEvenSquares(int squareLength, int val)
{
int nHops = val / squareLength;
return nHops % 2 == 0;
}
static Colour GetColourAtPosition(int squareLength, int x, int y)
{
if ((x % squareLength == 0) || (y % squareLength == 0))
{
return Colour.Black;
}
if (IsEvenSquares(squareLength, x))
{
return IsEvenSquares(squareLength, y) ? Colour.Black : Colour.White;
} else
{
return IsEvenSquares(squareLength, y) ? Colour.White : Colour.Black;
}
}
Simply put, we see if we’re on an even or odd square with respect to the first in both X and Y, and we use that to determine the colour of the square we’re on. Also, the boundaries between squares count as black, so we add a check for that.
How many hops does it take?
We figure this out with a simple loop, of course!
int posX = x;
int posY = y;
int nHops = 0;
int startDistanceX = GetDistanceFromSquareStart(squareLength, x);
int startDistanceY = GetDistanceFromSquareStart(squareLength, y);
Colour currentColour = GetColourAtPosition(squareLength, x, y);
if (currentColour == Colour.Black)
{
nHops++;
posX += dx;
posY += dy;
while (true)
{
currentColour = GetColourAtPosition(squareLength, posX, posY);
if (currentColour == Colour.White)
{
break;
}
nHops++;
posX += dx;
posY += dy;
}
}
But what if we never hit a white square? Well, the U of Waterloo doesn’t disappoint: The simple question of “when do I stop?” bamboozled, perplexed, and dare I say confuddled me for quite some time.
The flea stops here…or here?
So the first thing that jumps out here is that at some point the flea’s hop pattern will repeat, and continuing the algorithm past that point would be a waste. But how do we calculate this “period”? I tried assuming that if the position with respect to the lower-left corner of the current square is the same as the one it started on, then our pattern has repeated anew. We can find this efficiently using the modulo operator:
static int GetDistanceFromSquareStart(int squareLength, int val)
{
return val % squareLength;
}
And our loop:
int posX = x;
int posY = y;
int nHops = 0;
int startDistanceX = GetDistanceFromSquareStart(squareLength, x);
int startDistanceY = GetDistanceFromSquareStart(squareLength, y);
bool startEvenX = IsEvenSquares(squareLength, x);
bool startEvenY = IsEvenSquares(squareLength, y);
Colour currentColour = GetColourAtPosition(squareLength, x, y);
if (currentColour == Colour.Black)
{
nHops++;
posX += dx;
posY += dy;
while (true)
{
currentColour = GetColourAtPosition(squareLength, posX, posY);
if (currentColour == Colour.White ||
(GetDistanceFromSquareStart(squareLength, posX) == startDistanceX && GetDistanceFromSquareStart(squareLength, posY) == startDistanceY)
{
break;
}
nHops++;
posX += dx;
posY += dy;
}
}
if (currentColour == Colour.White)
{
Console.WriteLine($"After {nHops} jumps the flea lands at ({posX}, {posY}).");
} else
{
Console.WriteLine($"The flea cannot escape from black squares.");
}
Seems easy enough so far. Running it against the sample data gave me all the correct answers. Let’s submit it!
Kattis: Wrong Answer
OK, don’t panic. Usually this just means we forgot an edge case. Ah! What if we start on a white square that’s at the edge of the board? It’s not technically a boundary between squares since there’s only the endless abyss on the other side:
static Colour GetColourAtPosition(int squareLength, int x, int y)
{
if ((x > 0) && (x % squareLength == 0) || (y > 0) && (y % squareLength == 0))
{
return Colour.Black;
}
if (IsEvenSquares(squareLength, x))
{
return IsEvenSquares(squareLength, y) ? Colour.Black : Colour.White;
} else
{
return IsEvenSquares(squareLength, y) ? Colour.White : Colour.Black;
}
}
Kattis: Wrong Answer
I thought about it for a while and…ran out of ideas. So I did what every self-respecting code monkey does, I Googled the issue. I came across a forum of users who attempted to solve this problem. There were a few posts about using a formula to calculate the maximum number of hops:
int maxHops = LCM(squareLength / GCD(squareLength, dx), squareLength / GCD(squareLength, dy));
And, a lonely post at the bottom with a single test case:
1000 0 499 500 1501: After 1003 jumps the flea lands at (501500, 1506002).
Sure enough, plugging the above case into my program: The flea cannot escape from black squares..
Defeated, I tried the above formula. The idea is to find the lowest common multiple of how many hops it takes to traverse a square in both X and Y. It makes sense to me, though it’s probably not something I would have come up with. I figured maybe my attempt at detecting when we’ve restarted the pattern was simply too pedestrian for this kind of mathematical problem. I modified the program to use the above formula and:
1000 0 499 500 1501
The flea cannot escape from black squares.
Uh-oh, looks like the industry best-practice of copying random code off of Google isn’t such a good idea after all! It turns out that forumla and my method both produced the same max hop count: 1000. But the flea lands on a white square after 1003 hops. What’s going on?
An Even Oddity
I added some more debug output to the program, printing the distance from the start of the current square as well as the current position. Sure enough, the position from the start repeats at 1000:
1000 0 499 500 1501
Jump 1 position (500, 2000) FromSquare: (500, 0)
Jump 2 position (1000, 3501) FromSquare: (0, 501)
Jump 3 position (1500, 5002) FromSquare: (500, 2)
...
Jump 1000 position (500000, 1501499) FromSquare: (0, 499)
Jump 1001 position (500500, 1503000) FromSquare: (500, 0)
Jump 1002 position (501000, 1504501) FromSquare: (0, 501)
Jump 1003 position (501500, 1506002) FromSquare: (500, 2)
If we start from position (500000, 1501499) the program correctly lands on the white square in 3 hops. So what gives? What does (500000, 1501499) have that (0, 499) doesn’t? Well, after a bit of head scratching, I realized that the key is in dy = 1501. Turns out, after 1000 hops, that little 1 in 1501 becomes a whole square! So at hop 1003, the Y is on an even square, whereas at hop 3, it was on an odd square. I had originally assumed that if the current position relative to the current square is identical to that of the start position, then the pattern has repeated. However, this is dead wrong: We also need to take into account whether the current square’s evenness is identical to that of the start:
bool startEvenX = IsEvenSquares(squareLength, x);
bool startEvenY = IsEvenSquares(squareLength, y);
...
if (currentColour == Colour.White ||
(GetDistanceFromSquareStart(squareLength, posX) == startDistanceX && GetDistanceFromSquareStart(squareLength, posY) == startDistanceY && IsEvenSquares(squareLength, posX) == startEvenX && IsEvenSquares(squareLength, posY) == startEvenY))
{
break;
}
Kattis: Accepted
Success!
As a bonus, I noticed that of the 3 C# attempts submitted so far, mine came in as the fastest at 0.06s execution time =]