Advent of Code

[tonycollinet]

Key learning point for day 9, as in most tests:

Read the fecking question 

[Greenbank]

Had the time to redo my day 9 properly.

(click to show/hide)

Usual paranoia that the O(n) sliding window algorithm used in part 2 may not always work (it does as long as you don't have any negative numbers).

[Diver300]

Day 10 was quite interesting.

(click to show/hide)

I did part 1 on a spreadsheet, where sorting is two clicks.

For part 2 I realised that each time there is a step of 3 jolts, it effectively splits the problem into "above" and "below" the 3 jolt gap.

I then saw that the biggest run of 1-jolt gaps was 4, and I worked out how many ways there are to cover runs of 1 to 4 1-jolt gaps by writing down the possibilities. It's only 7 for a run of 4.

Then I used the spreadsheet to work out the lengths or the runs of 1-jolt gaps, used a look-up to find how many ways that run can be covered. The answer was just the product of all those look-up results.

[Greenbank]

Spent far too long on part 2 as I was distracted by a work call where I had to be paying attention for most of it.

Got the answer with similar observations to Diver300 above.

[Davef]

I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.

[Greenbank]

Well yes, getting the two stars the bare minimum, but I rarely ever stop there.

Other things to consider are:
a) Does it handle exceptions or assume the input data is clean?
b) Will it work on slightly different input (eg, what would your code for today [2020 Day 10] have done if the input consisted of the numbers to 1 to 8)?
c) Will it be performant on pathalogical cases of inputs of the same magnitude
d) Will it be performant/correct on inputs of a much greater magnitude
...etc...

[Ben T]

(click to show/hide)

Code: [Select]

        static async Task Run(string[] args)
        {
            long desiredTotal = long.Parse(args[0]);

            var numbers = new List<long>();
            string line;
            while((line = await Console.In.ReadLineAsync()) != null)
            {
                numbers.Add(long.Parse(line));
                while(numbers.Sum() > desiredTotal)
                {
                    numbers.RemoveAt(0);
                }

                if(numbers.Sum() == desiredTotal)
                {
                    await Console.Out.WriteLineAsync($"{numbers.Min() + numbers.Max()}");
                    return;
                }
            }
        }


(click to show/hide)

part 1:
sort -n day10.txt | awk '{if($1-prev==1) ones++; if($1-prev==3) threes++; prev=$1} END {print ones*(threes+1)}'

part 2: pretty standard combinations alg (apart from to change int->long when it overflowed and returned a negative)

Code: [Select]

    public class Day10
    {
        private static ConcurrentDictionary<long[], long> cache = new ConcurrentDictionary<long[], long>(new Comparer());
        public static async Task Run(string[] args)
        {
            var numbersList = new List<long>();
            string line;
            while((line = await Console.In.ReadLineAsync()) != null)
            {
                numbersList.Add(long.Parse(line));
            }
            numbersList.Insert(0, 0);
            numbersList.Add(numbersList.Max() + 3);
            numbersList.Sort();
            var combinations = cache.GetOrAdd(numbersList.ToArray(), CalculateCombinations);
            await Console.Out.WriteLineAsync(combinations.ToString());
        }

        private static long CalculateCombinations(long[] remaining)
        {
            if(remaining.Length <= 1) return 1;
            long combinations = 0;
            for(var i = 1; i < remaining.Length; i++)
            {
                if(remaining[i] <= remaining[0] + 3)
                    combinations += cache.GetOrAdd(remaining.Skip(i).ToArray(), CalculateCombinations);
                else break;
            }
            return combinations;
        }

    }

    class Comparer : IEqualityComparer<long[]>
    {
        public bool Equals([AllowNull] long[] x, [AllowNull] long[] y) => x.SequenceEqual(y);

        public int GetHashCode([DisallowNull] long[] obj)
        {
            int hashCode = 31;
            foreach(var i in obj) hashCode = HashCode.Combine(hashCode, i);
            return hashCode;
        }
    }



[Greenbank]

(click to show/hide)

Tweaked my code to handle pathalogical cases:-

Code: [Select]

