Advent of Code

emanresu A

03:58

1h

Redwolf Programs

04:36

→ 13 awkward ruined joke moved to The Nineteenth Bakery

So uh...

emanresu A

23m

Redwolf Programs

I hope today's is easy

But not for other people

emanresu A

I hope today's is a challenge from here

(I hope both parts are)

Redwolf Programs

04:56

4m

Quiet today

The Fifth Marshal

3.5m

2m

Redwolf Programs

1m

tjjfvi

1m

Redwolf Programs

glhf

hyper-neutrino

finished showering and brushing my teeth and whatever just like a minute ago

pretty good timing

emanresu A

04:59

glhfaggnbr

Unrelated String

wow

emanresu A

@hyper-neutrino *at midnight8

good luck have fun achieve gold get ninjad by redwolf

Unrelated String

05:10

well since my part 1 is having massive performance issues and the leaderboard is already fucked for it i guess it's time for a premature start to part 2

emanresu A

844 p1

Unrelated String

...my part 1 is also wrong

oh wait nvm

emanresu A

You can guess what p2 is

Unrelated String

shocking

emanresu A

And I'm kinda stuck on how to do p2 again

Unrelated String

05:14

i have a
vague
idea

only 4 people have finished it so far

emanresu A

If python had 3d ranges I'm sure you could run a naive solution with that

Unrelated String

i
doubt it

actually i guess?

depending on the implementation

but i doubt it lol

hyper-neutrino

well my code is taking

a while to run

Unrelated String

i can imagine

hyper-neutrino

i accidentally ran the joint command in the second window

so it re-ran my test even though i was trying to run them parallel

Razetime

05:17

@UnrelatedString how do you check this btw

Unrelated String

stats tab

emanresu A

10 now

Razetime

@emanresuA way too slow imo

emanresu A

Tip: Use regeg

Unrelated String

h

what

Razetime

05:19

what?

emanresu A

/(on|off) x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)/

Razetime

no regex in my language

emanresu A

I just need a way to calculate the intersection of two cuboids...

this is the first time I've written a function taking twelve arguments

Unrelated String

uh

i have a really good idea of the general outline of how to do this and a really bad idea of how to implement it

Razetime

so all of the points inside are off initially right

Unrelated String

05:26

ye

hyper-neutrino

ok idk why i thought that'd work

3d segtree time

i don't think this is necessary

emanresu A

I had an idea then realised it was O(2^n) where n is the number of instructions...

