Advent of Code

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

I did actually a version that sorted first but I stripped it out to get my solution down to 80 characters.

[tonycollinet]

Realising (now) that lowest common multiplier wasn't actually needed in day 13 - still a question that came up:

Is it true that LCM (a,b,c,d...)

Is equal to

LCM(d,LCM(c,LCM(b,a)))

?? (Assuming I've got the brackets in the correct places  )

[Croft]

Yes.

Informally, because you can calculate LCM by finding the maximum prime factor exponent of each number and max more obviously satisfies the same property: max (a,b,c) = max (a, max(b,c))

[Davef]

Or that the lcm of a set of numbers is their product divided by their gcd. I find it easier to visualise the gcd in a  mental venn diagram of prime factors. It is fundamental that set intersection works this way from the colouring in I did at school.

[Davef]

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

Doesn’t your favourite theorem require the bus numbers to be relatively prime too ?

[Greenbank]

Doesn’t your favourite theorem require the bus numbers to be relatively prime too ?

The basic one yes, but the more generalised version works on non-co-prime moduli too.

[Ben T]

I think day 14 part 2's badly explained, I don't even get what the program's meant to be doing.

After applying the mask, four bits are overwritten, three of which are different, and two of which are floating. Floating bits take on every possible combination of values; with two floating bits, four actual memory addresses are written:

000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)
000000000000000000000000000000111010  (decimal 58)
000000000000000000000000000000111011  (decimal 59)
Next, the program is about to write to memory address 26 with a different bitmask:

address: 000000000000000000000000000000011010  (decimal 26)
mask:    00000000000000000000000000000000X0XX
result:  00000000000000000000000000000001X0XX
This results in an address with three floating bits, causing writes to eight memory addresses:

000000000000000000000000000000010000  (decimal 16)
000000000000000000000000000000010001  (decimal 17)
000000000000000000000000000000010010  (decimal 18)
000000000000000000000000000000010011  (decimal 19)
000000000000000000000000000000011000  (decimal 24)
000000000000000000000000000000011001  (decimal 25)
000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)

The entire 36-bit address space still begins initialized to the value 0 at every address, and you still need the sum of all values left in memory at the end of the program. In this example, the sum is 208.

"four actual memory addresses are written"... written with what?
"In this example, the sum is 208".... which of the above values sum to 208?

They seem to sum to 342 to me. Even if you only count each one once (26 and 27 are twice), they sum to 289.

How does he get 208?

[grams]

mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1

The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.

I can't see a sensible way of implementing it with a spreadsheet yet.

[Davef]

mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1

The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.

I can't see a sensible way of implementing it with a spreadsheet yet.

My first go splurged stuff all over the place but worked. I then redid it imagining I had a quantum processor using a superposition of quantum states. I then fell back through a wormhole to day 13 part 2.

[Davef]

Day 13 part 2, only loops 38 times rather than 1000 now, but I feel sorry for the person taking over code maintenance

