#AoC 2022 | Day 12 | Solutions & Spoilers

1320 messages Β· Page 2 of 2 (latest)

knotty vale
#

Hehe

candid vortex
#

I can't see your response in my client

#

be my test subject for a bit while I debug, I'll delete the posts I make as i go

knotty vale
#

ok

candid vortex
#

ok apparently the client setup I had just broke, maybe using a different electron version just broke stuff

placid quail
#

how's it going?

candid vortex
#

try this case this

#

the output from your thing is weird

placid quail
#

ah

#

ok

#

so

#

that is because

#

it gets to the end

#

before that thing finishes

#

so if you replace the while loop with a for loop and do it 1000 times it's normal

merry scarab
#

there's probably better than run dijkstra for each 'a' elevation right ?

balmy bramble
#

Didn't really bother doing a more efficient thing for P2, was fast enough just iterating all possibilites:

from common import *

with open(infile('12.txt'), 'r') as f:
    text = f.read().strip()

grid, *_ = parse_block_grid(text, str)
grid = grid_to_dict(grid)

start = next((i, j) for i, j in grid if grid[i, j] == 'S')
end = next((i, j) for i, j in grid if grid[i, j] == 'E')

def dist_to_end(begin):
    d = deque()
    d.append((begin, 0))
    visited = set()
    while d:
        cur, ln = d.popleft()
        if cur in visited:
            continue
        if cur == end:
            return ln
        visited.add(cur)
        for nxt in neighbours(*cur):
            if nxt in grid:
                if grid[cur] == 'S' or ord(grid[nxt]) <= ord(grid[cur]) + 1:
                    d.append((nxt, ln+1))
    return float('inf')

def part1():
    return dist_to_end(start)

def part2():
    return min(dist_to_end(v) for v in grid if grid[v] == 'a')

print("Part 1:", part1())
print("Part 2:", part2())
merry scarab
#

@balmy bramblecould you define "fast enough"

balmy bramble
merry scarab
#

this doesn't look like dijkstra

balmy bramble
#

it's BFS

#

you don't need dijkstras

#

no weighted edges

merry scarab
#

but won't that get you the first path found ?

#

instead of the shortest one

balmy bramble
#

yes, in unweighted graph first path from BFS is shortest

#
  • kind of the point of a breadth first search πŸ˜…
#

all dijkstras does is emulate BFS but with the definition of "breadth" adjusted w.r.t weights

merry scarab
#

*sight* i'm an idiot

#

an idiot with a working djikstra algo, but still

balmy bramble
merry scarab
#

yeah, took me a lot of time for a mediocre result

#

T_T

#

I guess I've learn something at the very least

balmy bramble
#

the smarter thing here would be to do BFS starting at E and record the distance to every other node, then this becomes pretty fast, but I couldn't be bothered reorganizing code

#

just one pass that way

tacit forge
#

doing it that way I didn't even have to reorganise the way adjacent nodes are calculated

scenic bay
balmy bramble
candid vortex
#

it would have been nice if the input was bigger to actually force people to be a bit more clever for p2

balmy bramble
#

yeah It would have been nice to actually reverse the BFS direction, but I guess having too many as would make part 1 trivial because of too many paths

candid vortex
#

another missed opportunity for teaching a worthwhile lesson

candid vortex
scenic bay
#

On a slow laptop, but it's basically instant

novel plume
#

3.5s / 2.5s ☺️

balmy bramble
novel plume
#

yes. soo fast. πŸ˜…

candid vortex
#

2.5s?

scenic bay
balmy bramble
#

nice

candid vortex
#

~250us on my side, but I'm cheating by not using python πŸ˜›

scenic bay
# balmy bramble nice 
print('part1:', bfs(start,end))
print(f'part1 total: {perf_counter()-t1:0.6f}');t1 = perf_counter()
print('part2:', min(filter(None,(bfs(start,end) for start in heatmap if heatmap[start]==ord('a')))))
print(f'part2 total: {perf_counter()-t1:0.6f}')

look at that hacky part2. It's just that it's fast enough not to worry about making it better.

candid vortex
balmy bramble
#

why not just use a generator expression instead of doing a filter

candid vortex
#

I've realized we have different thresholds for fast enough πŸ˜›

balmy bramble
#

wouldn't that be faster

candid vortex
#

I try to keep under 1ms per day if possible

balmy bramble
candid vortex
#

(and 1s across all days, which was my target last year)

balmy bramble
#

I did everything in C last year

#

some of the days got... really annoying

candid vortex
#

I learned rust from scratch during AoC last year

