[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / pw / qst / sci / soc / sp / tg / toy / trv / tv / vp / vt / wsg / wsr / x / xs] [Settings] [Search] [Mobile] [Home]
Board
Settings Mobile Home
/g/ - Technology


Thread archived.
You cannot reply anymore.


[Advertise on 4chan]


onsen edition

>Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.
https://adventofcode.com/

/g/ leaderboard join code:
796940-44255af5
anonymous-only leaderboard:
383378-dd1e2041

previous thread: >>103568820
>>
The brutal ones are being saved for the weekend aren't they
>>
File: tabular.png (118 KB, 708x580)
118 KB
118 KB PNG
@cachefags need not apply
>>
File: Untitled.png (19 KB, 901x760)
19 KB
19 KB PNG
>>
>>103574305
"Eric said it's okay to use AI after the leaderboard fills, which it has"
>>
>>103574304
manual cache is not better than automatic cache
>>
>>103574317
i am not using manual cache; i am using a list
>>
>>103574330
that list is a cache
>>
>>103574305
>all eric needed to do was to add a few slurs into the puzzle
>>
>>103574334
yes, but @cache is not a substitute since i solve iteratively
>>
File: im-1734617118087.png (55 KB, 692x437)
55 KB
55 KB PNG
>>103574304
top-down pytoddler yields to superior tabular approach.
>>
>>103574363
it's you again; your terminal emulator is really nice
yield accepted
>>
eric dp my anus
>>
File: 1720417967222186.jpg (39 KB, 1365x767)
39 KB
39 KB JPG
had to look at how to solve part 2
>>
File: carbon (10).png (266 KB, 1818x1284)
266 KB
266 KB PNG
Eric has given up or what's up with these past 2 puzzles? These would be days 5-10 in past years.
>>
>>103574429
you could tell me today was the 2nd - 5th and i would believe you
>>
File: nick-point-laugh.jpg (31 KB, 533x475)
31 KB
31 KB JPG
>>103574407
filtered
>>
>>103574372
oh no i wasn't the one bickering with you about the dp solve, but i do recognize the superiority of tabular. some other coping anon.
>>
>>103574471
no i mean i remember your terminal from previous threads; some other anon asked about the scan line shader / background
>>
File: file.png (1.02 MB, 1739x1232)
1.02 MB
1.02 MB PNG
>>103574458
>>
>>103574483
haha yeah it's literally this
>>
File: nickthespick.jpg (70 KB, 651x1024)
70 KB
70 KB JPG
>>103574486
say nick the spick ONE MORE FUCKING TIME
>>
>>103574304
>I am superior for doing more manual indexing
>>
>>103574305
just tell it to roleplay as the grinch
>>
>>103574538
you have to pass the state `(i)` in your recursive solution too, dumbfuck
>>
do you people even enjoy doing this
>>
>>103574573
At the very least it's something fun to talk about for the season
>>
>>103574573
yes i enjoy Christmas puzzles
>>
>>103574573
this year isn't as fun
>>
>dpdpdpd
>topdownbottomuptopdownbottomuo
aaaaaaaaaaaaaaaaaaaaaaaa fuck you fuck you fuck you fuck i hate dp so fcukimg much aaaaaaaaaaaaaaaa
>>
>>103574602
>dp memoisation top-down bottom-up push pull
cry more, faggot
>>
>>103574567
Thankfully, Python strings have lots of methods that let you compare and manipulate strings without having to do manual indexing.
What is it with the "people" on this board managing to brag about the most retarded shit possible?
>>
>>103574573
I did last year, but this year was dogshit
>>
>>103574614
>his state is a sliced string
are you actually retarded?
>>
>>103574619
this year is so boring I've mostly been going back on previous years and doing those instead. the christmas tree one was mildly entertaining for the visual aspect alone and the reverse engineering one was ok too
>>
>>103574637
i think the reverse engineering one was the best by far
>>
>>103574637
>>103574619
>>103574585
Filtered
>>
>>103574724
can you faggots shut the fuck up please
>>
>>103574744
Filtered
>>
>>103574630
Obviously, it's the natural representation of the problem and even lets me reuse cached values for different input lines with zero effort.
And it somehow runs about three times faster than your gay solution, huh. Yes I actually tested it because you're a faggot.
>>
>>103574770
>contributes nothing and shits up the thread
fucking kill yourself
>>
File: baseddepartment.png (358 KB, 600x1079)
358 KB
358 KB PNG
>>103574770
>contributes nothing and shits up the thread
>>
File: carbon.png (989 KB, 1700x4604)
989 KB
989 KB PNG
Fairly easy day, but had a long runtime before. Wrote a simple trie, runs in ~400µs.
>>
>>103574649
not a high bar to beat when the rest are all snorefests
>>
>>103574847
Good time. I got like 35ms using DP. I wonder whether the difference is in the approach, or the fact that I am constructing lots of strings. Should rewrite using sub string views to avoid memory allocations.
>>
>>103574407
How is that possible if you already solved the day with the multiplying stones. You DO understand the algorithms you are implementing right anon?
>>
>only need to check once per design index

It was really that easy.
>>
>>103575146
You don't need to solve a day to try another
>>
>>103575185
disgusting in every way, irredeemable
>>
>>103575210
In that case you can go back and solve the stones now.
>>
>>103575220
>t. used DP or caching as a crutch
>>
File: tinytim.jpg (281 KB, 953x1390)
281 KB
281 KB JPG
>>103575262
call me tiny tim bitch
>>
File: 1728072886088731.png (879 KB, 2000x2000)
879 KB
879 KB PNG
>>103571781
It took me a few tries to get a formulation that solves it in a reasonable time, but it's definitely doable with FOSS solvers.
Pic related solves both parts in about 10 minutes on my shit computer. The main issue seems to be that the search space is very symmetric (lots of valves have zero flow rate, for example), and the only "manual" optimization I did is to not even try opening those. I assume Gurobi / CPLEX would do much more automatically.
>>
File: code.png (244 KB, 1282x1988)
244 KB
244 KB PNG
Python

There is no need for cache.
>>
Can someone explain the actual solution for part 2? I'm just trying to find unique tokens so I can get the factorial. So far I'm pretty sure its lower than 25! so I'm thinking its probably something like 10!-15! but I don't get the actual solve.
for a in designs:
for b in designs:
if a + b in alldesigns:
if a + b in designs:
alldesigns.remove(a + b)
for c in designs:
if a + b + c in alldesigns:
alldesigns.remove(a + b + c)
for d in designs:
if a + b + c + d in alldesigns:
alldesigns.remove(a + b + c + d)
for e in designs:
if a + b + c + d + e in alldesigns:
alldesigns.remove(a + b + c + d + e)
>>
>>103574953
I got ~25ms with a queue, no new strings. Guessing it's the graph approach that makes the difference.
>>
>>103575317
Is this bait
>>
File: 1577742904314.jpg (149 KB, 1348x1470)
149 KB
149 KB JPG
>>103575317
chinese remainder theorem
>>
>>103575344
Obviously
>>
>>103575344
>>103575373
holy shit I totally missread the problem my bad
>>
File: hm.jpg (192 KB, 1330x1056)
192 KB
192 KB JPG
>>103575317
>>
Remember anon, 90% of brooters kill the process and start trying to do something "intelligent" just moments before the broot probably would have finished...
>>
File: 1713024016199382.jpg (73 KB, 680x588)
73 KB
73 KB JPG
>>103575560
>>
Recursive solution in Swift.
>>
>>103575587
cool go run it on an ipad dumbass fapple manboi
>>
File: carbon.png (170 KB, 1268x954)
170 KB
170 KB PNG
>>103574953
This pretty basic hashmap-backed memoization takes ~14ms, I think I got it down to around 6ms by using a vector instead of hashmap before I wrote the trie. Also, it checks if the current substring is in towels instead of .startswith().
>>103575320
I tried an existing trie but it was even slower than picrel, because it was allocating all found prefixes. So I think it's also important to keep the trie lean. Returning an iterator instead of a vector and using fairly small array without too weird of an indexing both helped a lot.
>>
>>103575185
realised how much I was overcomplicating it
>>
File: tim.png (78 KB, 234x296)
78 KB
78 KB PNG
>>103575777
that's better
>t. tiny tim
>>
File: unnamed.jpg (49 KB, 512x341)
49 KB
49 KB JPG
wtf I'm still not filtered and its day 19. this is actually the furthest I've made it. I can't tell if I got smarter or this year is just way easier.
>>
>>103575863
this year is easier imo
>>
>this year is easier
you've been saying this every year, for years
>>
>>103574248
>spent an hour looking for a bug
>one variable was an int instead of long long
i hate myself so much it's unreal
>>
>>103575929
I think it is true, but also a function of returning anons getting better at solving them so they feel easier even though they may have struggled with these same puzzles in the past.
>>
>>103575941
I was filtered by the amphipod tunnels in 2021. I could probably complete it now easily.
>>
>same puzzle as last year
>in the same hotsprings
Eric doesn't even care anymore.
>>
File: maxresdefault.jpg (81 KB, 1280x720)
81 KB
81 KB JPG
Is there a word for the thought process where you solve every problem by adding more complexity, end up with something retardedly overcomplicated, and only when you step back (i.e. after posting) do you realise how dumb it is?
>>
>>103575982
tunnel vision, decision fixation, etc.
having high energy without perspective is like missing your turn while flooring it in a race car. Congrats, you've got a really good engine, but you're wasting it and you'll be late.
>>103575935
hate yourself enough to use Zig? It's super anal about integer types and casting, and you would've gotten a runtime error from the overflow.
>>
>>103575982
It's called not cheating. Ever notice that the diversity of solutions significantly decreases as the day goes on. That's because people are cheating and filtered.
>>
I may be filtered but I'll keep going and learn from other's solutions. I will save christmas.
>>
This year feels like when the main character in Idiocracy was taking the IQ test.
>>
>no tree problems
>No cellular automata
>no wall of text follow 100000 different rules problems
>Just grid problem, grid problem, leetcode problem, recycled problem
Eric has given up
>>
>>103576225
This is what day 18 was like. It set up an interesting premise and then hit you with
>how many buckets do you have?
>>
>>103576233
There’s still 6 days left. He’s saving the best for last… right?
>>
>>103576261
he's saving the last for the last
these feel like the rejected problems from previous years
>>
>>103576308
kek he's dumping all the trash upon us in the last year
>>
>>103575317
You need more loops.
>>
>>103575317
depth-first search with memoization. That's it.
Write a recursive function over a string. If the string's empty, return true. If the string's not empty, find all valid prefixes and recurse on the string absent that prefix, and return the sum of the true values returned from that recursion. If there are no valid prefixes on a non-empty string, return false.
This will solve your example but be as slow as obsidian on your input. Slap a cache on the recursive function and it'll be fast.
>>
File: 19.png (109 KB, 687x943)
109 KB
109 KB PNG
Babby's first dynamic programming problem. Hoping for something crazy this weekend. Slightly washed C++, mostly squished to fit onto my screen for a picture.
>>
File: 1570617259427.jpg (5 KB, 164x202)
5 KB
5 KB JPG
>part 2 works for example, not for input
>spend two (2) hours trying to find a corner case bug in the code
>the problem was using int instead of long
FUCK
>>
>>103576261
i hope an even harder version of the elf vs goblin puzzle
>>
File: file.png (2 KB, 128x48)
2 KB
2 KB PNG
>read part 2
>get PTSD from last year (filtered by memoization)
>go to sleep
>wake up, make coffee
>solve problem
FUCK YOU ERIC SUCK MY DICK BITCH
>>
>>103576640
i'm doing that on and off and i'm guessing p2 is "figure out the minimum total health the elves need to win" or something, how close am I?
>>
>>103576233
Cellular automata is tonight's problem.
>>
>>103576100
>That's because people are cheating and filtered.
Or it's because the only people left actually know all the relevant data structures and algorithms.
>>
>>103576640
Part 1: Elves vs goblins but you have to find the shortest path the reindeer can take to collect all the christmas orbs on your map before the goblins kill all the elves. Goblins and elves run away from the reindeer when he's within 3 tiles (manhattan distance). Each christmas orb on the map is a digit 1-9 that heals all remaining elves for that amount. Goblins, elves, and the reindeer cannot occupy the same tile.

