Stream: advent of code

Topic: 2025 Day 2

Matthieu Pizenberg (Dec 04 2025 at 22:42):

With the recent fixes, and the incoming one in https://github.com/roc-lang/roc/pull/8573, I now have a correct AoC day 2!
Well almost ^^. Actually it’s correct with the demo short inputs, but I’m getting a stack overflow with the real inputs. But I’m pretty confident that it would be correct without the stack overflow because I’m getting the correct results for the demo values and the code is essentially the same as my valid Julia solution.

❯ roc day02.roc
Part 1 (demo): 1227775554
Part 2 (demo): 4174379265

The code is here for those interested:

app [main!] { pf: platform "https://github.com/lukewilliamboswell/roc-platform-template-zig/releases/download/0.1-test/7iDKk44no3gF9Nrh2VyF8Y5yvy1jUBhrbhHURN1WQptB.tar.zst" }

import pf.Stdout
import pf.Stderr

demo_input = "11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124"

day_input = demo_input # TODO: copy actual input here

print! : Str => {}
print! = |msg| msg.split_on("\n").for_each!(Stdout.line!)


parse_range : Str -> Try((I64, I64), _)
parse_range = |range_str| {
    match range_str.split_on("-") {
        [a, b] => Ok((I64.from_str(a)?, I64.from_str(b)?))
        _ => Err(InvalidRangeFormat)
    }
}


is_invalid : I64 -> Bool
is_invalid = |x| {
    s = x.to_str().to_utf8()
    n = s.len()
    mid = n // 2

    left = s.sublist({ start: 0, len: mid })
    right = s.sublist({ start: mid, len: n - mid })

    left == right
}


part1! : Str => Try(I64, _)
part1! = |input| {
    var $sum = 0

    for range_str in input.trim().split_on(",") {
        (start, end) = parse_range(range_str)?

        var $x = start
        while $x <= end {
            if is_invalid($x) {
                $sum = $sum + $x
            }
            $x = $x + 1
        }
    }

    Ok($sum)
}


repeat = |list, n| repeat_helper([], list, n)

repeat_helper = |acc, list, n| match n {
    0 => acc
    _ => repeat_helper(acc.concat(list), list, n - 1)
}

has_repeating_pattern : I64 => Bool
has_repeating_pattern = |x| {
    s = x.to_str().to_utf8()
    n = s.len()

    # Check all divisors of n
    var $d = 1
    while $d <= n // 2 {
        if n % $d == 0 {
            # Check if repeating the first d characters n/d times equals s
            slice = s.sublist({ start: 0, len: $d })
            repeated = slice->repeat(n // $d)
            if repeated == s { return True }
        }
        $d = $d + 1
    }

    False
}


part2! : Str => Try(I64, _)
part2! = |input| {
    var $sum = 0

    for range_str in input.trim().split_on(",") {
        (start, end) = parse_range(range_str)?

        var $x = start
        while $x <= end {
            if has_repeating_pattern($x) {
                $sum = $sum + $x
            }
            $x = $x + 1
        }
    }

    Ok($sum)
}


run! = || {
    print!("Part 1 (demo): ${part1!(demo_input.trim())?.to_str()}")
    #print!("Part 1: ${part1!(day_input.trim())?.to_str()}")
    print!("Part 2 (demo): ${part2!(demo_input.trim())?.to_str()}")
    #print!("Part 2: ${part2!(day_input.trim())?.to_str()}")
    Ok({})
}


main! = |_args| {
    match run!() {
        Ok(_) => Ok({})
        Err(_) => Err(1)
    }
}

Richard Feldman (Dec 04 2025 at 23:01):

yeah I'm bumping the default stack size in a PR that should be landing soon

Matthieu Pizenberg (Dec 09 2025 at 21:30):

aaaaaaaah
It was so close. Now that all the bugs I’ve encountered were fixed on main and day01 was running smoothly with no memory leak, I was praying to the insect gods and ... it wasn’t enough XD

❯ roc --no-cache day02.roc
thread 586390 panic: index out of bounds: index 2863311530, len 1049
???:?:?: 0x104a7476f in _instantiate.Instantiator.instantiateTagUnion (???)
???:?:?: 0x104a02f4f in _instantiate.Instantiator.instantiateFlatType (???)
???:?:?: 0x10495c1d3 in _instantiate.Instantiator.instantiateContent (???)
...

Tomorrow I’ll try to minimize it.

Richard Feldman (Dec 09 2025 at 22:16):

if you want to just paste the non minimized version I can take care of it!

Matthieu Pizenberg (Dec 09 2025 at 22:23):

Here is the file in full. It’s using Luke’s latest platform version 0.5

day02.roc

Matthieu Pizenberg (Dec 10 2025 at 08:31):

It’s a weird one again. If I change almost anything, the panic goes away. Even removing dead code.

Matthieu Pizenberg (Dec 10 2025 at 08:48):

