File: 1734351996338348m.jpg (46 KB, 1024x424)

46 KB JPG

I am too dumb for any of this all I do is monkey crud

what is a dijkstra's edition:

import math
import sys

sys.setrecursionlimit(int(1e9))

g = list(map(list, open(0).read().split('\n'))); g.pop()
rows, cols = len(g), len(g[0])
cache = [[math.inf] * cols for _ in range(rows)]

m = {}
def dfs(pos, d, cost):
    if pos == (1, cols - 2):
        return cost
    (r, c) = pos
    cache[r][c] = min(cache[r][c], cost)
    dx = ((-1, 0), (0, +1), (+1, 0), (0, -1))
    minimum = math.inf

    # continue
    (dr, dc) = dx[d]
    (rr, cc) = (r + dr, c + dc)
    if g[rr][cc] in '.E' and cache[rr][cc] > cost - 1e3:
        minimum = min(minimum, dfs((rr, cc), d, cost + 1))
    
    # turn left and continue
    (dr, dc) = dx[tmp := d-1 & 3]
    (rr, cc) = (r + dr, c + dc)
    if g[rr][cc] in '.E' and cache[rr][cc] > cost:
        minimum = min(minimum, dfs((rr, cc), tmp, cost + 1001))
    
    # turn right and continue
    (dr, dc) = dx[tmp := d+1 & 3]
    (rr, cc) = (r + dr, c + dc)
    if g[rr][cc] in '.E' and cache[rr][cc] > cost:
        minimum = min(minimum, dfs((rr, cc), tmp, cost + 1001))
        
    if minimum not in m:
        m[minimum] = set()
    m[minimum].add((r, c))
    return minimum

p2 = len(m[p1 := dfs((rows - 2, 1), 1, 0)]) + 1
print(p1, p2)

File: solve.png (796 KB, 5546x3842)

796 KB PNG

idiomatic Rust solution

>>103538073