(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 n=5;

__int64 p = 1;
__int64 s = 0;
 
for(i=n;i;p*=a[--i]);for(;i<n;i++,a++){if(*a>1){__int64 z=*a,d=z,t,q,e=0,f=1,w=p/ *a;while(w>1){q=w/z;t=z,z=w%z,w=t;t=e,e=f-q*e,f=t;}s+=(*a-i)*(f+(f<0)*d)*(p/ *a);}}

ret=s%p;

[Greenbank]

(click to show/hide)

Yeah, the 'worst' mask in my input had 9 X's and so that's 512 different addresses it could modify. Given that, I used to a recursive function to set the actual memory. If the address contained an X it would call itself twice replacing the X with a 0 and a 1. If it didn't contain an X it would set the bit of memory to the value provided.

Usual trick of using a hash/dict for memory rather than an array, as the memory in use can be quite spread out and sparse.

But, yes, I think I had to re-read the description about 10 times more than I usually do, it just wouldn't sink in at first.

[Davef]

(click to show/hide)

Yeah, the 'worst' mask in my input had 9 X's and so that's 512 different addresses it could modify. Given that, I used to a recursive function to set the actual memory. If the address contained an X it would call itself twice replacing the X with a 0 and a 1. If it didn't contain an X it would set the bit of memory to the value provided.

Usual trick of using a hash/dict for memory rather than an array, as the memory in use can be quite spread out and sparse.

But, yes, I think I had to re-read the description about 10 times more than I usually do, it just wouldn't sink in at first.

(click to show/hide)

That was the first approach. I then changed to not expanding the addresses at all and just keeping them with the Xs in as all you want is the total. when it comes to the final output if you have an address with say 8 Xs in and value 200 you add 51200 to you output. The complication is where two address overlap so you have to add corrective entries to negate the intersection (e.g. mem address 26 and 27 in the example). You can spot two addresses that intersect as they both have X at the same point but it gets messy

So for the example after reading input I would end up with have 3 entries in memory
.....X...x 100
......x      -100
.......x..xx  1

The total would be 208 ( 100x4 -100x2 1x8 )

[Ben T]

mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1

The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.

I can't see a sensible way of implementing it with a spreadsheet yet.

Oh, I see...
yeah you might have to wheel a programming language out.

[Lightning Phil]

mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1

The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.

I can't see a sensible way of implementing it with a spreadsheet yet.

Oh, I see...
yeah you might have to wheel a programming language out.

You can do bit operations in Google sheets.  Haven’t looked at what you need to do but bit manipulation via ORs ANDs, shifts etc should not stop you using sheets.

[grams]

You can do bit operations in Google sheets.  Haven’t looked at what you need to do but bit manipulation via ORs ANDs, shifts etc should not stop you using sheets.

That's not the problem. Part 1 was straightforward enough.

The problem is storing the intermediate results of each write, and combining the overwrites to get the final total. Without hashtables or nested loops or a 2^36 array.

There's probably some clever radical simplification of the problem.

[Davef]

You can do bit operations in Google sheets.  Haven’t looked at what you need to do but bit manipulation via ORs ANDs, shifts etc should not stop you using sheets.

That's not the problem. Part 1 was straightforward enough.

The problem is storing the intermediate results of each write, and combining the overwrites to get the final total. Without hashtables or nested loops or a 2^36 array.

There's probably some clever radical simplification of the problem.

You could have one column with memory addresses in an the values in the next. They are are just labels.

[tonycollinet]

Day 14 complete - less tricky than 13, but...

(click to show/hide)

Still had to think about how to sequence all the X in a part 2 address through all combinations.

For the memory, a python dictionary was useful.

At first I was surprised that the total for part 2 was lower than part 1 - then realised the memory contents were not increased by the mask as they were in P1.

**********************************************************
def AddLead36 (binary):
    if binary[:2] == "0b":
        tmp = binary [2:]
    else:
        tmp = binary
    tmp = "000000000000000000000000000000000000"[:36-len(tmp)]+tmp
    return "0b"+tmp

def ApplyMask (mask, number):
    mXto0 = int(mask.replace("X","0"),2)
    mXto1 = int(mask.replace("X","1"),2)

    return (number | mXto0) & mXto1

def WriteMem2Float (addr, value, mask):
    global mem2
   
    mXto0 = int(mask.replace("X","0"),2)
    addrfloat = AddLead36(bin(addr | mXto0))
    countX = 0
    for c in range (len (mask)):
        if mask[c:c+1]=="X":
            addrfloat = addrfloat[:c+2] + "X" + addrfloat[c+3:]
            countX += 1
   
    for genAdr in range (2**countX):
        sourcebits = AddLead36(bin (genAdr))
        sourcepos = len(sourcebits)-countX
        for c in range (len (mask)):
            if mask[c:c+1]=="X":
                fbit = sourcebits[sourcepos:sourcepos+1]
                addrfloat = addrfloat[:c+2] + fbit + addrfloat[c+3:]
                sourcepos+=1
       
        mem2 [int(addrfloat,2)] = value   
   
# start get data
input_file = open("14Input.txt", "r")
data = [(line.strip()).split(" = ") for line in input_file]
input_file.close()

#format data
df = []
for d in data:
    if d[0]=="mask":
        df_n = ["ma","0",d[1]]
    elif d[0][:4]=="mem[":
        tmp = d[0].split("[")[1]
        tmp = tmp[:len(tmp)-1]
        df_n = ["me",tmp,d[1]]
    else:
        print ("ERROR")
       
    df.append(df_n)


#Part 1 & 2 combined

mask = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
mem1 = {}
mem2 = {}
value1 = 0
value2 = 0

for index, d in enumerate(df):
    if d[0] == "ma":
        mask = d[2]
    elif d[0] == "me":
        addr = int(d[1])
        value1 = ApplyMask (mask,int(d[2]))
        value2 = int(d[2])
        mem1[addr] = value1
        WriteMem2Float (addr,value2,mask)
       
total1 = 0
for m in mem1:
    total1+=mem1[m]
print ("part 1: ",total1)

total2 = 0
for m in mem2:
    total2+=mem2[m]
print ("part 2: ",total2)

[Diver300]

Day 14 complete.

(click to show/hide)

For part 2 I suspected that the addresses wouldn't overlap, and spent too long checking whether that was the case. It wasn't
With 100 masks and, and up to 9 Xs in those masks, the total number of memory locations used is a tiny fraction of the 2^36 space, so I thought that they might not overlap.

If there was no overlap, the totals would be the memory values multiplied by 2^(number of Xs in mask)

My data had about 5% of the values replacing others.

It's not very difficult to have a list of addresses and a corresponding list of values. The lisst for my data were about 70000 long, so just over 2^16 and far easier to manage than 2^36

[grams]

Day 14 part 1. Relatively trivial.
https://docs.google.com/spreadsheets/d/1uprQs9jfVjy9C7WC-q9_iVRd9lz6VEts1kPm-iAzPaA/edit?usp=sharing

Day 14 part 2.
https://docs.google.com/spreadsheets/d/1wTfCJDeHbetXmXDTj6ZkR7Z_KBjIpG2dLe91rwaOyNg/edit?usp=sharing

(click to show/hide)

The first step is to apply the 0/1 bit mask. Pretty easy.

In the second step I generate all 70,000 writes and each address. If I had a more malleable data format, I'm sure this could be optimised away, but that's the opposite of what I have.

The real problem was the final step, de-duplicating to work out which values get overwritten. The MATCH() function 70,000 times over 70,000 rows would take literally days. The optimisation that worked was working out that only ca. 2,700 addresses actually get written to more than once, so if I only need to run the full de-duplication search on those.

And now I can go to bed (with 28 gold stars).

[tonycollinet]

Day 15 oddly trivial, even brute forcing part2. I assume there is a more intelligent method for that, but if there is, I haven't found it yet.

(click to show/hide)

Again, a dictionary has proven quite useful

***********************************************
numbers = {8:1,0:2,17:3,4:4,1:5}
turn = 6
lastnum = 12


while turn <30000000:
    if lastnum in numbers:
        num = turn-numbers[lastnum]
    else:
        num = 0

    numbers [lastnum] = turn
    turn += 1
    if turn%1000000==0:print (turn, lastnum, num)
    lastnum = num
   
print ("turn is ", turn, "number is ", num)

[Greenbank]

Occasionally there are 'easy' days to give people a break and let them catch up.

(click to show/hide)

I think the main thing today was teaching people that keeping every turn in an array and looping through the array to search for the previous mention wasn't going to work. Hence the use of a hash/dict to speed up this part of the searching.

The only "trick", as you spotted, was to add the previous turn to the hash after considering the current turn.

My perl solution takes close to 20s but perl's hashes are pretty generic and so integer->integer hash storage/lookup performance isn't optimised.

If I can get some time today I'll rewrite it in C to see how fast that can go.

I don't think there's any way of shorcutting the calculation. Various example series exists in OEIS with no mention of a way to generate arbitrary terms.

[tonycollinet]

Occasionally there are 'easy' days to give people a break and let them catch up.

(click to show/hide)

I think the main thing today was teaching people that keeping every turn in an array and looping through the array to search for the previous mention wasn't going to work. Hence the use of a hash/dict to speed up this part of the searching.

The only "trick", as you spotted, was to add the previous turn to the hash after considering the current turn.

My perl solution takes close to 20s but perl's hashes are pretty generic and so integer->integer hash storage/lookup performance isn't optimised.

If I can get some time today I'll rewrite it in C to see how fast that can go.

I don't think there's any way of shorcutting the calculation. Various example series exists in OEIS with no mention of a way to generate arbitrary terms.

(click to show/hide)

Interesting - I keep seeing talk of hashes, and have no idea what they are in this context. Google is... confusing. Is it simply another term for a dictionary?

[Greenbank]

(click to show/hide)

Interesting - I keep seeing talk of hashes, and have no idea what they are in this context. Google is... confusing. Is it simply another term for a dictionary?

Yes, a hash is another name for a dictionary. Different languages use different names.

Dictionaries, hashes, hashmaps, maps, ...

[Greenbank]

Rewrote it in C to see how quick I could get it:-

Code: [Select]

$ gcc -ansi -pedantic -Wall -O4 15.c -o 15
$ time ./15 2 3 1
2020: 78
30000000: 6895259

real    0m0.813s
user    0m0.761s
sys     0m0.052s


(click to show/hide)

Used a hybrid storage, an array for numbers below 100000 and a hash for anything above that. Previous pure hash version was ~2s.

[Croft]

(click to show/hide)

I spent too long on part 2 looking for repeated patterns in the hope of predicting a cycle. But here is a rather nice proof there can be no cycles in the sequence: https://youtu.be/etMJxB-igrc?t=310