$ seq 1 73 | time ./10.pl
Part 1: d1=73 d3=1 tot=73
Part 2: 12903063846126135669
0.00user 0.00system 0:00.00elapsed 50%CPU (0avgtext+0avgdata 9248maxresident)k
0inputs+0outputs (0major+617minor)pagefaults 0swaps
(Any more than 73 and the output is > 2^64 and I can't be bothered to deal with that.)

Before the tweaks my solution would take more than second to do the output for an input of 1..30, no chance of it ever returning with an input of 1..73

[grams]

Day 9:
https://docs.google.com/spreadsheets/d/1­aRLwJyPDhppCY4Xuy6ciW_zAutiHcRFAGpK4CkQF­yy4/edit?usp=sharing

Day 10 part 2:
https://docs.google.com/spreadsheets/d/1­2uXNKlJWxkxXb80ATMF3YRxS9fdXDgycL_ViGti3­gu0/edit?usp=sharing

I populated the lookup tab by figuring out what numbers would make the two examples work. That was enough to make the real data work.

I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.

I think they must deliberately generate the data to allow simpler approaches to work. Seems unnecessary to go beyond that.

It is just for fun after all.

[Greenbank]

I think they must deliberately generate the data to allow simpler approaches to work. Seems unnecessary to go beyond that.

It is just for fun after all.

Indeed, as I said above, there's a challenge in going beyond it. (But then that's easier for me as programming has been my job for years.)

And, without going beyond the two stars you may not learn about lovely things such as:

(click to show/hide)

Tribonacci numbers

[tonycollinet]

Well that (day 10) had me scratching my head for a bit.

I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.

The data is set up so that you have to do it that way....

(click to show/hide)

My 'exhaustive' combination method was generating about 100K solutions per second. Assuming a trillion possible answers, this  was going to take about 10 (24 hour) days to complete and then would probably have been wrong the first time around (in fact, the actual answer was >>1 trillion - I'd have been waiting more than 100 years ).

The first part of the question is designed to show the way. You are asked to calculate how many step 3's there are. These then become the points within the data that allow you to break it into a multiple of some much smaller combination sets.

(click to show/hide)

def FindCombinations (jolt,target,start):
    global data
    global solutionCount
    newJolt = 0
   
    for index, adaptj in enumerate( data [start:] ):
        jdif = adaptj - jolt
        if jdif < 4 and jdif >0:
            newJolt = jolt+jdif
            if newJolt == target:
                solutionCount +=1
                return True
            elif newJolt < target:
                FindCombinations (newJolt, target, start+index)
    return False

# start
input_file = open("10aInput.txt", "r")
#data = [(line.strip()).split() for line in input_file]
data = [int(line.strip()) for line in input_file]
input_file.close()

data.sort()

# part 1
jolt = 0
difCounters = [0,0,0,0]

for adapterJ in data:
    jdif = adapterJ - jolt
    if jdif < 4 and jdif >= 0:
        jolt += jdif
        difCounters [ jdif ] += 1
    else:
        print (jolt, adapterJ, "ERROR ERROR ERROR")
        break

difCounters [3]+= 1 #built in adapter
jolt += 3
   
print (jolt, difCounters, difCounters [1]* difCounters [3]) #part 1 answer


#part 2
#find targets
targets = [[0,0,0]]

for index, jolt in enumerate (data):
    if index+1 < len(data) and data[index+1]==jolt+3:
        targets.append ([jolt, index, 0])

#add final targets for internal adapter
       
targets.append ([data[len(data)-1],len(data)-1,0])

print (targets)
solutionCount = 0
totalSolutions = 0

for tIndex in range (1, len (targets)):
    startJolt = targets [tIndex-1] [ 0 ]
    targetJolt = targets [tIndex] [ 0 ]
    dataStart = targets [tIndex-1] [1]
    FindCombinations ( startJolt, targetJolt, dataStart )
    targets [tIndex][2] = solutionCount
    solutionCount = 0
    if tIndex == 1:
        totalSolutions = targets [1][2]
    else:
        totalSolutions = totalSolutions * targets [tIndex][2]
 
print (targets)
print (totalSolutions) #answer part 2

[Davef]

How do you do this spoiler malarkey ?

[tonycollinet]

Click the Sp button next to the

quote

button.

[Davef]

Single sequential pass, ‘one line’ solution to day 10 part 2.

(click to show/hide)

// works with sequences of up to 7 ones so
// more than enough for sample input
// single pass with freaky obfuse arithmetic !

__int64 part2(int *a, int n)
{
__int64 r=1;

qsort(a, n, sizeof(int), s);

int c = -1;
for (; n; a++) if (c += a[1]-*a==1,!--n||a[1]-*a==3) { r*=c>=0?(2<<c)-(c*c-c>>1):1;c=-2; }

return r;
}

Edit: Realised it was a bit longwinded so abbreviated
Edit: could remove the curly brackets and use comma operator, but that might make it less readable.

[Ben T]

How do you do this spoiler malarkey ?

[spoiler]the code[/spoiler]

[Davef]

How do you do this spoiler malarkey ?

[spoiler]the code[/spoiler]

Thanks. Done now. See above.

[Diver300]

Day 11 done.

I keep making the mistake of writing something like:-

Code: [Select]

} while ( done = 0 ) when I mean