while let Some((cp

you rust pedophiles disgust me

>>103538087
the child consented though

>>103538057
top kek

glad I made sure to keep a tab open explaining dijkstra for the past ten days, it really came in handy today

>>103538460
sorry but you don't need dijkstra's today: >>103538070
keep that tab open

>>103538498
>cache
yeah that's dijkstra's

>>103538540
no dijkstra's is BFS but with a priority queue

>>103538540
dijkstra's guarantees that when a node is visited that its distance is final.
not only does my code not make that guarantee, it fucking *revisits* nodes.
you truly don't know what dijkstra's is.

>>103538543
same thing

>>103538574
nta but your version is retarded brute foce that assumes that the chracter is starting in such way that no pi radian turn is required and thus guaranteeing that it won't run for an infinite time
You didn't even solve the problem.
>b- but mut star
ok, be happy about it, that's a seperate system and doesn't equate to solving the problem.

>>103538594
>dijkstra fag coping and seething
DFS chads keep winning

>>103538594
are these pi radian turns in the room with us now? Eric only says they can turn 90 degrees.

>>103538594
>>103538605
>>103538606
Forgive me I didn't read through your code carefully
> cache[rr][cc] > cost - 1e3
So this is what makes sure that the program will eventually terminate huh.
Still slower than my bfs if the graph is large enough.
O(logv(V+E)) vs
S
O O O O O
O
.
.
.
O
Consider this graph there is an edge from every node in level 2 to the single node in level 3 and it has a really long tail. And all the edges are 1 smaller than last one, then it will revisit the entire long tail over and over and over again.
You could do this in muliple layers so the runtime is catastrophic, could be Omega(2^n) worst case if the weights are like that.
Face it, your solution is niggerlicious.

File: carbon.png (784 KB, 953x4227)

784 KB PNG

>>103536112

Bigboy/day 16 bigboy    time:   [169.31 ms 169.93 ms 170.62 ms]
day 16                  time:   [1.7307 ms 1.7336 ms 1.7368 ms]

I first find all connections between important tiles: crossroads, S and E. Then use dijkstra's algorithm to find all shortest paths to E. At the end, I do dfs starting from E and only visiting nodes that previously had the exact same costs as current cost from E and record tiles between them. That last part is kinda nice, because I don't have to allocate or clone anything.

Are most of you employed or in school? Is it fair to say that most people who do these are in their 20s?

>>103538789
I'm younger than that.

>>103538789
this post glows

>>103538757
the 1e3 check accounts for branches which reach the same cell from different directions
if i had 4 copies of the graph in cache then the speed would be comparable to dijkstra's
the niggerlicious slowdown is from the naive "if it's only off by 1000 then it's still worth investigating"
i chose to solve it this way because it's shorter
you may also know me as the guy who rotated the entire graph on day 15 0 or 4 times on each step so i only had to consider one case

if this is monday's puzzle, I'll be filtered by friday

>>103538853
I can see the appeal of dfs for part 2 because of the path recovery, however if you store parents from which you arrived at optimum cost you to some node, starting from the end position node it will form a tree and by traversing that with dfs you still get part 2
And for part one bfs is objectively better how is that shit shorter than heappush and heappop

>>103538853
>you may also know me as the guy who also did some retarded shit on a previous day

>>103538863
If you feel like you'll get filtered on Friday because of today's puzzle, you got filtered by today's puzzle. Don't wait, remove your name NOW!

if this is monday's puzzle, I'll save christmas on time

>>103538896
Sorry this is not entirely precise the parent node thing will form a dag not necessarily a tree but that doesnt change the fact that it can be traversed with dfs just dont blindly increase a counter but rather turn the flag on sum afterwards

File: im-1734366480537.png (33 KB, 524x704)

33 KB PNG

>pytoddler
washed and replaced my dumb implementation of part 2 with a smarter approach.

>>103538979
Anon Python is one of the 6 certified White man's languages
Anyone telling you otherwise is just cope

>>103539024
what are the other 5?

File: 24_D16_C#.png (887 KB, 2372x4206)

887 KB PNG

Spent way too long trying to figure out why my hashmap wasn't properly hashing. Even had to use AI to find out in the end. It's so over.

man i’m happy with my part 2 solve. ended up just changing 1 line. score < visited(xy) to score < visited + 1000. that and len(set(pos)) was enough. unfilty’d today bois.

>>103539121
HolyC, C, C++, x86 asm, Mathematica

File: file.png (8 KB, 690x677)

8 KB PNG

Pretty sure I overcomplicated my solution, but I think it's pretty neat. I did two runs of Dijkstra's algorithm, one from S and one from E (and critically for the second one, I made (E, north, 0), (E, south, 0), etc. the initial frontier). This creates two maps, sSPD and eSPD, where sSPD contains the shortest path distances from (S, east) to any (P, dir) and eSPD has the shortest path distances from any (E, endDir) to (P, dir). For any particular point P, the length of shortest path that goes through P is the min over all directions D of sSPD[(P, D)] and eSPD[(P, -D)] (we have to negate D here because eSPD has paths in the opposite direction of what we want)
Probably could do some pruning during the second run of Dijkstra's algorithm to ignore points that won't possibly lie on the shortest path from S to E, but my brain's a little too cooked for that now

File: r-castle2.jpg (82 KB, 1041x658)

82 KB JPG

>>103539024
>tfw been shitting out python for nearly 15 years now
it's just so comfy though

I solved it by doing Djikstra's and then
>backtrack through the least-cost path
>at every fork in the road, determine if the other fork is also a least-cost path
It was kind of retarded but happy to not be filtered without cheating

File: carbon(2).png (990 KB, 894x5652)

990 KB PNG

Bigboy times:

   backfill: 28.95ms
   nodelist: 36.81ms
   graph: 13.85s
   part1: 13.97s
800196
2367
    total: 14.13s

Graph creation is killing me. Turned each <intersection, direction> pair into a hashmap node, is there a more efficient way?

>>103539230
C++ doesn't belong

>>103539349
where the bigboi at

>>103539377
>>103528248

>>103539387
what in the hell i aint reading all that shit

>>103539366
Yes it does and you're brown

>>103539377
See >>103536112
https://files.catbox.moe/l64q3v.txt
1000x1000
Part 1: 800196
Gold: 2367

>>103539418
Stop projecting vivek, only a streetshitter would defend what might be the worst-designed language of all time.

>>103539454
newfag streetshitter, how dare you question a Danish Aryan AND The Divine Intellect
https://www.youtube.com/watch?v=25hLohVZdME

>>103536564
Using Ddijkstra in Part 2 allows you to avoid tracking paths, which is expensive and slow. The idea is this:

>From the start, get the min cost to every other tile.
>From the end, get the min cost to every other tile.
>For every tile, if cost_from_start + cost_from_end == min_path_cost_from_part_1, add tile to set.
>Return length of set.

I'm getting 130ms in Python. You don't necessarily NEED to use Djikstra, but it's a very straightforward way to get the minimum cost to every other tile from some start tile (though you can also get this with DFS/BFS).

>>103539490
Oh, just doing Djikstras from the ending node is so much simpler than what I did for part2

>>103539490
oh shit that's brilliant

>>103539490
wow this is hella slow

>you'll need to determine which tiles are part of any best path through the maze
so? I'm getting ESL'd here. There's only one BEST solution. There are multiple good enough solutions, but there's only one BEST solution.
Unless multiple paths exist with the same score?

>>103539594
>Unless multiple paths exist with the same score?
yes

File: filtered.png (163 KB, 1653x960)

163 KB PNG

Well, I'm filtered. Can't even get part 1. I've tried both recursion and Djikstra, I've written the entire program 4 times, and every time it works on the two examples but not the input.
It's been fun, see you all next year.

>>103539600
thanks

>>103539594
>Unless multiple paths exist with the same score?

If only there were ASCII examples showing graphs with multiple best routes

>>103539609
Run someone else's code and see if it's something dumb like being 1000 off (aka one corner)

>>103539594
maybe read the part where it describes what a best path is?

>11:11:11 until the next puzzle drops
what does it mean? is this a secret hint for what tomorrow's puzzle will be, in the form of a little easter egg left by eric?

I wonder, does this show up in any inputs?

##.##
##.##
.....
##.##
##.##

Couldn't be in mine because I'm fairly sure it wouldn't handle this case

>>103539706
haha anon very funny keep it up

>>103539488
Luckily he was able to leave his job and move onto non-shit languages

So did you all find nodes or use the grid as is?

Graph compression is kind of a waste of time here, right?

>>103539757
making a graph is a waste of time, just operate on the grid directly

>>103539757
That's what I assumed. I can see how it would help on Part 1, but for Part 2 (which is where I wanted to speed things up) it seems pointless since you have to uncompress anyway to get the distinct tiles. Maybe there's a big brain approach here I'm overlooking that lets you get the count of unique tiles from the compressed graph.

>>103539757
I'm not sure how well it would work given that heading matters for scoring purposes

File: carbon (12).png (273 KB, 1118x1353)

273 KB PNG

>>103539786
Washed python. Quite pleased with this one, although it's completely different than my original solution.

File: sad-apologizing-emoticon-(...).jpg (107 KB, 1300x1146)

107 KB JPG

>>103539821
Sorry, didn't mean to respond to you >103539786

>>103539349
I used a vector backed graph here >>103538776 and each node has 4 edges that might point to another node's index. A hashmap is used for the initial graph construction but that's it. It takes 135ms to construct the graph, but I create new nodes on the fly instead of your initial sweep. I still count all neighbors every step to detect crossroads but at least there are no hashmaps involved...
>>103539782
I store paths between 2 nodes, part 2 takes like 800µs for bigboy, it's a bit hard to measure. I think you could also just store the edge lengths, then:
part 2 = unique edges' lengths - 1 for each repeat node visit

ok i give up i spent way too much time on this and i can't figure it out
what is the trick to solve part 2?

>>103539909
>>103539490
or just Dijkstra again while recording the path so far, pruning every time you exceed the cost from your part 1 answer. Every time you get to the end with a cost equal to your part 1 answer, add that path to a set of tiles.

>>103539909
Brute force

File: amazing.gif (55 KB, 1200x600)

55 KB GIF

part 2 gif. nbd. but I guess you could say I'm pretty a-maze-ing.

>>103539720
I've got crossroads in my input, if that's what you're getting at. There's one in the first example as well, line 8 character 4.

all i'm sayin is tomorrow better not be some 3d bullshit.

>>103539909
just dfs, you can even use your p1 result if you want: >>103538070

>>103536112
does this have features not present in the official input? my solution solves both parts in 60ms but OOMs on the bigboy

File: reddit.jpg (82 KB, 1080x1061)

82 KB JPG

>code keeps giving wrong answer
>spend an hour trying to find bug, no luck
>copy paste code into chatgpt
>immediately points out minor typo causing the issue
Why shouldn't I do this? Why waste time when i can get my bug fixed immediately?

>>103538789
AoC didn't exist when I was in my 20s.

>>103539909
My shitty broot solution was just to keep track of the path tsken as well as the cost in my djikstra.

got filtered today on part 2. see ya next year bros.

>>103540200
Do whatever you want, lil brainlet

>>103540200
>immediately points out minor typo causing the issue
editors have been doing this for people forever
hell, even the python interpreter catches this shit

>>103540200
Constantly relying on other systems to solve your problems will erode your own ability to solve them.

>>103540282
let me guess, you didn't know how to handle rotations properly and just applied the score to the next node instead of the current one bricking your path reversal?

>>103540282
Part 2 is easy to broot using the results from part 1.

>>103540282
p2 is so short you can fit it in a 4chan post: >>103538070
no dijkstra bullshit, just broot: >>103540357

>>103540190
It has

.#
#.

>>103539757
A waste of programmer time for solving the input? Yes.
A waste of CPU time for optimizing execution speed?
No.

>>103540443
new cope just dropped
define waste

>>103540354
exactly
>>103540357
>>103540362
my PC crashed when I tried, kek

Caught a cold and I can barely think... bros I don't want get filtered....

File: 16304932219190.jpg (52 KB, 512x267)

52 KB JPG

>>103540443

File: xarbon.png (17 KB, 500x868)

17 KB PNG

washed ass for day 16, still lazy to wash 15
bigboy:

$ ./main < l64q3v.txt 
+ ulimit -s unlimited
+ pypy main.py
+ tee /dev/fd/63
++ tail -n 1
++ xclip -sel clip
800196 2367

real    0m15,494s
user    0m15,345s
sys     0m0,146s

Do you
>fap before the puzzle to have a clear mind when it starts
Or
>don't fap unless you get stuck on a specific edge case, to let the problem sauté for a while, until you come back to it with a fresh mind

>>103540635
there's a reason why it's called an edge case anon

>>103540481
to handle rotations properly you need to add another dimension to your score table, direction
>scores[direction][y][x]
and now one of the paths you can take on your djikstra is rotate (different direction, same y/x) on a node

>>103540635
>Or
> >don't fap
Yes.

File: code.png (520 KB, 1792x3308)

520 KB PNG

Python

I adapted a pathsearch from previous years. I somehow got one of the 2000 and 1000 swapped on dirs_scores and it gave me the correct answer on part 1 for both examples but not the input. Quite MADDENING.

Also It is doubtful I will be able to do the next three days.

>>103540653
thanks, this makes sense. I still consider myself filtered. I spent literal hours on this, feel tired, and don't want to play anymore.

>>103540635
man I have RSI now after years of this shit, have to conserve my arms for typing
only when I'm actually horny

>>103540413
that shouldn't cause any issues for me, but my solution is to find all the junctions and path over the graph of those instead. maybe it's just too many (bigboy has 149966)

>>103540635
>edge case
heh

>>103539720
No idea, but my solution most likely handles this.

>>103539720
>>103540825
My input has this pattern.

>>103540635
i do the puzzle first, then I spend the rest of the day fapping, once for each line of code

File: tgf.png (869 KB, 2039x2117)

869 KB PNG

Stop crying. It is quite unbecoming.

File: day16_swift.png (1.28 MB, 1834x5138)

1.28 MB PNG

Swift using BFS in both directions. Could be cleaner.

File: 1714507751764855.png (8 KB, 379x764)

8 KB PNG

truly an import solution sorta day today my uiua friends
code to come

File: 1705830243686198.png (32 KB, 467x478)

32 KB PNG

>>103541216
here it is
visualization code not included and left as an exercise to the reader

File: 1704245775702956.png (63 KB, 400x400)

63 KB PNG

why are all these nerds talking about their smarty-pants algorithms when all you need to do is ``from networkx import all_shortest_paths`` baka

>>103541241
you did not beat aoc

File: day16.png (41 KB, 908x325)

41 KB PNG

BQN day 16

>>103541241
i haven't used nx but i've seen it in solves over the years -- do you have to massage your data into an adjacency list or what particular data-structure in order for it to work?

>>103541404
answering myself here but wouldn't you need to do a bfs over the gameboard and then add all the edges and costs in order to then use nx to solve it?

>>103540996
Well I am now filtered. Yesterday was piss easy, but I cannot figure out D16 part 1. I've got Dijkstra implemented, but setting up my costs for each travel step is fucking me in the arse. It's been fun, but this is where I get filtered.

>>103541428
if you need a hint and haven't figured it out yet you can calculate the next step's cost in a "stateless" manner
i.e. you don't have to keep the currently facing direction as global state to the dijkstra function

>>103541428
hint: you don't need dijkstra's: >>103538070

>>103541428
>>103541448
all this direction stuff made me think: is there a path where you cross a point twice? once on North-South axis, and the other time on West-East axis?

File: aoc_2024_16_b.png (1.12 MB, 2022x6888)

1.12 MB PNG

>>103541448
This is my (broken) solution. I'm pretty sure the problem sits with the recurse function and not Dijkstra.

>>103541468
no, the shortest path would always turn at such a point

>>103541468
no by definition because you would prefer turning in that point

>>103541484
turnleft and turnright is useless, you just need to know the neighbours
dijkstra guarantees you wont turn back on your path

>>103541503
But knowing whether I continue forward or turn determines whether I add weight 1 or 1001 to the edge.

>>103541404
>>103541421
Not that anon and not the most efficient algorithm on part 2 but here's what mine looked like. Nodes are ((i,j), direction) tuples. Iterate over the grid adding every edge to the graph.

import networkx as nx
import numpy as np
import sys

grid = np.array([[*l] for l in open(sys.argv[1]).read().splitlines()])
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
G = nx.DiGraph()
for p, e in np.ndenumerate(grid):
    if e == "S":
        start = p
    if e == "E":
        end = p
    if e == "#":
        continue
    for i, dir in enumerate(dirs):
        G.add_edge((p, i), (p, (i + 1) % 4), weight=1000)
        G.add_edge((p, i), (p, (i - 1) % 4), weight=1000)
        if grid[p[0] + dir[0], p[1] + dir[1]] != "#":
            G.add_edge((p, i), ((p[0] + dir[0], p[1] + dir[1]), i), weight=1)

print(
    min((nx.shortest_path_length(G, (start, 0), (end, i), "weight")) for i in range(4))
)

seen = set()
for i in range(4):
    seen.update(
        node[0]
        for path in nx.all_shortest_paths(G, (start, 0), (end, i), "weight")
        for node in path
    )
print(len(seen))

>>103541509
like I said, you can do that statelessly
btw your recursion function is all sorts of fucked up
its better to just quit when you get to a bad path instead of only going to good paths, this is true for 99% of recursion algorithms

File: 4way.png (9 KB, 969x897)

9 KB PNG

>>103541468
It's entirely possible (at least in part 2)

>works on examples
>doesn't work on input
at this point I'm not even surprised

>>103541531
>btw your recursion function is all sorts of fucked up
Don't I know it, lol.
Ah well, it gives me something to do when I go on leave next week.

>>103541544
That is two different paths crossing one point. Not one path crossing the same point twice.

>>103541552
Don't do recursion.
Implement a stack. It is easier.

>>103541547
Had that with both parts, something about today's problem

>>103541509
Nodes in dijkstra can be more abstract than just irl coordinates

>>103541453
If you have dijkstra set up it'll be much easier to add direction to state than use a completely different algorithm

>>103541552
https://www.youtube.com/watch?v=ngCos392W4w
I really recommend watching this video to understand recursion
it's basically just proof by induction, you handle base cases first, you figure out how to get a step closer to a base case, and then you just assume that your function works and use the result of it to compute the total result
the video definitely explains it better, but recursion gets incredibly easy once you just handwave all the complexity away and assume it just works by default
>>103541570
recursion is generally easier than iterative once you know the process imo

>>103541568
Obviously it's impossible in part 1, you won't revisit any tile

File: file.png (4 KB, 603x539)

4 KB PNG

>>103541568
If you have any loop like that, then it'll always be a strictly worse path than just making a turn that avoids the loop entirely

>>103541598
>recursion is generally easier than iterative once you know the process imo

Recursion is just iteration where you're using the call stack as your stack. Sure it's slightly easier in that you have to write less code, but if you're at all confused about what's happening, better to spell it out. Plus you often end up with much faster code.

sounds like this AoC features all the most fun and exciting topics: parsing, caching and graph algorithms

>>103541653
it's basically work

What edge case this is falling?

const auto [nodes, start, end] = parse(argv[1]);
auto score = std::unordered_map<vector<2, int64_t>, int64_t, hash>();
auto pqueue = std::priority_queue< std::tuple<vector<2, int64_t>, int64_t, int64_t>, std::vector<std::tuple<vector<2, int64_t>, int64_t, int64_t>>, cmp>();
    
for (const auto& n : nodes) score[n] = std::numeric_limits<int64_t>::max();
score[start] = 0;
pqueue.emplace(start, 0, 1);

while (!pqueue.empty()) {
    const auto [n, s, d] = pqueue.top();
    pqueue.pop();

    if (n == end) {
        std::println("{}", s);
        break;
    }

    auto nn = n + directions[d];
    if (nodes.contains(nn)) {
        auto ns = s + 1;
        if (ns < score[nn]) {
            score[nn] = ns;
            pqueue.emplace(nn, ns, d);
        }
    }

    auto ns = s + 1001;
    auto nd = (d + 1) % 4;
    nn = n + directions[nd];
    if (ns < score[nn]) {
        score[nn] = ns;
        pqueue.emplace(nn, ns, nd);
    }

    nd = (d - 1 + 4) % 4;
    nn = n + directions[nd];
    if (ns < score[nn]) {
        score[nn] = ns;
        pqueue.emplace(nn, ns, nd);
    }
}

>>103541639
>Recursion is just iteration where you're using the call stack as your stack.
that's true, but imo only in a literal sense
from my experience when people "get" recursion it's as simple as being able to solve one or two incredibly simple examples and then just handwaving away the rest of the solution because they know they're always progressing towards the base case
with iteration there definitely seems to be a bigger incentive to people trying to fit the entire problem (or at least the stack) in their heads, which is probably why recursion ends up going above people's heads

edgecase bros

#######
#S#...###
#...#...#
#.#####.####
#...#.....E#
###.#.######
  #...#
  #####

>>103541692
doesn't your priority queue want the priority to come first?

File: 1570843334040.jpg (46 KB, 899x324)

46 KB JPG

Now that we've had dijkstra this year, what can we expect in coming days?
>3D points and lots of calculating intersections or some shit
>line segments
>unfuck this assembly program
>DP (yes I know we kinda had it day 11, but that was too easy)
>rotating shit in grids
>RPG / simulation
>???

>>103541801
>line segments
>unfuck this assembly program
>hard cycles shit with primes
Those for sure

>>103541801
Folding origami 4D hypercube

Fucking do it, Eric. I dare you.

>>103541801
Cellular automata
Didn't have one last year, so we're due

File: carbon.png (316 KB, 2348x1676)

316 KB PNG

>>103541404
Not that anon, but this was my lazy solution using networkx. I just created a directed graph where there was a separate node for each (x,y,direction), then added edges with the appropriate weight between each of the relevant nodes (1000 to turn on the spot, 1 to move forwards while facing the same direction).

The contracted_nodes part is just combining the two versions of the end node where you are facing north and east, since the problem doesn't care which direction you're facing once you reach the end. It would probably be more efficient to identify the end space during the parsing and handle it differently at that point, but I cba to deal with that. It's also ignoring the versions of the end space where you're reaching it facing south or west, but in this case since the end is always in the top-right corner those situations are impossible here.

After you've set up the graph, it's just a case of abusing the built-in methods to find the shortest path and getting the answers.

>>103541832
We just had cycles with primes, although it wasn't very hard

>>103540635
I edge on puzzles for hours.

>>103540635
a mid problem shit or fap always helps me debug

File: aoc_2024_16_a.png (839 KB, 2022x5126)

839 KB PNG

>>103541484
Holy fuck, this actually works for Part A. I just handle the direction within Dijkstra's algorithm. Thanks for the advice, lads.

>>103541801
Would love for him to thrown an intcode program in there as a callback to 2019, perhaps as the "unfuck this assembly" problem.

redpill me on C#

>>103541801
More
>grid problem
>grid problem
>grid problem
>grid problem
>grid problem
>grid problem

>>103541987
more like C-Shart

>>103541866
Did we?
Fuck I can't recall at all.
Maybe I got Parkinson's or something.

>>103541801
lots and lots of leetcode-tier problems -- forever

>>103541987
white mans language

>>103542004
Day 14 can be brute forced by just checking all W*H states, but one way of optimizing it is by finding two points in time that minimize the X and Y coordinate variances (which requires far fewer iterations as the motion is periodic) and applying the Chinese remainder theorem to find the time that minimizes both variances at once

>>103542031
it's the most indian thing that isn't java

>>103542040
no thats js

>>103542040
all programming languages should be ranked by how much of their relative popularity comes from india

>>103542046
prove it

File: file.png (41 KB, 751x509)

41 KB PNG

>>103542056
>>103542057
oh nonono pytoddlers...

not filtered but today was straight up NOT FUN

>>103541801
Assembly would be nice. Anything visual too.

>already have a graph of each state visited and the best possible score at the state
>just start at the goal, imagine the prior states and then add all ones in your graph to the set of visited states (repeat x failure)

I HECKIN LOVE GRAPHS!!!!

Is Part B just asking for every path that goes from S to E, without cycles?

>>103542192
Every path that goes from S to E with the same min

surely there must be an alternative to advent of code where you build something cool over a few weeks, rather than doing job interview problems

>>103542192
len(set([node in best_paths]))

File: 1699477087520166.jpg (97 KB, 550x512)

97 KB JPG

>>103542214

>>103542239
you don't like doing graphs?

File: 1645533642916.jpg (42 KB, 800x450)

42 KB JPG

>>103541989
worst thing about aoc

>>103542239
You mean like home projects?

>>103541801
tomorrow you have to dust off your intcode vm and extend it with doubles. the 4.5793472146389 instruction is division

>>103542361
>intcode
>doubles

>>103542239
codecrafters has this but its not an event
idk how good it is either I just know its shilled by some youtubers I like

File: 2024-12-16_22-45.png (241 KB, 1830x1323)

241 KB PNG

corejavabros we came really close to being filtered today.
one more day with this kind of part 2 and it might be it for this year...

>>103536112
getting wrong part 1, then part 2 balloons to multiple dozen gigs of RAM after a few minutes and presumably never finishes
thanks for providing a bigboi tho, it's truly a big one

>>103542119
>just imagine a solution to the puzzle

>>103542567
>then part 2 balloons to multiple dozen gigs of RAM
This is the same problem I'm running into, no idea how to solve it. But I get the correct part 1 answer in 600ms.

>>103542567
>>103542604
Are you enumerating all paths? Because the number of paths is exponential, and you don't need to do that.

>>103542612
Yes. Is it not enough to just cull paths if they exceed the min cost I find for part 1?

>>103542618
The number of minimum cost paths is still exponential, so no.

>>103541920
Dijkstra tutorials suck because they pretty much all confuse a node in the search with a physical node in a map. When irl the state often carries other info.

>>103542069
Now we know why shills hate Rust

>>103542361
dubs and this is happening

File: maze.png (15 KB, 1000x1000)

15 KB PNG

Fellow anons what is wrong with this obviously perfect solution? I get both examples correct for A and B, but this solution for part B, on my actual puzzle data is too looooow.

>>103542604
What are you considering a node, each dot?

>>103542696
Each junction. Solves the official input in 30ms so I'm surprised it doesn't work for the bigboy.

>>103541653
There haven't been any days with difficult parsing yet this year.

>>103542689
Triple check your score algorithm.
I got it wrong and some how gave me the right answer for both examples but not the input.

>>103541653
>filterlet cope
seethe and return to vscode with catpuccin I see you faggot

>>103542689
off by 1 error add 1

>>103542142
I FUCKIN HATE GRAPHS

File: Day16-2.png (4 KB, 191x131)

4 KB PNG

>>103542689
Looks like there should be another valid path here.

>>103542782
what the hell is catpuccin?

>>103542824
Common (and overdone) onions-dev color scheme.

>>103542801
Damn. I think you are right. How could it catch the others but miss that one? Investigating. Thanks!!

>>103542689
Triple check the start/end states are handled properly, that was my edge case. Thought Eric was generous with two examples but a bunch of anons are saying the same thing, there are common input edge cases the examples don't touch.

>>103542704
How exactly are you storing the graph+paths? I got similar times on the input and bigboy was 14s. Others got similar input times and ms bigboy times, and at a high level all our code sounds pretty similar.

>>103538073

while let some cp r(a)p(e) d(ouble)p(enetration) h(ymem).pop()

No way that is a coincidence.

>>103542604
>no idea how to solve it
ngl I just ran it to see if it would, saw that no, and that's it. doubt I could find a fast enough solution even if I tried.

>>103542612
>Are you enumerating all paths
to a point?
enumerating routes until one of:
1. I run into a node+orientation I visited before, and my current cost is higher than back then
2. current path cost exceeds best cost (silver result)
I'm sure there's much clever ways to do it, but by the looks of it >>103542623 is right and my priority queue grows faster than I pop off it, and the cost of interacting with it is what dominates time spent in the end

>>103542941
schizo

>>103542957
Consider each node individually. Is the minimum cost to end plus the minimum cost to start equal to the minimum cost from start to end? Then the node is part of a minimum cost path.

>>103543000
yeah I tried this double-dijsktra-type approach at one point, and got the wrong value back
probably cause I didn't handle the matching of both sides + their respective possible directions
but also double-dijkstra for each node is slow as shit and I strongly doubt anyone solved bigboy with that
but maybe there's a way with 2 dijkstra passes and then just looking at cost maps? idfk to be honest

>>103541241
based solution importer

>>103543051
Dijkstra gives the minimum cost to all nodes, so you only need to run it twice and save the cost for each node.

>>103542604
You solve exactly like part 1, except for each node you store a vector of [shortest nodes that reached this node]. Almost all vectors will have 1 element, some will have 2. At most they can have 3.

When you reach the end node, put it on a stack (only exit when you find a node with a higher value, just in case there are 2 routes that approach the end from different directions).

Then you backtrace, sure this occasionally branches but it's basically linear:

// node.0 is the coordinates, node.1 is the direction

// Count unique tiles on shortest paths.
let mut unique_tiles: usize = 1;
let mut been_on_stack: HashSet<Point> = HashSet::new();

while !stack.is_empty() {
    let current_node: PointDir = stack.pop_front().unwrap();

    // Cannot retrace further than start.
    if current_node.0 == start.0 {
        continue;
    }
    for prev_node in previous.get(&current_node).unwrap() {

        // Rotation, doesn't affect path count.
        if prev_node.0 == current_node.0 {
            stack.push_front(*prev_node);
            continue;
        }

        // Hope there are no paths >1000.
        let path_len: usize = graph.get(prev_node)
            .unwrap()
            .iter()
            .filter(|maybe_current| maybe_current.0 == current_node)
            .next()
            .unwrap().1 % 1000;
        unique_tiles += path_len;

        // Only backtrace from each node once,
        // even if mutiple paths lead to it.
        if been_on_stack.contains(&prev_node.0) {
            unique_tiles -= 1;
        } else {
            stack.push_front(*prev_node);
            been_on_stack.insert(prev_node.0);
        }
    }
}

// unique_tiles is now your part2 answer.

I have no idea where you're using gigabytes of RAM on part 2 specifically.

>>103543051
I didn't have to worry about directions at all.

optimal_tiles = set()
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            if grid[y][x] != '#':
                for dir1 in '^v<>':
                    for dir2 in '^v<>':
                        if forward_costs[x,y,dir1] + backward_costs[x,y,dir2] == min_cost:
                            optimal_tiles.add((x,y))
                            break      

Just broot through every direction combination and take all combos that result in the min_cost path.

>>103542879
My graph is an array of nodes, each node has an array of edges, each edge has an index into the node array and a list of points between the two nodes. I think the design is all reasonable except where I build paths. Each time I visit a new node I record the position permanently in a list as a child of some other position in the list, and this list of visited nodes is multiple millions of elements. I don't prune it because I want the indices to be stable, but this is partly why mine is fucked (the other is that the queue of places to visit is also >1M)
>>103543000
what the FUCK my mind is blown

>>103542957
thats normal for a bfs, you have to use a different algorithm if the number of paths is that large
>>103542604
for the bigboy or for the real puzzle? if its the real puzzle you fucked up somewhere

>>103538057
I was able to modify my Djikstra's to actually work though... The path mapping gets hairy but conveniently the input lets you implement it incorrectly and still get the right answer. There is also only one unique way to reach the End point with the lowest cost.

>>103542801
Thanks again this fixed it. I was backtracking from the end and only following edges with exactly the cost I was expecting at that point. The flaw was marking vertices as 'already visited' instead of the edges as 'already followed'.
In this edge case you have to revisit the vertex while backtracking from a different direction.

Is 326ms anywhere near reasonable for this problem? This is taking a big bite out of my self-allotted budget of 1 second for the entire aoc2024.

>>103543135
imo anything 3 seconds or less is good enough but im a pytoddler

How do you handle the scoring with Dijkstra? I'm thinking of an example that has a crossroads. When you approach the tile, there's no guarantee if you'll turn or keep going straight, but if you just store it as a series of nodes there's no sense of "turning"
Using this as a sample >>103539720
>Approaching from the west, heading east
Would be no turn, only +1
>Approaching from the west, heading south
Turn, +1001
>Approaching from the north, heading south
No turn, +1

I don't get how you store this on a node by node basis because in this sample going from the middle node south can have a different score depending on where you came from, but that'd mean storing an extra node back worth of information. Do you just check the last two nodes instead of the last 1 node?

>>103543107
Forgot to add,

previous

stores the shortest previous nodes, and

path_len

is just getting the distance between the current and previous node from the graph.

>>103543157
instead of using nodes as (X,Y), consider (X,Y,face).
if approached from different direction, you are on a technically different node

>>103543157
A node in Dijkstra doesn't have to be a (y, x) coordinate. It can be a (y, x, dir) triple.

So (4, 7, N) is adjacent to (4, 7, E) and (4, 7, W) with distances of 1000 each. N E S W can just be numbers 0 1 2 3.

>>103543157
Don't move on turns.
Your state key is basically current x, y and your vector and your cost is well, the cost.
At each junction you just push a counter clockwise and clockwise rotation (+1000 cost) and one step forward (+1).
Your base case is wall (prune) or finding the E.

Use a hashmap for your distance map and a minheap for the frontier. Part2 is a bit hairy, but idk if you're at that point.

>>103543157
>I don't get how you store this on a node by node basis because in this sample going from the middle node south can have a different score depending on where you came from

The beauty of Dijkstra's algo is that you don't need to store this.

With Dijkstra's algorithm, if we process nodes in strict order of current cost (guaranteed if using a heap), then the FIRST time we visit a node is GUARANTEED to be the cheapest possible path to that node.

>>103543157
Yet another person filtered by >>103542674

>>103539342
>ran poster and python user
BASED ** 2

>>103543203
that doesnt help you with part 2 though, as you could visit it again later with the same cost

>>103543205
He's right thoughbeit. People forget the "node" can be virtual as long as it carries the necessary state. I used Dijkstra's for the Wizard problem in 2015 as well and it literally just works.

>>103543155
I'm doing C++ this year and going for highly optimized solutions. Hence the bugs :)
Did a small optimization in my cost calculation, and brought the time down to 46ms. Might still be some room for improvement, but now day 14 is a bigger problem with 133ms.

>>103542239
game jams come to mind

>>103543203
There could be a south->north path that's lower cost than a west->east path at that physical location, but has more turns and ends up more expensive than the west->east path. You'd never find the shortest path if you treat each location as a node. You have to be more abstract with what you consider a node to be.

>>103543219
Did you do this?
>>103542035

>>103543217
>People forget the "node" can be virtual as long as it carries the necessary state
people dont understand algorithms at all, they just mindlessly copypaste it

>>103543214
For most advents you don't need the path mapping in Dijkstra, just the cost. for part2 you can tweak the pathing storage to work for part2. Worst case (which seems to never happen) you can pop more off the heap if they're same cost and at End if it was possible to reach End with the same cost from different states.

>>103542602
imagine if you weren't awarded any starts today

File: qman.jpg (58 KB, 525x503)

58 KB JPG

>>103542983
Better safe that sorry.
Anyway I have being doing my own research and it seems that language is popular among certain population that is commonly associated with child abuse.
I will do what I can contacting my representative to bring some attention to this issue. Hopefully we can ban that language as part of the Project 2025.

>>103543232
Obviously you need to consider turns and forward advances as separate nodes.

>>103543214
It helps if you use a bidirectional dijkstra for part two.

>>103543254
>It helps if you use a bidirectional dijkstra for part two.
whats the point when you can do it with one

File: 4way.png (9 KB, 880x839)

9 KB PNG

>>103543203

>>103543259
double dijks saves you the trouble of needing to track or save paths

I don't get it, what's all this arguing about? it's just dijkstra but you append new shortest paths found instead of replacing the previous one, then you go backwards from the end node

>>103543254
>Obviously you need to consider turns and forward advances as separate nodes

Clearly that's not obvious since the whole issue with >>103543157 stemmed from confusing physical locations with nodes.

>>103543274
tracking paths saves you the trouble of pathfinding multiple times

>>103543236
No I counted the number of adjacent robots in every frame, and the image has a much higher count than all the others. I just did the counting in a really dumb way by iterating over the entire grid. Just updated that to just look at the robots. It is now down to 38 ms.

* Day01 0.305ms
* Day02 0.737ms
* Day03 0.247ms
* Day04 0.945ms
* Day05 1.185ms
* Day06 2.104ms
* Day07 1.517ms
* Day08 0.063ms
* Day09 0.492ms
* Day10 1.943ms
* Day11 6.254ms
* Day12 0.718ms
* Day13 0.748ms
* Day14 38.576ms
* Day15 1.516ms
* Day16 48.505ms

>>103543260
It doesn't happen in this problem on any input I've seen, but if it does, just keep a sentinel that's basically costmax = INT_MAX.

When you reach End, set costmax = cost and then keep popping the heap til your cost is no longer equal to or less than costmax.
It's an abuse, but it should guarantee you get all same (LOWEST) cost paths to E.

>>103543274
>doing [complex thing] saves you the trouble of [simple thing]

If you do dijkstra and want to save your min path(s) just store the min prior node(s).

>>103543280
You'd think, but at least when I tried both methods, my double dijk was about 10x as fast. Maybe my implementation was bad though.

For path map, you just do -> hashmap(node, list node)
It's really not that complex. You can use a simple stack to visit all the paths to origin...
Idk why you niggas using double dijks or whatever the fuck. Obviously the list of old nodes must have the same cost reaching the node you mapped it to.

If your cost visiting node is less, clear the list before adding the current node you're on.... Again, real easy.

>>103543282
Do that but instead of doing 10403 steps over two axes do 101 steps over 1 axis and 103 steps over the other.

>>103543354
Bigboy time?

it's over

starting to filter myself due to sheer unwillingness to do another AoC pathfinding puzzle
send help

>>103543381
Idfk. If I had to optimize it, I'd just use a fixed 4 space array since the same cost can only be coming from different vectors, but I didn't bother because I don't care.

>>103543396
Just copy code from previous puzzles. Less than half the lines in my solution were original.

>>103543108
>>103543102
welp good point... tyty both

>>103543124
>you have to use a different algorithm if the number of paths is that large
is there any good method aside from the double-dijkstra one?

Played catchup on the weekend's at work today. Saturday's was pretty easy, the Christmas tree part was a bit annoying since you have to either make assumptions or watch through thousands of outputs, I just assumed that the output from the first 10,000 that minimizes the number of robots with no adjacent robots would be the best, and it ended up working
Sunday's annoys me because I had a very clean and clever recursive solution but had to write a way to view the map each iteration to find a miniscule bug (I had a set of boxes, when a box is moved up, it is removed from the set and the box with the new position is added to the set. Problem is if you add a box that is already in the set then that box will be removed when it is supposed to stay)
Didn't start writing today's but it seems like simple uniform cost search should do the trick

>>103543473
for an exhaustive search you can just dfs, the problem with bfs is only that it uses too much memory to expand every path at the same time

>>103543386
yo am I still in this if I hand my assignment in late or as soon as I miss an assignment by 24 hours I'm officially filtered?

>>103543371
Oh that sounds interesting. Going to think this over on the morrow.

File: 1702956462947922.png (2.56 MB, 868x3302)

2.56 MB PNG

Finally had time to wash my messy solution.

Benchmark 1: ../target/release/aoc-day16 /tmp/bigboy.txt
  Time (mean ± σ):      1.129 s ±  0.009 s    [User: 1.050 s, System: 0.072 s]
  Range (min … max):    1.115 s …  1.140 s    10 runs

nobody on /g/ knows what Djikstra's algorithm is huh

>>103543808
I'm guessing "aoc_utils" is an external library? If so, that's probably cheating

>>103543606
>yo am I still in this if I hand my assignment in late
yes

>>103538057
Looks good

>>103543852
>organizing and reusing your code is cheating

>>103543852
it's my own local crate, I'm not going to redefine Point2D or rewrite the code to open the input file every day

>>103544046
I think I wrote
>return i >= 0 and j >= 0 and i < arr.length and j < arr[0].length
at least 5 times now

>>103543852
Formally or informally, everyone has their own utils library. Or do you write another grid-reading algorithm every day?

>>103544100
I write grid = np.array([[*l] for l in open("input.txt").read().splitlines()]) from scratch every day

>>103543606
The filter is dropout cope. If you solved the puzzles you're in.

>>103543606
There is no cash prize. You're doing this for fun. You're an adult, you get to decide for yourself whether you're "still in it" and who else is "still in it" from your perspective.

>>103544112
>np
cheater

>>103543606
24 hours = filtered

>>103543371
Oh shit this works. Set ans2 to xr and add width until it equals yr mod height. Where xr and yr are the indices of the steps with suspiciously clustered values. You only need to simulate 102 steps.

my broot part 1 is still running guys give me a minute.

>>103544176
Basketball rules, you dodge the filter if you ran your code before 24hr.

>>103544175
>add width until it equals yr mod height
https://en.wikipedia.org/wiki/Chinese_remainder_theorem

>>103544191
>not brooting your congruences

ishygddt

Are there any youtubers who explain this stuff well? Not livestream/speedrunner shit but explaining the most efficient solution.

File: day16_fast.png (319 KB, 943x2757)

319 KB PNG

finally a fast solution. this was such a pain...
>>103536112

 time ./target/release/aoc_2024 < ./bigboys/l64q3v.txt
day16 result:(800196, 2367)
./target/release/aoc_2024 < ./bigboys/l64q3v.txt  0.11s user 0.01s system 89% cpu 0.130 total

File: aoc_2024_16.png (106 KB, 1024x1218)

106 KB PNG

Perl. I should try to store sets of paths of optimal lengths to each visited point instead of brute forcing p. 2, but it is good enough for today.

>>103544280
sub 1 ms for regular input

wait, people on /g/ are unironically using rust now?

>>103544112
>import numpy

>>103544280
Nice
>hash map and hash set for x,y,r tuples
What if you use an array instead?

File: Screenshot AoC 16-1.jpg (500 KB, 1776x2147)

500 KB JPG

> Wake up, open puzzle.
I'm not writing a maze solver again.
> Manually color in spreadsheet cells and prune passages for five hours.
> Got silver star, fuck part 2.

>>103544504
>anime girl as the background
Either you're a coomer and that's your waifu or you're a tranny

>>103544504
based

>>103544504
that IDOL song gets stuck in my head whenever I see Ai Hoshino

>>103544516
>doesn't know oshi no ko
anime website

>>103544609
troon confirmed

File: cd15c7b99af219c95df5c5847(...).jpg (48 KB, 749x565)

48 KB JPG

>>103544609
I know this is an anime website, but
A) not many people, even on 4chan, would go out of their way to set their spreadsheet software's background as an anime waifu, and
B) do you expect me to know every SOL anime? Only anime I watch are shounen like dragon ball and the occasional "2deep4me" shit like steinsgate

