Advent of Code

[Greenbank]

All of the previous AoC years have had a similar puzzle at some point in them I think.

Some time next year I'm going to go through all of the years and reimplement them in a few different languages, I'll also take the time to classify them so I can see how common individual things come up.

I may even write a load of template code/functions[1] ready to have a go at getting on the top 100 leaderboard, however I don't think I can be arsed getting up and having my brain ready and switched on for 5am even for a few days let alone every day.

1. This is how the majority of the top 100 get such fast times. Preparation (based on guesswork and experience) and then knowing which template would be best used as a basis for each puzzle...

[tonycollinet]

Day 11 Part 1 is here. It takes about 20 minutes to recalculate 100 iterations,

Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.

[grams]

Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.

That's for a Google Sheet with two million cells running in a browser tab.

More efficient approaches are no doubt available.

[Davef]

Day 11 Part 1 is here. It takes about 20 minutes to recalculate 100 iterations,

Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.

63 trillion iterations of a 100,000 by 100,000 grid might take a while.

https://conwaylife.com/wiki/Pi_calculator

[grams]

OK, did day 11 part 2:
https://docs.google.com/spreadsheets/d/1mfMTK1UA9qBIduBxIRKw92QYtu95AZ6LUPiETdR_uZA/edit?usp=sharing

(click to show/hide)

Basically I'm making strings of the available seats in each of the 8 directions, searching for the first one in the string  and figuring out its offset in my array, which is easy to substitute into the same formulae from part1. The working out how to do it is trivial compared to waiting for it all to recalculate.

It's so slow now I used someone else's python code to verify I was getting the right answers, which made the whole thing extra pointless.

[tonycollinet]

Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.

That's for a Google Sheet with two million cells running in a browser tab.

More efficient approaches are no doubt available.

Ah - fair enough.

[tonycollinet]

So time constraints meant that I've only just completed day 11 p2.

(click to show/hide)

I used recursion again for the Part 2 scan along the line of sight. Really liking how it simplifies this sort of repetitive stuff.

I could also reduce code lines by combining P1 and P2 with a conditional section on part number, but can't be bothered. And for execution time, this way will be (marginally) faster anyway.
******************************
def TestSeatP1 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#set up matrix for valid test
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
   
#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if test_valid[rs][cs]:
                seat_val = seats[row+rs-1][col+cs-1]
                if seat_val == "#":
                    count_occupied += 1
   
    return (count_occupied)                   

def ScanP2 (row, col, rcnt, ccnt):
#set up matrix for valid test
    num_col = len (seats

• )

    num_row = len (seats)
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
    if test_valid [rcnt][ccnt]:
        seat_val = seats[row+rcnt-1][col+ccnt-1]
        if seat_val == ".":
            return ScanP2 (row+rcnt-1,col+ccnt-1,rcnt, ccnt)
        else:
            return seat_val
    else:
        return "E"


def TestSeatP2 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if ScanP2 (row, col, rs, cs) == "#":
                count_occupied += 1
   
    return (count_occupied)                   

# start get data
input_file = open("11Input.txt", "r")
#data = [(line.strip()).split() for line in input_file]
seats = [line.strip() for line in input_file]
input_file.close()

#take a copy for part 2
original_seats = seats.copy()

# part 1

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 1", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP1 (row,col)
            if now == "#" and occupied >= 4:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part1Ans = num_occupied
part1Iterations = iterations


# part 2
seats = original_seats.copy ()

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 2", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP2 (row,col)
            if now == "#" and occupied >= 5:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part2Ans = num_occupied
part2Iterations = iterations

print ("Part 1: No iterations ", part1Iterations,"Number occupied: ", part1Ans)
print ("Part 2: No iterations ", part2Iterations,"Number occupied: ", part2Ans)

[Davef]

So time constraints meant that I've only just completed day 11 p2.

(click to show/hide)

I used recursion again for the Part 2 scan along the line of sight. Really liking how it simplifies this sort of repetitive stuff.

I could also reduce code lines by combining P1 and P2 with a conditional section on part number, but can't be bothered. And for execution time, this way will be (marginally) faster anyway.
******************************
def TestSeatP1 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#set up matrix for valid test
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
   