Part 2: what is the maximum number of turns at least 1 elf can survive for without collecting any orbs? Turns out evil santa corrupted the orbs so they cause a 1 health/turn loss of all units within 5 tiles (manhattan distance). (Input designed so you have to use the fleeing mechanic, but also so that the simulation eventually ends by causing the last elf to flee into another goblin or degen zone)
>>
Just redid 2023 d12 and was surprised by how hard it was. Much harder than today's problem.
>>
>>103574784
actually the minimal representation of the state is a single integer
you failed to make this observation, so you're actually filtered; better luck next year
>>
>>103575726
Adding a custom substring implementation (to avoid allocations) with custom hash function brought the time down from ~32ms to ~22ms. Your trie still wins. Or maybe C++ unordered_map just sucks.
>>
>>103575777
>(&design[dx..]).starts_with(&towel)
you don't need the manual borrow
>>
>>103576233
Could you create 500 interesting problems over 10 years?
>>
>>103577000
Eric never had to. That he won't accept puzzle suggestions was always pointless and self-inflicted. Even if his mods are much more nuts about it, the IP fixation comes from Eric hiimself.
>>
Wasted a few minutes trying to debug the answer because it looked way too big.
>>
>>103576967
You're right. Leftover from before I realised starts_with was a thing.
>>
File: 1708032521139740.png (583 KB, 2100x1158)
583 KB
583 KB PNG
>>103577021
imagine a world where people can upload input.txt to github and submit puzzle ideas
>>
>>103577021
whatever man if you made something really cool you probably wouldn't want a bunch of jeets and chinese stealing it either.
you wouldn't want a bunch of trannies creating committees to discuss the upcoming years' problems, and how to make AOC more inclusive, or whatever they do when trying to ruin everyone else's fun.
>>
>>103577031
after solving part 1 (with an answer around 200), I quickly wrote something for part 2 and tried on my input without testing against the example, and I got something around 2500
it was wrong of course, but when I went back and made sure I had code that worked against the example, and THEN ran my input, I got a huge number (around 10^14) and thought, well, guess I'll try it and see if it works
was quite surprised when it did. my first attempt definitely was not thorough apparenlty
>>
>>103575726
I used such a hashmap memoization. That vector memo approach is genius. How did you come up with that? Does that approach have a name?
>>
>>103576665
WTF anon, is just a hash map.
>>
C++ 23 + good old macros.
#include "aoc.h"
static V<Sv> patterns;
static M<Sv, N> sols;
static N count(const Sv d) {
def it = sols.find(d);
if (it != sols.ω) return it->second;
N n = 0;
for (def p : patterns)
d.starts_with(p) && (n += p.ϟ == d.ϟ ? 1 : count({d.α + p.ϟ, d.ω}));
return sols[d] = n;
}
int main(int argc, const char** argv) {
MmFile in(argc >= 2 ? argv[1] : 0);
def input = in | "\n\n";
patterns = input.h / ", ";
N silver = 0, gold = 0;
for (def d : input.t / '\n') silver += count(d) != 0, gold += count(d);
$o silver, gold;
}
>>
>>103577226
nta but hashmap memo stuff is bananas. ive only ever seen / used it with aoc stuff. its actually so much more understandable than tabular dp for me. but I don't even know how the space complexity compares for junk like this
data = list(map(int, data.strip().split(" ")))
tab = defaultdict(int)
for stone in data:
tab[stone] = 1
for i in range(75):
step = defaultdict(int)
for stone, count in tab.items():
if stone == 0:
step[1] += count
elif len(str(stone)) % 2 == 0:
power = pow(10, (1 + math.log10(stone)) // 2)
step[int(stone // power)] += count
step[int(stone % power)] += count
else:
step[stone * 2024] += count
tab = step
if (i + 1) % 25 == 0:
print(sum(tab.values()), end=" ")
>>
>>103577346


anon that isn't APL
>>
>>103577021
>reddit mods
>power over the most meaningless shit going to their heads
tale as old as time
>>
>>103577457
Why waste time typing five characters when I can AltGr + w to get ω?
>>
>>103577292
I know that now. But when I didn't know that I had ten pages of notes and my desk looked like a schizophrenic basement
>>
can I stay awake for another 8 and a half hours?
>>
seeing this mathlet always makes me laugh. go back to grade school dummy
>>
File: file.png (12 KB, 680x46)
12 KB
12 KB PNG
mathlets_btfochads we are so back
>>
>>103576597
i don't remember making this post
spooky
>>
File: boblins.webm (1.24 MB, 396x582)
1.24 MB
1.24 MB WEBM
did someone say goblins and elves?
>>
>>103577511
>>103577639
>mathlets_btfo
>mathlet has a higher score
lol, lmao
>>
>>103577971
>Day 26: Goblin Gangbang
>>
>>103575146
I don't see the connection between these days.
>>
>>103578011
An exponential process you can turn into a linear process via counting
>>
>>103577973
You will never be a real programmer. You have no commits, you have no pull requests, you have no public repos. You are a low IQ brown man twisted by an unearned comp sci degree and coding bootcamps into a crude mockery of nature's autism.

All the “validation” you get is two-faced and from bots. Behind your back people say you're a useless DEI hire. Your parents are disgusted and ashamed of you, your “tech bros” laugh at you behind closed doors.

Real programmers are utterly repulsed by you. Thousands of forum posts have allowed programmers to sniff out frauds with incredible efficiency. Even devs who “pass” have no creative output and excessively verbose with AI generated tech buzzwords. Your GitHub profile is a dead giveaway, and even if you manage to score a 3 month internship at some tech company, they'll lay you off the second they find out that you haven't completed any non school related projects.

You will never be happy. You cope by saying that your bullshit software is using a "proprietary test framework" so you can't open source it, but deep down you know it's because you don't want people to see your incompetence where all you did was push README updates over and over, and that the core codebase was stolen off an open source GPL licensed project which you're shamelessly profiting off.

Eventually it will be too much to bear. You'll buy a google gift card, a spoofed business phone number, and start cold calling old people into redeeming your scam.

This is your fate. This is what you chose. There is no turning back.
>>
Guys, I left my 12 thread bruteforce of part 2 going overnight but it isn't finished.
>>
>>103577226
Well, you can substitute vector for a hashmap if you know the data stored is at least somewhat contiguous, like indices of a string. I think it's not that great if you need to cache values by multiple things at once or if your stuff is spaced apart.
If you mean the trie version, I think that'd be tabulation instead of memoization, since it's building upon earlier calls and not caching later ones. I just left the name there and changed the type definition.
>>103576960
A trie in cpp might be even faster if you swap that indirect node indexing for pointers. Or maybe the compiler sees that's basically a pointer and skips that entirely, I don't know.
I think it'd still be good to keep nodes in a vector, just to keep them close together in memory.
>>
File: pretentious.png (193 KB, 832x983)
193 KB
193 KB PNG
>>103574304
space-optimised bottom-up tabular push dynamic programming solution: buzzword edition
>>
>>103578155
you need more threads
>>
>>103578155
Quick! Lend anon your CPUs! He needs our power!
>>
>>103578155
anon give me some of your input, i'll give you some answers
>>
I give up, Im filtered
Especially annoying since I saw videos on YT explaining it that are around 6 mins long
>>
>>103578286
>youtube videos
learn from the best: >>103574304, >>103578202
>>
>>103577973
he got filtered by modulo math
>>
Turns out cellular automata are awkward as fuck to program. What if one tile deletes adjacent tiles, but another tile moves? When the tile gets deleted depends on which cell is updated first.
>>
rustbros do we have a #[cache] macro?
>>
>>103578298
so use two grids and swap the references on each iteration?
>>
I'm back home, slightly tipsy.
Time to use the ballmer curve or get filtered.
>>
>>103578155
If every thread can find one valid combination every millisecond, you needed to start brooting when Jesus Christ was born.
Very topical.
>>
>>103576960
>custom substring implementation
what's wrong with std::string_view?
>>
>>103578298
store the next step in a new grid, alternate grids
if you want to be fancy, you can even use sets instead of arrays for easy infinite grids
>>
File: day19.png (207 KB, 749x2217)
207 KB
207 KB PNG
trie-solution. couldn't get it to run faster than that other rust solution from last thread.
about 0.5 ms.
tried to avoid any heap allocations, even though most of it made no difference performance wise.
>>
>>103576915
"Natural" is not the same as "minimal."
And you curiously failed to address my objective reason to use strings as keys (easily reusing progress for multiple designs). How peculiar.

At least the idiomatic Rust guy seems to be at least competent, you are both confident and retarded.
>>
>>103576960
std::unordered_map sucks a lot because the standard imposes requirements that force it to be implemented using a chaining hash table, try using a drop in replacement like robin_hood::unordered_flat_map
>>
>>103578286
Say for some index X of a design, you know there are exactly 7 combos of towel pattern that reach it (i.e. there are 7 sequences of towels that cover from char 0 to char X-1 inclusive, so X is the next tile).

For every towel, check if it matches the substring starting at X. E.g. for a towel of length 3, you'd check if towel[0] == design[X] and towel[1] == design[X + 1] and towel[2] == design[X + 2] (hopefully your language has a builtin feature like comparing string slices).

If it does, you've found 7 patterns that reach index X+3 (any of the 7 patterns that reach X, plus the 3-length towel).

Of course there could be other patterns that reach X+3. But if you'd exhaustively checked every towel with every priori index, you could be sure you've found all the patterns. And there's one index you definitely know - 0 has exactly 1 path, so to speak.

So you create a vector of 0s that's the length of the design +1, and set vector[0] to 1, and then for every index from 0 onwards you see if every towel matches, and if it does you add vector[current_index] to vector[current_index + length_of_towel]. With each step you guarantee a correct total for 1 more index and when you've done the final index (i.e. design.len(), the hypothetical index 1 past the end of design that you'd reach when you place the final towel that covers the last chars of design) you have the number of patterns.

For part 2, add all these final values, and for part 1, add 1 for every value that's not zero.
>>
>>103578293
damn, clever
I was aiming for similar stuff but I overengineered it and couldn't debug it
>>
>>103578439
the minimal state is the canonical state; i don't care what is considered 'natural' in your twisted mind
my solution was slow because i omitted logic for early exits for the sake of terseness:
        if not dp[i]: # nothing to push
if not any(dp): # no solution
break
continue

you can see my space-optimised solution here: >>103578202
though i expect it to run slightly slower due to extra modular arithmetic
now fuck off
>>
>>103578449
now I get it
I made a big mistake of stopping taking index of a string into account, which screwed the results.
Lesson learned I guess
>>
>>103578513
dp problems tend to be fairly simple
your state variables should be the minimal representation of the problem at each step; the value you're optimising is *not* a state variable
if you have e.g. 3 state variables, then your table should have 3 dimensions
the recurrence relations can be derived through thinking "which states can reach me" (pull dp), or "which states can i reach" (push dp)
you can often space-optimise by overwriting unreachable states - typically equivalent in effect to dropping 1 dimension - but in this case you do need a history of length `k`
>>
>>103578523
Well, I tried both the "improved" monstrosity and even the original with a similar early exit, and guess what: it makes no fucking difference and is still slow as shit.
When will you just admit to being retarded?
>>
>>103578580
>>103578202 is O(n**2) for any sensible defiition of n i.e. the input size. if say half of the input are designs you iterate over n/2 in the outer loop then you check against every position in every pattern in the worst case. (you do a compare of len(pattern))
>>
>>103578601
performance: >>103574304
Days              : 0
Hours : 0
Minutes : 0
Seconds : 2
Milliseconds : 260
Ticks : 22603467
TotalDays : 2.61614201388889E-05
TotalHours : 0.000627874083333333
TotalMinutes : 0.037672445
TotalSeconds : 2.2603467
TotalMilliseconds : 2260.3467

performance: >>103578202
> Measure-Command { cat .\input.txt | python .\aoc.py | Out-Default }
242 595975512785325


Days : 0
Hours : 0
Minutes : 0
Seconds : 1
Milliseconds : 281
Ticks : 12810889
TotalDays : 1.48274178240741E-05
TotalHours : 0.000355858027777778
TotalMinutes : 0.0213514816666667
TotalSeconds : 1.2810889
TotalMilliseconds : 1281.0889

stop lying on the internet
>>
>>103578580
yea I clearly have a problem with implementing DP
Last year I was filtered by day 12 as well
>>
>>103578628
>O(n**2)
false, which is why i ignored the number of designs and talked about the complexity of solving a single design
the length of each design isn't related at all to the number of designs, or to the length of any other designs;
you cannot call both the number of designs and the length of each design `n`
>>
Now I see why Conway's is so simple. Oh, you want 1 cell to push another? Gotta check a 5x5 window every time to avoid double writing.
>>
>>103578630
Oh damn you're right, it actually does make a 20% difference.
$ time python fag.py < input
315 625108891232249

real 0m2,662s
user 0m2,649s
sys 0m0,008s

vs
$ time python got.py < input
315 625108891232249

real 0m2,217s
user 0m2,184s
sys 0m0,014s
.

Now my very low-effort solution (>>103571076 for reference) runs only about 2.5x faster on my machine, how will I recover.
>>
File: day-12.png (1.46 MB, 2952x8217)
1.46 MB
1.46 MB PNG
>>103578655
i was also the tabular anon from day 12 last year :)
>>
>>103578345
>what's wrong with std::string_view
Mostly that I didn't know it existed. I'm doing this year's aoc in C++ to learn the language, and STL is confusing as hell.
>>
>>103578655
day 12 last year was my first dp problem and I hacked at it for well over a day before it clicked, this year when people mentioned the stones being similar to lantern fish I looked that up and did it first, it was easier to reason about but the same logic applied to the stones
>>
>>103578690
good for you i guess?
i consider my approach canonical, and the principle of using minimal states simplifies harder problems: >>103578692
i think your machine has overhead somewhere, as the difference is >20% on my machine
>>
>>103578665
no, but the sum of the lengths is what you need to consider... I am 90% sure you are larping but still, today was another boring day. Why is there no bigboy?
>>
>>103578724
I only linked that other post to show that the bottleneck is not "early exits."
Your solutions are neither readable nor particularly efficient (even by Python's very low standards).
I wouldn't even respond if you just posted pictures without pretending to know what you are talking about.
>>
File: 1733887359530571.png (629 KB, 822x744)
629 KB
629 KB PNG
wheeeee

/,/ { split($0,q,", "); l=NF; next }

$0 {
print NR
s[++p] = $0
while(p>0) {
n = s[p--]
if(n ~ /^0+ /) { p2++; if(!flag) p1++ }
for(i=1;i<=l;i++) {
if(n ~ " " i "[ $]") continue
if(n !~ q[i]) { n = n " " i; continue }
n2 = n
gsub(q[i],"0",n2)
s[++p] = n2 " " i
}
}
}

END { print "Part 1: " p1 "\nPart 2: " p2 }
>>
>>103578665
>>103578764
in case you are not just run your solution on a list of a 500 times a 1000 'w' s as designs and 500 times 500 'w's as your patterns.
then scale all numbers by 2 and see what happens
>>
>>103578801
shit, that's not my final version; that "print NR" should be resetting the flag to 0 and the flag should be set to 1 after we increment p1.

oops! still not filtered
>>
>>103578174
>I think that'd be tabulation instead of memoization, since it's building upon earlier calls and not caching later ones.
Yes, I meant the vector named "memo" in the trie version ( >>103574847 ). Looks like a really fast solution and very predictable. For me it is much harder to see how well the caching approach is going to behave memory and speed wise.
>>
>>103574538
looking through the replies i guess i hit a nerve by indirectly calling you a "@cachefag"
sorry for being rude on 4chan but you need to get a fucking grip
>>
>>103574538
Yes, I am.
>>
[Big brain idea] Pauli is operating his reindeer-powered exclusion machine; if any two cells move to the same location on the same turn, both are annihilated, leaving an empty cell. This makes the puzzle more fun and definitely isn't because I'm filtering myself coding it.
>>
File: 1722588356504220.png (524 KB, 720x761)
524 KB
524 KB PNG
>>103578864
Anime website, election toddler (and windows fag lol).
>>
>>103578296
I was filtered by time.
>>
>>103578883
There are anons on here who get upset if you use basic terms from Algorithms 101, like Dijkstra. It's amazing the strange hang-ups people develop. A bitter resentment towards their betters if you ask me!
>>
>>103578964
yeah that's what happens when you broot
>>
>>103579041
Mathematica isn't really the language for bruting.
>>
>>103578927
technology board; at least post lain or something
>windows fag
i deny these allegations, my laptop and server run linux - this is just my vidya machine
>>
File: quadratic.png (19 KB, 640x480)
19 KB
19 KB PNG
>>103578864
so that comes out to about exactly n**2, when scaling the problem "most reasonably". i.e. by keeping the sizes of the patterns and designs limited but increasing their number. (or almost any other way as well)
    patterns = ["w" * 10 for _ in range(M)]
designs = ["w" * 100 for _ in range(M)]

input_size = sum(map(len, patterns)) + sum(map(len, designs))

gives almost perfect quadratic scaling of time/input_size on your solution.
>>
File: 1602213874914.png (727 B, 32x16)
727 B
727 B PNG
/g/ saves Christmas 2025

Next year, I will create an alternative advent calendar for /g/. Please contribute your puzzles.
https://forms.gle/7f8849M1LLF8ZeAF6
01.12.2025 is almost a year away, so if you don’t have any ideas or time to implement them right now but would like to contribute later, just save this link and contribute when you're ready. (I probably won’t post it after the end of the current Advent of Code, as it would be weird to create a dedicated thread.)
Submissions are editable, so you can submit unfinished puzzles and complete them later.
>>
Unfiltered, unbothered.
I wish we had 2023 again. As much as I hated some of the puzzles, they were absolute kino compared to most of the problems this year.
>>
>>103579041
I sense deep and bitter mathlet resentment from you. Bad experience in grade school?
>>
>>103579107
2023 was bullshit-hard, not fun-hard.

2022 was the last great year. I still have my cube and 3D-printed magma boulder.
>>
Did any of you implement or use Aho-Corasick for yesterday's?
>>
>>103579127
>Bullshit hard
That's what made it kino.
2023-21 was beautiful. Sadly Eric fucked up.
>>
>>103579129
Does it work for 0-length patterns?
>>
>>103579103
it's insane to refer to both the patterns and designs as `n`, and it only comes n**2 because you scaled both in tandem
O(n*m) final offer, where `n` corresponds to patterns and `m` corresponds to designs, or vice versa
>>
>>103579106
i'm working with another anon on releasing a puzzle on the 26th and hopefully more next Christmas, if you're interested
irc.oftc.net #hoc
>>
>>103579165
I missed a few days, are you guys still ripping on the guy from the disk fragmentation problem? If so keep it up.
>>
File: 1723018180739193.jpg (102 KB, 640x920)
102 KB
102 KB JPG
>>103579095
I recognize now that I was indeed seething at one point and I still believe you to be incorrect, but I think that we can put things behind us.
I'll even post a Nanami just for you.
>>
>>103579183
I have "concepts of a plan" for a way to do puzzles on the board, if I have time later I'll post it.
>>
File: lain.jpg (34 KB, 338x303)
34 KB
34 KB JPG
>>103579188
>>
>>103579198
we were planning on setting up a Tor site and generating inputs (and bigboys) for individual users
>>
>>103579208
Why tor?
>>
>>103578991
i can't remember a single aoc grid that required dijkstra's, i always use bfs
>>
File: tgf.png (924 KB, 2039x2117)
924 KB
924 KB PNG
>>
>>103579223
we want an edgy story about steinwitz collecting stars of david to save hanukkah
we also want to get away with it
>>
>>103579183
I will check it out. Gonna go back to grinding the leetcode daily problem again after Christmas anyway. I just like puzzles mayne.
>>
>>103579239
do something with more soul... anything but leetcode
https://cses.fi/problemset/
>>
>>103579208
How are you going to handle users? it seems like the most difficult part to figure out.
>>
>>103579188
I miss Nanami.
>>
>>103579255
we could either use oauth or give people individual username:password combos, or both
e.g. if you ask on irc, we can pm you a login without botnet services
>>
>>103579288
I know nothing about any of that stuff. Maybe you could just do a 4chan tripcode system where you just have a password that is hashed and logs you in. Idk.
>>
>>103579295
could do, but you still have the problem of people spamming the leaderboard with their 50 alt trips
oauth and username:password on request makes that less of an issue
>>
>>103579288
Why not just email+password?
>>
>>103579321
Then your beeper goes off.
>>
>>103579327
What
>>
>>103579321
would need email verification and would only support botnet providers like gmail or proton
i don't think people want to give their real email to some /g/ user over Tor anyway, it's invasive
>>
>>103579343
Ok, fuck tor, I don't want an advent of pol anyway. It will be clearnet next year with email/password. >>103579106
>>
>>103579106
>>103579183
>/g/ aoc clone
Gets brought up basically every year, has never gone anywhere.
If you're going to go through with it, having it competing with AoC is not the way to go. At least do it in a different time span.
>>
real "We should start a band!!!" energy
>>
I'm here for AoC and will only be participating in that.
>>
>>103579374
>competing with AoC
should be okay to run in parallel with the early problems
they only take a few minutes so people have time for ours too

>>103579367
okay :(
>>
Just post a puzzle here every week over the summer or something
No need for a site
>>
>>103579390
AoC might be over after this year
>>
>>103579374
We'll see in a year. Maybe I will move it later, but I want christmas thematic. AoC has a lot of days when it feels not enough. Probably different time of a day and less leaderboard faggotry (e.g. filtered/not-filtered only) to avoid people worrying about their time.
>>103579381
Yeah, but you can't start a band without it.
>>103579403
It kills the idea of a second part.
>>
bigboy/mediumboy for today. you can thank >>103578864
https://files.catbox.moe/1sgxqb.txt
day19 result:("4979", "1479223848389312371")
>>
>>103579436
we could probably drop the edgy story if you want to just concentrate efforts
we have a few ideas for making LLM-resistant problems >>103579183

if you're willing to host on clearnet then i would contribute some puzzles
>>
>>103579396
>should be okay to run in parallel
So are you going to piggyback off of /aocg/ (filling them with stuff unrelated to AoC), or are you going to fragment things and start up a second christmas general? This is more what I mean as a problem.
If it's more original/not overlapping, it's probably fine. If it's shoehorned to fit in, not so much. It's hard enough to convince anons to participate in AoC, trying to make a second unrelated service integral to /aocg/ is just asking for trouble.
>>
>>103577163
it's not about the reasonable of the worry, but about the reasonableness of the degree of fear shown about it. If Eric had his entire site, backend, puzzle ideas, 30 years of elf fan fiction, and ASCII art library on a prominent git repository, then AoC would've been instantly cloned. If he hadn't had some branding sense and had hosted it on neocities, then the clone would also have a better domain name.
But inputs and story ideas are not a threat at all without him going public, making millions, and getting stockholders who can turn around and lawfare him to seize his incredibly valuable and irreplaceable assets.
>>
File: 1701973326591240.png (57 KB, 1917x1152)
57 KB
57 KB PNG
>>103579479
>edgy story
I am in this to fuck anxious elves with some Christmas chub, anon.
>>
>>103579487
literally everything discussed so far is negotiable, but i'd imagine a separate series of threads hopefully linked in the aocg OPs
>>
>>103579479
You'll definitely get more interest without the edgy story. As much as Shlomo's adventures in coin clipping would be amusing, not everyone has a dark sense of humor.
>>
>>103579520
i discussed this at the start of the month and there was a lot more interest for wogbergs adventures, but i guess most of those people are filtered by now
the only thing i actually care about is that the problems are LLM-resistant
>>
Here's how you can do two parts, but without any site infrastructure.

Part 1 is just what you see on the image, it'll be something reasonably simple, the way Eric does it. The harder Part 2 is another image contained within the bits of the first image (Steganography), which will be XOR'd with some number that is a function of the Part 1 solution. Part 2 can be verified as correct by hiding a success message, once again in the first at a given offset, and also XOR'd with the Part2 answer.

With this, there's no need for any infrastructure, just an anon who is willing to create a problem. The machinery involved in generating the puzzles can be automated away. These puzzles may optionally be licenced AGPL+Nigger to prevent it ending up on social media, and since tampering with the image destroys the puzzle, the notice cannot be cropped out.
>>
>>103579605
good idea but the jannies will literally ban the poster for steganography
>>
File: 1725974643409547.jpg (1018 B, 130x97)
1018 B
1018 B JPG
fuck this shit, i got filtered on day 12, today i decided to come back to it because i just couldn't understand why the solution didn't work, and it turns out that the logic was correct but somehow rust's group by was yielding nondeterministic results, i then decided to reimplement the group by myself and it worked just fine fuckkkkkkkkkkkkkkkk

this is the solution that doesn't work
fn sides_of_dir(border: &HashSet<((isize, isize), Dir)>, dir: Dir) -> usize {
border
.iter()
.filter(|(_, d)| *d == dir)
.map(|(p, _)| p)
.group_by(|p| match dir {
Dir::U | Dir::D => p.1,
Dir::L | Dir::R => p.0,
})
.into_iter()
.map(|(_, sides)| {
sides
.into_iter()
.map(|p| match dir {
Dir::U | Dir::D => p.0,
Dir::L | Dir::R => p.1,
})
.sorted()
.collect_vec()
.windows(2)
.filter(|w| w[1].abs_diff(w[0]) != 1)
.count()
+ 1
})
.sum()
}


this works
fn sides_of_dir(border: &HashSet<((isize, isize), Dir)>, dir: Dir) -> usize {
let mut by_axis: HashMap<isize, Vec<isize>> = HashMap::new();
for (x, y) in border.iter().filter(|(_, d)| *d == dir).map(|(pos, _)| pos) {
match dir {
Dir::U | Dir::D => by_axis.entry(*y).or_default().push(*x),
Dir::L | Dir::R => by_axis.entry(*x).or_default().push(*y),
}
}
by_axis
.values()
.map(|axis| {
axis.iter()
.sorted()
.collect_vec()
.windows(2)
.filter(|w| w[1].abs_diff(*w[0]) != 1)
.count()
+ 1
})
.sum()
}


rustfags owe me an explanation
>>
>>103579466
You sure? Because I get:
Silver: 5000
Gold: 1060948046952
>>
>>103579706
most stable rust behavior

>>103579631
I assume he means he'd host the images on a static site with clear instructions on how to extract the text and just link the site here.
>>
>>103579466
>>103579707
No wait, your format is wrong. In the input there is a space between the ',' and the next pattern. Change that and I get the right results. 4.3 seconds.
>>
>>103579719
if you have a static site anyway, just host normally
it would also let you take aoc market share if eric quits
>>
>>103579706
And what have we learnt about using Rust?
>>
>>103579706
you brought it on yourself by choosing the devil's language
>>
>>103579605
>>103579719
>>103579732
If you are using a static site just encrypt part 2 with your answer to part 1 and write some js that tries to unencrypt it with user's input, nobody has time to xor your images or whatever.
>>
>>103579631
>>103579719
I actually didn't know that was banned. Hosting elsewhere is another option I guess, but it would be cooler to just keep it all here. The sad irony is that hidden images could be posted without jannies being any wiser, and yet when we're honest about it, for an innocuous puzzle we run into trouble.
>>
>>103579762
>nobody has time to xor your images or whatever.
If you cannot XOR, you don't belong in the challenge, it's not for you and you should go back to jeet code.
>>
>>103579762
>nobody has time
Speak for yourself.
>>
>>103579785
could maybe ask for permission but it's a humiliation ritual and 40% chance they say no and 60% chance they don't reply
>>
Big brain solution: use the patterns to define and build a regex and then just check if each string matches the regex.
>>
>>103579856
That might work for part 1, but there may also be some limits to the amount of backtracking your regexp has. It may even be a compile time restriction.
>>
>>
Was shocked how easy today's was for day 19, like if you did a recursive solution for part 2 all you had to do was make it return numbers instead of bools and add a basic memo.
I went back and did day 19 for last year (which i skipped), pretty fun problem got to use a lot of lambdas for part 1 and part 2 was a very different problem where you instead had to view the input as a tree of sorts.
>>
>>103579963
No go back to 2015 day 19 if you want to experience real fun. If you got a lucky input, the problem is quite easy. Otherwise you’re in for a lot of pain.
>>
>>103579762
Something like this:
https://pastebin.com/Puzkva2d
>>
>>103580016
Is this bait? That's literally dp 101
>>
>>103580025
Nope. As I mentioned, it’s very dependent on the input you get. I know this because at the time I happened to get the easy input, and then was confused as to why reddit found it so hard.
>>
we still haven't had any gaussian elimination problems yet this year
we had like 5 parsing heavy versions of that in 2020
>>
>>103580045
I solved it with top-down dp and computer the upper bound of the state count to be around 30 million.
>>
>>103580059
Which is not a general solution.
>>
>>103579706
>the logic was correct but somehow rust's group by was yielding nondeterministic results
Because HashMap and HashSet aren't stable, they iterate in random order
>>
File: Advent1.png (359 KB, 1602x2154)
359 KB
359 KB PNG
>>103574248
Just finished day one, how does it look?
>>
>>103580079
Why do you think so?
>>
>>103580092
Good morning
>>
>>103580095
You received a lucky input, otherwise your reply wouldn’t have been “It’s just DP 101!”.
>>
>>103580090
pytoddlers btfo

>>103580092
enable preview and it can get even smaller
https://openjdk.org/jeps/477
>>
>>103580090
it shouldn't matter because i am only filtering and mapping and i called .sorted() before checking contiguity
>>
>>103580114
Give me a bad input then. It's pretty easy to see that dp works in all cases.
>>
File: evg.webm (501 KB, 884x652)
501 KB
501 KB WEBM
bros I think my elves have autism, they won't stop forming lines
>>
File: carbon(145).png (606 KB, 2936x4244)
606 KB
606 KB PNG
Assembly on a $5 1GHz RISC-V cpu versus Python on a $450 5800x3D
Python is about 6x slower
>>
>>103580166
i thought this was going to end up spelling the gamer word
>>
>>103580184
Don't spoil part 2
>>
>>103580166
What is this?
>>
>>103579877
Got something close enough to it. No backtracking needed but takes about 1s to check each case.
>>
File: aoc_2024_19.png (48 KB, 945x604)
48 KB
48 KB PNG
Perl.
You can actually force the regexp to brute the solution with something like
$design =~ /^(?:$pattern)+(??{$gold++ if $& eq $design; return "(*FAIL)"})/;
, but I did not bother seeing it to the end on the actual puzzle. Curiously, using
^(?:$pattern)+(?{...})$(*FAIL)
actually triggers an optimization, regexp engine will not attempt to match left side of the string again if it has exhausted all combinations for it. So for patterns "a", "b" and "ab", trying to match "abab" it will match "a""b""ab" and "a""b""a""b" and then give up after reaching "ab".
>>
>>103580248
:set shiftwidth=4
>>
File: xarbon.png (15 KB, 556x660)
15 KB
15 KB PNG
>>103580114
>>103580131
Here's my code, find the flaw then, oh ambassador of plebbit. Why do you even visit that shithole?
>>
>>103580262
Shan't, helps keeping track of how nested the things are and to avoid going too much into it in smaller files.
And all the rest is already at 8 and switching would be a pain.
>>
>>103579234
Nobody is going to shut down your website for having an edgy story. You can say nigger on twitter now.
>>
>>103580248
>(??{ ... })
>(?{ ... })
These are so nice. Imagine if instead of the regex engine we had a general Prolog language with a good syntax for matching strings and arbitrary data structure (not the deprecated DCG shit) with the ability to put regular code inside (imperative, functional, and even control flow statements (next, last, goto) that could act on the outter quantifier as if it was a regular loop). It would be unparalleledly expressive.

I don't know for certain but I think it may have to do with the optimizations on the regexes's "main loop". The default main loop is try_match_at(0), try_match_at(1), ... try_match_at(length(string)), and the presence of anchors at the top level (not inside an alternation) is one of the situation where the main loop tries can be cut down so it does not try to match at every position.
>>
>>103579396
For early problems I'd rather spend hours optimizing for bigboys than doing an entirely different and inferior problem
Don't compete with AoC, the best time to run it would honestly be like July when people aren't burned out
>>
>>103580652
Hmm, I will think about it.
>>
>>103580092
Looks good. I'd just add
throws IOException
to main instead of catching it, and
String#split(CharSequence)
takes a regex so you can also use \\s+ instead of multiple spaces.
>>
>>103580279
m=defaultdict(lambda *x:[])
Is this AI slop? BTW how quickly does it compute an answer for you. I have an input that has been taking over a minute so far .
>>
>>103580759
>Is this AI slop
no, why would it be? I wrote that. I like to mark arguments that I don't use as optional and you can't write lambdas with zero args.
>taking over a minute so far
It's an extremely unoptimized version, it took me 4 hours lol.
I'll write one in C++ that uses segment trees, that should run in less than a minute.
>>
>>103579129
>Did any of you implement or use Aho-Corasick for yesterday's?
Hmm, I might do it just for fun and post a bigboy that can only be solved by it.
>>103579165
Unironically it works with zero-length strings if there are rules that prevent infinite usage.
>>
>>103578314
>be future anon
>anyone has access to a streetcorner time machine, just a quarter per use
>working on an advent of code 2099 puzzle
>brute force will take 2000 years
>only 2000 years? that's easy
>equip laptop with an infini-battery™ and spend a quarter on time travel
>lock it in a box and bury it outside where your house will be built
>go back to present
>dig up box
>brute finished a century ago, input answer
>That's right! You've earned another gold star!
>brutebros win again
>>
>>103580795
>you can't write lambdas with zero args.
>>> (lambda: print("hello"))()
hello

works on my machine
also you can just do defaultdict(list)
>>
>>103580836
kek good to know, thanks
then I remembered wrong, I'll fix that
>>
>>103580795
Well if you're the same anon, you were so damn arrogant about the problem. "Is this bait? It's just dp 101!" And yet... It doesn't seem to work.

I don't care for reddit either, but in 2015 that was the nexus around the puzzles. I went there to laugh at them feeling smug that my very naive solution "just worked" while they were pulling their hair out. Anons here were talking about that being a tough day and even as recent as a year ago there's still reddit discussions about it. Apparently the general solution is to create a parser for a context free grammar, with https://en.wikipedia.org/wiki/CYK_algorithm recommended. I want to explore this further.
>>
>>103580870
It does work, just needs some optimizations. I promise I'll post it in the following days.
And it IS dp 101, but of course if you brute compute the states then it's slow. You have to query the minimum sum quick.
>>
What's in store for us tonight, xisters?
>>
>>103579706
>group_by on a hashset.
Did you even bother to read the docs?
https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.iter

It literally says the order is arbitrary. You can't have a meaningful group_by using it.
>>
>>103580977
i know that iterating over hashsets is not deterministic, but why is it a problem? an element is not put into a group based on its position
>>
>>103580915
Djikstra (good things come in threes)
>>
>>103581067
https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.chunk_by

Consecutive elements with the same key.
Note the example where key = bool.
Collect into a sorted vec first.
>>
>>103581111 (checked)
Now cue the tard who will tell you that you’re trying to sound smart.
>>
File: 1711026230973115.gif (192 KB, 1580x968)
192 KB
192 KB GIF
>>103580915
>>
>>103581140
that would be awesome actually
first fun puzzle of the year
>>
>>103581115
Also note the name change. Probably because people got confused by the name group_by. Haskell's does the exact same shit btw. I don't know if the python itertools module partitions or not (doubt).
>>
>>103581140
DELETE THIS
>>
File: day19.png (70 KB, 1616x1220)
70 KB
70 KB PNG
not horrendously slow for mathematica
>>
>>103579706
Anon fell for https://github.com/rust-itertools/itertools/issues/374
>>
>>103581140
I wonder what a sentient being in the game of life looks like.
>>
>>103581171
Cool. Didn't think of using graphs.
>>
File: D19_aho_corasick.png (942 KB, 2400x3910)
942 KB
942 KB PNG
>>103579129
>>103580806
A little Aho-Corasick warmup before today's puzzle.
>>
>>103581067
why do you think your second works and the first one doesn't
>>
>>103581140
>Part 1
>The elves will move based on specific rules. How many elves after 1000 seconds?

>Part 2
>The elves are actually practicing a dance, but the ruleset was corrupted. What rules do the elves need to follow to eventually form a Christmas Tree?
>>
File: file.png (865 B, 23x42)
865 B
865 B PNG
why is it off center?
>>
>>103581182
Kek this basically confirms everything I've ever thought about rust.
>>
>>103581401
It works the exact same way in python
>>
>>103581401
>idk what an Iterator is
low IQ poster right here. The behavior of group_by makes perfect sense if you aren't retarded.
>>
>>103581348
>>What rules do the elves need to follow to eventually form a Christmas Tree?
>The Christmas tree pattern that Eric meant this time
0000000000000
0000001000000
0000000000000
0000010100000
0000000000000
0000101010000
0000000000000
0001010101000
0000000000000
0000001000000
>>
HALF AN HOUR
>>
where my brootbros at
>>
>>103581479
I'm ready to BROOOT today's puzzle
>>
File: 1733748369024790.jpg (274 KB, 1280x1500)
274 KB
274 KB JPG
>>103581479
>>
>starting from 2015
>got to 2016 day 11
this one is hard. I keep getting 9 steps for the example, I think I misunderstood the rules in some way.
>>
>>103581513
that's another puzzle that I take one look at and cringe because of how long it took me
I repressed the memory of how I solved it
>>
File: yukari-2316.jpg (55 KB, 569x800)
55 KB
55 KB JPG
any AOC++ leakers in chat?
>>
>>103581462
Entropy/compression would still work on that
>>
I think I will continue with one puzzle a night until I get all 500 stars, then again in a new language. Advent of Code is the gift that keeps on giving!
>>
>>103581522
I hope todays is as hard. Eric is boring me this year.
>>
>>103581309
How did it perform?
>>
>>103581527
pathfinding on a grid 3 and it's easier than both previous problems
>>
I told my friends I would stream my screen doing tonight’s puzzle so it is now guaranteed to be hard so I get filtered live.
>>
>>103581527
You're given a list of equations
1 + 2 = 3
10 + 4 = 14
15 + 6 = 99
2 * 5 = 10
And you have to count the number of equations that are wrong.
>>
>>103581527
Cellular automaton day
>>
Poop checked.
Ready to go.
>>
File: loli-sunglasses.png (813 KB, 899x899)
813 KB
813 KB PNG
>>103581527
game simulation today
>>
>>103581568
FUCK
>>
>>103581566
thanks for cosmically guaranteeing us a difficult day today anon
>>
two possibilities:
- Chinese Remainder Theorem day
- 3d Space (X, Y, Z) coordinates day
>>
im so sleepy guys...
>>
>>103581594
tree day
automata day
>>
>>103581568
too hard, eric would never go that far
>>
dijkstra today
>>
>>103581602
We’ve already had that day.
>>
>>103581552
DP silver: 78.168964ms
Aho-Corasick silver: 18.146983ms
DP gold: 29.145208ms
Aho-Corasick gold: 7.637811ms


The bigboy that will tell the real difference should include heavily overlapping patterns like
A, B, AB, AAB, AAAB,  AAAAB,  AAAAAB, AAAAAAB
>>
>>103581607
but what about second dijkstra?
>>
>eval(left)==eval(right)
Pssh, nothin personnel.
>>
File: file.png (48 KB, 1200x1200)
48 KB
48 KB PNG
Just under the wire. I thought I had a pretty good track record keeping these relatively non-lewd (except for day 5 which was low hanging fruit) but I couldn't help myself on the literal onsen problem
>>
>>103581610
Nice. Pretty good decrease.
>>
>>103581614
rm -rf = 12

Pssh, nothin personnel.
>>
>>103581568
This except the input is formatted like
1 + 2 == 3
10 + 4 == 14
15 + 6 == 99
[1000 more lines]
sudo rm -rf --no-preserve-root /
[1000 more lines]
2 * 5 == 10
>>
>>103581610
I very much doubt Aho-Corasick is worth it at pattern length 8 and I'm sure that DP could be optimized to be much faster.
>>
>>103581623
I wish Eric had the balls to do something like this.
>>
>>103581617
BLESS YOU ANON
>>
>>103581597
I am too exhausted to solve anything right now. I plan to read the problem, then go to sleep and hope the solution comes to me in a dream.
>>
>>103581617
I love you
>>
>>103581617
needs more lewd
>>
>>103581624
I'd send Eric $5,000 on the spot if he actually did that and it caused a cacophony of seething reeeees from redditors.
>>
>>103581625
>I very much doubt Aho-Corasick is worth it at pattern length 8
No shit, the bigboy should have 1000 strings with lengths from 1 to 1000.
>>
>>103581625
>and I'm sure that DP could be optimized to be much faster.
No lol.
>>
>>103581648
No we don't and fuck you.
>>
>>103581623
>Remove-Item: A parameter cannot be found that matches parameter name 'rf'.
>>
>>103581617
I don’t have enough time to fap before the puzzle.
>>
>>103581663
Winbros cannot and will not stop winning.
>>
>>103581662
yes we do
>>
>>103581663
>PajeetShell
>>
>>103581665
>fap
>not goon
what is old head yapping about
>>
>>103581674
There are other boards for that you fucking monkey nigger.
>>
FIVE MINUTES
>>
>>103581661
Compress each pattern to 3 bits/letter and use a lookup table
Or construct a perfect hash function from all patterns and use a lookup table
>>
File: showtime.jpg (46 KB, 640x480)
46 KB
46 KB JPG
https://www.youtube.com/watch?v=hjGZLnja1o8
>>
>unironically need to shit
puzzles for this feel?
>>
>>103581689
kino music
>>
>>103581689
cancer music
>>
>>103581684
>a perfect hash function from all patterns
It's called Aho-Corasick.
>>
sleepy...
>>
File: 1709047066162837.jpg (130 KB, 440x518)
130 KB
130 KB JPG
>>
>>103580248
>>103580306
yuck
>>
File: showtime-frog.png (468 KB, 1858x1829)
468 KB
468 KB PNG
>>103581689
>>
SHOW TIME
>>
>>103581693
too slow chud
>>
>>103580306
I think :set tabstop=4 and :%retab! would fix it automatically if you wanted (which you don't, but just so you know)
>>
>>103581689
kino music
>>
>>103581479
still brooting yesterday's
>>
FILTER THIS TIME
>>
better not be another fucking grid
>>
>>103581719
Taskete Claude-sama
>>
WAIT FOR ME I'M TAKING A SHIT
>>
>>103581694
Aho-Corasick isn't calculated on 8 bytes at once.
>>
>>103581722
4D grid just for you.
>>
FUCK
>>
FUCK
>>
advent of grids
>>
dijkstra
>>
>maze
I'm killing myself.
>>
>>103581556
you're kidding me
>>
Give it up for Djikstra round 3!
>>
File: marisa-_-.png (66 KB, 403x250)
66 KB
66 KB PNG
>another fucking grid problem
>>
Eric has given up.
>>
I'm just brooting this, fuck it.
>>
worked on example, wonder how long real one will take
pretty big grid
>>
>>103581763
i have given up
if my broot doesnt work im not doing it
>>
part 2 broot running..... pray for me
>>
File: carbon-2.png (174 KB, 1558x1212)
174 KB
174 KB PNG
>he doesn't have a maze-solving helper in his AoC library
laughing_elves.jpg
>>
>>103581858
>process killed
fugg
>>
Thread theme
https://www.youtube.com/watch?v=YVlcADaT94o
>>
>works on part 1
>works on example
>fails on input
HOW
>>
File: Untitled.png (9 KB, 622x50)
9 KB
9 KB PNG
??????
the usual suspects didn't make it to the leaderboard except the Bikatr7 fag
still i'm not entirely convinced i'll see if he manages to clear a actual bloodbath in the next few days
>>
FUUUUCK I COULD HAVE DONE SO MUCH BETTER IF I STOPPED AND THINKED AND DIDNT PANIC. AAAAAAAAAAAAAAA

top 1k times though pretty happy.
>>
>>103581901
gpt o1 pro could probably solve everything if you're willing to spend 200$ a month on it
>>
>>103581921
Eric has given up btw.
>>
>>103581872
you're brooting wrong
>>
>only ones to get global leaderboard times
>dont do all the puzzles. only certain ones because.... I JUST DONT FEEL LIKE IT OK?
IM NOOOOOOOTICING
(And Higgston is legit obviously)
>>
>>103581901
Not enough, I'll believe it when he gets top 100 for something like day 12. Today was tough on llms but I wouldn't say its impossible with the proper guidance.
inb4 its all ezpz llm days after today
>>
>it's another maze
>>
>>103581981
this year just hasn't been that interesting. i haven't done a puzzle since day 10
>>
>>103581991
inb4 eric cocksuckers starts saying filtered
>>
>>103581991
>>103581994
filtered
>>
>>103581994
filtered
>>
>>103581981
>>103549605
he couldn't do 18 and 19 because his pc was busy brooting 17
>>
File: carbon.png (553 KB, 1846x3164)
553 KB
553 KB PNG
Slightly washed version. This wasn't crazy hard (especially for a day 20 problem) but it was at least a little fun.
Panicked mega hard at part 2 until I realized I could massively simplify things by just checking each pair of open tiles that are sufficiently close together. I wonder if there's a way of doing that that's better than just O(n^2), but there probably isn't as every single air tile seems to be part of the path
>>
So.... tomorrow will be the filter for sure this time right bros?
>>
>>103582017
wtf is that function signature man, just use strings lol
>>
>>103581983
bold of you to assume he wont disappear again tomorrow
>>
File: worry.png (193 KB, 472x313)
193 KB
193 KB PNG
>part 1
>ez pz
>part 2
>giving me incorrect results on the example and i don't know why
>>
>>103582029
It's my AOC repository and I can write whatever ridiculously complicated testing framework I want
>>
>>103581556
How did you know...
>>
>>103582031
mine is correct on the example but fails on the real one
>>
done
whatever
I iterate through every location on the grid, then check it against iterating through every location on the grid again to get manhatten distance and see if it's less than 21
it takes two minutes to run and I spent half an hour debugging because I forgot to add absolute values when checking manhatten
don't care
this problem felt like doing work
maybe the only time in aoc history I've felt genuinely bored doing a puzzle
>>
>>103582031
>>103582066
I know the edge case you are having :^).
>>
>up to 2 picoseconds (spaces)
>examples all phase through only one wall
>example output only expects one wall phased through
I should know by now not to trust Eric's writing
>fix code
>got the answer for a different input
fuck
>>
>>103582067
WTF was eric thinking putting 3 maze problems within 5 days.
>>
>>103582074
TELL ME
>>
>get distance from the start to every tile
>get distance from the end to every tile
>for every possible jump, the time if you cheat that way is dist (start->a) + dist (start->b)
somehow I still can't get anything that remotely makes sense for the example though. Is this approach fundamentally flawed, or am I just retarded
>>
>>103582091
the shortcuts you are taking are different lengths and you arent accounting for that.
>>
Don't spoil me, I just want to know if a cheat ends upon reaching a normal track again or is the following cheat possible for this example map:
###########
#...#...#E#
#.#.#.#.#.#
#.#.#.#.#.#
#.#.#.#.#.#
#.#.#.#.#.#
#S#...#...#
###########

###########
#...#...#E#
#.#.#.#.#^#
#>>>>>>>>^#
#^#.#.#.#.#
#^#.#.#.#.#
#S#...#...#
###########

In other words, can I have a cheat active across multiple walls, as long as it is at most 20 contiguous steps? (Am I reading that constraint correctly as well).
>>
      -------Part 1--------   -------Part 2--------
Day Time Rank Score Time Rank Score
20 00:10:10 138 0 01:07:06 1599 0

>try to solve with modified djikstra
>don't get anywhere
>try to broot it
>works
FUCK
Also lost a minute because I forgot to change the shortcut gains from 50 to 100 for the sample.
>>
>>103582081
If day 22 is another maze I'm going to lose it.
>>
>>103582092
I just had to add 2, lmao
>>
File: file.png (5 KB, 426x56)
5 KB
5 KB PNG
>>103582095
yesi am
>>
>>103581981
> (And Higgston is legit obviously)
I don't know if Mathematica and >import solution counts as "legit"...
>>
>>103582096
>can I have a cheat active across multiple walls, as long as it is at most 20 contiguous steps
yes
>>
File: UNWASHED ASS.png (286 KB, 824x2253)
286 KB
286 KB PNG
>>103582098
UNWASHED ASS
>>
>>103582101
my mistake. That was my problem.
>>
>>103581991
>day 11 stones
lol
>>
>>103582102
More legit than llms.
>>
>works on part 1 example
>solves part 1
>works on part 2 example
>doesnt solve part 2
i dont fucking get it its basically the same thing just increasing 2 to 20
>>
>>103582114
>I don't care about aoc thats why I haven't done some of the problems
>In the thread at midnight
hmmmmmm
>>
File: file.png (9 KB, 734x55)
9 KB
9 KB PNG
>>103582123
nevermind im fucking retarded and forgot to put the <= 20 in the code
what a shit puzzle
>>
>>103581981
>AOC is about not being filtered and not about enjoying the puzzles you find interesting because... IT JUST IS OK?
>>
I'm actually mad, I think I'm actually unironically mad at the quality of the puzzles this year
>>
>>103582138
Filtered
>>
>>103582139
Same. I almost hope it is the last year if it is going to continue like this.
>>
>code works on part 1
>code works on part 2
>code no longer works on the example
whoops :)
>>
>>103582139
Eric has given up
>>
is anyone else finding these correctly in p2 example:
There are 4 cheats that save 74 picoseconds.
There are 3 cheats that save 76 picoseconds
but messing up the other ones?
There are 12 cheats that save 70 picoseconds.
There are 22 cheats that save 72 picoseconds.

My prog only sees 12 saving 72, and only 10 saving 70.
>>
>>103582150
If you haven't already, mind the different distances in the example vs real input in part 2 (50 vs 100).
>>
File: carbon.png (405 KB, 1516x1818)
405 KB
405 KB PNG
      --------Part 1--------   --------Part 2--------
Day Time Rank Score Time Rank Score
20 01:07:00 3551 0 01:09:43 1672 0

At first I was just calculating the best paths assuming you can phase for 2 moves, but that kept giving me the wrong answer. For example, I'd never get that 20ps cheat from the example, because it's strictly worse than going down instead of right. Took me a while to get that he wants us all unique pairs of path tiles...
>>
>>103582138
>Puzzles you find interesting
Sorry but there was none this year Eric has given up
>>
>>103582127
yes
>>
>>103582160
Did you add your start and end points to the list of points to consider?
>>
>>103582161
I figured it out. I was counting paths that saved 0 seconds by not going through walls at all :^)
>>
>>103582180
Ah yeah, I just filtered those out with
if 0 < dist <= 20
.
>>
File: file.png (120 KB, 1079x487)
120 KB
120 KB PNG
>too high on real input
fuck
>>
>>103582180
Why would that change the answer.
>>
i dont know how to cache this
>>
>>103582187
You counted unique pairs, right?
>>
>>103582188
it didn't, it's just that for understanding the example, every single cheat saves less than 100us, so I was looking at every cheat :)
>>
There're no tricks with the input right? Even if it takes a while, the broot solution's not gonna take 10 years to complete?
>>
>>103582201
for part 1, that's correct
>>
>>103582201
there's a big clump of walls without any paths in my input, that's probably a part 2 brute filter depending how you implement it
>>
>>103582192
>day 19
>HAHAHA Imagine manually caching I just imported it from functools :^)))))
>day 20
>NOOOOO IM NOT FILTERED IM NOT FILTERED NOOOOOOOOOOOOOOOO
damn that sucks bro.
>>
File: file.png (278 KB, 1568x1646)
278 KB
278 KB PNG
importchad coming through
>>
>>103582192
The solution has nothing to do with DP.
>>
>>103582233
I need to at least put all of my grid functions in my own library.
>>
it seems like everyone is treating it like the shortcut has to start/end on part of the best non-cheating path, but thats not necessarily true right? eric inputs again?
e.g. this for part 1
#####
#...#
#S#.#
###.#
#.#.#
#E#.#
#.#.#
#####
>>
File: file.png (112 KB, 875x1269)
112 KB
112 KB PNG
>>103582198
It should.
There's probably an off-by-1 somewhere fucking me over, I kept twiddling with off-by-1s quasi-randomly until it seemed to work.
>>
>>103582245
meant this
#####
#...#
#S#.#
###.#
#.#.#
#E#.#
#.#.#
#...#
#####
>>
>>103582245
>there is only a single path from the start to the end
>>
>>103582245
>but thats not necessarily true right?
Nigga, just look at your input and see that S and E have only one free position nearby.
>>
>>103582245
Are people who are doing this getting the correct answer? That is my last straw with eric if true.
>>
>>103582257
there is still only one path here >>103582255
>>103582260
its a minimal example, use your head nigga
you could imagine there being a square that doesnt appear on the best path that you could potentially shortcut to to get a better path
>>
>>103582270
thats what i did and it does give the right answer
>>
>>103582285
thats fucking stupid. eric used to include edge cases in his puzzles. Discovering the obscure edge cases was the most fun part. FUCK YOU ERIC
>>
>>103581981
Santa needs your help! The oofmatoes we were growing on (day 12) is malfunctioning! Instead of solving puzzles every single day he appears to skip days randomly! To avoid disaster we must predict which day he will skip in advance. But fear not! the elves have collected some insight

