Advent of Code

[Greenbank]

but

Code: [Select]

   A|BC
   ++++
isn't unless you look further afield than immediately adjacent characters. I couldn't be bothered so just wrote a prompt in to look at it by eye and indicate where it should go

If you're coming down from A then it's unambiguous. You go down, turn left (as you can't turn right), to the end of that line (because you only turn when you can't continue straight on) and then the only choice is to turn left (up) to get to C.

Likewise coming down from C is unambiguous (C down, right, all the way to the end, right and up to A).

Coming down from B is ambiguous as you have a choice of which way to turn, but my reading of the instructions was that this was not going to occur since it didn't say what to do in such cases.

[Oaky]

(click to show/hide)

I haven't yet solved the threaded version's race condition though.  I'm finding it difficult to reliably tell from one thread whether the other thread is also blocked :/

(click to show/hide)

I've done 18b in a threaded way as well and I think it's always possible to make them deadlock at the 'wrong' place.
I've done a deadlock check by doing a test-lock-retest for whether the receive queue is empty, and if the other thread is also waiting on an empty queue, there's a deadlock.
However, it's always possible that if one thread races ahead and does, say, 100 or more lines before the other does any, then they get into a deadlock situation far before the 'latest possible' deadlock situation.
So most of the time my code generates the answer that was the first and only one I tried and which was accepted, 6958.  But 1 time out of 10 it will generate 127.
Could there have been multiple correct answers, I wonder?
It does say in the text "in fact, the programs don't even necessarily run at the same speed".
Not sure how to define 'race condition' in this case. I can prove that it deadlocks other than when at the 'maximum' right answer but not sure how to deem that wrong other than by forcing them to go at the same speed.
I think what would also prevent this 'race condition' would be to force them to go at similar speeds, but how 'similar' it needs to be is the question.

(click to show/hide)

I can't see how they can deadlock and produce anything but a single answer. The data they send is not dependent on anything timing related and must the be the same each time.

There can only be a deadlock when both queues are empty and both are attempting to receive. It's impossible to detect this from the other process if there are no other communication channels between the programs. A "haven't heard from it from 30 seconds, assuming it is also deadlocked" is about the best you can do without something that knows about the state of the other processes queue.

I was going to re-implement mine this evening as two separate processes using TCP comms, just for fun.

(click to show/hide)

The basis of my deadlock detection was to have two objects in each VM state... pseudo-code (aka pigeon-python):-

Code: [Select]

self.i_am_blocked
self.other_is_blocked

and connecting the programs involves cross-connecting these objects...

Code: [Select]

def connect(self, other):
    self.other_is_blocked = other.i_am_blocked

(as well as similarly connecting their send buffers...)

The deadlock detection then looks like

Code: [Select]

if self.i_am_blocked and self.other_is_blocked:
    # deadlocked
    <do deadlock stuffs here>

self.i_am_blocked gets set when I try to rcv, but my queue is empty.  I then go into a tight loop retrying the rcv, and testing for a deadlock each time round the loop.

self.i_am_blocked gets cleared when I sucessfully read a value from my queue^*.

I mostly see the threaded version giving me the same answer as the non-threaded, but sometimes it erroneously detects a deadlock early, giving me answers starting at 127 but sometimes higher (usually less than 1000, though).

( * ) I wondered if this might be the issue. Maybe instead I should have been clearing the other program's blocked status via self.other_is_blocked when I send a value to my queue?  Then again,  I think there's still scope for prog1 to try a rcv, fail, then prog0 do a snd, clearing clear the prog1 blocked flag before prog1 got round to got round to setting it with the net effect that prog1 thinks it's blocked (or at least looks blocked to prog0 via the self.other_is_blocked channel, but does in fact, have stuff in its queue.

Perhaps I need to either have a lock which the thread acquires when touching the send/receive/am I blocked code and releases once it's out of there.

Perhaps I should make one of the programs special based on it's program number and have only that program maintain (or just clear?) the blocked states?  I need to think about the failure modes of the non-atomicity of the receive adn blocked flag maintenance.

[Greenbank]

(click to show/hide)

self.i_am_blocked gets cleared when I sucessfully read a value from my queue^*.

...

( * ) I wondered if this might be the issue. Maybe instead I should have been clearing the other program's blocked status via self.other_is_blocked when I send a value to my queue?  Then again,  I think there's still scope for prog1 to try a rcv, fail, then prog0 do a snd, clearing clear the prog1 blocked flag before prog1 got round to got round to setting it with the net effect that prog1 thinks it's blocked (or at least looks blocked to prog0 via the self.other_is_blocked channel, but does in fact, have stuff in its queue.

