Fork me on GitHub
#adventofcode
<
2017-12-18
>
mfikes00:12:41

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?)

mfikes00:12:03

The pre- and post- multiplication aspect is frigging cool too!

bhauman02:12:14

wow this is really cool

minikomi03:12:43

weekend is done, need to catch up (^_^;)

minikomi11:12:27

aww man, stuck ininfinite loops for 18pt2

orestis11:12:31

Day 18 is fun; I implemented my first multi method for part 1, and I’m tempted to use core.async for part 2 🙂

minikomi11:12:26

oh shit.. is it first in first out.. ahhhhhhh

minikomi11:12:09

time to go home

nooga14:12:33

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

nooga14:12:49

and it looks like it finishes in 5 minutes, thanks clojure

bhauman14:12:38

ok the instructions are really unclear on this one, does "how many sent" mean "sent and received" ?

borkdude14:12:08

I’m counting the messages that p1 sends (so not on the queue but sent in total).

borkdude14:12:16

But I haven’t finished it yet.

bhauman14:12:35

yeah I'm counting that and my answer is wrong, too high to be exact

borkdude14:12:59

My program doesn’t halt. And when it did it was indeed too high.

borkdude14:12:12

How long does yours take to run?

borkdude14:12:38

ok, there must be an error in mine somewhere. I’ll look at it tonight

bhauman14:12:24

ok what about this what if one program comes to and end and the other is still running sending its little heart out

borkdude14:12:07

that’s not deadlock

borkdude14:12:26

at least not for both programs

ihabunek14:12:29

deadlock is reached when both programs are stuck on rcv, so it means they received all messages sent by the other

ihabunek14:12:39

so it shouldn't matter if you count sent or received

ihabunek14:12:03

but my result is wrong, so what do i know.

bhauman15:12:56

I was counting wrong

bhauman15:12:20

I was counting messages received let's see if that fixes it

ihabunek15:12:55

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.

bhauman15:12:13

I got that too, I was copying your answer though 🙂

ihabunek15:12:31

this was a total accident

bhauman15:12:36

yeah me too

ihabunek15:12:40

at least i'm in the right ballpark

orestis15:12:58

Bah, I get a too-low number as an answer for part 2.

bhauman15:12:08

I'm now walking through my instructions step by step, and "everything seems correct"™️

minikomi15:12:01

Be careful of the jumps X value

mfikes15:12:02

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

bhauman15:12:32

@mfikes yeah I'd love that

ihabunek15:12:39

i'll pm you

borkdude15:12:46

If there were a bug, it would be a hot topic on Reddit by now?

bhauman15:12:56

good point

borkdude15:12:56

(didn’t check Reddit yet)

mfikes15:12:06

Yeah. Unless lots of people are building up anxiety right now, ready to start posting.

mfikes15:12:55

To be honest, this problem was sufficiently complex where an error on AoC side seems slightly possible.

bhauman15:12:08

output: 7477

borkdude15:12:24

ok… jgz can also take two ints as operators

ihabunek15:12:09

i discovered that when i got an exception

mfikes15:12:23

@borkdude Spec saved my ass immediately with that particular gotcha

borkdude15:12:07

long live Spec!

borkdude15:12:27

If I’d used a decent parser (non handwritten) I would have discovered it too

bhauman15:12:38

yeah but > doesn't work very well on 'p

borkdude15:12:28

@bhauman What do you mean?

mfikes15:12:55

@bhauman For your input (which differs from mine in only one instruction), I get a lower value of output than 7477

bhauman15:12:21

cool that's what AoC is telling me

borkdude15:12:34

@bhauman That is valid. You should compare p to zero and jump the value of p if p > 0.

mfikes15:12:39

What was your part 1 answer, @bhauman I can check that as well

bhauman15:12:01

my part 1 answer was accepted at 8600

borkdude15:12:16

My part 1 was 3188

mfikes15:12:18

Cool. That's what I'm getting on your input as well.

ihabunek15:12:12

ok, so it's not a bug, we're just stupid 🙂

bhauman15:12:28

@borkdude I here you I got what you were saying backwards

nooga15:12:41

weird, mine was 8600 as well

ihabunek15:12:11

no idea how many variants of input exist

mfikes15:12:13

This part 2 is brutal because if you get it wrong, then there isn't much to go on...

bhauman15:12:14

I looked at @mfikes code and we are basically doing the same thing so the is obviously a wrong assumption in my code

mfikes15:12:28

(I got part 2 wrong a couple of times, but was able to suss it out.)

bhauman15:12:44

yeah they don't give you a real example program and answer for part 2

mfikes15:12:58

Ahh, good point...

ihabunek15:12:09

having a very close answer is a pain because it's not obvious what's wrong

