Fork me on GitHub
#adventofcode
<
2019-12-20
>
fellshard00:12:24

Key simplifications you can make (in thread to hide spoilers)

fellshard00:12:12

1. Seal up dead-ends (including doors that lead to dead ends) 2. Remove trivial key-door pairs, I think every puzzle set has a series of these in one path 3. Remove keys for which there are A. no doors and B. which are automatically retrieved en route to another key I suspect you should reduce the mazy to a dependency graph - the obvious route for mine can be worked out by hand and a couple of assisting tools (distance between points); I just haven't had the time yet. Of these, the first is the biggest aid to visualizing the shape of the data you've been given and understanding its quirks.

dmarjenburgh06:12:54

One key optimization I used is that the state after getting keys a,b,c and b,a,c are the same. So if you have a fn shortest-path(curpos, collectedkeys) you can memoize it.

dmarjenburgh06:12:24

The second one is that I created a map from key/entrancepoint to the possible other keys with their distance and doors in between. You can compute this map once and use it to efficiently get the next possible steps given your current position(s) and collected keys

fellshard08:12:28

There's a whole path in mine that has nothing but keys; you can fetch each of them with optimal efficiency with a thorough traversal, and that unlocks the next dependency in the graph as well given which ones are placed in there. I'm presuming based on what I saw in other inputs that each maze is very similar in logical layout.

nam.hyunwoo05:12:22

getting heavier, and I don't feel like i'm enjoying anymore 😢

fellshard06:12:50

These last few days get pretty hefty

fellshard08:12:09

Well, took long enough. Spent way too much time parsing by hand which probably could have been spent manually encoding the maze coordinates. ... And that's just part one. Part two will have to come later, but I'm intrigued.

dmarjenburgh13:12:48

That parsing was annoying. My first version had a bug because it read labels in the order away from the maze point .. But all labels read left-to-right or up-to-down.

fellshard08:12:48

I lied, finished it. It was too interesting to resist. The changes aren't that significant between phases.

misha11:12:26

that was fast. I wasted time debugging because of bug in outer-portal? fn, which I wrote first, and assumed it fails last kappa

fellshard19:12:41

My first answer was off because I mis-counted where the bottom/right inner portals were placed; converting that to a calculated value instead of a hand-measured one was more robust for using the sample scenarios to test, anyway

fellshard08:12:29

Sketching this one could be interesting... depends how many layers deep it goes.

misha11:12:48

today's is easier though. probably just because search space is

misha11:12:02

a tube, and you obviously have to use BFS, or you risk chasing infinity on very first path walk

dmarjenburgh13:12:19

Got behind a bit due to travel. Caught up today: Day 19 https://gitlab.com/dmarjenburgh/adventofcode/blob/a159992a5123919594d95471ed7fae0fd2afdbc8/src/adventofcode/year_2019.clj#L587-617 Day 20 https://gitlab.com/dmarjenburgh/adventofcode/blob/a159992a5123919594d95471ed7fae0fd2afdbc8/src/adventofcode/year_2019.clj#L619-663 Again searching on a grid, finding neighbours above,below,left and right. I’ve written that code so many times I’m wondering if I should find a way to reuse it 😄

dmarjenburgh14:12:31

I used to feel Clojure is not the best language for things like AoC, but in many situations it is and in others I now feel it probably requires a different way of approaching the problem. With the right solution, I think the Clojure code is always fast enough. For day 19 with the tractor beam, I wrote an infinite lazy-sequence that gets more of the beam with each item (the beam points for the next y-coordinate). Then the stopping condition was a separate fn and I could use take-while. It decouples generating the next iteration from calculating the stopping condition (square), the lazy-sequence could be used for both part 1 and 2. In in imperative loop, these things would have been coupled.

misha15:12:23

you can just find first bottom-left corner for which all 4 corners will be within beam. even no need for lazy seqs there

misha15:12:22

will be faster, because everything you drop-while is still calculated

dmarjenburgh15:12:25

Doesn’t that amount to the same amount of calculations? You iterate until you can fit the square

misha16:12:50

tbh your code is hard to glance over with all the inline fns with nested inline destructuring, so maybe you did exactly what I wrote.

misha16:12:11

(defn beam? [cpu x y]
  (when (-> cpu (assoc ::cpu/input [x y]) cpu/step ::cpu/output (= 1))
    [x y]))

(defn score [x y]
  (-> x (* 10000) (+ y)))


(defn f2 [input size]
  (let [cpu    (make input)
        size   (dec size)]
    (loop [x1 0
           y2 size]
      (if-not (beam? cpu x1 y2) ;;left bottom corner
        (recur (inc x1) y2)
        (let [x2 (+ x1 size)
              y1 (- y2 size)]
          (if (and
                (beam? cpu x2 y2) ;;right bottom corner
                (beam? cpu x2 y1)) ;;right top corner
            (score x1 y1)
            (recur x1 (inc y2))))))))

dmarjenburgh20:12:56

It’s the same in going down increasing y per iteration and stopping when the square fits. I have some optimization based on the assumption that the min-x/max-x coords of the beam change by 1 unit at most (which held true). Therefore I run the intcode program twice per y coordinate.

misha14:12:33

it depends on what you consider "fast enough". seconds? yes. But c++ and rust people start to cringe if stuff takes 10ms+ to run

dmarjenburgh15:12:29

I’d rather save on development time d

misha15:12:38

altho, some of the python/c aoc solutions are just 2-3variables and 2-4 nested loops, for 7-10 lines total, less characters than my usual parse-input fn

misha15:12:03

I doubt anyone ever got global top100 gold star with clojure for any mid month-ish puzzle

yuhan11:12:31

I got global top-100 stars for some of the intcode problems in pure clojure 🙂

yuhan11:12:08

I feel like part of the reason was the instant RDD feedback and being able to directly get a feel of the shape of the data and manipulate it, definitely makes up for some of the verbosity

ghadi17:12:06

dunno @misha, your Day 10 solution got a gold star from me

ghadi17:12:19

way more elegant than any imperative mess

misha17:12:23

but elegance is just one of dimensions, and is rarely a top1 one would consider while solving puzzles under time limit

ghadi17:12:34

yeah true

ghadi17:12:37

need a speed hammock

rjray22:12:13

I find my Clojure solutions at least feel more elegant. Granted, I'm not a code-golfer so I'm writing meaningful variable/function names (most of the time). And I'm not even trying to compete on the main leaderboard.

rjray23:12:56

Meanwhile, having finally gotten day 18 done (after stopping to do 19 when it unlocked) I am now looking at day 20. Parsing this input will be tricky. Hell, it would be tricky even in a language like Perl that lives for stuff like this...