(Worstcase, it's probably more like O(2^n/2)

hyper-neutrino

my computer is intermittently freezing

i am concerned my program will crash my computer before i get my answer

Unrelated String

one of my solutions that i almost went through with is worst case at least exponential but probably bnetter in practice but i'm still not going to do that shit

emanresu A

Actually no

My sol's O(26^n) worstcase

Unrelated String

05:29

that's literally the same but also how 26

emanresu A

Oh wait no, O(6^n)

My idea was basically how you'd do this if it was 1d, keeping track of ranges where it's on

Unrelated String

O(6^n) is still literally the same as O(2^n) because it's a constant factor but yeah i think you're doing wait no the shit i was thinking of would fucking
divide regions into up to *8* new ones

btnlq

my p2 solution (pypy) used 4 gb but finished successfully
it's O(n^4) time and O(n^3) memory

Bubbler

@UnrelatedString O(6^n) is strictly worse than O(2^n).

Unrelated String

asymptotically

Bubbler

05:33

asymptotically worse

emanresu A

Probably worse than naive approach

Unrelated String

wait am i forgetting something

fuck

emanresu A

@btnlq Where n is?

Unrelated String

okay wait yeah that's how that works

btnlq

@emanresuA number of steps

hyper-neutrino

05:38

ah i'm stupid

Unrelated String

same

hyper-neutrino

ok my code will finish within today

k now my code is taking 18 years to sum the thing

4/84

lmfao

emanresu A

Ugh... this is pain

I thought the hard ones were over

hyper-neutrino

lol why

these last few days are like

all hard

ok maybe i wasn't expecting this much on a weekday either

today's problem is actually really good (IMO)

very easy spec that is very challenging and requires some thinking

Unrelated String

^

Razetime

05:45

yeah it is good

hyper-neutrino

leaderboard closed at 43:54

Razetime

deceptively not easy

hyper-neutrino

this would be a good one for a video methinks

Unrelated String

yeah

hyper-neutrino

i also should implement hover spoiler into my library

Razetime

05:49

the only idea i can think of is just splitting the cube into multiple cuboids

this i have no idea how to implement

tjjfvi

That was fun

115/109

so close

hyper-neutrino

aw, so close. good job tho :D

Unrelated String

i'm trying a really scuffed intersect everything and offset double counting directly approach but i'm trying it on just the part 1 stuff and it's... slow

tjjfvi

@Razetime That's what I started to do but I switched courses midway through

Unrelated String

^

hyper-neutrino

05:51

i did that and then did it a worse way and then did it a third time

all three times were correct the first two were just really fucking slow

and also i was missing three characters that cost me like 5 minutes of debugging

tjjfvi

How did you do it in the end?

Unrelated String

oh of course i just hit an infinite loop

tjjfvi

I spoiler

Redwolf Programs

I'm currently trying to split into sub-regions, is that what y'all are doing?

Unrelated String

i was doing that

hyper-neutrino

05:54

@RedwolfPrograms that is how i did it

like quite early on i was like "yeah this is obviously a sparse array problem"

and then failed to do it correctly twice

tjj's approach sounds very interesting tho

Redwolf Programs

Does anyone know if there are there any triple intersecting points?

tjjfvi

Here's my solution: github.com/tjjfvi/aoc-2021/blob/main/solutions/2021-22-2.ts (slightly cleaned up)

Unrelated String

of course i'm double counting the subtractions now

Redwolf Programs

@RedwolfPrograms Update: There are

I literally have no idea what to do, my current solution is just too slow

I don't wanna just copy tjjfvi's

Wait hang on

I'm an idiot

hyper-neutrino

oh i ended up with

Redwolf Programs

06:02

My approach would've worked

hyper-neutrino

a different way of handling intersecting points between regions

Redwolf Programs

I was just doing it wrong

hyper-neutrino

i just add one to the end coordinate and use half-exclusive

Redwolf Programs

@RedwolfPrograms Wait it wouldn't have

I have literally no idea what to do

Did anyone else use exclusive range on p1 by mistake

That cost me a rank :/

Ugh I don't even know where to start

Bubbler

Two predictions:
- AoC is getting algorithmically tougher every year since 2020
- hyper will get a lot of job offers

3

Redwolf Programs

06:09

:(

I'm so lost

I don't even know where to begin

I don't get why tjjfvi's sol works

Wait, I think I sort of do now?

Ugh, I hate this so much

Redwolf Programs

06:31

I've practically ported tjjfvi's at this point and it's still wrong :/

Unrelated String

rip

hyper-neutrino

@Bubbler lmao, i hope

Redwolf Programs

Hang on...my volume is going down over time

That's not supposed to happen

hyper-neutrino

uh

Redwolf Programs

Wait nvm

Wait no it is

Unrelated String

06:39

of course my intersection code itself is fundamentally broken

...and i think the fix would have been easier to write in the first plac

e

Redwolf Programs

Wait same

D:

Unrelated String

so now i'm only off by 1 on the first example

got it fully working on the first example and was on the verge of saying "wow, i guess the rest of the logic wasn't as shit as i worried" and then i ran the second example with just the stuff in the part 1 zone and it gave me 53012372

Redwolf Programs

Day       Time  Rank  Score       Time  Rank  Score
 22   00:08:27   323      0   01:46:57   979      0

:/

Razetime

so i was thinking about splitting stuff and I'm worried how i am supposed to hadle having a "off" block in the middle of an "on" block

Redwolf Programs

Today seems like it was way harder for me than for other people and I don't know why that is

Unrelated String

06:49

@Razetime you can probably split in each plane

Redwolf Programs

I guess I need to get a more thorough understanding of 3d space

Unrelated String

yeah

same

Razetime

3d in general is a huge pain

hyper-neutrino

@Razetime yeah i just split into 27 blocks like unrelated said

tbh i wish this problem were 2d

3

Redwolf Programs

@hyper-neutrino Wait that works?

hyper-neutrino

06:52

more reasonable execution time/size and much easier to imagine

@RedwolfPrograms yeah

Unrelated String

i was thinking more like 8 blocks but that works too

hyper-neutrino

how i do it is

Redwolf Programs

I did 27 then some filtering (so up to 15)

hyper-neutrino

along every x coordinate that exists across all block edges, i cut my space

and same for each axis

so for the real input, i cut my space into uh

about 512 million blocks

which explains why it takes so long to run

it takes about 1 second to update like, 5 or so blocks maybe?

Redwolf Programs

Ohh, so I wasn't doing something wrong

hyper-neutrino

06:53

and then took a solid minute and a half to sum the result

Redwolf Programs

I started to get lots and lots of cuboids, so I just stopped doing it since I figured it was too slow

hyper-neutrino

ah

Redwolf Programs

Well, I'm glad my initial solution would've worked if I'd stuck with it, I feel like the solution I ended up with was more AviFS/tjjfvi's than my own

hyper-neutrino

there is

definitely a smarter way to do it

in fact, i'm 99% sure i already have a much smarter on in mind. do i care enough to go back and implement it? no

although for my library

i am probably building an efficient n-d sparse array utility

Redwolf Programs

Wait would that have worked here?

(No, it seems)

Razetime

07:00

ok so analyzing my input it looks like none of my given cuboids are completely within each other

Razetime

07:17

nvm that was wrong

Unrelated String

rip

i thought my problem was with how i handle intersections of deleted regions but looks like i'm going way over the result before hitting any deleted regions other than the ones i insert in intersections of added regions

maybe i just want to go back to dividing lmao

Razetime

man i do not get this problem lol

tjjfvi's solution looks so oddly small

i just do not get it

Unrelated String

i still haven't looked at it lol

hyper-neutrino

07:33

oh that is quite small

here's mine, which is also... smaller than i remembered it being github.com/hyper-neutrino/advent-of-code/blob/main/2021/…

Unrelated String

...
...i'm going to go backwards
maybe that'll make it make sense

hyper-neutrino

also really fucking slow - @tjjfvi how long did yours take to run

emanresu A

07:48

AOoh just thought of how

Unrelated String

i think i may have finally gotten something working by cycling back through every single ting i already tried before reversing it

let's fucking go

that was

an experience

hyper-neutrino

pog

Unrelated String

1009/1815 😎

having just committed that abomination reminds me

@emanresuA by the way i did literally talk about writing that

so i'm actually kind of surprised nobody got it lmao

so yeah my approach finally worked when i decided not to try treating off-commands the same as existing intersections by treating them the same as on-commands instead

emanresu A

Oh lol

I'm going to start on p2 now

I don't understand how everyone's works..

I'ma use the division approach with one key difference: remerging

Razetime

08:04

this Advent of Code was sponsored by Blender™️

someone with blender scripting knowledge has to have made this work

emanresu A

Check the subreddit lol

Unrelated String

btw my solution runs in like 3 seconds

emanresu A

@UnrelatedString ...should take 5-6

p1 held me up for ages because I forgot JS flat without args flattens by a single level...

Unrelated String

worst case 8 since you could have something completely inside another

emanresu A

No, that's 6

Unrelated String

08:10

wait yeah that is 6

i might need food

emanresu A

I've just realised - the only difference between adding an on cuboiud and an off cuboid is that with the on one you return one more cuboide

Unrelated String

backwards that is at least

oh yeah or doing the division thing

yeah

fundamentally both have to cancel the intersections

emanresu A

08:32

I've taken apart a rubik's cube to visualise division

hyper-neutrino

lol

Unrelated String

the marginal advantage of my having taken a masking approach is i could pretty much just think about 2d

emanresu A

CMQ: Which day has had the biggest difference between p1 and p2?

Unrelated String

completion?

i assume proportional if so because otherwise day 3

emanresu A

Difficulty, for you

Unrelated String

08:39

day 8

emanresu A

d8 was kinda fun

Unrelated String

ye

emanresu A

@Bubbler If hyper gets a lot of job offers, do I get 1 for beating hyper once?

Ooh today's AoC gave me an idea for a challenge which I'll writeup once I'm done

Got division working correctly

Razetime

with the help of reddit and splitting everything a lot and dying i finished part 2

emanresu A

Guys I think Lyxal hacked AoC again

there are exactly 420 instructions

Razetime

09:01

Wait @hyper-neutrino how did amending a grid of 2^50 cubes work?!

hyper-neutrino

what

Razetime

ok maybe i don't understand your solution propely

emanresu A

Bruh I forgot to use inclusive ranges

Razetime

@hyper-neutrino oh wow ok, so you're making a 3d grid for all uniques x,y,z values and partitioning that way?

emanresu A

Should I reconstruct a substantial chunk of my code or add some ones and hope it works?

hyper-neutrino

09:08

@Razetime yeah

emanresu A

It's clever and fast to code but slow to run

Razetime

i wish i thought of that earlier

hyper-neutrino

with 1d it's a pretty standard sparse array

for 3d it's... quite inefficient

i'd need to do it a lot more intelligently

Razetime

so yours is doing a similar thing to what ngn's is doing as well.

interesting

context

emanresu A

So, when running my code on one of the samples for p1, I got... 11.6 billioon

For context, the volume of the 101x101x101 cube is 1.03 million

Razetime

09:22

uhhh

what's going on there

emanresu A

I have no idea :P

Razetime

p1 shouldn't be that hard but if you're solving for p2 along with it then it gets.. hairy

emanresu A

>The wide range of benefits in pythons has made people choose them for development

Source

Feels like it was written by an AI

Razetime

for a moment i thought that was your code

hyper-neutrino

> Node.js vs Python before going into the topic, it is better to know what Node.js and Python mean. Of course, in general words, it can also be called a programming language, but people call Python as a language python and Node.js as Node.

yeah i do not understand this

emanresu A

09:49

oh

I'm pushing a duplicate copy of new cuboids for every cuboid it intersects...

VICTORY!!!

My code, surprisingly simple

1.5s lol

844/2830

Razetime

10:11

wpwp

mine is very similar lol

emanresu A

Aren't you using BQN?

Or are you just also using the division approach?

Razetime

yep but BQN can do the same thing as well :)

emanresu A

True lol

Razetime

see github.com/razetime/AOC2021-BQN/blob/main/22.bqn#L23

emanresu A

Oh wow I see what you mena

emanresu A

10:53

It's a shame github doesn't recognise BQN as a language

Razetime

oh we are gonna be pushing that hard

tjjfvi

16:38

@hyper-neutrino 200ms

hyper-neutrino

damn

maybe i do need to rewrite my solution

The Fifth Marshal

18:03

I finally finished (444/6188)

And my approach also took a really long time

emanresu A

22:22

@TheFifthMarshal What was your approach to p2?

(Mine / razetime's / unrelatedstring's was cube division, hyper's was dividing space up into a bunch of chunks based on unique x/y/z coords)

Transcript for