Advent of Code 2025 | NAMTAO Productions | Page 2

wild otter Dec 8, 2025, 1:16 PM

#

why did the n_2 move to the right

smoky owl Dec 8, 2025, 1:16 PM

#

wild otter why did the n_2 move to the right

because evaluation goes rtl

#

it's addup(square(subtract(..))

wild otter Dec 8, 2025, 1:16 PM

#

okay but it makes sense now and didnt before

#

why isnt euc distance just sqrt(this)

smoky owl Dec 8, 2025, 1:16 PM

#

wild otter why isnt euc distance just sqrt(this)

you can write it like that

#

but it misses the phenomenal symmetry that the formula has

#

distance is "under square, add"

#

square, add, sqrt

#

the first version reflects that

#

(with the subtraction at the front because we're doing two arbitrary points instead of doing it to the origin)

smoky owl Dec 8, 2025, 1:17 PM

#

smoky owl square, add, sqrt

"under squaring, add up"
it's english

wild otter Dec 8, 2025, 1:21 PM

#

very slightly faster

#

as expected, almost all the time is spent in quick_sort

smoky owl Dec 8, 2025, 1:22 PM

#

wild otter as expected, almost all the time is spent in quick_sort

i wonder, is there a fast sorting algorithm that can break out once its seen N sorted elements?

#

like, rise but with early return

wild otter Dec 8, 2025, 1:23 PM

#

smoky owl i wonder, is there a fast sorting algorithm that can break out once its seen N s...

there are so many sorting algorithms

#

all im doing is sorting

smoky owl Dec 8, 2025, 1:23 PM

#

wild otter all im doing is sorting

lmfao

smoky owl Dec 8, 2025, 1:24 PM

#

wild otter there are *so many* sorting algorithms

so, uhm
is there one that does what I said?

wild otter Dec 8, 2025, 1:24 PM

#

i didnt really understand your idea

#

oh

#

a largest k algorithm?

#

to get just the closest 1000?

#

there are some largest k algorithms, yes

#

not that useful in part 2

smoky owl Dec 8, 2025, 1:26 PM

#

wild otter not that useful in part 2

this is true

wild otter Dec 8, 2025, 1:26 PM

#

i said i wont go deep into optimizations this year but i wanna try my earlier idea

#

start with just one per box

smoky owl Dec 8, 2025, 1:27 PM

#

wild otter start with just one per box

hm?

zealous jungle Dec 8, 2025, 1:29 PM

#

i wonder if you can make a sorting algorithm that sorts a little bit, then outputs the smallest item

wild otter Dec 8, 2025, 1:29 PM

#

thats literally a binary heap

zealous jungle Dec 8, 2025, 1:29 PM

#

which you can then send to another thread and continue sorting

wild otter Dec 8, 2025, 1:30 PM

#

ok not that

#

but you could probably write something that uses a binary heap while sorting an array in the background

#

and hot swap them

#

sounds like a pain

zealous jungle Dec 8, 2025, 1:30 PM

#

i was thinking run along the entire array, bubble sort it, but also keep the minimum

wild otter Dec 8, 2025, 1:30 PM

#

hmm

#

i can imagine an insertion sort that has an atomic counter for how much is already sorted

#

so the thread thats reading the sorted array pauses when there isnt a sorted item to read

#

but that means im overlapping the reading, that takes like 5%
with sorting

zealous jungle Dec 8, 2025, 1:32 PM

#

or you can split off sorted items into a channel

wild otter Dec 8, 2025, 1:32 PM

#

that will grow from nlog n to n^2

#

sure, but thats even slower

#

hmm

zealous jungle Dec 8, 2025, 1:33 PM

#

but threads won't need to fight for the lock

wild otter Dec 8, 2025, 1:33 PM

#

what lock

#

no locks

#

just atomic counter

zealous jungle Dec 8, 2025, 1:33 PM

#

if you need to access one array from two threads

wild otter Dec 8, 2025, 1:34 PM

#

you dont need a lock

#

in rust youll probably need some unsafe cell but its fine

#

as long as you maintain that any item below the current counter will never be modified its safe

#

for how to do that..

#

you could modify some nlogn sorting algorithm to prefer sorting the start first

#

radix/quick sort would work

#

merge no

zealous jungle Dec 8, 2025, 1:39 PM

#

could also use multithreaded sort

wild otter Dec 8, 2025, 1:42 PM

#

you could
were probably at the scale it helps

zealous jungle Dec 8, 2025, 1:45 PM

#

i mean, you're spending 85% of the time sorting one million entries

#

it could help here

wild otter Dec 8, 2025, 2:01 PM

#

HUH

#

so i use a heap of heaps

#

each internal heap is a box and its distances to other boxes

#

and the heaps are sorted in the outer heap based on their peek value

wild otter Dec 8, 2025, 2:05 PM

#

zealous jungle i mean, you're spending 85% of the time sorting one million entries

and this is with parallel sorting instead

smoky owl Dec 8, 2025, 2:05 PM

#

wild otter and the heaps are sorted in the outer heap based on their peek value

insert shitpost here about peek/peak

wild otter Dec 8, 2025, 2:05 PM

#

so no need for my cursed heap of heaps

zealous jungle Dec 8, 2025, 2:05 PM

#

remove the hash maps also

zealous jungle Dec 8, 2025, 2:06 PM

#

wild otter all im doing is sorting

almost a 1% here

wild otter Dec 8, 2025, 2:06 PM

#

those are the sets

#

each circuit is a hash set

#

of box ids

zealous jungle Dec 8, 2025, 2:06 PM

#

i did it with just vecs and it was faster

#

there are limited circuit ids

wild otter Dec 8, 2025, 2:07 PM

#

this laptop isnt stable enough to measure 1% saving

#

||```rs
fn boxes_to_distances(boxes: &[(i32, i32, i32)]) -> BinaryHeap<DistancesFromBox> {
let distance_count = (boxes.len() * (boxes.len() + 1)) / 2;
let mut distances = BinaryHeap::with_capacity(distance_count);
for (idx1, box1) in boxes.iter().enumerate() {
let mut distances_from_box = DistancesFromBox {
box_id: idx1 as u32,
distances: BinaryHeap::with_capacity(boxes.len() - idx1),
};
for (idx2, box2) in boxes[idx1 + 1..].iter().enumerate() {
// correct the offset
let idx2 = idx2 + idx1 + 1;
distances_from_box.distances.push(Distance {
box2: idx2 as u32,
distance: calc_distance(*box1, *box2),
});
}
distances.push(distances_from_box);
}
distances
}
...
let mut this_box = distances
.pop()
.expect("There must be at least 1000 possible connections");
let other_box = this_box.distances.pop().unwrap();
let mut circuit1_id = box_to_circuit[this_box.box_id as usize];
let mut circuit2_id = box_to_circuit[other_box.box2 as usize];
distances.push(this_box);
...

#

my heap of heaps code

#

ignore the expect forgot to remove

zealous jungle Dec 8, 2025, 2:09 PM

#

all my structures are [bool; n*n] for connections, [usize; n] to map junction to circuit id, [Vec<usize>; n] for circuit id to vec of junction ids

wild otter Dec 8, 2025, 2:10 PM

#

yeah i know how to do it with hash maps

#

just saying i wouldnt be able to measure if its faster

#

i could if i setup the laptop with a lower clock and put it back on the stability fan ^tm

zealous jungle Dec 8, 2025, 2:11 PM

#

an array is faster than a hash map if your indexes are ints and there's a limited set of them

wild otter Dec 8, 2025, 2:12 PM

#

actually, why did i use a set

zealous jungle Dec 8, 2025, 2:12 PM

#

also you can type :tm: and discord will replace it with ™

wild otter Dec 8, 2025, 2:12 PM

#

™

#

huh

zealous jungle Dec 8, 2025, 2:13 PM

#

wild otter Dec 8, 2025, 2:16 PM

#

removed the hash, happy?

#

is there a better way to do this?

            if circuit2_id < circuit1_id {
                // make id 1 the smallest for the split
                swap(&mut circuit1_id, &mut circuit2_id);
            }
            let (s1, s2) = circuits.split_at_mut(circuit2_id as usize);
            let mut circuit1 = &mut s1[circuit1_id as usize];
            let mut circuit2 = &mut s2[0];

#

i want to take 2 mutable references from the vector

#

i know that they are always distinct

#

its checked one line up

#

its all rayon now

#

4.45% on parsing and filling the vector before the sort

wild otter Dec 9, 2025, 9:56 AM

#

todays part 2 is really hard

#

part 1 was among the easiest so far

#

and then this massive ramp up

#

I DID IT

#

visual of part 2, maybe spoiler

wild otter Dec 9, 2025, 11:11 AM

#

zealous jungle Dec 9, 2025, 12:52 PM

#

now i wonder if my convoluted solution for part 1 will work

#

nope, i don't have that much ram

zealous jungle Dec 9, 2025, 2:28 PM

#

only solution i see so far is to draw the shape an a 2d grid, fill it and then search max rectangles there walking on the edge

#

but that will take forever to write and to run

#

@wild otter no way you did that though, right?

#

i don't know how to solve it differently so whatever, i won't do the second part

zealous jungle Dec 9, 2025, 2:31 PM

#

zealous jungle but that will take forever to write and to run

i can make the "drawing" low-res so the initial search is fast, then work with the high-res version to find the exact size

wild otter Dec 9, 2025, 2:31 PM

#

zealous jungle <@205209821866229761> no way you did that though, right?

nope

zealous jungle Dec 9, 2025, 2:31 PM

#

but that's way more complicated

wild otter Dec 9, 2025, 2:31 PM

#

try to make a list of what disqualifies a rectangle

zealous jungle Dec 9, 2025, 2:52 PM

#

zealous jungle Dec 9, 2025, 3:11 PM

#

oh wow

#

#

whatever

#

it works

#

a bit faster

#

(i store the "drawing" in chunks, and added skipping empty chunks to not check everything in them)

#

@wild otter look at this cursed thing

📎 day9.rs

wild otter Dec 9, 2025, 3:37 PM

#

disgusting

#

👍

#

the real answer i was looking for is || for every potential rect, check if no consecutive pair of points draws a line that crosses into the rect||

zealous jungle Dec 9, 2025, 3:40 PM

#

mine does that but way worse

wild otter Dec 9, 2025, 3:40 PM

#

my specific solution was ||rect is invalid if one of two things is true: 1. any point is within the rect, 2. the line between any 2 consecutive points intersects with the diagonal of the rect||

zealous jungle Dec 9, 2025, 3:42 PM

#

smart

#

O(n*((n*n)/2)) solution, i think

wild otter Dec 9, 2025, 3:56 PM

#

we call that O(n^3)

#

yes

#

i took an optimization from someone i talked to of calculating all the areas first, sorting, and checking from biggest until i find a valid one

zealous jungle Dec 9, 2025, 4:06 PM

#

wild otter we call that O(n^3)

n^3 is bigger though

#

you don't need n^2 time to iterate over pairs of inputs

wild otter Dec 9, 2025, 4:07 PM

#

you need n time per pair

#

there are n^2 pairs

zealous jungle Dec 9, 2025, 4:07 PM

#

||```rust
for (i, t1) in red_tiles.iter().copied().enumerate() {
for t2 in red_tiles.iter().skip(i + 1) {
...
}}

wild otter Dec 9, 2025, 4:08 PM

#

yeah we have n^2 of these

#

i mean

zealous jungle Dec 9, 2025, 4:08 PM

#

wild otter there are n^2 pairs

well no actually?

wild otter Dec 9, 2025, 4:08 PM

#

the inner part runs n^2 times

#

O(n^2) pairs

zealous jungle Dec 9, 2025, 4:08 PM

#

n^2 includes two pairs of same two items plus a pair with same item

wild otter Dec 9, 2025, 4:08 PM

#

i think you dont understand how big O notation works

#

it removes all the smaller factors

#

50n = O(n)

#

(n^2)/2 = O(n^2)

#

n^3+n^2=O(n^3)

zealous jungle Dec 9, 2025, 4:12 PM

#

then it's just an arbitrary thing

#

not reflective of the real algorithm

wild otter Dec 9, 2025, 4:14 PM

#

not sure what youre talking about
thats how big O works

#

the goal is to reflect how it scales when the parameters grow

#

if you dont care about the scaling just dont use big O

#

its very useful to compare algorithms at a high level

#

because the scales were working on are usually past the point where performance graphs would diverge

#

insertion sort does (n(n+1))/2 comparisons and very little else, and quick-sort does, idk (30*n*log n) operations

#

i dont really need the extra stuff to know that at the scales i care for quick-sort wins

#

so instead, quick sort O(nlogn) and inseration is O(n^2), easy to see quick sort wins

white talon Dec 9, 2025, 9:23 PM

#

day 2 part2:
|| I had the fun realization that the prime finding regex would work here so I came up with this

echo ',' | cat input - | while read -a arr -d ,; do seq $(echo $arr | sed 's/-/ /') | grep -P '^(.+)\1+$'; done | sort | uniq | paste -sd+ | bc```||(Im not a bash programmer)

wild otter Dec 9, 2025, 9:38 PM

#

white talon day 2 part2: || I had the fun realization that the prime finding regex would wor...

pipe the text+a final , into the read loop,
each pair turns into an array, and the - is removed
seq prints all numbers between the 2 numbers
grep filters for ones that are repetitions
sort|uniq to dedup
paste adds + between each value
bc sums them up

i think i got it all?

#

how long does it take to run

#

0.2s on my input/machine

zealous jungle Dec 9, 2025, 9:40 PM

#

same

#

wow

wild otter Dec 9, 2025, 9:40 PM

#

thats surprisingly fast

#

only 6 times slower than my solution

wild otter Dec 10, 2025, 9:42 AM

#

todays part 2 is evil

#

finally done

#

you need to

||recognize its a linear problem||
||solve it||

#

2 is madness without a library to do it for youj

#

but theres one problem like this every year

zealous jungle Dec 10, 2025, 1:20 PM

#

okay, the dumbest solution to the part 1 isn't that slow

#

(||make a [Vec<u16>; max_states] to track transitions between states, make a vec with distances to the final state, update it while it updates, read distances[0]||)

zealous jungle Dec 10, 2025, 1:59 PM

#

for the part 2 my only idea is ||depth-first search on values||

#

but i already screwed up that in the first part and had to do a dumb but slow solution

wild otter Dec 10, 2025, 3:13 PM

#

zealous jungle (||make a `[Vec<u16>; max_states]` to track transitions between states, make a v...

some sort of dynamic programming?

#

my part 1 is just a stupid brute force

#

||recursively go down the button list and xoring the state||

#

and it was plenty fast

#

O(2^buttons) per line but there are like 10 buttons max

zealous jungle Dec 10, 2025, 4:01 PM

#

oh no

#

i made a program trhat solves part 2 test input correctly but on the real input it just hangs

#

oh nooo

#

it's just taking forever, it's not hanging

smoky owl Dec 10, 2025, 4:26 PM

#

zealous jungle it's just taking forever, it's not hanging

add progress bar and leave overnight :3

zealous jungle Dec 10, 2025, 4:35 PM

#

problem is, it solves the first line in <1ms then hangs on the second line

#

i don't know for how long yet

#

uhm

#

yea cool

#

📎 message.txt

#

alright

#

i guess i shouldn't do recursive multithreading that much

white talon Dec 11, 2025, 12:59 AM

#

smoky owl add progress bar and leave overnight :3

p much what im doing rn

#

im trying to figure out something smart

#

like where Im at rn is ||Mathematically you can express each button as a vector with unit distances in the directions corresponding to the light dimension. Well yeah that was during math class.

anyways, my current impl is||

#

thanks ducks!

#

anyhow thats not that much faster. anyhow my current impl is ||store each button associated with its lowest indexed light, and iterating over each combination which satisfies the current light, and since non of the buttons in my table can modify backwards i go all the buttons like this. Unfortunately, this doesn't guarantee that I find a minima, and i must therefore find every solution and find the minimum thereof. ||

white talon Dec 11, 2025, 1:30 AM

#

||30% of execution time is clone rn tf||

zealous jungle Dec 11, 2025, 2:06 AM

#

part 2?

#

also to find the minimum, you can have it in a AtomicUsize and read that from all searching threads

#

so as soon as one thread finds new minimum value, other threads will stop wasting their time going deeper

zealous jungle Dec 11, 2025, 2:12 AM

#

white talon anyhow thats not that much faster. anyhow my current impl is ||store each button...

i was thinking of doing that but my cpu fan gets too loud when computing and my mom is sleeping nearby so it'll wait

#

does rayon manage its threads so they won't go over the os thread limit?

white talon Dec 11, 2025, 4:59 AM

#

zealous jungle so as soon as one thread finds new minimum value, other threads will stop wastin...

nah I have to find every solution because i wouldn't know if its a global minimum

zealous jungle Dec 11, 2025, 5:00 AM

#

no, i mean, deeper than that minimum amount of steps

#

since they need to find the number of steps that's smaller

white talon Dec 11, 2025, 5:03 AM

#

oh ig yea

zealous jungle Dec 11, 2025, 5:26 AM

#

zealous jungle i was thinking of doing that but my cpu fan gets too loud when computing and my ...

it's still very slow

#

running for 5 minutes on... 5 threads? and still haven't found a solution for line 2

#

my thread spawner thingy not spawning more than 5 threads for some reason

#

WHAT

#

i'm sorry, it segfaulted??

#

weird

#

it can't solve 10 lamp specifically

#

anything else it can solve

white talon Dec 11, 2025, 5:36 AM

#

10 lamp?

#

10 lamp gotcha

zealous jungle Dec 11, 2025, 5:37 AM

#

machines with 10 lamps

#

and when i give it a test case with 10 lamps it works

#

um

#

i'm getting the weirdest errors on this day, i see

white talon Dec 11, 2025, 5:38 AM

#

safe rust?

zealous jungle Dec 11, 2025, 5:39 AM

#

yes, all safe rust

#

oh wow

#

it solved one 10 lamp machine i threw at it

#

so it works, it's just that machines are hard

#

alright, i guess i'll give it some time

#

no, it just dies

#

after running for 9 minutes it segfaults

#

oh god, joltage can be above u8

zealous jungle Dec 11, 2025, 6:11 AM

#

oooh

#

randomized the search order and it's finding solutions now

#

omg it solved that machine

zealous jungle Dec 11, 2025, 6:44 AM

#

added caching to not recompute long stuff lol

zealous jungle Dec 11, 2025, 7:00 AM

#

oh no, it almost OOM'd my pc

#

whatever, enough of this shitshow

wild otter Dec 11, 2025, 8:20 AM

#

wild otter Dec 11, 2025, 8:20 AM

#

zealous jungle oh no, it almost OOM'd my pc

still day 10 part 2?

#

i did say its one of those "you better use a library" days

#

btw warning: day 11 is one of those with a different example in part 2

#

was stuck for a bit before i noticed i need to change the example input

white talon Dec 11, 2025, 5:06 PM

#

ok im giving up on figuring out 10p2 myself

#

||Lecture time!||

#

||tbf I do have a working algo which is almost done (and hopefully correct)||

#

||I gave up tbh, I just slapped threading on it and its faster™||

wild otter Dec 11, 2025, 5:13 PM

#

white talon ||[Lecture time!](https://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pd...

dead link

white talon Dec 11, 2025, 5:13 PM

#

really?

#

works for me

wild otter Dec 11, 2025, 5:14 PM

#

is it from your university?

#

probably does some authentication

white talon Dec 11, 2025, 5:14 PM

#

no

#

just a random uni

smoky owl Dec 11, 2025, 5:15 PM

#

it's accessible for me

wild otter Dec 11, 2025, 5:15 PM

#

oh now it loaded

#

weird

white talon Dec 11, 2025, 5:15 PM

#

spoil discussion about this?

#

yea right

#

||Im not even close to comfortable with matrices for this||

wild otter Dec 11, 2025, 5:16 PM

#

white talon ||[Lecture time!](https://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pd...

i learned all that in uni but forgot by now
||Linear Optimization|| is really complicated

#

and this is not even all of it

white talon Dec 11, 2025, 5:17 PM

#

||also this will probably not even give the minima right?||

wild otter Dec 11, 2025, 5:17 PM

#

this is just ||how to solve Ax=b||

white talon Dec 11, 2025, 5:17 PM

#

||so my dumb idea was to add the equation adding up all the coefficients and iterating upward||

wild otter Dec 11, 2025, 5:18 PM

#

you wont finish running that any time soon

white talon Dec 11, 2025, 5:19 PM

#

wdym?

wild otter Dec 11, 2025, 5:19 PM

#

itll take forever

white talon Dec 11, 2025, 5:19 PM

#

nah I have 144 done already

#

||(been running for hours so lol)||

zealous jungle Dec 11, 2025, 5:20 PM

#

wild otter still day 10 part 2?

yes

white talon Dec 11, 2025, 5:23 PM

#

white talon ||so my dumb idea was to add the equation adding up all the coefficients and ite...

||or can you do like derivative magic||

wild otter Dec 11, 2025, 5:24 PM

#

not really

white talon Dec 11, 2025, 5:26 PM

#

||https://en.wikipedia.org/wiki/Triangular_matrix is the notation of a 0 in nomandsland just pad everything here with zeroes?||

wild otter Dec 11, 2025, 5:26 PM

#

you could ||use the missing amounts to click multiple times to save on iterations||

#

but that gets complicated and you need to deal with a lot of things like ||overshooting||

white talon Dec 11, 2025, 5:27 PM

#

||Binary search?||

wild otter Dec 11, 2025, 5:27 PM

#

basically turning it into some weird ||gradient descent||

wild otter Dec 11, 2025, 5:27 PM

#

white talon ||<https://en.wikipedia.org/wiki/Triangular_matrix> is the notation of a 0 in no...

yes

#

on the aoc subreddit ive effectively only seen 2 working solutions

#

||use an LP solver library||
||extremely optimized BFS with a bunch of heuristics for the order and pruning||

white talon Dec 11, 2025, 5:31 PM

#

||best way to learn matricies right?||

zealous jungle Dec 11, 2025, 11:54 PM

#

that doesn't look right lol

#

TOO LOW??

#

waity

#

what

#

it gives a different answer every time it's ran

#

uh oh

#

and it ||loops back through devices, that's not right too||

#

it ||loops back through you, which would've been caught in the first part||

zealous jungle Dec 12, 2025, 12:32 AM

#

alright..... that worked i guess..

#

(btw, there's alot of string cloning and such, i didn't bother doing it without reallocating)

wild otter Dec 12, 2025, 7:16 AM

#

day 12 sucks

#

not because it is extremely hard

#

but because it is extremely hard if you dont make the massive assumption you need to

#

my code solves the real input and not the example because of how big this assumption is

#

and its not obvious even if you do look at your input

#

zealous jungle Dec 13, 2025, 12:03 AM

#

wild otter but because it is extremely hard if you dont make the massive assumption you nee...

oh, i see lol

#

though i haven't finished 10.2 so that's the end for me

#

i did wonder ||how many trees can be solved without actually solving them, just by doing the math||

#

||though i also wonder if you do write the correct solver, will it give the same results or not||

#

does 12.2 exist or you just solve all previous parts and it gives you the last star

white talon Dec 13, 2025, 6:15 AM

#

zealous jungle does 12.2 exist or you just solve all previous parts and it gives you the last s...

the latter

wild otter Dec 13, 2025, 7:38 AM

#

zealous jungle ||though i also wonder if you do write the correct solver, will it give the same...

of course its the same

zealous jungle Dec 13, 2025, 7:39 AM

#

actually right, should've thought for a bit

wild otter Dec 13, 2025, 7:39 AM

#

if you split the trees into ||"always fits with any packing", "will never fit even with perfect packing" and "dunno solve np-hard"||
that last group is always empty

#

so i only split based on the first

#

dont even need to parse the presents

#

||filter(|area| area.size>=area.presents*9).count||

zealous jungle Dec 13, 2025, 7:40 AM

#

that relies heavily on that specific type of input

wild otter Dec 13, 2025, 7:40 AM

#

everyone got it

zealous jungle Dec 13, 2025, 7:41 AM

#

and that presents are always same size

wild otter Dec 13, 2025, 7:41 AM

#

"same size" as in, fits in 3x3

#

im pretty sure everyone got external 3x3 internal 7 squares taken

zealous jungle Dec 13, 2025, 7:42 AM

#

i think i saw ones with 3 empty in my input

wild otter Dec 13, 2025, 7:42 AM

#

sure its not the example?

#

the example has one like that

#

the example is stupid

zealous jungle Dec 13, 2025, 7:42 AM

#

2:
#..
##.
.##

#

from my input

wild otter Dec 13, 2025, 7:42 AM

#

huh

#

anyway
splitting on first group only still works

#

splitting on any number between them works

#

because of the ||emptiness||

zealous jungle Dec 13, 2025, 7:44 AM

#

||```rust
let result = 'solve: {
let total_sum: usize = counts.iter().copied().enumerate().map(|(i, c)| presents[i].active_tiles * c).sum();

if total_sum > width * height {
    break 'solve Some(false);
}

let width_fit = width / PRESENT_SIZE[0];
let height_fit = height / PRESENT_SIZE[1];
let total_presents: usize = counts.iter().copied().sum();

if width_fit * height_fit >= total_presents {
    break 'solve Some(true);
}

None

};