when the puzzle day is 1 digit he has a 100% completion rate for example day
1,2,3,4,5,6,7,8,9 will net us 18 stars

from 2 digits onwards he will skip 2 days and solve puzzles for another 2 days except when the current day is a factor of 75 like 15
this rule is overwritten if the previous day is a single digit day and he will skip that day

when the day is a multiple of 17 he will only get 1 star and spend the next 2 days trying to broot 8trillion calculations>>103549605

How many stars will he earn if he was tasked with doing all the following days?

To begin, get your puzzle input.
>>
File: 24_D20_C#.png (484 KB, 2372x2048)
484 KB
484 KB PNG
>>103582208
Looks like I forgot about the time cap on going noclip and that was what was slowing my code down
>>103582212
my p2 implementation only checks points already traversed so I don't have to deal with any walls
>>
>>103582279
>there is only a single path from the start to the end
>imagine there being a square that doesnt appear on the best path
that is not possible
unless you want to argue semantics and say that eric didn't mean
>there is only a single path, that being the path that starts at the start and ends at the end
but he meant
>there is only a single path if you start at the start and end at the end (but there could be more than one path at different starting/ending locations)
>>
>>103582198
>>103582250
Fuck I just realized I'm not actually filtering for the 'cheat' distance at all, it's effectively counting infinite noclip. Naturally, that that doesn't matter in the example at all.
>>
      --------Part 1--------   --------Part 2--------
