Fork me on GitHub
#adventofcode
<
2018-12-20
>
Average-user04:12:17

Very similar to day 23 of 2017

norman05:12:15

Day 20… Where to begin…

gklijs05:12:57

At room 0,0 with 4 optional doors?

norman07:12:03

That’s it!

fellshard07:12:03

Quite enjoyed this one. Had to backtrack a bit once I realized I was parsing into a difficult-to-wrangle format.

norman07:12:24

Again, my solution is really slow… It seems to be making progress, but…

norman07:12:28

Hmm. I had to cache/memoize a bit. That sped it up a lott, but It doesn’t feel like I should have needed to do that. Maybe it’ll be more obvious in the morning.

norman08:12:26

I couldn’t sleep until I figured this out, despite being too tired to actually think. Whenever I alternate, push [pos, pattern] for each alternation onto the search stack, which can cause a lot of duplicate work to be done. Adding in the cache check reversed the duplication, which really shouldn’t have been there. That probably makes no sense to anyone but me, but I at least I can let myself sleep 🙂

misha08:12:03

memoize + store set of visited rooms in each path:

"Elapsed time: 1402.048955 msecs"
"Elapsed time: 1255.330936 msecs"

misha08:12:26

good thing, it is a "tree", not a graph

fellshard10:12:28

Interesting, I didn't even check to see if any of the paths ever looped back on themselves

misha10:12:02

every branch in examples is either terminates ))))$, or loops to the previous point (NEWS|)... after doing a circle

norman15:12:42

I don’t think tracking the visited rooms is sufficient - you have to know you haven’t been to the same room with the same remaining pattern to search

fellshard19:12:14

I'd recommend breaking the solution up into multiple stages.

meikemertsch09:12:50

Argh! All examples of part one work with my solution but of course the big one doesn’t 🙈

meikemertsch13:12:27

Ah. I think I know what I did

misha09:12:39

had a different issue, massively misunderstood p2, and wasted like extra hour on it

Average-user18:12:37

(time (part-1))
"Elapsed time: 39457.156774 msecs"
3314

misha19:12:00

memoize it, @lucaspolymeris

Average-user19:12:18

If you analyze the code, the only function that takes real time is nodes-depth

misha19:12:50

(filter (complement seen) (remove seen)

misha19:12:46

move might be used many times with same args

Average-user19:12:39

I always forget remove, but will just change readability, not performance I think. But thanks anyways

misha19:12:22

(defn move [dir [x y]]

misha19:12:03

if you have shared seen - make it transient

Average-user19:12:12

ahh right. But the only function that uses move is build-graph. Which takes:

(time (count (build-graph (clean-input))))
"Elapsed time: 77.78829 msecs"
10000

misha19:12:12

I tracked seen per branch, so could not make it transient, but my move repetitive usage is noticable

misha19:12:04

(reduce conj seen front)
                 (reduce conj ds (map (constantly depth) front))
into might speed these 2 up, since it does transient under the hood, if possible.

Average-user19:12:17

I might try to update neighbors, since I will never use one key more than once

misha20:12:00

so you are doing exhaustive search, and then - select?

Average-user20:12:20

not sure what you mean. nodes-length returns the minimum distance between the root and every other node

Average-user20:12:07

into doesn't change much btw

misha20:12:59

but you assign those distances to every known room first

baritonehands21:12:34

I like how it came using some string manipulation and the reader:

(defn parse-input [input]
  (-> input
      (str/replace #"[\^]" "[")
      (str/replace #"[\$]" "]")
      (str/replace "|" " | ")
      (read-string)))
[ENWWW (NEEE | SSE (EE | N))]

baritonehands21:12:45

still working on actually processing that for the solution though

baritonehands21:12:52

oops, left the regexes even though I no longer need them

norman23:12:22

@lucaspolymeris I don’t think yours works. Try “^N(E|)N(E|)N$”

norman23:12:34

or even “^N(E|)N”

Average-user00:12:59

Im only with my phone now, I'll try it later. But there might be some off by ones errors in small inputs

norman00:12:18

No - it’s actually not your code, it’s that the stack based approach doesn’t work except for on the sample input

Average-user01:12:44

Is not stack based

Average-user01:12:30

I think is just a coincidence of names

Average-user01:12:47

It worked with my input (not sample)