Advent of Code 2024

Posted on Dec 8, 2024

Here are my solutions to the 2024 Advent of Code, using Julia.

Day 1
Day 2
Day 3
Day 4
Day 5
Day 6
Day 7
Day 8

Day 1

using CSV, DataFrames
df = CSV.read("advent1.csv", DataFrame, header=["L1", "L2"], delim="   ")
println("Day1, Answer 1: ", sum(abs.(sort(df.L1) - sort(df.L2))))
println("Day1, Answer 2: ", sum([i*count(x->(x == i), df.L2) for i in df.L1]))

Day 2

Part 1

Read the data

records = [[parse(Int32, x) for x in field]
           for field in [split(r, " ")
                         for r in readlines("advent2.csv")]]

Calculate the changes

delta = [x[2:end] - x[1:end-1] for x in records]

Count the conditions


range1_3 =  [all(x -> (abs(x)>=1) & (abs(x)<=3), d) for d in delta]
declining = [all(x -> x < 0, d) for d in delta]
rising =    [all(x -> x > 0, d) for d in delta]

safe = range1_3 .& (declining .| rising)

println("$(sum(safe)) records are safe")

Part 2

Create functions for tidiness (could have used above)

function rangegood(l)
    all(x -> (abs(x)>=1) & (abs(x)<=3), l)
end
function strictmono(l)
    all(x -> x < 0, l) | all(x -> x > 0, l)
end

For each unsafe record, drop each element one at a time, calculate the changes and test. If dropping any element makes the record pass, it passes as a whole. Testing by dropping all elements is redundant (after the first pass) but breaking out saves negligible time.

safe2 = copy(safe)
for i in 1:1000
    if !safe[i]
        for j in 1:length(records[i])
            dropone = records[i][setdiff(1:length(records[i]), j)]
            deltad1 = dropone[2:end] - dropone[1:end-1]
            if rangegood(deltad1) & strictmono(deltad1)
                safe2[i] = true
            end
        end
    end
end

println("$(sum(safe2)) records are safe if we allow one exception")

Day 3

# Part 1
## Read the data, joining the lines
data = join(readlines("advent3.dat"))

## Create a function
mul(a,b) = a*b

# Regular expressions, and treating data as code:
result1 = sum([eval(Meta.parse(m.match)) for m in eachmatch(r"mul\([0-9][0-9]?[0-9]?,[0-9][0-9]?[0-9]?\)", data)])
println("First calculation comes to $result1")

# Part 2
## first pass: regexp to remove don't() to do()
## second: if there is one last don't() without a do() after, remove that to end

datanew = replace(data, r"don't\(\).*?do\(\)" => "")
datanew = replace(datanew, r"don't\(\).*?$" => "")
result2 = sum([eval(Meta.parse(m.match)) for m in eachmatch(r"mul\([0-9][0-9]?[0-9]?,[0-9][0-9]?[0-9]?\)", datanew)])
println("Second calculation comes to $result2")

Day 4

Part 1

Awkward testxmas() function needs to test that we are not too near an edge, before extracting a text-slug and comparing it to “XMAS”.

data = readlines("advent4.dat")
nlines = length(data)
ncols = length(data[1])

xloc = [(i, j) for i in 1:nlines for j in 1:ncols if data[i][j] == 'X']

function testxmas(row, col, rowdir, coldir)
    if (row+3*rowdir > 0) &
        (row+3*rowdir <= nlines) &
        (col+3*coldir > 0) &
        (col+3*coldir <= ncols)
        slug = join([data[row+i*rowdir][col+i*coldir] for i in 0:3])
        if slug=="XMAS"
            return(true)
        else
            return(false)
        end
    else
        return(false)
    end
end


count = sum([testxmas(loc..., idir, jdir)
         for loc in xloc
             for idir in -1:1
                 for jdir in -1:1])

println("We find $count XMASes")

Part 2

Harder to understand the instructions, but less code for part 2. Avoid edges by iterating from 2 to end-1.

function itsX(i,j)
    Set([data[i-1][j-1], data[i+1][j+1]]) == Set([data[i-1][j+1], data[i+1][j-1]]) == Set(['M','S'])
