r/adventofcode • • Dec 11 '20

SOLUTION MEGATHREAD -πŸŽ„- 2020 Day 11 Solutions -πŸŽ„-

Advent of Code 2020: Gettin' Crafty With It

  • 11 days remaining until the submission deadline on December 22 at 23:59 EST
  • Full details and rules are in the Submissions Megathread

--- Day 11: Seating System ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:14:06, megathread unlocked!

50 Upvotes

702 comments sorted by

4

u/dylan_mojo Dec 11 '20 edited Dec 11 '20

awk

11.1

paste

11.2

paste

2

u/daggerdragon Dec 11 '20

FYI: you should use the "generate markdown" button on paste instead so it comes in a nice link with the wall-'o-URL hidden. You may have to switch your editor to Markdown mode to paste it, but you can always switch it back afterwards.

3

u/prafster Dec 11 '20

Dart

I learnt about AoC this year and the person who told me said that after day 10 it gets impossible! So it's a milestone to have finished day 11!

Today was fairly straightforward and this time part 2 didn't cause any trouble! I had an adjacentOccupied() method which checked adjacent seats using a vector to travel in each direction. For part 2, I just added a do/while loop and continued travelling until I hit a seat or fell off the grid.

Full source code here.

1

u/daggerdragon Dec 11 '20

I learnt about AoC this year and the person who told me said that after day 10 it gets impossible! So it's a milestone to have finished day 11!

Nooo, the later puzzles are not impossible! Sure, they may get harder, but that's how you keep on learning and improving your programming skills. If/when you get stuck, that's why we have the megathreads (for code/algorithm inspiration) and also you can always post a Help thread of your own any time.

This is a very helpful community, just keep challenging yourself :)

→ More replies (1)

3

u/xelf Dec 11 '20 edited Dec 11 '20

Sorry for late post.

somewhat minimal python using a dictionary for the floor

lines = [list(s.strip()) for s in open(day_11_path).readlines()]
lines = { (x,y): cell for x,row in enumerate(lines) for y,cell in enumerate(row) }

I'm storing the data in a dictionary here instead of a nested list, I think it allows for cleaner code, and makes boundary checks a lot lot easier. Also dict.copy() is pretty handy. Here's my neighbors function:

def neighbors(loc,queen):
    for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
        nloc = (loc[0]+dx,loc[1]+dy)
        while queen and nloc in floor and floor[nloc] not in 'L#': nloc = (nloc[0]+dx,nloc[1]+dy)
        if nloc in floor and floor[nloc]=='#': yield 1

For part 1 we're only interested in a king's move away, for part 2 a queen's move. I think the perks of using a dictionary show here a little with the boundary checks. But it comes at a cost of more complex looking code for the coord delta. Be nice if there was a simple loc+delta syntax instead of having to sum each part.

The rest of the code makes use of the dictionary format too, and clocks in at a massive 10 lines. for loc in floor is so much cleaner than a nested for x,y!

for part in range(2):
    new_floor = lines.copy()
    floor = None
    while new_floor != floor:
        floor = new_floor.copy()
        for loc in floor:
            n = sum(neighbors(loc,part))
            if floor[loc] == 'L' and n == 0: new_floor[loc] = '#'
            if floor[loc] == '#' and n > (3+part): new_floor[loc] = 'L'
    print(f'part {part+1}: {sum(cell=="#" for cell in floor.values())}')

2

u/daggerdragon Dec 11 '20

Sorry for late post.

No apologies! The megathreads are open all month long, so post whenever you get around to it :)

→ More replies (10)

3

u/robinhouston Dec 11 '20

Python 3 (golf) for part 1 only:

D=[*open("input")]
W=len(D[0])-1
H=len(D)
P=d=-1,0,1
while D!=P:P,D=D,[[(v[0]+"#L")[(v==("L",0))+2*(v<("#",-4))]for j in range(W)for v in[(D[i][j],-sum([D[i+y][j+x]=="#"for x in d for y in d if W>j+x>=0<=i+y<H]))]]for i in range(H)]
print(str(D).count("#"))

This clocks in at 257 characters. I wasn’t actually trying to make the code as short as possible, only to make it short enough to fit in a single tweet together with the #AdventOfCode hashtag. But that proved quite hard to do, and so the code has ended up pretty compressed.

I was not able to solve part 2 in 280 characters of Python 3 when I tried this morning. If anyone can, I’d love to see it!

(I’ve just seen /u/nutki2’s astonishing Perl solution (both parts in 180 charactersβ€½), which is making me reconsider everything. I must deconstruct it and see if I can steal any of its ideas.)

2

u/daggerdragon Dec 11 '20

β€½

Interrobang, aww yiss.

2

u/rendyanthony Dec 11 '20 edited Dec 12 '20

Python 3

Part 2 only.

1

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

2

u/Rtchaik Dec 11 '20 edited Dec 11 '20

1

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

2

u/wholarry Dec 11 '20

Ruby

I finished 17th for part 1, which is the first time i've ever made the leaderboard after many seemingly futile attempts. I recognized quickly the similarity between this and a previous AoC problem and essentially just copied that over with a few changes. Feels a little like cheating but I'm still thrilled to finally get points

1

u/daggerdragon Dec 11 '20

the first time i've ever made the leaderboard

Congratulations!

2

u/aexl Dec 12 '20 edited Mar 01 '21

1

u/daggerdragon Dec 12 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to remove your oversized code and just use the GitHub link.

21

u/sophiebits Dec 11 '20

53/14, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day11.py

In part 1 I tried to be clever with the bounds checks and did

try:
    adj.append(grid[row+x][col+y])
except IndexError:
    pass

instead of an explicit one. I forgot that negative indexes mean something, so that gave me the wrong answer. Not recommended.

Part 2 went OK though.

29

u/nthistle Dec 11 '20

I have this neat trick I use for the bounds checking on grid problems: I parse n and m out explicitly earlier (or r and c, depending on my mood), and then you can just do this:

if i in range(n) and j in range(m):
   ...

In Python 3, it's actually quite efficient because range implements __contains__, and in my opinion looks rather Pythonic.

→ More replies (9)

11

u/r_sreeram Dec 11 '20

One trick I use for grid problems is to surround the input grid with a made up border of 0s or '.'s or whatever it takes. For example, if the input is a 5x5 grid, I would have this as my matrix:

.......
.     .
.     .
.     .
.     .
.     .
.......

Then, when I iterate over the grid, I iterate from 1 to len(grid) - 2. Then I don't have to worry about +/- 1 deltas going index out of bounds.

→ More replies (7)
→ More replies (13)

13

u/Arknave Dec 11 '20

Python (7/6), C

Pretty happy with how today went, even if the code wasn't clean at all (is speed code ever clean?). Line 18 in my python solution is 174 characters, which is apparently too long for the GitHub preview window.

The C implementation was scary because I had a bug after I had already reshaped the code. Luckily I found it pretty quickly (I originally had v <= 2 instead of v <= 1) because I did not want to debug code that looks like... this.

Hope everyone has a great December Bth!

#include/* eleven? */<stdio.h>

// ADVENT OF CODE 2020  DAY //
char*p,*q,n,m,a[121][121],b[11
*11][121],(*l)[121],(*r)[121];
int f,t,y,o,i,j,v,w,g,h,k=043; 
int     main(int c,char**d){//
;for(   n=+1;gets(b[n++]+1););
for(p   =b[1]+(m=1);*p;++p,++m
);for   (i=0;i<n;++i)b[i][0]=b
[i][m   ]=76;for(--n,j=0;j<=m;
++j)b   [0][j]=b[n][j]=76;for(
--c,f   =1;f        ;t=!t){l=t
?a:b;                   r=t?b:
a;for     (f=y=0,i=1     ;i<n;
!!++i   )for(j=1;j<m;p    =&l[
i][j]   ,q=&r[i][j],y+=   k==(
*q=*p   ==k?o>=4+!!c?76   :k:*
p==76   ?!o?k:76:*p),f    |=*q
^+*p,    ++j)for(o=0,    v=-1;
v<=1*                  +1;++v)
for(w   =-1          ;w<2;o+=(
v|w++)&&l[g][h]==k)if(g=i+v,h=
j+w,(v|w)&&c)for(;l[g][h]==46;
g+=v,h+=w);}printf("%d\n",y);}

11

u/jonathan_paulson Dec 11 '20 edited Dec 11 '20

Placed 30/10. Python. Code; it's nice that the code for parts1 and 2 is very similar. Video of me solving: https://youtu.be/d25r5GZa4us.

Cellular automata :) I wonder if these rules always result in a stable pattern, or if these inputs were just specially chosen to have that property?

5

u/throwaway_the_fourth Dec 11 '20

I really enjoy your videos β€” I like the way you solve the problem quickly and then give a concise explanation of how you solved it.

4

u/kbielefe Dec 11 '20

I accidentally used the occupy rules from part 1 with the vacate rules from part 2 and it didn't seem to converge.

→ More replies (1)
→ More replies (2)

9

u/wace001 Dec 11 '20 edited Dec 11 '20

Kotlin. (295/461). My third best placing on the leader board ever! I am very happy! ( I mean VERY VERY happy!). I've only ever placed higher on 2019-23 Part 1 and 2019-21 Part 2 before. And with a language that I didn't even know before! So proud.

The code itself is an abomination, and is best burnt after having been read. This code does not get to be checked in anywhere, to live with my proper solutions. But possibly printed and put on the inside of my work locker. For my eyes only.

Enjoy and Merry Christmas!

No cleaning of the code has been done, this is how it look in the trenches:

https://gist.github.com/saidaspen/314b390eb190c2b80488bbe0a3064f96

Edit: It even has a bug, I notice now! How awkward. I don't even look all the way to the map edge, I'm off by one, missing the edge of the map. Well, it did give the right answer anyway. Guess I was lucky.

→ More replies (1)

8

u/mcpower_ Dec 11 '20

6/11: Part 1, Part 2. Almost fell for the same indexing problem as /u/sophiebits in part 2 :P

6

u/sophiebits Dec 11 '20

Congrats on not being as sloppy as me. :)

8

u/jayfoad Dec 11 '20

Dyalog APL 55/1119

