Advent of Code

[Croft]

(click to show/hide)

Would have been much trickier if they'd included one or more stray points.

Calculate centroid (cx, cy) of point list.
For each point (x, y):
    if distance (cx, cy) to (x+vx, y+vy) > distance (cx, cy) to (x, y), remove it from point list

if bounding box of all (x+vx, y+vy) is > bounding box of all (x,y) HALT else repeat

[Greenbank]

(click to show/hide)

e.g. in my example where the areas go  56, 54, 57, 53, 13, 54.

I didn't encounter blips like that (i.e. 54, 57, 53 ).

It was monotonically decreasing to a minima and then monotonically increasing from there on.

Obviously if I'd hit a local minima I would have had to rejig the algorithm...

[Ben T]

(click to show/hide)

For example, try this input:-

Code: [Select]

position=<  -803,   948> velocity=<   5,  -6>
position=<  -927,   948> velocity=<   6,  -6>
position=< -1671,   824> velocity=<  12,  -5>
position=<   437,   576> velocity=<  -5,  -3>
position=<  1057,   824> velocity=< -10,  -5>
position=<  -555,   700> velocity=<   3,  -4>
position=<  -803,   576> velocity=<   5,  -3>
position=< -1423,   576> velocity=<  10,  -3>
position=<   -59,   700> velocity=<  -1,  -4>
position=< -1671,   948> velocity=<  12,  -6>
position=<  -927,   700> velocity=<   6,  -4>
position=<   933,  1072> velocity=<  -9,  -7>
position=<  1181,   824> velocity=< -11,  -5>
position=<   933,   824> velocity=<  -9,  -5>
position=<  1305,   824> velocity=< -12,  -5>
position=< -1051,  1072> velocity=<   7,  -7>
position=<   933,   700> velocity=<  -9,  -4>
position=< -1795,   700> velocity=<  13,  -4>
position=<   189,  1196> velocity=<  -3,  -8>
position=<   -59,   824> velocity=<  -1,  -5>
position=<  1181,   576> velocity=< -11,  -3>
position=< -1051,   948> velocity=<   7,  -6>
position=<  -555,   948> velocity=<   3,  -6>
position=<  1305,   576> velocity=< -12,  -3>
position=<    65,  1196> velocity=<  -2,  -8>
position=<   -59,  1072> velocity=<  -1,  -7>
position=< -1051,   824> velocity=<   7,  -5>
position=< -1051,  1196> velocity=<   7,  -8>
position=< -1919,   576> velocity=<  14,  -3>
position=<  1553,   576> velocity=< -14,  -3>
position=<  -431,   824> velocity=<   2,  -5>
position=<  1429,   824> velocity=< -13,  -5>
position=<   313,   576> velocity=<  -4,  -3>
position=<   313,  1196> velocity=<  -4,  -8>
position=< -1671,  1072> velocity=<  12,  -7>
position=<  -431,   948> velocity=<   2,  -6>
position=<  -679,   576> velocity=<   4,  -3>
position=<   437,  1196> velocity=<  -5,  -8>
position=<  1057,   576> velocity=< -10,  -3>
position=<  -431,  1072> velocity=<   2,  -7>
position=<  1429,   576> velocity=< -13,  -3>
position=<  -431,  1196> velocity=<   2,  -8>
position=< -1547,   700> velocity=<  11,  -4>
position=<   933,  1196> velocity=<  -9,  -8>
position=<   933,   948> velocity=<  -9,  -6>
position=<   933,   576> velocity=<  -9,  -3>
position=<    65,   576> velocity=<  -2,  -3>
position=<  -679,   948> velocity=<   4,  -6>
position=< -1671,  1196> velocity=<  12,  -8>
position=<   -59,   948> velocity=<  -1,  -6>
position=<   561,  1072> velocity=<  -6,  -7>
position=<   561,   700> velocity=<  -6,  -4>
position=<   189,   576> velocity=<  -3,  -3>

The answer isn't at the minima of area or x or y, but it's obviously very close.

(click to show/hide)

Prints 'YACF' after 123 seconds. Interestingly 2 seconds later, at t = 125 seconds it prints YACF, perfectly, but upside down. Intentional?

