Advent of Code

[grams]

Day 14, part 2

(click to show/hide)

Having slept on it, I realised the overwrites can be looked for trivially after doing a single stable sort by address, which is orders of magnitude faster than anything I did yesterday.

Day 15, part 2

(click to show/hide)

Google Sheets is limited to 5 million cells across all tabs. I don't really see how I can do 30 million iterations.

[tonycollinet]

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.

I tried the same in python, and it increased  execution time from 13s to nearly 15s

EDIT

(click to show/hide)

Suggests the dictionary lookup is less an overhead than interpreting the additional if-then-else.

[freeflow]

My Day 15 Part 2 is forecast to complete in around 4 hours

[Davef]

My whopping array takes a few milliseconds

(click to show/hide)

int n = (b==1) ? 30000000 : 2020;

const char *s = "0,14,6,20,1,4";
int *a = new int[n];  // big array!
memset(a, 0, n*sizeof(int));
 
// parse input string
for(int i=1;*s ;s++)if(*s>='0')*a=10**a+(*s-'0');else{a[2+*a]=i++;*a=0;}

// find solution
for(;i<n;){a[1]=*a;*a=a[2+*a];*a=*a?i-*a:0;a[a[1]+2]=i++;}
   
return *a;

[Greenbank]

My whopping array takes a few milliseconds

You can shave a tiny bit off if you remove the memset(). Linux should automatically give you zeroed memory.

[grams]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

[Greenbank]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-

(click to show/hide)

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

int mem[30000000];

int main( int argc, char **argv) {
        int turn=0;
        int last=-1;
        while( argv[turn+1] ) {
                last=atoi(argv[turn+1]);
                mem[last]=turn+1;
                turn++;
        }
        while( turn < 30000000 ) {
                int say=0;
                turn++;
                if( mem[last] > 0 ) say = turn-1-mem[last];
                mem[last]=turn-1;
                last=say;
        }
        printf( "%d\n", last );
        return(0);
}

Simply put, it initialises entries in an array to the turn number when that number was last seen.
The default of 0 will mean that the number has not been seen yet.

Each turn we default the "say" to 0
Unless we find the previous number has been mentioned before, in which case we calculate how many goes ago it was mentioned.
Only after we've done this do we set the 'last seen' entry for a number to the previous turn.
The we update the last item we saw to be the number we just said

Code: [Select]

$ gcc -ansi -pedantic -Wall -O4 15fast.c -o 15fast
$ time ./15fast 2 1 3
3544142

real    0m0.540s
user    0m0.468s
sys     0m0.072s


[Davef]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-

(click to show/hide)

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

int mem[30000000];

int main( int argc, char **argv) {
        int turn=0;
        int last=-1;
        while( argv[turn+1] ) {
                last=atoi(argv[turn+1]);
                mem[last]=turn+1;
                turn++;
        }
        while( turn < 30000000 ) {
                int say=0;
                turn++;
                if( mem[last] > 0 ) say = turn-1-mem[last];
                mem[last]=turn-1;
                last=say;
        }
        printf( "%d\n", last );
        return(0);
}


Code: [Select]

$ gcc -ansi -pedantic -Wall -O4 15fast.c -o 15fast
$ time ./15fast 2 1 3
3544142

real    0m0.540s
user    0m0.468s
sys     0m0.072s


Mine was specifically designed to be unreadable.

[Davef]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

Basically the same as yours but a big array instead of a dictionary And then I have pissed around to use as few characters as possible and make it as unreadable as possible!

e.g.
Int a[3000000]
a[19] = 1

How I actually wrote it first time with more characters  ...

(click to show/hide)

// parse the input and set it up with e.g.a[14]=1
for (; *s; i++)
{
n = strtol(s,&s,10);
if (*s) {s++;a[n] = i;}
}

// find solution
for (; i <= nn; i++)
{     
int oldn = n;
   
if (n = a[n])  // look it up or 0
          n = i - n - 1; // if found replace with offset

a[oldn] = i-1;  // store
}

[tonycollinet]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-

(click to show/hide)

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

int mem[30000000];

int main( int argc, char **argv) {
        int turn=0;
        int last=-1;
        while( argv[turn+1] ) {
                last=atoi(argv[turn+1]);
                mem[last]=turn+1;
                turn++;
        }
        while( turn < 30000000 ) {
                int say=0;
                turn++;
                if( mem[last] > 0 ) say = turn-1-mem[last];
                mem[last]=turn-1;
                last=say;
        }
        printf( "%d\n", last );
        return(0);
}

Simply put, it initialises entries in an array to the turn number when that number was last seen.
The default of 0 will mean that the number has not been seen yet.