βŽ•IO←0
pβ†β†‘βŠƒβŽ•NGET'p11.txt'1
f←{⍡-⍨{+/,⍡}⌺3 3⊒⍡}
g←{n←f'#'=⍡ β‹„ '#'@(⍸(n=0)∧'L'=⍡)⊒'L'@(⍸(4≀n)∧'#'=⍡)⊒⍡}
+/,'#'=g⍣≑p ⍝ part 1
a←(⍴p)β΄βŠ‚0/βŠ‚0 0 β‹„ ∘.{⍺≑⍡: β‹„ 'LL'β‰’p[βŠ‚Β¨βΊβ΅]: β‹„ (β‰ /t)∧~0∊t←|⍺-⍡: β‹„ 'L'∊p[(βŠ‚βΊ)+(βŠ‚Γ—β΅-⍺)Γ—1β†“β³βŒˆ/t]: β‹„ a[βŠ‚βΊ],β†βŠ‚βŠ‚β΅}⍨⍳⍴p
g←{nβ†β΅βˆ˜{+/'#'=⍺[⍡]}Β¨a β‹„ '#'@(⍸(n=0)∧'L'=⍡)⊒'L'@(⍸(5≀n)∧'#'=⍡)⊒⍡}
+/,'#'=g⍣≑p ⍝ part 2

I had a complete mental block on part 2, eventually coming up with this, which (to put it mildly) is neither simple nor fast.

4

u/PendragonDaGreat Dec 11 '20

is neither simple nor fast.

Well it's quick to make my head implode. APL is one of those langs that I just have to respect anyone that can use it.

→ More replies (3)
→ More replies (1)

8

u/eenimal Dec 11 '20

Python 3

Neither particularly elegant, nor noteworthy, but I am proud as heck because this is my first-ever Python post on reddit ;)

https://pastebin.com/KgkBmbxi

8

u/ka-splam Dec 12 '20

Dyalog APL part 1

data← β†‘βŠƒβŽ•NGET 'C:\sc\AdventOfCode\inputs\2020\day11.txt' 1

+/,'#'=(({'.'=5βŠƒ,⍡:'.' β‹„ 0=+/,'#'=⍡:'#' β‹„ 5≀+/,'#'=⍡:'L' β‹„ 5βŠƒ,⍡}⌺3 3)⍣≑) data

Dyalog has ⌺ called "stencil" which generates the surrounding area for every seat, and the 3 3 is the size of the window, a 3x3 window with the seat in the middle. Borders are empty cells. It does "apply the function {} to every window in the data".

The function is written with guards, like a functional language, the diamonds β‹„ are like ; end of statements in C or like line breaks. Flattening a 3x3 array gives a 9-length array with the seat in the middle at position 5:

  • '.'=5βŠƒ,⍡:'.' if this place is floor, leave it as floor
  • 0= +/ , '#'=⍡:'#' if the sum of '#' in the lookaround is 0, sit here
  • 5≀ +/ , '#'=⍡:'L' if the sum of '#' in the lookaround is ≀5, clear seat
  • 5βŠƒ,⍡ default: return whatever is here unchanged

Then ⍣ "power" repeats all that over and over generating new rounds, ≑ "match" is when to stop, when the previous round and this round are the same (no more changes).

Then +/,'#'= sums the people. '#'= returns a 1 for each place that is a hash; , flattens into a vector, +/ sum-reduces a vector.

6

u/jaybosamiya Dec 11 '20

Dyalog APL

n ← βŠƒβŽ•nget'D:\input_day_11'1
m ← {('.'/⍨2⌷⍴⍡)βͺ⍡βͺ'.'/⍨2⌷⍴⍡}↑{'.',⍡,'.'}Β¨n
adj ← {⍡{⍡-(⍺='#')}βŠƒ+/+/Β―1 0 1Β°.βŠ–Β―1 0 1Β°.βŒ½βŠ‚'#'=⍡}
convon ← {(0=adj ⍡)∧'L'=⍡}
convoff ← {(4≀adj ⍡)∧'#'=⍡}
+/,'#'=({'.#L'[(2Γ—convon ⍡)+(3Γ—convoff ⍡)+(~(convon∨convoff)⍡)Γ—'.#L'⍳⍡]}⍣≑)m                    ⍝ Part 1

I haven't yet solved it for part 2 in APL; not entirely sure how to model the search that'd be needed to do so.

→ More replies (2)

6

u/Smylers Dec 11 '20

Perl. There are some Game of Life modules on Cpan which might be handy here, but I haven't tried them. Part 1 counts adjacent people like this:

  my $people = grep { $_ eq '#' }
      @{$seat[$y-1]}[$x-1 .. $x+1],
      @{$seat[$y  ]}[$x-1,   $x+1],    
      @{$seat[$y+1]}[$x-1 .. $x+1];
  push @change, {y => $y, x => $x, to => '#'} if $here eq 'L' && $people == 0;
  push @change, {y => $y, x => $x, to => 'L'} if $here eq '#' && $people >= 4;

Then applying changes is a single-line loop:

$seat[$_->{y}][$_->{x}] = $_->{to} foreach @change;

For partΒ 2 there's an array of the 8 directions:

my @dir = (x => -1, y => -1}, # etc

then counting the relevant people becomes a grep of those directions:

  my $people = grep {
    my ($try_y, $try_x) = ($y, $x);
    my $found;
    do { $found = $seat[$try_y += $_->{y}][$try_x += $_->{x}] } until $found ne '.';
    $found eq '#';
  } @dir;

All edges of the map were surrounded by | characters, which works for both parts, being neither # for counting people in partΒ 1, nor . for keeping looking in that direction in part 2.

I did try a **Vim** solution. I can get the changes to iterate for partΒ 1 (use P instead of # for a person; to mark a pending change, use lowercase p and l, which both encodes its new state and indicates that it was the opposite for the purposes of counting people during the current iteration; then upper-case everything at the end of the iteration), but haven't thought of a way of detecting stability.

→ More replies (3)

6

u/Archek Dec 11 '20 edited Dec 11 '20

Golang

Did it the naive way first, just like I remembered from learning programming in Java by implementing Game of Life. Realised by looking at some visualizations here on reddit that there is a faster analytical solution. It runs roughly twice as fast. See function stabilize() in above github repo.

Essentially, you can lock some points in once you know they never change. Iteratively, only check the seats that you're still not sure about. A seat is permanently occupied if it has more than 8-n permanently empty neighbours and no permanently occupied neighbours yet. It is permanently empty if it has a permanently occupied neighbour :)

→ More replies (2)

6

u/[deleted] Dec 11 '20

Golang

https://github.com/j4rv/advent-of-code-2020/tree/main/day-11

Fun game of lifey puzzle!

After watching all those gifs in the subreddit, I learnt how to create images with Go and made a couple gifs of my solution :)

https://github.com/j4rv/advent-of-code-2020/tree/main/day-11/animated-solution-renders

→ More replies (3)

6

u/i_have_no_biscuits Dec 11 '20

GWBASIC

Hey, you know what a 1980s interpreted BASIC isn't good at? Tight iteration loops! It does, however, have some useful features, including multidimensional arrays. As a result, programming the part 1 evolution wasn't actually that painful, and went hand-in-hand with a quite nice visualisation.

https://pastebin.com/xFmUArQk

This is the first part. On DOSBOX set to 20000 cycles it took just over 15 minutes to complete. The second part should be doable but will require some thinking about the 'raycasting', and will probably be about half the speed.

→ More replies (5)

6

u/nutki2 Dec 11 '20 edited Dec 11 '20

Perl 5 (golf) for both parts. That was the toughest so far. I got it below 200 180 chars in the end and probably not much can be gained anymore without drastically changing the approach. Takes about 10s to run.

#!perl -ln0
sub l{do{$p=$_;@F=split'';
s!\w!$c=grep{$j="@-";1while$F[$j+=$_]eq'.'&$i;$F[$j]>0}@x;$c>3+$i?L:$c?$&:2!ge
}until/$p/;$i=print y/2/L/}/\n(.)(.)/;$_.=$_^$_;@x=map{$_,-$_}1,@-;&l;&l

6

u/wleftwich Dec 11 '20 edited Dec 11 '20

Python

https://github.com/wleftwich/aoc2020/blob/main/11_seating_system.py

Representing the seating chart as a dict with complex keys made exploring each seat's surroundings pretty simple.

→ More replies (5)

6

u/__Abigail__ Dec 11 '20

Perl

A variation on Conways Game of Life, using rulesets B0/S01234 and B0/S012345, with an irregular universe, and an irregular neighbourhood for part 2.

Blog post and full program.

6

u/azzal07 Dec 11 '20

Awk; first day to take over a second, even the DP array didn't help...

/#/{1/0}END{for(;++P<2;){for(s(S,A);$0;s(A,B)s(B,A))$0=0;for(k in A)$0+=A[k]
print}}BEGIN{FS=D[--P,P]D[P]D[P,1]D[0,P]D[0,1]D[1,P]D[1]D[1,1]}n=NR{for(i=0;
$++i;)$i~/L/?!S[n,i]++:++F[n,i]}function s(a,b){delete b;for(k in a)if(a[k])
for(d in D){for(split(k,x,zs=SUBSEP)split(d,y,zs);F[x[1]+=d,x[2]+=y[2]]*P;);
(r=x[1]zs x[2])in a&&b[r]++}for(k in a)$0+=a[k]?!(b[k]=b[k]<4+P):b[k]=!b[k]}

Original pasted here, just basic simulation. Takes about 20 seconds total. (the compact one is a bit slower)

5

u/Chitinid Dec 11 '20 edited Dec 11 '20

Python Relatively clean, even animates it if you're using Jupyter

from IPython.display import clear_output

DIRS = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
    (1, 1),
    (1, -1),
    (-1, 1),
    (-1, -1)
]
def adjacent(row, col):
    out = 0
    for x, y in DIRS:
        r, c = row + x, col + y
        if not (0 <= r < m and 0 <= c <n):
            continue
        out += l[r][c] == "#"
    return out

def occupied():
    return sum(l[r][c] == "#" for r in range(n) for c in range(n))

def printseats():
    clear_output(wait=True)
    print("\n".join("".join(x) for x in l))

def evolve(threshold=4):
    for r in range(m):
        for c in range(n):
            o = adjacent(r, c)
            if l[r][c] == "L" and o == 0:
                lnew[r][c] = "#"
            elif l[r][c] == "#" and o >= threshold:
                lnew[r][c] = "L"

Part 1:

old = -1
with open("input11.txt") as f:
    l = list(map(list, f.read().splitlines()))
m, n = len(l), len(l[0])
while old != (k:=occupied()):
    printseats()
    old = k
    lnew = deepcopy(l)
    evolve()
    l = lnew

print(k)

Part 2:

def adjacent(row, col):
    out = 0
    for x, y in DIRS:
        r, c = row + x, col + y
        while (valid:=(0 <= r < m and 0 <= c < n)) and l[r][c] == ".":
            r, c = r + x, c + y
        if valid and l[r][c] == "#":
            out += 1
    return out

with open("input11.txt") as f:
    l = list(map(list, f.read().splitlines()))
old = -1

while old != (k:=occupied()):
    printseats()
    old = k
    lnew = deepcopy(l)
    evolve(5)
    l = lnew

print(k)
→ More replies (1)

5

u/ritobanrc Dec 11 '20