mfikes15:12:50

@bhauman Since you looked at my code, you can also diff your input with mine. Up to you.

mfikes16:12:14

I don't see how that diff would provide much of a clue... hmm

bhauman16:12:34

thanks, well I would have an example program and output to target

bhauman16:12:57

so I'm not just chasing nothing

bhauman16:12:51

oh I think I found it

bhauman16:12:18

its a very very clojure trap to fall into

mfikes16:12:22

Please. I'm really curious now.

orestis16:12:46

Ah! Read the requirements, the p register is not that special…

ihabunek16:12:20

it's just pre-populated

orestis16:12:53

Yep; I misread that somehow as “it resolves always to 0 or 1”.

orestis16:12:08

@mfikes Ah, clojure.lang.PersistentQueue - this doesn’t show up on my Dash doc viewer…

mfikes16:12:53

@orestis Yes. I wonder if Clojure will get a reader tag for it like ClojureScript has.

minikomi01:12:13

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 😑

orestis16:12:13

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.

bhauman16:12:50

I won't spoil it by saying what hung me up but feel free to message me if you want to know

borkdude16:12:00

@orestis you can use compare-and-set for that… I tried it, but my program isn’t working yet 🙂

borkdude16:12:28

@bhauman Feel free to put a HINT in a thread under this message

bhauman16:12:38

my problem was a common clojure problem

bhauman16:12:57

I was using a vector for an input-queue

bhauman16:12:09

and using conj to append to the end

bhauman16:12:24

but then the queue type got flipped to a seq

bhauman16:12:39

and then conj started adding to the front

borkdude16:12:52

hmm, I used a PersistentQueue for that

orestis16:12:10

That is so annoying. I thought of that, and in the end just used (vec (rest ..))

borkdude16:12:44

Is PersistentQueue somehow not valid for this problem?

mfikes16:12:03

@borkdude That's what I used

bhauman16:12:03

@borkdude just not needed in my implementation

borkdude16:12:23

ok, phew… my program still won’t terminate… annoying.

bhauman16:12:41

my runtime is 500ms

orestis16:12:43

I couldn’t figure out a way to make the two program communicate cleanly what with the circular dependency; I took a different approach.

orestis16:12:51

Yes, it should end within 3-4 seconds…

mfikes16:12:54

@borkdude I was hypothesizing: If you implement it with threads, is a potential outcome a bona fide deadlock.

borkdude16:12:27

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.

bhauman16:12:40

persistent queue is better for this

borkdude16:12:06

I first had an algorithm which exchanged the queues after each iteration, but since that didn’t work I turned to atoms.

bhauman16:12:07

I'm still doing stepwise evaluation in mine

borkdude16:12:35

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.

orestis16:12:36

I took a hint from the puzzle description, and run the programs one-by-one until they block…

bhauman16:12:55

right on that's my approach

mfikes16:12:20

I wonder if there is a name for that approach. Greedy zig-zag?

borkdude16:12:41

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.

borkdude16:12:57

Should work right?

bhauman16:12:59

oh I'm not doing that

borkdude16:12:16

Since the speed is arbitrary it should be valid.

bhauman16:12:19

each program gets one instruction evaluated each step

borkdude16:12:46

They are not running on their own instruction set?

bhauman16:12:21

yes each program runs its own set

bhauman16:12:37

or rather each has its own program-counter

borkdude16:12:51

right, the instructions are immutable, but each has their own counter

mfikes16:12:09

Bruce, is it fair to say your queue s are of length 1?

mfikes16:12:56

Hmm. Maybe not... still trying to grok it.

bhauman16:12:37

only my output-queue

mfikes16:12:39

Ahh, I see how you pull an item off the front of the vector.

mfikes16:12:09

Interesting. So you have 4 queues.

bhauman16:12:31

really only two

mfikes16:12:47

Cool. 2 of them are just temporary buffers

bhauman16:12:49

output-queue is a misnomer

bhauman16:12:07

should be output-message

mfikes16:12:12

Yeah, maybe output-port of somesuch

bhauman16:12:25

I like that the states of the to programs are separate and then cross pollinated in a separate step

orestis16:12:37

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.

bhauman16:12:02

nope here:

bhauman16:12:20

I skipped the fnil

mfikes16:12:28

Ouch. Harder to see that one.

bhauman16:12:06

if I'd just had the habit of using a persistent-queue it wouldn't have been a problem

orestis16:12:18

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.

fellshard17:12:55

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.

ihabunek16:12:54

i'm a colossal idiot.

ihabunek16:12:12

programs are 0-indexed

ihabunek16:12:23

so "program 1" is the second program

ihabunek16:12:31

i was calculating the value for first

mfikes16:12:33

I made that mistake, FWIW 🙂

