Advent of Code

[Ben T]

17a was quite straightforward.
17b required minor thought but eventually succumbed to brute force

(click to show/hide)

Once you notice that 0 is always the first position, you only need to keep track of the insert when pos = 0. Nothing else matters. It then becomes a loop. There should be a way of readily checking which values would be applicable and going straight there but my maths is not up to that. runs in a few seconds so not much bother.

(click to show/hide)

Code: [Select]

current = (current + step + 1) % buff_len;
if (current == 0){buff [1] = i;}
That's all that I ran 50 million times. (starting at i = 1)
It takes about 3 seconds

(click to show/hide)

Interesting that they chose 50 million, I did a function of the type
f(n) = (f(n-1)+N)%n
and called it recursively but it threw a stack overflow at about 49million and something.

[Croft]

Ben T:

(click to show/hide)

If you modify f(n) so it also includes the previous value as a parameter, you make it tail-recursive, which in many languages should avoid stack overflow (it does not need to store anything on the stack).

[Ben T]

Ben T:

(click to show/hide)

If you modify f(n) so it also includes the previous value as a parameter, you make it tail-recursive, which in many languages should avoid stack overflow (it does not need to store anything on the stack).

(click to show/hide)

Really, interesting - so if I had:

static int N = 370; //(my puzzle input)

        static int F(int n)
        {
            if (n == 0) return 0;

            return ((F(n-1) + N) % n) + 1;
        }
        static void Main()
        {
            Console.WriteLine(F(50000000));
        }

how would I 'modify it to include the previous value as a parameter' ?
Because for that I need to call the function, for which I need the value for n-2, but to get that I need the value for n-3, ...... etc.

[Diver300]

Don't you need to increment buf_len?

Yes.

I put that after the conditional bit for some reason.

[Croft]

Ben T:

(click to show/hide)

if you count up rather than down your first call can be f(1,0) because we know the initial "previous value" is zero. You can either hard code the upper limit of 50000000 in the function or pass it in as a parameter.

[Greenbank]

Day 18.

Part a: Yet another psuedo CPU question. Boooring, or so I thought.

But part b was a lovely twist on it.

(00:15:45 from start to part a solution, 00:35:14 from start to part b solution, would have been a minute quicker if I'd read which answer I needed to give more closely.)

(click to show/hide)

I missed all of the clues as to what part b would be ("duet" and that "snd/rcv" generally stand for send/receive not sound/recover) in an effort to get part a done as quickly as possible.

Mind you, even if I had spotted that it wouldn't have changed my implementation for part a. As I'd implemented it it didn't take too much to pull the code into a subroutine acting on an object (rather than a bunch of global variables) so I could run two of them side-by-side with the snd/rcv instructions pushing/pulling items from a queue in the other program's object. Stall detection was pretty easy.

[Greenbank]

64 characters for part 2, including input data. 

I can get it down to 84 in perl, but then I'm not very good at code golf.

I look forward to comparing line noise tomorrow!

(click to show/hide)

$p=0;$i=0;while($i<50000000){$i++;$p=(($p+366)%$i)+1;$v=$i if($p==1);}print"$v\n";

Doh, obvious removal of initialisations...

while($i<50000000){$i++;$p=(($p+366)%$i)+1;$v=$i if$p==1;}print"$v\n";

while($i<5*10**7){$i++;$p=(($p+366)%$i)+1;$v=$i if$p==1;}print"$v\n";

69 chars

[David Martin]

First read the instructions..

(click to show/hide)

Straightforward though it took time to just write out all the functions.

(click to show/hide)

OK, rewrite to run two sets in parallel with rcv having the context switch between programs.
It then didn't end. Mostly due to me forgetting to remove the message from the message queue when I did the context switch, and not setting registers correctly. I'd set it to initialise all registers to the program id, not just one.
It then ran in next to no time at all.

[Pickled Onion]

64 characters for part 2, including input data. 

I can get it down to 84 in perl, but then I'm not very good at code golf.

I look forward to comparing line noise tomorrow!

(click to show/hide)

$p=0;$i=0;while($i<50000000){$i++;$p=(($p+366)%$i)+1;$v=$i if($p==1);}print"$v\n";

Doh, obvious removal of initialisations...

while($i<50000000){$i++;$p=(($p+366)%$i)+1;$v=$i if$p==1;}print"$v\n";

while($i<5*10**7){$i++;$p=(($p+366)%$i)+1;$v=$i if$p==1;}print"$v\n";

69 chars

(click to show/hide)

slow, using grep:

$l=1;print((grep{$c=1+($c+382%$l)%$l++;$c==1&&$_}(1..5e7))[-1]);

then basically the same as yours, with a couple of tricks to shorten:

$l=1;for(1..5e7){$c=1+($c+382)%$l++;$c==1&&print"\r$_"}

54 characters

[R_nger]

First read the instructions..

(click to show/hide)

Straightforward though it took time to just write out all the functions.

(click to show/hide)

OK, rewrite to run two sets in parallel with rcv having the context switch between programs.
It then didn't end. Mostly due to me forgetting to remove the message from the message queue when I did the context switch, and not setting registers correctly. I'd set it to initialise all registers to the program id, not just one.
It then ran in next to no time at all.

Should that be Day 18 ?

[Oaky]

(click to show/hide)

I coded part 1 with half an eye on the send/receive interpretation, creating a list of sent values and popping one off for the rcv part. So, once I'd written up the functions, it took very little time to adapt the code to part two.

I was also able to re-use functions from the day 8 vm which I wrote to allow registers or values in all of the appropriate areas.

I did, however, spend most of the day chasing two annoying bugs:

• I was popping the rcv value off the wrong end of the stack.
• A race condition in my threaded version of the solution

Once I fixed the first one, part 2 worked, running the two programs in a scheduler loop, switching between them whenever one was blocked.

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 :/

[David Martin]

First read the instructions..

(click to show/hide)

Straightforward though it took time to just write out all the functions.

(click to show/hide)

OK, rewrite to run two sets in parallel with rcv having the context switch between programs.
It then didn't end. Mostly due to me forgetting to remove the message from the message queue when I did the context switch, and not setting registers correctly. I'd set it to initialise all registers to the program id, not just one.
It then ran in next to no time at all.

Should that be Day 18 ?

That was probably one of the bugs..

[Greenbank]

Not much of a workout today. (Day 19). And scarily I wrote a 97 line perl program that ran first time with no syntax errors (but one minor logic error that my checking caught).

(click to show/hide)

I can only imagine part b is there to catch out people who tried to do the first part manually. You can't cheat either as the number of steps is greater than the number of non-whitespace characters in the puzzle input as some grid squares are passed over twice.

It was only 10s for me to add in a step counter and output that (although I had an off-by-one error so it cost me a minute to resubmit my answer, should have checked it against the example solution first!)

[David Martin]

Again, a lot of code for not much intellectual input - overengineered it but that isn't a bad thing.

(click to show/hide)

I  didn't look closely at the input so had all cases including letters immediately after corners and so on. A few silly mistakes but it got there without error once the silly things had been dealt with (starting off going N instead of S, and stripping all the whitespace off the end of lines when reading the input - D'Oh!)