Day Time Rank Score Time Rank Score
20 00:39:29 2019 0 01:42:05 2582 0

sigh I probably fucked around 40mins longer than I should because I fucked up my cheat End - start - delta calculation

fun problem
>>
>>103582303
alright i could see it meaning that
>>
>>103582303
Wait I just realized that its not even a maze, its just a one wide path. I am mad now. Why do all the problems this year have all of the complexity sucked out of them?
>>
>>103581617
CUTE!
>>
File: file.png (21 KB, 913x199)
21 KB
21 KB PNG
>>103582326
yeah kek i just rewrote my "pathfinding" to just go one by one and it still works
>>
>>103582096
>mfw I misread this part and wasted an hour
fuck. at least I got a good time on part 1
>>
File: carbon.png (417 KB, 997x2540)
417 KB
417 KB PNG
>>103582307
>That's the right answer! You are one gold star closer to finding the Chief Historian.
Oh thank fuck
      -------Part 1--------   -------Part 2--------
Day Time Rank Score Time Rank Score
20 01:08:29 3618 0 01:46:43 2695 0

unwashed ass
>>
File: carbon(64).png (599 KB, 1538x2882)
599 KB
599 KB PNG
Started 25 minutes late today, my sister dragged me out shopping.
      --------Part 1--------   --------Part 2--------
