about 45mins

Any bets on what's going to attack next?

shark

20mins

the polymer construction is going to malfunction and we are going to be "attacked" by water pressure is my guess

@emanresuA Giant underwater anime girls

I bet the engines are clogged up

I guess that would be no stranger than crab submarines, a single crab shuffling hundreds of thousands of cups around, or bugs spreading in folded space

(that is 2021 day 7, 2020 day 23 part 2, 2019 day 24 part 2)

CMQ: Is caffeine good for AoC?

4m

> Is caffeine good?

ftfy

never use caffeine in general

but it's very helpful to some programmers

for example that one person who golfs in malbolge

@Razetime (is this a directive or "I never ..."?)

3m

It was intended as "I never.."

but yeah it's also good as a directive

2.5m

Gotta say this year's ASCII art isn't looking too nice right now

Galactic colon

Agreed

lmao

looks like a huge cliff face

2m

galactic endoplasmic reticulum

1.25m

1m

1m

1m, glhf

1m, glag

*glhf

gulag

gulag

.5m

1/2m

good luck, add gold

1/4m

*achieve gold

Is this one A* or something?

I don't know this :(

neither do I

Ugh I'm betting there's going to be a path that doubles back

Also betting these are explicitly designed so the goto cheapest approach won't work

even the sample input doesn't work with goto cheapest

It's Dijkstra, and exactly a PE problem lol

89 people have finished p1

dijkstra or floyd warshall?

good question

Hopefully this works

whatever the fuck i've written works on the sample but is very slow on the real input

as in hasn't terminated yet

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 15   00:04:02    42     59   00:07:09     6     95

i think it also tries literally every path that only goes right or down so yeah no shit it can't perform lmao

damn, it took me a long time to remember how to do dijkstra

@UnrelatedString wait if that were guaranteed to be valid that'd be so much faster

wdym that can't perform lol

lmao

i mean mine tries fucking all of them

actually wait not that should be fine

literally just dp

there may be some other problem in my code then lmao

it hasn't given me a wrong answer because it hasn't given me an answer

rip

Project Euler has literally three versions of such pathfinding problems, where going in two/three/four directions are allowed respectively

lol

see i immediately recognized the necessary algorithm and then just uh

forgot how to implement it

like when i thought "dijkstra" i was like, hm do I need a DSU?

but no that's kruskal and i'm just rusty

good news though, +21 pts relative to ecner

i haven't implemented dijkstra's algorithm since the last time there was pathfinding on aoc

What's P2

Actually optimal dijkstra requires a niche data structure but a simple priority queue is fine for most purposes

l a r g e

