AOC23 - 10 December
2023-12-10
After conceding myself a free day I could distance myself from the obsession of completing every day's puzzle. Today I was able to be productive and dedicate my time to other projects, and I have noticed that allotting my self some time ahead ahead of the task and work until the end regardless of the progress lifts pressure from the need to chase down the solution until I am exhausted and being able to still walk away with a sense of accomplishment.
That being said, now it is 21:30 and I will give myself time til 00:00 to work on today's challenge. I have already had a peak at the prompt in the morning. And must say that it is interesting enough for me, in terms of the problem that it presents. The algorithm itself is a typical instance of what I have called "the chess problem" on day 8. The solution to the problem (traveling salesman / maze backtracking) has been studied multiple times and there are existing solutions 'en masse'. I will not waste my time with finding my own implementation to solve the general puzzle, at least in regards of crunching through the main input. Instead I will use this as inspiration for my own little implementation.
So let's recap what I have decided. I will try to extract the essence of the daily challenge to interpret them in a graphical or interactive form (in retrospective I kind of regret that I have not done this right from the start for all of them). I have always been fascinated by visual representations of algorithms. Because it provides one central challenge: the representation of time and execution flow. While algorithm are chronological sequence of steps they usual happen within the frame of computation cycles, so fast that they are invisible to the human eye, and the reason why computers are useful in the first place.
The discrepancy of perception of time for humans and computers results in an architectural problem, especially in a functional programming language, which I intend to solve. The algorithm works on a data set, which needs to be presented to the viewer. To showcase the behavior of the algorithm, steps need to be produced for the user to follow, in terms of feedback. The temporal change of data needs to be reflected in the state of the program. While usually we store these changes within the stack of the scope of the currently executed function, this requires us to store these intermediate state changes in the global state (a state accessible to multiple functions). This also leads to a different setup for implementing the algorithm, into smaller self-contained functions, those that change the state and return that intermediate state and those that provide information about that state.
Today's Prompt
Day 10 Prompt
As far as I could tell, today's prompt is a grid of character representing a pipeline
- dots represent nothing (ground)
- there are vertical and horizontal pipes
- there are corner pipes that connect two wind directions (South, North, East and West) to each other, in terms of the grid that is (Down, Up, Left and Right) respectively
- There is an animal in the pipe denoted by a start position (Which needs to be replaced by the respective pipe according to its connection logic and neighbors)
- You have to determine the longest point in the pipe system based on its position, by counting the tiles (not the direct line) it requires to traverse to get there (This is the part I don't care about)
Here is how I will change the prompt. The input prompt is parsed to a grid of visual pipes. The user can click on one of the pipe tiles to place the animal. The animal will then step through the pipes randomly without going backwards! So essentially only when it is presented with multiple options, it will choose randomly. I will give myself time to learn and not pressure myself finding a solution for all of these feature in the next two hours.
Let's see how far I get
The pipe parsing pipeline
Sorry, I had to make this joke. When if not now?
So let's review the idea here, we need to go through all the lines and store a grid of values for each cell. Waaaait a moment... Haven't I solved this problem already? Let's steal the code.
So let's start with the interesting stuff
type alias Position = {x : Int, y : Int}
type Direction = Up | Down | Left | Right
type Pipe = Pipe Connection | AnimalOnPipe
type alias CellContent = Maybe Pipe
type alias Cell = {pos : Position, content : CellContent}
Now this is amazing. Since I modeled day 3 with the abstraction of Grid and Cell. I just have to change the definition of CellContent to Maybe Pipe instead of Maybe CharType, and the remaining code works. I now have just to solve the problem of displaying the cell, because the layouting of the grid has already been solved by my past grid abstraction. But I am getting ahead of myself. We still need to parse.
Again I will only show what has changed.
parseCell : Int -> Int -> Char -> Cell
parseCell rowId posOnRow char =
let
position = {x = posOnRow, y = rowId}
inside =
case char of
'-' -> Just <| Pipe (Left, Right)
'|' -> Just <| Pipe (Up, Down)
'F' -> Just <| Pipe (Right, Down)
'7' -> Just <| Pipe (Down, Up)
'J' -> Just <| Pipe (Up, Left)
'L' -> Just <| Pipe (Right, Up)
'S' -> Just AnimalOnPipe
_ -> Nothing
in
{ pos = position, content = inside }
And since everything is wrapped inside the abstract Maybe type, my display function still works. Producing this:
Now this is pretty amazing, if you ask me.
Displaying the pipes
So now on to displaying the pipes. I have done some visual research about pipe tilesets and found a free pipe set on open gameart. I have also seen a few examples of layered pipesets, where background pipes are displayed darker and smaller to signal the depth. I think I will implement this effect for the unconnected pipes aswell. Now I need to figure out how to render pipes loading in the tiles.
So my theory is that similarly to normal HTML i can use the img element and use the source attribute to link to my image. Let's see.
Yup
src : String -> Attribute msg
-- The URL of the embeddable content. For audio, embed, iframe, img, input, script, source, track, and video.
renderPipe : Pipe -> Html msg
renderPipe pipe =
let
sourceImage =
case pipe of
Pipe (Left, Right) -> "./images/pipe_horizontal.png"
Pipe (Up, Down) -> "./images/pipe_vertical.png"
Pipe (Down, Right) -> "./images/pipe_corner_bottom_right.png"
Pipe (Down, Left) -> "./images/pipe_corner_bottom_left.png"
Pipe (Up, Left) -> "./images/pipe_corner_top_left.png"
Pipe (Up, Right) -> "./images/pipe_corner_top_right.png"
_ -> ""
in
img
[src sourceImage]
[]
Very satisfying.
Now you notice that there is a pipe missing, where the animal is. I have to write the first puzzle piece of the prompt, namely replacing the missing piece with its logical piece.
replacePipe : Grid -> Maybe Pipe -> Maybe Pipe
replacePipe grid mpipe =
mpipe |>
Maybe.andThen
(\pipe ->
case pipe of
AnimalOnPipe -> Debug.todo "Implement replacement"
_ -> Just pipe
)
The Debug.todo function is amazing. It implements the semantics of a missing implementation with that of a comment avoiding compiler errors for mismatching or not existing code branch.
replacePipe : Grid -> Cell -> Maybe Pipe
replacePipe grid cell =
let
buildLogicalReplacement cellA =
let
neighbors =
getNeighbors grid cell |>
Maybe.values
getDirections cells =
let
horizontalNeighbors = List.filter (\a -> a.pos.x /= cell.pos.x) cells
verticalNeighbors = List.filter (\a -> a.pos.y /= cell.pos.y) cells
in
if List.length horizontalNeighbors == 2
then Just (Left, Right)
else if List.length verticalNeighbors == 2
then Just (Up, Down)
else
mapTuple
(\cellsOnSide ->
List.head cellsOnSide |>
Maybe.andThen
(\cellOnSide ->
case (cellOnSide.pos.x - cell.pos.x + 1, cellOnSide.pos.y - cell.pos.y + 1) of
(0, 1) -> Just Left
(2, 1) -> Just Right
(1, 0) -> Just Down
(1, 2) -> Just Up
_ -> Nothing
)
)
(horizontalNeighbors, verticalNeighbors) |> traverseMaybe
in
if List.length neighbors == 2
then getDirections neighbors |> Maybe.andThen (Pipe >> Just)
else Nothing
in
cell.content |>
Maybe.andThen
(\pipe ->
case pipe of
AnimalOnPipe ->
buildLogicalReplacement cell
_ -> Just pipe
)
This part
(0, 1) -> Just Left
(2, 1) -> Just Right
(1, 0) -> Just Down
(1, 2) -> Just Up
Might seem confusing, but:
3| case a of -1 -> "no"
^
It is not possible to pattern match on negative numbers at this time. Try using
anifexpression for that sort of thing for now.
So I had to find a workaround.
There we go.
Also had to change my neighbor check
getNeighbors : Grid -> Cell -> List (Maybe Cell)
getNeighbors grid cell =
List.map (getNeighbor grid cell) <|
[ (0, -1)
, (-1, 0), (1, 0)
, (0, 1)
]
It is not perfect yet, but very satisfying. It doesn't know how to check for interconnected pipes yet, so for now it only check if it has 2 pipe neighbors.
Takeaway
Types can be very useful to create abstractions, especially for scalability. As we have seen, I just could replace my implementation from Day 3 and most of the grid logic stayed the same. Also allocating a given amount of time before the task helps to keep up with the time management and lift pressure.
One more thing, I have been trying to implement solutions as condense as possible, trying to put everything into one function, inspired by the idea of code golfing. But coding this way in the functional paradigm, especially in elm makes you go crazy, and that costs time. So I will return to modeling my logic in terms of simpler functions.
I also might want to think about a better datastructure for my directions. If I leave them as tuples the order of first and second is very important, however I don't care about the order.
This is more of a "Set" situation, so I might look into that instead. Today that felt very clumsy.