Code: [Select]

} while ( done == 0 )

[Davef]

Day 9:
https://docs.google.com/spreadsheets/d/1­aRLwJyPDhppCY4Xuy6ciW_zAutiHcRFAGpK4CkQF­yy4/edit?usp=sharing

Day 10 part 2:
https://docs.google.com/spreadsheets/d/1­2uXNKlJWxkxXb80ATMF3YRxS9fdXDgycL_ViGti3­gu0/edit?usp=sharing

I populated the lookup tab by figuring out what numbers would make the two examples work. That was enough to make the real data work.

I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.

I think they must deliberately generate the data to allow simpler approaches to work. Seems unnecessary to go beyond that.

It is just for fun after all.

I agree - but the fact there is a simple solution because of a quirk of the data - it would be nice if that quirk was guaranteed by the spec. It would only need one more sentence that would not really give much away.

[Davef]

Day 11 done.

I keep making the mistake of writing something like:-

Code: [Select]

} while ( done = 0 ) when I mean

Code: [Select]

} while ( done == 0 )

If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)

[Diver300]

Day 11 done.

I keep making the mistake of writing something like:-

Code: [Select]

} while ( done = 0 ) when I mean

Code: [Select]

} while ( done == 0 )

If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)

I'll try the (0==done) route.

[Davef]

Day 11 done.

I keep making the mistake of writing something like:-

Code: [Select]

} while ( done = 0 ) when I mean

Code: [Select]

} while ( done == 0 )

If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)

I'll try the (0==done) route.

As I read “!” as “not” .... while (!done) out loud is “while not done”

[Greenbank]

Day 11 done.

I keep making the mistake of writing something like:-

Code: [Select]

} while ( done = 0 ) when I mean

Code: [Select]

} while ( done == 0 )

If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)

Personally I think "0 == done" looks ugly, I much prefer the "!done" option but if I have to check for a specific value I still write "done == 1256" rather than "1256 == done".

If you use the right compiler options you get a warning for

Code: [Select]

} while ( done = 0 ), plus a load of other warnings for things you probably need to fix too:-

Code: [Select]

$ cat x.c
int main(void)
{
        int x=0;
        do { } while( x = 0 );
}
$ gcc x.c -o x
$ gcc -ansi -pedantic -Wall x.c -o x
x.c: In function ‘main’:
x.c:4:2: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
x.c:5:1: warning: control reaches end of non-void function [-Wreturn-type]


[Greenbank]

2020 day 11 done easily enough, but I haven't worked out the right trick to make it fast. (Bit busy with real work at the mo.)

Forgot the "cellular automata" item from the list of expected AoC challenges.

[grams]

Day 11 Part 1 is here. It takes about 20 minutes to recalculate 100 iterations, if it doesn't crash, and that's with hardcoding the cell references to make it easier*. I had a typo in my adjacent seat calculating formula that didn't cause a problem on the test data and had to redo all of it. Grrrr.

https://docs.google.com/spreadsheets/d/1QYtHllA3OYWupEnHUZmtXDV07zLlpniRcSfaBZpyDPg/edit?usp=sharing

(click to show/hide)

Not sure I can be arsed doing part 2. But it looks like you only have to calculate which 8 seats each seat cares about once, which should make it no slower than part 1.

(* will, if Google Sheets has a proper recalculations optimiser. I'm increasingly doubtful it does)

[Davef]

Perhaps it was a tribute the great John Conway who sadly died earlier this year.