(p2 requires a bit of preprocessing and then it's just p1 but 25x larger)

Mine's taking ages

@Bubbler oh, really?

duh what

And it probably won't work

Ugh I don't know A* or djikstra

This is garbage

A* won't work

i think

isn't it a heuristic not guaranteed to be optimal?

So...the sol is just "know some stuoud algo"?!?!?!

idk probably? i don't see any way other than dijkstra's to solve this

But really, the core of dijkstra is a BFS but you pick the next node with lowest cost

ALGOL programmers gonna be really happy today

@Bubbler ^. I'd argue BFS is just a special case of dijkstra where you get to take a shortcut because the weights are identical

Djikstra's seems suprisingly close to my initial idea

to be fair to wastl, dijkstra is... a pretty commonly used and well known algorithm; it's not at all niche or obscure and it's like, probably the most versatile

But this is stiull utter garbage

like, if you don't know BFS, you can just dijkstra

the only reason to BFS is because it's easier to write (and maybe faster?) when it works

A cheap way to keep track of neighbors and pick the lowest cost is to use a treemap

Sorry JS and Python

Well, running what is possibly djikstra's

So far it's taken 30s

wtf is a treemap

Thankfully I took a class on data structures (including graphs) only a few weeks ago ...

ಠ_ಠ djikstra's is wrong

Anyway, done 627/328

Is djikstra's supposed to go row by row...

I hate this

My part 1 algorithm took a measurable few seconds on part 2

I'm doing awful not because I'm a bad programmer, but because I haven't read about soem random algo somewhere

This sucks

And the only data structures I used were 2D lists

Oh eait

My code only worked for one-digit numbers

well, actually dictionaries of lists, but the dictionaries only had integer keys so they could have been represented as 2D lists

There are no two-digit numbers

(not in this challenge, anyway)

My attemtped djikstra's is just going row by row :/

There we go

I don't think it's supposed to do that

I implemented something which might have been a fancy graph-finding algorithm, but don't remember what it's called

I mean it turns out what I had written before was almost the exact same thing as djikstra's, but still...ugh

What even is this

Wrong :(

Fuck this

mine takes 0.924s on p2

probably my slowest so far

howww

I must be doing the alog wrong

i'd ask you to send the code but i suspect it's scattered chunks of expressions you typed into the console

can you explain your algorithm? i might be able to identify errors through that

Wait...am I supposed to set the value of the current cell I'm visiting, or its neighbors?

neighbors

fuwngiuwbvuibgvwiruvgsiu

Well, should work now

Looks pretty djikstra-y

Now I just gotta wait a year

Oh no it's gonna take ages on p2

I got p1 tho!!!

just tried using some random-ass heap thing in the python standard library and wow it just doesn't work

You don't need any fancy data structures for this

heapq?

yeah

...i also think i just realized what i fucked up trying to use it

but whatever

F

just heapq.heappop(x)

heapq.heappush(x, v)

Howww do you do this fasssttttt

i blindly reused shit from a completely different implementation of the algorithm lmao

i've implemented dijkstra like 20 times probably

My attempt at speeding it uo made it worse

I hate this

I put so much work into that

What do I even do

This isn't fun

:(

shall I give a lesson on dijkstra

which i have done like 5 times already

sure

i know i pulled this shit off in a previous year

and without heaps

My current approach is like...I have a 2d array for the value, and a dict for the unvisited spaces

Mapping the space to its value

idk what i was thinking with the dict

Dijkstra's Algorithm is a pathfinding algorithm that works for weighted graphs, both directed and not, and solves the Single Source Shortest Path (which gives the length of the shortest path to every node on the graph from a static starting point), which means it can be used to find the shortest path from A to B

wait yeah no i distinctly remember tracking neighbors directly what the fuck went wrong with that this time

i should probably convert this grid to an adjacency matrix

1679/1595 lmfao

first 4 digit rank in a week

I have p1, I just dont kbow how to make it fast enbough foir prrt 2

the idea behind DA is very similar to BFS - at its core, you maintain a priority queue of (node, cost) points (bubbler said there's a niche data structure that's more optimal but just use priority queue)

at each step, just like with BFS where you pop from your queue, with DA you just pop from your pqueue, getting the smallest item ordered by cost

essentially, at each step you go to the next cheapest point that you haven't visited

Hmm, maybe I should keep track of non-infinity points and only sort those

and then you just look at each neighbor and add it to the pqueue if it's not visited, and eventually you either empty your pqueue and have visited every node so you have the SSSP, or you arrive at your destination point

note that whereas with BFS it's optimal to add nodes to the visited set when you queue them, do not do that with DA, that will give you suboptimal results

you need to mark nodes as visited when you pop them off the PQ, and you should perform a visited check both when you pop and before you push

idk if javascript has a pq/heap lol. python has heapq

so basically we're doing a dijkstra with a 100 vertices

yeah

well actually 100 mil

well fuck

this may take forever in array language

ah

rip

hm, should i do video explanations for my solutions each day

i wonder if that would actually interest anyone

i'd see them

you are #4 on the leaderboard for an event with 100k participants (~40k actual participants) so i could see people being interested

true

i have gotten a shit ton of stars on my repo bc i'm the highest rated person with public solutions (or at least easily accessible public solutions)

lol nice

wait how did goffrie end up so far ahead of beta

they were apart by 5 points yesterday

wait, do I set my sights on overtaking beta too????

is that too ambitious??

do itttt

I set my sights on not jumpung off my roof in the next hour

This is awful

What do I even do

do you have any code you can send for me to check over?

Yes, but it's worse than no code at all in terms of readability

I just don't get how to make this fast

Should I implement that priority queue thingy?

Looks like a linked list might be the fastest way

Then again I don't know what a priority quee is IU'm just gyessing based off the name

pq works like such

you can insert elements arbitrarily

popping returns the smallest element

basically it maintains its order; O(log N) insert and pop

I think I can do that

you'd have to implement the heap data structure i think (maybe there's a workaround?)

I was thinking something like keep a linked list of the things where they're always in the right order, and to insert I just follow the list until I find the right spot to insert an item

Since I'd imagine most of it will be Infinitys for a while

that could work

it would definitely be slow compared to pq because it's O(N) insert but like

idk, you could try it

otherwise

you could do bellman ford i guess

That sounds scary so I'll try my idea first :p

bellman-ford is slower than dijkstra (but still fast enough for this) but its main use is that it works on negative edge weight graphs and can detect and report negative cycles

Wait I'd need all sorts of stuff like a doubly linked list for this to work, ugh (since I have to update the order whenever the neighbors get updated)

This isn't going to be fast enough

:(

Did anyone else do this in JS? How?

i didn;t update anything once it was on the heap and it worked fine; not sure if that can produce incorrect results because i stopped thinking about this the moment i got an answer but yeah

alright, guess I'll teach bellman-ford instead

given a list of verticies and a list of weighted edges, and a starting source vertex

begin by setting a distance list/map initially stating that the distance to every vertex is INF

and set the distance of the source to itself to 0

@UnrelatedString You won't get incorrect results if you make sure no nodes are processed twice

then, repeating (# of vertices) - 1 times

for each edge from U to V with weight W, if distance[U] + W < distance[V] then set distance[V] = distance[U] + W

then, at the end, you can just read off distance[desired destination]

this is O(|V| |E|) whereas dijkstra is O((|V| + |E|) log |V|)

I think I'm going to stick with djikstra and just try to optimize something

or you can do O(|V|^2) dijkstra with an array which would be far too slow here because that's on the order of 10 quadrillion

fibonacci heap dijkstra is O(|E| + |V| log |V|) but i have no idea what the fuck that is

is that the niche DS you were talking about @Bubbler?

It just makes me so mad that I didn't do well today because I don't have any formal CS education. It's like I'm being punished for figuring out what I know the hard way for the last six years.

Even if I was the best problem solver doing AoC, I just don't know some fairly common algorithm, so I lose

Yeah, fibonacci heap

It feels like one of those job interviews where you just implement a list of algorithms on a whiteboard or something

Instead of actual problem solving

Since the people who know the answer already do great, and the people who need to think it through suffer

Like...I know there's some amount of expectation that the people who will be competitive know various algorithms, but this adds nothing creative on top of that

my formal CS education taught me jack shit

i mean i learned how to do GUIs in java with netbeans drag-and-drop i guess

I actually know of a competitive programming site where the algorithms you need to learn at each level are very nicely laid out with example problems, but it's in Korean :/

it's cp that taught me everything that now gives me an advantage in aoc

solving contest problems is good practice tbh

Yeah, digging CP to moderate level can give you a lot of benefits

i'll continue to promote dmoj.ca; not affiliated with them in any way just has been really helpful for me cuz it has all sorts of CP problems from contests all over the world and other assorted problems

I'm torn between trying to do this now, or going to sleep

goto sleep;

I mean I probably could have run my slow original program in this amount of time

Instead of trying to do it the smart way

It's only 25x bigger

Oh wait

Well if you blew up time complexity without knowing it then you have no hope

Mine's a lot more than O(n) lol

yeah

Did like...everyone who did this know what a priority queue is and all that?

This seems super super niche

PQs aren't really niche (at least I think. maybe i'm wrong)

it's just "pathfind on a weighted graph"

so a good amount of people definitely would already know this

i don't like today's problem because it's too template

I feel like I'm also being punished for using js

No heaps or anything like that

I don't even know what a heap is honesrtly

This stuff rarely comes up in real programming, and in code golf I just brute force it :p

I'm :p'ing because as soon as I stop I'm going to cry :p

I hate this

I don't even know where to go

I guess I'll figure out what a prioerity ueu is?

honestly i recommend doing bellman ford

i could teach you how to implement a heap

but that sounds much more complicated

I'll try that I guess

Btw, I don't want it to seem like any of my frustration at this is directed toward you, you've been really helpful :)

oh, no worries, I totally understand :)

yeah having heapq feels like a huge advantage and javascript doesn't seem the best equipped for doing dijkstra. bellman ford should be fine tho but still :/

ok i found an adj matrix implementation for dijkstra but i feel it will take way too long on the input

why the fuck does [..."123"].map(parseInt) return [1, NaN, NaN]

but [..."123"].map(x => parseInt(x)) gives [1, 2, 3] as expected

lol

It's because of the i argument

The index

So it's using the wrong base for the others

LOL

right, forgor about that

i in map is both very useful and very annoying, but never both at once lol

hey why the fuck does for ... in ... give strings

Because it's meant for objects

oh right cuz object keys have to be strings

wait are you telling me

[1, 2, 3]["1"] will work

Yep

...

i hate this language so much :D

A lot of things treat array indices as strings, even

It's almost like that's the intended behavior, and they're just objects with extra properties

Since you can use an array exactly the same as an object

i mean that's one way of doing things

It's like the inventor of JS heard about the concept of OOP the day before it released, but only overheard a small snippet of the conversation, and pieced the rest together that night while incredibly sleep deprived

lmao

lmao

Is the |V| in Bellman-Ford the number of vertices?

yes

thanks

oh of course when you use arrays as keys they become comma separated strings

that's sane enough until you realize ["1,2", "3"] and ["1", "2,3"] become the same key

You could use a Map, but that just uses references to the arrays

ah

well that's disappointing

my implementation TLEs on TIO for p1 (full input)

wait how the fuck would bellman ford work i need to go ask the ppl who actually used it to solve today

10k vertices

Wait, for bellman-ford, should the edges include a copy in both directions?

around 40k edges

actually that should work in theory

@RedwolfPrograms yes

@hyper-neutrino Wait, why's it roughly 20k edges and not rougly 40k?

uh

because i'm stupid and forgot about directionality

lol no worries, that happened to my cat once

oh wait

bellman ford is O(|E| * iterations)

just that |V| - 1 for iterations will always work

but here you can do like just a bit over the side length

so i guess that's how you make it fast enough ¯\_(ツ)_/¯

sounds hacky to me but w/e

Wait how would this be fast enough

With 10k times 40k times 100 that's still a lot of iterations

And that's for p1

uh

not |V| * |E| * iterations

just |E| * iterations

Oh yeah

for p2 you get 1M * ~500 which is... slow but should eventually complete

even if it TLEs on TIO

my soln (which is admittedly probably quite inefficient) runs in just under 5s for p1

so for p2 2 minutes is... not absurd, i guess?? idk

wait my code's just taking ages to find the list of edges...

The console really needs a ctrl+c sorta thing

Wait this is fast for p1

:o maybe it'll work?

wait how do you do edges?

why is it slow lol

I was checking for dupes for some reason

oh

anyway here's my sol: tinyurl.com/2r6sf79b

probably not great lol

Okay, running it now. Wish me luck.

gl!

YES!

Ooh, and I'm still top 100!

Barely

nice!!

Day       Time  Rank  Score       Time  Rank  Score
 15   00:38:14  2629      0   02:15:37  4370      0

Well, not great, but at least I did it (and learned something new :p)

i should've gone for the bellman ford first :P

dijkstra is impossible without some sort of heap

Thanks for all the help, I would not have been able to do this without you

you're welcome :) glad you learned something from it lol

Anyway, I'm going to sleep lol

See y'all tomorrow o/

gn o/

i need to sleep soon i got 4 hours of sleep last night and idk how i'm still alive awake rn

tbf i got up late so i haven't been awake for that long and also i took a nap at 10 for like... some amount of time? i don't even know

heap implementation in JS

i'd be happy to explain what heaps are and how they work but this is a fine (i think) implementation of heaps (which are the underlying DS used for most priority queues)

oh another thing you could do for the bellman ford implementation

if no distances update in a cycle

you can exit early

alright my bellman ford works fine

pog

just exceeds heap size limit on the actual input

oh, rip

what lang are you using, bqn?

yep, bqn

i looked on the thread for other array langs

funny that dyalog had a builtin for this using tail recursion

woo part 1 done with a dumb hack

holy fuk part 2

yep...

yep

hm this is gonna take a while