Advent of Code

[Ben T]

Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.

My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.

Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?

initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.

I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.

hmm, weird. Rewrote it in c++ and it gets the correct answer in under a second, with about 14,000 games. No idea what the previous program was doing.

[Davef]

Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.

My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.

Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?

initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.

I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.

hmm, weird. Rewrote it in c++ and it gets the correct answer in under a second, with about 14,000 games. No idea what the previous program was doing.

Your computer is faster than my old laptop.

[Davef]

My day 23 part b cups speedy solution minimal version which after initialisation is technically one line of c (no curly brackets). It s about as fast as it can be too

(click to show/hide)

Code: [Select]


// puzzle input
const char *s = "389125467";
int n0 = strlen(s), n = 1000000;

// an array of 1 million integers.
int *a = new int [n+1];

// store puzzle input
for (int i=0,c=0,y=0,f=0,d=0; i < n0; i++) a[s[i]-'0']=s[(i+1)%n0]-'0';

// and the extra 1 million ish entries
for (i++,a[s[i-2]-'0'] = i,a[n] = *s-'0'; i<n ; i++) a[i]=i+1;

// do the business 10 million times
for (i=0,c=s[0]-'0';i<10000000&&(y=a[a[a[c]]],f=a[c]);a[c]=a[y],a[y]=a[d],a[d]=f,c=a[c],i++)
  for (d=c;d==c||d==f||d==a[f]||d==y; d=(d-1<1)?n:d-1) ; // empty loop, max 4 decrements to dest

return (__int64)a[1] * a[a[1]];  // return result



[Greenbank]

(click to show/hide)

If you have to iterate to find loop size, you might as well use the same loop to generate the private key as a simple multiplication and modulus is cheap:

long findPrivate (long card, long door)
{
  while (card != cardPublic)
  {
    card = (7*card) % 20201227;
    door = (doorPublic*door) % 20201227;
  }
  return door;
}

Sure that gets you the answer, but far from optimal.

For this problem even the most naive solution gives the answer quite quickly, but there are better ways to do it (as someone has mentioned already). If the question had much bigger numbers the naive solution would not have been workable.

If you want to get something to the power of 8 you can do it the naive way and use 7 multiplications and 7 modulus operations, e.g.

x=7
x*=7 ; x%=m;
x*=7 ; x%=m;
x*=7 ; x%=m;
x*=7 ; x%=m;
x*=7 ; x%=m;
x*=7 ; x%=m;
x*=7 ; x%=m;

Or you can do it in 3 multiplications and 3 modulus operations:-

x=7
x*=x ; x%=m; # current value is x^2 mod m
x*=x ; x%=m; # current value is x^4 mod m
x*=x ; x%=m; # current value is x^8 mod m

To raise to an arbitrary exponent you effectively look at the binary representation of the exponent and sometimes multiply in another x before you square the number you have as you go along.

So to raise something to the power 12413864 (for example) you can do 12413863 mulitply/modulus operations, or just ~30 by using the more optimal way.

As always with AoC, you can stop as soon as you've got the answer, or you can choose to delve a little deeper.

[Pickled Onion]

Done. Not helped by the fact that the dot net debugger crashes on the Apple M1 chip when stepping off a break point. Had to go back to old school debugging by print statements.

Now to go back to 2019 - I stopped at day 15. This year's seems tamer than previous years, or perhaps it's just easier with practice.

[Ben T]

For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check

[Davef]

For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check

Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply

[Ben T]

For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check

Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply

Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...

[Ben T]

Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply

Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...
[/quote]
Got it now, thanks davef - was a bug in setting up the initial data.
Was using a linked list and wasn't setting up the initial data correctly, so if the input was 315679824, I was setting e.g. 2.next = 4, and 4.prev = 2, and setting 4's next to 10.... but forgot to set 10's prev to 4.
Might try and create a generic linked list class, as the code is a bit of a mess and a pita to debug.

