Advent of Code

[grams]

(click to show/hide)

Top tip: If you're going for the floating point trig approach, you can use atan2 rather than atan and having to handle quadrants.

Also, should you ever need a sign(x) function in Python, you can use math.copysign(1,x)

(click to show/hide)

You can jump directly to the new x and y using the rotation matrix formula. No dicking about calculating intermediate distances or angles.

[Diver300]

Day 13 is more about maths than programming

(click to show/hide)

I used a really crude spreadsheet to find a way of combining the input data.
ID13 with and offset of 1 combined with ID59 with and offset of 4 can be combined and considered to be a single bus with ID 767 with offset of 417.

[Greenbank]

(click to show/hide)

Indeed, there's a name for it that should make it easier to look up and implement:-

(click to show/hide)

Chinese Remainder Theorem
And a further spoiler would be:

(click to show/hide)

There's no need to implement LCM (Least Common Multiple) as each of the bus numbers are prime so the lcm of any pair is just their product

I had the CRT algorithm from 2017 day 13 so it was just a quick copy of that.

The only real work remaining was building the individual relations properly before combining them.

[grams]

Are they trying to make me learn things? Fuck that.

[Greenbank]

Yep, and so this will be one of the first days with a big drop off between 1 star and 2 stars.

As I said on our internal company #advent-of-code Slack channel, today's problem is firmly over to the right of this scale:-

<------ "Programming" ----------------- "Computer Science" ---------------- "Discrete Mathematics" ------>

There's usually a good 2 or 3 each year that require something not usually covered in general "programming" or "Comp Sci".

Ob-xkcd:-

[Davef]

Day 13 part 2, keeping to my terse programming, 1 loop, 1ish lines, no function calls, no Chinese takeaways.

(click to show/hide)

// _a[] is array of nn ints with x replaced with 1
// const int x=1;
// int _a[] = {67,7,x,59,61};
// int *a = _a;
// int nn=5;

__int64 t = 1;
__int64 s = 1;

for (int c = 0; c < nn; )
{ t+=(*a==1)?0:s;s*=((t+c)%*a)?1: (c++,*a++) ; }

return t;

I seem to have smileys. How to I get rid ?

This is quite efficient. For my part 2 data it loops 1000 times which is microseconds.

[Greenbank]

I seem to have smileys. How to I get rid ?

Modify the post, expand the "Additional Options" box below it, check the "Don't use smileys" checkbox.

[Davef]

I seem to have smileys. How to I get rid ?

Modify the post, expand the "Additional Options" box below it, check the "Don't use smileys" checkbox.

I don’t seem to have those options. I put some spaces in. Is there some [] tags you can use? Even with the extra spaces I feel I am within the 80 character limit so I can keep the source code on one punch card.

[Croft]

Yep, and so this will be one of the first days with a big drop off between 1 star and 2 stars.

As I said on our internal company #advent-of-code Slack channel, today's problem is firmly over to the right of this scale:-

<------ "Programming" ----------------- "Computer Science" ---------------- "Discrete Mathematics" ------>

There's usually a good 2 or 3 each year that require something not usually covered in general "programming" or "Comp Sci".

Not sure I agree. It doesn’t require knowledge of that theorem and is quite computable with a fairly simple approach. Davef’s is a nice example of that.

We often see a similar pattern develop around the mid and later puzzles. The fastest and most experienced people spot a theory or solution from computer science or maths, share their observations on reddit. Others struggle for a bit, consult reddit, see lots of discussion on theorem X, and assume it is required for solution.

Eric is quite careful not to require such knowledge to derive a solution, even if it can help. We saw similar last year with the Slam Shuffle (day 22) that did allow solutions without detailed knowledge of modular arithmetic, even if it made spotting a solution easier.

[Greenbank]

I don’t seem to have those options. I put some spaces in. Is there some [] tags you can use? Even with the extra spaces I feel I am within the 80 character limit so I can keep the source code on one punch card.

Are you using a browser to view the forum or something like Tapatalk?

You should be able to avoid it using code tags I guess.

Code: [Select]

Does this appear as a smiley? 8)


[Davef]

If anyone is interested in how my simple solution to 13 day 2 works ...

(click to show/hide)

The basic problem is to find a (very large) number that satisfies some rule.

Suppose your numbers are 17 67 231 ...

The initial approach is to start at 1 and keep trying with increments of 1