end

println("X-MASes: $(sum([itsX(i,j)
                     for i in 2:nlines-1
                         for j in 2:ncols-1 if data[i][j] == 'A']))")

Day 5

Part1

Strategy: for each sequence, calculate all pairs and see if their reverse is in the rule set

## Read rules and sequences
rules = [parse.(Int32,split(x, "|")) for x in readlines("advent5rules.dat")]
updates = [[parse(Int32, x) for x in split(r, ",")] for r in readlines("advent5.dat")]

# Function: test a sequence against the rules & sum the infringements
function disordered(seq)
    sum([[seq[j], seq[i]] in rules for i in 1:length(seq)-1 for j in i+1:length(seq)])
end

nInfringe = [disordered(u) for u in updates]

answer1 = sum([seq[[Int(floor(length(seq)/2)) + 1]] for seq in updates[nInfringe.==0]])

Part 2

For all ordered (not necessarily consecutive) pairs, swap them if they infringe, repeating until the result is in order

incorrects = updates[nInfringe.>0]
nInfringe[nInfringe.>0]

corrected = []
for incorrect in incorrects
    temp = copy(incorrect)
    while disordered(temp)>0
        for i in 1:length(incorrect)-1
            for j in i+1:length(incorrect)
                # Swap pair if infringing
                if [temp[j], temp[i]] in rules
                    temp[[i,j]]  = temp[[j,i]]
                end
            end
        end
    end
    append!(corrected, [temp])
end

answer2 = sum([seq[Int(floor(length(seq)/2)) + 1] for seq in corrected])

println("Part 1: $answer1")
println("Part 2: $answer2")

Day 6

Part 1

rawlayout = readlines("advent6.dat")
layout = zeros(Int32,length(rawlayout), length(rawlayout[1]))
global gloc = [0,0]
for i in 1:length(rawlayout)
    for j in 1:length(rawlayout[1])
        if rawlayout[i][j] == '#'; layout[i,j] = 1; end
        if occursin(rawlayout[i][j], "^>v<"); global gloc = [i,j]; end
    end
end

global dir = 0
for i in 1:4
    if rawlayout[gloc[1]][gloc[2]] == "^>v<"[i]; global dir = i
    end
end

function moveguard(guard; mlayout = layout)
    # 1 up, 2 left, 3 down, 4 right
    i, j, dir = guard
    if dir == 1;     i -= 1
    elseif dir == 2; j += 1
    elseif dir == 3; i += 1
    elseif dir == 4; j -=1
    end
    if (i in range(1,size(mlayout)[1])) &
        (j in range(1,size(mlayout)[2]))
        if (mlayout[i,j] != 1)
            return([i,j,dir])
        else
            newguard = guard
            newguard[3] = 1 + mod(dir, 4)
            moveguard(guard)
        end
    else
        return(-1)
    end
end

Guard = [gloc..., dir]

track = []
while Guard != -1
    global Guard
    append!(track, [Guard[1:2]])
    Guard = moveguard(Guard)
end

println("Answer 1: $(length(unique(track)))")

Part 2

Part 2 is driving me mad. I get the correct answer on the training data but not on the real data!

function maketrack(initpos; layout=layout)
    result = ""
    coords = copy(initpos)
    track = []
    while coords != -1
        coords = moveguard(coords, layout = layout)
        if coords == -1
            result = "EXIT"
            break
        elseif coords in track
            result = "LOOP"
            break
        end
        append!(track, [coords])
    end
    return(result)
end


function testloc(loc; layout = layout, gloc=gloc, dir=dir)
    if layout[loc...] == 0
        templo = copy(layout)
        templo[loc...] = 1
        maketrack([gloc..., dir], layout=templo)
    else
        "Null"
    end
end

origtrack = unique(track)

exits = []
nulls = []
loops = []

Threads.@threads for block in origtrack
    outcome = testloc(block)
    if outcome == "LOOP"
        append!(loops, [block])
    elseif outcome == "EXIT"
        append!(exits, [block])
    elseif outcome == "Null"
        append!(nulls, [block])
    else
        println("Anomaly: $(block)")
    end