[Greenbank]

(click to show/hide)

This was my logic error (the joys of copy-and-paste programming):-

...

Code: [Select]

        if( $dir eq "S" ) {
                $y+=1;
        } elsif( $dir eq "N") {
                $y-=1;
        } elsif( $dir eq "E" ) {
                $x+=1;
        } elsif( $dir eq "E" ) {
                $x-=1;
        } else {
                print "ARGH: DIR $dir\n";
                exit;
        }

Of course you can do the above in a more compact way and fewer lines, but when the program stopped with "ARGH: DIR W" I knew exactly where to look.

[David Martin]

Fortunately the input was well behaved, I had considered cases like two corners in consecutive steps, realised that the coding would be more involved and if it came across a not immediately tractable solution to print the local environment and ask for guidance. It didn't need to as there was at least one step between each corner.

[Croft]

A bit disappointed in the simplicity of Part 1. I was almost certain when doing part 1, that the second part was going to ask for the shortest path from start to destination point of part 1.

[David Martin]

By only taking known routes and adding corners where they cross.. I'm just expecting a humdinger tomorrow then.

[Pickled Onion]

Tripped up by having my packet fall off the end of the route and carry on going. The test data was fine as that took it off the circuit board and stopped, but on the actual circuit it found another path and carried on in circles. Oops.

[Greenbank]

Fortunately the input was well behaved, I had considered cases like two corners in consecutive steps, realised that the coding would be more involved and if it came across a not immediately tractable solution to print the local environment and ask for guidance. It didn't need to as there was at least one step between each corner.

Not sure why this would be a problem, there are no decisions to be made at any corners. Either you can continue on in a straight line still or you have to choose left or right (and there won't be a choice).

For example:-

Code: [Select]

  |
B++A
  ++

is unambiguous.

(click to show/hide)

My solution didn't care what the route characters were. As far as it was concerned it was either a space (not part of a route) or not a space (part of the route, and possibly a letter).

[Ben T]

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

[Greenbank]

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

[Ben T]

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

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:

while (!ThisThreadsQueue.TryDequeue(out valReceived))
{
    bool monitorEntered = false;
    try
    {
        if (!(monitorEntered = Monitor.TryEnter(deadlockCheck)))
        {
            // a deadlock is detected - as we failed to read, but the other thread owns deadlockCheck - hence is also waiting
            OtherThreadsQueue.Enqueue(null); //so that it knows we have detected a deadlock and also stops
            OtherThreadsSemaphore.Release();
            throw new DeadlockException();
        }
        ThisThreadsSemaphore.WaitOne();
    }
    finally
    {
        if (monitorEntered) Monitor.Exit(deadlockCheck);
    }
}
if(valReceived == null) throw new DeadlockException(); //the other thread detected a deadlock, so we should also stop

// we read a value
p.Registers[p.P1] = valReceived.Value;

There must be a situation in which it can encounter a false positive when doing the deadlock check, but I can't think up a MCVE and a sequence of steps through it (i.e. how fast does one thread progress compared to the other) that nails it.

[David Martin]

Fortunately the input was well behaved, I had considered cases like two corners in consecutive steps, realised that the coding would be more involved and if it came across a not immediately tractable solution to print the local environment and ask for guidance. It didn't need to as there was at least one step between each corner.

Not sure why this would be a problem, there are no decisions to be made at any corners. Either you can continue on in a straight line still or you have to choose left or right (and there won't be a choice).

For example:-

Code: [Select]

  |
B++A
  ++

is unambiguous.

but

Code: [Select]

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

[Greenbank]

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