I can sort of see how the area would increase as the problem-setter was creating the input, and that you've simply reverse engineered that.
Would have been much harder (for you) if they'd been enclosed in a bounding box, like a 'TV', and 'bounce' off the sides or come back on at the left when they've gone off the right, etc. And would have been much harder for me if they'd used a lower case i.


My code could probably be rewritten (maybe in a different language) to run a lot faster, it took iirc probably >5 seconds to run, but was inside 30 seconds so optimization wasn't really needed. Only took about 10 mins to write.

Code: [Select]

using System;

namespace Day10
{
    using System.IO;
    using System.Linq;
    using System.Text.RegularExpressions;
    using AoCLib;

    class Program
    {
        static void Main(string[] args)
        {
            var parser = new Parser<Point>(new Regex(@"position\=\<\s*(?<PosX>[\-\d]+)\s*,\s*(?<PosY>[\-\d]+)\s*>\s*velocity\=\<\s*(?<VelX>[\-\d]+)\s*,\s*(?<VelY>[\-\d]+)\s*\>"));
            var points = File.ReadAllLines(@"..\..\..\input.txt")
                .Select(parser.Parse)
                .ToArray();
            int time = 0;
            while (true)
            {
                var alone = points.Count(p => !points.Any(p.IsNextTo));
                if (alone == 0)
                {
                    Print(points, time);
                }
                points.AsParallel().ForAll(p => p.Move());
                if(++time % 1000 == 0) Console.Write($"{time}    \r");
            }
        }

        private static void Print(Point[] points, int time)
        {
            var minX = points.Min(p => p.PosX);
            var minY = points.Min(p => p.PosY);
            var maxX = points.Max(p => p.PosX);
            var maxY = points.Max(p => p.PosY);
            char[][] lines = Enumerable.Range(0, 1 + maxY - minY).Select(y => Enumerable.Repeat(' ',1 + maxX - minX).ToArray()).ToArray();
            foreach (var point in points)
            {
                lines[point.PosY - minY][point.PosX - minX] = '#';
            }

            if (Console.BufferHeight < maxY - minY) Console.BufferHeight = maxY - minY;
            if (Console.BufferWidth < maxX - minX) Console.BufferWidth = maxX - minX;
            Console.Clear();
            foreach (var line in lines)
            {
                Console.WriteLine(new string(line));
            }
            Console.WriteLine($"\nafter {time}");
            Console.ReadKey(true);
        }
    }

    class Point
    {
        public int PosX { get; set; }
        public int PosY { get; set; }
        public int VelX { get; set; }
        public int VelY { get; set; }

        public void Move()
        {
            this.PosX += this.VelX;
            this.PosY += this.VelY;
        }

        public bool IsNextTo(Point other)
        {
            var xDiff = Math.Abs(this.PosX - other.PosX);
            var yDiff = Math.Abs(this.PosY - other.PosY);
            return xDiff <= 1 && yDiff <= 1 && (xDiff > 0 || yDiff > 0);
        }
    }
}



[Greenbank]

(click to show/hide)

Prints 'YACF' after 123 seconds. Interestingly 2 seconds later, at t = 125 seconds it prints YACF, perfectly, but upside down. Intentional?

(click to show/hide)

Yes, intentional, look at the positions of all the points at t=124.

[David Martin]

(click to show/hide)

I'd figured that it was probably going to be very close to the minimum but may not necessarily be at the minimum as you can compress the points further than legibility.
So I wrote a few functions that would let me move the points backward and forward in time, one that found the minimum and one that generated an image of the points.

So head to the minimum, view the image and then back up until it is obviously wrong, go forward till obviously wrong and stop when it is legible.

Part 2 was trivial and I should have counted the number of steps, but  saving the x of my first point and then calculating the time to move from its starting position was easy.

[Greenbank]

(click to show/hide)

Ooh, it's a classic.

O(n^3) or worse if implemented naively however it looks like the answer comes quite early so it's worth a punt and submitting whatever your program has spat out after running for a bit (assuming you output new high scores as they are found).

For a more optimal (or rather: less pessimal) solution (in C, was much faster than perl):-

$ time ./11 42
119 232,251,12

real    0m0.771s
user    0m0.768s
sys     0m0.004s

