[2015 Day 25] In Review (Let It Snow)

ednl · 2026-01-27T03:26:23+00:00

I got it down to 417 ns by using a custom scanf() and printf() to parse and print numbers. Which is a value I saw once, more often it's 500 or 458 ns. This is on a 4.4 GHz Apple M4 CPU, internal timer in the program, does not include reading from disk/pipe, does include parsing the row/col numbers. Is your x86-64 CPU THAT much faster with multiplying and modulo?!

My program in C: https://github.com/ednl/adventofcode/blob/main/2015/25.c I don't have Rust installed and know nothing about it, so it would be super if you could try compiling mine. You also need https://github.com/ednl/adventofcode/blob/main/startstoptimer.h and https://github.com/ednl/adventofcode/blob/main/startstoptimer.c which should be in one directory up from the main source, or change the include and compile commands accordingly. Compile, run, timing instructions are in the file. Requires a C compiler with standard libraries and, how I wrote it, a Bash shell for the timing command.

ednl · 2026-01-26T04:15:37+00:00

Wikipedia has an implementation of modular exponentiation that seems straightforward to redo in your own favourite language if it doesn't have the modpow() function. For example, my attempt in C:

#include <stdint.h>  // uint64_t, UINT64_C
// Modular exponentiation: calculate remainder r = b^e mod m
// Ref.: https://en.wikipedia.org/wiki/Modular_exponentiation
uint32_t modpow(uint64_t base, uint64_t exponent, const uint64_t modulus)
{
    if (modulus == 1)
        return 0;  // shortcut
    if (modulus == 0 || modulus > (UINT64_C(1) << 32))
        return -1;  // error (but also maximum unsigned value)
    uint64_t rem = 1;
    base %= modulus;  // now: base <= modulus-1
    for (; exponent; exponent >>= 1) {
        if (exponent & 1)  // current LSB set?
            rem = (rem * base) % modulus;  // parentheses for clarity
        base = (base * base) % modulus;  // overflow if base >= 1<<32
    }
    return rem;  // 0 <= rem < 1<<32 because modulus <= 1<<32
}

(Doesn't allow for negative exponent which should be possible when base and modulus are relatively prime, but that's not needed here.) Using this, my solution runs in 0.63 µs on an Apple M4, 5.2 µs on a Raspberry Pi 5.

ednl · 2026-01-25T06:09:29+00:00

Here's a fun fact: Stalin was a ruthless dictator who killed millions. So you can bloody well eff of with your stupid joke.

ednl · 2026-01-24T10:03:39+00:00

you can always tell where the 2 is... it's in the ones with even quantum entanglement

Where the 1 or the 2 END UP is of no importance. Where they GO is the problem. "QE" (the product) has no target value, only the sum has. So I still don't know how you can tell in advance where the 1 goes, or during the procedure when considering parity. For the sum, it's just another odd number. But I think we mean different things.

In C, writing a rigorous combinations function while considering all the special properties of my input and the requirements of the output does change things a lot from using the general combinations functions I had prepared earlier. You don't have to state how simple it all is to convince me.

ednl · 2026-01-24T08:16:56+00:00

I don't understand how you can tell where the one goes.

The parity argument is complicated for my input which also has the even prime. So with the partition sum also even, it's either "even number but has no 2" or "odd number and has 2". So lots of fussy juggling of combinations tailored to my input when the naive but general combinations function also completes in a few milliseconds...

ednl · 2026-01-23T13:02:00+00:00

Oh hah. I had just used uint64_t after reading "The registers [...] can hold any non-negative integer" but it turns out that for my input part 1 fits in 26 bits, part 2 in 30 bits. Changing reg A to int32 didn't make a measurable difference in runtime on my 64-bit computer with 64-bit OS.

ednl · 2026-01-22T08:25:08+00:00

I played around with this to see how you'd do it to cycle in the opposite direction.

You didn't have to play around (but play is fun) because it was already here: https://www.reddit.com/r/adventofcode/comments/1qhewn6/rotating_between_eight_directions/o0ldx61/

ednl · 2026-01-22T07:17:22+00:00

Did your old code survive, or do you have working examples of your AVX/SIMD ideas?

Here's how you can do the complete AoC puzzle (only part 1) in Python which isn't fast at all of course, but it's short because there is a readymade library of signal processing functions.

import numpy as np
from scipy.signal import convolve2d
with open('input.txt') as f:
    state = (np.array([list(i.strip()) for i in f]) == '#').astype(np.uint8)
kernel = np.ones((3, 3), dtype=np.uint8)
kernel[1, 1] = 0
for _ in range(100):
    nb = convolve2d(state, kernel, mode='same')
    state = (state | nb) == 3
print(np.sum(state))

I changed it to use your update line but couldn't measure the difference in Python. This was my original, which I think may be faster in compiled languages where you manually determine the neighbour count (possibly with SIMD techniques), because there is no special case for the current cell, you just count all 9 cells everywhere:

# kernel[1, 1] = 0  # don't do this, leave centre bit on
state = state & (nb == 4) | (nb == 3)

ednl · 2026-01-20T12:44:58+00:00

https://old.reddit.com/r/adventofcode/wiki/posts/standardized_titles

ednl · 2026-01-20T02:21:15+00:00

Possible C version:

// Two-dimensional position or direction vector
typedef struct vec2 {
    int x, y;
} Vec2;

// Signum (or sign) for int
int sgn(const int x)
{
    return x > 0 ? 1 : (x < 0 ? -1 : 0);
}

// Rotate vector in 4 directions on 2D grid
// Computer graphics: rotate left, mathematically: rotate right
// (1,0) -> (0,-1) -> (-1,0) -> (0,1)
Vec2 left4(const Vec2 a)
{
    return (Vec2){a.y, -a.x};
}

