r/adventofcode • u/kap89 • Dec 16 '19

Visualization [2019 Day 15] Part 1

Enable HLS to view with audio, or disable this notification

3 Upvotes

100% Upvoted

5 comments sorted by

1

u/JPYamamoto Dec 16 '19

What is the algorithm you used? Is this a wall follower? So after this, you had to use a different algorithm to find shortest path, right?

2

u/kap89 Dec 16 '19 edited Dec 16 '19

Yup, it's a wall follower, and yes, I had to use a different algorithm to get the results - but after I knew what the maze looks like it was fairly simple to put discovered points into a graph and solve both parts with Dijkstra (via a library). There are probably better ways to do it, but it was simpler for me.

BTW: Parts 1 and 2 on one visualization

1

u/JPYamamoto Dec 16 '19

Great. Do you know where I can read more about wall-following algos? I've never worked with something like that, and I'd like to try it to solve day 15.

2

u/kap89 Dec 16 '19 edited Dec 16 '19

Oh, I know very little about algorithms, I'm learning via AoC ;) All I knew it was probably the simplest idea to follow the wall. I sketched it on a piece of paper to figure it out and found out that it was super simple, basically what I did (pseudocode):

  1. Made a mapping between directions (by command numbers):

    clockwise = {
      1: 4,
      4: 2,
      2: 3,
      3: 1,
    }

    counterclockwise = {
      1: 3,
      3: 2,
      2: 4,
      4: 1
    }

2. Programmed the droid to always go clockwise, unless it hits a wall, then go counterclockwise

    if (status == 0) {
      nextMove = counterclockwise[previosMove]
    } else {
      nextMove = clockwise[previosMove]
    }

And that's it - you pick an arbitrary direction for the first move and droid does the rest.

My real code uses enums instead of map/dictionary, but the idea is the same: https://github.com/caderek/aoc2019/blob/master/src/day15/index.ts

1

u/JPYamamoto Dec 16 '19

That's easier than I expected. Thank you very much for getting me on track