Clojurians Log v2

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 (^_^;)

Hmm it’s function composition only in the sense that mapping a vector of indices over a vector of indices is composition. I’m compiling the dance down to 2 actions - spin+exchange and partner. They could each be passed to exponentiate to get the nth result

Actually I should probably try that :)

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.

^ https://dev.clojure.org/jira/browse/CLJ-976

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:

https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day18.clj#L91

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...

Ah right, I guess I misunderstood the code then

@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