[Ben T]

Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply

Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...

Got it now, thanks davef - was a bug in setting up the initial data.
Was using a linked list and wasn't setting up the initial data correctly, so if the input was 315679824, I was setting e.g. 2.next = 4, and 4.prev = 2, and setting 4's next to 10.... but forgot to set 10's prev to 4.
Might try and create a generic linked list class, as the code is a bit of a mess and a pita to debug.

My somewhat more verbose than your code:

(click to show/hide)

Code: [Select]

class cup
{
public:
    cup* prev;
    cup* next;
    int num;
};

int main(int argc, char** argv)
{
    int cupcount = 1000000;
    cup* cups = new cup[cupcount+1];

    int len = strlen(argv[1]);
    for (int i = 1; i <= cupcount; i++)
    {
        cups[i].prev = i == 1 ? cups+cupcount : cups+i-1;
        cups[i].next = i == cupcount ? cups+1 : cups+i+1;
        cups[i].num = i;
    }

    //arrange the (first) 10 cups according to the input
    for(int i = 1; i <= len; i++)
    {
        int cupnum = (int)(argv[1][i-1] - '0');
        int prevcupnum = i > 1 ? (int)(argv[1][i-2] - '0') : cupcount;
        cups[cupnum].prev = cups + prevcupnum;

        int nextcupnum = i < len ? (int)(argv[1][i] - '0') :
            (cupcount > len ? len + 1 : (int)(argv[1][0] - '0'));
        cups[cupnum].next = cups + nextcupnum;
    }
    if(cupcount > len) cups[len+1].prev = cups + (int)(argv[1][len-1] - '0'); // << the ommission of this line was the bug

    int firstcup = (int)(argv[1][0] - '0');
    cups[cupcount].next = cups+firstcup;

    int moves = 0;
    cup* current;

    for(current = cups+firstcup; moves++ < 10000000 ;)
    {
        cup* pickup_first = current->next;
        cup* pickup_last = pickup_first->next->next;

        //detach the ones picked up

        pickup_first->prev->next = pickup_last->next;
        pickup_last->next->prev = pickup_first->prev;

        int dest = current->num;

        do {
            if(--dest == 0) dest = cupcount;
           
        } while(
                pickup_first->num == dest ||
                pickup_first->next->num == dest ||
                pickup_first->next->next->num == dest);

        cup* insertion_before = cups+dest;
        cup* insertion_after = insertion_before->next;

        insertion_before->next = pickup_first;
        pickup_first->prev = insertion_before;
        pickup_last->next = insertion_after;
        insertion_after->prev = pickup_last;

        current = current->next;
       
    }

    // part 1

    // int count = 1;
    // for(cup* c = (cups+1)->next; count++ < cupcount; c = c->next)
    // {
    //     std::cout << c->num;
    // }
    // std::cout << std::endl;

    // part 2 (cup count and num moves changes)
    std::cout << cups[1].next->num << ", " << cups[1].next->next->num << " = " << (long)cups[1].next->num * cups[1].next->next->num << std::endl;


[Greenbank]

Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)

[Davef]

Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)

It is a flawed security system if it can be broken by some arithmetic !

[Pickled Onion]

(day 15 2019)

Late to it today as I'd been out all day at a family party. Chased a few silly bugs in a dreadful implementation but got it done.

The way I'd implemented meant it was only a very small change required to do part 2.

Loving the use of IntCode computers to provide inputs (i.e. the maze) that can't be analysed directly.

(click to show/hide)

2445 moves to discover the entire map, CPU time was 2.783s including the IntCode computer process time

Bah! Mapped out the route to the Oxygen by finding the walls and marking any dead-ends on backtrack. This gave all the map that was needed and the route back to origin was then the only one left.

Now for part two I need the whole map! 

[Greenbank]

Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)

It is a flawed security system if it can be broken by some arithmetic !

And I hadn't bothered optimising it. Down to 240usec now.