wild otter Dec 13, 2025, 7:45 AM

#

yeah thats kinda what i started with

#

just that i had a todo at the end

#

which is never hit

#

i then simplified to this
||```rs
pub fn part_one(input: &str) -> Option<u64> {
let mut valid = 0u64;
let mut input = &input.as_bytes()[96..];
while !input.is_empty() {
let (width, rem) = fast_parse::<u32>(input);
let (height, rem) = fast_parse::<u32>(&rem[1..]);
input = &rem[2..];
let mut presents_to_fit = 0;
for _ in 0..6 {
let (num, rem) = fast_parse::<u32>(input);
input = &rem[1..];
presents_to_fit += num;
}
if width * height >= presents_to_fit * 9 {
valid += 1;
}
}
Some(valid)
}

zealous jungle Dec 13, 2025, 7:46 AM

#

[96..] dam

wild otter Dec 13, 2025, 7:47 AM

#

printed original length-length after present parsing to get that

zealous jungle Dec 13, 2025, 7:48 AM

#

i got 6 types of presents too so ig everyone does

wild otter Dec 13, 2025, 7:48 AM

#

its always 96 on any input with 6 3x3s

#

if it changed id just do position(|&c|c==b'x').unwrap()-1 instead

zealous jungle Dec 13, 2025, 7:49 AM

#

not -2?

wild otter Dec 13, 2025, 7:49 AM

#

hm

#

actually yeah 2

zealous jungle Dec 13, 2025, 7:50 AM

#

or actually, just search back from x to the nearest \n

#

it's at most 2 bytes

wild otter Dec 13, 2025, 7:50 AM

#

if areas got above 99 id need another reverse \n search

zealous jungle Dec 13, 2025, 7:50 AM

#

width and height are always 2 digit for me

wild otter Dec 13, 2025, 7:51 AM

#

same

zealous jungle Dec 13, 2025, 7:51 AM

#

and present count are almost always 2 digit

#

singular one digit

wild otter Dec 13, 2025, 7:52 AM

#

need to parse them so you cant just skip

#

digit count only matters if youre gonna do extreme optimization on the parsing

zealous jungle Dec 13, 2025, 7:53 AM

#

you can assume they're 2 digits and very unlikely 1

wild otter Dec 13, 2025, 7:53 AM

#

could replace /10 parsing with a single lookup table

#

with that assumption

zealous jungle Dec 13, 2025, 7:53 AM

#

(bytes[0] - b'0') * 10 + (bytes[1] - b'0')

#

or a lookup yea

wild otter Dec 13, 2025, 7:54 AM

#

breaks on 1 byte

zealous jungle Dec 13, 2025, 7:54 AM

#

yea

wild otter Dec 13, 2025, 7:54 AM

#

a whole extra branch to check if its 1 or 2

zealous jungle Dec 13, 2025, 7:54 AM

#

mark it as unlikely and move on

wild otter Dec 13, 2025, 7:54 AM

#

thats probably actually a meaningful amount of time with how short this is

zealous jungle Dec 13, 2025, 7:55 AM

#

or store the width in the lookup table

wild otter Dec 13, 2025, 7:55 AM

#

zealous jungle `(bytes[0] - b'0') * 10 + (bytes[1] - b'0')`

also, replace both -'0' with a single -11*'0'

wild otter Dec 13, 2025, 7:56 AM

#

zealous jungle or store the width in the lookup table

nah, just fill the table with the space that follows in mind

zealous jungle Dec 13, 2025, 7:56 AM

#

but then lookup table should do 0 and 0\n

wild otter Dec 13, 2025, 7:56 AM

#

'1 ' is 1

#

'1\n' is also 1

#

yeah what you said

#

i did -99.9 to 99.9 parsing with a big lookup table in 1brc

#

took quite a bit of the CPU cache

zealous jungle Dec 13, 2025, 7:58 AM

#

lookup[u16::from_be_bytes(bytes) - 0x300a]

#

i think

wild otter Dec 13, 2025, 7:58 AM

#

you dont need to do hex stuff

#

11*b'0' is a constant that will computed in compile time

#

but also technically

#

you could skip the subtraction

#

if youre willing to waste that many slots

#

never accessed, not in cache
all you wasted is a tiny bit of memory

#

for my big table i used pext to construct the index from bits

#

i used pext like 4 times in aoc this year

zealous jungle Dec 13, 2025, 8:00 AM

#

couldn't you do it as const block

wild otter Dec 13, 2025, 8:00 AM

#

do what

zealous jungle Dec 13, 2025, 8:01 AM

#

the table

wild otter Dec 13, 2025, 8:01 AM

#

fill the table?

#

of course

#

my compile time on 1brc is kinda long for the amount of code there

#

because its filling the table with the const evaluation thing

wild otter Dec 13, 2025, 8:01 AM

#

wild otter my compile time on 1brc is kinda long for the amount of code there

(ignoring link time)

#

looking into the table is still at runtime obviously

zealous jungle Dec 13, 2025, 8:03 AM

#

zealous jungle the table

or make a macro that makes a giant match statement instead

#

how would rust handle that

wild otter Dec 13, 2025, 8:03 AM

#

a match statement is either a bunch of ifs, or a lookup table

#

if you want max perf, dont trust the compiler to choose the right one

#

especially when the indexing is complicated

#

also thats a fuckton of code

wild otter Dec 13, 2025, 8:04 AM

#

wild otter if you want max perf, dont trust the compiler to choose the right one

*in this case that you already know how to code a good table

zealous jungle Dec 13, 2025, 8:07 AM

#

yea alright, it makes a lookup table

#

oh sheeeesh

#

#

if input numbers are random, it makes a huge function instead

#

#

and instead of a lookup table, it does this

wild otter Dec 13, 2025, 8:14 AM

#

what did you put as input

#

nvm you show

zealous jungle Dec 13, 2025, 8:15 AM

#

random numbers

#

sampled from my aoc input lol

wild otter Dec 13, 2025, 8:15 AM

#

what changed between the 2

#

like

#

the first looks kinda random already

zealous jungle Dec 13, 2025, 8:15 AM

#

zealous jungle yea alright, it makes a lookup table

this?

wild otter Dec 13, 2025, 8:15 AM

#

yes

#

just in order 1 to whatever with values to return?

zealous jungle Dec 13, 2025, 8:16 AM

#

match arms were in straight ascending order from 0, not skipping anything

wild otter Dec 13, 2025, 8:16 AM

#

yeah makes sense

zealous jungle Dec 13, 2025, 8:16 AM

#

second one is just random on both sides

wild otter Dec 13, 2025, 8:17 AM

#

making a table from random is hard

#

maybe the range was too big or something

#

im guessing with a shorter range itll work

#

even with a few holes?

#

what does the ascending one do if you poke holes in it

#

or reorder

zealous jungle Dec 13, 2025, 8:18 AM

#

lookup table with 0s

#

(with _ => 0 in match)

wild otter Dec 13, 2025, 8:19 AM

#

what about => unreachable

zealous jungle Dec 13, 2025, 8:19 AM

#

zealous jungle Dec 13, 2025, 8:19 AM

#

wild otter what about => unreachable

function with a jump table

#

to small gadgets that return specific values

wild otter Dec 13, 2025, 8:19 AM

#

but still a lookup table?

#

wait what

#

show

zealous jungle Dec 13, 2025, 8:20 AM

#

lookup table to instruction addresses that return values

#

#

wild otter Dec 13, 2025, 8:20 AM

#

weird

#

what about unreachable unchecked

zealous jungle Dec 13, 2025, 8:21 AM

#

probably just a ud2 instead of panic..

wild otter Dec 13, 2025, 8:21 AM

#

ideally it should be able to go back to a normal table

zealous jungle Dec 13, 2025, 8:23 AM

#

yea, it does

#

except now it's 2 instead of 0 in the holes

wild otter Dec 13, 2025, 8:23 AM

#

weird choice but okay

zealous jungle Dec 13, 2025, 8:23 AM

#

fair dice roll lol

#

no, it's just always 2

#

oh wait i'm blind

#

it's .zero 2

#

i guess that's one character shorter than .short 0 ok

wild otter Dec 13, 2025, 8:30 AM

#

characters dont matter, its about the amount of asm bytes

#

i assumed itd be the same but maybe not

zealous jungle Dec 13, 2025, 8:31 AM

#

it's probably same

#

it must be same actually

wild otter Dec 13, 2025, 8:33 AM

#

are data sections just copied or are they instructions how to write the real data section

#

like
if i write .zero 10000 it could be like 16 bytes worst case and generate 10000 bytes

#

if its instructions

zealous jungle Dec 13, 2025, 8:34 AM

#

i think objects contain full data sections

#

also at about 350 entries in the lookup table it decides to replace it with a jump table

#

ah, it's about how far the items in it are apart

#

not about its size

wild otter Dec 13, 2025, 8:36 AM

#

yeah i guessed earlier

#

gaps

#

it has some heuristic to when to do a table

zealous jungle Dec 13, 2025, 8:37 AM

#

i guess it can estimate size usage for both

wild otter Dec 13, 2025, 8:37 AM

#

hmm

#

what if you have 2 dense ranges with 1 big gap between?

zealous jungle Dec 13, 2025, 8:37 AM

#

jump table long per item + mov + ret

#

jump table

#

with a big gap inbetween that points to nothing code

#

but i should check with a huge gap

#

with a gap of about 1000000000 it makes 2 jump tables

wild otter Dec 13, 2025, 8:45 AM

#

not 2 lookup tables?

zealous jungle Dec 13, 2025, 8:45 AM

#

no, jump tables

wild otter Dec 13, 2025, 8:45 AM

#

compiler suc

zealous jungle Dec 13, 2025, 8:45 AM

#

even though in those dense ranges, my values are consecutive

#

that's 3 bytes for each code block and 8 bytes for the jump table value

#

and could've been just 2 bytes for the actual value

white talon Dec 15, 2025, 2:26 PM

#

||Ok so I just did 12 and ugh i dislike this so much||

zealous jungle Dec 15, 2025, 11:44 PM

#

why

#Advent of Code 2025