end

    println("Exits: $(length(exits)); Loops: $(length(loops))")

Part 2 revisited

Day 6 part 2 really got me stuck. Moreso in that I was using a very inefficient algorithm that worked through the walkgrid cell-by-cell and took forever to complete (even with parallel processing). That’s something that makes debugging particularly difficult!

Then I realised I could speed it up by looking ahead to the next obstacle, rather than proceeding step by step. This movefast() function is key:

function movefast(guard; mlayout = layout)
    # 1 up, 2 left, 3 down, 4 right
    i, j, dir = guard

    ## route to next obstacle or edge
    exit = false
    idistance = 0
    jdistance = 0
    if dir == 1 # up, i reduces
        route = reverse(mlayout[1:i, j])
        if maximum(route) == 0
            exit = true
            idistance = -(length(route) - 1)
        else
            idistance = -(argmax(route) - 2)
        end
    elseif dir == 2
        route = mlayout[i, j:end]
        if maximum(route) == 0
            exit = true
            jdistance = length(route) - 1
        else
            jdistance = argmax(route) - 2
        end
    elseif dir == 3
        route = mlayout[i:end, j]
        if maximum(route) == 0
            exit = true
            idistance = length(route) - 1
        else
            idistance = argmax(route) - 2
        end
    elseif dir == 4
        route = reverse(mlayout[i, 1:j])
        if maximum(route) == 0
            exit = true
            jdistance = -(length(route) - 1)
        else
            jdistance = -(argmax(route) - 2)
        end
    end
        return((exit, [i+idistance, j+jdistance, 1 + mod(dir, 4)]))
end

This required changing some of the logic. The track that results is a set of legs, not a list of successive cells. This code yields the same answer as the Part 1 code above:

Guard = [gloc..., dir]
texit = false
mftrack = [Guard]
while texit != true
    texit, Guard = movefast(Guard)
    append!(mftrack, [Guard])
end

walkgrid = zeros(Int32, size(layout)...)

oldpoint = track[1][1:2]
walkgrid[oldpoint...] = 1

for elt in 2:length(track)
    for i in min(track[elt-1][1], track[elt][1]):max(track[elt-1][1], track[elt][1])
        for j in min(track[elt-1][2], track[elt][2]):max(track[elt-1][2], track[elt][2])
                        walkgrid[i,j] = 1
        end
    end
end

println("Answer 1: $(sum(walkgrid))")

The testloc() function introduces an obstacle and traces the progress of the guard. If one of the legs of the track duplicates an existing one, a loop is detected.

function testloc(block; gloc = gloc, dir = dir)
    tlguard = [gloc..., dir]
    texit = false
    isloop = false
    track = [tlguard]
    templo = copy(layout)
    templo[block...] = 1
    while texit != true
        texit, tlguard = movefast(tlguard, mlayout=templo)
        if tlguard in track
            append!(track, [tlguard])
            isloop=true
            break
        else
            append!(track, [tlguard])
        end
    end
    (isloop, track)
end

The walkgrid is important: where its value is 1 marks places it makes sense to pose an obstacle. So we iterate through those locations and count the loops.

ncols, nrows = size(walkgrid)
loops = []
exits = []
for i in 1:ncols, j in 1:nrows
    if walkgrid[i,j] == 1
        if testloc([i,j])[1]
            push!(loops, [i,j])
        else
            push!(exits, [i,j])
        end
    end
end

println("Answer 2: $(length(loops))")

Bonus: plotting the scene

Plot the guards’ standard walk:


function plotwalk(track, layout)
    y = [elt[1] for elt in track]
    x = [elt[2] for elt in track]
    plot(heatmap(layout), aspect_ratio=:equal, yaxis=:flip, colorbar=false, size=(800,800))
    plot!(x, y)
    scatter!([track[1][2]], [track[1][1]], color=:green, label="Start")
    scatter!([track[end][2]], [track[end][1]], color=:red, label="End")
end

plotwalk(mftrack, layout)
plot!(title="Guards' walk")
savefig("day6a.png")

Plot a walk with a loop due to an obstacle