[Diver300]

Day 11 part  2

(click to show/hide)

The only bit on non-naive programming that I did was to calculate the sum of the squares by adding each L-shape to go from one square up to the next. This meant that the largest square would uniquely need 599 points added to a previous total instead of 90,000 if previous totals were ignored. 

[Greenbank]

Day 11 part  2

(click to show/hide)

The only bit on non-naive programming that I did was to calculate the sum of the squares by adding each L-shape to go from one square up to the next. This meant that the largest square would uniquely need 599 points added to a previous total instead of 90,000 if previous totals were ignored. 

(click to show/hide)

Yep, that's good enough.

The most optimal algorithm would be a modification (slight simplification) of Kadane's 2D algorithm (since that deals with maximum sum rectangle in a 2D array so it's a bit simpler if doing max square).

Got a chance to knock up a version (now with optimisation):-

$ time ./k 42
hs=119 at 232,251,12

real    0m0.027s
user    0m0.023s
sys     0m0.004s

[Ben T]

naive implementation in C++ https://github.com/bjtaylor1/AoC2018/blob/master/Day11/Day11.cpp (link may contain spoiler)
takes about a couple or three seconds

[Greenbank]

(click to show/hide)

http://www.greenbank.org/aoc/2018_day_11.c.txt

(Not particularly nicely written, would be splitting things into separate functions if I spent any more time on it. Especially confusing as x goes from 0 to 299 but y goes from 1 to 300 (for the original grid values) as the extra row of zeros to support Kadane's algorithm.)

Almost instantaneous (0.03s).

[Ben T]

Day 10 extension 

Code: [Select]

position=<679, 117> velocity=<-7, -1>
position=<584, 498> velocity=<-6, -5>
position=<489, 594> velocity=<-5, -6>
position=<109, 310> velocity=<-1, -3>
position=<585, 399> velocity=<-6, -4>
position=<300, 305> velocity=<-3, -3>
position=<680, 211> velocity=<-7, -2>
position=<586, 493> velocity=<-6, -5>
position=<586, 494> velocity=<-6, -5>
position=<397, 398> velocity=<-4, -4>
position=< 18, 683> velocity=< 0, -7>
position=< 19,  18> velocity=< 0,  0>
position=<399, 399> velocity=<-4, -4>
position=< 19,  20> velocity=< 0,  0>
position=<115,  21> velocity=<-1,  0>
position=<591, 402> velocity=<-6, -4>
position=<401, 403> velocity=<-4, -4>
position=<307, 308> velocity=<-3, -3>
position=<498, 305> velocity=<-5, -3>
position=<308, 686> velocity=<-3, -7>
position=<688, 117> velocity=<-7, -1>
position=<404, 586> velocity=<-4, -6>
position=<594, 112> velocity=<-6, -1>
position=< 24, 398> velocity=< 0, -4>
position=< 24, 399> velocity=< 0, -4>
position=<215,  16> velocity=<-2,  0>
position=<216, 491> velocity=<-2, -5>
position=<121,  17> velocity=<-1,  0>
position=< 27, 588> velocity=< 0, -6>
position=< 28,  18> velocity=< 0,  0>
position=<503,  19> velocity=<-5,  0>
position=<218, 495> velocity=<-2, -5>
position=<503, 686> velocity=<-5, -7>
position=<598, 212> velocity=<-6, -2>
position=<601, 223> velocity=<-6, -2>
position=< 31, 319> velocity=< 0, -3>
position=<126, 510> velocity=<-1, -5>
position=<411, 701> velocity=<-4, -7>
position=<221, 227> velocity=<-2, -2>
position=<127, 223> velocity=<-1, -2>
position=<412, 323> velocity=<-4, -3>
position=<697, 419> velocity=<-7, -4>
position=<603, 507> velocity=<-6, -5>
position=<128, 705> velocity=<-1, -7>
position=<318, 326> velocity=<-3, -3>
position=<319, 696> velocity=<-3, -7>
position=<224, 232> velocity=<-2, -2>
position=<130, 696> velocity=<-1, -7>
position=<605, 707> velocity=<-6, -7>
position=< 36, 696> velocity=< 0, -7>
position=<226, 510> velocity=<-2, -5>
position=<606, 518> velocity=<-6, -5>
position=<322, 601> velocity=<-3, -6>
position=<702, 511> velocity=<-7, -5>
position=< 37, 139> velocity=< 0, -1>
position=<513, 601> velocity=<-5, -6>
position=<418, 511> velocity=<-4, -5>
position=<418, 140> velocity=<-4, -1>
position=< 39, 506> velocity=< 0, -5>
position=<609,  36> velocity=<-6,  0>
position=<514, 710> velocity=<-5, -7>
position=<705, 221> velocity=<-7, -2>
position=<705, 131> velocity=<-7, -1>
position=<135, 615> velocity=<-1, -6>
position=<326, 506> velocity=<-3, -5>
position=<136, 319> velocity=<-1, -3>
position=<231, 225> velocity=<-2, -2>
position=< 41, 701> velocity=< 0, -7>
position=<516, 236> velocity=<-5, -2>
position=<137,  31> velocity=<-1,  0>
position=<517, 319> velocity=<-5, -3>
position=<612, 236> velocity=<-6, -2>
position=<613, 506> velocity=<-6, -5>
position=<233, 412> velocity=<-2, -4>
position=<613,  33> velocity=<-6,  0>
position=<613,  46> velocity=<-6,  0>
position=< 50,  54> velocity=< 0,  0>
position=<145, 340> velocity=<-1, -3>
position=<525, 436> velocity=<-5, -4>
position=<620, 152> velocity=<-6, -1>
position=<525, 153> velocity=<-5, -1>
position=<240, 344> velocity=<-2, -3>
position=< 50, 155> velocity=< 0, -1>
position=<430, 156> velocity=<-4, -1>
position=<525, 442> velocity=<-5, -4>
position=<431, 624> velocity=<-4, -6>
position=<432, 624> velocity=<-4, -6>
position=<242, 245> velocity=<-2, -2>
position=< 53, 530> velocity=< 0, -5>
position=<434, 245> velocity=<-4, -2>
position=<625, 435> velocity=<-6, -4>
position=<721, 340> velocity=<-7, -3>
position=<721,  56> velocity=<-7,  0>
position=<351, 255> velocity=<-3, -2>
position=<161, 541> velocity=<-1, -5>
position=<161, 162> velocity=<-1, -1>
position=<352, 730> velocity=<-3, -7>
position=<257, 448> velocity=<-2, -4>
position=< 67, 354> velocity=< 0, -3>
position=<257, 450> velocity=<-2, -4>
position=<162, 166> velocity=<-1, -1>
position=<637, 262> velocity=<-6, -2>
position=<352, 738> velocity=<-3, -7>
position=<448, 159> velocity=<-4, -1>
position=<544, 634> velocity=<-5, -6>
position=<260,  64> velocity=<-2,  0>
position=<736, 444> velocity=<-7, -4>
position=<357,  64> velocity=<-3,  0>
position=<168, 729> velocity=<-1, -7>
position=<367, 741> velocity=<-3, -7>
position=<558, 171> velocity=<-5, -1>
position=< 83,  93> velocity=< 0,  0>
position=<274, 361> velocity=<-2, -3>
position=<369, 473> velocity=<-3, -4>
position=<465, 552> velocity=<-4, -5>
position=<180, 553> velocity=<-1, -5>
position=<370,  93> velocity=<-3,  0>
position=<181, 554> velocity=<-1, -5>
position=<561, 473> velocity=<-5, -4>
position=<752,  80> velocity=<-7,  0>
position=<372, 283> velocity=<-3, -2>
position=<468, 271> velocity=<-4, -2>
position=<373, 188> velocity=<-3, -1>
position=<184, 645> velocity=<-1, -6>
position=<469, 171> velocity=<-4, -1>
position=<279, 172> velocity=<-2, -1>
position=<754, 268> velocity=<-7, -2>
position=<659, 744> velocity=<-6, -7>
position=<184, 650> velocity=<-1, -6>
position=< 89,  81> velocity=< 0,  0>
position=<374, 747> velocity=<-3, -7>
position=<469,  83> velocity=<-4,  0>
position=<564, 559> velocity=<-5, -5>
position=<564, 750> velocity=<-5, -7>
position=<374, 656> velocity=<-3, -6>
position=<279, 562> velocity=<-2, -5>
position=<754, 373> velocity=<-7, -3>
position=<469, 374> velocity=<-4, -3>
position=<564, 565> velocity=<-5, -5>
position=<564, 186> velocity=<-5, -1>
position=<184, 472> velocity=<-1, -4>
position=< 89, 283> velocity=< 0, -2>
position=<280,  75> velocity=<-2,  0>
position=<565,  76> velocity=<-5,  0>
position=<185, 172> velocity=<-1, -1>
position=<375, 743> velocity=<-3, -7>
position=<470, 744> velocity=<-4, -7>
position=<470, 460> velocity=<-4, -4>
position=<566, 455> velocity=<-5, -4>
position=<566, 551> velocity=<-5, -5>
position=<625, 775> velocity=< 3,  2>
position=<626, 490> velocity=< 3,  5>
position=<342, 490> velocity=< 6,  5>
position=<817, 593> velocity=< 1,  4>
position=<342, 784> velocity=< 6,  2>
position=<818, 585> velocity=< 1,  4>
position=<818, 403> velocity=< 1,  6>
position=<344, 396> velocity=< 6,  6>
position=<344, 777> velocity=< 6,  2>
position=<439, 496> velocity=< 5,  5>
position=<249, 592> velocity=< 7,  4>
position=<440, 873> velocity=< 5,  1>
position=<725, 684> velocity=< 2,  3>
position=<915, 305> velocity=< 0,  7>
position=<251, 970> velocity=< 7,  0>
position=<442, 875> velocity=< 5,  1>
position=<917, 306> velocity=< 0,  7>
position=<348, 304> velocity=< 6,  7>
position=<823, 782> velocity=< 1,  2>
position=<634, 494> velocity=< 3,  5>
position=<349, 878> velocity=< 6,  1>
position=<730, 403> velocity=< 2,  6>
position=<920, 309> velocity=< 0,  7>
position=<449, 400> velocity=< 5,  6>
position=<829, 496> velocity=< 1,  5>
position=<449, 687> velocity=< 5,  3>
position=<354, 973> velocity=< 6,  0>
position=<354, 404> velocity=< 6,  6>
position=<544, 880> velocity=< 4,  1>
position=<639, 786> velocity=< 3,  2>
position=<449, 882> velocity=< 5,  1>
position=<544, 408> velocity=< 4,  6>
position=<450, 305> velocity=< 5,  7>
position=<641, 780> velocity=< 3,  2>
position=<927, 400> velocity=< 0,  6>
position=<453, 590> velocity=< 5,  4>
position=<359, 305> velocity=< 6,  7>
position=<359, 401> velocity=< 6,  6>
position=<740, 401> velocity=< 2,  6>
position=<836, 782> velocity=< 1,  2>
position=<362, 783> velocity=< 6,  2>
position=<362, 879> velocity=< 6,  1>
position=<742, 785> velocity=< 2,  2>
position=<743, 974> velocity=< 2,  0>
position=<933, 975> velocity=< 0,  0>
position=<743, 311> velocity=< 2,  7>
position=<269, 973> velocity=< 7,  0>
position=<934, 596> velocity=< 0,  4>
position=<554, 597> velocity=< 4,  4>
position=<839, 978> velocity=< 1,  0>
position=<650, 783> velocity=< 3,  2>
position=<461, 783> velocity=< 5,  2>
position=<937, 878> velocity=< 0,  1>
position=<558, 403> velocity=< 4,  6>
position=<844, 973> velocity=< 1,  0>
position=<655, 498> velocity=< 3,  5>
position=<941, 879> velocity=< 0,  1>
position=<562, 784> velocity=< 4,  2>
position=<658, 689> velocity=< 3,  3>
position=<658, 785> velocity=< 3,  2>
position=<469, 691> velocity=< 5,  3>
position=<849, 977> velocity=< 1,  0>
position=<671, 498> velocity=< 3,  5>
position=<576, 404> velocity=< 4,  6>
position=<291, 785> velocity=< 7,  2>
position=<861, 501> velocity=< 1,  5>
position=<482, 972> velocity=< 5,  0>
position=<387, 692> velocity=< 6,  3>
position=<578, 686> velocity=< 4,  3>
position=<958, 883> velocity=< 0,  1>
position=<389, 591> velocity=< 6,  4>
position=<389, 979> velocity=< 6,  0>
position=<579, 505> velocity=< 4,  5>
position=<295, 401> velocity=< 7,  6>
position=<580, 505> velocity=< 4,  5>
position=<866, 876> velocity=< 1,  1>
position=<866, 315> velocity=< 1,  7>
position=<677, 306> velocity=< 3,  7>
position=<867, 505> velocity=< 1,  5>
position=<393, 686> velocity=< 6,  3>
position=<583, 409> velocity=< 4,  6>
position=<393, 315> velocity=< 6,  7>
position=<394, 401> velocity=< 6,  6>
position=<964, 972> velocity=< 0,  0>
position=<774, 974> velocity=< 2,  0>
position=<394, 314> velocity=< 6,  7>
position=<775, 879> velocity=< 2,  1>
position=<680, 883> velocity=< 3,  1>
position=<490, 979> velocity=< 5,  0>
position=<586, 404> velocity=< 4,  6>
position=<396, 405> velocity=< 6,  6>
position=<871, 786> velocity=< 1,  2>
position=<871, 977> velocity=< 1,  0>
position=<682, 501> velocity=< 3,  5>
position=<588, 406> velocity=< 4,  6>
position=<778, 312> velocity=< 2,  7>
position=<589, 502> velocity=< 4,  5>
position=<495, 977> velocity=< 5,  0>
position=<506, 318> velocity=< 5,  7>
position=<792, 508> velocity=< 2,  5>
position=<603, 401> velocity=< 4,  6>
position=<698, 687> velocity=< 3,  3>
position=<413, 878> velocity=< 6,  1>
position=<413, 974> velocity=< 6,  0>
position=<603, 785> velocity=< 4,  2>
position=<793, 982> velocity=< 2,  0>
position=<889, 971> velocity=< 1,  0>
position=<509, 500> velocity=< 5,  5>
position=<604, 691> velocity=< 4,  3>
position=<414, 407> velocity=< 6,  6>
position=<794, 788> velocity=< 2,  2>
position=<699, 697> velocity=< 3,  3>
position=<415, 306> velocity=< 6,  7>
position=<795, 599> velocity=< 2,  4>
position=<700, 792> velocity=< 3,  2>
position=<701, 496> velocity=< 3,  5>
position=<416, 410> velocity=< 6,  6>
position=<891, 316> velocity=< 1,  7>
position=<797, 505> velocity=< 2,  5>


[Greenbank]

Day 10 extension 

Excellent, found it but will need to work on an algorithm to detect when to stop as I had to manually step through once in the right area to get the exact frame.

(click to show/hide)

I think testing for:-
* adjacency
* min height
* max height
* bounding box area

and then using a combination of those to make the decision might be required

[Ben T]

Day 10 extension 

Excellent, found it but will need to work on an algorithm to detect when to stop as I had to manually step through once in the right area to get the exact frame.

What does it say then? And at what time (frame)?

(click to show/hide)

I think testing for:-
* adjacency
* min height
* max height
* bounding box area

and then using a combination of those to make the decision might be required

You don't need all that - see #669  ...  https://yacf.co.uk/forum/index.php?topic=94710.msg2349625#msg2349625

[Greenbank]

What does it say then? And at what time (frame)?

(click to show/hide)

Console output with font size set to 1pt:-

Code: [Select]

$ cat inp.ben_t | ./10.pl | grep -v "^\.*$" | cut -b 1-40 | grep -A 20 t=94
t=94 987 14 983 16 sizes=940891 minsize=
-------------t=94------------------
..........###...........................
..........#.#...........................
..####....#..##.........................
.##..#....#...#.........................
.#...#...#....#.........................
.#....#..#....#.........................
#......#.#....#.........................
#......##...............................
#.......................................
#.......................................
....................##########..........
...................#.........#..........
.................##..........#..........
.................#.........##...........
.................#....#....#............
.................#.....#####............
.................#......................
..................#.....................
..................#.....................
...................#....................


[David Martin]

Day 11 was nice. I have only got round to it but looked at it briefly at Makerspace tonight. One of my fellow hackers had done it naively and it took a while, so having the benefit of seeing part 2 I realised that

(click to show/hide)

a dynamic programming method was needed.

1. calculate all powers.
2. Cumulative sum across rows.
3. Cumulative sum of sums down columns.

This gives the cumulative sum from 0,0 (I ran from 0 to 300 setting all (0,y), (x,0) as 0). to (x,y)

Then you just need to calculate for x,y,size the following:
square from 0,0 to x+size-1, y+size-1
+ square from 0,0 to x-1,y-1
-rectangle from 0,0 to x-1, y+size-1
- rectangle from 0,0 to x+size-1, y-1

and find the x,y which maximises that.
I can't see a shorter way of doing it.
My rather slow computer ran that in python in a few (<10) seconds

[Greenbank]

Day 12. Can't see why my part 2 is wrong.

[Diver300]

Day 12. Can't see why my part 2 is wrong.

Nor me.

[Greenbank]

(click to show/hide)

D'oh. Off by one (iteration) error.

Was printing out the running total after incrementing the time tick counter but before I'd done that iteration's work.

[Diver300]

Day 12. Can't see why my part 2 is wrong.

Nor me.

(click to show/hide)

Even though the final arrangements don't have plants in pots where n<0, and the start point doesn't either, some of the early intermediate arrangements do, so pots where n<0 need to be allowed for.

[Croft]

(click to show/hide)

a dynamic programming method was needed.

1. calculate all powers.
2. Cumulative sum across rows.
3. Cumulative sum of sums down columns.

This gives the cumulative sum from 0,0 (I ran from 0 to 300 setting all (0,y), (x,0) as 0). to (x,y)

Then you just need to calculate for x,y,size the following:
square from 0,0 to x+size-1, y+size-1
+ square from 0,0 to x-1,y-1
-rectangle from 0,0 to x-1, y+size-1
- rectangle from 0,0 to x+size-1, y-1

and find the x,y which maximises that.
I can't see a shorter way of doing it.
My rather slow computer ran that in python in a few (<10) seconds

Nice.

(click to show/hide)

That approach is used quite a lot in image processing when you need to make many rectangular brightness queries of a large image.

The only other optimisation I am aware of (apart from Greenbank's data-structure approach) would be to exploit the particular properties of the surface by terminating the window expansion once growing results in a significantly lower score (typically around the 25x25 size).

[Greenbank]

(click to show/hide)

a dynamic programming method was needed.

1. calculate all powers.
2. Cumulative sum across rows.
3. Cumulative sum of sums down columns.

This gives the cumulative sum from 0,0 (I ran from 0 to 300 setting all (0,y), (x,0) as 0). to (x,y)

Then you just need to calculate for x,y,size the following:
square from 0,0 to x+size-1, y+size-1
+ square from 0,0 to x-1,y-1
-rectangle from 0,0 to x-1, y+size-1
- rectangle from 0,0 to x+size-1, y-1

and find the x,y which maximises that.
I can't see a shorter way of doing it.
My rather slow computer ran that in python in a few (<10) seconds

Nice.

(click to show/hide)

That approach is used quite a lot in image processing when you need to make many rectangular brightness queries of a large image.

The only other optimisation I am aware of (apart from Greenbank's data-structure approach) would be to exploit the particular properties of the surface by terminating the window expansion once growing results in a significantly lower score (typically around the 25x25 size).

(click to show/hide)

Early exit is not an optimisation, it becomes a necessity if you're using an inefficient algorithm. If the real solution (using contrived data) was a square greater than, say 100, then something that bails at square size 25 is not going to find it.

The optimal algorithm (a simplified version of Kadane's 2D algorithm) works by taking the grid and making each cell the sum of itself and all cells above it, i.e. for a single column

Code: [Select]

. -> 0 (extra row of all 0 values)
A -> A
B -> A+B
C -> A+B+C
D -> A+B+C+D
...
Z -> A+B+C+D+E+...+X+Y+Z
...

If you build the original grid (calculating the power values) from top to bottom then this is just an extra addition when computing the value for each cell, since you only need to add the value of the cell above to the one you're just computing.

i.e. if you're computing cell D you work out the power value for row D and then add in the cell above which is already set to the sum A+B+C. When you get to row E you add in the value of the cell above which is A+B+C+D, etc.

If you're given a pre-computed grid then it's still just N*M addition operations that need to be performed to create this working grid.

Then, the partial sum of a column is just a single subtraction, i.e. to sum the 5 values from C downwards (i.e. C+D+E+F+G) you just need to subtract the value in row G from the value in row B as that works out as:-

A+B+C+D+E+F+G - (A+B) = C+D+E+F+G.

So, regardless of the number of cells in the partial column the calculation is just a single subtraction in order to sum all of those values.

If you imagine a square with sides of size 27 then, for the first square, you're still only doing 27 subtractions (to get each of the partial column sums) and then 27 additions (to add each of these together).
When you shift this square to the left once you just have to do one more subtraction (the partial sum of the next column) and one addition (to add that the to current square running total) and then another two subtractions (one to calculate the partial column total that is being removed from the left, and one to subtract that from the running total).

The important thing about this algorithm is that as the square size gets bigger the number of computations *decreases* (you still have to calculate all 300 partial column totals as you scan across the grid but you'll have to remove fewer of them, so there's less work involved). Most naive algorithms increase the number of individual computations as the square size approaches half the size of the grid. Also there are fewer rows to iterate over as the number of possible 'top' rows decreases as the size of square increases.

Kadane's 2D algorithm is a bit more complicated as it handles maximum sub *rectangles* in a matrix/grid, so there's an extra degree of freedom to make the naive algorithm O(n^4). It relies on Kadane's (1D) algorithm for maximum subset of a list which is needed to handle having a list of results instead of one result per square as a rectangle has that extra degree of freedom of the second side's size.

[David Martin]

(click to show/hide)

a dynamic programming method was needed.

1. calculate all powers.
2. Cumulative sum across rows.
3. Cumulative sum of sums down columns.

This gives the cumulative sum from 0,0 (I ran from 0 to 300 setting all (0,y), (x,0) as 0). to (x,y)

Then you just need to calculate for x,y,size the following:
square from 0,0 to x+size-1, y+size-1
+ square from 0,0 to x-1,y-1
-rectangle from 0,0 to x-1, y+size-1
- rectangle from 0,0 to x+size-1, y-1

and find the x,y which maximises that.
I can't see a shorter way of doing it.
My rather slow computer ran that in python in a few (<10) seconds

Nice.

(click to show/hide)

That approach is used quite a lot in image processing when you need to make many rectangular brightness queries of a large image.

The only other optimisation I am aware of (apart from Greenbank's data-structure approach) would be to exploit the particular properties of the surface by terminating the window expansion once growing results in a significantly lower score (typically around the 25x25 size).

(click to show/hide)

My line of work is analysing DNA sequences and the classical algorithm is the Needleman-Wunsch (later updated to a Smith-Waterman-Gotoh).
This uses a similar approach for finding the best alignment of two sequences with gaps (adds a lot more complexity). SWG does the optimal aligning subsequences.

[David Martin]

(click to show/hide)

I translated the input to a bitstring and use bitwise operations to read/build the new generation from the old.
Part 2 then will take about 5 million seconds using this approach so I am pretty sure there must be a better way. Maybe finding the largest previously seen matching number from that point  to do each section rather than repeating the same small mappings. Not got time to think about that now but will try that in the morning as the code will not have finished running by then. Need to find a big enough gap (4 zeros?) between numbers so that I have nonoverlapping patterns I can use.

[David Martin]

Got it - massive speed up.

(click to show/hide)

Make the search bit string much bigger than 5 bits - I've upped it to 20 bits and it is screaming through at about 1 million generations per second.
To bed now, unless it will finish very shortly...

[David Martin]

OK, not quite enough

(click to show/hide)

Really need to think about looking for repeated patterns over many iterations so I don't repeat every one individually. As there are 16 core transitions, there must be an optimisation in there somewhere (running at about 2 billion iterations per hour)

ETA: I'll look for the first repeat of a number and go from there straight to the last iteration. Save that for tonight.