>>103543606
>as soon as I miss an assignment by 24 hours I'm officially filtered?
Yes

>>103544609
>2020
That was the last year I consumed any weebshit desu

File: would have posted another(...).png (5 KB, 312x155)

5 KB PNG

>>103544631
Oh and speaking of "2deep4me", I need to watch lain some time but I'm too lazy to get around to it

File: welfin-2.png (583 KB, 921x620)

583 KB PNG

>>103544653
watched hunter with my kids last week or two and just started trigun
I forgot how good that shit can be sometimes

>>103544755
those are good animes not tranimes like posted above

File: carbon(34).png (315 KB, 943x2719)

315 KB PNG

>>103544466
actually sped it up a tiny bit. about 110 ms now

Small boy:
Silver 3007
Gold 17

######
#....#
#..#.#
#S.#E#
#..#.#
#....#
######

>>103544815
idgi
Is there some way of doing it that blows up here?

>>103544815
Impossible boy:
Silver undefined
Gold undefined

#######
#S.#.E#
#######

>>103544838
The official inputs are formatted to make it easier, so there are fewer "corner" cases, this one is not.

>using networkx
you didn't beat aoc

>>103544815
i dont understand how this could cause problems for anyone

File: file.png (1 KB, 163x20)

1 KB PNG

>>103544838
only if your code is retarded