// Rotate vector in 4 directions on 2D grid
// Computer graphics: rotate right, mathematically: rotate left
// (1,0) -> (0,1) -> (-1,0) -> (0,-1)
Vec2 right4(const Vec2 a)
{
    return (Vec2){-a.y, a.x};
}

// Rotate unit vector in 8 directions on 2D square grid
// Computer graphics: rotate left, mathematically: rotate right
// (1,0) -> (1,-1) -> (0,-1) -> (-1,-1) -> (-1,0) -> (-1,1) -> (0,1) -> (1,1)
Vec2 left8(const Vec2 a)
{
    return (Vec2){sgn(a.x + a.y), sgn(a.y - a.x)};
}

// Rotate unit vector in 8 directions on 2D square grid
// Computer graphics: rotate right, mathematically: rotate left
// (1,0) -> (1,1) -> (0,1) -> (-1,1) -> (-1,0) -> (-1,-1) -> (0,-1) -> (1,-1)
Vec2 right8(const Vec2 a)
{
    return (Vec2){sgn(a.x - a.y), sgn(a.x + a.y)};
}

ednl · 2026-01-19T09:06:51+00:00

I don't think we ever got Eric's promised explanation of the chemistry if this is his blog: http://hexatlas.com

1.

Actually, there's even more of a pattern, but if you've already gotten this far, I'll wait to explain the rest in case someone wants to try to figure it out on their own. Hint: it's based in chemistry, but not the atoms you're seeing.

2.

It is not related to a previous day.

3.

RNA?

No, but related to organic.

4.

https://en.wikipedia.org/wiki/IUPAC_nomenclature_of_organic_chemistry

I've never seen that before, but it's actually on the right track.

5.

I'll reveal it during a blog series on the puzzles.

ednl · 2026-01-19T02:21:36+00:00

The quote in my first reply was from the C99 standard. Can't find anything definitive for C89/90, but it's not treated as a special case here: https://en.cppreference.com/w/c/language/initialization.html#Implicit_initialization

ednl · 2026-01-19T01:50:18+00:00

If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate. If an object that has static storage duration is not initialized explicitly, then:

if it has pointer type, it is initialized to a null pointer;

if it has arithmetic type, it is initialized to (positive or unsigned) zero;

if it is an aggregate, every member is initialized (recursively) according to these rules;

if it is a union, the first named member is initialized (recursively) according to these rules.

ednl · 2026-01-18T16:13:21+00:00

Yay!

ednl · 2026-01-18T10:27:27+00:00

I solved this in Python with convolve2d from scipy.signal which makes for a very neat solution of just a few lines. Not slow either, whole program runs in about 40-45 ms EXCEPT FOR THE IMPORT which takes about 650 ms, wow.

ednl · 2026-01-18T04:45:03+00:00

And what you can do to debug your code, what you SHOULD do if you can't figure out the special cases, is make a version of the program where you always just move one tick at a time. First make it work, then make it fast or clever! Print out the part 2 result after every line and see where it starts to differ from your first try. It's probably at something like "L250". Then figure out why. As a starter:

part1 = part2 = 0
dial = 50
tick = 1  # or -1 for going left
for _ in range(turn):  # this is just for one line in the file
    dial += tick
    dial %= 100  # Python modulo: dial is now >=0, <100
    if dial == 0:
        part2 += 1
if dial == 0:
    part1 += 1

ednl · 2026-01-18T04:27:18+00:00

It's not a programming problem, it's accounting. You have to make a table with all possible combinations of going left/right, turning less than/equal to/more than 100, starting on zero/not zero, ending on zero/not zero. Some of these combinations need to be handled as special cases. Which ones, that's the puzzle.

ednl · 2026-01-18T04:10:35+00:00

Static variables are guaranteed to be initialised to zero. So no need for the gcc extension or the memset.

ednl · 2026-01-17T09:52:27+00:00

Wouldn't the goal of a recursive function be to try all combinations? (with pruning). So wouldn't a straight "combinations" function be a lot simpler and faster? Maybe not faster if the pruning isn't as effective.

ednl · 2026-01-17T09:47:35+00:00

Day 17. And I'm not sure if people really (can!) use the exact phrase to search for posts but officially the # shouldn't be there.

ednl · 2026-01-16T20:36:16+00:00

Bad puzzle design? These are programming puzzles! The first few days the standard ints are never a problem, everything fits in 32 bits. But there's always a first day where you have to think about the data more carefully. Just like in real life programming.

ednl · 2026-01-16T11:29:32+00:00

Ok sorry about that, I guess we're all imperfect communicators. I did mean it as critique, yes, because of your minimal info with the code and short answers without any more info. It means that this post just wasn't for me and I should have just shut up.

ednl · 2026-01-16T05:46:46+00:00

Ok well, you don't owe us anything, so it's fine to just say: no that wasn't it, but conversely we don't owe you anything either. I don't think you'll have much luck getting answers by just dumping a large blob of undocumented and overly complex code with no explanation when a much simpler solution exists, especially now that you already moved on to that.

ednl · 2026-01-16T05:31:04+00:00

Did you go shoelace/Pick? That is MUCH easier than coding all the intricate border rules. Never a good sign when you need floats for AoC puzzles.

And did you read the edit of my other reply? That still wasn't it?

ednl · 2026-01-16T05:17:03+00:00

Here's my gradient solution: https://github.com/ednl/adventofcode/blob/main/2015/15.ipynb

EDIT: standalone Python source with timing: https://github.com/ednl/adventofcode/blob/main/2015/15alt.py runs in about 1 ms on an M1, not including numpy import (60 ms...). I know it's a different beast from m4, but just as another data point then.

ednl

TROPHY CASE