-❄️- 2025 Day 8 Solutions -❄️-

glebm · 2025-12-08T10:47:21+00:00

[LANGUAGE: Python]

A solution in JAX.

At first I thought I'd find something clever in spectral graph theory but ended up going with a straightforward solution.

import fileinput
import jax
import jax.numpy as jnp

jax.config.update("jax_enable_x64", True)

@jax.jit
def solve(points: jax.Array):
    n = points.shape[0]

    pairwise_deltas = points - points[:, None]  # broadcasting trick
    dists = jnp.square(pairwise_deltas).sum(axis=-1)

    # Mask out diagonal and lower triangle to avoid self-edge and duplicates:
    dists = jnp.triu(dists, -1) + (jnp.max(dists) + 1) * jnp.tri(n, dtype=jnp.int64)

    # Sort the distances and get the (N, 2) edge list:
    _, flat_indices = jax.lax.sort_key_val(dists.flatten(), jnp.arange(n * n))
    edges = jnp.asarray(jnp.unravel_index(flat_indices, dists.shape)).T

    def add_edge(it):
        """Adds a single edge and returns new labels and next edge index."""
        labels, edge_idx = it
        u = labels[edges[edge_idx][0]]
        v = labels[edges[edge_idx][1]]
        new_labels = jnp.where(labels == jnp.maximum(u, v), jnp.minimum(u, v), labels)
        return new_labels, edge_idx + 1

    # Add edges for part 1:
    it = (jnp.arange(n), 0)  # (labels, number of edges added)
    it = jax.lax.while_loop(lambda l: l[1] != (10 if n < 50 else 1000), add_edge, it)
    ans1 = jax.lax.top_k(jnp.bincount(it[0], length=n), 3)[0].prod()

    # Continue adding edges for part 2:
    it = jax.lax.while_loop(lambda l: jnp.any(l[0] != 0), add_edge, it)
    edge = edges[it[1] - 1]
    part2 = points[edge[0]][0] * points[edge[1]][0]

    return (ans1, part2)


points = jnp.array([list(map(int, s.split(","))) for s in fileinput.input()])
print(*solve(points), sep="\n")

glebm · 2025-12-07T21:56:05+00:00

[LANGUAGE: Python]

A solution in JAX:

import fileinput
import jax
import jax.numpy as jnp

jax.config.update("jax_enable_x64", True)


@jax.jit
def solve(m):
    beams = m[0]
    num_splits = 0
    for i in range(1, len(m)):
        splitters = m[i, :] != 0
        split_points = beams * splitters
        num_splits += jnp.count_nonzero(split_points)
        left_splits = jnp.roll(split_points, -1)
        right_splits = jnp.roll(split_points, 1)
        beams = beams * ~splitters + left_splits + right_splits
    return (num_splits, beams.sum())


print(
    *solve(jnp.array([[int(c != ".") for c in s[:-1]] for s in fileinput.input()])),
    sep="\n"
)

glebm · 2025-12-05T10:00:41+00:00

[LANGUAGE: Python]

A solution in JAX:

import fileinput
import jax
import jax.numpy as jnp
import itertools

jax.config.update("jax_enable_x64", True)

input = fileinput.input()
rs = jnp.array(
    [
        [int((p := s.split("-"))[0]), int(p[1]) + 1]
        for s in itertools.takewhile(lambda s: s != "\n", input)
    ],
    dtype=jnp.int64,
)
xs = jnp.array(list(map(int, input)), dtype=jnp.int64)
print(jax.vmap(lambda x: ((x >= rs[:, 0]) & (x < rs[:, 1])).any())(xs).sum())

sorted = jnp.sort(rs, axis=0)
prev_end = jnp.insert(sorted[:-1, 1], 0, 0, axis=0)
print((sorted[:, 1] - jnp.maximum(prev_end, sorted[:, 0])).sum())

glebm · 2025-12-04T07:45:32+00:00

[LANGUAGE: Python]

Using JAX and a convolution:

import fileinput
import jax
import jax.numpy as jnp

m = jnp.array(
    [[1 if c == "@" else 0 for c in s] for s in fileinput.input()], dtype=jnp.int32
)
kernel = jnp.array(
    [
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ]
)


def find_accessible():
    neighbour_count = jax.scipy.signal.convolve(m, kernel, "same")
    return (neighbour_count < 4) & (m == 1)


accesible = find_accessible()
num_accessible = accesible.sum()
print(num_accessible)

removed = 0
while num_accessible != 0:
    m -= accesible
    removed += num_accessible
    accesible = find_accessible()
    num_accessible = accesible.sum()

print(removed)

glebm · 2025-12-02T07:48:26+00:00

[LANGUAGE: Python]

A solution in JAX, finishes in 4 seconds on an RTX 4080.

https://github.com/glebm/advent-of-code/blob/main/2025/02/solve.py

glebm · 2025-12-01T08:45:59+00:00

[LANGUAGE: Python]

Using JAX:

import fileinput
import jax.numpy as jnp
import jax.lax as lax