>>103543135
>Is 326ms anywhere near reasonable for this problem?
My solution takes 70 seconds and I'm not going to do anything to improve it

>>103543135
My machine is 9 years old and it takes 20ms, but I am coding in C++, not Python.

>>103544988
That is total time BTW, everything included.

>>103544988
Is 10ms after commenting out the code that prints the maze to screen.

>>103544875
I've written Dijkstra's algorithm a dozen times
I could again
I simply choose not to

File: comparison.png (320 KB, 1461x1653)

320 KB PNG

More people have been filtered this year than last year. Both screenshots from ~8:00PM Eastern on Dec. 16th of the respective year.

>>103545076
probably due to the influx of "coders" who make apps with ai prompts

>>103545076
Advent of Grids. I'd guess a lot of people got bored.

>>103545076
damn, what happen? I remember last year being harder

How come none of the search problems ever require a heuristic, I feel that'd be more fun

>>103545087
>I remember last year being harder
Maybe you just got better at coding. You should ask for a raise.

>>103545083
Just get better libraries, one that turns those grids into a proper directed graph. You only need to provide a lambda to calculate edge costs and call one of many functions available that do the job for you. EZ AF.
Of course you can reinvent the wheel if you are into that.

>>103545083
I only noticed now that excluding day 2, every single even-numbered day has been a grid problem. Wild

>>103545141
Don't forget day 15.

File: lisp.png (15 KB, 636x136)

15 KB PNG

>>103544875
Lisp, simple as that.

File: loli-sunglasses.png (813 KB, 899x899)

813 KB PNG

cycle detection today

>>103545122
I already get 200K making node.js webshit

You have never used Dijkstra's algorithm to solve a real problem and you'll likely never will.

>>103545185
biittch you ameri-jeets have it good. thats like a million leaf clown bucks

>>103545188
just used it to calculate the cost of getting my dick into your mom's pussy ($0)

>>103545208
jokes on you retard. with no cost thats just regular BFS

>>103545188
How many "real problems" are you solving by posting on 4chan buddy

>>103545126
its lame still, when i see a grid i skip the day

yeah I don't think I'll be back in time for today, good luck anons

>>103545031
>today was simply too easy, that's why I needed someone else's code to solve it

>>103545250
NTA, but I decided pretty much my entire career path based on 4chan posts and it turned out pretty good and I also found true love on here

completely filtered on silver of a boring and trivial problem that I've solved a dozen times already in prior puzzles, and for which I have 99% applicable code from last year, and while passing the examples but not the input.
Thanks Eric.