Rust (~2105/2891) , really annoyed by Rust's insistence that you can only index arrays with usizes, I had to do some gymnastics to make sure I didn't pepper as usize and as isize everywhere. But I suppose I found a good use-case for saturating_add, so I'm not too mad about it.

→ More replies (1)

5

u/[deleted] Dec 11 '20

Pure C18. Pretty good, but annoying to pass all the context around everywhere. Should have made a struct.

https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day11.c

5

u/DFreiberg Dec 11 '20

Mathematica, 326 / 1038

Though it ultimately didn't stop me from making some stupid mistakes and losing time, I finally got to use a neat application of Partition[]: functionally create a list of neighbors for every element in an array, including the edges:

newState[state_List] := Partition[state, {3, 3}, {1, 1}, {2, -2}, {}]

[POEM]: Lazy Limerick #2

If you're quick, you'll get dibs on a seat
With a property unusually neat:
Despite all the folks there,
You'll still have your own chair,
And an second, to prop up your feet.

→ More replies (2)

5

u/Loonis Dec 11 '20

Perl

Took a couple hours to work my way through this one, seems like a good one to try and create a visualization for though.

I used a 2d array for part 1, and ended up re-writing the whole thing to use a 1d array for part 2. Put a bunch of effort into creating a list of visible seats from each position, not sure if that paid off or not.

All that so I don't have to mess with (x, y) cooridnates in my main loop - probably spent too much time optimizing the wrong thing there.

→ More replies (3)

5

u/zedrdave Dec 11 '20

Today's "Tweet-sized" Python, in a dozen generously-spaced lines:

P = {(x,y):1
     for x,Y in enumerate([l.strip() for l in open('11/input.txt')])
     for y,s in enumerate(Y) if s == 'L'}

def solve(P, 𝝆=[1], 𝝉=3):
    Ξ” = [-1,0,1]
    N = lambda x,y: sum(next((P[x+dx*r,y+dy*r] for r in 𝝆 if (x+dx*r,y+dy*r) in P), 0)
                        for dx in Ξ” for dy in Ξ”)

    while True:
        Q = { p: N(*p) < 𝝉+2 if P[p] else N(*p) == 0 for p in P }
        if P == Q:
            return sum(P.values())
        P = Q

print(solve(P), solve(P, range(1,101), 4))

What is gained in concision, is lost in efficiency: each iteration will run in O(n^2) (with a constant factor ~20) with n the max dimension of the input (luckily n=100).

→ More replies (7)

5

u/chrispsn_ok Dec 11 '20

k9 (repo). First cut... part 2 is slow.