Each turn we default the "say" to 0
Unless we find the previous number has been mentioned before, in which case we calculate how many goes ago it was mentioned.
Only after we've done this do we set the 'last seen' entry for a number to the previous turn.
The we update the last item we saw to be the number we just said

Code: [Select]

$ gcc -ansi -pedantic -Wall -O4 15fast.c -o 15fast
$ time ./15fast 2 1 3
3544142

real    0m0.540s
user    0m0.468s
sys     0m0.072s


Where I am struggling with a lot of these C implementations - I can't see where your input arrives in the code - the first 5 (or whatever) numbers.

[Davef]

I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.

Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.

So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:

(click to show/hide)

<?php
$lookupTable = array( 19 => 1 , 0 => 2, 5 => 3, 1 => 4, 10 => 5 );
$lastNumber = 13;

for ($i = 6; $i <= 30000001; $i++) {
        if (array_key_exists($lastNumber, $lookupTable)) {
                $previousIndex = $lookupTable[$lastNumber];
                $nextNumber = $i - $previousIndex;
        } else {
                $nextNumber = 0;
        }
        $lookupTable[$lastNumber] = $i;
        if (($i % 10000) == 0 or ($i == 2020)) {
                echo $i . ": " . $lastNumber . "\n";
        }

        $lastNumber = $nextNumber;
}
?>

Davef, do you want to talk us through your code a little bit? My head indirectly hurts.

Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-

(click to show/hide)

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

int mem[30000000];

int main( int argc, char **argv) {
        int turn=0;
        int last=-1;
        while( argv[turn+1] ) {
                last=atoi(argv[turn+1]);
                mem[last]=turn+1;
                turn++;
        }
        while( turn < 30000000 ) {
                int say=0;
                turn++;
                if( mem[last] > 0 ) say = turn-1-mem[last];
                mem[last]=turn-1;
                last=say;
        }
        printf( "%d\n", last );
        return(0);
}

Simply put, it initialises entries in an array to the turn number when that number was last seen.
The default of 0 will mean that the number has not been seen yet.

Each turn we default the "say" to 0
Unless we find the previous number has been mentioned before, in which case we calculate how many goes ago it was mentioned.
Only after we've done this do we set the 'last seen' entry for a number to the previous turn.
The we update the last item we saw to be the number we just said

Code: [Select]

$ gcc -ansi -pedantic -Wall -O4 15fast.c -o 15fast
$ time ./15fast 2 1 3
3544142

real    0m0.540s
user    0m0.468s
sys     0m0.072s


Where I am struggling with a lot of these C implementations - I can't see where your input arrives in the code - the first 5 (or whatever) numbers.

In my obscure version at post 1004 above there is a ‘for’ loop after the comment that says parse input

It reads the input string
const char *s = "0,14,6,20,1,4";
 one ascii character at a time and converts to numbers and puts the numbers in the array. Normally I would use a library function for that but instead I convert the asciii to decimal by subtracting ‘0’ (and repeatedly multiplying by 10 if more than one char)

Edit: looking at greenbanks, his input is coming in on the command line. C programs main() function are invoked with an array of arguments in char *argv[]

[Diver300]

On day 15 part 1, I had a list of numbers, and for 2020 numbers it didn't take long.

Once I set the same code to run to 30,000,000 numbers it was heading for all day with the computer fan running flat out, and it was slowing down.

(click to show/hide)

Then I realised that a list of positions was a much better way than a list of numbers. There was no need to search through a big array for a particular number. All that was needed was selecting the nth item. The array was only a bit smaller than the 30,000,000, but it only had about 3,600,000 entries.

[tonycollinet]

Edit: looking at greenbanks, his input is coming in on the command line. C programs main() function are invoked with an array of arguments in char *argv[]

That'll be it - thanks.

[grams]

Once I set the same code to run to 30,000,000 numbers it was heading for all day with the computer fan running flat out, and it was slowing down.

So I've worked out that (for my data), to get to 30 million by brute force you'd need to do 71 trillion comparisons. Whereas for 1 million it only needs to do 92 billion. Which is 771, and computer science tells us that's the same as 900.

So to finish in under an hour it needs to get to a million in under 4 seconds, or 23 billion comparisons per second. It's not implausible you could get there with SIMD and/or running it on a GPU.

ETA: I've got the inner loop down to three x86 assembly instructions (load+compare, decrement pointer, conditional jump) and it still takes 45 seconds to get to a million, suggesting a 10 hour completion time. Bah.

[Davef]

Once I set the same code to run to 30,000,000 numbers it was heading for all day with the computer fan running flat out, and it was slowing down.

