This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2017-12-18
Channels
- # adventofcode (326)
- # aws (1)
- # beginners (67)
- # cider (52)
- # cljs-dev (5)
- # cljsrn (5)
- # clojure (104)
- # clojure-art (2)
- # clojure-austin (34)
- # clojure-france (12)
- # clojure-greece (38)
- # clojure-india (2)
- # clojure-italy (6)
- # clojure-spec (11)
- # clojure-uk (32)
- # clojurescript (51)
- # core-async (5)
- # cursive (11)
- # data-science (5)
- # datascript (3)
- # datomic (3)
- # defnpodcast (7)
- # fulcro (26)
- # graphql (10)
- # hoplon (1)
- # instaparse (2)
- # jobs (1)
- # klipse (3)
- # lumo (13)
- # off-topic (50)
- # om (2)
- # onyx (19)
- # parinfer (1)
- # pedestal (4)
- # re-frame (18)
- # ring-swagger (1)
- # spacemacs (1)
- # specter (42)
- # sql (9)
- # uncomplicate (18)
- # unrepl (13)
Is Val's exponentiation somewhat along the lines of saying x^16 = (x^8)^2 = ((x^4)^2)^2 = (((x^2)^2)^2)^2 ? (Thus leading to logarithmic time complexity?)
@mfikes exactly :)
Day 18 is fun; I implemented my first multi method for part 1, and I’m tempted to use core.async for part 2 🙂
http://adventofcode.com/2017/day/16 it just struck me that wrapping the function from the part 1 in memoize
would be even less work than finding cycles
ok the instructions are really unclear on this one, does "how many sent" mean "sent and received" ?
ok what about this what if one program comes to and end and the other is still running sending its little heart out
deadlock is reached when both programs are stuck on rcv
, so it means they received all messages sent by the other
Day 18: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_18.cljc
lol, i just got: > That's not the right answer; your answer is too high. Curiously, it's the right answer for someone else; you're either cheating, logged in to the wrong account, or got an unlucky guess.
I'm now walking through my instructions step by step, and "everything seems correct"™️
@bhauman Given the backlog here, I wonder if there might be a bug in Advent of Code. If your input is available, and you give me the answer you are getting, I could run my code on your input and see if I get the same answer as you. (You could theoretically do the same, but you might not want to be spoiled by seeing any code, or any answers. That last aspect could be fixed by using ==
instead of having the code emit the answer.)
Yeah. Unless lots of people are building up anxiety right now, ready to start posting.
To be honest, this problem was sufficiently complex where an error on AoC side seems slightly possible.
jgz 1 3
, I definitely didn’t handle that case.
Thanks to this reddit comment: https://www.reddit.com/r/adventofcode/comments/7kkumq/help_2017_day_18_part_2rust_stuck_on_infinite_loop/
@bhauman For your input (which differs from mine in only one instruction), I get a lower value of output than 7477
@bhauman That is valid. You should compare p to zero and jump the value of p if p > 0.
I looked at @mfikes code and we are basically doing the same thing so the is obviously a wrong assumption in my code
@bhauman Since you looked at my code, you can also diff your input with mine. Up to you.
https://repl.it/repls/CompassionateGroundedHalicore this is my 1st part
My day 18: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day18.clj
@mfikes Ah, clojure.lang.PersistentQueue - this doesn’t show up on my Dash doc viewer…
@orestis Yes. I wonder if Clojure will get a reader tag for it like ClojureScript has.
Wow, that’s neat.. I also made three mistake of using a vec with peek/pop and getting stuck for ages until I realized the queues were fifo and not like a stack 😑
I was looking for a way to do an atomic pop-and-return-value, that would return [head, rest-of-coll] — I initially thought of running the two programs in two threads and use some of Clojure’s concurrency constructs, but I don’t know enough and it seemed a bit fiddly.
https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day18.clj
I won't spoil it by saying what hung me up but feel free to message me if you want to know
@orestis you can use compare-and-set for that… I tried it, but my program isn’t working yet 🙂
I couldn’t figure out a way to make the two program communicate cleanly what with the circular dependency; I took a different approach.
@borkdude I was hypothesizing: If you implement it with threads, is a potential outcome a bona fide deadlock.
I didn’t do threads. To make it easy on me I started using two atoms with a PersistentQueue in each which are shared with both programs.
I first had an algorithm which exchanged the queues after each iteration, but since that didn’t work I turned to atoms.
I had some stupid mistakes like not setting the init value properly and things like that. There might still be something like that in there.
I took a hint from the puzzle description, and run the programs one-by-one until they block…
This is what I’m trying right now: run program 1 until it’s waiting, then turn to program 2, etc. until they are both waiting.
I like that the states of the to programs are separate and then cross pollinated in a separate step
I get the correct answer by doing that zig-zag; run 0 until blocks, then 1 until blocks. The logic to detect the deadlock is a bit gnarly though.
@bhauman Was your bug right on this line? https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day18.clj#L85
if I'd just had the habit of using a persistent-queue it wouldn't have been a problem
Isn’t this a prime candidate of where a persistent data structure is more trouble? Because you need to make sure that both references point to the updated one.
I considered moving my solution to a linearized version just to see how the solution works itself out differently. I ended up running both programs in parallel at each step, then syncing outputs of each into each other's queues to conclude the step.
Similar to my dynamic rebinding dance so that p
always evaluated to 0 or 1, rather than been just propulated. 45 minutes 🙂
Cool. The use of p
while also using the words “p rogram ID” probably caught a lot of people off guard if you don't read the description carefully.
I didn’t read this properly: > Once both of your programs have terminated (regardless of what caused them to do so) This means that not both programs have to be deadlocked…
The only other case where a program terminates is when it jumps before or after the instruction list; so then the other keeps on going. But to be honest in my input both programs end up as blocked.
It is interesting if you look at https://adventofcode.com/2017/stats and calculate the percentage of participants who haven't completed part 2 for each day:
{1 16,
2 14,
3 26,
4 9,
5 4,
6 4,
7 23,
8 2,
9 2,
10 9,
11 3,
12 3,
13 9,
14 8,
15 2,
16 11,
17 7,
18 39}
I think that one had the highest missed guess rate for me, and I ultimately solved it by hand before successfully writing proper code for it.
@borkdude Do you end up with both programs going into a waiting state, or do they just keep running indefinitely?
This is my output before I cancel execution:
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
1 waiting...
boot.user>
what if you just run program 0 until it blocks for the first time? does that ever happen?
This is obviously very wrong:
p0 is writing to buf0 4424
[] [3142 7236 6781 1615 9553 9174 487 5263 8490 4877 7397 1572 2781 724 7087 1957 2396 4361 7509 630 3489 7917 1716 2592 7872 5372 8575 4031 8051 4352 5790 9023 9786 1147 1335 8212 9615 4144 2025 4572 4593 5030 3448 9823 4746 9209 5195 208 8618 9927 8093 6367 4333 5895 8710 4486 911 7895 1137 1585 8978 4112 6266 9370 5106 7721 5788 1700 4571 1129 2265 3188 6142 3291 2270 3551 6243 7724 8606 4149 5014 4268 9066 8617 474 933 645 8505 364 1643 9447 8181 3920 95 9224 1056 5457 6781 2362 2203 2164 3543 4309 3842 8826 7245 8414 5958 8188 110 7505 767 1239 9936 1807 5936 4265 1283 1809 4109 8173 385 3587 3021]
Hm, seems to be correct after all:
buf0 changes to [1335]
1 waiting...
buf0 changes to []
prog 1 succeeded reading 1335
I think I might have the situation where p1 writes so fast to the queue that compare-and-set never wins
<hint> i just ran the first program until it blocked, then the second, and did that in a loop until both were blocked
@borkdude My coding error that produced 127 involved an incorrect calculation for when a program is blocked.
This is my end condition…
(and (:waiting? p0)
(:waiting? p1)
(empty? (:in p0))
(empty? (:in p1)))
It was pretty cut-n-dry for me because one of the programs was marked as waiting when it had stuff left to consume in its queue.
Do you mark a program as :waiting?
when it tries to rcv
but finds its inbound queue is empty?
snd
(let [v (get-val registers reg)]
(do (when (= id 1)
(swap! p1-sending inc)))
(->
p
(update :ctr inc)
(update :out conj v)))
rcv (if-let [v (peek in)]
(assoc p
:in (pop in)
:waiting? false)
(assoc p :waiting? true))
If so, I'm wondering if the instruction pointer is incremented upon a successful (non-`:waiting?`) rcv
The program counter was missing indeed.. I refactored it and forgot. Now it doesn’t terminate…
FWIW here’s my day 18 so far… https://github.com/borkdude/aoc2017/blob/master/src/day18.clj
@U052520AT hm, why? I reset it when I received a value
otherwise you stay in locked state, maybe I do not read your code correct and this is fixed in a different way
https://github.com/borkdude/aoc2017/blob/master/src/day18.clj#L105 this is called the next time ?
This is what’s happening: https://gist.github.com/borkdude/d54ad43d7001334adde2912c87d9a1d6
the idea is, it’s always incremented, unless (and then the old value ctr is used + something)
But you don't give a chance to run while in waiting state? To see if new values arrived?
That is, loop-until-wait checks for the previously set waiting flag, not the current one, I think. Reading this on a mobile, might be misreading...
@borkdude I just added some assertions to check that the input queue is empty before you overwrite it
loop-until-wait lets a program consume its entire in queue and then returns it in a waiting state with an empty in queue
@borkdude yes but the second time round, it doesn't call next-state, does it? The waiting flag is only cleared after next state is run...
@U052520AT is this one of the solutions?
(defn loop-until-wait
[instructions prog]
(loop [p (next-state instructions prog)]
(if (:waiting? p)
p
(recur (next-state instructions p)))))
credits in the code: https://github.com/borkdude/aoc2017/blob/master/src/day18.clj
Ugh. So in the end it was a jgz
vs. jnz
mistake? That kind of stuff is insidious to find.
@mfikes yes, that was one of the bugs. another one was pointed out by orestis and erwin