ihabunek16:12:52

i lost over an hour 😄

ihabunek16:12:49

sorry, should this have been under a HINT?

bhauman16:12:55

I don't think so

bhauman16:12:09

I'm in the dunce club as well

orestis16:12:15

Similar to my dynamic rebinding dance so that p always evaluated to 0 or 1, rather than been just propulated. 45 minutes 🙂

mfikes16:12:54

Yeah, that p thing was a bit odd.

bhauman16:12:17

its how they got different behavior from the same program

mfikes16:12:22

Perhaps it is what makes the programs follow a different path?

mfikes16:12:36

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.

borkdude17:12:16

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…

orestis17:12:16

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.

borkdude17:12:15

yeah, I would get an exception if that would happen

mfikes17:12:11

Yes me too.

mfikes17:12:06

Well, one could fall of the end of the instruction range....

mfikes17:12:38

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}

mfikes17:12:10

Something was up with day 7

mfikes17:12:01

Ahh right, day 7 involved some tricky math mixed with recursion

mfikes17:12:41

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.

ihabunek17:12:21

day 3 was tricky as well, i remember my group of friends had trouble solving it

ihabunek17:12:11

fortunately, i had solved something similar recently doing the python challenge

mfikes17:12:30

@borkdude Do you end up with both programs going into a waiting state, or do they just keep running indefinitely?

borkdude17:12:05

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> 

mfikes17:12:05

That means that program 1 is waiting?

borkdude17:12:14

yes (program 0 is still running)

mfikes17:12:15

That would seem to imply program 0 is running but never sending.

mfikes17:12:34

(Like an infinite loop without a snd instruction.)

ihabunek17:12:22

what if you just run program 0 until it blocks for the first time? does that ever happen?

borkdude17:12:38

going to test..

orestis17:12:07

Dumping the queues at every step also helps.

borkdude17:12:12

I’m printing the buffers now. ^

borkdude17:12:50

it seems buffer 0 is not properly filled up

borkdude17:12:05

(the one program 1 should read from)

borkdude17:12:21

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]

borkdude17:12:54

Hm, seems to be correct after all:

buf0 changes to [1335]
1 waiting...
buf0 changes to []
prog 1 succeeded reading 1335

borkdude17:12:37

I think I might have the situation where p1 writes so fast to the queue that compare-and-set never wins

borkdude17:12:11

which is a deadlock in and of itself

bhauman18:12:16

concurrent programming is hard 😬

ihabunek18:12:32

&lt;hint&gt; i just ran the first program until it blocked, then the second, and did that in a loop until both were blocked

borkdude18:12:51

yeah I had that at first, I might revert to that. Thanks!

borkdude19:12:44

I keep getting 127, but that’s not the right anwer

mfikes20:12:48

@borkdude Getting 127 was also one of my failure modes, FWIW.

mfikes20:12:21

@borkdude I'm able to repro how I produced 127, if you end up wanting a hint.

borkdude20:12:05

Yes please sir.

mfikes20:12:53

@borkdude My coding error that produced 127 involved an incorrect calculation for when a program is blocked.

mfikes20:12:28

In other words, it concluded that it was blocked, when it need not be.

mfikes20:12:51

(Not sure if these vague hints are adding confusion.)

borkdude20:12:07

I think I get what you mean yeah

borkdude20:12:25

This is my end condition…

(and (:waiting? p0)
                   (:waiting? p1)
                   (empty? (:in p0))
                   (empty? (:in p1)))

mfikes20:12:55

Cool. My 127 error involved the lack of the empty? checks.

mfikes21:12:54

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.

mfikes21:12:32

Do you mark a program as :waiting? when it tries to rcv but finds its inbound queue is empty?

mfikes21:12:34

Cool. That sounds right. (It matches my logic.)

mfikes21:12:46

Do you ever unmark the :waiting? flag?

borkdude21:12:42

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

borkdude21:12:06

the p1-sending is just a hack for now which I would clean up when I find the answer

mfikes21:12:49

Is :ctr the instruction pointer?

mfikes21:12:41

If so, I'm wondering if the instruction pointer is incremented upon a successful (non-`:waiting?`) rcv

mfikes21:12:19

Another potential problem @borkdude is that the v associated with rcv is discarded.

mfikes21:12:36

