2024 Day 9 · advent of code · Zulip Chat Archive

Stream: advent of code

Topic: 2024 Day 9

Luke Boswell (Dec 09 2024 at 05:58):

Here's my Part 1, I should be right to tackle Part 2 later... but figured I share what I have to far :smiley:

https://github.com/lukewilliamboswell/aoc/blob/main/2024/09.roc

TIMING:
READING INPUT:  <1ms
SOLVING PART 1: 4ms

Oskar Hahn (Dec 09 2024 at 07:42):

Here is my part1: https://github.com/ostcar/aoc2024/blob/main/day09.roc

After reading the assignment for Part2, I can say, that my solution for part1 is to clever and can not be used at all for Part2. I have to do Part2 later and remember, not to be clever :face_exhaling:

Nicola Peduzzi (Dec 09 2024 at 11:14):

so are we sure the only way to iterate N times in Roc is via a List.walk or recursion at the moment yes? no loops whatsoever? :sweat_smile:

Anton (Dec 09 2024 at 11:16):

for loops are planned #ideas > `for` and `var` @ 💬

Oskar Hahn (Dec 09 2024 at 15:47):

So Part 2 is finally done. I am not so happy with it and it took too long to write. There are probably better solutions:

On an optimized build:
part1 in 4.347ms
part2 in 1.52s

Nicola Peduzzi (Dec 09 2024 at 20:20):

Well I give up. Can't pass part 2 even if the example checks out. Plus the mental gymnastic today was exhausting. Can't win em all. https://github.com/thenikso/advent-of-code-2024-roc/blob/main/09.roc

Nicola Peduzzi (Dec 09 2024 at 22:12):

Nope! attempted a new solution inspired by Oskar and got it https://github.com/thenikso/advent-of-code-2024-roc/blob/main/09bis.roc

Day 09 part 1: (Ok ...) [1428ms]
Day 09 part 2: (Ok ...) [11559ms]

would not recommend :sweat_smile:

Paul Stanley (Dec 10 2024 at 00:09):

I had a very frustrating time today too. It's really a problem that feels tailor made for a mutable imperative approach. (Nothing wrong with that ... but it runs against the grain of an immutable functional language). On an optimized build, Part 1 in 3 ms and Part 2 in 634 ms. But it's just very naive: a dreary recursive version of an imperative program endlessly walking a list, and pretending it's mutable, more or less.

Header