Day Time Rank Score Time Rank Score
20 01:31:05 4484 0 01:41:28 2571 0
>>
File: day20clojure.png (1.02 MB, 977x830)
1.02 MB
1.02 MB PNG
ugly clojure for today
don't think I'll make it look much nicer
>>
>>103582312
my golang unwashed first part
dfs the maze to determine the distance to end for each row/col on the path.
    imap := make([][]byte, 0)
wmap := make(map[rc]struct{})
startp := rc{}
endp := rc{}

dmap := make(map[rc]struct{})
for r, vs := range strings.Split(string(dat), "\n") {
vs = strings.TrimSpace(vs)
if len(vs) <= 0 {
continue
}
imap = append(imap, []byte(vs))
for c, cha := range vs {
if cha == '#' {
wmap[rc{r, c}] = struct{}{}
}
if cha == 'S' {
dmap[rc{r, c}] = struct{}{}
startp = rc{r, c}
}
if cha == 'E' {
dmap[rc{r, c}] = struct{}{}
endp = rc{r, c}
}
if cha == '.' {
dmap[rc{r, c}] = struct{}{}
}
}
}
maxr := len(imap)
maxc := len(imap[0])

hist := make(map[rc]rcsp)
dlist := &mheap{h: make([]rcs, 0), end: endp}
heap.Init(dlist)
starts := 0
start := rcs{startp, starts}
dlist.push(start)
hist[startp] = rcsp{start, startp}
wallcands := make(map[rc]struct{})
var curr rcs
for dlist.Len() > 0 {
curr = dlist.pop()
if curr.r == endp.r && curr.c == endp.c {
break
}
for _, d := range dirs {
ndir := curr.rc.add(d)
if ndir.r < 0 || ndir.r >= maxr || ndir.c < 0 || ndir.c >= maxc {
continue
}
if _, ok := wmap[ndir]; ok {
wallcands[ndir] = struct{}{}
continue
}
nscore := curr.score + 1
pscore, ok := hist[ndir]
if ok {
if pscore.score <= nscore {
continue
}
}
rrnew := rcs{ndir, nscore}
hist[ndir] = rcsp{rrnew, curr.rc}
dlist.push(rrnew)
}
}
// fmt.Println("hist", hist)
fmt.Println("done")
fmt.Println("wallcands", len(wallcands))
shortcuts := make(map[int]int)