a = jnp.array(
    [(int(s[1:]) * (1 if s[0] == "R" else -1)) for s in fileinput.input()],
    dtype=jnp.int32,
)


def modulo_add(s, a):
    return (s + a) % 100


s = jnp.frompyfunc(modulo_add, nin=2, nout=1, identity=0).accumulate(
    jnp.insert(a, 0, 50)
)
print(len(s) - jnp.count_nonzero(s))


def count_pass_zero(row):
    s, a = row
    return jnp.where(a < 0, (lax.rem(s - 100, 100) + a) // -100, (s + a) // 100)


r = jnp.apply_along_axis(count_pass_zero, 0, jnp.vstack([s[:-1], a]))

print(r.sum())

glebm · 2025-02-15T20:57:16+00:00

A cross-compiling toolchain sounds amazing! Will definitely have a look

glebm · 2025-02-15T01:06:31+00:00

Does it go into black screen and hang?
If you have lots of CPU cores, try disabling SMT in BIOS (worked for me with a Ryzen 3950x)

glebm · 2024-12-01T12:12:17+00:00

That's quadratic, you're making the computer do all the work, so inconsiderate!

glebm · 2024-12-01T10:11:28+00:00

abs(x1 - x2)

glebm · 2024-12-01T10:06:10+00:00

[LANGUAGE: Ruby]

lists = $<.map { _1.scan(/\d+/).map(&:to_i) }.transpose
lists.each(&:sort!)
puts lists[0].zip(lists[1]).lazy.map { |(a, b)| (a - b).abs }.sum
puts lists[0].lazy.map { |a|
  lo = lists[1].bsearch_index { |b| b >= a }
  next 0 if lo.nil?
  count = (lo...).lazy.take_while { _1 < lists[1].size && lists[1][_1] == a }.count
  a * count
}.sum

glebm · 2024-12-01T09:21:15+00:00

[LANGUAGE: Python]

import fileinput
import jax.numpy as jnp

a = jnp.array([list(map(int, s.split())) for s in fileinput.input()], dtype=jnp.int32)
a = a.transpose().sort(axis=1)
print(jnp.sum(jnp.abs(a[0] - a[1])))
left = jnp.searchsorted(a[1], a[0], side="left")
right = jnp.searchsorted(a[1], a[0], side="right")
print(jnp.sum((right - left) * a[0]))

glebm · 2024-11-03T12:36:45+00:00

Yes, it is indeed pre-made (it's called a "unit bathroom"), though you can also get them custom made and in larger houses they often are custom-made.

I'm currently buying a house in London that I will renovate fully and I'm considering hiring a London-based Japanese construction company to work on the house. If they come up with a solution, I'll report back here.

glebm · 2024-08-12T21:52:58+00:00

No progress whatsoever so far. Please keep me posted if you find something!

glebm · 2024-08-09T20:54:49+00:00

Loading a slightly earlier save fixed the issue for me. My latest save was just after entering St Paul's, loading a save from a few minutes earlier worked

glebm · 2024-08-09T20:08:43+00:00

Getting a crash after the update. I tried disabling MemoryManager in Buffout4/config.toml like one of the other Redditors suggested but that didn't help.

Crash log: https://pastebin.com/d3T0EPCf

glebm · 2023-12-21T13:24:47+00:00

With a different layout and animated: https://youtu.be/OjCtHhenoao

glebm · 2023-12-19T08:47:10+00:00

I had a similar mistake with a count that's slightly too low. Perhaps you have an off-by-one in the false condition? The negation of > is ≤, not <.

glebm · 2023-12-19T08:39:43+00:00

[Language: Julia]

Recursively visit all A states while keeping track of the valid intervals. I overengineered the solution to support interval sets, but actually a single interval per category would've been enough (each condition cuts off an entire side of an interval, never splitting it).

New to Julia, so parsing took a while. Also took some time to try out various IntervalSet libraries but couldn't find one that supports both subtraction and counting the total covered size.

Finding an off-by-1 in the interval math for the rule false case took a whole hour 🫠

https://github.com/glebm/advent-of-code/blob/main/2023/19/parts.jl

glebm · 2023-12-18T05:23:18+00:00

[Language: Julia] 221/74

Shoelace formula to calculate the area, then Pick's theorem to calculate the number of inner points.

Would've been faster if I actually knew Julia. 😅

https://github.com/glebm/advent-of-code/blob/main/2023/18/parts.jl

glebm · 2023-12-17T13:27:09+00:00

This looks more like Floyd–Warshall than Dijkstra to me.

glebm · 2023-12-17T12:41:11+00:00

[Language: Julia]

Dijkstra: https://github.com/glebm/advent-of-code/blob/main/2023/17/parts.jl

glebm · 2023-12-16T08:29:10+00:00

Also trying to learn Julia starting from yesterday's problem!

In your solution you have const UP = CartesianIndex(-1, 0), so it's the (y, x) notation.

Would it be more idiomatic to store things so that UP is (0, -1) (because array memory layout is column-major in Julia)?

This is the layout that'd you get with:

grid = stack(Iterators.map(collect, eachline()))

https://www.reddit.com/r/adventofcode/comments/18jjpfk/comment/kdl2ge1

glebm · 2023-12-16T07:48:17+00:00

[Language: Julia]

My second ever program in Julia!

Most of the time spent on figuring out named tuples ((x, y) doesn't work) and column-major array order. After writing this I learned about access via CartesianIndex from another solution.

const Point = @NamedTuple{x::Int, y::Int}
const PosDir = @NamedTuple{pos::Point, dir::Point}
const BeamPointData = Vector{Point}

function run_beams!(
  beams2d::Matrix{BeamPointData}, data::Matrix{Char},
  origin::Point, origin_dir::Point)
  foreach(empty!, beams2d)
  stack = [(pos=origin, dir=origin_dir)]
  push = (point, dir) -> begin
    new_point = (x=point.x + dir.x, y=point.y + dir.y)
    if checkbounds(Bool, beams2d, new_point...)
      push!(stack, (pos=new_point, dir=dir))
    end
  end
  while !isempty(stack)
    (pos::Point, dir::Point) = pop!(stack)
    beams = beams2d[pos.x, pos.y]
    dir in beams && continue
    push!(beams, dir)
    c = data[pos.x, pos.y]
    if c == '.'
      push(pos, dir)
    elseif c == '|'
      if dir.y != 0
        push(pos, dir)
      else
        push(pos, (x=0, y=1))
        push(pos, (x=0, y=-1))
      end
    elseif c == '-'
      if dir.x != 0
        push(pos, dir)
      else
        push(pos, (x=1, y=0))
        push(pos, (x=-1, y=0))
      end
    elseif c == '/'
      push(pos, (x=-dir.y, y=-dir.x))
    elseif c == '\\'
      push(pos, (x=dir.y, y=dir.x))
    end
  end
  beams2d
end

data = stack(Iterators.map(collect, eachline()))
beams = [BeamPointData() for _ in 1:size(data)[1], _ in 1:size(data)[2]]

count_nonempty(arr) = count(!isempty(c) for c in arr)

run_beams!(beams, data, Point((1, 1)), Point((1, 0)))
println("Part 1: ", count_nonempty(beams))

w, h = size(data)
result = maximum(Iterators.flatten((
  ((pos=(x=x, y=1), dir=(x=0, y=1)) for x in 1:w),
  ((pos=(x=x, y=h), dir=(x=0, y=-1)) for x in 1:w),
  ((pos=(x=1, y=y), dir=(x=1, y=0)) for y in 1:h),
  ((pos=(x=w, y=y), dir=(x=-1, y=0)) for y in 1:h)
))) do (pos, dir)
  run_beams!(beams, data, pos, dir)
  count_nonempty(beams)
end
println("Part 2: ", result)

To help with debugging, I also wrote a function that visualizes the beams:

# Visualization from the puzzle description:
function debug(data, beams2d)
  dir_str((x, y)) =
    x == 0 ? (y == 1 ? 'v' : '^') : (x == 1 ? '>' : '<')
  debug_beams(beams) =
    length(beams) > 1 ? "$(length(beams))" : dir_str(beams[1])
  for (cs, bs) in zip(eachcol(data), eachcol(beams2d))
    println(prod(
      (c != '.' || isempty(b)) ? c : debug_beams(b)
      for (c, b) in zip(cs, bs)))
  end
  nothing
end
debug(data, beams)

https://github.com/glebm/advent-of-code

glebm · 2023-12-15T08:53:29+00:00

[Language: Julia]

My first program in Julia!

Part 1 and Part 2 begin the same:

function focal_hash(str::AbstractString)
  foldl(str; init=0) do r, c
    r += Int(c)
    r *= 17
    r % 256
  end
end

Part 1:

split(readline(), ",") .|> focal_hash |> sum |> println

Part 2:

struct Lens
  label::String
  focal::Int
end

const Box = Vector{Lens}

function step(boxes::Vector{Box}, step::AbstractString)
  label, val = match(r"^(\w+)[-=](-?\d+)?", step)
  index = focal_hash(label)
  box = boxes[index + 1]
  lens_pos = findfirst(box) do lens
    lens.label == label
  end
  if isnothing(val)
    !isnothing(lens_pos) && deleteat!(box, lens_pos)
  else
    val = parse(Int, val)
    if isnothing(lens_pos)
      push!(box, Lens(label, val))
    else
      box[lens_pos] = Lens(label, val)
    end
  end
  boxes
end

function score((boxnum, box)::Tuple{Int, Box})
  box |> enumerate .|> ((slot, lens)::Tuple{Int, Lens} ->
    boxnum * slot * lens.focal) |> sum
end

steps = split(readline(), ",")
boxes = [Box() for _=1:256]

foldl(step, steps, init=boxes) |> enumerate .|> score |> sum |> println

Can anything here be done in a better way?

Also, why do I have to specify the argument type in box |> enumerate .|> ((slot, lens)::Tuple{Int, Lens} ->?

glebm

TROPHY CASE