After 17 attempts you find the number 17 which satisfies your first requirement (but unfortunately no others). You could carry on looking one at a time for something that matches the first and second requirement, but you can skip some as you quickly realise only every 17th number will satisfy criteria 1, so you can change your step size to 17 and carry on until you find an answer that satisfies 17 and 67. At this point you can increase your step size to 17x67 and when you find the next 17x67x231

You are soon leaping through the numbers skipping billions at a time.

[Greenbank]

Yep, and so this will be one of the first days with a big drop off between 1 star and 2 stars.

As I said on our internal company #advent-of-code Slack channel, today's problem is firmly over to the right of this scale:-

<------ "Programming" ----------------- "Computer Science" ---------------- "Discrete Mathematics" ------>

There's usually a good 2 or 3 each year that require something not usually covered in general "programming" or "Comp Sci".

Not sure I agree. It doesn’t require knowledge of that theorem and is quite computable with a fairly simple approach. Davef’s is a nice example of that.

We often see a similar pattern develop around the mid and later puzzles. The fastest and most experienced people spot a theory or solution from computer science or maths, share their observations on reddit. Others struggle for a bit, consult reddit, see lots of discussion on theorem X, and assume it is required for solution.

Eric is quite careful not to require such knowledge to derive a solution, even if it can help. We saw similar last year with the Slam Shuffle (day 22) that did allow solutions without detailed knowledge of modular arithmetic, even if it made spotting a solution easier.

Sure, but my point is that in pretty much every case the solutions that people come up with (like Davef's above) are just implementing simple (and/or non-optimal) cases of the underlying theorem.

(click to show/hide)

Such an algorithm wouldn't be guaranteed to return the lowest possible answer if not all of the bus numbers were pairwise co-prime. (Eric has obviously chosen the bus numbers to be primes in everyone's input so that it is much easier.)