var cdirs = []rc{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
for dp := range dmap {
for _, d := range cdirs {
ndir := dp.add(d)
wallcands[ndir] = struct{}{}
}
}
fmt.Println("wallcands", len(wallcands))


>>
>part 2 answer way too high on example
i dont get it, isnt it like the exact same problem
>>
>>103582374

size := 20
shortcuthist := make(map[rc]map[rc]struct{})
for wallcand := range dmap {
cols := 0
distref := hist[wallcand]
for rr := -size; rr <= 0; rr++ {
for cc := -cols; cc <= cols; cc++ {
if rr == 0 && cc == 0 {
continue
}
ndir := wallcand.add(rc{rr, cc})
hend, oks := shortcuthist[wallcand]
if !oks {
hend = make(map[rc]struct{})
}
if _, oke := hend[ndir]; oke {
fmt.Println("got shortcuthist")
continue
}
hend[ndir] = struct{}{}
shortcuthist[wallcand] = hend
phis, ok := hist[ndir]
if !ok {
continue
}
dist := max(rr, -rr) + max(cc, -cc)
_ = dist
delta := phis.score - distref.score - dist
if delta > 0 {
shortcuts[delta]++
}
}
cols += 1
}
cols--
for rr := 1; rr <= size; rr++ {
cols--
for cc := -cols; cc <= cols; cc++ {
ndir := wallcand.add(rc{rr, cc})
hend, oks := shortcuthist[wallcand]
if !oks {
hend = make(map[rc]struct{})
}
if _, oke := hend[ndir]; oke {
fmt.Println("got shortcuthist")
continue
}
hend[ndir] = struct{}{}
shortcuthist[wallcand] = hend
phis, ok := hist[ndir]
if !ok {
continue
}
dist := max(rr, -rr) + max(cc, -cc)
_ = dist
delta := phis.score - distref.score - dist
if delta > 0 {
shortcuts[delta]++
}
}

}
}
shortcutkeys := make([][]int, 0, len(shortcuts))
over100 := 0
for k, count := range shortcuts {
if k >= 100 {
over100 += count
}
shortcutkeys = append(shortcutkeys, []int{k, count})
}
sort.Slice(shortcutkeys, func(i, j int) bool {
return shortcutkeys[i][0] < shortcutkeys[j][0]
})
fmt.Println(shortcutkeys)
for _, dd := range shortcutkeys {
fmt.Println(dd[1], "save", dd[0])
}
sum := over100
fmt.Println("sum", sum)
>>
> tfw finally found the retarded error
> happy, send answer
> forgot to set minimum saves to 100 instead of 72
> no I need to wait 5 minutes
AAAAAAAAAAAAA
>>
File: confusing cheat.jpg (71 KB, 272x544)
71 KB
71 KB JPG
I don't get it - why is this a valid cheat? Point 2 (labeled A in picrel) in this path is a point on the actual track, so shouldn't the cheat just end right there? I know there's an alternative but this example sucks if that's the case. Because if you can go through a point, is B not also a 2-length cheat? I went through part 1 assuming that you can't go over a point, only through walls when doing a cheat and got the right answer - so how does this make any sense?
>>
>>103582396
continue...
for each row/col block on the path step in a 20/20 diamond around the block. check if the endpoint is in my history map (its on the path and has a distance to the end), subtract the 'steps' to the shortcut endpoint. and store all the shortcuts in a map to count them.
>>
>>103582399
IT IS STILL NOT CORRECT
FUCK
I DIDN'T READ ANYTHING HERE, I AM NOT FILTERED
>>
>>103582403
you can move through anything while you are cheating (even normal spaces). You only have to END on a valid path space.
and yes, if you 'cheat' forward on the path. you cheat eg 2 steps forward, but it 'costs' you 2 seconds for the 2 step cheat. so you final time will be the same.
>>
>>103582403
>part 1 assuming that you can't go over a point, only through walls when doing a cheat
if the cheat lasted 1 second, you would go into a wall, the cheat would end, and you would get stuck, so nothing would work
when the cheat lasts 2 seconds, you go into a wall, come out on a point, then the cheat ends, and if you moved into another wall, it wouldn't work
so for part 1, it's the same as assuming you can only go through walls during the cheat
part 2 makes the cheat last 20 seconds and explicitly explains that you can move over points, not just walls while the cheat is active
>>
>>103582420
ah so B would be classified as a 1 length cheat, though it'd still be a separate cheat
>>
File: 1726818498452181.png (189 KB, 1280x1858)
189 KB
189 KB PNG
So many off by ones
Fun puzzle though
     --------Part 1--------   --------Part 2--------
Day Time Rank Score Time Rank Score
20 01:05:07 3463 0 01:50:51 2785 0
>>
File: 1722034471197753.png (1.59 MB, 1884x2965)
1.59 MB
1.59 MB PNG
>>103582218
Just for you, friend.
>>
File: 20.png (2.03 MB, 1812x4898)
2.03 MB
2.03 MB PNG
Pretty fun problem. Took me some thinking to come up with something that would work. My final algorithm was:

1. BFS to get the minimum distance of each cell from the start cell
2. Iterate over every cell
3. From that cell, find every reachable cell at most 20 cells away that are valid landing cells (i.e. '.'s)
4. For each cell we iterate over we add the distance to get to that cell, plus the manhattan distance of all the reachable cells we found, plus the distance from the reachable cell to the end
5. If that distance is less than 100, increment gold
5a. If the reachable cell was less than or equal to 2 away, also increment sllver.

Probably not the best way, but it was fun to come up with.

Now what is the Computer Science Master's Degree way of doing things?
>>
File: yui-sob.jpg (34 KB, 586x601)
34 KB
34 KB JPG
>works on example
>logic looks correct, no problems!
>submit for input
>"That's not the right answer; your answer is too low."
>>
>>103582435
in your example. B would be a 2 length cheat.
step 1 is 1 away from the 'start' of the cheat (B). step 1 is the wall in this case.
step 2 is the first '.' next to the wall. there is your 2 step cheat.
your arrow shows a 3 step cheat.
>>
>>103582440
lmao I kneel.
>>
>>103582446
sorry. NOT 2.
B would be a 3 length cheat.
>>
>>103582441
neato. I did the same.
Yeh not sure if there is a more CSway of doing it.
>>
>>103582441
Sorry, correction for point 5.

5. If that new distance saves 100 or more steps, increment gold.

Probably obvious what I meant, but just to be clear.
>>
I'm gonna bruuuuuuuute.
>>
>advent of Dijkstra
>>
>>103582477
DEEK-stra
>>
filtered on day 20 by: sleeping through the release
>cpu
>picoseconds
>racetrack
are these really leftovers?
>>
>>103582420
>>103582433
>>103582446
okay, turns out my main issue was an off by one error. get bruted, eric, I win
>>
going insane because iterating over the open spaces simply skips over some pairs (unfiltered)
>>
>>103582477
I wish it was advent of dijkstra. Check the input again, its not even a maze. Advent of straight fucking lines.
>>
>>103582486
nice
>>
>>103582484
wait this looks awesome.
2017 was the best year, I won't begrudge its leftovers
>>
what is your runtime?
shitty unwashed golang
real    0m2.432s
user 0m1.628s
sys 0m0.987s
>>
>>103582507
time ./a.out < ../20.in
Silver: 1365
Gold: 986082

real 0m0.119s
user 0m0.108s
sys 0m0.013s
>>
>>103582514
wtf is your approach?
>>
>>103582444
Check the example, when cheating is enable you can traverse several walls, not only one, not only walls.
>>
>>103582507
20.527 seconds
broot btw
>>
File: day20.png (192 KB, 740x1807)
192 KB
192 KB PNG
>>103582507
~10 ms. did a bit of washing. started late
Day       Time   Rank  Score       Time   Rank  Score
20 01:52:17 5053 0 01:58:37 2954 0
>>
>>103582517
See >>103582441

Probably a better, faster way. I'm curious to see how my approach fares on a big boy.
>>
there's definitely a graphchad way of doing this, right?
>>
File: 1374170092279.png (2.02 MB, 2539x3169)
2.02 MB
2.02 MB PNG
i will not compete for the bigboy wit this code but it was so fast to write, wtf is this day 20?
grid = {i+j*1j: c for i,r in enumerate(open('in.txt'))
for j,c in enumerate(r) if c != '#'}

start, = (p for p in grid if grid[p] == 'S')

dist = {start: 0}
todo = [start]

for pos in todo:
for new in pos-1, pos+1, pos-1j, pos+1j:
if new in grid and new not in dist:
dist[new] = dist[pos] + 1
todo.append(new)


a = b = 0

for p in dist:
for q in dist:
d = abs((p-q).real) + abs((p-q).imag)
if d == 2 and dist[p]-dist[q]-d >= 100: a += 1
if d < 21 and dist[p]-dist[q]-d >= 100: b += 1

print(a, b)

>>
>>103582449
Thanks bro.
Don't try to run it on Windows though, because I also had to increase the stack size with ulimit or it would crash lel
>>
File: 1734679356485.png (55 KB, 412x354)
55 KB
55 KB PNG
If the last 5 problems aren't really good, I might not show up next year.

actually disregard my doompost. I'll just do it in lisp or assembly or something. I'm still mad though.
>>
>>103582526
fak. i feel i did the same but you are fucking fast.
>>
>>103582507
unwashed ada 1260.61ms
>>
>>103582531
jesus. i did the same. maybe i just fucked it somewhere to get >1s
>>
>>103582559
well the last part is parallelized. single thread it's 45ms
>>
I FUCKING FORGOT TO USE ABSOLUTE VALUES WHEN I WAS CHECKING MANHATTAN DISTANCE IT TOOK ME NEARLY 1.5 HOURS
>>
>>103582487
>reassigning variable in enhanced for loop actually fucks the iteration
thanks Java
>>
>>103582559
ok removed some random state i didnt need anymore
p1 1452
p2 999556

real 0m0.482s
user 0m0.449s
sys 0m0.135s

>>
>>103582572
Ouch. I've made a retarded mistake like this nearly every day, so I feel your pain.
>>
>>103582578
gotta keep those variables immutable anon
>>
>>103582420
> you cheat eg 2 steps forward, but it 'costs' you 2 seconds for the 2 step cheat.
I had an off by one error on my bounds check for part 1 that I couldnt figure out, but "it just werks" so I didn't care. This was the answer, wasnt accounting for the time of using the cheat
>>
File: 1710165001071045.jpg (96 KB, 1200x892)
96 KB
96 KB JPG
>>103582572
it's ok bro I was running a search for all 4 cardinal directions (just did 2*dir on p1) on a 50x50 area instead of the 20x20 in the puzzle text
took forever to get the wrong answer
>>
>p2 example correct
>p2 input too high
>>
File: 1608629474575.png (12 KB, 657x527)
12 KB
12 KB PNG
>>103582605
Are you me? I did exactly the same at first.
>>
>>103582572
Also before that for some reason I thought that cheat starts in a cell you move first after it was activated.
>>
>>103582606
god dammit I was counting time saves over 50 because that was the example
>>
>>103582526
stupid question.
why do you get 'd_start' and 'd_end'?
with d_start you have the two distances you need already.
your px,py is the cheat 'start' and ex,ey is cheat end.
so you can just use d_start to get the 'end' distance sub the start dist and the man-dist?
>>
>>103582558
I'd be even less motivated to use a meme language when problems are boring.
At least with Python or something you can get through it quickly.
I will try to come up with something for >>103579106, maybe that will be good if it actually happens.
>>
>>103582634
you are totally correct, that second bfs is unnecessary.
>>
>>103582637
I want to try doing a meme language but I think would take me 45 minutes to parse the strings and make the grid each day.
>>
My p1 and p2 are basically exactly the same. How would you even do this problem differently? I tried to brute p1 at first and it took way too long. It seems like everyone will have the same solutions for both parts
>>
>>103582650
I think I've solved every puzzle this year with 1 of
- extract all integers from string
- read tilemap into 2d array of characters
- read lines of file
Except yesterday I needed string split too. Just write a utility function for each.
>>
>>103582649
cool.
>>
>>103582650
Yesterday I used Emacs Lisp. It was slow, but the advantage is that you can load your input into a text buffer and treat it as data. Grids/mazes directly work that way, with lists of colour patterns (yesterday's problem) I simply use editor commands to transform the input file into a Lisp expression that I can evaluate.
>>
>>103582655
In p1 I iterated over all walls, checked if it is between two free cells and bfs between them to get the time saved. Doing it in p2 way is obviously faster, but I didn't think of it then.
>>
>>103582675
ha. I had the same approach for p1. then switched for p2
>>
File: day20_faster.png (216 KB, 943x1900)
216 KB
216 KB PNG
>>103582526
now without hashmaps and >>103582634
it's at about 3ms parallelized.
>>
>>103582688
nice
>>
>>103582650
What's the hardest puzzle to parse? I remember not liking this one https://adventofcode.com/2022/day/11
>>
>>103582697
In normal languages everything is easy as long as you have regexes.
>>
File: kuroko-eye-palm.gif (247 KB, 498x329)
247 KB
247 KB GIF
>cant figure out why part 2 doesn't work
grim grim grim
>>
>>103582675
Also my code for p1 would break if input had something like:
##.###
##.###
...###
###...
###.##
###.##

Since I checked only opposite cells.
>>
File: carbon (11).png (461 KB, 1940x2178)
461 KB
461 KB PNG
Honestly, harder than it looked. Kinda fun to figure it out, kinda boring since it's yet another best path grid problem.
>>
How would you do this problem if it wasn't simplified with the single path - if it actually was a maze
>>
>>103582688
finding the first \n for the width and then calculating the height based on the length is going to be faster by a small amount
>>
File: kuroko-victory-fist.png (3.59 MB, 1920x1080)
3.59 MB
3.59 MB PNG
>>103582732
nvm, i figured it out
>Both parts of this puzzle are complete! They provide two gold stars: **
>>
>>103582742
It's only slightly harder.
For each tile, calculate the distance from both the S tile and the E tile.
To calculate a cheated time, add up the S-distance of the start of the cheat and the E-distance of the end of the cheat.
>>
>>103582742
that's a bit ill-defined for how the problem is described, because intentionally going into a dead-end and then using cheat time just to get back on the main path would be worse overall, but still "saving time" for that specific path
###E#   ###5#   ###9#
###.# ###4# #678#
#...# #..3# #543#
###.# ###2# ###2#
###S# ###1# ###1#

does the third example count as "saving time"?
>>
>>103582697
you probably overcomplicated it. you don't need regex, learn to use splits
>>
>>103582767
Each part of the cheat counts as a step, so no - you aren't saving time since it took equal/longer to get to the tile by cheating than just going there directly
>>
>>103582488
what shortcuts can we get by taking advantage of this though? my program is pretty slow (13s)
>>
>>103582697
the only puzzle I never bothered implementing a real parser for was monkey cube
>>
>>103582742
>>103582775
alright then, first you'd find the distance from the start to any given tile
then you'd get the distance from the end to any given tile
for every tile, look for every other tile within 20 units in manhattan distance
the distance from the start to the first tile, plus the manhattan distance required, plus the distance from the second tile to the end, is how fast you can get to the end by cheating between those two tiles
subtract the regular distance to the end without cheating to get the time saved
record how many give a equal to or greater than 100 yield
>>
>>103582742
Two dijkstras from start and from finish, then iterate over a best path without cheating in the same manner.
>>
>>103582824
Even Eric didn't, he would've given people different layouts otherwise.
>>
File: aoc_20.png (303 KB, 2000x1000)
303 KB
303 KB PNG
The first hard problem will be today
>>
>>103582824
which one was that
>>
Wait, you can walk 'through' the exit in cheat mode?
>>
>>103582908
https://adventofcode.com/2022/day/22
>>
>>103582697
https://adventofcode.com/2016/day/11/input
Not too bad but the ratio of difficulty to parse by hand vs writing the appropriate regexes is skewed way in favor of hand-parsing.
https://adventofcode.com/2018/day/24/input
I still shudder remembering hand-parsing this one, and still have no working parser.
https://adventofcode.com/2019/day/20/input
Honorable mention for the damn little warp labels
>>
>"you have someone else's solution!"
>reread
>at least 100
>change > to >=
>works
can't believe I wasted an hour on this
>>
>>103582917
sure, why not?
though I don't think there's any instance in the real input where that's required
it is in this example:
#########################
#S#E................#...#
#.#################...#.#
#.#####################.#
#.......................#
#########################
>>
File: 1718295189628873.png (28 KB, 284x558)
28 KB
28 KB PNG
>>103582975
there are some, like considering the cheat from "x" to my Green cursor here
you have to take the manhattan distance from x to green as your cheat period, and then step back to E. My program was immediately ending whenever you passed over E, even if you were in cheat mode - and another version of it was stepping around the E in cheat mode and getting the wrong counts.
>>
>>103582917
technically no but I don't think he actually checked for it
>If cheat mode is active when the end position is reached, cheat mode ends automatically.
>>
>>103582893
add a white background next time nigger i cant read that shit
>>
File: carbon.png (552 KB, 2048x2346)
552 KB
552 KB PNG
>>103582963
washed
also my issue with mutated iterators was me being an idiot and reassigning an outer loop variable
>>
part2 is basically. scan across the map with a diamond of sides 20 and count distances smaller than sth. you could keep a running count of all the distances in the diamond and only do a "boundary" update when sweeping. i.e. remove leftmost layer add one layer to the right. using a fenwick tree ( range sum variant) might make this reasonably fast, and still parallelizable across row "chunks" (with some overlap). but for this to be worth it you need a bigger bigboy and probably a larger cheating distance, since we remove a factor of "cheat distance" but add a factor "log(pathlen)"
>>
File: kuroko_devastated.png (473 KB, 460x520)
473 KB
473 KB PNG
>>103582763
> wash the solution to be clean
> gold is now off by one
fml
>>
>>103582732
>>103582763
>>103583052
kuroko sex
>>
AoC++ leak:
looks like tomorrow is a 2D grid
and it involves a starting position and an ending position
and a large part of the challenge is finding the minimum amount of time getting from the start to the end
and also advent of code is being rebranded to advent of pathfinding
>>
File: kuroko_smile2.png (2.6 MB, 1370x1080)
2.6 MB
2.6 MB PNG
>>103583052
> added a random -1 somewhere and it works now
life is good
>>
>>103582767
It's not ill-defined. Were there multiple paths and dead ends, it would still be absolutely possible to cheat from/to squares that don't fall on the shortest path(s) and still beat the honest record by enough peniseconds.
>>103582813
It's not exactly a shortcut since implementing double Dijkstra's isn't much more difficult, but only considering tiles on the shortest path wouldn't account for the class of cheats I described above.
Also I'm just letting you guys know my fiance is really fucking smart, competent, considerate and hot
>>
File: bjarne_int8_t.jpg (48 KB, 473x505)
48 KB
48 KB JPG
>>103583072
how hard is it for eric to just smash puzzle ideas together fuck's sake
give us a cellular automata problem that produces a grid to pathfind on after it reaches a stable state or something
>>
>>103583090
easier to make that 2 of the 25 puzzles instead of only 1 of the 25
>>
>>103583072
Plot twist: is a 2D hexagonal grid.
>>
>>103583072
I'm so fucking done with AOC please just give us ONE good puzzle
>>
C++
#include "aoc.h"
int main(int argc, const char** argv) {
MmFile in(argc < 2 ? 0 : argv[1]);
const int w = (in | '\n').h.ω - in.α, w1 = w + 1, z = in.ω - in.α;
if (!z) return 1;
const char * const maze = in.α;
const int delta[] = {1, w1, -1, -w1}, max_dist = z;
int start = 0, end = 0;
ɤi (z) if (maze[i] == 'S') start = i; else if (maze[i] == 'E') end = i;
V<int> dist(z); ɤm (dist) m = max_dist;
dist[start] = 0;
Q<int> q; q.push(start);
ɤ (q.ϟ) {
def pos = q.front(); q.pop();
if (pos == end) break;
ɤi (4) {
def np = pos + delta[i];
if (maze[np] != '#' && dist[np] == max_dist)
dist[np] = dist[pos] + 1, q.push(np);
}
}
const int max_cheat = 20;
int silver = 0, gold = 0;
#pragma omp parallel for reduction (+: silver, gold)
ɤi (w) ɤj (w) {
def o_dist = dist[i + j * w1];
if (o_dist == max_dist) continue;
def by_ = j - max_cheat, ey_ = j + max_cheat + 1;
def by = by_ < 0 ? 0 : by_, ey = ey_ > w ? w : ey_;
ɤy (by, ey) {
def ajy = abs(j - y), max_cx = max_cheat - ajy, yw1 = y * w1;
def bx_ = i - max_cx, ex_ = i + max_cx + 1;
def bx = bx_ < 0 ? 0 : bx_, ex = ex_ > w ? w : ex_;
ɤx (bx, ex) {
def npos_dist = dist[x + yw1];
if (npos_dist == max_dist) continue;
def distance = abs(i - x) + ajy;
def saved = npos_dist - o_dist - distance;
if (saved >= 100) ++gold, silver += distance == 2;
}
}
}
$o silver, gold;
}
>>
File: IMG_4087.gif (737 KB, 220x347)
737 KB
737 KB GIF
>”paths” are allowed to overlap themselves
>but only during the cheat stage
>the spec says nothing about this
>>
>>103582488
advent of hey asshole, first actually look at your input

not a bad thing IMO
>>
>>103583157
Cheats are uniquely identified only by their start and end points, so this is never something you have to consider or handle. Learn to learn then learn to read.
>>
Pretty easy problem to broot. Once you have the path, the feasible shortcuts are just every pair of path tiles. Just compare them all, get their taxicab distance, and you're good to go
>>
>>103583220
I’m unashamed to admit that’s how I got my stars. Elegance will follow later.
>>
>>103581864
python chads can just import solution
>>
File: IMG_2398.jpg (39 KB, 707x630)
39 KB
39 KB JPG
>>103583201
What the fuck are you mumbling about you fucking retard? There are 12 cheats that save 66 moves, meaning this is one of them:
###############
#...#...#.....#
#X#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#X#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Fucking kill yourself
>>
>>103583072
If I have to manually parse my data into a grid one more time I'm going to freak
>>
File: 1734495507114167.jpg (242 KB, 919x1024)
242 KB
242 KB JPG
Literally had to do today on a phone because I was traveling and my laptop's battery died. Also I didn't have internet access for like 4 hours. Well that sucks
>t. xarbon guy
>>
>>103583311
>Also I didn't have internet access for like 4 hours
Believed your lie up to that point.
>>
File: 1720989637908864.png (350 KB, 1210x2210)
350 KB
350 KB PNG
>>103583311
full unwashed, sorry but no xarbon today
>>
I almost got filtered by bad reading comprehension, kill me.
>>
NEW THREAD
>>103583342
>>103583342
>>103583342
>>
>>103583289
what? you can go into the wall to get there. i see your concern, but I doubt its going to matter much since 20 is pretty big and you can Go Around a lot with it. the only situation i can imagine where it presents a problem is if you have something shaped like
######################
#,,,,,,,,,X,,,,,,,,,,,#
#,###################,#
#,#,,,,,,,,,,,,,,,,,,,,,#
#,#,####################
#,#,,,,,,,,,,,,,,,,,,,,,
#,######################
#,,,,,,,,,,,Y,,,,,,,,,,#

######################

(hope i drew that right) long things like this where you cant get from X to Y without crossing the middle rows, possibly invalidating the path
>>
>>103583371
in <=20 steps I mean
>>
>>103583371
>go around
that takes up more steps
which means the distance from beginning to end is longer if you deliberately avoid overlapping
>>
File: Day20.png (179 KB, 977x1669)
179 KB
179 KB PNG
CShart

>>103582302
how fast is your code? Mine takes 4sec
>>
File: two wars.jpg (66 KB, 1242x902)
66 KB
66 KB JPG
>>103583090
TWO PUZZLES??



[Advertise on 4chan]

Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.