#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if test_valid[rs][cs]:
                seat_val = seats[row+rs-1][col+cs-1]
                if seat_val == "#":
                    count_occupied += 1
   
    return (count_occupied)                   

def ScanP2 (row, col, rcnt, ccnt):
#set up matrix for valid test
    num_col = len (seats

• )

    num_row = len (seats)
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
    if test_valid [rcnt][ccnt]:
        seat_val = seats[row+rcnt-1][col+ccnt-1]
        if seat_val == ".":
            return ScanP2 (row+rcnt-1,col+ccnt-1,rcnt, ccnt)
        else:
            return seat_val
    else:
        return "E"


def TestSeatP2 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if ScanP2 (row, col, rs, cs) == "#":
                count_occupied += 1
   
    return (count_occupied)                   

# start get data
input_file = open("11Input.txt", "r")
#data = [(line.strip()).split() for line in input_file]
seats = [line.strip() for line in input_file]
input_file.close()

#take a copy for part 2
original_seats = seats.copy()

# part 1

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 1", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP1 (row,col)
            if now == "#" and occupied >= 4:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part1Ans = num_occupied
part1Iterations = iterations


# part 2
seats = original_seats.copy ()

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 2", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP2 (row,col)
            if now == "#" and occupied >= 5:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part2Ans = num_occupied
part2Iterations = iterations

print ("Part 1: No iterations ", part1Iterations,"Number occupied: ", part1Ans)
print ("Part 2: No iterations ", part2Iterations,"Number occupied: ", part2Ans)

All that typing takes a while.

(click to show/hide)

// count number ‘adjacent’ to x,y in each of 8 directions, unlimited distance
int countadjacent8x(const CSparse& a, int x0, int y0, int val, int w, int h)
{
int ret = 0;

for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
{
if (!dx&&!dy) continue; // the 9th unwanted NULL direction

for (int x=x0+dx,y=y0+dy ; (x>=0)&&(y>=0)&&(x<=w)&&(y<=h) ; x+=dx,y+=dy) 
{
int c = a.get(x,y);

if (c==val) ret++; // found one
if (c) break; // hit something so on to next direction
}
}

return ret;
}

// produce next iteration from a into b, returns number of changes
int d11iterb(const CSparse& a, CSparse& b, int w, int h)
{
int ret = 0;

for (int x=0; x<=w; x++)
for (int y=0; y<=h;y++)
{
int c = a.get(x,y);

if (c)
{
int n = countadjacent8x(a,x,y,'#',w,h);
if (((c=='L')&&(n==0))||((c=='#')&&(n>=5)))
{
c =‘#’+’L'-c;  // toggle between # and L
ret++;
}

b.set(x,y,c);
}
}

return ret;
}

[grams]

Day 12 is oddly simple:
https://docs.google.com/spreadsheets/d/1NyEKHBwBLrFNKyLmZ63jB8CxNB6vBg3_ci3R9WBDgPM/edit?usp=sharing

(click to show/hide)

Did finally find a use for matrix transformations we spent far too long on in school. "use" being relative here.

[Arellcat]

Code: [Select]

user@cinelli ~ $ python -V
Python 2.7.6


Woah, slow down, Einstein. 

This may be why I am not a programmer, although I do like a good spreadsheet.

[Davef]

Day 12 is oddly simple:
https://docs.google.com/spreadsheets/d/1NyEKHBwBLrFNKyLmZ63jB8CxNB6vBg3_ci3R9WBDgPM/edit?usp=sharing

(click to show/hide)

Did finally find a use for matrix transformations we spent far too long on in school. "use" being relative here.

My terse version

(click to show/hide)

int x=0,y=0; // ship position
int v=10,w=1; // way point position

for (int i = 0; i < nn; i++)
{
const char *s = a;
char c = s[0];      // command
int d = atoi(s+1);  // amount

switch (c)
{
case 'N': w += d; break;
case 'E': v += d; break;
case 'W': v -= d; break;
case 'S': w -= d; break;
case 'F': x += v * d; y += w * d; break;
case 'L': d =  360-d;
case 'R': d /= 90; while (d--){w-=v;v+=w;w-=v;}
}

}
ret = abs(x)+abs(y);

