I gotta find another solution
#AoC 2022 | Day 14 | Solutions & Spoilers
noble lava
quaint ocean
(why?)
ornate forge
you just want to make your part 1 faster?
noble lava
you just want to make your part 1 faster?
Yeah
ornate forge
did you try the thing I mentioned earlier? you don't have to simulate from the beginning every time
quaint ocean
You basically can't do it with an algorithmic change, it's a code optimisation you need
ornate forge
you can backtrack one step and simulate from there
noble lava
did you try the thing I mentioned earlier? you don't have to simulate from the b...
Yeah I'm trying to adopt that strategy now
dire meadow
i think simulating from one step above might work
no, it won't, pits can be deep
you have to backtrack as far as a pit in the middle could be
ornate forge
no, you only have to backtrack one step at most
nothing changed above the sand you just placed
quaint ocean
I think he means working backwards from p2
ornate forge
the next sand will follow the same path up until that point
ornate forge
I think he means working backwards from p2
dire meadow
yes, working backwards from p2
quaint ocean
I'm like 90% sure it's impossible but I don't know how to prove that
noble lava
I thought @ornate forge meant that when you place a sand grain then you can start simulating from the last recorded position of that last grain
quaint ocean
You can
noble lava
I'm like 90% sure it's impossible but I don't know how to prove that
I'm also sure it's impossible to work from p2
quaint ocean
Salt's talking about something else
quaint ocean
I thought <@133944101929222144> meant that when you place a sand grain then you ...
Whenever you successfully land a grain, you can remember the last position. The next grain is guaranteed to fall to at least there
golden pier
looks pretty cool tho
quaint ocean
You might need a stack actually
dire meadow
i mean line-by-line does work
ornate forge
welp, the line based one is faster but gives me the wrong answer
quaint ocean
welp, the line based one is faster but gives me the wrong answer
I can improve on it even further: part_one = part_two = lambda *i: 0
Now you can get the wrong answer even faster 🙃
ornate forge
I bet it will be even faster ported to rust
quaint ocean
True
dire meadow
ported to nim
quaint ocean
I bet it will be even faster ported to rust
#include <sys/syscall.h>
.globl _start
_start:
mov $SYS_exit,%eax
xor %edi,%edi
syscall
Fastest version
quaint ocean
This looks like Powder Toy
quaint ocean
Fair
dire meadow
they're really fun to implement though
i create a separate task for each particle in my implementation --- but the particles can put themselves to sleep if they don't change
quaint ocean
Presumably you have some kind of particle update system, like Minecraft block updates?
dire meadow
i dunno how minecraft updates
quaint ocean
I'm not too familiar with the internals but I know that most updates are done via block updates
I.E. when a block changes (e.g. being placed/destroyed) it tells its neighbours to update
(e.g. to break or fall)
golden pier
like when there's unsuported sand from world gen but it doesn't fall until you update it
quaint ocean
Or the entire category of contraption that is block update detectors
still slightly mad they just turned that into a block, BUDs were cool
dire meadow
oh, particles will wake up neighbors when they update -- in case the neighbors were sleeping -- but other than that tasks are just executed in whatever order asyncio decides
quaint ocean
Yeah that's what I meant
golden pier
oh, particles will wake up neighbors when they update -- in case the neighbors w...
is it open source so we can check it out?
noble lava
i mean line-by-line does work
This is also what I did for part 2 and it works great
ornate forge
neat, I ported my rust code to python and it's instant on part 1
ignoring the parsing it's <1ms
with parsing and everything 3.5ms
0.023s for part 2
faster than I expected from python
noble lava
0.023s for part 2
I did it faster 😛
But I suck in the first part, I probably did backtracking the wrong way
noble lava
I just kept a list with the positions that the grains had. I append a position when I move the grain and I pop a position when I place a grain
ornate forge
yes
noble lava
dammit pyright
Yeah i feel you lol
ornate forge
res = 0
stack = [(500, 0)]
while stack:
x, y = stack[-1]
if not grid[y + 1][x]:
stack.append((x, y + 1))
elif not grid[y + 1][x - 1]:
stack.append((x - 1, y + 1))
elif not grid[y + 1][x + 1]:
stack.append((x + 1, y + 1))
else:
res += 1
grid[y][x] = True
stack.pop()
part 2 takes 0.005
ornate forge
wait
this is part 2
let me fix
there
res = 0
stack = [(500, 0)]
while True:
x, y = stack[-1]
if y >= max_y - 1:
break
if not grid[y + 1][x]:
stack.append((x, y + 1))
elif not grid[y + 1][x - 1]:
stack.append((x - 1, y + 1))
elif not grid[y + 1][x + 1]:
stack.append((x + 1, y + 1))
else:
res += 1
grid[y][x] = True
stack.pop()
where grid is a 1000 x something grid of booleans
True if occupied
the nice thing about this code is that the same code with a very small change solves both quickly
noble lava
def main(input):
cave, max = parse_cave(input)
max = max + 2
step=1
count=0
current:set[int]={500}
while step<=max:
attempt:set[int]=set()
count+=len(current)
for x in current:
attempt.add(x)
attempt.add(x-1)
attempt.add(x+1)
if step in cave:
attempt.difference_update(cave[step])
current=attempt
step+=1
return count```
This is the main for my part 2. parse_cave gives the y of the lowest rock, and it gives a dict which associates a y with the various xs that are occupiedcave:dict[int,list[int]]
cave is something like {6:[496,497,498,502]}
ornate forge
the set stuff would look so neat with C++ bitsets
attempt = current << 1 | current | current >> 1
noble lava
```python
def main(input):
cave, max = parse_cave(input)
max = max + 2
...
I really like this solution, I think it's a smart algo
Alex: [ 0.003729 ] [ 0.005533 ]
Winners: [ Alex ] [ Alex ]```
I'm finally satisfied with the times I getI can go to sleep now
noble lava
``` Day 14: [ PART 1 ] [ PART 2 ]
Alex: [ 0.003729 ] [ 0.0055...
Parsing is included
ornate forge
parsing is probably the majority of time on p1
noble lava
Yeah, also my parsing function looks like shit
ornate forge
parsing in a nutshell
noble lava
lol
ornate forge
I cheat and use my util to read all ints from the input
makes life a bunch easier
or, all ints in a line of input
newlines actually matter a lot here
bitter pond
[y,x][bool(x)]
lol
bitter pond
I suppose if you want to allow other False values you'd need the is not None in there.
ornate forge
ok, finally got a good impl of the lines based part 2 in rust
bitter pond
x = 0
[y,x][x is not None]
You're already optimizing stuff for tonight? You're way ahead of the game. 🙂
shrewd bobcat
do you guys deal with resizing the grid or just start out with a huge map
haughty juniper
why even have a grid
bitter pond
do you guys deal with resizing the grid or just start out with a huge map
neither, just populated a set
haughty juniper
set gang
bitter pond
do you guys deal with resizing the grid or just start out with a huge map
board = set()
for row in [[eval(s) for s in line.split(' -> ')] for line in aocdata.splitlines()]:
for (x,y),(i,j) in zip(row,row[1:]):
board.update((a,y) for a in range(x,i+1) or range(i+1,x))
board.update((x,b) for b in range(j,y+1) or range(y,j+1))
probably
board = {(l,m)
for row in [[eval(s) for s in line.split(' -> ')] for line in aocdata.splitlines()]
for (x,y),(i,j) in zip(row,row[1:])
for l,m in {(a,y) for a in range(x,i+1) or range(i+1,x)}|{(x,b) for b in range(j,y+1) or range(y,j+1)}}
steep mist
jesus that's a lot of comprehension in one line
bitter pond
jesus that's a lot of comprehension in one line
but it works... 🙂
steep mist
that's actually really smart
haughty juniper
let's steal it for golf 😈
bitter pond
note my actual code has the update() version, not the single comprehension.
steep mist
I usually go for a long comprehension if I see it but I couldn't see a way to do the ranges without if statements
bitter pond
yeah, finding range() or range() worked was a feels good moment
bitter pond
the rest of my code was a bit more boring I'm afraid.
# drop some sand
for c in range(H*R):
a,b = (500,0)
while (a,b) not in board:
if (a, b+1) not in board: a,b = (a, b+1)
elif (a-1,b+1) not in board: a,b = (a-1,b+1)
elif (a+1,b+1) not in board: a,b = (a+1,b+1)
else: board.add((a,b))
if b>=H:
print(c);H*=H
if b==0:
print(c+1);
break
i wonder how feasible it would be for python to use bitwise nots as a set complement operator
steep mist
let's steal it for golf 😈
maybe there's enough fors there that we can finally implement the eval("".replace('@',' for ')) optimization
haughty juniper
obviously you wouldn't be able to iterate over it
but membership, union, intersect, etc would all be possible
steep mist
what would be the universal set tho
haughty juniper
maybe there's enough fors there that we can finally implement the eval("".replac...
🤔
haughty juniper
what would be the universal set tho
complement of empty?
_ in ~{} would always be true
or wait that's a dict
but you get the point
maybe i'll do something like this in my own lang
bitter pond
Is there a cool way to use match/case here? I tried it and it ended up just being a slow if/elif block. But maybe I missed something match can do?
while True:
sand = (500,0)
while True:
match sand:
case (a,b) if (a,b+1) not in board:
sand = (a,b+1)
case (a,b) if (a-1,b+1) not in board:
sand = (a-1,b+1)
case (a,b) if (a+1,b+1) not in board:
sand = (a+1,b+1)
case _:
c+=1
board.add(sand)
break
?
haughty juniper
actually maybe it's a mobile thing
bitter pond
the indentation isn't the question.
haughty juniper
looks like the while was indented
winter skiff
Is there a cool way to use match/case here? I tried it and it ended up just bein...
Apparently if you're using if in a match you're already doing it wrong 😄
bitter pond
it works, it's just slower than if/elif
haughty juniper
Apparently if you're using `if` in a match you're already doing it wrong 😄
agreed
there's no point if you're just going to use conditionals anyways
bitter pond
Apparently if you're using `if` in a match you're already doing it wrong 😄
which is why I swapped to if/elif, the question remains though, is there something match provides that would be a good choice here?
haughty juniper
not really
bitter pond
conditionals aren't bad, but if every case is a conditional you haven't gained anything.
ornate forge
which is why I swapped to if/elif, the question remains though, is there somethi...
for else 😛
haughty juniper
do it to flex on the <= 3.9 nerds
winter skiff
Nothing I'm aware of. patma is more about the shape of things than literal values.
steep mist
I had a cool next(s + d for d in (1j,-1+1j, 1+1j) if s + d not in block_set) approach but I had to scrap that because next() was too slow
ornate forge
#
a, b = sand
for p in ((a, b+1), (a-1, b+1), (a+1, b+1):
if p not in board:
sand = p
break
else:
c+=1
board.add(sand)
break
surprising that it was too slow.
I wonder if a queue approach that just flood fills might be better? for any sand you always add the 3 beneath it if they're not already there.
ornate forge
that's basically the line based thing people have discussed
haughty juniper
I wonder if a queue approach that just flood fills might be better? for any sand...
take that further and add the whole triangle
deep wave
take that further and add the whole triangle
cavity
brazen sorrel
I'm curious, did you all do anything smart except simulating it out? I can see a way of doing part 2 by just looking at the triangle underneath the start point and just counting how many spots would be filled
but my brute force is like 4.4 seconds on CPython and 1 second on pypy so didn't bother 😛
golden pier
I'm curious, did you all do anything smart except simulating it out? I can see a...
yup, salt-die did that
karmic blaze
@brazen sorrel
brazen sorrel
... and I just realize that the board is not big enough to warrant me not just creating a grid which would probably make this all a lot faster
basically DFS I am assuming?
lmao now that I say it out loud the problem even hinted at pathfinding
goddammit lol
karmic blaze
if you store the path the sand falls down you can just go 1 step up after setting the sand down
brazen sorrel
yeah it basically just seems like a DFS
you're describing the "backtracking" part
but yeah I guess you can structure it more nicely because of the restriction, I see what you're saying
cool, not gonna bother implementing it klol
severe folio
... and I just realize that the board is not big enough to warrant me not just c...
yeah i feel like so far this years aoc hasnt been as harsh on naive solutions as it has been in the past
brazen sorrel
Yeah mostly been able to brute force
With the exception of that LCM the other day but pretty trivial change
severe folio
haha definitely trivial (it did not take me two hours)
fathom stump
i think my solution for part 2 is correct but its incredibly inefficient for the large input, it was running for about half an hour and still didnt return
# counts rest sand units until overflow, with infinitely wider ground
def simulate_p2(self):
sand_units = 0
while True: # void
curr_pos = self.start
self.sand.append(curr_pos)
left = (curr_pos[0] - 1, curr_pos[1] + 1)
middle = (curr_pos[0], curr_pos[1] + 1)
right = (curr_pos[0] + 1, curr_pos[1] + 1)
if all(x in self.sand for x in [left,middle,right]): # overflow
return sand_units + 1
while True:
for dx, dy in self.directions:
next_pos = (curr_pos[0] + dx, curr_pos[1] + dy)
if not any(next_pos in pos for pos in [self.rocks, self.sand]):
curr_pos = next_pos
self.sand[sand_units] = curr_pos
break
else: # rest
self.sand[sand_units] = curr_pos
sand_units += 1
break
if (curr_pos[1] >= self.height): # floor
self.sand[sand_units] = curr_pos
sand_units += 1
break
# self.visualize()
# sleep(0.1)
;-;
quaint ocean
Don't use a list
At least use a set
Using a set would probably optimise your code enough, it gets rid of a linear search you're seeing every single simulation step
low hare
My part 1 was initially incredibly wasteful as I simulated each grain of sand starting from the source each time
Thank god I fixed that before moving to Part 2 or I would have been super screwed for that
as it was, my part 2 does spit out a result ... in 3 minutes XD
fathom stump
Using a set would probably optimise your code enough, it gets rid of a linear se...
ýeah i figured that, and removed some for loops, takes a bit but much better, thanks!
fathom stump
as it was, my part 2 does spit out a result ... in 3 minutes XD
at least im not alone xD
starting now day 15, and im scared
fathom stump
ahahahahhaha same
fathom stump
i did a visualizer but it would take days for it to render on the actual input
but works well with the example
low hare
i did a visualizer but it would take days for it to render on the actual input
i do have a print out of the actual input with the floor
takes a good few minutes to spit out but it's there
fathom stump
my "floor" isnt there in the actual print out but it is in the logic, so it works
low hare
this is the bottom part of my input with the floor
dire meadow
looks amazing
i used a scroll view to show everything in the terminal
dire meadow
fathom stump
cause it was O(n^2) for each frame
dire meadow
oh, i had to slow down the animation on purpose
fathom stump
jeez thats awesome
dire meadow
thanks
velvet storm
I've got part A done, and my tests are passing for part B...
well, test
but I'm over shooting on the final answer :/
my modification to how i'm generating the rock space doesn't seem to change anything on the small scale
i am perplexed...
is there somewhere people share extra test inputs?
golden pier
is there somewhere people share extra test inputs?
well, you are discouraged to share your inputs
velvet storm
:nods: I was wondering if someone had made extra test cases
ok, i guess I was counting the final sand glob in a way that overshoots in the real case, but not the test case
oh, no, i wasn't, i just have shit eyes
neon shell
How did you capture the animation?
I just printed to the terminal, which needs to run quite slowly to avoid excessive flicker, but it's rather meditative to watch 🙂
dire meadow
How did you capture the animation?
I just printed to the terminal, which needs ...
i don't clear screen between frames, i move the cursor to a spot that needs to change and change it
primal abyss
How do u do that kind of animation without clearing the screen?
fallow oar
How do u do that kind of animation without clearing the screen?
There are libraries that'll do that kind of thing like curses, but any library that does that relies on ANSI escape codes, which are special characters that when printed to the terminal, most modern terminals will interpret as things like color text, cursor movement, or changing the cursor style (flashing, invisible, etc).