...

(click to show/hide)

Yes, that's where the problem lies.

In your setup you could have p1 blocked waiting for a signal, and p0 sends a signal and then progresses to a rcv command (where nothing is ready to be received and so blocks itself) at which point it sees both p1 blocked (since it hasn't cleared its flag yet) and itself (p0) blocked, and triggers the exit.

And, yes, locks (mutexes/condition variables/etc) are the solution. Implementing them properly is left as an exercise for the reader.

Modifying who does what where will only move the problem and enable a different scenario that can lead to false deadlock detection, or highlight a problem that cannot be detected or prevented.

i.e. making a program repsonsible for clearing the other processes is_blocked flag, you would imagine it executes nice and linearly like this:-

p1 blocked
p0a sends message to p1
p0b clears p1's is_blocked status
p1 processes message
etc...

but what if it did:-

p1 blocked
p0a sends message to p1
p1 processes message
p1 executes another rcv command, nothing on queue, marks itself as blocked
p0b clears p1's is_blocked status
p0 waits for message (nothing on its queue)

now it's deadlocked and there's no deadlock detection

I think it's possible if you have a single shared mutex protecting access (both read and write) to the is_blocked variables and make the sending program clear the counterpart's is_blocked variable, but I haven't run through all of the scenarios. I'll see if I can implement it myself with perl's threads (with and without a mutex) and try and replicate the undefined behaviour.

[EDIT] Sorry, I keep editing the above, we need a YACF-AOC Slack channel. I've created one but would this be a good idea or do people want to keep the discussion here?

[Oaky]

I'd join a Slack channel.

(click to show/hide)

I fixed my threaded implementation. 

It was pretty simple in the end - a judicious sprinkling of "with lock:" blocks around the snd, rcv and deadlock detection code fixed it.



BTW - this is quite nice: Javascript 18b solver

[Oaky]

(click to show/hide)

I tried to second-guess the part 2 question while writing my MapWalker.  I thought that he was either going to ask for the number of times I crossed another pipe, or the number of turns I made, so I kept track of the times I went under another pipe and the times I changed direction.  I was wrong.  Number of steps was one metric I hadn't maintained during part 1.

This was one of those (there was at least one last year: Reindeer Medicine?) where I decided not to use a feature of the input and test data which wasn't explicitly a part of the description.  In both my input data and the example data, there are no examples where two pipes are directly side by side (they always have at least one space between - i.e. "| |" rather than "||").  The only difference it would have made to my code would have been in the crossing detection, though, so it's irrelevant anyway.

[Greenbank]

(click to show/hide)

I think it's possible if you have a single shared mutex protecting access (both read and write) to the is_blocked variables and make the sending program clear the counterpart's is_blocked variable, but I haven't run through all of the scenarios. I'll see if I can implement it myself with perl's threads (with and without a mutex) and try and replicate the undefined behaviour.

Yep, as expected.

Without a mutex it randomly detects an early deadlock (at a whole load of values below the actual answer, not just 127). It works correctly about 1 in 10 times for me.

If I clear the is_blocked variable when sending (without mutex protection) it never detects a deadlock.

With a mutex, and protecting the send/receive code with that mutex, it works fine.

The horror: http://www.greenbank.org/misc/aoc/2017_18t_mutex.txt

(I should really minimise the snd/rcv stuff done inside the mutex lock.)

I hate perl threads/mutexes.

[Ben T]

(click to show/hide)

No, I know it's impossible to detect IF there isn't comms between them. But I took it as a challenge to implement deadlock detection... by having some form of communication between them.
The basis of it is:
...

(click to show/hide)

The race condition I can see is that you check to see if you can dequeue something without having anything locked, so the order could be:-

p0 check to see if anything on queue from p1, nothing
p1 puts something on queue for p0
p1 attempts a receive and checks to see if anything on queue from p0, nothing
p1 enters deadlock check code
p0 tries to enter deadlock check code but fails as p1 has it locked and so it all exits, despite there being something on p0's queue

(Based on a quick scan of that code...)

(click to show/hide)

ah.... Yes I see, thanks, so I suppose I need to extend the test-lock-retest logic to the "is it deadlocked" test. Illustrates just how fiddly threading synchronization is.

[Greenbank]

(click to show/hide)

And here's a hacky TCP version (uses 127.0.0.1 port 7777 for comms).

http://www.greenbank.org/misc/aoc/2017_18_tcp.txt

cat input | ./18_tcp.pl 0 &
cat input | ./18_tcp.pl 1 &

Or enable the various print statements that are commented out in the code and run them in separate terminal windows.

Deadlock detection is simply when a program hits a rcv and doesn't receive anything for 5 seconds.

Pre-exit sleep() is there to prevent p0 from exiting before p1 has finished checking the socket (since the code doesn't handle exceptions on sockets properly) and getting to its own exit code (and printing the answer).

[Greenbank]

Relatively simple today (day 20).

(click to show/hide)

Was expecting many more iterations to be required. For my input part (a) settled down after 414 iterations and part (b) was done in just 38 iterations. I did 10,000 iterations just to be sure, takes a few seconds but wanted to be sure.

Will now look for an analytical method for part(a) rather than brute forcing it. I guess it'll work by looking at the minimum manhattan 'distances' of the accelerations first, then minimum manhattan distances of the velocities as a tie breaker, then minimum manhattan distances of the starting positions if there is a tie on those two.

[EDIT]
Thinking about it, it's not quite that simple when it comes to position...

p=< 3,0,0>, v=< 0,0,0>, a=<1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>

Same magnitude of acceleration and velocity but p1 will always be closer despite starting further away (because it first travels towards the origin rather than p0 which travels away).

[EDIT2] Doh. Missed the most obvious way of doing part a (no iterations required although still need to pick a number n rather than doing it purely analytically), but then I guess my brain was expecting a need to do it by iterations for part (b) (and doing part (b) non-iteratively would have been interesting...)

[David Martin]

I must have something wrong with my iterations as it is taking a long time and not finding collisions.

(click to show/hide)

I started by assuming that the lowest acceleration wins. But forgot to consider multiple equally low options. Having failed the first time it was trivial to find the alternative.

[David Martin]

*blush* Silly bug. Not updating z coordinate. Now solved.

[Diver300]

Day 20
First part was solved with one run through the data.

(click to show/hide)

For this part the initial position isn't relevant.
I first thought that the speed wasn't relevant but if there is a tie on the acceleration, the initial velocity matters.
I ran through all particles finding the smallest Manhattan acceleration. For a tie, where any axis that had zero acceleration, the Manhattan total of the velocities was used to decide.

My plan probably only works where the smallest accelerations have zero accelerations in some axes.

[Greenbank]

Day 20
First part was solved with one run through the data.

(click to show/hide)

For this part the initial position isn't relevant.
I first thought that the speed wasn't relevant but if there is a tie on the acceleration, the initial velocity matters.
I ran through all particles finding the smallest Manhattan acceleration. For a tie, where any axis that had zero acceleration, the Manhattan total of the velocities was used to decide.

My plan probably only works where the smallest accelerations have zero accelerations in some axes.

(click to show/hide)

You can't ignore position. Consider this case:-

p=< 3,0,0>, v=< 0,0,0>, a=<1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>

Same magnitude of acceleration and velocity but p1 will always be closer (after the first iteration) despite starting further away (because it first travels towards the origin rather than p0 which travels away).

[Diver300]

Day 20
First part was solved with one run through the data.

(click to show/hide)

For this part the initial position isn't relevant.
I first thought that the speed wasn't relevant but if there is a tie on the acceleration, the initial velocity matters.
I ran through all particles finding the smallest Manhattan acceleration. For a tie, where any axis that had zero acceleration, the Manhattan total of the velocities was used to decide.

My plan probably only works where the smallest accelerations have zero accelerations in some axes.

(click to show/hide)

You can't ignore position. Consider this case:-

p=< 3,0,0>, v=< 0,0,0>, a=<1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>

Same magnitude of acceleration and velocity but p1 will always be closer (after the first iteration) despite starting further away (because it first travels towards the origin rather than p0 which travels away).

True. I'm not claiming that my algorithm for part 1 would work with all possible inputs.

[Oaky]

(click to show/hide)

hmm... my part 2 is not working and I don't know why.

It works fine on the example, and seems to converge on my input in 36 iterations, but the answer is not accepted.

On my own input, I don't see any collisions that arent simply pairs of particles, although my algorithm does detect the three way collision in the example.

Code: [Select]

iteration        1: count = 1000
iteration       10: count = 998
iteration       18: count = 996
iteration       35: count = 994
iteration       36: count = 992
and there it sits.... 

[Greenbank]

(click to show/hide)

More than 40% of my particles collided. Sometimes as many as 9 at once.

8 in total seems very few.

PM me your input (or email - alex @ <yacfusername> . org) and I'll give you a co-ordinate where lots of stuff happens. (If you want that kind of help.)

[Pickled Onion]

(click to show/hide)

There were a number of schoolboy errors that were easy to slip up on in part 2. I thought I'd got them all, and the test data was working well, but I forgot that even if you put integers as the keys of a perl hash it will still sort lexically. Oops.

But yes, there will be more than 8 collisions. I had ~350, and up to 26 at once.

So Oakers, what's your strategy?

[Diver300]

Day 20 b

(click to show/hide)

I gave each particle a collision time, starting at a large number.
I through each particle 3 times for each time interval
First to detect collisions by comparing each particle's positions with each other particles, where the collision time of the other was >= current time
If there was a match, the collision time was set to current time.

Second time through I did the newtonian dynamics

Third time though I counted the uncollided particles.

I just ran and displayed 100 time intervals. Everything stopped changing at about 40.

Interestingly, all collisions were within a Manhattan distance of 127 of the origin.

[David Martin]

(click to show/hide)

I created a list of particles. I then created a list of indexes of the list of particles.
I then check the positions of all the particles in the list of indices with a hash (by hashing the position and adding to the list of particles at that position) and iterate the particle as I check it's position.
If the list of positions is shorter than the list of current particles (the list of indices) then I remove from the list of indices every particle that is in a position list longer than 2.

Repeat till a convergence criteria is reached (number of consecutive steps with no collisions). If I was keen I could set a smaller convergence criteria and check that particles are not converging as a limit. But I didn't.

All code on github at https://github.com/davidmam/aoc2017

[Greenbank]

(click to show/hide)

I parsed the last of particles and created a multi-dimensional array, one row per particle (so the row index is particle number since they started at 0) and columns for: px, py, pz, vx, vy, vz, ax, ay, az
I also create a perl hash (a.k.a. dict in most other languages) to hold the particle numbers that have collided and are out of the game.
each iteration:-
__initialise an empty perl hash to store the location of each particle (this is initialised each iteration)
__for each particle that has not already been marked as collided (this is just checking for non-existence of a key in the hash)
____calculate its new velocity (vx+=ax; vy+=ay; vz+=az;)
____calculate its new position (px+=vx; py+=vy; pz+=vz;)
____check if position as a comma separated string exists in the location hash (e.g. "1,2,7")
______if it doesn't then store the particle's location in the location hash with the value being the particle number, e.g. "1,2,7" -> 0
______if it does match then the current particle is marked as collided and so is the particle number stored in the location hash for this position
At the end of the code I just have to count the number of keys in the collided hash to see how many particles collided, and take this away from the total number of particles to get the answer

I could easily have stored the collided state as a 10th column in the original array, but storing it in a hash meant I could count the number of entries with a simple bit of code 'scalar(keys %collided)' rather than having to loop through the array to count them.

[Ben T]

 how have you all identified the state where won't be any more collisions for part b, ( or changes in closest to origin for a)?
Did you identify merely a point at which there probably won't be any more or that there can't possibly be?

(click to show/hide)

I identified a "quiescent" state where all the particles have the same sign of p, v and a (but obviously not as each other) (thus are moving and accelerating away from the origin) and also that the particle with the lowest magnitude of position also has the lowest magnitude of velocity, thus can't possibly ever "overtake" another one. That seems to work for b as well but thinking about it I can't see how it proves there can't ever be another collision, only that the closest one will always remain so.

[Greenbank]

Day 21 looking meaty...

(click to show/hide)

I didn't bother looking to identify whether there was a chance of another collision.
I didn't see any more collisions after 38 iterations, and ran it for 10,000. Since the answer I posted was correct I never bothered doing any more work on it.
But, yes, it would be quite easy to contrive an input with a single pair of particles that didn't collide for hundreds of thousands of steps just to catch people out.

[David Martin]

Definitely requiring more thought. First time this year in the top 1000

(click to show/hide)

OK, this took some thinking. Eventually I determined a solution and then part b was a simple extension.
There are at maximum 8 transformations for each pattern including the identity. By generating a list of transforms and then applying them in turn to each cell until one matched a transformation key, it was straightforward.

I could have generated a hash of all possible patterns from the input data and my list of transforms - that would have saved some time and made the code a bit more compact.

(click to show/hide)

There is a temptation with a small number of iterations to try and shortcut. The full version doesn't take long unoptimised (a few seconds)

[Greenbank]

Day 21.

Correct answer for part (a), wrong answer for part (b).

The madness begins.

[David Martin]

Off by one in your iteration count?