So in a way, the good news is that for example just using Stdout.line! instead of my print! makes the program run. The bad news is that even in ReleaseFast, interpreter seems way to slow to be able to compute day02 with the naive implementation I came up with while trying to solve it in Julia.

Richard Feldman (Dec 10 2025 at 14:54):

https://github.com/roc-lang/roc/pull/8617 should fix this!

Richard Feldman (Dec 10 2025 at 14:56):

even in ReleaseFast, interpreter seems way to slow to be able to compute day02 with the naive implementation I came up with while trying to solve it in Julia.

this is a good data point to have! one of the open questions with the interpreter is "will it be fast enough compared to our previous compiler's strategy of doing monomorphization and then direct-to-machine-code code gen?" and it sounds like in this case the answer is that it wasn't fast enough

Richard Feldman (Dec 10 2025 at 14:56):

if Julia is fast enough, then our direct-to-machine-code backend should definitely be fast enough

Matthieu Pizenberg (Dec 10 2025 at 14:57):

Julia takes roughly 2s, and the roc interpreter I’ve stopped after 1h not finishing for the same puzzle range.

Richard Feldman (Dec 10 2025 at 14:58):

of note, even trying out a direct-to-machine-code backend is blocked on monomorphization and lambda set specialization being implemented (one of the other benefits of trying out an interpreter approach is that it has fewer prerequisites) so it'll be awhile before we can even consider trying that as an alternative

Richard Feldman (Dec 10 2025 at 14:58):

although since we've already done it once in Rust, I bet a LLM can port a bunch of that over to Zig for us; it wouldn't be like we'd have to start over from scratch

Richard Feldman (Dec 10 2025 at 15:00):

but I think for now we should continue with the interpreter and reconsider the direct-to-machine-code backend option once we have the LLVM backend in place, since at that point we'll have all the prerequisites for both - as well as more data points on how long the interpreter takes to run

Matthieu Pizenberg (Dec 10 2025 at 15:00):

Yeah, for that puzzle I’ll just have to write a less trivial solution.

Richard Feldman (Dec 10 2025 at 15:01):

can you post the one that reproduces the slowness somewhere?

Richard Feldman (Dec 10 2025 at 15:01):

ideally that and the julia one - would be great to have both of those for future comparison when revisiting this question

Matthieu Pizenberg (Dec 10 2025 at 15:01):

I’ll do a little bit of cleanup tonight and post both ok

Richard Feldman (Dec 10 2025 at 17:53):

awesome, thanks!

Matthieu Pizenberg (Dec 10 2025 at 18:21):

@Richard Feldman
Here: https://github.com/roc-lang/roc/issues/8621

Matthieu Pizenberg (Dec 11 2025 at 00:22):

I’ve rewritten day 2 in a completely different approach which is less trivial but also much more efficient, and now I got a valid response in Roc for both part 1 and part 2, in a not-too-long amount of time :)

Here is the implementation for those interested.
day02_gen.roc

❯ roc day02_gen.roc
error(gpa): Allocation alignment 8 does not match free alignment 1. Allocation:
Unable to print stack trace: Unable to open debug info: MissingDebugInfo
 Free:
Unable to print stack trace: Unable to open debug info: MissingDebugInfo
...
... tons more error(gpa) alignment issues
...
-----------
Part 1 (demo): 1227775554
Part 1: 54641809925
Part 2 (demo): 4174379265
Part 2: 73694270688

As you can see, there are still memory alignment issues, meaning sometimes I have to add a stdout line here and there to prevent a crash (no idea why). But when it goes to the end, it gives the correct answer!

Matthieu Pizenberg (Dec 11 2025 at 00:37):

PS this solution is now panicking on the latest main b60aa9a3

Richard Feldman (Dec 11 2025 at 00:46):

I'll look into that tonight!

Matthieu Pizenberg (Dec 11 2025 at 08:35):

Thanks for the fix!

There's a separate memory leak issue but that happens on the host side, not in the compiler!

By "memory leak", do you mean the lines I see with "Allocation alignment 8 ..."?
By "on the host side", do you mean it’s in the v0.5 platform template?

Luke Boswell (Dec 11 2025 at 09:18):

Should be fixed in https://github.com/lukewilliamboswell/roc-platform-template-zig/releases/tag/0.6

Luke Boswell (Dec 11 2025 at 09:19):

The host memory leak that is

Matthieu Pizenberg (Dec 11 2025 at 09:37):

I can confirm. Day 2 is now officially cleanly returning the correct result

❯ roc day02.roc
Part 1 (demo): 1227775554
Part 1: 54641809925
Part 2 (demo): 4174379265
Part 2: 73694270688

Matthieu Pizenberg (Dec 11 2025 at 09:41):

tonight is for day 3 :)

Luke Boswell (Dec 11 2025 at 09:45):

Awesome, looking forward to smashing any more bugs we find :bug: :hammer:

Richard Feldman (Dec 11 2025 at 13:59):

yeah this has been extremely helpful - thank you so much for all the bug reports @Matthieu Pizenberg!

Last updated: Dec 21 2025 at 12:15 UTC