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?)
The pre- and post- multiplication aspect is frigging cool too!
@mfikes exactly :)
@mikelis.vindavs AFAICT the main difference is that in your solution, compilation consists of composing functions to avoid the cost of navigating data structures, whereas in mine it consists of compacting the steps into a concrete data structure - which is what enables exponentiation
wow this is really cool
weekend is done, need to catch up (^_^;)
aww man, stuck ininfinite loops for 18pt2
Day 18 is fun; I implemented my first multi method for part 1, and I’m tempted to use core.async for part 2 🙂
oh shit.. is it first in first out.. ahhhhhhh
lol
damn
ok got it
time to go home
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
and it looks like it finishes in 5 minutes, thanks clojure
ok the instructions are really unclear on this one, does "how many sent" mean "sent and received" ?
I’m counting the messages that p1 sends (so not on the queue but sent in total).
But I haven’t finished it yet.
yeah I'm counting that and my answer is wrong, too high to be exact
My program doesn’t halt. And when it did it was indeed too high.
How long does yours take to run?
not long
22s
ok, there must be an error in mine somewhere. I’ll look at it tonight
ok what about this what if one program comes to and end and the other is still running sending its little heart out
that’s not deadlock
at least not for both programs
deadlock is reached when both programs are stuck on rcv
, so it means they received all messages sent by the other
so it shouldn't matter if you count sent or received
but my result is wrong, so what do i know.
Day 18: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_18.cljc
I was counting wrong
I was counting messages received let's see if that fixes it
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 got that too, I was copying your answer though 🙂
this was a total accident
yeah me too
at least i'm in the right ballpark
Bah, I get a too-low number as an answer for part 2.
I'm now walking through my instructions step by step, and "everything seems correct"™️
Be careful of the jumps X value
@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.)
@mfikes yeah I'd love that
cool,
i'll pm you
If there were a bug, it would be a hot topic on Reddit by now?
good point
(didn’t check Reddit yet)
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.
@bhauman uploaded a file: https://clojurians.slack.com/files/U064J0EFR/F8GA5TAP6/-.clj
output: 7477
really?
HINT
@borkdude Spec saved my ass immediately with that particular gotcha
ok… jgz can also take two ints as operators
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/
long live Spec!
i discovered that when i got an exception
If I’d used a decent parser (non handwritten) I would have discovered it too
yeah but >
doesn't work very well on 'p
@bhauman What do you mean?
jgz p p
@bhauman For your input (which differs from mine in only one instruction), I get a lower value of output than 7477
cool that's what AoC is telling me
@bhauman That is valid. You should compare p to zero and jump the value of p if p > 0.
What was your part 1 answer, @bhauman I can check that as well
my part 1 answer was accepted at 8600
My part 1 was 3188
Cool. That's what I'm getting on your input as well.
ok, so it's not a bug, we're just stupid 🙂
@borkdude I here you I got what you were saying backwards
weird, mine was 8600 as well
mine too
no idea how many variants of input exist
This part 2 is brutal because if you get it wrong, then there isn't much to go on...
I looked at @mfikes code and we are basically doing the same thing so the is obviously a wrong assumption in my code
(I got part 2 wrong a couple of times, but was able to suss it out.)
yeah they don't give you a real example program and answer for part 2
Ahh, good point...
having a very close answer is a pain because it's not obvious what's wrong
@bhauman Since you looked at my code, you can also diff your input with mine. Up to you.
I don't see how that diff would provide much of a clue... hmm
thanks, well I would have an example program and output to target
True 🙂
so I'm not just chasing nothing
oh I think I found it
its a very very clojure trap to fall into
Please. I'm really curious now.
https://repl.it/repls/CompassionateGroundedHalicore this is my 1st part
Ah! Read the requirements, the p register is not that special…
it's just pre-populated
My day 18: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day18.clj
Yep; I misread that somehow as “it resolves always to 0 or 1”.
@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.
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 🙂
@bhauman Feel free to put a HINT in a thread under this message
HINT
my problem was a common clojure problem
I was using a vector for an input-queue
and using conj to append to the end
but then the queue type got flipped to a seq
and then conj
started adding to the front
hmm, I used a PersistentQueue for that
That is so annoying. I thought of that, and in the end just used (vec (rest ..))
Is PersistentQueue somehow not valid for this problem?
@borkdude That's what I used
@borkdude just not needed in my implementation
ok, phew… my program still won’t terminate… annoying.
my runtime is 500ms
I couldn’t figure out a way to make the two program communicate cleanly what with the circular dependency; I took a different approach.
Yes, it should end within 3-4 seconds…
@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.
persistent queue is better for this
I first had an algorithm which exchanged the queues after each iteration, but since that didn’t work I turned to atoms.
I'm still doing stepwise evaluation in mine
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…
right on that's my approach
I wonder if there is a name for that approach. Greedy zig-zag?
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'm a colossal idiot.
Should work right?
oh I'm not doing that
programs are 0-indexed
Since the speed is arbitrary it should be valid.
each program gets one instruction evaluated each step
so "program 1" is the second program
i was calculating the value for first
I made that mistake, FWIW 🙂
😢
They are not running on their own instruction set?
i lost over an hour 😄
yes each program runs its own set
yeah
or rather each has its own program-counter
sorry, should this have been under a HINT?
right, the instructions are immutable, but each has their own counter
I don't think so
I'm in the dunce club as well
Bruce, is it fair to say your queue s are of length 1?
Hmm. Maybe not... still trying to grok it.
only my output-queue
Ahh, I see how you pull an item off the front of the vector.
Interesting. So you have 4 queues.
really only two
Cool. 2 of them are just temporary buffers
output-queue is a misnomer
should be output-message
Yeah, maybe output-port of somesuch
Similar to my dynamic rebinding dance so that p
always evaluated to 0 or 1, rather than been just propulated. 45 minutes 🙂
yeah
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
nope here:
I skipped the fnil
Ouch. Harder to see that one.
if I'd just had the habit of using a persistent-queue it wouldn't have been a problem
Yeah, that p
thing was a bit odd.
its how they got different behavior from the same program
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.
Perhaps it is what makes the programs follow a different path?
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…
right?
Well, one could fall of the end of the instruction range....
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}
Something was up with day 7
yeah, I would get an exception if that would happen
Ahh right, day 7 involved some tricky math mixed with recursion
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.
Yes me too.
day 3 was tricky as well, i remember my group of friends had trouble solving it
fortunately, i had solved something similar recently doing the python challenge
@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>
That means that program 1 is waiting?
yes (program 0 is still running)
That would seem to imply program 0 is running but never sending.
(Like an infinite loop without a snd
instruction.)
hmm yes…
what if you just run program 0 until it blocks for the first time? does that ever happen?
going to test..
Dumping the queues at every step also helps.
I’m printing the buffers now. ^
it seems buffer 0 is not properly filled up
(the one program 1 should read from)
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]
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.
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
which is a deadlock in and of itself
concurrent programming is hard 😬
<hint> i just ran the first program until it blocked, then the second, and did that in a loop until both were blocked
yeah I had that at first, I might revert to that. Thanks!
I keep getting 127, but that’s not the right anwer
@borkdude Getting 127 was also one of my failure modes, FWIW.
@borkdude I'm able to repro how I produced 127, if you end up wanting a hint.
Yes please sir.
@borkdude My coding error that produced 127 involved an incorrect calculation for when a program is blocked.
In other words, it concluded that it was blocked, when it need not be.
(Not sure if these vague hints are adding confusion.)
I think I get what you mean yeah
This is my end condition…
(and (:waiting? p0)
(:waiting? p1)
(empty? (:in p0))
(empty? (:in p1)))
Cool. My 127 error involved the lack of the empty?
checks.
😢
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?
yes
Cool. That sounds right. (It matches my logic.)
Do you ever unmark the :waiting?
flag?
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))
the p1-sending
is just a hack for now which I would clean up when I find the answer
Is :ctr
the instruction pointer?
If so, I'm wondering if the instruction pointer is incremented upon a successful (non-`:waiting?`) rcv
Another potential problem @borkdude is that the v
associated with rcv
is discarded.
(Can't tell from the code fragment.)
The program counter was missing indeed.. I refactored it and forgot. Now it doesn’t terminate…
Another good point. Brb!
FWIW here’s my day 18 so far… https://github.com/borkdude/aoc2017/blob/master/src/day18.clj
Oh, I should store the value on RCV…
still 127 with that “fix"
shouldn't you reset the waiting state on a send?
@erwin hm, why? I reset it when I received a value
if p1 sends you should reset waiting for p0
otherwise you stay in locked state, maybe I do not read your code correct and this is fixed in a different way
doesn’t that happen when p0 receives the message?
but your loop-until-wait never gets there?
it does next time in the loop
I mean, it does next time next-state'
is called I think?
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
@borkdude shared a file: https://clojurians.slack.com/files/U04V15CAJ/F8FRV8D32/gistfile1.txt
so p0 builds up the out queue as far as possible
then p1 takes over and does the same
eventually everything is empty and both are waiting
ah and then you are done, but the value is wrong
right
I'm looking at your code @borkdude and your jump counter looks weird to me
tell
it looks like you increment twice on zero?
the idea is, it’s always incremented, unless (and then the old value ctr is used + something)
gotcha you save the counter
and overwrite
right
could someone try my input just for sanity?
https://github.com/borkdude/aoc2017/blob/master/resources/day18.txt
do you want the answer?
yep it runs
just knowing it’s not 127 is good enough
it is not 127
its up around our numbers
in the ballpark of?
no where near 127
what is “our numbers"
near above 7000
between 7000 - 8000
I might save this one for christmas then… the first 😢
What happens if a program that is already waiting is re-run?
then loop-until-wait returns the program
without modification
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
and it failed
loop-until-wait lets a program consume its entire in queue and then returns it in a waiting state with an empty in queue
its not empty??
bhauman: I responded to orestis, didn’t see your comment yet… gonna check
@bhauman uploaded a file: https://clojurians.slack.com/files/U064J0EFR/F8HC7DNFQ/-.clj
i just posted a snippet to the main chat area
thank you
going to investigate
@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...
aah
I added both bhaumans assertions and your suggestion now… it’s running
I know the answer if you want to check it
@borkdude I fixed a couple bugs in your code and it prints the correct answer now
(as in: the same as @bhauman and my code)
that’s good… 🙂
how many were there…?
the problem I suggested to you, and another
so 2
@erwin 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)))))
ah, yes, I fixed it different, but that would also work
for the other: please read carefully how the instructions work
you mean snd and rcv specifically?
I'm off for the night -- I hope the elusive bug will be found soon :)
thanks orestis
@borkdude no
zero check
aaaaaaa ffffff
thanks 🙂
your welcome 🙂
aw man, without you guys I would still be sitting here until 3 AM 🙂
I rearranged your logic and got it working, not that that is helpful
but your code does work 🙂
how is that not helpful?
it’s super helpful!
credits in the code: https://github.com/borkdude/aoc2017/blob/master/src/day18.clj
you got it working!!!
with a little help from my friends
can I show you my alternative logic?
yes
@bhauman uploaded a file: https://clojurians.slack.com/files/U064J0EFR/F8GHRKGUC/-.clj
in the main chat
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
yes and the first exercise was so week that it didn't detect it
@bhauman what does #(reduce conj % (seq (:out p0)
do, copy the queue?
who not just take it as it is?
The challenge on this one is you need to get all of the planets in alignment with no way of figuring out which (or which ones) are off
I'm combining the queues because they are not empty now
only taking one step at a time
aaah and then it worked?
yep
wow
good catch man
I’m off to bed…
have a good night
thanks again