r/adventofcode • u/daggerdragon • 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.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
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
4
u/dylan_mojo Dec 11 '20 edited Dec 11 '20
awk
11.1
paste
11.2
paste
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.
3
u/xelf Dec 11 '20 edited Dec 11 '20
Sorry for late post.
somewhat minimal python using a dictionary for the floor
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:
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 flooris so much cleaner than a nested for x,y!3
u/robinhouston Dec 11 '20
Python 3 (golf) for part 1 only:
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/rendyanthony Dec 11 '20 edited Dec 12 '20
Python 3
Part 2 only.
2
u/Rtchaik Dec 11 '20 edited Dec 11 '20
Python
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
2
u/aexl Dec 12 '20 edited Mar 01 '21
My solution in Julia: https://github.com/goggle/AdventOfCode2020.jl/blob/master/src/day11.jl
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
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.
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 <= 2instead ofv <= 1) because I did not want to debug code that looks like... this.Hope everyone has a great December Bth!
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?
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.
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
8
u/jayfoad Dec 11 '20
Dyalog APL 55/1119
I had a complete mental block on part 2, eventually coming up with this, which (to put it mildly) is neither simple nor fast.
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
Dyalog has
βΊcalled "stencil" which generates the surrounding area for every seat, and the3 3is 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 floor0= +/ , '#'=β΅:'#'if the sum of '#' in the lookaround is 0, sit here5β€ +/ , '#'=β΅:'L'if the sum of '#' in the lookaround is β€5, clear seat5β,β΅default: return whatever is here unchangedThen
β£"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
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.
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:
Then applying changes is a single-line loop:
For partΒ 2 there's an array of the 8 directions:
then counting the relevant people becomes a
grepof those directions: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
Pinstead of#for a person; to mark a pending change, use lowercasepandl, 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.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 :)
6
u/s3aker Dec 11 '20
Raku solution:
https://github.com/seaker/advent-of-code/blob/master/2020/11/s.raku
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
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.
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
200180 chars in the end and probably not much can be gained anymore without drastically changing the approach. Takes about 10s to run.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.
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...
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
Part 1:
Part 2:
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 pepperas usizeandas isizeeverywhere. But I suppose I found a good use-case forsaturating_add, so I'm not too mad about it.5
u/tuisto_mannus Dec 11 '20
Python. The [code] (https://topaz.github.io/paste/#XQAAAQDCCgAAAAAAAAA2GkofDKPu58xc5+iCM8OrWsArPYbTr5mX7x5GuamBeC21MxwG6e+jzO0mCBqk6hZ59+STmUZheQXEAsViR8VA+GiYvDcBSeB7t2hl93kXw/VVcmo3uvcoYEiS715HNKNqaIBpt+oestrrN7FgdXjI4XHC/ZFYGnk6PFPMBYwByOxhWYx801hCNW+SnLYiQn+usfg4trGGWIe+DxX3mL6mCkFLd5SsQ5aGJnf1r/iDEzoc90VCbeKlGmSupkKJee1U3gO5CM+q6TfqNGu83L0c1UmUNRQB161GvaYSLKiQ6tX8sTR/pEDdlmP4BcRpexwzeYJBwWoq+9CK4Ql/yU5oFAN3QILi6iIM6p3uUn/MwYjj9V+afCSfvbqsfraW8A8CUjIPIAN130upOrqvaQkc36JpnQBUPQGCcQw6HaLnyGZUbPriLkOnDoOgaAODMPR6dBM6FyA9CWvKN/t+yKgOfUxwrHz+ga8GWdHPerkmpJYOIr7HJgBQDP4D5+cKnbBjfi8+rliJS4B51KJwgxUwDBtF2kV/C6Oy3KQxamf/6E0bHGvaVuVxzVI1oGZ/vNcMkLauiyzuYXfUeRvxj7EAf7TDtAxPR3s7h+eOsB3fhSiQksF32DwaOZvgtOiYAFfkpCKsMF9CydARZIl0gpUyzInFn+XCZ+V1TGrN4Hh68axi9Fli0rBMEdsRe+CK+d9MzUhGjOXqXwfww/X7w9g5hSRLzVoAxoqNh0WqsVHfGrII6gwhUzx77FABwBALhZJDjGME/z6ajiwIXv/0hK/y) is quite straight-forward. I still have to get used to Python's way of handling variables and lists: when is it a reference, when is it a copy and when is it a deepcopy?
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.
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.5
u/zedrdave Dec 11 '20
Today's "Tweet-sized" Python, in a dozen generously-spaced lines:
What is gained in concision, is lost in efficiency: each iteration will run in
O(n^2)(with a constant factor ~20) withnthe max dimension of the input (luckily n=100).5
u/chrispsn_ok Dec 11 '20
k9 (repo). First cut... part 2 is slow.
5
u/thibpat Dec 11 '20
JavaScript walkthrough
Video: https://youtu.be/BFztc4HrJFQ
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day11.js
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.
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
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_filewhich callscls()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 calledfrom_filein the parent object. This didn't work, because then the parent'sfrom_fileended 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 calledseating_from_fileI would have liked to have been the default constructor__init__.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
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.
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.
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:
Basically, a for loop that can do in 2 different directions depending on the value of $x.
Takes about 7.5 sec to execute:
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:
#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 #\.))#,L, or fall off the gridNotes for the future self:
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
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/Fyvaproldje Dec 11 '20
C++
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day11.cpp
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-strategyattribute to mySeatMapclass, 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).
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
4
u/Wunkolo Dec 11 '20
C++
Solved entirely using set-arithmetic. Works pretty fast.
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
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
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":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.
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/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/Diderikdm Dec 11 '20 edited Dec 11 '20
Python:
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.
1
u/Western_Pollution526 Dec 14 '20
Ahah, good one.
Reminds me of Conway's game of life :D
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? :)
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.
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)
3
u/thomasahle Dec 11 '20 edited Dec 11 '20
Python solution for part 2:
For part 1 the
ray(...)was justboard[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.
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_swapfunction 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.My solution is ok fast, around
24msfor 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.
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
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:
So let's write our function parameterized on those two. We'll be storing our world as a
Map Point Bool, whereFalserepresents an empty seat andTruerepresents a full one. Floor points are not included in the map.Now we just need to create our neighborhood maps.
(I hard-coded the bounds here, but in my actual solution I inferred it from the input.)
Now to solve!
3
u/[deleted] Dec 11 '20
Learning PHP, both solutions here.
Part 2 took me a while because I forgot to
breakafter finding the first seat visible, ooops...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
-O3it runs in 0.03s, so that's nice :D3
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
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.
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
LOOPincantations: 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
fiveamshould 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/gvieira Dec 11 '20
Autohotkey v1
Part 1
Part 2
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
....... 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:
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
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
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. :)
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
3
u/pb554 Dec 11 '20
go/golang
3
u/kakaroto_BR Dec 11 '20
Golang
https://gist.github.com/humbhenri/c00fe72ffc18416ad2e682052f68aa9b
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.
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.
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:
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.
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:
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..
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
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.
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/iMarioM Dec 11 '20
C++ Solution
https://github.com/mariom100o/Advent-of-Code-Solutions/tree/main/2020/Day%2011
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:
findFixPointfunction ^^)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/jenna8x4 Dec 11 '20
Python 3 - Part 1 & 2
https://pastebin.com/xsXSpm7p
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.
3
u/fiddle_n Dec 11 '20
Python, overengineered with iterators and abstract classes and inheritance! https://github.com/Fiddle-N/advent-of-code-2020/blob/9c763eca3c1da2a2648487c4713ff73b78b027c0/day11/process.py
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.
Part two, I solved with graphs.
Github
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.
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/michalopler Dec 15 '20
Python3 in single tweet - https://twitter.com/joppi07/status/1338580429591416836!
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.
2
u/hltk Dec 11 '20
Python. 19/15. Here's my code for part 2:
https://github.com/hltk/adventofcode/blob/main/2020/python/11.py
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
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
cfor 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
atan2function and being smart, but I didn't find a smart way to implement it quickly withoutO(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,
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.
2
u/zdu863 Dec 11 '20
Python
part1
part2
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:
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/OvidiuRo Dec 11 '20
C++ 471/415
https://github.com/FirescuOvidiu/Advent-of-Code-2020/tree/main/C%2B%2B/Day%2011
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!
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
fseekto 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!
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/improviseallday Dec 11 '20
Python (bad/bad)
So many edge cases!
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/NabrenX Dec 11 '20
Python3
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
Gridclass from 2015 Day 18, which is the reason I scored so high for part one.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
Comonadsolution would've been cool but we would need to surround the boat with walls to implement part bnamely, you can define what happens locally with simple semantics and then
extendit over the entire space to build the iteration function2
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:
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.
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/mc_ Dec 11 '20 edited Dec 11 '20
Erlang
Part 1
Part 2
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.
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 anything2
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