balmy bramble
#

rust or scratch?

candid vortex
#

(and managed a total sum of times of <0.5s)

gloomy basin
#

c sounds like a pain for aoc

candid vortex
#

sounds kinda fun

candid vortex
#

what task so far actually require something fancy?

#

rather than just arrays or similar

scenic bay
#

Ok, so I tried passing all the starts and runing one bfs:

start: 0.000001
setup: 0.019679
part1: 412
part1 total: 0.010674
part2: 402
part2 total: 0.010168
#

so about 90 times faster.

candid vortex
#

helped a bit πŸ™‚

scenic bay
#

but 0.90s vs 0.01s is not that much of difference in raw value. πŸ™‚

candid vortex
#

(Eric is too kind to people with his input sizes)

scenic bay
#

*sometimes.

candid vortex
#

most of the time

scenic bay
#

This one felt right. If you did it wrong, it was impossible and would never complete, if you did it right, it was not bad at all.

candid vortex
#

(I would argue your bfs from all points isn't "right")

#

(but I'm pretentious about algos like that)

#

as said I think it's a missed opportunity to teach a nice lesson

#

about one to many bfs

scenic bay
#

it's only day 12, the lessons come next weekend. πŸ™‚

candid vortex
#

similar for the range problem we had that was easily bruteforcable

#

when there are nice lessons about interval math in there

#

I liked yesterday, it actually made me have to be creative to hit my time goals πŸ˜›

#

since running all 10000 iterations turned out too slow

#

"oh hey, you got stuck in a cycle, I can stop here and exploit this"

merry scarab
#

takes 4sec with n bfs instead of 20-30 with n djikstra

brisk ginkgo
#

I'm starting to think I got lucky with my Part 2... I stop looking after hitting the first a, but I've seen mention of people checking multiple paths :/

vast helm
#

if you're doing a breadth first, then the finding the first "a" sounds right

modest glacier
#

Or keep searching until you find the start to do both parts at once

scenic bay
merry scarab
#

@scenic bay that's because my bfs and dijkstra expect a fixed origin and destination

#

instead of looking for the first 'a' char

winged zodiac
#

4 seconds sounds really bad though

merry scarab
#

that's the next step I guess

#

well times 1 bfs * number of 'a' nodes

#

656 bfs to be precise

scenic bay
scenic bay
brisk ginkgo
#

Here we go:

def traverse_terrain(terrain: Terrain, source: Point, dest: Point, asc: bool = True) -> int:
    """Traverse a terrain.

    Can either go from low elevation to high (asc is True, default) or from
    high elevation to low (asc is False).

    Parameters
    ----------
    terrain : Terrain
        The terrain to traverse
    source : Point
        Source point
    dest : Point
        destination point, ignored if asc = False
    asc : bool, optional
        ascending (low to high) or not, by default True

    Returns
    -------
    int
        Number of steps to reach the destination.
    """
    visited: list[Point] = [source]
    heap: list[tuple[int, int, int]] = [(0,) + source]

    destination = dest if asc else "a"

    while heap:
        steps, y, x = heapq.heappop(heap)

        if (y, x) == destination or terrain[y][x] == destination:
            return steps

        for ox, oy in ((0, -1), (1, 0), (0, 1), (-1, 0)):
            dx = x + ox
            dy = y + oy

            if (dy, dx) in visited or not in_bounds(terrain, dx, dy):
                continue

            current_elevation = ord(terrain[y][x]) - 97
            next_elevation = ord(terrain[dy][dx]) - 97
            delta_elevation = next_elevation - current_elevation

            if not asc:
                delta_elevation *= -1

            if delta_elevation <= 1:
                heapq.heappush(heap, (steps + 1, dy, dx))
                visited.append((dy, dx))

    return 0

S and E are converted to a and z in terrain before being passed into this function. Their coords are held in start and dest. This function handles ascending and descending with the asc flag.

scenic bay
brisk ginkgo
#

no

#

it did earlier today but fixed that πŸ˜„

tacit forge
winged zodiac
balmy bramble
merry scarab
#

well seems like vs doesn't want to let me use the profiler with a cmake project so this is where I stop for tonight

#

tyvm for pointing out my mistakes

scenic bay
brisk ginkgo
#

Yeah I flip the sign on descent

scenic bay
#

no I mean while ascending you can go from r to s, or from r to c max 1 up, or unlimited down

#

and vice versa if going from z to a

brisk ginkgo
#

ah yeah

#

This code is 90% the same as I used for the cave puzzle from last year πŸ˜„

scenic bay
#

There we go, fast enough for me.

start: 0.000
setup: 0.019
part1: 412
part1 total: 0.010
part2: 402
part2 total: 0.013
scenic bay
#

Would have come in handy.

brisk ginkgo
#

I ought to take notes of what each day's puzzle is. Might help me in future.

#

I got lucky this time that I remembered a vaguely similar puzzle

candid vortex
#

my rust code is kinda boring, but short for being rust I guess

fn bfs(input: &[Vec<u8>], starts: Vec<Pt>, target: Pt) -> AocResult<i32> {
  let mut queue = VecDeque::new();
  queue.extend(starts.into_iter().map(|pt| (0, pt, b'a')));

  let mut visited = vec![vec![false; input[0].len()]; input.len()];

  while let Some(v) = queue.pop_front() {
    let (dist, cur, h) = v;

    for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
      let p = Pt::new(cur.x + dx, cur.y + dy);
      // In range?
      if let Some(new_h) = input
        .get(p.y as usize)
        .and_then(|row| row.get(p.x as usize))
      {
        // Valid height?
        if h >= new_h - 1 {
          // At target?
          if p == target {
            return Ok(dist + 1);
          }
          // Not previously visited?
          if !visited[p.y as usize][p.x as usize] {
            visited[p.y as usize][p.x as usize] = true;
            queue.push_back((dist + 1, p, *new_h));
          }
        }
      }
    }
  }

  aoc_error("No answer found")
}
winged zodiac
#

Pt is point?

candid vortex
#

(well, of course this isn't the whole code, but the parsing isn't interesting, and neither is the code that calls this for part 1 and 2)

#

right, just a dumb struct containing an x and an y

balmy bramble
#

I optimized my code to run in 0.4 seconds from 2.6 seconds

#

I only had to change one line

# 
python3 12.py

to

pypy3 12.py
candid vortex
#

lol

#

yeah, pypy is good at this kind of code

balmy bramble
#

why not jsut do one BFS starting from E

#

would probably be faster no?

candid vortex
balmy bramble
#

still

#

do BFS from E

candid vortex
#

for part 1 I pass the S, for part 2 I pass all the a's

balmy bramble
#

you will get distance to S for free

#

if you keep going

#

if you don't exit early BFS will give you shortest path from one node to every other node in the graph

#

that way you only need one bfs for both parts togteher

candid vortex
#

you could do that, but idk if making the code messier to shave a bit of time off is worth it

#

I'm already way under my target time

balmy bramble
#

don't think it woiuld be messier?

#

can you give me your full rust code I'll try do it

candid vortex
#

I'm already at 250us

merry scarab
#

ok I've found my weakness

#

I just went from debug -> release

#

it's all good now lol

candid vortex
#

you could probably get it closer to mid 100us

balmy bramble
brisk ginkgo
#

Anyone recommend a decent benchmarking lib? Timeit is an utter pain to work with the way i set up my AoC days

balmy bramble
#

how do you compile this?

#

right I'm stupid

merry scarab
#

~400ms for the ~600 bfs

balmy bramble
#

ah too much work to pukll it out, I give up

#

i am not very motivated

merry scarab
#

@brisk ginkgo I like line_profiler but it's more a profiler than a benchmark per say.

candid vortex
#

and run with the input file as a command line arg

#

it's currently set up to run day 12 like that

#

(and you can pass an integer after the file name for number of times to run and time)

#

e.g. this to take time across 1000 runs

> cargo run --release -- inputs/12input 1000
brisk ginkgo
#

My part 2, including parsing:

0.6427856066991808

spice ocean
spice ocean
#

Works well enough for me Β―_(ツ)_/Β―

#

Although I write my solutions so that the problem gets piped into standard input.

#

So to time my code, I do: ```bash
time cat input | python solution.py

#

If I want to try an example, I do ```bash
cat example | python solution.py

candid vortex
#

pithink

python solution.py < example
spice ocean
#

Ah yeah that would also work

candid vortex
#

using cat and a pipe for this is a bit of an anti-pattern

spice ocean
#

Not sure why I never thought to do it that way pithink

latent kindle
#

I just run it in notebooks and get the time of each cell.

spice ocean
#

In my mind, the data has to flow from left to right πŸ˜„

latent kindle
#

Add click and take an arg in your script?

candid vortex
#

redirecting from file is generally better for performance than doing the cat pipe dance

#

you give the program access to the file directly that way

#

rather than streaming things over a pipe

spice ocean
#

Right ic

lime osprey
#

for part1 just BFS and then return the first to reach end?

#

bcs the first to reach end should also be the shortest

runic finch
#

my part 1 needs 30 seconds to run

#

🀣 where did i most likely fed up

spice ocean
#

The shortest path will never contain a cycle, so if you're doing a breadth-first-search, you don't need to consider re-visiting any locations you've already visited along the current path.

runic finch
#

how likely is it that i implemented that?

#

:S

spice ocean
#

Maybe πŸ˜„

#

How have you implemented it? Can I see?

runic finch
#

!paste

spice ocean
runic finch
#

i just did start with 0 on S

#

and then all neighbors reachable +1

#

and all the ones visited i put in checked

#

and then i added new neighbors

#

checked again etc.

runic finch
spice ocean
#

Does it return the right answer?

runic finch
#

yep i get part 1 correct

#

but it takes 30 seconds

#

so in part 2 checking all "a" which are like ~1000 i think

#

i dont want to torture my CPU

spice ocean
#

You might be able to simplify your code a bit. What does coords2check do?

runic finch
#

it adds coordinates to unchecked-set

spice ocean
#

Oh right. Which coordinates get added?

runic finch
#

assuming a grid 9x9 for example

#

when the S is at arr[4][0]

#

like here

#

in the first iteration it would get

#

those green ones

#

in the next

#

the blue ones

spice ocean
#

Oh. Are you sure this will work? For example what if the path goes out and back again?

#

I think there might be a function missing from the code you provided @runic finch Where is cleaner? And also, what is state.

tight kraken
#

realizing now that making a graph of all nodes and using Dijkstra was probably overcomplicating it, this was practically made for A*

#

Also spent WAY too long pulling my hair out cause I missed reading that you could go down more than one level

runic finch
#

even if one does not get checked immedietely it remains in unchecked for later checking ig

runic finch
#

and cleaner is not working u can just delete it lemon_angrysad

manic gyro
#

very rare you would ever have such a large grid

#

and if the grid is that large I'd probably use numpy

runic finch
#

but i also cannot see how i would do it without it

spice ocean
#

If you had a function neighbors(node), then you could do: ```py
for candidate in unchecked:
for neighbor in neighbors(candidate):
...

#

You'll need to check that the neighbor is a valid location on the map. But other than that, your code will be mostly unchanged.

runic finch
#

i dont see it

#

what do i do with neighbor iterator

spice ocean
#

I'll show you. One sec.

#

@runic finch I made a few small changes to your code: https://paste.pythondiscord.com/alitozepov.py

  • I deleted coords2check and replaced it with a set comprehension. This shouldn't affect the efficiency.
  • I created a neighbors function, and used it in check_neighbor, as I described above. This is what will have had the biggest effect on the efficiency.
  • I put the main part of your code in a main() function, and I have it reading the input from stdin, to make it easier for me to test different inputs.
#

Change the main function back to read from a file if that's more convenient for you.

#

But now it runs quite quickly actually: about 1.2 seconds for my input.

#

And yes, I think you have essentially implemented breadth-first search.

runic finch
#

i will try to implement your ideas before i look at it

spice ocean
#

Do you understand the changes I've made?

spice ocean
runic finch
#

yes

#

whats different from this to the A* , djistara(?) things

#

are they just more performant?

spice ocean
#

Erm, Dijkstra's algorithm (a.k.a. uniform cost search) is slightly more general than breath-first search. It allows you to find the minimum cost path on graphs where the cost of moving between two nodes isn't necessarily constant.

#

A* search is like Dijkstras, but with an AI element. It uses a "heuristic" (kind of like an estimate of the distance to the goal) to guide it towards the goal.

runic finch
#

ty!

balmy hedge
#

part 1 took me like 6 hours to do, but now i can honestly say I have Successfully Implemented Djikstra's Algorithm. An accomplishment approximately 12 years in the making lol (I tried to do it back in uni for some reason but gave up after awhile)

#

now lets see if I can pull off part 2... I think just flipping the direction would work and stopping as soon as I find a tile with height 'a'. I might need another beer first lol

knotty vale
#

Sounds like you are on the right path.

balmy hedge
#

about the algorithm or the beer :p

knotty vale
#

both!

balmy hedge
#

correct!

manic gyro
balmy hedge
#

i considered going backwards from the beginning, but i had more trouble visualizing things that way :p. I also considered a sort of double-ended solution where i take turns searching from the end and the start, but decided that was too complicated and probably wouldn't be much faster anyways

knotty vale
#

start = "E" end = "a"

balmy hedge
#

alternatively, I could write a script to just attempt submitting every number under my part 1 solution, decrementing by 1 every minute until it's correct. The answer has to be less than part 1's solution, and probably not by much.

#

Maybe I should race that lol

knotty vale
#

That would only take a few minutes using the data I was provided.

balmy hedge
#

so what im hearing is that's the optimal solution 🀣

#

part 1: fancy named graph theory algorithm. part 2: BRUTE FORCE bayBEEE

winged zodiac
balmy hedge
#

true, and making a script for that would take longer anyway :p

balmy bramble
#

Did you do Dijkstra's with the priority queue and everything?

#

That's not quite needed for today's solution, though it probably will later in AoC

knotty vale
#

It was the first thing I thought of. Just used heapq for it.

winged zodiac
#

why though

knotty vale
#

When I think of path finding, my limited experience says Dijkstra or A*.

#

I know how those work and how to implement them.

winged zodiac
#

why not just bfs though

knotty vale
#

I never went to school for this stuff. I'm not sure what bfs is.

#

breadth first search or something?

#

Is the only difference the priority queue?

winged zodiac
#

basically. also you keep track of distances

distant palm
#

Also the ratelimit is exponential I think

#

1, 1, 5, 10 IIRC

balmy hedge
distant palm
#

Not but like also I'm not convinced that p1 is guaranteed to be more than the shortest path

#

I wouldn't be entirely surprised is someone had p1 == shortest

balmy hedge
#

less than or equal to then. offbyones everywhere

winged zodiac
#

also the instructions say something along the lines of "consider the level of S to be a", but does that mean reaching "S" counts as an "a"?

knotty vale
#

Hmm... I'm not actually sure what algo I used then... here is my code:```py

Day 12: Hill Climbing Algorithm

https://adventofcode.com/2022/day/12

from heapq import heappop, heappush

def shortest_path(grid, start, ends, direction):
# This function returns the shortest path in the grid
# from the start point to one of the ends.
next_node = []
visited = set()
heappush(next_node, (0, start))
# Loop until we hit an end.
while True:
steps, (x, y) = heappop(next_node)
if (x, y) in visited:
continue
if (x, y) in ends:
return steps
visited.add((x, y))
for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if 0 <= ny < len(grid):
if 0 <= nx < len(grid[ny]):
if (ord(grid[ny][nx]) - ord(grid[y][x])) * direction <= 1:
heappush(next_node, (steps + 1, (nx, ny)))

Parse the puzzle input file.

with open("advent_of_code\2022\day12.txt") as puzzle_input:
height_map = [list(row) for row in puzzle_input.read().splitlines()]
# Set the start and end positions.
# Part 1, S is the start and E is the end.
# Part 2, E is the start and any position that contains an "a" is the end.
starts = [None, None]
ends = [set(), set()]
for y, line in enumerate(height_map):
for x, height in enumerate(line):
if height == "S":
height_map[y][x] = "a"
starts[0] = (x, y)
if height == "E":
height_map[y][x] = "z"
starts[1] = (x, y)
ends[0].add((x, y))
if height_map[y][x] == "a":
ends[1].add((x, y))

Part one.

print(shortest_path(height_map, starts[0], ends[0], 1))

Part two.

print(shortest_path(height_map, starts[1], ends[1], -1))

distant palm
distant palm
#

They're actually the same when the cost is 1

knotty vale
#

That's basically the only one I know.

distant palm
#

There's also A* where the priority is (cost so far + heuristic underestimating the distance to the goal)

knotty vale
#

Oh, yeah, I know about that one. I felt like what I coded was fast enough, so I didn't add heuristics.

distant palm
#

I wrote what I thought was A* then realised it didn't work so it was just Dijkstra's/BFS lol

#

But it's fine because it solved the puzzle

balmy hedge
#

WOO got it in right under the wire

candid vortex
#

a well implemented bfs in python would take like 0.01s on this size of input

runic finch
# spice ocean Ah right ok.

i made it btw. it ran in 0,1 seconds and i just bruteforced the second part with it πŸ₯Ή . ty again for the help

glossy matrix
#

are we to assume E has an elevation value of z?

manic gyro
#

it says in the brief

runic finch
glossy matrix
#

ah, right, my bad

balmy canopy
#

we can just do bfs right with weghts = 1

spice ocean
spice ocean
candid vortex
#

moving here because spoilers
@ivory glen what do you think applies if I looked at only 5?

#

wait

#

wrong day

quick drum
#

Just caught up to Day 12

#

I love networkx

#

That's all I'm going to say :)

midnight surge
#

My code works with example but not with the input

placid quail
#

same bro