[Diver300]

Day 12 is oddly simple:
https://docs.google.com/spreadsheets/d/1NyEKHBwBLrFNKyLmZ63jB8CxNB6vBg3_ci3R9WBDgPM/edit?usp=sharing

(click to show/hide)

Did finally find a use for matrix transformations we spent far too long on in school. "use" being relative here.

I used a spreadsheet as well.

(click to show/hide)

I used sin and cos for the rotations, but I only ever used multiples of 90 degrees. The x and y components were separately multiplied by the H parameter

[grams]

snip

Tactical fallthrough. Nice.

[Davef]

(click to show/hide)

Bizarre way of rotating clockwise by 90 degrees using 3 translations parallel to axes



Or if you dislike infix
y = y - x
x = x + y
y = y - x

[Ben T]

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.

Really? not sure how "fast" you want it, mine takes about a second although that's in debug and probably includes compilation, they all take that - so I think the actual calculation, if I produced a release binary it would probably be sub-second.

my code is distinctly 'pedestrian', but reasonably efficient enough

(click to show/hide)

Code: [Select]

    public class Day11
    {
        public static async Task Part1(string[] args)
        {
            var matrix = await Matrix.Parse(Console.In);

            int changes;
            do
            {
                matrix = Iterate(matrix, out changes);
            } while(changes > 0);

            await Console.Out.WriteLineAsync(matrix.Cells.Count(c => c.Value == '#').ToString());
        }

        public static async Task Part2(string[] args)
        {
            var matrix = await Matrix.Parse(Console.In);

            int changes;
            do
            {
                matrix = IteratePart2(matrix, out changes);
            } while(changes > 0);

            await Console.Out.WriteLineAsync(matrix.Cells.Count(c => c.Value == '#').ToString());
        }

        private static Matrix Iterate(Matrix m, out int changes)
        {
            changes = 0;
            var newMatrix = new Matrix(m);
            foreach(var c in m.Cells)
            {
                var adjacents = m.AdjacentsIncludingDiagonal(c.Key).ToArray();
                if(c.Value == 'L' && !adjacents.Any(a => m.Cells[a] == '#'))
                {
                    newMatrix.Cells[c.Key] = '#';
                    changes++;
                }
                else if(c.Value == '#' && adjacents.Count(a => m.Cells[a] == '#') >= 4)
                {
                    newMatrix.Cells[c.Key] = 'L';
                    changes++;
                }
            }
            return newMatrix;
        }

        private static Matrix IteratePart2(Matrix m, out int changes)
        {
            changes = 0;
            var newMatrix = new Matrix(m);
            foreach(var c in m.Cells)
            {
                var visible = m.SightlinesIncludingDiagonal(c.Key, '.');
                if(c.Value == 'L' && !visible.Any(a => m.Cells[a] == '#'))
                {
                    newMatrix.Cells[c.Key] = '#';
                    changes++;
                }
                else if(c.Value == '#' && visible.Count(a => m.Cells[a] == '#') >= 5)
                {
                    newMatrix.Cells[c.Key] = 'L';
                    changes++;
                }
            }
            return newMatrix;
        }
    }



where 'Matrix' is a reusable component in my generic library AoCTools:

Code: [Select]

    public class Matrix
    {
        public Matrix() {}

        public Matrix(Matrix matrixToClone)
        {
            Cells = matrixToClone.Cells.ToDictionary(x => x.Key, x => x.Value);
            Length = matrixToClone.Length;
            Height = matrixToClone.Height;
        }

        public readonly Dictionary<MatrixCoord, char> Cells = new Dictionary<MatrixCoord, char>();
        public int Length{get; private set;}
        public int Height{get;private set;}

        public static async Task<Matrix> Parse(TextReader reader)
        {
            var matrix = new Matrix();
            string line;
            int? lineLength = null;
            int y = 0;
            while(!string.IsNullOrEmpty(line = await reader.ReadLineAsync()))
            {
                if(lineLength.HasValue && line.Length != lineLength.Value) throw new InvalidOperationException("Mismatched line lengths");
                lineLength = line.Length;
                for(int x = 0; x < line.Length; x++)
                {
                    matrix.Cells.Add(new MatrixCoord(x, y), line[x]);
                }
                y++;
            }
            matrix.Length = lineLength.Value;
            matrix.Height = y;
            return matrix;
        }

        public IEnumerable<MatrixCoord> AdjacentsIncludingDiagonal(MatrixCoord coord)
        {
            for(int dx = -1; dx <= 1; dx++)
            {
                for(int dy = -1; dy <= 1; dy++)
                {
                    var ox = coord.X + dx;
                    var oy = coord.Y + dy;
                    if(dx == 0 && dy == 0) continue; // this one
                    if(ox < 0 || oy < 0 || ox >= Length || oy >= Height) continue; //out of bounds
                    yield return new MatrixCoord(ox, oy);
                }
            }
        }

        public IEnumerable<MatrixCoord> SightlinesIncludingDiagonal(MatrixCoord coord, char space)
        {
            for(int dx = -1; dx <= 1; dx++)
            {
                for(int dy = -1; dy <= 1; dy++)
                {
                    if(dx == 0 && dy == 0) continue; // this one
                    for(int m = 1;;m++)
                    {
                        var ox = coord.X + m*dx;
                        var oy = coord.Y + m*dy;
                        if(ox < 0 || oy < 0 || ox >= Length || oy >= Height) break; //out of bounds
                        var oc = new MatrixCoord(ox, oy);
                        if(Cells[oc] != space)
                        {
                            yield return oc;
                            break;
                        }
                    }
                }
            }
        }
    }

    public struct MatrixCoord
    {
        public MatrixCoord(int x, int y)
        {
            X = x;
            Y = y;
        }

        public int X{get;}
        public int Y{get;}

        public override bool Equals(object obj)
        {
            return obj is MatrixCoord coord &&
                   X == coord.X &&
                   Y == coord.Y;
        }

        public override int GetHashCode()
        {
            int hashCode = 1861411795;
            hashCode = hashCode * -1521134295 + X.GetHashCode();
            hashCode = hashCode * -1521134295 + Y.GetHashCode();
            return hashCode;
        }
    }


the "trick", which you've probably seen, I recognised it instantly from previous similar problems, is

(click to show/hide)

immutability, don't modify it in place but create a copy (it says in the instructions all transformations happen simultaneously)

Curious enough to see if you can do it in fewer clock cycles, even if you don't need to

[tonycollinet]

So time constraints meant that I've only just completed day 11 p2.

(click to show/hide)

I used recursion again for the Part 2 scan along the line of sight. Really liking how it simplifies this sort of repetitive stuff.

I could also reduce code lines by combining P1 and P2 with a conditional section on part number, but can't be bothered. And for execution time, this way will be (marginally) faster anyway.
******************************
def TestSeatP1 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#set up matrix for valid test
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
   
#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if test_valid[rs][cs]:
                seat_val = seats[row+rs-1][col+cs-1]
                if seat_val == "#":
                    count_occupied += 1
   
    return (count_occupied)                   

def ScanP2 (row, col, rcnt, ccnt):
#set up matrix for valid test
    num_col = len (seats

• )

    num_row = len (seats)
    test_valid = [[row>0 and col>0,row>0, row>0 and col<num_col - 1],
                  [col>0,False,col<num_col-1],
                  [row<num_row-1 and col>0,row<num_row-1,col<num_col-1 and row<num_row-1]]
    if test_valid [rcnt][ccnt]:
        seat_val = seats[row+rcnt-1][col+ccnt-1]
        if seat_val == ".":
            return ScanP2 (row+rcnt-1,col+ccnt-1,rcnt, ccnt)
        else:
            return seat_val
    else:
        return "E"


def TestSeatP2 (row, col):
    global seats
    num_col = len (seats

• )

    num_row = len (seats)

#examine surrounding seats
    count_occupied = 0
    for rs in range (3):
        for cs in range (3):
            if ScanP2 (row, col, rs, cs) == "#":
                count_occupied += 1
   
    return (count_occupied)                   

# start get data
input_file = open("11Input.txt", "r")
#data = [(line.strip()).split() for line in input_file]
seats = [line.strip() for line in input_file]
input_file.close()