So I've worked out that (for my data), to get to 30 million by brute force you'd need to do 71 trillion comparisons. Whereas for 1 million it only needs to do 92 billion. Which is 771, and computer science tells us that's the same as 900.

So to finish in under an hour it needs to get to a million in under 4 seconds, or 23 billion comparisons per second. It's not implausible you could get there with SIMD and/or running it on a GPU.

ETA: I've got the inner loop down to three x86 assembly instructions (load+compare, decrement pointer, conditional jump) and it still takes 45 seconds to get to a million, suggesting a 10 hour completion time. Bah.

I think you have the problem the wrong way round. It should only take 30,000,000 loops

I have moved on to trying to squeeze my day 16 down in size. I feel it is going to spread to a couple of punch cards.

[grams]

I think you have the problem the wrong way round. It should only take 30,000,000 loops

I have the problem the right way round, which is O(n^2), and that's how I like it. I'm trying to figure out if computers are fast enough yet to JFDI, at least for n = 30 million.

[Davef]

I think you have the problem the wrong way round. It should only take 30,000,000 loops

I have the problem the right way round, which is O(n^2), and that's how I like it. I'm trying to figure out if computers are fast enough yet to JFDI, at least for n = 30 million.

Are you doing it with no storage then ?

With no storage it is O(n^2). With n integers of storage it is O(n)

[grams]

I'm storing the raw list of numbers and looking backwards until I find a matching number (or, worse, don't).

[Davef]

Day 16 2

(click to show/hide)

// const char *s = "departure location: 39-715 or 734-949 etc  assumes \r\n line separator
int part=0,i=0,i0=0,lr=0,z=0,m=0;
__int64 ret = 1;

int _a[100000];
memset(_a,0,sizeof(_a));

int *a = _a+20;
int *res = _a;

for (;z<6;s++)
{
for (int k=0;!*s&&k<20;k++) // process results when they are ready
{
for (int j=0,c=0,t=0;j<20;j++) if (!((m|res[k])&(1<<j))){c++;t=j;}
if (c==1){ret*=(t<6)?z++,a[lr+k+1]:1;m|=(1<<t);}
}

if (*s>47&&*s<58)a=10*a+*s-48; // build an integer from ascii
else if (a) // and do something with it
{ 
for (int ok=0,j=0;part==2&&!ok&&j<=lr;j+=2) // valid ticket ?
ok=a>=a[j]&&a<=a[j+1];

for (int t=0,k=0;part==2&&ok&&k<=lr;k+=2) // which fields?
{
t+=a>=a[k]&&a<=a[k+1];
if (k%4==2){if(!t)res[i-i0]|=1<<k/4;t=0;}
}

// assumes CRLF - otherwise change to 10 and checking s[1]
if (*s==13){i0=i+1;if(s[2]==13&&!part++)lr=i;} // next input section
i++;
}
}
return ret;

Better result processing using bitmask

[Davef]

I'm storing the raw list of numbers and looking backwards until I find a matching number (or, worse, don't).

Why ? The beauty of arrays is that they provide fast access via an integer key

(click to show/hide)

// parse the input and set it up with e.g.a[14]=1
for (; *s; i++)
{
n = strtol(s,&s,10);
if (*s) {s++;a[n] = i;}
}

// find solution
for (; i <= nn; i++)
{     
int oldn = n;
   
if (n = a[n])  // look it up or 0 - this is an assignment as well as test
          n = i - n - 1; // if found replace with offset

a[oldn] = i-1;  // store
}

[grams]

Why ? The beauty of arrays is that they provide fast access via an integer key

Idle curiosity.

Clearly the question was set with the expectation that many people would create a naive O(n^2) algorithm for Part 1 and then have to replace it with something at least O(n log n) to calculate Part 2 in reasonable time. But I reckon it's possible to run an O(n^2) solution for n = 30 million in reasonable time.

Day 16:

(click to show/hide)

For part 1, Google Sheets interpreted some - but not all - of the tickets as very large numbers and rounded them off, which took me ages to spot. Grrrrr.

Good thing no one uses spreadsheets for anything life or death.

[tonycollinet]

Day 16 done.

But I really don't enjoy the ones that result in a mess of data manipulation (how to code it) as distinct from puzzle solving (what do I need to code). It was more like work than fun.

(click to show/hide)

This is as it evolved. I can't be bothered to look if optimisation is possible.
********************************
# start get data
input_file = open("16Input.txt", "r")
data = [line.strip() for line in input_file]
input_file.close()

#format data
rules = []
tickets = []