(Can't tell from the code fragment.)

borkdude21:12:13

The program counter was missing indeed.. I refactored it and forgot. Now it doesn’t terminate…

borkdude21:12:18

Another good point. Brb!

borkdude22:12:26

Oh, I should store the value on RCV…

borkdude22:12:38

still 127 with that “fix"

erwin22:12:27

shouldn't you reset the waiting state on a send?

borkdude22:12:26

@U052520AT hm, why? I reset it when I received a value

erwin22:12:18

if p1 sends you should reset waiting for p0

erwin22:12:52

otherwise you stay in locked state, maybe I do not read your code correct and this is fixed in a different way

borkdude22:12:56

doesn’t that happen when p0 receives the message?

erwin22:12:21

but your loop-until-wait never gets there?

borkdude22:12:47

it does next time in the loop

borkdude22:12:14

I mean, it does next time next-state' is called I think?

borkdude22:12:48

so p0 builds up the out queue as far as possible

borkdude22:12:06

then p1 takes over and does the same

borkdude22:12:24

eventually everything is empty and both are waiting

erwin22:12:29

ah and then you are done, but the value is wrong

bhauman22:12:08

I'm looking at your code @borkdude and your jump counter looks weird to me

bhauman22:12:04

it looks like you increment twice on zero?

borkdude22:12:17

the idea is, it’s always incremented, unless (and then the old value ctr is used + something)

bhauman22:12:42

gotcha you save the counter

bhauman22:12:58

and overwrite

borkdude22:12:20

could someone try my input just for sanity?

erwin22:12:06

do you want the answer?

bhauman22:12:10

yep it runs

borkdude22:12:23

just knowing it’s not 127 is good enough

erwin22:12:31

it is not 127

bhauman22:12:32

its up around our numbers

borkdude22:12:40

in the ballpark of?

bhauman22:12:52

no where near 127

borkdude22:12:02

what is “our numbers"

bhauman22:12:04

near above 7000

erwin22:12:14

between 7000 - 8000

borkdude22:12:35

I might save this one for christmas then… the first 😢

orestis22:12:42

What happens if a program that is already waiting is re-run?

borkdude22:12:36

then loop-until-wait returns the program

borkdude22:12:41

without modification

orestis22:12:59

But you don't give a chance to run while in waiting state? To see if new values arrived?

orestis22:12:56

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

bhauman22:12:49

@borkdude I just added some assertions to check that the input queue is empty before you overwrite it

bhauman22:12:53

and it failed

borkdude22:12:06

loop-until-wait lets a program consume its entire in queue and then returns it in a waiting state with an empty in queue

bhauman22:12:17

its not empty??

borkdude22:12:46

bhauman: I responded to orestis, didn’t see your comment yet… gonna check

bhauman22:12:23

i just posted a snippet to the main chat area

borkdude22:12:08

going to investigate

orestis22:12:34

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

borkdude23:12:03

I added both bhaumans assertions and your suggestion now… it’s running

bhauman23:12:29

I know the answer if you want to check it

erwin23:12:47

@borkdude I fixed a couple bugs in your code and it prints the correct answer now

erwin23:12:11

(as in: the same as @bhauman and my code)

borkdude23:12:25

that’s good… 🙂

borkdude23:12:03

how many were there…?

erwin23:12:36

the problem I suggested to you, and another

borkdude23:12:40

@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)))))

erwin23:12:17

ah, yes, I fixed it different, but that would also work

erwin23:12:53

for the other: please read carefully how the instructions work

borkdude23:12:23

you mean snd and rcv specifically?

orestis23:12:33

I'm off for the night -- I hope the elusive bug will be found soon :)

borkdude23:12:45

thanks orestis

erwin23:12:43

zero check

borkdude23:12:50

aaaaaaa ffffff

borkdude23:12:54

thanks 🙂

erwin23:12:10

your welcome 🙂

borkdude23:12:27

aw man, without you guys I would still be sitting here until 3 AM 🙂

bhauman23:12:34

I rearranged your logic and got it working, not that that is helpful

bhauman23:12:42

but your code does work 🙂

borkdude23:12:50

how is that not helpful?

borkdude23:12:01

it’s super helpful!

bhauman23:12:30

you got it working!!!

borkdude23:12:25

with a little help from my friends

bhauman23:12:44

can I show you my alternative logic?

bhauman23:12:05

in the main chat

mfikes23:12:09

Ugh. So in the end it was a jgz vs. jnz mistake? That kind of stuff is insidious to find.

borkdude23:12:30

@mfikes yes, that was one of the bugs. another one was pointed out by orestis and erwin

bhauman23:12:44

yes and the first exercise was so week that it didn't detect it

borkdude23:12:02

@bhauman what does #(reduce conj % (seq (:out p0) do, copy the queue?

borkdude23:12:08

who not just take it as it is?

mfikes23:12:09

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

bhauman23:12:36

I'm combining the queues because they are not empty now

bhauman23:12:44

only taking one step at a time

borkdude23:12:47

aaah and then it worked?

borkdude23:12:26

good catch man

borkdude23:12:42

I’m off to bed…

bhauman23:12:59

have a good night

borkdude23:12:40

thanks again