Advent Of Code Day 13 Reflections

Today’s advent of code challenge was a lot of fun. It’s always fun when a brute force attempt can be reduced to a mathematical equation. And it was a LLM that helped me find the right equation.

Once I broke down the problem and parsed the input file into a structure, I set about trying to solve the numbers. Each problem set contains three coordinates and the problem can be represented by Ax + By = P. Here, x and y are the number of times we need to advance the coordinates A and B to reach the prize P. It’s a equation with two variables and I didn’t know a generic solution. A bit of searching I did pointed me to a refactored equation that would let me calculate x for different values of y. (It’s simple: x = (P-By)/A.) This still needs a loop, of course but it’s a better representation.

So, I started writing the function:

func solveEquation(ax, ay, bx, by, px, py int64) (int64, int64) {        

And I pressed Cmd+I to let Amazon Q complete it (free version). It generated:

	// Solve system of equations:
	// ax * t + bx * s = px
	// ay * t + by * s = py

	// Using Cramer's rule
	det := ax*by - ay*bx
	if det == 0 {
		return 0, 0 // No unique solution
	}

	t := (px*by - py*bx) / det
	s := (ax*py - ay*px) / det

	return t, s
        

The key thing here was the reference to Cramer’s rule. I looked it up and it seemed exactly the mathematical solution I was hoping for. I ran it through the test and it worked. I still had to satisfy another condition that these values can’t be greater than 100.

But I wasn’t done. With the actual test problem, there were failures and I looked at the equations again to see that this doesn’t only give integer solutions. So I had to only accept the values of t and s when they are integers. I started editing the code and Amazon Q again prompted.

	t := (px*by - py*bx) // I removed the division here
	s := (ax*py - ay*px)  // and moved it to the return line.

	if t%det != 0 || s%det != 0 { // I started typing the block and AI completed it.
		return 0, 0 // No integer solution
	}

	return t / det, s / det
        

This worked and passed all tests. When I had to change this for part 2 where the numbers increased by 10 Trillion, it calculated the numbers in a jiffy.

Imagine if I had written a loop and I had to adjust variables until I reached 10 Trillion! That was, of course, what the challenge was going for (another such challenge was day 11). This shows why approaching computer science problems from a mathematical perspective is important. And since we don’t have a background in mathematics, this shows how AI can help us.

So, takeaways:

• Try to reduce the problem to a mathematical construct.
• Use AI as a search engine. How exactly you do that depends on the interface. In my case, I used the autocomplete interface. I invoked it by pressing Cmd+I which asks for a prompt. You might have also used a chat interface.
• I used a free model and I had to work with the limited context. But even larger context can lead to mixed results. You would need expensive models for that and free models probably won’t cut it. My experience with paid models for generating complete programs is mixed as well. It’s much better to let AI take care of very specific problems in your code base rather than let it generate a complete program from a problem statement. I did have the problem statement in README.md that might have gotten into the context.
• Again, depending on the context length, AI might not account for everything. In my case, part 1 requirements were to discard values above 100 and it didn’t account for that (this is trivial though and I wouldn’t need AI for that anyway). But the other requirement to discard non-integer values didn’t get implemented. Of course, this was not explicitly mentioned in the problem statement. This was something that we had to deduce from the requirements.
• All this in line with the common understanding of LLM models for code generation today.
• Use it for specific problems and questions.
• Think of it as a sophisticated search engine that generates code rather than returning results.
• Because it is a search engine, it can’t help you for truly novel problems. In that case, reduce or rephrase the problem into something that might have been solved before. Then adjust the generated code if required.