AOC++

[Ben T]

(click to show/hide)

I think you are double counting. You only need to count the excess (or the missing) presents, not both.
Otherwise yes. Calculate the average (which is an integer unless my number generation is wrong) and then the number of packages that need to be moved to either make up the deficits, or reduce the surpluses *but not both* or you will be counting when a present leaves one sleigh and when it arrives in the other.

(click to show/hide)

I get 1258 for part 2

I almost fell for the double counting trap but caught it when testing with an input of:-

0 1 1 2 1 1 1 1 1

which obviously only requires a single present to be moved to balance it out.

(click to show/hide)

997

[Greenbank]

(click to show/hide)

Ah yes, 997. I calculated the right number for each paper but then evened out the number of presents already in the sleigh, rather than presents of the same paper between sleighs).

[Greenbank]

OK here's a good one for you.

Did them all. First one quite simply, runs in 0.004sec.

Part 2 I get the answer in 11.3sec (thanks to using libgmp).

(click to show/hide)

$ cat a.c
#include <gmp.h>
#include <stdio.h>

int main(int argc, char **argv )
{
        mpz_t r;
        mpz_init( r );
        mpz_fac_ui( r, atoi(argv[1]) );
        printf( "pc = %lu\n", mpz_popcount( r ) );
        return( 0 );
}
$ gcc a.c -o a -lgmp
$ time ./a 30254975
pc = 338988211

real    0m11.221s
user    0m11.078s
sys     0m0.148s

Part 3 also rattles through in 84s (again thanks to libgmp).

It'd be a completely different story if I was trying to implement those without using a bignum library.

Part 2 can be partially optimised:-

(click to show/hide)

If you implement the factorial yourself you can remove all factors of 2 as you multiply up, since they won't affect the number of bits set.

Will try and come up with my own puzzles in a bit. What I'll probably do is to extend the inputs of existing puzzles (from AOC 2015/16/17) to push them to the point that lots of optimisations have to be made for them to complete in a reasonable timeframe.

[Ben T]

That's good, yes I used the same lib, or the windows version of it MPIR.
Part 2 almost exactly the same as you (your better timings could be due to gcc being better at it than msvc which I'm using - what OS did you use?)
https://github.com/bjtaylor1/AoC2017/blob/bt1part2/BT1/BT1.cpp

Part 3 not sure if anything fundemantally faster than writing to stringstream but I could probably optimize by trimming all the zeros off the end
https://github.com/bjtaylor1/AoC2017/blob/bt1part3/BT1/BT1.cpp

You probably noticed that I sort of gave input numbers according to it running in a reasonable but not too quick time

[Oaky]

Will try and come up with my own puzzles in a bit. What I'll probably do is to extend the inputs of existing puzzles (from AOC 2015/16/17) to push them to the point that lots of optimisations have to be made for them to complete in a reasonable timeframe.

In that vein,  there's an interesting one here based on day 25:-

https://www.reddit.com/r/adventofcode/comments/7mvtsb/2017_day_25_turing_optimization/