If you want to just get the two stars on each day and stop then that's fine, but you're missing out on learning something extra (which is one of the other goals of Eric's puzzles). It's entirely optional though.

For example, Davef's solution may complete part 2 in ~1000 iterations (rather than trillions), but it's possible to get the answer in a lot fewer iterations than that.

[Greenbank]

If anyone is interested in how my simple solution to 13 day 2 works ...

(click to show/hide)

The basic problem is to find a (very large) number that satisfies some rule.

Suppose your numbers are 17 67 231 ...

The initial approach is to start at 1 and keep trying with increments of 1

After 17 attempts you find the number 17 which satisfies your first requirement (but unfortunately no others). You could carry on looking one at a time for something that matches the first and second requirement, but you can skip some as you quickly realise only every 17th number will satisfy criteria 1, so you can change your step size to 17 and carry on until you find an answer that satisfies 17 and 67. At this point you can increase your step size to 17x67 and when you find the next 17x67x231

You are soon leaping through the numbers skipping billions at a time.

(click to show/hide)

I think the differences I'm talking about are easily summed up by how people's code would handle a seemingly simple input that's designed to be difficult for solutions that don't use the ideal underlying algorithm/theorem. For example, how does your code handle this pathological input:-

3,1000000000000037

You can see that trying to find a solution for the 1000000000000037 bus by counting up 3 at a time is not going to be computeable in a reasonable timeframe.

The more people attempt to 'optimise' it by going "ah, but with big values like this I can see that I can spot that and skip a whole bunch of values in one go and make it much faster" the more they are actually working their way towards the "proper" generalised algorithm/theorem that works in an optimal manner in all cases.

[Davef]

If anyone is interested in how my simple solution to 13 day 2 works ...

(click to show/hide)

The basic problem is to find a (very large) number that satisfies some rule.

Suppose your numbers are 17 67 231 ...

The initial approach is to start at 1 and keep trying with increments of 1

After 17 attempts you find the number 17 which satisfies your first requirement (but unfortunately no others). You could carry on looking one at a time for something that matches the first and second requirement, but you can skip some as you quickly realise only every 17th number will satisfy criteria 1, so you can change your step size to 17 and carry on until you find an answer that satisfies 17 and 67. At this point you can increase your step size to 17x67 and when you find the next 17x67x231

You are soon leaping through the numbers skipping billions at a time.

(click to show/hide)

I think the differences I'm talking about are easily summed up by how people's code would handle a seemingly simple input that's designed to be difficult for solutions that don't use the ideal underlying algorithm/theorem. For example, how does your code handle this pathalogical input:-

3,1000000000000037

You can see that trying to find a solution for the 1000000000000037 bus by counting up 3 at a time is not going to be computeable in a reasonable timeframe.

The version I initially wrote sorted the numbers and worked largest first. It made little difference on the sample so I posted a simplified version.

Longer version with presorting (should start with step=a[0] too)

(click to show/hide)

int *idx = new int[nn];
        int nz = 0;

for (i = 0; i < nn; i++)
idx = i;

c_idx = a;
 qsort(idx, nn, sizeof(int), comp13);

for (i = 0; i < nn; i++)
{
if (!a[idx]) break;
DoLogF("%d", idx);
}

nn = i;

DoLogF("nn reduced to %d", i);

// start with the largest
__int64 t = 1;
__int64 step = 1;

int found = 0;
for (; found < nn; )
{
t += step;
int ii = idx[found];
int id = a[idx[found]];
if (((t+ii)%id)==0) { found++; step *= id; }
}

[Croft]

Sure, but my point is that in pretty much every case the solutions that people come up with (like Davef's above) are just implementing simple (and/or non-optimal) cases of the underlying theorem.

I agree, which is what I really like about AoC. It is possible to get those gold stars (and so not necessarily a drop-off in puzzle competitions), but the process encourages us to find out more. What better way for to introduce Theorem X by inviting us to 'discover' it via our own implementation that uses a (possibly compromised) version of it? This is pretty much the gold standard in teaching - "create" is better than "discover" is better than "show" is better than "tell".

This year's so far has been better than most in that respect. Few have been hard in the sense of preventing casual programmers from finding a solution, but many have invited further thought on ways of refining / generalising.

[Greenbank]

The version I initially wrote sorted the numbers and worked largest first. It made little difference on the sample so I posted a simplified version.

Sure, but I wrote that particular pathological case specifically for the version of the algorithm you posted.

I know your algorithm would work (and be much quicker than most) for all of the example inputs within AoC but, as I've said before, I'm talking about people choosing to use AoC to learn how to solve the general case and not just get the two stars each day before moving on.

If you provided an algorithm that worked largest case first I can provide a different pathological case that will attempt to maximise runtime for that version of the algorithm.

For most problems this back and forth can be repeated again and again until the program tends to be an implementation of the optimal algorithm.

You should try the https://onlinejudge.org/ coding puzzles. The difference between AoC and those is that with the OnlineJudge ones you don't get to see the final input your program is tested against, you submit your code (in whatever language you want) for that one. The examples that are given are all quite simplistic and the input your program is actually tested on is specifically crafted to stretch the designs of most programs to the limit. It's much harder when anything less than an optimal solution just comes back with "Time exceeded, execution aborted" each time.

[Croft]

(click to show/hide)

Such an algorithm wouldn't be guaranteed to return the lowest possible answer if not all of the bus numbers were pairwise co-prime.

(click to show/hide)

Maybe I'm missing something, but surely if the bus numbers are not pairwise co-prime, there is no solution regardless of algorithm (e.g. {5,10} will never arrive a minute apart).

[Greenbank]

(click to show/hide)

Such an algorithm wouldn't be guaranteed to return the lowest possible answer if not all of the bus numbers were pairwise co-prime.

(click to show/hide)

Maybe I'm missing something, but surely if the bus numbers are not pairwise co-prime, there is no solution regardless of algorithm (e.g. {5,10} will never arrive a minute apart).

(click to show/hide)

Correct that there can't be a solution to {5,10} but what about:-

5,x,x,x,x,10

?

(I think I've got the right amount of x's for it to have a solution)

[Croft]

Ah, yes of course ^.

That kind of sloppy thinking on my part is why I'll never be any good at those blind coding challenges.

[grams]

Day 13:
https://docs.google.com/spreadsheets/d/1AqziDqaSP6ThPImbihOYHoUNlIHToVUPxhCX_A_a2ks/edit?usp=sharing

(click to show/hide)

I could sort of see the pattern but couldn't get it straight in my head until I read Davef's comment about skipping billions at a time.

It worked on all the test samples but got stuck on the real data. I spent ages thinking I'd run into a floating point rounding error in google sheets, or maybe it needed thousands of iterations.

But running Davef's C code* against mine I discovered that reusing the "next bus" approach from Part 1 (rounding up using CEILING()) wasn't working when it was the third bus that matched the pattern (bus 17 in 40 minutes). I changed that to a MOD(), which almost worked but it turns out the MOD function has an artificial limit, so I had to roll my own. I finally got the right answer.

(* btw int nn=sizeof(_a)/sizeof(int); makes putting in test data much easier)

And I haven't learnt anything new about primes.

[tonycollinet]

Well Day13 stretched my capability to logic to it's limit. My head now officially hurts. I'm in the camp of no comp_sci training, and weak engineering maths so just have to puzzle it out.

Pleased I didn't look at spoilers though.

(click to show/hide)

import math

def CalcLcm(a, b):
    return abs(a*b) // math.gcd(a, b)
# start get data
input_file = open("13Input.txt", "r")
data = [(line.strip()).split(",") for line in input_file]
input_file.close()

depart = int(data[0][0])
busses = data [1]

max = depart
min = [0,max]
int_busses = []
for bus in busses:
    if bus != "x":
        wait = int(bus)-depart % int(bus)
    if wait < min [1]: min = [ int(bus), wait]
    if bus !="x": print (bus, wait, min)
print ("Answer P1 ", min[0]*min[1])

#part 2
tstamps = []

for index, bus in enumerate(busses):
    if index > 0:
        if bus!="x":tstamps.append([int(bus), index])
tmp = [[int(busses[0]),0]]
tstamps.sort()
tstamps = tmp + tstamps
print (tstamps)
lcm = tstamps [0 ][0 ]
answer = tstamps [0 ][1 ]

for bus in tstamps[1:]:
    notfound = True
    while notfound:
        answer += lcm
        need_remain = bus[0 ] - bus[1]%bus[0 ]
        if (answer+lcm) % bus[0 ] == need_remain:
            answer+= lcm
            notfound = False
            lcm = CalcLcm (lcm, bus[0 ])
    print (answer, answer% tstamps [0 ][0 ], answer//bus[0 ]*bus[0 ], answer%bus[0 ], bus[1])

[tonycollinet]

Lots of talk about theorems above, and now I've completed would be interested to learn more. Can anyone point out what theorem is applicable to day 13, and ideally a link to a primer of some sort.

Ta.

[Greenbank]

Lots of talk about theorems above, and now I've completed would be interested to learn more. Can anyone point out what theorem is applicable to day 13, and ideally a link to a primer of some sort.

It's in this post: https://yacf.co.uk/forum/index.php?topic=94710.msg2568783#msg2568783

[Ben T]

If anyone is interested in how my simple solution to 13 day 2 works ...

(click to show/hide)

The basic problem is to find a (very large) number that satisfies some rule.

Suppose your numbers are 17 67 231 ...

The initial approach is to start at 1 and keep trying with increments of 1

After 17 attempts you find the number 17 which satisfies your first requirement (but unfortunately no others). You could carry on looking one at a time for something that matches the first and second requirement, but you can skip some as you quickly realise only every 17th number will satisfy criteria 1, so you can change your step size to 17 and carry on until you find an answer that satisfies 17 and 67. At this point you can increase your step size to 17x67 and when you find the next 17x67x231

You are soon leaping through the numbers skipping billions at a time.

(click to show/hide)

I think the differences I'm talking about are easily summed up by how people's code would handle a seemingly simple input that's designed to be difficult for solutions that don't use the ideal underlying algorithm/theorem. For example, how does your code handle this pathological input:-

3,1000000000000037

You can see that trying to find a solution for the 1000000000000037 bus by counting up 3 at a time is not going to be computeable in a reasonable timeframe.

The more people attempt to 'optimise' it by going "ah, but with big values like this I can see that I can spot that and skip a whole bunch of values in one go and make it much faster" the more they are actually working their way towards the "proper" generalised algorithm/theorem that works in an optimal manner in all cases.

(click to show/hide)

You can actually evaluate the buses in descending order so in this case you would start off by skipping 1000000000000037 first

[tonycollinet]

Lots of talk about theorems above, and now I've completed would be interested to learn more. Can anyone point out what theorem is applicable to day 13, and ideally a link to a primer of some sort.

It's in this post: https://yacf.co.uk/forum/index.php?topic=94710.msg2568783#msg2568783

Thanks - missed that in the nested spoilers