section = "rules"
for d in data:
    if d!="":
        if section == "rules":
            if d.split()[0]=="your":
                section = "tickets"
            else:
                rules.append([d.split(": ")[0],     d.split(": ")[1].split(" or ")[0].split("-"),      d.split(": ")[1].split(" or ")[1].split("-")])
        else:
            dw1 = d.split()[0]
            if dw1!="" and dw1!="nearby":
                tickets.append(d.split(","))

#part 1
error_rate = 0

for tindex, ticket in enumerate(tickets):
    for val in ticket:
        value = int (val)
        valid = False
        for rule in rules:
            range1 = range(int(rule[1][0]),int(rule[1][1])+1)
            range2 = range(int(rule[2][0]),int(rule[2][1])+1)
            if value in range1 or value in range2:
                valid = True
        if not valid:
            error_rate += value
            tickets[tindex][0]="invalid"

print (error_rate) #Part 1

#Part 2

#Create a matrix of rules (rows) and fields (columns) which are vaild for the rule
rule_valid = []
for r in rules:
    rule_valid.append ([r[0]+"........................."[:-len(r[0])]])

for rindex, rule in enumerate(rules):
    fvcount = 0
    range1 = range(int(rule[1][0]),int(rule[1][1])+1)
    range2 = range(int(rule[2][0]),int(rule[2][1])+1)
    for field in range (len (tickets[0])):
        field_valid = True

        for tindex, ticket in enumerate(tickets):
            if ticket

• != "invalid":

                tick_f = int(ticket[field])
                if tick_f not in range1 and tick_f not in range2: #rule invalid for field on this ticket
                    field_valid = False
        if field_valid:
            rule_valid[rindex].append(1)
            fvcount+=1
        else:
            rule_valid[rindex].append(0)
    rule_valid[rindex].append(fvcount) #tag a count of how many fields are valid to the end of the rule row.

#scan the matrix to decide which field is applicable to which rule
available_flds = [True]*20
for valid_fld_cnt in range (21):
    for rindex, rv in enumerate(rule_valid):
        if rv[-1] == valid_fld_cnt:
            for field in range (len (tickets[0])):
                if rv[field+1]==1 and available_flds[field]:
                    rule_valid[rindex].append(field)
                    available_flds[field]=False

#print the buggers out, and calc the answer.
dep_multi = 1
for rv in rule_valid:
    print (rv)
    if rv[0][:9]=="departure":
        num = int(tickets[0][rv[-1]]) #field from my ticket
        dep_multi *= num

print (dep_multi)

[Greenbank]

Why ? The beauty of arrays is that they provide fast access via an integer key

Idle curiosity.

Clearly the question was set with the expectation that many people would create a naive O(n^2) algorithm for Part 1 and then have to replace it with something at least O(n log n) to calculate Part 2 in reasonable time. But I reckon it's possible to run an O(n^2) solution for n = 30 million in reasonable time.

Have implemented what I think is the fastest O(n^2) algorithm for day 15 part 2. So far:-

Code: [Select]

$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
t=106 turn=1500000
t=153 turn=1800000
t=208 turn=2100000
t=272 turn=2400000
t=347 turn=2700000

Each one of those lines represents 1% of the number of turns with the t value being the time in seconds it has been running.

Extrapolating I'd be happy if it's done in <24 hours.

[EDIT] The rate of change of the rate of change is about 10 seconds per 1%.

So extrapolating that gives 10 * 100 * 99 / 2 = 49500 seconds =~ 14h

[grams]

Day 16 done:
https://docs.google.com/spreadsheets/d/1t3jC4tIqWEm3IPSIk0FSWWqPeY4BrNc9HMUSfa0R2fg/edit?usp=sharing

Reasonably straightforward but a lot of steps and therefore a lot of annoying debugging cell reference typos.

[Greenbank]

Have implemented what I think is the fastest O(n^2) algorithm for day 15 part 2. So far:-

Code: [Select]

$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
t=106 turn=1500000
t=153 turn=1800000
t=208 turn=2100000
t=272 turn=2400000
t=347 turn=2700000

Each one of those lines represents 1% of the number of turns with the t value being the time in seconds it has been running.

Extrapolating I'd be happy if it's done in <24 hours.

[EDIT] The rate of change of the rate of change is about 10 seconds per 1%.

So extrapolating that gives 10 * 100 * 99 / 2 = 49500 seconds =~ 14h

It's exciting (and that updated prediction is looking quite accurate). Should be done inside an hour.

Code: [Select]

...
t=41498 turn=28800000
t=42355 turn=29100000
t=43223 turn=29400000
t=44095 turn=29700000

(The question is whether it will give the right answer! [Which should be 3544142 for the input I gave it.])