#take a copy for part 2
original_seats = seats.copy()

# part 1

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 1", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP1 (row,col)
            if now == "#" and occupied >= 4:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part1Ans = num_occupied
part1Iterations = iterations


# part 2
seats = original_seats.copy ()

changed = True
iterations = 0
seats_new = []
while changed:
    print ("part 2", iterations)
#     for index, row in enumerate (seats):
#         if index<10:
#             print (row)
    num_changes = 0
    num_occupied = 0
    seats_new = seats.copy()
   
   
    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            occupied = TestSeatP2 (row,col)
            if now == "#" and occupied >= 5:
                new = "L"
                num_changes+= 1
            elif now == "L" and occupied == 0:
                new = "#"
                num_changes += 1
            else:
                new = now
            seats_new [row] = seats_new[row][:col]+ new + seats_new [row][col+1:]


    seats = seats_new.copy()
   
   
    if num_changes == 0:
        changed = False
    else:
        iterations += 1

    for row in range (len (seats)):
        for col in range (len(seats[0])):
            now = seats [row][col]
            if now == "#":num_occupied += 1
part2Ans = num_occupied
part2Iterations = iterations

print ("Part 1: No iterations ", part1Iterations,"Number occupied: ", part1Ans)
print ("Part 2: No iterations ", part2Iterations,"Number occupied: ", part2Ans)

All that typing takes a while.

(click to show/hide)

// count number ‘adjacent’ to x,y in each of 8 directions, unlimited distance
int countadjacent8x(const CSparse& a, int x0, int y0, int val, int w, int h)
{
int ret = 0;

for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
{
if (!dx&&!dy) continue; // the 9th unwanted NULL direction

for (int x=x0+dx,y=y0+dy ; (x>=0)&&(y>=0)&&(x<=w)&&(y<=h) ; x+=dx,y+=dy) 
{
int c = a.get(x,y);

if (c==val) ret++; // found one
if (c) break; // hit something so on to next direction
}
}

return ret;
}

// produce next iteration from a into b, returns number of changes
int d11iterb(const CSparse& a, CSparse& b, int w, int h)
{
int ret = 0;

for (int x=0; x<=w; x++)
for (int y=0; y<=h;y++)
{
int c = a.get(x,y);

if (c)
{
int n = countadjacent8x(a,x,y,'#',w,h);
if (((c=='L')&&(n==0))||((c=='#')&&(n>=5)))
{
c =‘#’+’L'-c;  // toggle between # and L
ret++;
}

b.set(x,y,c);
}
}

return ret;
}

(click to show/hide)