templo = copy(layout)
templo[68, 40] = 1 # <--- obstacle
texit = false
tlguard = [gloc..., dir]
tltrack = [tlguard]
while texit != true
    texit, tlguard = movefast(tlguard, mlayout=templo)
    if tlguard in tltrack
        append!(tltrack, [tlguard])
        isloop=true
        break
    else
        append!(tltrack, [tlguard])
    end
end
plotwalk(tltrack, templo)
plot!(title="Obstacle at 68, 40 causes loop")
savefig("day6b.png")

Day 7

I spent ages thinking ineffectively about this, and then found a quick idiomatic solution.

data = [split(line) for line in readlines("advent7.dat")]

results = [parse(Int64, x[1][1:end-1]) for x in data]
coefs = [[parse(Int64, x) for x in line[2:end]] for line in data]


rlist = []
for seq in coefs
    result = seq[1]
    for i in 2:length(seq)
        result = vcat([r + seq[i] for r in result],[r*seq[i] for r in result])
    end
    append!(rlist, [result])
end

println("Answer day 7, part 2: ", sum([results[i]*(results[i] in rlist[i]) for i in 1:length(coefs)]))

Moreover, the extension to part 2 was easy.

## Part 2

function concatop(a, b)
    parse(Int64, "$a$b")
end

r2list = []
for seq in coefs
    result = seq[1]
    for i in 2:length(seq)
        result = vcat([r + seq[i] for r in result],
                      [r * seq[i] for r in result],
                      [concatop(r,seq[i]) for r in result])
    end
    append!(r2list, [result])
end

println("Answer day 7, part 1: ", sum([results[i]*(results[i] in r2list[i]) for i in 1:length(coefs)]))

Day 8

Part 1

Read the data (symbols get mapped to integers)

rawlayout = readlines("advent8.dat")
nrows = length(rawlayout); ncols = length(rawlayout[1])
layout = zeros(Int32, nrows, ncols)
for i in 1:nrows
    for j in 1:ncols
        if rawlayout[i][j] != '.'
            layout[i,j] = rawlayout[i][j]
        end
    end
end

Antinodes are defined like this

function antinodes(a, b)
    deltai = b[1] - a[1]
    deltaj = b[2] - a[2]
    [[a[1]-deltai, a[2] - deltaj],
     [b[1]+deltai, b[2] + deltaj]]
end

For each frequency, build a list of locations in a Dict

antennae = Dict()
for i in 1:nrows, j in 1:ncols
    ant = layout[i,j]
    if ant != 0
        if haskey(antennae,ant)
            push!(antennae[ant], [i,j])
        else
            antennae[ant] = [[i,j]]
        end
    end
end

For each frequency, for each pair of antennae, calculate antinodes and append to a list

locs1 = []
for key in keys(antennae) # For every freqeuency
    aset = antennae[key]
    for i in 1:length(aset)-1, j in i+1:length(aset) # for every pair of antennae
        append!(locs1, antinodes(aset[i], aset[j]))
    end
end

Filter out the off-grid antinodes, and count unique observations:

locs1a = [l for l in locs1 if (l[1] in 1:nrows) & (l[2] in 1:ncols)]
println("Answer 1: $(length(unique(locs1a)))")

Part 2

A new function to define new antinodes: All elements of the line with slope deltai/deltaj that passes through the pair, that are integer values.

function antinodesp2(a, b)
    deltai = b[1] - a[1]
    deltaj = b[2] - a[2]
    slope = deltai/deltaj
    lineelts = [[a[1] + (x-a[2])*slope, Int(x)]     for x in 1:ncols]
    [floor.(Int,elt) for elt in lineelts if floor(elt[1])==elt[1]]
end

Analagous steps to summarise

locs2 = []
for key in keys(antennae)
    aset = antennae[key]
    for i in 1:length(aset)-1, j in i+1:length(aset)
        append!(locs2, antinodesp2(aset[i], aset[j]))
    end
end

locs2a = [l for l in locs2 if (l[1] in 1:nrows) & (l[2] in 1:ncols)]
println("Answer 2: $(length(unique(locs2a)))")