It's not just arithmetic, it's searching the full search space to solve a^e = x mod m (i.e. finding e for a given a, x and m). It just does it in a more efficient way with a lot fewer calculations.

(In this example 7^e = x mod 20201227)

The security system is a little better if you use much bigger primes. 20201227 is a tad on the small size.

If I give you even a 256-bit prime such as 90903494037702082433862493857994179414185677901950849383197625766750833066817 then it's not so quick or easy.

[Davef]

Here is my day 25. I think it is quite efficient both in terms of performance and typing and is surprisingly readable. With the exception of the sea monster I have them all down to a handful of lines of code. Just fine tuning my 4d life.

(click to show/hide)

for (__int64 c=2084668,d=3704642,m=20201227,e,f,g,h=g=f=e=1;e!=c&&f!=d;e=e*7%m,f=f*7%m,g=g*c%m,h=h*d%m)
   ;
return e==c?h:g;

Or if you were happy to take a punt on which key was easier to find you could remove f and g but if one was much easier than the other it could be much slower

(click to show/hide)

for (__int64 c=2084668,d=3704642,m=20201227,e,h=e=1;e!=c;e=e*7%m,h=h*d%m)
   ;
return h;

[Greenbank]

Can't see it mentioned anywhere but there's Project Euler too, for anyone wanting to continue with problems throughout the year.

I've made a thread for it here: https://yacf.co.uk/forum/index.php?topic=117960.0 so not to clutter up this one (which we can save for AoC).

[Pickled Onion]

Can't see it mentioned anywhere but there's Project Euler too, for anyone wanting to continue with problems throughout the year.

I've made a thread for it here: https://yacf.co.uk/forum/index.php?topic=117960.0 so not to clutter up this one (which we can save for AoC).

Thanks, but I think I'm going to be busy going over the previous years' ones I gave up on at the time.

[Pickled Onion]

Day 17 (2019). Another example of READ THE TEXT, then READ IT AGAIN.

The "obvious" route, of going straight across each intersection, might have led to a final set of instructions that could not be compressed to fit the input instruction rules.

Having to then go back and make the first part of part 2 output every possible permutation until one that could be compressed adequately would have been less fun.

A transcription error meant I missed the obvious route (and didn't look for spoilers). So I implemented the "every permutation" with linked lists and recursion. It was a rather laborious, but popped out the answer very quickly.

[Croft]

It's that time of year again. Anyone doin'?

https://adventofcode.com/

Private leaderboard code that YACF people have been using for a few years now: 48462-ea506236

[Pingu]

First two days weren't too hard. But then I probably think that every year 

[perpetual dan]

We did a bit of this as learning with interns at work. I seem to have done four days now, luring me in

[Diver300]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

[perpetual dan]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

(click to show/hide)

Or buy a bigger computer. But your approach was faster for me as well!

[Diver300]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

(click to show/hide)

Or buy a bigger computer. But your approach was faster for me as well!

(click to show/hide)

Lots of puzzles from previous years started with something that could be solved with brute force, but then part 2 took amount of computing power needed beyond my PC. Therefore from the start I was on the lookout for something that took less computing power. The final answer for day 6 was around 1.6 million million, so having to have arrays that big is a large fraction of a PC's power. Simply having an array of nine numbers that are each that big is much quicker.

[perpetual dan]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

(click to show/hide)

Or buy a bigger computer. But your approach was faster for me as well!

(click to show/hide)

Lots of puzzles from previous years started with something that could be solved with brute force, but then part 2 took amount of computing power needed beyond my PC. Therefore from the start I was on the lookout for something that took less computing power. The final answer for day 6 was around 1.6 million million, so having to have arrays that big is a large fraction of a PC's power. Simply having an array of nine numbers that are each that big is much quicker.

My day job tends to call on that kind of optimization, so i had a similar predisposition

In contrast, my solution for today's feels quite clunky. Though coding before coffee might be an issue.