Alright, smartypants
To be fair - mine includes both parts. And the reading of input data. (I couldn't see that in yours - in fact I think I can only see two function definitions, but that might be just my lack of familiarity with C ).

....Oh, yes - and is built by a novice 

[tonycollinet]

Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. 

(click to show/hide)

import math

def sign(x):
    if x > 0:
        return 1.
    elif x < 0:
        return -1.
    elif x == 0:
        return 1.
    else:
        return x

def getHeadingDeg (n,e):
    quad = [sign (n), sign (e)]
    NE = [1,1]
    SE = [-1,1]
    SW = [-1,-1]
    NW = [1,-1]
   
    if n == 0:
        angle = 90
    else:
        angle = math.degrees(math.atan(abs(e)/abs(n)))
   
    if quad == NE: angle = angle
    elif quad == SE: angle = 180-angle
    elif quad == SW: angle = 180+angle
    elif quad == NW: angle = 360-angle
    return angle

# start get data
input_file = open("12Input.txt", "r")
#data = [(line.strip()).split() for line in input_file]
cmnds = [[line.strip()[:1],int(line.strip()[1:])] for line in input_file]
input_file.close()

# #part 1

heading = 90 #east
nPos = 0
ePos = 0

for cmd in cmnds:
    if cmd[ 0 ]=="N":
        nPos += cmd[1]
    elif cmd [ 0 ]=="S":
        nPos -= cmd[1]
    elif cmd [ 0 ]=="E":
        ePos += cmd[1]
    elif cmd [ 0 ]=="W":
        ePos -= cmd[1]
    elif cmd [ 0 ]=="L":
        heading -= cmd[1]
        if heading < 0:heading += 360
    elif cmd [ 0 ]=="R":
        heading += cmd [1]
        if heading >=360: heading -=360
    elif cmd [ 0 ]=="F":
        nPos += round(cmd [1] * math.cos(math.radians(heading)))
        ePos += round(cmd [1] * math.sin(math.radians(heading)))
       
print ("********************************")
print ("North ",nPos,"East", ePos, abs(nPos)+abs(ePos))
print ("********************************")
#part 2

nWay = 1
eWay = 10
nPos = 0
ePos = 0

for cmd in cmnds:
    if cmd[ 0 ]=="N":
        nWay += cmd[1]
    elif cmd [ 0 ]=="S":
        nWay -= cmd[1]
    elif cmd [ 0 ]=="E":
        eWay += cmd[1]
    elif cmd [ 0 ]=="W":
        eWay -= cmd[1]
    elif cmd [ 0 ]=="L":
        angWayDeg = getHeadingDeg (nWay, eWay)
        dstWay = math.sqrt(nWay ** 2 + eWay ** 2)
        angWayDeg -= cmd[1]
        nWay = round(dstWay * math.cos(math.radians(angWayDeg)))
        eWay = round(dstWay * math.sin(math.radians(angWayDeg)))
    elif cmd [ 0 ]=="R":
        angWayDeg = getHeadingDeg (nWay, eWay)
        dstWay = math.sqrt(nWay ** 2 + eWay ** 2)
        angWayDeg += cmd[1]
        nWay = round(dstWay * math.cos(math.radians(angWayDeg)))
        eWay = round(dstWay * math.sin(math.radians(angWayDeg)))

    elif cmd [ 0 ]=="F":
        nPos += cmd [1] * nWay
        ePos += cmd [1] * eWay
   
       
print ("********************************")
print ("North ",nPos,"East", ePos, abs(nPos)+abs(ePos))
print ("********************************")

[Ben T]

Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. 

The reason you know it won't have is because you (probably) won't end up with integer coordinates.
Problems usually only deal in integers, full stop. They (only very occasionally) use floating point numbers, but then it will be obvious it's a "floating points" question and it will be floating points throughout.
It's very rare to have one that's mainly integers, but you might sometimes have to round off.

[Davef]

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.

Really? not sure how "fast" you want it, mine takes about a seconds although that's in debug and probably includes compilation, they all take that - so I think the actual calculation, if I produced a release binary it would probably be sub-second.

my code is distinctly 'pedestrian', but reasonably efficient enough

(click to show/hide)

Code: [Select]

    public class Day11
    {
        public static async Task Part1(string[] args)
        {
            var matrix = await Matrix.Parse(Console.In);

            int changes;
            do
            {
                matrix = Iterate(matrix, out changes);
            } while(changes > 0);

            await Console.Out.WriteLineAsync(matrix.Cells.Count(c => c.Value == '#').ToString());
        }

        public static async Task Part2(string[] args)
        {
            var matrix = await Matrix.Parse(Console.In);

            int changes;
            do
            {
                matrix = IteratePart2(matrix, out changes);
            } while(changes > 0);

            await Console.Out.WriteLineAsync(matrix.Cells.Count(c => c.Value == '#').ToString());
        }

        private static Matrix Iterate(Matrix m, out int changes)
        {
            changes = 0;
            var newMatrix = new Matrix(m);
            foreach(var c in m.Cells)
            {
                var adjacents = m.AdjacentsIncludingDiagonal(c.Key).ToArray();
                if(c.Value == 'L' && !adjacents.Any(a => m.Cells[a] == '#'))
                {
                    newMatrix.Cells[c.Key] = '#';
                    changes++;
                }
                else if(c.Value == '#' && adjacents.Count(a => m.Cells[a] == '#') >= 4)
                {
                    newMatrix.Cells[c.Key] = 'L';
                    changes++;
                }
            }
            return newMatrix;
        }

        private static Matrix IteratePart2(Matrix m, out int changes)
        {
            changes = 0;
            var newMatrix = new Matrix(m);
            foreach(var c in m.Cells)
            {
                var visible = m.SightlinesIncludingDiagonal(c.Key, '.');
                if(c.Value == 'L' && !visible.Any(a => m.Cells[a] == '#'))
                {
                    newMatrix.Cells[c.Key] = '#';
                    changes++;
                }
                else if(c.Value == '#' && visible.Count(a => m.Cells[a] == '#') >= 5)
                {
                    newMatrix.Cells[c.Key] = 'L';
                    changes++;
                }
            }
            return newMatrix;
        }
    }



where 'Matrix' is a reusable component in my generic library AoCTools:

Code: [Select]

    public class Matrix
    {
        public Matrix() {}

        public Matrix(Matrix matrixToClone)
        {
            Cells = matrixToClone.Cells.ToDictionary(x => x.Key, x => x.Value);
            Length = matrixToClone.Length;
            Height = matrixToClone.Height;
        }

        public readonly Dictionary<MatrixCoord, char> Cells = new Dictionary<MatrixCoord, char>();
        public int Length{get; private set;}
        public int Height{get;private set;}

        public static async Task<Matrix> Parse(TextReader reader)
        {
            var matrix = new Matrix();
            string line;
            int? lineLength = null;
            int y = 0;
            while(!string.IsNullOrEmpty(line = await reader.ReadLineAsync()))
            {
                if(lineLength.HasValue && line.Length != lineLength.Value) throw new InvalidOperationException("Mismatched line lengths");
                lineLength = line.Length;
                for(int x = 0; x < line.Length; x++)
                {
                    matrix.Cells.Add(new MatrixCoord(x, y), line[x]);
                }
                y++;
            }
            matrix.Length = lineLength.Value;
            matrix.Height = y;
            return matrix;
        }

        public IEnumerable<MatrixCoord> AdjacentsIncludingDiagonal(MatrixCoord coord)
        {
            for(int dx = -1; dx <= 1; dx++)
            {
                for(int dy = -1; dy <= 1; dy++)
                {
                    var ox = coord.X + dx;
                    var oy = coord.Y + dy;
                    if(dx == 0 && dy == 0) continue; // this one
                    if(ox < 0 || oy < 0 || ox >= Length || oy >= Height) continue; //out of bounds
                    yield return new MatrixCoord(ox, oy);
                }
            }
        }

        public IEnumerable<MatrixCoord> SightlinesIncludingDiagonal(MatrixCoord coord, char space)
        {
            for(int dx = -1; dx <= 1; dx++)
            {
                for(int dy = -1; dy <= 1; dy++)
                {
                    if(dx == 0 && dy == 0) continue; // this one
                    for(int m = 1;;m++)
                    {
                        var ox = coord.X + m*dx;
                        var oy = coord.Y + m*dy;
                        if(ox < 0 || oy < 0 || ox >= Length || oy >= Height) break; //out of bounds
                        var oc = new MatrixCoord(ox, oy);
                        if(Cells[oc] != space)
                        {
                            yield return oc;
                            break;
                        }
                    }
                }
            }
        }
    }

    public struct MatrixCoord
    {
        public MatrixCoord(int x, int y)
        {
            X = x;
            Y = y;
        }

        public int X{get;}
        public int Y{get;}

        public override bool Equals(object obj)
        {
            return obj is MatrixCoord coord &&
                   X == coord.X &&
                   Y == coord.Y;
        }

        public override int GetHashCode()
        {
            int hashCode = 1861411795;
            hashCode = hashCode * -1521134295 + X.GetHashCode();
            hashCode = hashCode * -1521134295 + Y.GetHashCode();
            return hashCode;
        }
    }


the "trick", which you've probably seen, I recognised it instantly from previous similar problems, is

(click to show/hide)

immutability, don't modify it in place but create a copy (it says in the instructions all transformations happen simultaneously)

Curious enough to see if you can do it in fewer clock cycles, even if you don't need to

that is the way I am doing it (with the slight optimisation of discarding the dots from the matrix to reduce the number of elements ). It is not however an efficient way of solving the problem. You will need to get a slower computer to see the benefits.

[Greenbank]

Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. 

The reason you know it won't have is because you (probably) won't end up with integer coordinates.
Problems usually only deal in integers, full stop. They (only very occasionally) use floating point numbers, but then it will be obvious it's a "floating points" question and it will be floating points throughout.
It's very rare to have one that's mainly integers, but you might sometimes have to round off.

Two variants then that would still be possible given care:-

a) Angles of 30, 45 or 60 degrees. You've then only got to also keep track of 1/2s, sqrt(2) and sqrt(3) as well as integers. The input would be chosen so that the end point (or answer) ends up on an integer set of co-ordinates
b) Movements along arbitrary angles that cancel out, e.g.