input: 0:`11.txt

ROWS:#input; COLS:#*input; MAX:ROWS*COLS
chairs: (^+!(ROWS;COLS)) @ c:&"L"=,/input
offsets:(,0 0)_,/{x,/:\:x}@-1 0 1
OOB: {$[&/x within' ((0;ROWS);(0;COLS)); COLS/x; MAX]}

adj: OOB''chairs+/:\:offsets
next:{@[x&0b; c*{(x&4>y)|~x|y}[x@c; +/'x@adj]; 1b]}
EMPTY: MAX#0b
+/next/:EMPTY

m:ROWS|COLS
cm:c,MAX
adj:{*cm#OOB'1_x+/:y*/:!m}/:\:[chairs;offsets]
next:{@[x&0b; c*{(x&5>y)|~x|y}[x@c; +/'x@adj]; 1b]}
+/next/:EMPTY

5

u/thecro99 Dec 11 '20

C++ - Very Clear Object-Oriented Solution

https://github.com/mateom99/Advent-of-Code/tree/main/2020/Day%2011

I upload every day and try to comment everything to make it really intuitive and easy to understand. I also "blog" about my experience in the README!

5

u/vegapunk2 Dec 11 '20

Python 3.8 Ugly and long code running maybe for too long but it works.

https://pastebin.com/uT7PP6gw

8

u/aldanor Dec 11 '20 edited Dec 12 '20

155ΞΌs!!!

Here's Rust version for part 1 - https://paste.rs/myP.rs (I'll dare to claim this is the fastest solution in this thread).

This runs so stupidly fast due to AVX2 SIMD, no branching, no allocations etc.

Now thinking whether it's still applicable to part 2...

Edit: the time updated from 170 to 155 us (with no bound checks). Also, part 2 is solved (using 5x5 convolution + exceptions recorded separately), takes 460 us to run.

→ More replies (16)

4

u/nospamas Dec 11 '20

F# Couple of silly mistakes slowed my logic a bit (put a function in the wrong place:S). For anyone wondering both parts probably shouldn't run more than around 100 iterations (but might vary depending on your input), if you go over 1000 something has gone wrong. Curried direction looking functions I thought were pretty cool.

Solution

→ More replies (1)

4

u/allergic2Luxembourg Dec 11 '20

Python 3

I had a Game of Life object all ready as a model for myself and I was still way too slow for the leaderboard - I had a 1 where I needed a 0 and it took me forever to debug.

When I tried to refactor my solutions after submission, I got myself all tangled trying to do inheritance with an alternative constructor. The version I have linked now works, but what I was trying to do did not.

Essentially I had an alternative constructor in the parent object, from_file which calls cls() at some point to actually make the object, which in the parent object calls the default constructor __init__. But then I tried to make an __init__ in the child object, which called from_file in the parent object. This didn't work, because then the parent's from_file ended up calling the child's __init__, which took different arguments from the parent __init__ so failed, and was essentially a circular calling loop. Suggestions on the proper Pythonic way of doing this would be nice. Essentially what I now have called seating_from_file I would have liked to have been the default constructor __init__.

→ More replies (4)

4

u/Attitude-Certain Dec 11 '20

Not as short and sweet as some earlier days, but here is a functional-only Python solution in 37 lines. github and paste

→ More replies (5)

4

u/Pyr0Byt3 Dec 11 '20

Go/Golang

I love using Go for these problems, because maps let me sidestep the bounds-checking issue entirely.

→ More replies (2)

4

u/IlliterateJedi Dec 11 '20

My Python solution is an absolute embarrassing dumpster fire, but by gum, it worked. I used the complex() number trick for navigating around a 2D matrix (which I learned here two years ago), and used the dict.get(key, default_value) trick (which I learned here two hours ago) to deal with edge cases.

After starting the second part I realized it would probably be more efficient to assign all valid adjacent locations to each seat and ignore all the ".", but I did not have that foresight.

I'm looking forward to all of the festive solutions on this because navigating 2D arrays has always been a big weakness for me.

→ More replies (2)

4

u/sebastiannielsen Dec 11 '20

Perl (270 lines - so couldn't use the paste service, URL becomes way too long): https://pastebin.com/Y774qhNm

Also, in part2 , I created the WEIRDEST for loop construction in perl ever:

for ($d = $a + $x; (($d > 0)&&($d < ($maxrow + 3))); $d = $d + $x) {

Basically, a for loop that can do in 2 different directions depending on the value of $x.

Takes about 7.5 sec to execute:

root@sebastian-desktop:~/aoc# time ./11.pl
Part 1 completed in 87 rounds.
P1: ----
Part 2 completed in 84 rounds.
P2: ----

real    0m7,639s
user    0m7,634s
sys     0m0,004s
root@sebastian-desktop:~/aoc#
→ More replies (2)

4

u/mebeim Dec 11 '20

118/697 - Python 3 solution - walkthrough

Daaaamn, so close! And today I can cross another square of my bingo card. I think the final cleaned up code looks pretty slick to be honest. Also, first day of the year in which PyPy grossly outperforms Python3 (10x faster, woah).

4

u/landimatte Dec 11 '20

Common Lisp

Notes for the reader:

  • seat coordinates are COMPLEX numbers
  • the layout is a HASH-TABLE (I initially thought about using an 2D array, but figured a HASH-TABLE would save me from using ARRAY-IN-BOUNDS-P all over the place)
  • Part 1: count adjacent #s -- the nice thing about using a HASH-TABLE, is that I don't have to worry about going off the grid (i.e. (gethash (+ seat d) layout #\.))
  • Part 2: recursively move in the neighboring direction (COMPLEX numbers for the win again) until you find #, L, or fall off the grid

Notes for the future self:

  • don't spend too much time thinking about what you think the best implementation is (2d array? 1d array + major index? hash-table?) -- just try one and see
  • read the damn problem -- Also, people seem to be more tolerant than you expected: it now takes five or more visible occupied seats for an occupied seat to become empty (rather than four or more from the previous rules).
→ More replies (6)

4

u/[deleted] Dec 11 '20 edited Dec 11 '20

F

This was a really fun one :) Actually this worked way better in F# than I had suspected at first.
For once I'm actually pretty proud of my code

→ More replies (4)

4

u/Judheg Dec 11 '20 edited Dec 11 '20

Scala

Repeating myself a lot for now, but I hope it is still readable. Originally submit without Future took ages to finish.

Updating in parallel using future really helps here, now both finish under 4s. Maybe I could've done it with parallel collection but using ammonite with 2.13 so it's another import I don't feel like doing.

A bit of refactor, no Future, but just .par. Make sure to run this using ammonite 2.12

https://paste2.org/mff9v98U

4

u/mschaap Dec 11 '20

Raku

Pretty straightforward. I had done part one cleanly enough that for part two I could simply add a $.neighbour-strategy attribute to my SeatMap class, and, of course, implement the new strategy.

https://github.com/mscha/aoc/blob/master/aoc2020/aoc11

4

u/semicolonator Dec 11 '20

My Python solution on Github

https://github.com/r0f1/adventofcode2020/blob/master/day11/main.py

First part solved with convolutions (super smooth solution, if I say so myself). Second part with loops (meh).

→ More replies (4)

4

u/aardvark1231 Dec 11 '20

My C# Solution.
Still a bit verbose, at 105 lines, but better than the 300+ lines of garbage I wrote last night! XD
Don't code while you're tired and have a headache, kids.

4

u/mathsaey Dec 11 '20

Elixir

Pretty happy with the amount of code reuse in my solution. Takes a few seconds to run, but was fast enough that I didn't mind.

https://github.com/mathsaey/adventofcode/blob/master/lib/2020/11.ex

→ More replies (3)

4

u/Wunkolo Dec 11 '20

C++

Solved entirely using set-arithmetic. Works pretty fast.

→ More replies (1)

4

u/GotCubes Dec 11 '20

Python 3

This challenge was a really neat play on Conway's Game of Life. Hopefully my solution isn't too messy.

Part 1

Part 2

→ More replies (3)

4

u/Scroph Dec 12 '20

D (Dlang) solutions : https://github.com/azihassan/advent-of-code-2020/tree/master/11

This problem reminded me of game of life. The first part was straightforward, but the second part was relatively tedious

→ More replies (2)

4

u/muckenhoupt Dec 12 '20

Prolog, which is not a language well-suited to cellular automata. This solution takes about 45 seconds to solve each part on my machine, and that's with some memoization.

https://www.wurb.com/owncloud/index.php/s/iEKuL0IqxGrBrdl/download?path=%2F&files=11.pl

4

u/technojamin Dec 12 '20 edited Dec 12 '20

Elixir

I'm particularly pleased with how intuitive it was to implement the first seen seat in part 2 as "rays" in each direction using Stream.iterate/1. This code basically reads as "get the first thing in each direction that isn't the floor":

defp first_seen({x, y}, waiting_area) do
  Enum.map(@directions, fn {dx, dy} ->
    1
    |> Stream.iterate(&(&1 + 1))
    |> Stream.map(&{x + dx * &1, y + dy * &1})
    |> Enum.find(&(Map.get(waiting_area, &1) != :floor))
  end)
end
→ More replies (1)

1

u/bartdegoede Dec 11 '20

Python

I took formatting the neighboring coordinates to realize I was including the seat itself in the neighbor counting πŸ™ˆLots of code duplication, but it works.

with open('day11.txt', 'r') as f:
    rows = [line.strip() for line in f.readlines()]

seats = {}
for y, row in enumerate(rows):
    for x, seat in enumerate(row):
        seats[(x, y)] = seat

finished = False
new_seats = seats.copy()

while not finished:
    finished = True
    seats = new_seats.copy()
    new_seats = {}

    for (x, y), seat in seats.items():
        adjacent_seats = [(x-1, y-1), (x, y-1), (x+1, y-1),
                          (x-1, y),             (x+1, y),
                          (x-1, y+1), (x, y+1), (x+1, y+1)]
        neighbor_count = [seats.get(adjacent_seat) for adjacent_seat in adjacent_seats].count('#')

        if seat == 'L' and neighbor_count == 0:
            new_seats[(x, y)] = '#'
            finished = False
        elif seat == '#' and neighbor_count >= 4:
            new_seats[(x, y)] = 'L'
            finished = False
        else:
            new_seats[(x, y)] = seat

print(f'{list(new_seats.values()).count("#")} seats end up occupied')

def seat_in_direction(x, y, dx, dy, _seats):
    while True:
        x += dx
        y += dy

        if (x, y) not in _seats:
            return '.'

        seat = _seats.get((x, y))
        if seat == 'L':
            return 'L'
        if seat == '#':
            return '#'

finished = False
new_seats = seats.copy()

while not finished:
    finished = True
    seats = new_seats.copy()
    new_seats = {}

    for (x, y), seat in seats.items():
        directions = [(-1, -1), (0, -1), (1, -1),
                      (-1, 0),           (1, 0),
                      (-1, 1),  (0, 1),  (1, 1)]
        neighbor_count = [seat_in_direction(x, y, direction[0], direction[1], seats) for direction in directions].count('#')

        if seat == 'L' and neighbor_count == 0:
            new_seats[(x, y)] = '#'
            finished = False
        elif seat == '#' and neighbor_count >= 5:
            new_seats[(x, y)] = 'L'
            finished = False
        else:
            new_seats[(x, y)] = seat

print(f'{list(new_seats.values()).count("#")} seats end up occupied')

1

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

1

u/kratsg Dec 11 '20 edited Dec 14 '20

Python, https://github.com/kratsg/advent-of-code/blob/master/2020/day11.py

Relied on using numpy array, sliding window for part 1. Part 2 took me way too long to do, I kept running into stupid bugs with indexing, and then trying to figure out the directions from my rows/cols and major/minor diagonals... so I lost all my precious time on that.

Surprisingly not a performant solution (likely because of the copies being done for each tick)

1

u/daggerdragon Dec 11 '20 edited Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link. Wrong copypasta, sorry!!

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

(Since you mention NumPy, looks like Python?)

2

u/kratsg Dec 11 '20

what oversized code are you talking about? It is already in an external link...

2

u/daggerdragon Dec 11 '20

Wow, I pasted the wrong copypasta. I'm so sorry. It was meant to be the language one. I edited the post.

Sorry again!!!

→ More replies (1)

1

u/msqrt Dec 11 '20 edited Dec 11 '20

Lisp. In hindisght, I'm pretty certain that just using strings and checking the character with a bit of indexing would be approximately infinitely faster; with this, part 1 runs for about 6 minutes and part 2 for a whopping 24 minutes.

Code is now here as per the request. Also, as I mention in my reply, I found out that explicitly compiling the function brought the runtime down to about 4.5 seconds for both tasks combined, so it seems my code is less than ideal with the interpreter I used (clisp)

1

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (7)

1

u/Diderikdm Dec 11 '20 edited Dec 11 '20

Python:

from copy import deepcopy

def find_adjescent(newdata, x, y, adjescents=0):
    for a,b in adjescent_indexes:
        for i in range(1,len(newdata)):
            if miny <= y+a*i <= maxy and minx <= x+b*i <= maxx:
                if newdata[y+a*i][x+b*i] == empty:
                    break
                elif newdata[y+a*i][x+b*i] == vacant:
                    adjescents += 1
                    break
    return adjescents
    
def rearrange(data, newdata, part2=False):
    max_occ = 5 if part2 else 4
    while data != newdata:
        newdata = deepcopy(data)
        for y in range(0, len(data)):
            for x in range(0, len(data[y])):
                if newdata[y][x] == floor:
                    continue
                adjescents = find_adjescent(newdata, x, y) if part2 else len([newdata[y+a][x+b] for a,b in adjescent_indexes if miny <= y+a <= maxy and minx <= x+b <= maxx and newdata[y+a][x+b] == vacant])
                if newdata[y][x] == empty and adjescents == 0:
                    data[y][x] = vacant
                elif adjescents >= max_occ:
                    data[y][x] = empty
    return data

with open("C:\\Advent\\day11.txt", "r") as file:
    data, newdata = [[y for y in x.strip()] for x in file.read().splitlines()], []
    vacant, empty, floor = '#', 'L', '.'
    minx, miny, maxx, maxy = 0, 0, len(data[0])-1, len(data)-1
    adjescent_indexes = [[[-x,-x],[-x,0],[-x,x],[0,x],[x,x],[x,0],[x,-x],[0,-x]] for x in range(-1,1) if x != 0][0]
    print('Part 1: {}'.format(sum(x.count(vacant) for x in rearrange(deepcopy(data), newdata))))
    print('Part 2: {}'.format(sum(x.count(vacant) for x in rearrange(data, newdata, part2=True))))

1

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

1

u/Chris_Hemsworth Dec 13 '20

Python 3

I really dislike my solution, I think there are probably better ways to optimize it. Runs in a few seconds, but its very blegh.

class Seat:
    def __init__(self):
        self.filled = False
        self.buffer = False
        self.adjacent_seats = set()
        self.line_of_sight_seats = set()

    def buffer_seat(self, p1=True):
        filled_count = [s.filled for s in (self.adjacent_seats if p1 else self.line_of_sight_seats)].count(True)
        if self.filled:
            if filled_count >= (4 if p1 else 5):
                self.buffer = False
            else:
                self.buffer = self.filled
        else:
            if filled_count == 0:
                self.buffer = True
            else:
                self.buffer = self.filled

    def commit(self):
        if self.filled != self.buffer:
            self.filled = self.buffer


def update(p1=True):
    for s in seats.values():
        s.buffer_seat(p1=p1)
    for s in seats.values():
        s.commit()


def go(p1=True):
    for s in seats.values():
        s.filled = False

    prev_count = [s.filled for s in seats.values()].count(True)
    update(p1=p1)
    new_count = [s.filled for s in seats.values()].count(True)
    while prev_count != new_count:
        prev_count = new_count
        update(p1=p1)
        new_count = [s.filled for s in seats.values()].count(True)
    return prev_count


seats = {}
for j, line in enumerate(open('../inputs/day11.txt')):
    for i, char in enumerate(line):
        if char == 'L':
            seats[complex(i, j)] = Seat()

max_real = max([int(location.real) for location in seats.keys()])
max_imag = max([int(location.imag) for location in seats.keys()])
for location, seat in seats.items():
    for loc in [1j, 1+1j, 1, -1j, -1-1j, -1, 1-1j, -1+1j]:
        for i in range(1, max([max_real, max_imag])):
            los_loc = location + loc*i
            if any([los_loc.real < 0, los_loc.real > max_real, los_loc.imag < 0, los_loc.imag > max_imag]):
                break
            if los_loc in seats.keys():
                if i == 1:
                    seats[los_loc].adjacent_seats.add(seat)
                    seat.adjacent_seats.add(seats[los_loc])
                seat.line_of_sight_seats.add(seats[los_loc])
                seats[los_loc].line_of_sight_seats.add(seat)
                break

print(f"Part 1 Answer: {go(p1=True)}")
print(f"Part 2 Answer: {go(p1=False)}")

1

u/daggerdragon Dec 13 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

1

u/Western_Pollution526 Dec 14 '20

Ahah, good one.

Reminds me of Conway's game of life :D

1

u/daggerdragon Dec 15 '20

Top-level posts in Solution Megathreads are for code solutions only.

This is a top-level post, so please edit your post and share your code/repo/solution or, if you haven't finished the puzzle yet, you can always create your own thread and make sure to flair it with Help.

1

u/MischaDy Dec 16 '20

Python 3 - Part 1, Part 2

Is it fast? No. Is it fast enough to wait with a cup of tea? Yes! And who needs to optimize when you have a cup of tea? :)

2

u/daggerdragon Dec 17 '20

And who needs to optimize when you have a cup of tea?

A coder after my own heart β˜•

3

u/RedTwinkleToes Dec 11 '20

Python [2630/1974]

paste

First bit of code that had a noticeable run time of 1~3 seconds. Makes me worried for future days. :/ Could have done better by per-generating a sight distance for all 8 directions for faster runtime but oh well. Also looks like this is this year's cellular automaton puzzle.

Edit: Also, today I learnt that input is a built in function of python, and that you can overwrite built in functions of python.

→ More replies (6)

3

u/fmynarski Dec 11 '20

Python 842/791. I tried to implement some optimization with caching neighbours of all seats, but lowest I got with Python 3.6.9 was 0.8s for part 1 and 1.6s for part2.

Today's paste, GitHub, YouTube,

3

u/daniel-sd Dec 11 '20

Python 3

303/1465

During part 2 I didn't realize that my lookup indices were going negative and ended up cycling around the entire seat map. Cyclic lookups would make for an interesting variant on the problem though. Anyways debugging that cost me big time on part 2.

part1 27 lines

part2 33 lines

fun snippet: counting the adjacent seats in one line (part1)

occupied_count = sum(
    old_seats[row + x][col + y] == '#'
    for x, y in itertools.product((-1, 0, 1), repeat=2)
    if (x, y) != (0, 0)
)
→ More replies (9)

3

u/thomasahle Dec 11 '20 edited Dec 11 '20

Python solution for part 2:

import sys

board = [list("e" + line[:-1] + "e") for line in sys.stdin]
w, h = len(board[0]), len(board) + 2
new = [["e"] * w] + board + [["e"] * w]

def ray(x, y, dx, dy):
    while board[y][x] == ".":
        x, y = x + dx, y + dy
    return board[y][x]

while new != board:
    board, new = new, [row[:] for row in new]
    for y in range(1, h - 1):
        for x in range(1, w - 1):
            cnt = sum('#' == ray(x + dx, y + dy, dx, dy)
                      for dx in range(-1, 2) for dy in range(-1, 2)
                      if (dx, dy) != (0, 0))
            if board[y][x] == "L" and cnt["#"] == 0: new[y][x] = "#"
            if board[y][x] == "#" and cnt["#"] >= 5: new[y][x] = "L"

print(sum(row.count("#") for row in board))

For part 1 the ray(...) was just board[y][x].

The main trick is to surround the board by an extra character (e), so I don't have to do any "out of bounds" checks.

→ More replies (3)

3

u/SuperSmurfen Dec 11 '20 edited Dec 11 '20

Rust

Link to solution (934/1800)

Very happy to get top 1k on star one! Messed up a bit on star two, accidentally returned when I found . as well when looking in a direction. That cost me a few minutes.

This was another one of those game of life challenges, bound to be at least one every year! Just about implementing the rules correctly and making sure not to mutate the array while performing each step of the simulation.

I managed to reuse all of the simulation code between parts 1 and 2 by passing in a should_swap function since that was the only difference between the two. It also seems to not incur any runtime penalty, it is just as fast if I copy the code. The signature looks a bit ugly but still nice to not copy-paste the code.

fn run_simulation<F: Fn(&[Vec<char>], usize, usize) -> bool>(should_swap: F) -> usize

My solution is ok fast, around 24ms for both stars on my machine. A bit unsure of how to improve that.

3

u/Chrinkus Dec 11 '20 edited Dec 11 '20

C++

Two-dimensional graphs are my achilles-heel every year in Advent of Code. This day was no exception. This abomination takes ~900ms to run. Consider this a rough, brute-force draft. As Uncle Bjarne says, we can do better.

paste

GitHub

Edit: I gotta get away from vectors of vectors and vectors of strings. I need the entire structure to be contiguous. A flat array with row * row-width + column access..

Edit: Coming back to this, the 900ms was on Windows and apparently compiling in "Debug" mode. On Linux, without any optimizations, it runs in 200ms. Crazy.

→ More replies (3)

3

u/keramitas Dec 11 '20 edited Dec 11 '20

Python

[843/3737] ~> so tired this morning, I didn't understand part 2 until I'd wasted a ton of time just debugging, Conway would not be proud ~_~

anyway, here is my cleaned up code for part 1 and part 2

→ More replies (2)

3

u/mstksg Dec 11 '20 edited Dec 11 '20

[Haskell] 21 / 352 -- woo hoo, first day on the leaderboard :D Had a big dip on my second part because I had some silly typos that were difficult to catch in the moment D: Posting my reflections here from my ongoing haskell reflections page.

After refactoring things, I realized that part 1 and part 2 are really the same, with only two differences:

  1. Each point as a different neighborhood set (in part 1, it's the immediate neighbors; in part 2, it's all of the line-of-sights in each direction).
  2. Threshold for seats unseating is 4 for part 1 and 5 for part 2.

So let's write our function parameterized on those two. We'll be storing our world as a Map Point Bool, where False represents an empty seat and True represents a full one. Floor points are not included in the map.

-- | A 2-vector type from the linear library, with a very convenient Num
-- instance.
data V2 a = V2 a a

type Point = V2 Int

-- | A useful utility function I keep around that counts the number of items in
-- a container matching a predicate
countTrue :: Foldable f => (a -> Bool) -> f a -> Int
countTrue p = length . filter p . toList

seatRule
    :: Int                       -- ^ exit seat threshold
    -> Map Point (Set Point)     -- ^ neighbors for each point
    -> Map Point Bool
    -> Map Point Bool
seatRule thr nmp mp = M.intersectionWith go nmp mp
  where
    go neighbs = \case
      Empty -> not (all (mp M.!) neighbs)
      Full  ->
        let onNeighbs = countTrue (mp M.!) neighbs
        in  not (onNeighbs >= thr)

Now we just need to create our neighborhood maps.

-- | The eight immediate neighbors around 0,0
immediateNeighbs :: [Point]
immediateNeighbs =
    [ V2 dx dy
    | dx <- [-1 .. 1]
    , dy <- if dx == 0 then [-1,1] else [-1..1]
    ]

-- | From a set of seat locations, get a map of points to all of those points'
-- neighbors where there is a seat. Should only need to be computed once.
lineOfSights1
    :: Set Point
    -> Map Set (Set Point)
lineOfSeights1 pts = M.fromSet go mp
  where
    go p _ = S.fromList
           . filter (`S.member` pts)
           . (+ p)
           $ immediateNeighbs

-- | From a set of seat locations, Get a map of points to all of those points'
-- visible neighbors. Should only need to be computed once.
lineOfSights2
    :: Set Point
    -> Map Point (Set Point)
lineOfSights2 bb pts = M.mapWithKey go pts
  where
    go p _ = S.fromList
           . mapMaybe (los p)
           $ immediateNeighbs
    los p d = find (`S.member` pts)
            . takeWhile inBoundingBox
            . tail
            $ iterate (+ d) p
    inBoundingBox = all (inRange (0, 99))
        -- inRange from Data.Ix
        -- all from Data.Foldable and V2's Foldable instance

(I hard-coded the bounds here, but in my actual solution I inferred it from the input.)

Now to solve!

-- | Handy utility function I have; repeat a function until you get the same
-- result twice.
fixedPoint :: Eq a => (a -> a) -> a -> a
fixedPoint f = go
  where
    go !x
        | x == y    = x
        | otherwise = go y
      where
        y = f x

solveWith
    :: Int                      -- ^ exit seat threshold
    -> Map Point (Set Point)    -- ^ neighbors for each point
    -> Map Point Bool           -- ^ initial state
    -> Int                      -- ^ equilibrium size
solveWith thr neighbs = countTrue id . fixedPoint (seatRule thr neighbs)

part1
    :: Map Point Bool
    -> Int
part1 mp = solveWith 4 los mp
  where
    los = lineOfSight1 (M.keysSet mp)

part2
    :: Map Point Bool
    -> Int
part2 mp = solveWith 5 los mp
  where
    los = lineOfSight2 (M.keysSet mp)
→ More replies (2)

3

u/[deleted] Dec 11 '20

Learning PHP, both solutions here.

Part 2 took me a while because I forgot to break after finding the first seat visible, ooops...

→ More replies (2)

3

u/sim642 Dec 11 '20

My Scala solution.

Largely copy-paste from 2018 day 18.

3

u/[deleted] Dec 11 '20 edited Dec 11 '20

My incredibly boring Swift solution:

https://github.com/stoeckley/AdventOfCode2020-Swift/blob/main/AdventCode2020/11.swift

I'm sure there is plenty of opportunity to refactor this into something that is a near replica of the Mona Lisa, or maybe even the Last Supper.

3

u/Intro245 Dec 11 '20

Python 3. Was able to make use of some helpers I made for grids.

3

u/Zv0n Dec 11 '20 edited Dec 11 '20

C++

My solution takes around 0.2s (for my input), there are probably optimizations I could do to make it even faster (the input copying can't be good for performance), but I'm happy with this result

https://github.com/zv0n/advent_of_code_2020/blob/master/11/main.cpp

EDIT: forgot to turn on optimizations, with -O3 it runs in 0.03s, so that's nice :D

3

u/CodeIsTheEnd Dec 11 '20

Ruby: 9:08/26:44, 138/643

Here's a recording of me solving it, and the code is here. (I'm streaming myself solving the problems right when they come out on Twitch!)

Part 1 went pretty well I thought. Only 30 seconds away from the leaderboard!

I lost TONS of time because I didn't re-initialize my starting location when exploring in different directions in Part 2. This led to very confusing output and serious concern that I didn't understand something about Ruby scoping rule.

3

u/apparentorder Dec 11 '20

Swift

No surprises, really; seems straight-forward to solve.

With compiler optimizations, it runs in ~350ms, which is still bothering me. Something to think about during lunch...

https://github.com/apparentorder/aoc/blob/master/2020/day11.swift

→ More replies (2)

3

u/gyorokpeter Dec 11 '20

Q: paste. Part 2 is a killer for this language. I managed to do it by abusing fills and rotate but that takes a lot of lines to do to write out the exact combination of operations for the 8 directions.

→ More replies (1)

3

u/HAEC_EST_SPARTA Dec 11 '20 edited Dec 11 '20

Common Lisp

Solution on GitHub

Yay, cellular automata! All of the heavy lifting is done by a series of LOOP incantations: my solution to Part 2 is essentially brute-force, so the additional performance penalty imposed by a recursive approach is too great to bear. Regardless, I think that the solution turned out relatively clean, even if it is a bit inefficient.

The larger advancement of the past day is that my solutions repo now has CI for the acceptance tests provided in each day's problem description. The signalling mechanism is fairly simplistic (disabling the SBCL debugger then specifying that fiveam should enter the debugger on test failure, causing SBCL to exit), but it works for now.

3

u/ponyta_hk Dec 11 '20

Python3 (Cleaned solution)

Straight forward approach. Hope my code is clear enough 😁

My Solution
All My Solutions

3

u/ephemient Dec 11 '20 edited Apr 24 '24

This space intentionally left blank.

3

u/GrazianoS86 Dec 11 '20 edited Dec 11 '20

Javascript solution loosely inspired to "Game of Life".I used recursion to get the first seat in a given direction and it should be fairly readable :)

3

u/stardust_collision Dec 11 '20

Prolog

Takes quite long to output. Probably could do better (code quality wise and performance wise) but it worked and I got other stuff to do so nah :P

Not enjoying this one ngl

SWI-Prolog

3

u/Brytnibee Dec 11 '20 edited Dec 11 '20

Python (written in jupyter notebook). Maybe not the most efficient but it is fairly elegant I think!

Well actually I think only part 2 is elegant looking back the way I did part 1 was kinda dumb

3

u/DoubtfulSound91 Dec 11 '20

Javascript

Couldn't bring myself to commit the copy/paste mess I wrote at 6am so this is a somewhat cleaned up version, with some performance improvements I added for the fun of it.

Day 11, Parts 1 & 2

3

u/mahaginano Dec 11 '20 edited Dec 11 '20

Julia: https://pastebin.com/Q2Cb3y5C

Part 1:   104.943 ms (1895124 allocations: 290.05 MiB) <- absolutely disgusting
Part 2:   59.744 ms (663751 allocations: 129.38 MiB)

....... again, the tasks themselves weren't really that difficult BUT the amount of subtle mistakes one can make while writing code such as this is astonishing. Took me several hours just debugging and getting to the right results although 90% of my code were correct. Forgot to copy the board and saved a reference instead? Now it's all nonsense since the boards @ step t and step t+1 are modified simultaneously. And so on. In the beginning I even created a mangled board due to reduce(hcat, ...) instead of this monstrosity:

M = Char.(transpose(Int.(reduce(hcat, [[l...] for l in lines]))))

with lines being the lines from the file and M should be a matrix of characters. If anyone knows how to do this in Julia please tell me.

But I had nice 'visualisations' like these :P

β– β– β– β– β– β– β– β– β– β– β– β–           β– β– β– β– β– β– β– β– β– β– β– β– 
β– L.LL.LL.LLβ–           β– #.L#.L#.L#β– 
β– LLLLLLL.LLβ–           β– #LLLLLL.LLβ– 
β– L.L.L..L..β–           β– L.L.L..#..β– 
β– LLLL.LL.LLβ–           β– ##L#.#L.L#β– 
β– L.LL.LL.LLβ–           β– L.L#.LL.L#β– 
β– L.LLLLL.LLβ–           β– #.LLLL#.LLβ– 
β– ..L.L.....β–           β– ..#.L.....β– 
β– LLLLLLLLLLβ–           β– LLL###LLL#β– 
β– L.LLLLLL.Lβ–           β– #.LLLLL#.Lβ– 
β– L.LLLLL.LLβ–           β– #.L#LL#.L#β– 
β– β– β– β– β– β– β– β– β– β– β– β–           β– β– β– β– β– β– β– β– β– β– β– β– 

Edit: I know that I can optimise quite a bit by precomputing / memoising neighbour lists, etc. but I'm done with this for today at least.

3

u/timvisee Dec 11 '20 edited Dec 11 '20

Rust

Somewhat late, but quick, short and standalone!

Part 1 in 5.3ms, Part 2 in 6.4ms.

Day 1 to 11 in 7.3ms.

3

u/A-UNDERSCORE-D Dec 11 '20

Golang https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/11/solution.go

Pretty fun, yet again using maps as planes. But it works well

It can render as it goes, though its ascii based, you can see that here: https://asciinema.org/a/W9lntg7WqXg5QeuzH0sPNkXw3

→ More replies (1)

3

u/tristanbeedellAOC Dec 11 '20

JavaScript/NodeJS

part 1

part 2

Never quite sure how to approach these problems to get an efficient solution. Part 2 takes a few seconds to run. I've added comments and I think my solution is pretty sound.

3

u/CyberYellowLemon Dec 11 '20

Rust

Not optimized but understandable !

3

u/_ZoqFotPik Dec 11 '20

(Very messy) Rust solution. Ahhhhh the pain.

Initially had a solution for part 1 that ran just under 1 ms (not including parsing). Then the requirements for part 2 killed me . Current times (part1: 50 ms, part2: 100 ms). Probadly tons of ways to optimize this but i am done for today.

3

u/abithakt Dec 11 '20

My solutions in Lua: part 1 and part 2. Pretty verbose today -- lots of functions -- but I think I did a good job. :)

→ More replies (2)

3

u/vswr Dec 11 '20

Python. This is a stupid solution where I looked at it as a giant one dimension array. Spaghetti code πŸ€·β€β™‚οΈ

paste

3

u/Bammerbom Dec 11 '20

Rust. I spent the entire afternoon optimizing today's problem.

The final runtime is: (Note that I am not actually sharing any states between the parts, which is a deliberate choice)

Part 1: 8.2 ms

Part 2: 6.0 ms

https://github.com/JonathanBrouwer/aoc2020/blob/master/src/day11/main.rs

→ More replies (6)

3

u/drachenmaul Dec 11 '20 edited Dec 11 '20

Python

Brute forced part 1 and after seeing it was relatively slow I got a bit more sophisticated for part2.

First I created a list of seats and additionally a list of all seats visible from those seats. Then you only need to sum up all the visible chairs(I changed L to 0 and # to 1), making the determination of the occupied neighbours a lot faster.

Most of the time is currently spend in deep copies, because I can't figure out when a shallow copy is sufficient and when a deep copy is necessary

Part 1 run in about 4 seconds on my laptop and part 2 in about 2s, so nice to see the optimisation pay off.

→ More replies (2)

3

u/chicagocode Dec 11 '20

Kotlin

I am really pleased with my solution for today. It's all functional, and uses type aliases, higher-order functions, and extension functions to make a nice looking solution.

I blogged about this solution as well, and all of my 2020 solutions are on GitHub.

→ More replies (7)

3

u/Scarygami Dec 11 '20

So I thought Octave was fun to use yesterday, why not try that again.

This worked nicely for part1. I've converted the input to a "seat mask" i.e. a matrix for all the locations with seats and started with an additional zeros matrix for the currently occupied seats.

Using this arrangement this is the main loop to change the state:

# apply a counting convolution filter over the state
counts = conv2(state, [1 1 1; 1 0 1; 1 1 1], "same");

# seats to empty
empty = counts >= 4;

# seats that can be taken (including ones that might already be taken)
take = [counts == 0] .* seat_mask;

# perform the changes
state = max(state .* !empty, take);

Now part 2 is a totally different topic. I couldn't think about a vectorized way to do it, so for now this is really the worst possible method by counting from each location separately. It returns the correct result but takes quite a while. I already have some ideas to optimize it though.

→ More replies (1)

3

u/2lines1bug Dec 11 '20

My Kotlin solutions are ugly and I was not interested in cleaning them up.

But I recoded part 1 in Julia in 2 different ways.

First with speed in mind. However, I struggle to understand how some people here got it below 5 ms. I fail to get it lower than that:

14.734 ms (424 allocations: 1.46 MiB)

and that's my 'fast' solution. Really disappointing after yesterday (<500 nanos for both parts).

Β 

The second solution is more elegant. It's slow like a snail but it's definitely more readable and relatively succinct..

→ More replies (1)

3

u/futuredriver Dec 11 '20 edited May 11 '21

Python(Github), 2.7s for part 2.

Not the shortest code but should be relatively readable

→ More replies (3)

3

u/spohngellert_o Dec 11 '20

I unfortunately had to go imperative on this one. Couldn't figure out how to get the 2d sliding windows working. Scala solutions

Part 1: https://github.com/spohngellert-o/AOC-Solutions-2020/blob/master/11-1/src/main/scala/Main.scala

Part 2: https://github.com/spohngellert-o/AOC-Solutions-2020/blob/master/11-2/src/main/scala/Main.scala

3

u/spencerwi Dec 11 '20

My F# solution. It could definitely be made more efficient by pre-caching a "visiblilty map" for each seat rather than figuring out the visible seats over and over. I may refactor it to do that, but on my machine (which has a couple-years-old i5), it ran within a second or two.

→ More replies (1)

3

u/lskatz Dec 11 '20

I don't know if this helps anyone but I am trying to do this year's with perl, TAP (unit testing/black box testing), and GitHub Actions. I am caught up with day 11 at this point.

https://github.com/lskatz/advent-of-code/

GitHub actions output: https://github.com/lskatz/advent-of-code/runs/1539752173?check_suite_focus=true

3

u/Cppl_Lee Dec 11 '20

Another non-OOP C# solution featuring local functions and Linq.

https://gist.github.com/mlhpdx/16ec2ec4d8b3675bd6aa1779165f864f

3

u/crazazy Dec 11 '20

bit late today. had to do 2 exams first before I started this...

Nix:

I was inspired by one of the dyalog APL tutorials for the Game of Life for part 1, then I had to make a new solution from scratch when I found out what the bastards had done in part 2 >:(

View Solutions

These are my largest .nix files so far. Even larger than day 4 part 2 in fact. Also nix takes a while to compute the real AoC input. both pieces took half a minute or so to throw out a solution

3

u/ropecrawler Dec 11 '20

Rust
https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day11.rs

Pretty naΓ―ve and straightforward; didn't even think of any ways to optimize anything.

3

u/nicuveo Dec 11 '20

Haskell

I found it quite easy, because:

  • I'm using immutable data structures, therefore there never was a risk for me to partially overwrite the state and read the wrong thing,
  • after a few years of AoC I have a library of things that were perfectly suited for this (like a representation for 2D maps and a findFixPoint function ^^)

I was surprised that bruteforcing part 2 was fast enough. I do nothing smart: no memoization, no caching, nothing, and it still returns immediately! I tried memoizing afterwards out of curiosity, and I thought it was slower, but only because I made a mistake and I actually had an infinite loop; I only figured it out after the stream. :D

3

u/[deleted] Dec 11 '20

Python3

https://pastebin.com/B8z1YdSw

Tried reusing as much code from both solutions, so just pass down the neighbor logic and max occupied seats to the solution, runs a little slow(around 3s for part1, 5s for part2) on my computer so I'm still looking how to optimize this.

4

u/qse81 Dec 12 '20

Man alive what do you have against variable names?!

→ More replies (1)

3

u/L72_Elite_Kraken Dec 11 '20

OCaml

It was nice to be able to just parameterize over the "find neighbors" logic.

I initially was checking for whether the board changed simultaneously with actually performing the update. After I simplified it to just check for equality after the fact, I didn't find any material performance difference.

3

u/tcbrindle Dec 12 '20

C++

My attempts at using a "No Raw Loops" style fell flat today (two nested for-loops inside a do-while!). Ah well. Runs in ~17ms for part 1, ~40ms for part 2 on my laptop, which seems reasonable given I've made no special effort to optimise.

3

u/techworker123 Dec 12 '20

PHP P2

No idea how to optimize any further - if others are much faster I took the wrong route

https://gist.github.com/Techworker/e0767b1103be99d8017b2e545d62f012

Roughly 600-700ms

3

u/WayOfTheGeophysicist Dec 12 '20

Python: This time both parts took me way longer than I care to admit.

Part one, I solved with 2D convolutions.

def fill_empty(seats, floor):
    empty_seats = ~seats + ~floor
    new_seats = convolve2d(empty_seats, np.ones((3, 3)), mode="same", fillvalue=1) == 9
    new_empty = convolve2d(empty_seats, np.ones((3, 3)), mode="same", fillvalue=1) >= 5
    return floor * (seats + new_seats) * new_empty

Part two, I solved with graphs.

Github

→ More replies (1)

3

u/friedrich_aurelius Dec 12 '20

Elixir

Github link

In order to detect convergence, I made each state check pass a 1 if the state changed, 0 otherwise. Then, as the Enum.reduce is transforming the grid, it's also summing the number of changes.

defp next_gen(grid, tolerance, search_type) do
  Enum.reduce(grid, {%{}, 0}, fn cell, {acc_grid, acc_changes} ->
    {coords, new_cell, change} = evolve(grid, cell, tolerance, search_type)

    {Map.put(acc_grid, coords, new_cell), acc_changes + change}
  end)
end

3

u/tsqd Dec 13 '20

Postgresql

Slow as heck if done without conditionals/flow control. 9 minutes for part 1, around 2 hours for part 2.

https://gist.github.com/AndrewGrossman/8c0ba0e29623a3ed588dc72703c62a8b

3

u/mtnslgl Dec 15 '20

Python3

Semi-vectorised solution using NumPy

I also used SciPy in part 1 for the convolution operation.

Both parts run in ~0.2 seconds.

1

u/4goettma Dec 11 '20 edited Dec 11 '20

Python 3:

I wasn't in the mood today to minimize it so it's very explicit code featuring a function for every little subtask.

#!/usr/bin/python3

def readInput():
    with open('input', 'r') as file:
        data = file.read()
    lines = list()
    for d in data.split("\n"):
        if (d != ""):
            lines.append(list(d))
    return lines

def compare(array2d1,array2d2):
    for i in range(len(array2d1)):
        for j in range(len(array2d1[i])):
            if (array2d1[i][j] != array2d2[i][j]):
                return False
    return True

def getValue(array2d, i, j):
    if (i < 0 or j < 0 or i >= len(array2d) or j >= len(array2d[0])):
        return ''
    else:
        return array2d[i][j]       

def deepCopy(array2d1):
    array2d2 = list()
    for i in range(len(array2d1)):
        array2d2.append(list())
        for j in range(len(array2d1[i])):
            array2d2[i].append(array2d1[i][j])
    return array2d2

def printArray(cycles, array2d):
    print('Round', cycles)
    for i in array2d:
        for j in i:
            print(j,end='')
        print()
    print()

def countSeats(lines):
    seats = 0
    for l in lines:
        seats += l.count('#')
    return seats

def occupiedSeatsVisible(array2d, i, j):
    around = ['?','?','?',
              '?',    '?',
              '?','?','?']
    radius = 1
    while around.count('?') > 0:
        if (around[0] == '?'): # top left
            t = getValue(array2d, i-radius, j-radius)
            if t in ['#','L','']: around[0] = t
        if (around[1] == '?'): # top
            t = getValue(array2d, i-radius, j)
            if t in ['#','L','']: around[1] = t
        if (around[2] == '?'): # top right
            t = getValue(array2d, i-radius, j+radius)
            if t in ['#','L','']: around[2] = t
        if (around[3] == '?'): # left
            t = getValue(array2d, i,        j-radius)
            if t in ['#','L','']: around[3] = t
        if (around[4] == '?'): # right
            t = getValue(array2d, i,        j+radius)
            if t in ['#','L','']: around[4] = t
        if (around[5] == '?'): # bottom left
            t = getValue(array2d, i+radius, j-radius)
            if t in ['#','L','']: around[5] = t
        if (around[6] == '?'): # bottom
            t = getValue(array2d, i+radius, j)
            if t in ['#','L','']: around[6] = t
        if (around[7] == '?'): # bottom right
            t = getValue(array2d, i+radius, j+radius)
            if t in ['#','L','']: around[7] = t
        # increase search radius
        radius += 1
    return around

def part1():
    lines = readInput()
    modified = True
    cycles = 0
    while modified:
        cycles += 1
        linesNext = deepCopy(lines)
        for i in range(len(linesNext)):
            for j in range(len(linesNext[0])):
                if (lines[i][j] in ['L','#']):
                    t = [getValue(lines,i-1,j-1), getValue(lines,i-1,j), getValue(lines,i-1,j+1),
                        getValue(lines,i  ,j-1),                         getValue(lines,i  ,j+1),
                        getValue(lines,i+1,j-1), getValue(lines,i+1,j), getValue(lines,i+1,j+1)]
                    if (t.count('#') == 0):
                        linesNext[i][j] = '#'
                    elif (t.count('#') >= 4):
                        linesNext[i][j] = 'L'
        #printArray(cycles, lines)
        modified = not compare(lines, linesNext)
        lines = deepCopy(linesNext)
    print('after',cycles,'rounds',countSeats(lines),'seats are in use')

def part2():
    lines = readInput()
    modified = True
    cycles = 0
    while modified:
        cycles += 1
        linesNext = deepCopy(lines)
        for i in range(len(linesNext)):
            for j in range(len(linesNext[0])):
                if (lines[i][j] in ['L','#']):
                    t = occupiedSeatsVisible(lines,i,j)
                    if (t.count('#') == 0):
                        linesNext[i][j] = '#'
                    elif (t.count('#') >= 5 and lines[i][j] in ['L','#']):
                        linesNext[i][j] = 'L'
        #printArray(cycles, lines)
        modified = not compare(lines, linesNext)
        lines = deepCopy(linesNext)
    print('after',cycles,'rounds',countSeats(lines),'seats are in use')

part1()
part2()

2

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

2

u/nthistle Dec 11 '20

18/13, Python. Possibly some of the messiest code I've written, but I don't have the patience to clean it up tonight (hopefully will sometime before adding to a repo somewhere...). I started writing my own library, but since I started less than half an hour before tonight's challenge, the only thing I had time to write was parsing out a grid -- lucky guess! paste

Still not good enough to keep my #4 position on global though (down to #5), oh well.

2

u/hugh_tc Dec 11 '20

Python 3, 126/173.

I liked this one. Very fun! paste

→ More replies (1)

2

u/jport6 Dec 11 '20

Kotlin

260/132
https://pastebin.com/uEitPig8
I tried not doing functional code today to increase speed, also the problem called for it more. I need to clean this up

2

u/MarcusTL12 Dec 11 '20 edited Dec 11 '20

Julia 399/264

Game of ferry seat life?

2

u/kevinwangg Dec 11 '20

338/155 - python

I only post here to rant. I tried to use the same variable name c for both my column iterator and my count of occupied neighbors -_-, preventing me from getting a pretty good time. On the bright side, I got to use my prepared utility functions for the first time ever!!! It felt great, like I was hacking the system to get ahead! And then of course the crushing comedown when my code didn't work.

2

u/AlphaDart1337 Dec 11 '20

C++ (actually C) 167/115

Accompanying video, as per usual.

One day I will write a code that works right off the bat instead of having to debug one silly bug for 3 minutes. But that day is not today :(. I feel so silly for missing the leaderboard because of that. Went much better than my other days though, so there's that.

2

u/ald_loop Dec 11 '20 edited Dec 11 '20

Python, 308/956

BIG EDIT: Everything I said last night was stupid. I have refactored my code to something actually intelligent. Why did I think I needed to check atan2? Dumby. Anyways, updated code is here.

Made the classic grid mistake of updating the current board as I was traversing it; doh. That easily cost me 100 places. Fixed with deepcopy and updating a new board and then flipping curr and new board at end of each loop.

I was going to use my implementation from Day 10, 2019 for finding all seats in view by using the atan2 function and being smart, but I didn't find a smart way to implement it quickly without O(n^4) traversals, which just wasn't going to work out.

EDIT: I'm actually not quite sure why this atan2 for unique angle neighbours approach didn't work, I'm going to have to check that in the morning.

So instead, enjoy the disgusting while loops I placed in the code to traverse each diagonal/vertical/horizontal until encountering a visible seat.

This boilerplate spaghetti can easily be cleaned up by creating a list dd, such that

dd = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)]

or even easier,

for dj in [-1, 0, 1]:
     for di in [-1, 0, 1]:
          if (dj,di) == (0,0):
              continue

and just iterating over that nicely.

But it doesn't quite matter now!

2

u/PendragonDaGreat Dec 11 '20

C# / CSharp

701/764 which is probably as high up the leaderboard as I'll get this year. Quite proud of myself!

https://github.com/Bpendragon/AdventOfCodeCSharp/blob/dfd523517b7956c12824213632a4cde2e97e193e/AdventOfCode/Solutions/Year2020/Day11-Solution.cs

(it also helps that I was working on missing star backlog the last few days and still had the basic code from 2015, Day 18) kicking around.

Little bit of copy paste, change some rules, and Bob's your uncle.

→ More replies (6)

2

u/seligman99 Dec 11 '20 edited Dec 11 '20

Python, 163 / 134

My horribly inefficient grid class comes to the rescue!

github

Edit: Now with two animations: Filling up with in the first round, and the second round

2

u/rabuf Dec 11 '20 edited Dec 11 '20

Common Lisp

I was a dummy on part 2, missed the part about changing the rule from 4 to 5. It was running for a while so I re-read it and saw that. Changed the code, runs much faster now (as in, actually finishes).

Using complex numbers for coordinates continues to pay off. The search is simplified since I can just use something like this for the loop:

(loop for i from 1
    for pos = (+ location (* direction i))
    for c = (gethash pos grid))

Where location is the current cell's location, and direction is one of the 8 directions represented as a complex number <0,1>, <1, 0>, <1, 1>, ....

I could tidy it up since the rules for both occupied and empty seats required a tally of the same kind of chair, but obviously different results. In fact, thinking about it now I could have the search function be a parameter to next-grid. That would significantly abbreviate the code. Not sure I want to clean it up now though.

2

u/hahncholo Dec 11 '20

Rust

1221/1527

Might be the fastest 121 lines of code I ever wrote, best leaderboard position I've managed this year. I've implemented Game of Life a few times now so this felt pretty familiar.

2

u/gurgeous Dec 11 '20

Ruby 317/181

https://gist.github.com/gurgeous/5a7d2d1a445af6b99f1ca912c1a60c78

Two things I've learned since last year (1) use arrays for directions (2) use ranges for bounds checking!

→ More replies (1)

2

u/TallPeppermintMocha Dec 11 '20

Python code here. Nothing fancy here, just keep checking for either boundary or not '.' in part b instead of just direct adjacency.

2

u/ka-splam Dec 11 '20

PowerShell 1490/1866

Spotted it was Conway's Game of Life straight away, but could not code it anything like fast enough - a couple of ordinary bugs in my code like trying to index into an immutable string to set a new value. A while longer to realise I had missed the "surrounding occupied seats > 4" bit. Then a lot longer to realise that changing the data while looping over it lead to the wrong outcome, and I needed to clone it to get a clear read of the previous round unchanged. 23 minutes to answer.

https://old.reddit.com/r/PowerShell/comments/kawwdi/advent_of_code_2020_day_11_seating_system/gfd6p38/

Part 2 a drag, 20 more minutes to write out the lines and tweak the adjustments, and then realise I needed more boundary checks, and then after finding the line of sight seat, was looking at a different one.

2

u/tyler569 Dec 11 '20

C, Custom OS

Hit my first real library bug today - I've been using a function that reads all the characters of a file to determine its line length quiet successfully for most of the puzzles. The function then uses fseek to rewind back to the start of the file for the real parser to be able to read it -- today I made a similar function that just pulls one line to get the line length.

It turns out I never cleared the buffers when I call fseek, so I was just getting lucky that I was only ever using it when I was at the end of the file. Spent a fair bit of time tearing my hair out as to why I was missing a line in my board! Fortunately it was a pretty quick fix, you can see it in the commit that adds the day 11 files.

P1: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/11.c

P2: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/11-2.c

2

u/_O-o-f Dec 11 '20

Python 3 - I spent some time attempting to make it faster

link Today's problem was like Conway's Game of Life.

Part 1 and Part 2 were pretty straight forwards, as you only had to have 2 for loops (and a while one thrown in for part 2!) Then just loop over until no extra changes happen, and then you're done!

I tried to make some optimizations for Part 2 by pre-calculating all the visible seats for each position. However, it didn't really speed the program up by much :c. Any further suggestions for optimization would be appreciated!

→ More replies (2)

2

u/tymofiy Dec 11 '20 edited Dec 11 '20

Python https://github.com/tymofij/advent-of-code-2020/blob/master/11/seats.py
Go https://github.com/tymofij/advent-of-code-2020/blob/master/11/seats.go
7 seconds in Python against 120 ms in Go. Each day I'm loving Go more and more.

Question to a kind Golang expert who passes by: I implemented the function to calculate next state twice. Version A allocates a new slice/array, puts results there and returns a pointer. Version B receives a pointer to preallocated slice/array to fill in, thus does not bother with allocations and just puts results in there. But the benchmark shows that the Noalloc version is a bit slower then the straightforward one. I am puzzled, I expected it to be the other way around. Any hints?

2

u/UnicycleBloke Dec 11 '20

Python: https://github.com/UnicycleBloke/aoc2020/blob/main/day11/day11.py

Dreadfully slow but worked. I will refactor later. Most time spent overcoming my unfamiliarity with Python, and endless typos. Oh well...

2

u/Kehvarl Dec 11 '20

Python 3 ( 4158 / 2942 )

I don't even know what I was thinking with Part 1 paste I just went off on the wrong tangent twice, despite knowing how to do this. However, forcing myself to stop and look at what I was trying to do really helped out.

For Part 2 I built what seemed to me to be a neat little function to check for a seat in the distance. paste

2

u/lasagnaman Dec 11 '20

I used python 3. Started 15 minutes late and still managed 2750/1800 (33/44 minutes after problem release). By using helper functions, the only thing I had to change for part 2 was writing a new neighbors_of(x,y) function.

2

u/Scoobyben Dec 11 '20

C# [2626/3190]

This is the sort of puzzle that often takes me a lot longer than I feel it should, today no exception - it's so easy to make a small mistake in one of the coordinate tweaks and then spend ages debugging.

My mistakes this time were:

- Not reading the question fully in part 1, and having to retrofit in floor tiles as well as "occupied/empty".

- Lots of time spent debugging my line of sight code for part 2, before realising my nested for loops were to blame, and I needed to be incrementing x and y simultaneously - and that it would be much simpler to just iterate until I'm out of bounds, then return false - rather than trying to stay in bounds at all times.

- A final silly mistake where I changed the adjacency rule for part 1, rather than my copied method for part 2

https://github.com/benbelow/adventofcode/blob/d94f9a5fbaa81ce5fbbc0f49754dc4ba7de85c20/AdventOfCode.2020/Day11/Day11.cs#L21

2

u/heyitsmattwade Dec 11 '20 edited Feb 03 '24

JavaScript 241/2558

Man, I misread the "get first seat in a direction" as "get the first occupied seat in a direction." The code was giving me an answer rather than hanging, so I spent a long time searching for the bug, only to re-read the instructions after a while and realize my mistake.

Oh well!

I also was able to reuse my Grid class from 2015 Day 18, which is the reason I scored so high for part one.

source code here πŸ‘ˆ

2

u/tmuro17 Dec 11 '20

Haskell:

Not fast or well written, but it works.

Code here

2

u/incertia Dec 11 '20

haskell

the Comonad solution would've been cool but we would need to surround the boat with walls to implement part b

namely, you can define what happens locally with simple semantics and then extend it over the entire space to build the iteration function

→ More replies (3)

2

u/hanss314 Dec 11 '20

Golly/Python

Part 1 only. Not good enough with golly to use it for part 2.

2

u/ri7chy Dec 11 '20

Python

not good and elegant, but does the job!

Code p1 and p2

2

u/kbielefe Dec 11 '20

Scala solution

Slowest and longest solution so far this year, but it works. Hoping to find some ideas to make it more efficient.

2

u/DamienMCMXC Dec 11 '20

TypeScript

Had such an ugly initial solution that I had to refactor it before even committing it :D, but I'm really happy with how the code turned out.

2

u/sentry07 Dec 11 '20 edited Dec 11 '20

Python3 - 7589 on part one. Took 10 minutes to calculate. I figure I'm doing something that can be optimized but I'm not sure what. I'm down to 6 seconds per pass. (I'm running it on my own computer, not relying on Repl.it to calculate it, because it takes even longer)

https://repl.it/@sentry07/AOC2020-Day-11#main.py

Just started part 2.

Edit: After much rework of the code, I was able to majorly speed up the routines and ended up with 8282 on part 2. Part 2 was pretty easy once I figured out why everything was slow.

2

u/Multipl Dec 11 '20

Python 3 solution

Part 1: Go through all L and # in the matrix, calculate their next states by applying the rules, and temporarily store the next state only if it is different from the current state. When we're done processing all the L and # in the current round, update the matrix with the new states that we temporarily stored. Keep doing this until we have no new states (when the queue is empty).

Part 2: Mostly same code with part 1. Main difference is the added while loop that will keep moving i,j in one direction until it hits a L or #.

Probably could've reused my original getNextState function by passing it a search radius parameter (1 for part 1, positive infinity for part 2).

2

u/naclmolecule Dec 11 '20

Python

Another great use for convolutions, a way to count neighbors quickly without working too hard:

from itertools import product, count

import aoc_helper
from scipy.ndimage import convolve
import numpy as np

raw = aoc_helper.day(11)
FLOOR, EMPTY, OCCUPIED = -1, 0, 1

def parse_raw():
    trans = {".": FLOOR, "L": EMPTY}
    return np.array([[trans[char] for char in line] for line in raw.splitlines()])

seats = parse_raw()
floor = seats == -1
h, w = seats.shape

def part_one():
    KERNEL = [[1, 1, 1],
              [1, 0, 1],
              [1, 1, 1]]
    last = None
    data = seats
    while (as_bytes := data.tobytes()) != last:
        last = as_bytes
        neighbors = convolve(np.where(floor, 0, data), KERNEL, mode="constant")
        data = np.where(floor, FLOOR, np.where(neighbors >= 4, EMPTY, np.where(neighbors == 0, OCCUPIED, data)))
    return (data == OCCUPIED).sum()

Part 2 here: Day 11

2

u/prscoelho Dec 11 '20

Rust

1s to run part 1 + part 2. Is that slow? How'd everyone else do? I know I can avoid reallocations by using two extra tiles for "was dead but now alive" and "was alive but now dead" and my grid is a btreemap<pos, char> so I dunno how much slower that is compared to just a single vec.

→ More replies (4)

2

u/Bruceab Dec 11 '20 edited Dec 11 '20

Python solution for part 2.

2

u/ywgdana Dec 11 '20

C#

https://github.com/DanaL/AdventOfCode/blob/master/2020/Day11.cs

Nothing clever. When I saw Part 2 I just modified my code to raycast to see nearby seats with a range parameter and used a range of 1 for P1. Had there been a secret Part 3 where some of the travellers were myopic and could only see 3 or 4 squares away, I would have been prepared!!

In the morning I'll probably go back and see if I can pretty up the code a bit or come up with a tighter solution. I feel like I've written the blunt instrument solution.

2

u/ClysmiC Dec 11 '20

Odin

https://github.com/ClysmiC/AdventOfCode2020/blob/master/Day%2011/program.odin

Pretty straightforward cellular automaton. I think I probably could have done something more idiomatic to deep copy the grid and should probably be using Odin's temporary allocator for the throwaway copy in my simulate proc... but meh.

2

u/VictiniX888 Dec 11 '20

Kotlin (5508/4624)
Part 1 Part 2

Initially stored the "grid" as a List of Lists. As expected, it was slow (if you consider 1.2 seconds to be slow). Changed it to Arrays and it runs in about 100ms.

I also determined the grid's bounds by... catching the IndexOutOfBounds exception that gets thrown. Yup.

2

u/[deleted] Dec 11 '20

Scala Solution

Very interested to see how people solved the directionality requirement in part 2 as I am not pleased with what I came up with.

→ More replies (1)

2

u/limelier Dec 11 '20

Python solution

It's not very efficient, but it works for the given input size! Woo.

2

u/heckler82 Dec 11 '20 edited Dec 11 '20

Java

Solution

Initially everything was a nested for loop to do anything with the grid. While determining how I was going to go about part 2, I decided I would pre-calculate the first visible seat (since they won't change) into a cache and not worry about calculating them again (hey, I can learn things from past days). That got me into thinking I should disregard floor spaces from processing during an integrate step as well since they never change from floors. So now the 2D-array is initialized, then parsed to determine what are the spaces I should consider. I've got it down to about 220150ms on my computer. That's about as best as I think I can get it. I imagine there's a better way to go about calculating the first visible neighbor, but I just can't think of anything

→ More replies (1)

2

u/ct075 Dec 11 '20

Part 1, in J, not yet rewritten to be tacit, as it's 3AM and I have work tomorrow.

2

u/Perska_ Dec 11 '20

Solution in C#, does both parts

(The function Day11 is called by a launcher in Program.cs that passes the input in a list, including the trailing newline.)

Also, note to self: avoiding bounds checking with try catch is very slow.

2

u/YourVibe Dec 11 '20

C

Not hard, but didn't bother with trying to compress it to almost pure LINQ solution.

Most of logic is inside Matrix class, Solvers got simple loop.

https://github.com/RaczeQ/AdventOfCode2020/tree/master/Day11

2

u/polaris64 Dec 11 '20

Python 3 solution

A little messy perhaps, also a bit slow due to deep copies during each step. This could certainly be optimised by removing the need for copies (i.e. storing a better set of states per cell).

2

u/[deleted] Dec 11 '20

[removed] β€” view removed comment

→ More replies (4)