advent of code 2023

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > advent of code 2023

«‹›15 »

MrQueasy: Nov 15, 2005; Probiot-ICK

for day 13 I wrote a whole rear end parser for the input, but my buddy just used the python json corelib :rant:

# ? Dec 13, 2022 08:15

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 14:23

Cybernetic Vermin: Apr 18, 2005

MrQueasy posted:

for day 13 I wrote a whole rear end parser for the input, but my buddy just used the python json corelib

not even that needed, as pythons own eval() does it fine.

other than that though i wrote so many braindead bugs today, took way longer than it had any right to.

# ? Dec 13, 2022 10:22

The Chairman: Jun 30, 2003; But you forget, mon ami, that there is evil everywhere under the sun

really happy with my day 13 solution in Racket since all it takes is one modification to the readtable (reading commas as spaces) to get it to recognize the data file as a bunch of S-expressions, and then it's just one long match expression and a couple of for comprehensions to get the rest of the way there

code:

#lang racket
(require advent-of-code)

(define raw-packets
  (parameterize ([current-readtable (make-readtable #f #\, #\space #f)])
    (port->list read (open-aoc-input (find-session) 2022 13 #:cache #true))))

(define (compare xs ys)
  (match* (xs ys)
    [('() (list* _)) #true]
    [((list* _) '()) #false]
    [((list* a x-rest) (list* a y-rest)) (compare x-rest y-rest)]
    [((list* (? integer? x) _) (list* (? integer? y) _)) (< x y)]
    [((list* (? list? xs*) _) (list* (? list? ys*) _)) (compare xs* ys*)]
    [((list* (? list?) _) (list* (? integer? y) y-rest)) (compare xs (cons (list y) y-rest))]
    [((list* (? integer? x) x-rest) (list* (? list?) _)) (compare (cons (list x) x-rest) ys)]))

;; part 1
(for/sum ([i (in-naturals 1)] [packet (in-slice 2 raw-packets)] #:when (apply compare packet)) i)

;; part 2
(define divider-packets (list '((2)) '((6))))
(define amended-packets (append divider-packets raw-packets))

(for/product ([i (in-naturals 1)] [packet (in-list (sort amended-packets compare))]
                                  #:when (member packet divider-packets))
             i)

# ? Dec 13, 2022 14:36

Cybernetic Vermin: Apr 18, 2005

upset by my initial messing up i decided to go back and commit some crimes, this time in julia

code:

inp=[eval(Meta.parse(x)) for x in readlines(open("in")) if x!=""]

Base.isequal(x::Int,y::Vector)=Base.isequal([x],y); Base.isless(x::Int,y::Vector)=Base.isless([x],y)
Base.isequal(x::Vector,y::Int)=Base.isequal(x,[y]); Base.isless(x::Vector,y::Int)=Base.isless(x,[y])

p1=sum(findall(map(x->x[1]<x[2],inp[i:i+1] for i in 1:2:length(inp))))

inpx=sort(vcat(inp,[[[2]],[[6]]]))
p2=findfirst(x->x==[[2]],inpx)*findfirst(x->x==[[6]],inpx)

this monkeypatches comparisons in a breaking way, so never do this in reality.

Cybernetic Vermin fucked around with this message at 15:22 on Dec 13, 2022

# ? Dec 13, 2022 15:06

DrPossum: May 15, 2004; i am not a surgeon

MrQueasy posted:

for day 13 I wrote a whole rear end parser for the input, but my buddy just used the python json corelib

# ? Dec 13, 2022 15:57

cool av: Mar 2, 2013

MrQueasy posted:

for day 13 I wrote a whole rear end parser for the input, but my buddy just used the python json corelib

I spent a few minutes thinking about how to write a parser before realizing I should just use a JSON lib. but then discovered some weird poo poo in the newtonsoft JToken class (JArray.Values() flattens any nested lists) that cost mew a few more minutes; so worst of both worlds

# ? Dec 13, 2022 16:15

MrQueasy: Nov 15, 2005; Probiot-ICK

Day 14 is also amenable to animation in a way. Attempting to render the grains as they fall is proving trickier than I thought. I think I need to record the states and then filter out some to make the grains fall fast enough.

Here's just the final resting points appearing to "spawn in".

# ? Dec 14, 2022 08:14

MrQueasy: Nov 15, 2005; Probiot-ICK

Only displaying 1:1000 frames...

https://i.imgur.com/i9smyAr.gifv

Sorry, can't timg a gifv, and I'm too vain not to have it display in the thread.

# ? Dec 14, 2022 19:05

Petanque: Apr 14, 2008; Ca va bien aller

thanks op, i made those sorting algorithm sounds in my head watching that fill up

# ? Dec 14, 2022 20:37

Cybernetic Vermin: Apr 18, 2005

yeah, super-neat visualization. i had nothing very interesting to say about today, have a cold and slogged through it anyway, suspect i'd have enjoyed it a happier day.

# ? Dec 14, 2022 20:50

Athas: Aug 6, 2007; fuck that joker

I have a hunch that today can be parallelized in an interesting way, but I did not have time to do so, and it probably would not be efficient anyway.

# ? Dec 14, 2022 23:55

DrPossum: May 15, 2004; i am not a surgeon

mine too a while to fill

# ? Dec 15, 2022 00:21

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

I think you could probably solve part 2 without any simulation, by calculating the area of the "shadows" underneath the rock and subtracting that from the whole triangle.

Very inefficient use of time if you already wrote a simulation for the first part though.

# ? Dec 15, 2022 00:34

Lime: Jul 20, 2004

here's my gif, the sim runs multiple grains per frame, adding one every frame. that kept the frame count down but it was still pretty slow, so this is every tenth frame

# ? Dec 15, 2022 03:00

cool av: Mar 2, 2013

hats off to everybody who managed to not waste 10+ minutes on the absolute minefield of off-by-ones today

edit: cool visualizations. you'd never notice the "structures" in the input w/o doing a visualization

# ? Dec 15, 2022 07:12

Peewi: Nov 8, 2012

cool av posted:

hats off to everybody who managed to not waste 10+ minutes on the absolute minefield of off-by-ones today

I instead spent way longer on a much sillier problem.
I just used ints for everything, so the step of multiplying x by 4 million was overflowing and I didn't understand why I was getting the right answer for the sample input, but a wrong answer for the real input.

# ? Dec 15, 2022 07:44

MrQueasy: Nov 15, 2005; Probiot-ICK

I'll have you know I only had to restart once due to too much memory use.

# ? Dec 15, 2022 08:57

echinopsis: Apr 13, 2004; by Fluffdaddy

DrPossum posted:

more like advent of chode

# ? Dec 15, 2022 10:17

Cybernetic Vermin: Apr 18, 2005

first day where i had a real 'huh, how am i going to manage that on part 2', had some coffee, realized i was being rather crude in part 1, and then the coding went smoothly. i expect this could be tackled in numerous ways.

# ? Dec 15, 2022 11:15

FalseNegative: Jul 24, 2007; 2>/dev/null

Obligatory day 14 visualization - Part I only

https://i.imgur.com/GvqEnHd.mp4

# ? Dec 15, 2022 13:35

DrPossum: May 15, 2004; i am not a surgeon

I wrote some code to build the collective exclusion ranges for a row and then scanned line-by-line looking for a hole. Took a minute to run but worked. I feel like there might be something more elegant like working in a space rotated by 45 degrees (which wouldn't be appropriate for part 1 I think)

# ? Dec 15, 2022 16:52

Cybernetic Vermin: Apr 18, 2005

i also figure a suitable csg or polygon manipulation library would trivialize it, and i suspect that would have been a more interesting way to do it. didn't know one off-hand and started too dumb though.

# ? Dec 15, 2022 16:57

The Chairman: Jun 30, 2003; But you forget, mon ami, that there is evil everywhere under the sun

I had the right algorithm for part 1 for this one but I kept getting the wrong answer because I made a really dumb parsing mistake in reading the data file

turns out numbers can be negative too

# ? Dec 15, 2022 17:42

DrPossum: May 15, 2004; i am not a surgeon

The Chairman posted:

turns out numbers can be negative too

the greatest mistake including null

# ? Dec 15, 2022 18:53

Cybernetic Vermin: Apr 18, 2005

i for the record very deeply appreciate how aoc is unapologetically 1-base indexed. i solve very few in languages that are (sometimes julia sneaks in), but let's not pretend that you're describing a real thing where "elf 0" is a thing.

# ? Dec 15, 2022 18:58

MrQueasy: Nov 15, 2005; Probiot-ICK

DrPossum posted:

I wrote some code to build the collective exclusion ranges for a row and then scanned line-by-line looking for a hole. Took a minute to run but worked. I feel like there might be something more elegant like working in a space rotated by 45 degrees (which wouldn't be appropriate for part 1 I think)

Using Java's parallel streams from inside Kotlin, I did exactly this, but it took around 500ms

# ? Dec 15, 2022 22:09

cool av: Mar 2, 2013

Cybernetic Vermin posted:

i for the record very deeply appreciate how aoc is unapologetically 1-base indexed. i solve very few in languages that are (sometimes julia sneaks in), but let's not pretend that you're describing a real thing where "elf 0" is a thing.

they had monkey 0 in the monkey one and i appreciated it

# ? Dec 16, 2022 00:41

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Ugh, this puzzle is tough. The input is too big to totally brute-force, but my first attempt at a greedy algorithm demonstrably fails on the sample input...

# ? Dec 16, 2022 14:30

cool av: Mar 2, 2013

first one this year where i had to go to bed before finishing. i got a promising idea to try tonight tho

# ? Dec 16, 2022 15:28

Cybernetic Vermin: Apr 18, 2005

Jabor posted:

Ugh, this puzzle is tough. The input is too big to totally brute-force, but my first attempt at a greedy algorithm demonstrably fails on the sample input...

not had time to really try part 2 yet, but i think it is intended to be quite brute-forceable with some small optimizations; keeping only the deduplicated state for the last minute, noting that you have a number of valves statuses that can fit in a 64-bit integer, and so on. but it seems decidedly non-trivial to work through, which is why it moved from a coffee-break task to an after-work task.

Cybernetic Vermin fucked around with this message at 21:06 on Dec 16, 2022

# ? Dec 16, 2022 15:57

Lime: Jul 20, 2004

my first approach for part 2 that works was doing a breadth-first search and tracking for every triple of (my position, elephant's position, bitset of remaining valves) that i've seen, what the best flow there was. if a later path comes to back to that state with a lower total flow, then there's no point continuing. this made runtime / memory use feasible but at worst i still had 28 million paths in flight and it took about 25 seconds.

my best version now also does some preprocessing of the graph to cache for each node the distance to each valve. then during the BFS, for a given path i can take the bitset of remaining valves and the remaining time and calculate a (very) conservative bound for the best possible additional flow. if that still doesn't exceed the best flow i've seen so far, then i forget the path. with this i have at worst only 1.5 million paths in flight and the whole thing finishes in < 2 seconds. i think there's still a lot of options for tightening that bound and getting better pruning but i may quit here.

EDIT: never mind, with a better (but still very loose) bound that only counts a valve's potential flow once between me and the elephant, the path set shrunk to half a million at worst, and runtime is under 300ms.

Lime fucked around with this message at 21:27 on Dec 16, 2022

# ? Dec 16, 2022 21:05

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Ended up throwing out my first approach and starting over.

Aggressively pruning the search tree was essential to getting a reasonable runtime, I still don't think it's achievable by micro-optimizing a search over the entire space.

# ? Dec 17, 2022 02:32

cool av: Mar 2, 2013

finally got it, a bit dirty but fun one

My part 1 which did a full search of the space (after pruning out the 0-score nodes) ran fast enough that I figured I would just store every possible viable > 0 scoring "route" through the graph.

There were only ~ 1 million routes for 30 minutes and around ~400,000 for 26 minutes.

Then it's just a matter of finding the best pair of those routes that don't overlap, which isn't too hard with some sorting and hashset comparisons.

# ? Dec 17, 2022 02:51

cool av: Mar 2, 2013

Lime posted:

my first approach for part 2 that works was doing a breadth-first search and tracking for every triple of (my position, elephant's position, bitset of remaining valves) that i've seen, what the best flow there was. if a later path comes to back to that state with a lower total flow, then there's no point continuing. this made runtime / memory use feasible but at worst i still had 28 million paths in flight and it took about 25 seconds.

my best version now also does some preprocessing of the graph to cache for each node the distance to each valve. then during the BFS, for a given path i can take the bitset of remaining valves and the remaining time and calculate a (very) conservative bound for the best possible additional flow. if that still doesn't exceed the best flow i've seen so far, then i forget the path. with this i have at worst only 1.5 million paths in flight and the whole thing finishes in < 2 seconds. i think there's still a lot of options for tightening that bound and getting better pruning but i may quit here.

EDIT: never mind, with a better (but still very loose) bound that only counts a valve's potential flow once between me and the elephant, the path set shrunk to half a million at worst, and runtime is under 300ms.

I'm curious how tracking that triple and doing 1 BFS is enough, aren't there points in "time" when you or the elephant are "between" nodes?

EDIT: nvm. The "between node" thing was an artifact of my dubious optimization of pruning out all the 0-score nodes

# ? Dec 17, 2022 02:55

cool av: Mar 2, 2013

uhhhh idk what I was doing for today's but staring at the data long enough to find a repeating pattern and then coding in a bunch of random magic numbers got the job done

# ? Dec 17, 2022 07:44

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

The whole find a fixed point so you can skip a whole bunch of stuff in the middle comes up a kinda regularly. It's generally a pretty good complication.

# ? Dec 17, 2022 10:42

Cybernetic Vermin: Apr 18, 2005

yeah, today is absolutely not easy, but i think it is instructive, not so much a real-world use-case as an exercise in considering what is the relevant state in your code, here being the profile of the *top* of your tower, 7 *relative* integers removing the total height below that profile, plus the piece and jet cycle positions. in small annoyances there are inputs where this fails, at least the way i did it i.e. when one of the columns is left untouched i will never discover a period. kind of a common small flaw in aoc, having it be vastly easier to make some assumptions you wouldn't normally know hold.

Cybernetic Vermin fucked around with this message at 12:23 on Dec 17, 2022

# ? Dec 17, 2022 12:18

Athas: Aug 6, 2007; fuck that joker

Finally managed to bruteforce day 16 in 19ms by running it on an expensive GPU.

Not really a fan of the later AOC problems as the social aspect becomes lost. I have enough free time to push through, but many of my friends have to stop because they can't allocate this many hours for a daily programming challenge. Is there an alternative to AOC that keeps the difficulty more even? I think I would prefer that. I miss being able to discuss the problems with my friends.

Athas fucked around with this message at 13:47 on Dec 17, 2022

# ? Dec 17, 2022 13:24

Cybernetic Vermin: Apr 18, 2005

yeah, i do like tackling some of the more difficult problems, but most of the fun is chatting about it with various friends who these days program very little outside aoc, and are generally busy. so i generally prefer if aoc leans towards some puzzling more than actual programming.

Cybernetic Vermin posted:

not had time to really try part 2 yet, but i think it is intended to be quite brute-forceable with some small optimizations; keeping only the deduplicated state for the last minute, noting that you have a number of valves statuses that can fit in a 64-bit integer, and so on. but it seems decidedly non-trivial to work through, which is why it moved from a coffee-break task to an after-work task.

reporting back in on this a python solution which basically maintains a dictionary of all (my position, elephant position, state of valves) -> highest flow achieved, then does a minute at a time tracking all such states, ran in about 30 minutes (so in a language not hilariously slow like python it should be in the realm of extremely doable). the deduplication inherent in that setup is no doubt necessary, and beyond that i marked all valves with 0 flow already open, but that's it for optimization. last simulation step had ~70 million states.

# ? Dec 17, 2022 13:45

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 14:23

Lime: Jul 20, 2004

absurdly long tetris gif, runs until the fixed point

Lime fucked around with this message at 14:40 on Dec 17, 2022

# ? Dec 17, 2022 14:17

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > advent of code 2023

«‹›15 »