R47
F10
R90
F1
R90
F1
R90
F1
L90
F9
R133

Which (if I've got it right) should leave you in the initial state.

[Ben T]

Theoretically it would be possible for intermediate points to be floating point (or multiples of sqrt(2) etc) if he was being mean, but experience tells you he doesn't generally set questions where the description generally talks in integers, and the answer is an integer, but you are expected to have to deal with floating point numbers for intermediate points.

I may yet be proved wrong

My general strategy is make an assumption, and structure the code such that it throws an exception if the assumption is wrong.

[Davef]

Different approach to day 11 part 2. Throws away the 2D grid and just keeps numbered seats ....

(click to show/hide)

int day11b(CSparse& a, int w, int h)
{
int ret = 0;

// go thru matrix and number the seats, starting at 1
int i = 1;
int nn = 0;
POSITION pos = a.GetStartPosition();
while (pos)
{
int x,y,v;
a.GetNextAssoc(pos,x,y,v);
if (v=='L')
{
nn++;
a.set(x,y,i);
i++;
}
}

int *state   = new int[nn+1]; // the state of each of the nn seats plus an extra at 0
int *net = new int[(nn+1)*8]; // the connectivity network - each seat depends on up to 8
int *changes   = new int[nn+1]; // the seats changed on this iteration
state[0] = 0;

// initialise neighbour network - just the once
for (int x0=0; x0<=w; x0++)
for (int y0=0; y0<=h;y0++)
{
int idx = a.get(x0,y0);
if (idx)
{
state[idx] = 0;

idx *= 8;     // e.g. 100..107

for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
{
if (!dx&&!dy) continue; // the 9th unwanted NULL direction

int c = 0;
for (int x=x0+dx,y=y0+dy; !c&&(x>=0)&&(y>=0)&&(x<=w)&&(y<=h); x+=dx,y+=dy) 
c=a.get(x,y);
net[idx++] = c;
}
}
}

    // phew, all set up, lets start iterating
for (int iter = 0;;iter++)
{
int changeidx = 0;
int occupied = 0;

// for each seat
for (int i = 1; i <= nn; i++)
{
// count neighbours
int n = 0;
for (int j = 0; j < 8; j++)
n += state[net[i*8+j]];

int c = state;
occupied += c;
if ((!c&&(n==0))||(c&&(n>=5)))
changes[changeidx++] = i;
}

// apply the changes
for (i = 0; i < changeidx; i++)
state[changes] ^= 1; // toggle between # and L

if (!changeidx) return occupied;
}

return ret;
}

This reduces the work in each iteration dramatically

[Croft]

Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. 

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

[Croft]

Two variants then that would still be possible given care:-

a) Angles of 30, 45 or 60 degrees. You've then only got to also keep track of 1/2s, sqrt(2) and sqrt(3) as well as integers. The input would be chosen so that the end point (or answer) ends up on an integer set of co-ordinates
b) Movements along arbitrary angles that cancel out, e.g.

R47
F10
R90
F1
R90
F1
R90
F1
L90
F9
R133

Which (if I've got it right) should leave you in the initial state.

I wonder if there might be an integer approach for arbitrary integer angles using taxicab geometry. http://sites.science.oregonstate.edu/~tevian/physics/taxicab/taxicab.pdf

You can define trig functions in Manhattan space using modulo arithmetic, which I think would give you a pretty good degree of precision when scaled by a large integer. But your mathematical intuition is much better than mine, so perhaps you'd have a stronger idea as to whether this would be possible.

[tonycollinet]

Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. 

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

Will look at those - thanks.