I think the key hold up is finding space in Part 2 and what I have revolts me. I tried minor optimisations (e.g. using List.findFirstIndex to skip to free space) but they slowed it down quite a bit (which did surprise me somewhat: I might not be surprised to find it not much faster but I wouldn't have expected it to be slower). You should be able to take advantage of the fact that blocks _never_ move "right" to construct a list of all the free space at the outset, but there would still be some book-keeping and I couldn't be bothered.

https://gist.github.com/PaulStanley/4a48ddb3e8e9c05b050b3cb032222e69

Anthony Bullard (Dec 10 2024 at 01:43):

No spoilers!

Ben Thomas (enkidatron) (Dec 10 2024 at 02:01):

Hiding any spoilers, here's my day 9: https://github.com/Enkidatron/advent-of-code-2024/blob/main/day9.roc
(I'm not using the aoc framework package because I'm doing this to learn Roc and I don't want to use the framework until I understand what it's doing. My Roc is probably not idiomatic for the same reason. )

Part 2 thoughts

Brendan Hansknecht (Dec 10 2024 at 05:28):

The complaints and perf issues here make me feel like I should solve it or at least investigate if the perf issues are roc primitive related or algorithmic

Ben Thomas (enkidatron) (Dec 10 2024 at 06:19):

Performance information: using roc dev day9.roc, my part 1 is consistently 16ms and part 2 is 1580-1650ms.
(I have learned enough to duplicate how the aoc framework was doing the timing)

Luke Boswell (Dec 10 2024 at 06:23):

You also can get performance using an optimised build with --optimize

Luke Boswell (Dec 10 2024 at 06:23):

I usually do

$ roc build --optimize app.roc
$ ./app.roc < input.txt

Luke Boswell (Dec 10 2024 at 06:24):

But you can also do

$ roc --optimize app.roc < input.txt`

Oskar Hahn (Dec 10 2024 at 07:39):

Luke Boswell said:

I usually do

$ roc build --optimize app.roc
$ ./app.roc < input.txt

But you can also do

$ roc --optimize app.roc < input.txt`

I don' understand way, but in my cases, the first one is much faster. For example for this day:

$ roc --optimize day09.roc
part1 in 36.136ms
part2 in 12.133s

$ roc build --optimize day09.roc && ./day09
part1 in 3.892ms
part2 in 928.913ms

Brendan Hansknecht (Dec 10 2024 at 07:42):

did we ever fix roc ... ignoring the optimize flag?

Brendan Hansknecht (Dec 10 2024 at 07:43):

My guess is no based on the comment above

Brendan Hansknecht (Dec 10 2024 at 07:43):

Also, I'm almost done with my own implementation before I'll look at perf of others. I have part two working for the example, but a bug with the full run...

Brendan Hansknecht (Dec 10 2024 at 16:46):

Here is my implementation: https://gist.github.com/bhansconnect/0c457a377473f9c80237d26751fa7fe7
I probably should have started with a more naive solution instead of a more optimized one...
I'm sure there is still room for improvement, but hard to tell exactly what without better debug info.

$ /tmp/aoc-2024/day8/main
Part 1: ... -> 2ms
Part 2: ... -> 8ms

EDIT: manage to cut off 2-3ms from part 2 by avoid a List.range and using a recursive walk instead. So now at 5-6ms

Brendan Hansknecht (Dec 10 2024 at 16:48):

Later today I'll start looking at the other solution to try and figure out if any roc perf sharp edges are leading to major perf drops. Not sure how much of this is implicit to certain solution vs due to roc cloning way too much or similar.

Brendan Hansknecht (Dec 10 2024 at 16:55):

fix for roc --optimize day09.roc: https://github.com/roc-lang/roc/pull/7326

Anton (Dec 10 2024 at 18:23):

Claude is struggling with this one...

Brendan Hansknecht (Dec 10 2024 at 19:04):

Makes sense

Anton (Dec 10 2024 at 19:16):

It was eventually able to solve part 1 in one shot:

SOLVING PART 1: 288ms

Main prompt additions for this one :

- Roc does not use `head :: tail`, use `[head, .. as tail]` instead. Make sure you do not forget the `as`!
- Roc does not have currying.
- You can not pattern match directly on booleans. Avoid using Bool.true and Bool.false in general, it is better to use descriptive tags, for example `HasNoExtraLine` and `HasExtraLine`.
- Roc does not allow shadowing.

main_claude_part1.roc

Anton (Dec 10 2024 at 19:42):

I'm giving up on part 2 :sob:
It's definitely a good benchmark to try to improve the prompt for in the future.
prompt-aoc-9-part2.txt

Ben Thomas (enkidatron) (Dec 11 2024 at 02:59):

Luke Boswell said:

I usually do

$ roc build --optimize app.roc
$ ./app.roc < input.txt

Thanks! The optimized day9 takes about 8ms and 650ms, which feels like an impressive speed up to me, a roc beginner. The compiler is definitely smarter than I am at making that code run fast.

Anthony Bullard (Dec 11 2024 at 16:51):

This was definitely one where the optimizer did it's thing

Anthony Bullard (Dec 11 2024 at 16:51):

Using Roc Run:

Part 1: 6401092019345 [26000ns]
Part 2: 6431472344710 [1000ns]

Using optimized build:

Part 1: 6401092019345 [1000ns]
Part 2: 6431472344710 [0ns]

Anthony Bullard (Dec 11 2024 at 16:52):

https://github.com/gamebox/aoc-2024/tree/main/day9

Anthony Bullard (Dec 11 2024 at 16:52):

It also is NOT a problem for functional languages :-)

Brendan Hansknecht (Dec 11 2024 at 18:05):

Your timing is broken

Brendan Hansknecht (Dec 11 2024 at 18:06):

Context is the last two messages in day 8 of aoc

Brendan Hansknecht (Dec 11 2024 at 18:07):

It's due to some sort of roc bug with ! on task

Anthony Bullard (Dec 11 2024 at 19:33):

I’ll fix it and remeasure

Anthony Bullard (Dec 11 2024 at 19:33):

Is it only for optimized builds?

Anthony Bullard (Dec 11 2024 at 19:34):

Either way I’ll check it out after work

Brendan Hansknecht (Dec 11 2024 at 20:31):

For both I think

Brendan Hansknecht (Dec 11 2024 at 20:31):

I think we desugar in a way that reorders things wrong

Last updated: Jul 06 2025 at 12:14 UTC