I'm starting to see what's going on here. The elves of 1518 have somehow procured a future book of classic programming algorithms. Today there was a little distraction in problem description around infinite spaces and equidistant points, but it boils down to a pixel fill algorithm. If you ever worked on a classic 1980s-90s style paint program you'll recognise it.

First let's make some geometric primitives:

data classPos(valx:Int,valy:Int)data classBox(valx:IntRange,valy:IntRange)enumclassDir{UP,DOWN,LEFT,RIGHT}typealiasManhattan=Int

For readable code we'll add some useful operations, using Kotlin's carefully limited operator overloading where appropriate:

We need a data model for our coordinates, and a parser. I know it's just two integers separated by a comma, but I hope by now you see what I mean by the One True Way of parsing text:

The last two lines make an infinite sequence of integers and zip it with the parsed coordinates so each coordinate gets a "name".

The problem talks about an infinite space, but the insight you need to solve it is that any area which reaches the edge of the "known" space is effectively infinite. The known space is the extent of the input coordinates in every direction, so let's compute that:

Breaking things down into tiny operations makes everything much easier to understand, means you're composing ideas at the same level of abstraction and frankly leaves fewer places for bugs to creep in.

We know the size of the space, now we need the area filling data model. A cell is either unclaimed, has a coordinate on it, is claimed by a single coordinate or is equidistant to two or more coordinates. It's a sum type!

And we represent the space with a simple two-dimensional array of these:

data classSpace(valbox:Box){valcells:Array<Array<Cell>>init{valwidth=box.x.endInclusive-box.x.start+1valheight=box.y.endInclusive-box.y.start+1cells=Array<Array<Cell>>(height){Array<Cell>(width){Cell.Unclaimed}}}

Now the fill algorithm. I've written this before, so I'm happy to say once it compiled this actually gave the correct result first time. The only change I had to make was to change it from stack-based recursion to a heap-based stack of pending operations to cope with the size of the main input data.

Recursive functions are often best implemented with a helper and a "starter" method.

In the original version the inner fill() helper called itself recursively. Now it returns the next set of cells to fill, and the outer loop processes these.

The first check is that we've remained inside the bounding box. You could note here that the affected ID has an infinite area but I feel that's conflating the fill and area check parts of the problem. Merge them later if performance is an issue.

The when block looks at the current state of the cell and computes what to do. If the cell is unclaimed or closer to the current coordinate, we claim it. If it's the same distant it becomes Equidistant. Some of the cases leave it alone.

Finally if we've made a change to the cell, update the 2D array and continue to the surrounding set of cells.

Part 1

The question in part 1 is to determine the largest finite area. We need a sum type!

This is not the most efficient form of the algorithm by any means. It will check the same cell many times during a pass. It runs in 1.5 seconds on my Thinkpad though.

Part 2

Part 2 was a bit disappointing as it didn't really build on the first much. I refactored the Space class to be generic in its content, so I could make a space of manhattan distances. Filling it was easy:

## re: AoC Day 6: Chronal Coordinates VIEW POST

FULL DISCUSSIONFrom my github:

I'm starting to see what's going on here. The elves of 1518 have somehow procured a future book of classic programming algorithms. Today there was a little distraction in problem description around infinite spaces and equidistant points, but it boils down to a pixel fill algorithm. If you ever worked on a classic 1980s-90s style paint program you'll recognise it.

First let's make some geometric primitives:

For readable code we'll add some useful operations, using Kotlin's carefully limited operator overloading where appropriate:

We need a data model for our coordinates, and a parser. I know it's just two integers separated by a comma, but I hope by now you see what I mean by the One True Way of parsing text:

The last two lines make an infinite sequence of integers and zip it with the parsed coordinates so each coordinate gets a "name".

The problem talks about an infinite space, but the insight you need to solve it is that any area which reaches the edge of the "known" space is effectively infinite. The known space is the extent of the input coordinates in every direction, so let's compute that:

Breaking things down into tiny operations makes everything much easier to understand, means you're composing ideas at the same level of abstraction and frankly leaves fewer places for bugs to creep in.

We know the size of the space, now we need the area filling data model. A cell is either unclaimed, has a coordinate on it, is claimed by a single coordinate or is equidistant to two or more coordinates. It's a sum type!

And we represent the space with a simple two-dimensional array of these:

Now the fill algorithm. I've written this before, so I'm happy to say once it compiled this actually gave the correct result first time. The only change I had to make was to change it from stack-based recursion to a heap-based stack of pending operations to cope with the size of the main input data.

Things to note:

`fill()`

helper called itself recursively. Now it returns the next set of cells to fill, and the outer loop processes these.`when`

block looks at the current state of the cell and computes what to do. If the cell is unclaimed or closer to the current coordinate, we claim it. If it's the same distant it becomes`Equidistant`

. Some of the cases leave it alone.## Part 1

The question in part 1 is to determine the largest finite area. We need a sum type!

To calculate the area for a coordinate ID I took a very simple approach:

This is not the most efficient form of the algorithm by any means. It will check the same cell many times during a pass. It runs in 1.5 seconds on my Thinkpad though.

## Part 2

Part 2 was a bit disappointing as it didn't really build on the first much. I refactored the

`Space`

class to be generic in its content, so I could make a space of manhattan distances. Filling it was easy:Then the size of the area under the threshold is

`space.count { d -> d < max }`

I enjoyed this one a lot, which was pleasing after yesterday. Roll on the next...