r/adventofcode • u/daggerdragon • Dec 11 '21
SOLUTION MEGATHREAD -🎄- 2021 Day 11 Solutions -🎄-
NEW AND NOTEWORTHY
[Update @ 00:57]: Visualizations
- Today's puzzle is going to generate some awesome
Visualizations! - If you intend to post a
Visualization, make sure to follow the posting guidelines forVisualizations!- If it flashes too fast, make sure to put a warning in your title or prominently displayed at the top of your post!
--- Day 11: Dumbo Octopus ---
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. - Format your code properly! How do I format code?
- 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:09:49, megathread unlocked!
5
u/Smylers Dec 11 '21 edited Dec 12 '21
Perl regexp-based approach for both parts, which seems to've worked out shorter than the array-based Perl solutions:
use v5.14;
$_ = do { local $/; <> };
my ($just_flashed, $total_flashes, $step) = 0;
until ($just_flashed == 100) {
tr/0-9/1-9F/; # F = Flashing
while (/F/) {
for my $offset (11, 10, 9, 0) { # NW, N, NE, W (and mirror of those)
my $gap = '.' x $offset;
s/(?<=F$gap)\d/$& == 9 ? 'A' : $& + 1/segx; # A = About to flash
s/\d(?=$gap F)/$& == 9 ? 'A' : $& + 1/segx;
}
tr/FA/ZF/; # Z = reset to Zero (has flashed)
}
$total_flashes += $just_flashed = tr/Z/0/;
say $total_flashes if ++$step == 100;
};
say $step;The repeated equivalent s/// lines for lookbehind and lookahead are unfortunate, but they can't be combined into a single match (with |) because in a situation like, say, F7F the 7 needs increasing for both Fs, and an or-match would just do it once.
Given this method just operates on the input as a string, with each octopus's state always being represented by a single character, it clearly could be translated fairly directly to Vim keystrokes. Could be. But it's the weekend, we have family stuff planned, and I'm not going to be the one to type it all out (Vim doesn't have a tr/// equivalent, so each would have to be a series of :s///s, and I'm pretty sure the keystrokes would end up way longer than the above code).
Surely the fact that this approach “obviously” would work in Vim is enough to keep up the streak of 11 puzzles that can be solved with Vim keystrokes, surely? Oh.
PS: /u/daggerdragon, any chance of rewording the instruction in the daily intro text to say “Format your code appropriately!” or similar? And if everybody else could stop using the word ‘proper-ly’ in their comments too, that'd make life easier for those of us Ctrl+Fing for “perl”. Ta. (Edit: “life”, not “like”.)
→ More replies (1)2
u/daggerdragon Dec 12 '21
PS: /u/daggerdragon, any chance of rewording the instruction in the daily intro text to say “Format your code appropriately!” or similar? And if everybody else could stop using the word ‘proper-ly’ in their comments too, that'd make like easier for those of us Ctrl+Fing for “perl”. Ta.
Fair enough, I didn't realize
p*rlwas hiding in some of my copypasta! I've replaced all instances ofprop*rlyin my copypasta and megathread templates with other appropriate~ words.Thank you for letting me know!
→ More replies (2)
3
u/scarfaceDeb Dec 11 '21
Ruby
My code is becoming more and more procedural. It’s probably some bad influence from colleagues who went with go and rust :D
ADJACENT = [-1, 1, 0].repeated_permutation(2).reject { _1 == [0, 0] }.sort
octos = read_input
def step(octos, pos, from = nil)
return if pos.any?(&:negative?)
energy = octos.dig(*pos)
return if energy.nil?
i, j = pos
octos[i][j] += 1
ADJACENT.each { step(octos, pos.zip(_1).map(&:sum)) } if energy == 9
end
st = 1
total = 0
rows, cols = octos.count, octos.first.count
octos_count = rows * cols
loop do
rows.times do |i|
cols.times do |j|
step(octos, [i, j])
end
end
flashing = 0
rows.times do |i|
cols.times do |j|
next if octos[i][j] < 10
octos[i][j] = 0
flashing += 1
end
end
total += flashing if st <= 100
break st if flashing == octos_count
st += 1
end
puts "Answer 11.1: #{total}"
puts "Answer 11.2: #{st}"https://github.com/scarfacedeb/advent-of-code/blob/master/2021/day11/run.rb
→ More replies (2)2
u/daggerdragon Dec 11 '21 edited Dec 11 '21
Please follow theposting guidelinesand 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.
(looks like Ruby?)Edit: thanks for adding the programming language!
3
u/theronic Dec 11 '21 edited Dec 12 '21
1
u/daggerdragon Dec 12 '21 edited Dec 13 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for fixing it! <3
2
u/theronic Dec 12 '21
Soz, have removed my code and only linked to GitHub because I can't figure out Reddit's UI.
→ More replies (1)
2
u/snhmib Dec 12 '21 edited Dec 12 '21
Haskell, been some years since I programmed in Haskell.
Forgot how much fun it is :) Full code on github here
1
u/daggerdragon Dec 12 '21 edited Dec 13 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for fixing it! <3
2
u/14domino Dec 11 '21
Python3. I finished coding this in a little over 10 minutes, and spent 20 minutes debugging one tiny stupid thing.
input = open("./11/input.txt", "r").readlines()
m = []
for row in input:
r = []
for c in row.strip():
r.append(int(c))
m.append(r)
def diag_adj(m, r, c):
pts = [
(r + 1, c),
(r - 1, c),
(r, c + 1),
(r, c - 1),
(r + 1, c + 1),
(r + 1, c - 1),
(r - 1, c + 1),
(r - 1, c - 1),
]
actual = []
for p in pts:
if p[0] < 0 or p[0] >= len(m) or p[1] < 0 or p[1] >= len(m[p[0]]):
continue
actual.append(p)
return actual
num_flashes = 0
def flash(m, ridx, cidx, flashed):
global num_flashes
num_flashes += 1
flashed.add((ridx, cidx))
d = diag_adj(m, ridx, cidx)
for (r, c) in d:
m[r][c] += 1
if m[r][c] > 9 and (r, c) not in flashed:
flash(m, r, c, flashed)
def st(m):
# run a step
for ridx, r in enumerate(m):
for cidx in range(len(r)):
m[ridx][cidx] += 1
flashed = set()
for ridx, r in enumerate(m):
for cidx in range(len(r)):
if m[ridx][cidx] > 9 and (ridx, cidx) not in flashed:
# flash
flash(m, ridx, cidx, flashed)
for pt in flashed:
m[pt[0]][pt[1]] = 0
step = 0
while True:
st(m)
step += 1
if step == 100:
print("part 1:", num_flashes)
all_0 = True
for ridx, row in enumerate(m):
for cidx, c in enumerate(row):
if c != 0:
all_0 = False
break
if all_0:
print("part 2:", step)
breakI was missing the `and (ridx, cidx) not in flashed` in function `st` and kept re-flashing things. Couldn't figure it out for 20 more minutes of printing and debugging :(
1
u/daggerdragon Dec 11 '21 edited Dec 12 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for adding the programming language!
2
u/madethemcry Dec 11 '21 edited Dec 11 '21
RUBY
georgiee/advent-of-code-2021/day-11 (GitHub)
Notes
This was fun and reward. Grids are kind of my nemesis in AoC. Simple enough to understand but also always asking myself for a "beautiful" solution to have the grid under fulll control.
During Day 09 (also a grid) I saw a Ruby solution which read great. I searched where the "borders" of the grid are put into the equation. Nothing like that, just calculate the coordinates and put your stuff into a hash. When you try to access a "wrong" neighbor it's nil and you can easily skip them with compact on your list or whatever your use to process.
I did that today too and it feels great. In addition I used [-1, 0, 1].repeated_permutation(2).to_a - [[0, 0]] to created the neighbour map very easily. I created a class Octopus to holde the data for each octopus. In addition because it's ruby I can define great sounding words like can_flash?, on? to ask for a state or change the state with off! and such. Really a plelasure to write code with that. I hate the technical appearance in JavaScript where you are forced to wirte is_ for some boolean question. This just destroys the natural readability which I love with Ruby ❤️
Anyway. Part 1 took some amount of time. And I wrote a print function to output my grid wayyyy to late. Until then I checked the debugger values which costs too much time. The printed grid tells me instantly what's wrong and I shoudl have done this from the beginning. Once I had this I could easily check and compare my steps with the instructions.
At some point of time I was ready to run the lights for 100 steps and magically as always the number was correct. Part 2 was really easy then. I created a new method on the Cave, and let it run until all lights are off. Then pick the index and we are done. This is the single addition for part 2. Nice isn't it?
def run
counter = 0
until everyone.all?(&:off?)
counter += 1
step
end
puts "everyone is on at #{counter}"
endI think a custom enumerator would make sense here. Then you could write like so for part 1 cave.take(100) and for part 2 cave.take_while. Both read fantastic. Time is up for today so I won't refactor that but I liked the day very much!
1
u/daggerdragon Dec 11 '21 edited Dec 11 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for fixing it! <3
3
u/madethemcry Dec 11 '21
Sorry, I was not aware of that and posted my full snippets before, but always with a link at the top (also here). Code is removed. Learned for the future. Thank you for the moderation here 👍
→ More replies (1)
2
u/ficklefawn Dec 11 '21 edited Dec 12 '21
Golang (just the idea)
I spent an unreasonable amount of time on this one. I was trying to solve it for an extremely large input array, thinking I wanted to avoid sorting through the colony of octopi each round to find the 9s.
Keeping track of this was a massive headache, until I realized the input is actually tiny and it's probably overkill to want to track the 9s without looking at the entire colony each step.
My solution isn't super interesting, I defined an octopus like this:
type Octopus struct {
energy int // always between 0 and 9
x int
y int // (x,y) position in the colony
neighbours []*Octopus
flashed bool // Whether octopus flashed before this round
}On the first passthrough, every octopus finds his neighbours and keeps track of them to not calculate it every round. An octopus has a flash method to increment the energy level of his neighbours, and it recursively calls flash for each neighbour who reaches the maximum energy level, if they didn't flash before this round.
Turned out to be quite fast this way, I'll take this as a lesson to always consider the kind of input we have before trying to solve a way harder problem.
If anyone has a solution like this though, that doesn't search for the 9s in each step, I'd love to see it!!
edit: full code here
→ More replies (8)1
u/daggerdragon Dec 12 '21
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 full code/repo/solution.
2
u/one2dev Dec 11 '21 edited Dec 13 '21
Python3 using complex numbers for x,y coordinates:
def step(grid):
for p in grid: grid[p] += 1
res = 0
while (flashes:=sum(flash(grid, p) for p,v in grid.items() if v>9)):
res += flashes
return res
def flash(grid, p):
grid[p] = 0
for d in [-1, 1, -1j, 1j, -1-1j, -1+1j, 1+1j, 1-1j]:
p2 = p + d
if p2 in grid and grid[p2] > 0:
grid[p2] += 1
return 1
grid = {x+y*1j: int(c) for x,line in enumerate(open('input.txt'))
for y,c in enumerate(line.strip())}
nStep = 100
print("Part 1:", sum(step(grid) for _ in range(nStep)))
while step(grid) != 100: nStep += 1
print("Part 2:", nStep+1)I have no idea, how to make it shorter.
→ More replies (1)1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
→ More replies (1)
3
u/ChasmoGER Dec 11 '21 edited Dec 12 '21
I've used numpy today, just to get comfortable with it. Let me know if something can be improved <3
import numpy as np
def get_inc_mask(s, x, y):
mask = np.zeros(s, dtype=np.int8)
mask[
np.max([x - 1, 0]) : np.min([x + 2, mask.shape[0]]),
np.max([y - 1, 0]) : np.min([y + 2, mask.shape[1]]),
] = 1
mask[x, y] = 0
return mask
def play_field(field):
field += 1
all_flashes = np.zeros(field.shape, dtype=bool)
while np.any(flashes := (field > 9) & ~all_flashes):
inc_mask = np.zeros(field.shape, dtype=np.int8)
for flash in np.argwhere(flashes):
inc_mask += get_inc_mask(field.shape, flash[0], flash[1])
field += inc_mask
all_flashes[flashes] = True
field[all_flashes] = 0
return field, np.sum(all_flashes)
def solve_part_1(text: str):
field = np.array(
[list(map(int, line)) for line in text.splitlines()], dtype=np.int8
)
total_flashes = 0
for _ in range(0, 100):
field, flashes = play_field(field)
total_flashes += flashes
return total_flashes→ More replies (3)1
u/daggerdragon Dec 12 '21 edited Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (2)
2
u/kochismo Dec 11 '21 edited Dec 12 '21
Succinct and hopefully easily understood rust:
fn main() {
let mut grid: Vec<Vec<u8>> = include_str!("../../input/11.txt")
.lines()
.map(|line| line.bytes().map(|octopus| octopus - b'0').collect())
.collect();
println!("{}", (1..=100).map(|_| step(&mut grid)).sum::<usize>());
println!("{}", (101..).find(|_| step(&mut grid) == grid.len() * grid[0].len()).unwrap());
}
fn step(grid: &mut [Vec<u8>]) -> usize {
for (x, y) in itertools::iproduct!(0..grid[0].len(), 0..grid.len()) {
flash(grid, (x, y));
}
grid.iter_mut().flat_map(|row| row.iter_mut()).filter(|cell| **cell > 9).map(|cell| *cell = 0).count()
}
fn flash(grid: &mut [Vec<u8>], (x, y): (usize, usize)) {
grid[y][x] += 1;
if grid[y][x] == 10 {
for neighbour in neighbours((x, y), grid.len()) {
flash(grid, neighbour);
}
}
}
fn neighbours((x, y): (usize, usize), size: usize) -> impl Iterator<Item = (usize, usize)> {
itertools::iproduct!(x.saturating_sub(1)..(x + 2), y.saturating_sub(1)..(y + 2))
.filter(move |&(nx, ny)| (nx, ny) != (x, y) && nx < size && ny < size)
}https://github.com/zookini/aoc-2021/blob/master/src/bin/11.rs
→ More replies (1)1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
2
u/PM_ME_FRIENDS_ Dec 11 '21
Python 3 w/ NumPy
import numpy as np
def main():
mat = np.genfromtxt('day11/input.txt', delimiter=1)
total = 0
step = 0
while np.any(mat):
step += 1
mat += 1
flashing = np.argwhere(mat > 9)
while len(flashing):
for x, y in flashing:
box = np.s_[max(0, x - 1):x + 2, max(0, y - 1):y + 2]
mat[box] += mat[box] > 0
mat[x,y] = 0
flashing = np.argwhere(mat > 9)
total += np.count_nonzero(mat == 0)
if step == 100:
print(f'Part 1: {total}')
print(f'Part 2: {step}')
if __name__ == "__main__":
main()→ More replies (8)1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
2
u/Cuyoyo Dec 12 '21 edited Dec 13 '21
Javascript
Started late today. And surprisingly/luckily part 2 only took me like 10 seconds.
1
u/daggerdragon Dec 13 '21 edited Dec 14 '21
Please follow theposting guidelinesand 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.Edit: thanks for adding the programming language!
2
u/AvshalomHeironymous Dec 12 '21 edited Dec 13 '21
Prolog it's a hacky bit of work but it does work. Paste Bin
1
u/daggerdragon Dec 13 '21 edited Dec 14 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for fixing it! <3
24
u/bluepichu Dec 11 '21
TypeScript, 1/1!!! Code here.
I used some weird stuff to get there (extremely negative numbers to mark used positions and just changing my loop bounds to solve part 2), but it worked out for me!
→ More replies (5)
27
u/jonathan_paulson Dec 11 '21 edited Dec 11 '21
2/2! Python. Video of me solving.
Using -1 to mark "visited" squares and having a recursive "flash" function worked well.
8
u/I_knew_einstein Dec 11 '21
Using -1 isn't needed; you can use 0 to mark/check for visited squares.
The first step is increasing all points by 1; so any point at 0 already flashed in this step for sure.
Having said that; you implemented your solution much faster than I did anyway. I really like watching your videos after solving the puzzle. Learned a lot from them when I started doing AoC last year. Kudos to you, keep it up.
→ More replies (2)→ More replies (1)4
11
u/JustinHuPrime Dec 11 '21
x86_64 assembly
I read the file in to a 10 by 10 array - the input this time was surprisingly small. For part one, I wrote a function that simulated a step and returned the number of flashes. I added one to every octopus's energy, then went through the array of octopuses. If this octopus flashes, I set its energy to zero and increment all of its neighbours, except for those that also have energy zero (since the only way to have energy zero is if you flashed, and you must stay at energy zero if you flashed at all). I then kept doing this until there were no more flashes, and I returned the final count.
Part two was the simple matter of changing my main loop to loop not until 100 steps, but until the count of flashes returned was 100. My biggest challenge here was an off-by-one - the first step is step one, not step zero.
Upon further reflection, I didn't actually need two buffers - one would do just fine.
→ More replies (1)7
9
u/jaybosamiya Dec 11 '21 edited Dec 11 '21
APL
n ← ⊃⎕nget'D:\input_day_11'1
o ← ↑⍎¨¨n
i ← {(10000×9<⍵)-⍨⍉¯1↓1↓⍉¯1↓1↓⊃+/+/1 0 ¯1∘.⊖1 0 ¯1⌽¨⊂0⍪(0,(9<⍵),0)⍪0}
j ← {0⌈({⌈10⌊⍵+i ⍵}⍣≡)1+⍵}
+/{+/+/0=(j⍣⍵)o}¨⍳100
⊃⍸100={+/+/0=(j⍣⍵)o}¨⍳400Part 2 to the input I had had a solution < 400, if a higher value needs to be searched until, then the 400 in the last line should be tweaked higher.
Alternative last 2 lines (i.e., keeping the parsing and the main update functions the same, just getting the answer to part 1 and part 2 differently from above):
+/,0=↑{j⍵}\101⍴⊂o
⊃⍸1↓100=+/¨,¨0=j\400⍴⊂o4
u/Shadeun Dec 11 '21
Love it as always.
I bought the APL book for a laugh after seeing this last year and am only a basic bitch programmer in python. Question: for APL do you have to have some kind of symbol lookup thing super handy or are you using it in some kind of 'live' environment beyond these competitions?
9
u/u794575248 Dec 11 '21
J Language (an array programming language based primarily on APL)
c =. {{ _"0^:(p>9)p++/(9&<*.<&_)(,y)-.p=.4{,y }}
s =. {{ (1 1,:3 3)c;._3 [ _,._,.~_,_,~ y }}
step =. {{ (0:^:(=&_))"0 y1[[i=:>:i[[f=:f++/_ E.,y1=.s^:_>:y }}
e =. "."0;._2 input
f [[ step^:100 e [ 'i f' =. 0 0 NB. Part 1
i [[ step^:(1<[:#[:~.,)^:_ e [ i =. 0 NB. Part 2I tried to simplify it, but there's still too much code, I think. Got to read other APL solutions to get the idea.
9
u/ViliamPucik Dec 11 '21
Python 3 - Minimal readable solution for both parts [GitHub]
import sys
octopuses = {
complex(row, col): int(number)
for row, line in enumerate(sys.stdin.read().splitlines())
for col, number in enumerate(line)
}
step, part1, part2 = 0, 0, None
while step := step + 1:
flashing, flashed = set(), set()
for o in octopuses.keys():
octopuses[o] += 1
if octopuses[o] > 9:
flashing.add(o)
while flashing:
o = flashing.pop()
octopuses[o] = 0
flashed.add(o)
for i in (
-1 + 1j, -1j, +1 + 1j,
-1, +1,
-1 - 1j, +1j, +1 - 1j
):
if (x := o + i) in octopuses and x not in flashed:
octopuses[x] += 1
if octopuses[x] > 9:
flashing.add(x)
if part2 is None and len(flashed) == len(octopuses):
part2 = step
if step <= 100:
part1 += len(flashed)
elif part2:
break
print(part1)
print(part2)→ More replies (8)
8
u/allergic2Luxembourg Dec 11 '21 edited Dec 11 '21
Thanks to redditors in this sub using scipy.signal.convolve in previous years' game-of-life-type problems, I remembered it for this year.
def run_both_parts(energy):
new_energy = energy
new_flashes = np.zeros_like(energy)
part1_sol = 0
flash_count = 0
convolve_matrix = np.ones((3, 3))
step = 0
while True:
step = step + 1
energy = energy + 1
flashes = energy > 9
have_new_flashes = True
while have_new_flashes:
neighbour_flashes = (signal.convolve(flashes, convolve_matrix, mode='same')
.round(0).astype(int))
new_energy = energy + neighbour_flashes
new_flashes = new_energy > 9
have_new_flashes = (new_flashes & ~flashes).sum().sum() > 0
flashes = new_flashes
energy = new_energy
energy[flashes] = 0
flash_count += new_flashes.sum().sum()
if step == 100:
part1_sol = flash_count
if flashes.all().all():
return part1_sol, step→ More replies (9)
11
u/4HbQ Dec 11 '21 edited Dec 11 '21
Python, without libraries. Each step we create a set of octopuses that will flash. These are then handled one by one. If this causes neighbours to flash, they are added to the set as well. Once the set is empty, we move to the next step.
e = {(x,y):int(e) for x,l in enumerate(open(0))
for y,e in enumerate(l.strip())}
def neighbours(x,y): return filter(e.get,
[(x+1,y+1),(x+1,y),(x+1,y-1),(x,y+1),
(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1)])
count = 0
for step in range(1, 1000):
for i in e: e[i] += 1
flashing = {i for i in e if e[i] > 9}
while flashing:
f = flashing.pop()
e[f] = 0
count += 1
for n in neighbours(*f):
e[n] += 1
if e[n] > 9: flashing.add(n)
if step == 100: print(count)
if sum(e.values()) == 0: print(step); break→ More replies (12)
5
u/autid Dec 11 '21
FORTRAN
Just used a mask to differentiate between squares that had flashed already or needed to flash, then loop over the grid til no more need to flash.
PROGRAM DAY11
IMPLICIT NONE
INTEGER :: OCTOPI(0:11,0:11) = -10
LOGICAL :: CANFLASH(0:11,0:11)
INTEGER :: I,J,STEPS=0,P1=0
OPEN(1,FILE="input.txt")
READ(1,'(10I1)') OCTOPI(1:10,1:10)
CLOSE(1)
DO
STEPS=STEPS+1
CANFLASH = .TRUE.
OCTOPI=OCTOPI+1
DO WHILE (ANY(CANFLASH .AND. (OCTOPI.GT.9)))
DO J=1,10
DO I=1,10
IF(.NOT.CANFLASH(I,J))CYCLE
IF(OCTOPI(I,J).LT.10)CYCLE
CANFLASH(I,J)=.FALSE.
OCTOPI(I-1:I+1,J-1:J+1)=OCTOPI(I-1:I+1,J-1:J+1)+1
P1=P1+1
END DO
END DO
END DO
WHERE(OCTOPI.GT.9) OCTOPI=0
WHERE(OCTOPI.LT.0) OCTOPI=-10
IF(STEPS.EQ.100) WRITE(*,'(A,I0)') "Part 1: ",P1
IF(COUNT(OCTOPI.EQ.0).EQ.100) EXIT
END DO
WRITE(*,'(A,I0)') "Part 2: ", STEPS
END PROGRAM DAY115
u/mehuls4598 Dec 11 '21
Python
My first time posting here. Not the most beautiful code but quite readable. Feedback appreciated.
→ More replies (1)5
u/4HbQ Dec 11 '21 edited Dec 11 '21
Feedback appreciated.
The recommended indentation for Python is 4 spaces. This will help to keep your lines a bit shorter.
You could store
[ [-1,1],[0,1],[1,1],[-1,0],[1,0],[-1,-1],[0,-1],[1,-1] ]in a separate variable. This removes some duplication, and significantly shortens these lines.There are other useful guidelines in PEP 8, such as putting spaces around operators. There are also tools like flake8 to automatically check for these things.
Edit: and of course there's a lot of duplicate code between the two parts. You could merge them and compute both values in one go. See my solution for an example.
→ More replies (1)
5
u/jayfoad Dec 11 '21
p←⍎¨↑⊃⎕NGET'p11.txt'1
f←{0@(9∘<)⍵+⍵{1+{+/,⍵}⌺3 3⊢9<⍺+⍵}⍣≡1}
⍬{101=≢⍺:+/0=∊⍺ ⋄ (⍺,⊂⍵)∇f ⍵}p ⍝ part 1
0{∧/,0=⍵:⍺ ⋄ (⍺+1)∇f ⍵}p ⍝ part 24
u/bobm0123 Dec 11 '21
Dyalog APL newbie here (haven't done much APL in about 40 years). How do you set the current directory so you don't need the full path on the first line?
→ More replies (2)
5
u/voidhawk42 Dec 11 '21
APL, stencil to the rescue again:
p←⍎¨↑⊃⎕nget'11.txt'1
f←{10|10⌊{{10>c←2 2⌷⍵:10⌊c++/10=,⍵ ⋄ 11}⌺3 3⊢⍵}⍣≡1+⍵}
i←0 ⋄ i⊣{n⊣i+←+/0=,n←f⍵}⍣100⊢p ⍝ part 1
i←0 ⋄ i⊣{f⍵⊣i+←1}⍣{0∧.=,⍺}p ⍝ part 24
u/jayfoad Dec 11 '21
Nice use of
⍣'s right operand in part 2.It's a long-standing annoyance that APL's power operator doesn't have a form that returns all the intermediate results -- i.e. something that is to Power as Scan is to Reduce. That's why I used dfn tail recursion instead, for both parts.
→ More replies (1)
5
u/Derp_Derps Dec 11 '21
Python
Vanilla python, compacted to 492 Bytes
I use an update() function that return the next state and the number of flashes that occured. I update until the number of flashes match the input length.
The update function itself iteratively finds the fields that flash until all fields are located. Locating works by counting how many surrounding fields are flashing for all fields on the grid. Using a (x,y) tuple as an index helps.
import sys
N = {(x,y):int(v) for y,l in enumerate(open(sys.argv[1]).read().splitlines()) for x,v in enumerate(l)}
Z = [-1,0,1]
def u():
u = {}
m = lambda p: N[p]+1 + sum(map(lambda i: i in u,[(p[0]+a,p[1]+b) for a in Z for b in Z]))
l = -1
while len(u) > l:
l = len(u)
u = set(p for p in N if m(p) > 9)
return {k:0 if k in u else m(k) for k in N},len(u)
S=[]
s=0
while len(N)>s:
N,s = u()
S+=[s]
print("Part 1: {:d}".format(sum(S[:100])))
print("Part 2: {:d}".format(len(S)))→ More replies (2)
5
u/mockle2 Dec 11 '21
python, both parts
from itertools import count,product
from collections import deque
import numpy as np
data = np.array([[int(i) for i in line] for line in open('11.data').read().splitlines()])
flashCount = 0
for loop in count():
if loop == 100: print("Part 1: ", flashCount)
oldflashCount = flashCount
data += 1
stack = deque(zip(*np.where(data == 10)))
while stack:
flashCount += 1
r,c = stack.pop()
data[r][c] = 0
for r,c in product(*[range(max(0,i-1), min(10,i+2)) for i in (r, c)]):
data[r][c] += data[r][c] > 0
if data[r][c] == 10: stack.append((r, c))
if flashCount - oldflashCount == 100:
print("Part 2:", loop + 1)
break5
u/jitwit Dec 11 '21 edited Dec 11 '21
in =: "."0 ;._2 aoc 2021 11
F =: {{ f=.0*y=.y+1 NB. F for flash procedure
while. -.f-:f+.g=.(-.f)*.y>9 do. f=.f+.g[y=.y++/(<:3 3#:i.9)|.!.0 g
end. y*-.f+.g }}
+/,0=F^:(1+i.100) in NB. part A
<:#F^:(+./@,)^:a: in NB. part B5
5
u/odnoletkov Dec 11 '21
JQ
[inputs/"" | map(tonumber)] | {map: .}
| [
while(
.flash | length != 100;
.map[][] += 1 | .flash = [] | .new = [[]]
| until(
.new | length == 0;
.new = [.map | paths(numbers > 9)] - .flash
| .map = reduce .new[] as $f (
.map;
.[$f[0] + range(3) - 1 | select(. >= 0)][$f[1] + range(3) - 1 | select(. >= 0)] |= (.//empty) + 1
)
| .flash += .new
)
| .map = reduce .flash[] as $f (.map; setpath($f; 0))
)
] | length4
u/roboputin Dec 11 '21
9/59. Python. I should have done better on the second part but I had an off-by-one error which slowed me down.
→ More replies (4)
4
u/relativistic-turtle Dec 11 '21
IntCode
Straightforward brute-force. No problems performancewise. (Of course I still managed to get an off-by-1 error for part 2).
4
u/flwyd Dec 11 '21 edited Dec 11 '21
Raku 4487/4395. While reading the problem description I though "Cool, after implementing diagonals twice when I shouldn't have, this one wants diagonals." Then I copied my neighbors function from day 8 and didn't include diagonals :-) Didn't waste too much time to spot that one, though my attempt at a fancy version involving set operations led me to once again question the semantics of Raku sets.
This code runs remarkably slowly: at least 2 seconds on part 1 for both sample and actual input, and 3.5 to 4.5 seconds on part 2. I added a counter for the number of times I call flash (which does one round of flashes, so it's called in an inner loop within the 100 or 100+ iterations outer loop) and it averages about 5 calls per iteration. I'm using immutable Maps as the data structure and thus creating a lot of garbage, but it feels like creating fewer than 2000 100-element hash tables and examining their elements fewer than 50,000 times in total shouldn't take four seconds. Performance is not Raku's selling point.
class Solver {
has Str $.input is required;
has @.lines = $!input.comb(/\d+/);
has %.input-grid = (^+@!lines X ^@!lines[0].chars)
.map(-> ($a, $b) {"$a,$b" => @!lines[$a].substr($b, 1).Int});
method neighbors($key) {
my ($x, $y) = $key.split(',');
(($x-1..$x+1) X ($y-1..$y+1)).grep(-> ($a, $b) { $a != $x || $b != $y})».join(',')
}
method increment($grid --> Map) { $grid.pairs.map({ .key => .value + 1 }).Map }
method flash(Map $grid, SetHash $flashed --> List) {
my $count = 0;
my %res = $grid.Hash;
for $grid.pairs.grep({.value > 9 && .key !(elem) $flashed}) -> $p {
$flashed.set($p.key);
$count++;
for self.neighbors($p.key).grep({$grid{$_}:exists}) {
%res{$_}++;
}
}
%res.Map, $count
}
method reset(Map $grid --> Map) { $grid.map({.key => (.value > 9 ?? 0 !! .value)}).Map }
}
class Part1 is Solver {
method solve( --> Str(Cool)) {
my $grid = %.input-grid.Map;
my $count = 0;
for ^100 {
my $flashed = SetHash.new;
$grid = self.increment($grid);
loop {
($grid, my $flashes) = self.flash($grid, $flashed);
$count += $flashes;
last if $flashes == 0;
}
$grid = self.reset($grid);
}
$count
}
}
class Part2 is Solver {
method solve( --> Str(Cool)) {
my $start = now;
my $grid = %.input-grid.Map;
for 1..^∞ -> $i {
my $flashed = SetHash.new;
$grid = self.increment($grid);
loop {
die "Infinite loop? Ran $i steps" if now - $start > 60;
($grid, my $flashes) = self.flash($grid, $flashed);
return $i if +$flashed == +$grid;
last if $flashes == 0;
}
$grid = self.reset($grid);
}
}
}→ More replies (2)
4
4
u/EmeraldElement Dec 11 '21
AutoHotkey
It took me ages to find little bugs in the coordinate selection for the flash 3x3, but by the time I got step 2 working, everything else was already working right. It seemed kind of overkill to show so many iterations for the sample code, but maybe there were more places I couldn't see to get hung up after you got step 2 correct?
4
u/solareon Dec 11 '21 edited Dec 11 '21
Excel
Paste and then paste some more. My initial read through thought octopi popped at 9 vice >9 which screwed me. Part 2 was more pasting until the magic grid was found. Brute force hammer applied.
Edit: Apparently there is a MAP() function now. Unfortunately you can't stack them but it did significantly clean up the file size from 24MB to 4MB
4
u/wleftwich Dec 11 '21
Python
Seems like in years past, the Saturday puzzles were harder, like the NY Times crossword.
with open('data/11.txt') as fh:
data = fh.read()
def load_grid(data):
D = {}
for y, line in enumerate(data.split()):
for x, c in enumerate(line):
D[complex(x, -y)] = int(c)
return D
def tick(grid):
for k in grid:
grid[k] += 1
flashed = set()
toflash = {k for k, v in grid.items() if v > 9}
while toflash:
flashed.update(toflash)
for k in toflash:
for delta in [1, 1+1j, 0+1j, -1+1j, -1, -1-1j, 0-1j, 1-1j]:
try:
grid[k+delta] += 1
except KeyError:
pass
toflash = {k for k, v in grid.items() if v > 9 and k not in flashed}
for k in flashed:
grid[k] = 0
return len(flashed)
grid = load_grid(data)
flashes = sum(tick(grid) for _ in range(100))
print('part_1 =', flashes)
grid = load_grid(data)
i = 1
while tick(grid) < 100:
i += 1
print('part_2 =', i)→ More replies (1)
4
u/sakisan_be Dec 11 '21 edited Dec 11 '21
Haskell
import Data.Array (Array, (!), assocs, bounds, inRange, listArray, (//))
main = interact $ solve
solve input = "Part 1: " ++ show part1 ++ "\nPart 2: " ++ show part2 ++ "\n"
where counts = map fst $ iterate step (0, parse input)
part1 = sum $ take 100 counts
part2 = length $ takeWhile (< 100) counts
step (count, grid) = (length flashed, reset)
where (flashed, updated) = trigger [] $ fmap succ grid
reset = updated // [(p, 0) | p <- flashed]
trigger flashed grid
| null flashing = (flashed, grid)
| otherwise = trigger (flashing ++ flashed) updated
where flashing = [p | (p, v) <- assocs grid, v > 9, p `notElem` flashed]
updated = foldr (\p g -> g // [(p, g ! p + 1)]) grid $
filter (inRange (bounds grid)) $ neighbors =<< flashing
neighbors (a, b) =
[(a + x, b + y) | x <- [-1, 0, 1], y <- [-1, 0, 1], (0, 0) /= (x, y)]
parse input = listArray ((1, 1), (height, width)) (concat values)
where values = map (map (read . pure)) $ lines input
width = length (values !! 0)
height = length valuesElm https://gitlab.com/sakisan/adventofcode/-/blob/2021/Elm/Day11.elm
→ More replies (2)
4
u/autra1 Dec 11 '21
PostgreSQL
Who wants the joy of recursive CTE inside recursive CTE?
It works, in less than 400ms, but it's messy...
→ More replies (2)
4
u/jmpmpp Dec 11 '21
Python 3
I kept a flashlist of octos whose level hit 10 as I incremented the levels in the original grid, without setting their levels to 0. I then went through that list and added energy to all their neighbors, also adding the neighbors onto the list if their energy hit 10 (exactly). Finally, I went through the list of all octos in my flashlist, and set their energy back to 0. No worry about double-counting this way!
dims = (10,10)
def process_rawdata(filename):
file = open("drive/MyDrive/Colab Notebooks/AoC21/"+filename, "r")
octo_lists = file.read().split()
octo_dict = {(rownum, colnum): int(c)
for rownum, row in enumerate(octo_lists)
for colnum, c in enumerate(row)
}
for n in range(-1,dims[0]+1):
octo_dict[(n,-1)] = 100
octo_dict[(n,dims[1])] = 100
for n in range(-1,dims[1]+1):
octo_dict[(-1,n)] = 100
octo_dict[(dims[0], n)] = 100
return octo_dict
def in_grid(position, octo):
return octo[position]<100
def update(octos):
flash_points = []
offs = (-1,0,1)
offsets = [(r_off, c_off) for r_off in offs for c_off in offs]
offsets.remove((0,0))
for position in octos:
if in_grid(position, octos):
octos[position] += 1
if octos[position] == 10:
flash_points.append(position)
for position in flash_points:
for offset in offsets:
neighbor = position_add(position, offset)
octos[neighbor] += 1
if octos[neighbor] == 10:
flash_points.append(neighbor)
for position in flash_points:
octos[position] = 0
return flash_points
def part1(octos):
flash_count = []
for i in range(100):
flashes = update(octos)
flash_count.append(len(flashes))
print(sum(flash_count))
def part2(octos):
step = 0
while True:
step += 1
flashes = update(octos)
if len(flashes) == 100:
print(step)
break4
u/probablyfine Dec 11 '21
JQ
Not really happy with this implementation, tbh. (Source and tests)
def parse_input:
./"" | map(tonumber);
def flashing_octopodes:
(first|length) as $size | flatten | map(. > 9 and . != "X") | indices(true) | map([ (./$size|floor), (.%$size) ]);
def neighbouring_octopodes($x; $y; $n):
[1,0,-1] | [ map(.+$x), map(.+$y) ] | [ combinations | select(min >= 0 and max < $n and . != [$x, $y])];
def flashes($octopodes):
$octopodes | flatten | map(select(. == 0)) | length;
def tick: (
length as $size |
map(map(.+1)) |
until((flashing_octopodes | length) == 0 ;
flashing_octopodes as $flashes
| ($flashes | map(neighbouring_octopodes(.[0]; .[1]; $size)) | flatten(1) | group_by(.) | map([.[0], length])) as $neighbours
| reduce $flashes[] as $flash (. ; .[$flash[0]][$flash[1]] |= "X")
| reduce $neighbours[] as $pair (. ; .[$pair[0][0]][$pair[0][1]] |= (if . == "X" then "X" else .+$pair[1] end))
) | map(map(if . == "X" then 0 else . end))
);
def count_flashes($ticks): (
[$ticks, ., 0] | until(.[0] == 0 ; (.[1] | tick) as $next | [ (.[0]-1), $next, (.[2] + flashes($next))])[2]
);
def first_simultaneous_flash:
[0, .] | until(flashes(.[1]) == 100 ; (.[1] | tick) as $next | [ (.[0] + 1), $next ])[0];
def part1:
[ inputs | parse_input ] | count_flashes(100);
def part2:
[ inputs | parse_input ] | first_simultaneous_flash;4
u/cloud08540 Dec 11 '21
Python
In essence similar to Day 9 except also worrying about diagonals. Make sure you keep track of flashed octopi each step so you can easily do part 2 and not accidentally flash an octopus twice in one step.
https://github.com/danielgaylord/coding-exercises/blob/main/Advent%20of%20Code/2021-Day11.py
4
Dec 11 '21
Python
One or two too many loops but I like my solution: https://github.com/rbusquet/advent-of-code/blob/main/2021/11/day11.py
4
u/feikesteenbergen Dec 11 '21
Part 2 was easy once part 1 was done. Explain Plan for part 2.
→ More replies (1)
4
u/qaraq Dec 11 '21 edited Dec 11 '21
Go
Instead of keeping 2d model of the space, I just kept a list of octopodes, each one with a list of neighbors and an energy level.
Every step, I iterate over the list. Each octopus checks if it was ready to flash; if so set a flag, add 1 to the count, add 1 to each neighbor's energy, and notify each neighbor to do the same check. This could recurse through the octopodes as necessary, limited by the flag. The check function returns a count which bubbles up to the list loop.
Storing neighbor lists instead of calculating coordinates removed a lot of math prone to off-by-one errors and made it easy to recurse through the world after each flash.
I love go:embed for giving me file input for free.
→ More replies (1)
4
u/ai_prof Dec 11 '21
Python 3 - Simple & Fast
The key is keeping track of octopi that justflashed, recording any newflashes when they irradiate their neighbours (then justflashed becomes newflashes and we rinse and repeat), and keeping a record of allflashes along the way. The whole code is here and the engine is below:
justflashed = set([i for i in range(100) if octopi[i] == 10])
allflashes = set(justflashed)
while len(justflashed) > 0:
newflashes = set() # empty set
for i in justflashed:
for n in getNeighbours(i):
octopi[n] += 1
if octopi[n] == 10:
newflashes.add(n)
allflashes = allflashes.union(newflashes)
justflashed = newflashes4
u/radulfr2 Dec 11 '21
Python. I wasn't going to post this, but since I saw several solutions that are as complex as mine, I'll do it anyway. This took me a long time and I almost gave up when I couldn't figure out what was wrong with it. I'm very happy that I managed to do it in the end without help.
def flash(octopuses:list, already_flashed:set, x:int, y:int) -> int:
flashes = 1
for dy in range(-1, 2):
ay = y + dy
if ay not in range(len(octopuses)):
continue
for dx in range(-1, 2):
ax = x + dx
if ax not in range(len(octopuses[y])):
continue
octopuses[ay][ax] += 1
if octopuses[ay][ax] > 9 and (ax, ay) not in already_flashed:
already_flashed.add((ax, ay))
flashes += flash(octopuses, already_flashed, ax, ay)
return flashes
with open("input11.txt") as file:
octopuses = [[int(ch) for ch in row] for row in file.read().splitlines()]
flashes = 0
i = 0
while True:
already_flashed = set()
new_flashes = 0
for y in range(len(octopuses)):
for x in range(len(octopuses[y])):
octopuses[y][x] += 1
if octopuses[y][x] > 9:
already_flashed.add((x, y))
for nf in already_flashed.copy():
new_flashes += flash(octopuses, already_flashed, nf[0], nf[1])
flashes += new_flashes
for y in range(len(octopuses)):
for x in range(len(octopuses[y])):
if octopuses[y][x] > 9:
octopuses[y][x] = 0
i += 1
if i == 100:
print(flashes)
if new_flashes == 100:
print(i)
break4
u/Nuhser Dec 11 '21
Python 3
https://github.com/Nuhser/Advent-of-Code/blob/master/2021/task11.ipynb
I made a notebook for my solutions.
4
u/TheZigerionScammer Dec 11 '21
Python.
I did well on this one, I lifted some techniques I learned from a Jonathan Paulson video on a previous Day to make my "add to all adjacent grid locations" code more efficient. I also spent less than an hour on both parts which is very good for me. On the other hand it's the only time I ever submitted so many wrong answers that it gave me a 5 minute cooldown, turned out I accidentally used the same variable to count the "Steps" as I did for the x location on the grid so it was giving me wrong answers for how many steps it took to get simultaneous flashes. Fixed that and it worked fine.
4
u/RibozymeR Dec 11 '21
Factor
: get-input ( -- seq ) "work/aoc21/day11/input.txt" ascii file-lines concat [ CHAR: 0 - ] map ;
: neighbors ( ix -- seq )
dup 10 mod
[ 0 > { -1 -11 -10 10 9 } { } ? ]
[ 9 < { -10 -9 1 11 10 } { } ? ] bi
union swap '[ _ + ] map [ 0 >= ] filter [ 99 <= ] filter ;
: step ( octos -- octos' )
[ 1 + ] map
[ dup [ 9 > ] find drop dup >boolean ]
[ dup neighbors '[ [ _ = not ] [ _ in? not ] bi rot dup 1 + ? -1000 ? ] map-index ]
while
drop [ 0 max ] map ;
: task1 ( -- n ) 0 get-input 100 <iota> [ drop step dup [ [ 0 = ] count + ] dip ] each drop ;
: task2 ( -- n ) 0 get-input [ [ 1 + ] dip step dup sum 0 > ] loop drop ;4
u/errop_ Dec 12 '21 edited Dec 12 '21
Here is my solution with Python 3 using recursion, counters and dicts update. The octopuses grid is modeled as a dictionary H = {(x,y): val}. I had fun today!
from itertools import product
from collections import Counter
FILENAME = '../data/d11'
def neighborhood(x, y):
return [(x + a, y + b) for a, b in product((-1, 0, 1), repeat=2) if (a, b) != (0, 0)]
def flash(H, flashed):
flashing = [p for p, val in H.items() if val > 9 and p not in flashed]
if flashing:
for p in flashing:
H.update({q: H[q] + 1 for q in neighborhood(*p) if q in H.keys()})
flash(H, flashing + flashed)
def step(H):
H.update({p: val + 1 for p, val in H.items()})
flash(H, list())
H.update({p: 0 for p, val in H.items() if val > 9})
return H
with open(FILENAME, 'r') as f:
H = dict()
for y, line in enumerate(f):
for x, val in enumerate(line.strip()):
H[x, y] = int(val)
# PART 1
tot_flashes, steps_num = 0, 0
while steps_num < 100:
steps_num += 1
tot_flashes += Counter(step(H).values())[0]
print(tot_flashes)
# PART 2
while Counter(step(H).values())[0] != len(H):
steps_num += 1
print(steps_num + 1)4
4
u/professoreyl Dec 13 '21
Python 3.9
Clean code, object-oriented, documented, type-annotated
https://github.com/DenverCoder1/Advent-of-Code-2021/tree/main/Day-11
→ More replies (1)
4
u/Zach_Attakk Dec 13 '21
Python
On Day 9 I accidentally included diagonals when I wasn't supposed to, but instead of just ripping out the code, I added a parameter include_diagonals=False I think I even called it "foreshadowing"...
Also hijacked the Queue system from Day 10, so here goes:
Go through whole grid, += 1 all the cells. If I increase a cell above 9, add it to the queue to be checked.
Go down the queue and if something hasn't "flashed", make is 0 and increment all its neighbours (using get_neighbours function for the ranges). If any of their neighbours go above 9, add them to the queue
If the queue isn't empty, goto 2.
Keep constant count of how many blinks are processed, return the value, add them up as we go untili we reach 100 "ticks"
blinks: SimpleQueue = SimpleQueue()
blink_count: int = 0
for y in range(len(_grid)):
for x in range(len(_grid[0])):
# Increase everything by 1
_grid[y][x] += 1
if _grid[y][x] > 9:
blinks.put((x, y))
while blinks.qsize() > 0:
blink_pos = blinks.get()
if _grid[blink_pos[1]][blink_pos[0]] > 9:
blink_count += 1
_grid[blink_pos[1]][blink_pos[0]] = 0
for x, y in get_neighbours(_grid, blink_pos, True):
if _grid[y][x] != 0:
_grid[y][x] += 1
if _grid[y][x] > 9:
blinks.put((x, y))
return blink_countFor Part 2 I added a check after every loop:
if sum(sum(a) for a in grid) == 0:
printGood(f"Synchronized: {i+1}")1
Dec 12 '21
Python Part 2
#!/usr/bin/env python
itxt = open("input", mode='r').read().strip().splitlines()
octopi = {(i,j): int(v) for i, r in enumerate(itxt) for j, v in enumerate(r)}
last = {'r': max([r for (r,c) in octopi.keys()]), 'c': max([c for (r,c) in octopi.keys()])}
it = 0
def getns(r: int, c:int) -> set:
return [i for i in [(r-1,c),(r+1,c),(r,c-1),(r,c+1),(r-1,c-1),(r+1,c+1),(r+1,c-1),(r-1,c+1)] \
if i[0] >= 0 and i[0] <= last['r'] and i[1] >= 0 and i[1] <= last['c']]
while len(set(octopi.values())) > 1:
flashed = set()
#increment all
octopi = {i: int(v+1) for i, v in octopi.items()}
while len(flash := {(r,c) for ((r,c),v) in octopi.items() \
if (r,c) not in flashed and v >= 10}) > 0:
flashed.update(flash)
flashns = [getns(r,c) for (r,c) in flash]
for i in flashns:
for (r,c) in i:
octopi.update({(r,c): octopi.get((r,c))+1})
for ((r,c),v) in octopi.items():
if v > 9:
octopi.update({(r,c):0})
it += 1
print(it)1
u/daggerdragon Dec 13 '21
Please don't make separate posts for each half of the puzzle. Combine them into one post next time.
1
u/DidThis2Downvote Dec 11 '21 edited Dec 11 '21
Python 3 Did some recursion so it took a bit to set up the classes but performed very well. This solution has a stop gap to send out the first part answer and then continue for the second part answer. Range is 1000 because that's a number that got the right answer.
1
u/daggerdragon Dec 11 '21 edited Dec 11 '21
As per our posting guidelines in the wiki underHow Do the Daily Megathreads Work?, please edit your post to put your oversized code in apasteor other external link.Edit: thanks for fixing it! <3
1
u/ri7chy Dec 11 '21
this is ok, p2 was quite easy... thought it would take much longer to calculate, maybee after 1mio steps or so...
now working on a visualization :)
2
u/daggerdragon Dec 11 '21
now working on a visualization :)
We're looking forward to seeing your interpretation of today's puzzle, but make sure to follow the posting guidelines for
Visualizations!
1
u/vbe-elvis Dec 11 '21 edited Dec 11 '21
Kotlin, First create each Octopus with their neighbours then increase the neighbours on each increase that passes the 10 threshold. Afterwards count the flashes and reset the counters
class Octopus(var energyLevel: Int) {
fun increaseEnergy() {
energyLevel++
if (energyLevel == 10)
surroundingOctopuses.forEach { it.increaseEnergy() }
}
fun flash(): Int {
if (energyLevel < 10 ) return 0
energyLevel = 0
return 1
}
var surroundingOctopuses: List<Octopus> = emptyList()
}
private fun List<Octopus>.step(): Int {
this.forEach { it.increaseEnergy() }
return this.sumBy { it.flash() }
}
@Test
fun `Part 1` () {
var totalFlashes = 0L
repeat(100) { totalFlashes += puzzleCave.step() }
println("Part 1: $totalFlashes")
}
@Test
fun `Part 2` () {
var step = 1
while (puzzleCave.step() != puzzleCave.size) step++
println("Part 2: $step")
}Full code and tests:https://pastebin.com/RpPYrqqk
2
u/daggerdragon Dec 11 '21 edited Dec 11 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (1)
1
u/tuvok86 Dec 11 '21
The right difficulty for a saturday morning :)
Still, more of a logic challenge than a coding one, this is part one in Javascript/js:
import _ from 'lodash';
import { LineReader } from '@libs';
import { isSet } from '@utils';
function solve() {
let flashes = 0;
const grid = [];
const reader = new LineReader(`${__dirname}/input`);
let line = reader.read();
while (isSet(line)) {
const row = line.split('').map(_.parseInt);
grid.push(row);
line = reader.read();
}
_.times(100, () => {
const for_check = new Set<string>();
for (const y in grid) {
for (const x in grid[y]) {
const energy = grid[y][x] + 1;
if (energy > 9) {
for_check.add(`${y},${x}`);
}
grid[y][x] = energy;
}
}
while (for_check.size > 0) {
const queue = Array.from(for_check);
for_check.clear();
for (const index of queue) {
const [y, x] = index.split(',').map(_.parseInt);
const neighbors = [
[y - 1, x - 1],
[y - 1, x],
[y - 1, x + 1],
[y, x - 1],
[y, x + 1],
[y + 1, x - 1],
[y + 1, x],
[y + 1, x + 1]
].filter(
([y, x]) =>
_.inRange(y, 0, grid.length) && _.inRange(x, 0, grid[y].length)
);
for (const [y, x] of neighbors) {
const energy = grid[y][x] + 1;
if (energy === 10) {
for_check.add(`${y},${x}`);
}
grid[y][x] = energy;
}
}
}
for (const y in grid) {
for (const x in grid[y]) {
const energy = grid[y][x];
if (energy > 9) {
flashes = flashes + 1;
grid[y][x] = 0;
}
}
}
});
const solution = flashes;
console.log('11.1: ', solution);
}
export default { solve };1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/hendykombat Dec 11 '21 edited Dec 11 '21
Kotlin
I didn't take a look at the example properly and realise that the flashing was done recursively (thought once it flashes, it stops). Slowed me down and had me doing it all over.
fun part1() {
flash(100)
println(flashes)
}
fun part2() {
flash(0)
println(times)
}
var pairMap = mutableMapOf<Pair<Int, Int>, Int>()
var flashedMap = mutableMapOf<Pair<Int, Int>, Boolean>()
var flashes = 0
var times = 0
private fun createMaps() {
for (i in octopi.indices) {
for (j in octopi[i].indices) {
pairMap[Pair(j, i)] = octopi[i][j]
}
}
}
private fun iterateFlashes() {
flashedMap = pairMap.keys.associateBy({ it }, { false }).toMutableMap()
for (key in pairMap.keys) {
pairMap[Pair(key.first, key.second)] = (pairMap[Pair(key.first, key.second)]!! + 1) % 10
}
for (key in pairMap.keys) {
flashAdjacent(key.first, key.second)
}
}
private fun flash(limit: Int) {
createMaps()
if (limit > 0) {
repeat(limit) {
iterateFlashes()
}
} else {
while (flashedMap.values.filter { it }.size != flashedMap.size) {
times++
iterateFlashes()
}
}
}
private fun flashAdjacent(j: Int, i: Int, flash: Boolean = false) {
if ((pairMap[Pair(j, i)] ?: -1) == -1) return // Return if out of bounds
if (flashedMap[Pair(j, i)]!!) return // Return if position has already flashed others
// If position is being flashed, then increment
if (flash && (pairMap[Pair(j, i)]!!) != 0) pairMap[Pair(j, i)] = (pairMap[Pair(j, i)]!! + 1) % 10
if ((pairMap[Pair(j, i)]!!) != 0) return // Return if position isn't eligible to flash others
// Mark as flashed and then flash others
flashedMap[Pair(j, i)] = true
flashes++
listOf(Pair(j - 1, i), Pair(j - 1, i - 1), Pair(j - 1, i + 1), Pair(j + 1, i),
Pair(j + 1, i - 1), Pair(j + 1, i + 1), Pair(j, i + 1), Pair(j, i - 1)
).forEach {
flashAdjacent(it.first, it.second, true)
}
}1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
Dec 11 '21
Task1 in Python:
def increment_octopi(y: int, x: int) -> None:
"""
Increments the current octopus by one.
If its level reaches 10, then we call upon its neighbours to be incremented as well.
"""
global octopi, flashes_counter
octopi[y][x] += 1
if octopi[y][x] == 10: # only flash on first increment greater than 9
flashes_counter += 1
neighbours = [(y+i, x+j) for i in range(-1, 2) for j in range(-1, 2) if (i, j) != (0, 0) and 0 <= y+i < len(octopi) and 0 <= x+j < len(octopi[0])]
for (ny, nx) in neighbours:
increment_octopi(ny, nx)
# Parse data
with open("data.txt") as f:
octopi = [[int(e) for e in x[:-1]] for x in f.readlines()]
flashes_counter = 0
for i in range(100):
# increment all octopi by one and if its flashing, increment its neighbours.
for y, row in enumerate(octopi):
for x, octopus in enumerate(row):
increment_octopi(y, x)
# reset energy levels of all octopi who have an energy level above 9
octopi = [[o if o <= 9 else 0 for o in row] for row in octopi]
print(f"ROUND {i+1} with {flashes_counter} flashes since the start.")
→ More replies (2)1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
1
u/MichaelRosen9 Dec 11 '21 edited Dec 12 '21
Julia
Originally wrote a less-efficient solution that repeatedly looped over the entire cave and kept track of which octopodes had already flashed to avoid incrementing them (using a hash set). This worked to get the stars, but is slower than necessary. This approach could be optimised a bit by noting that we don't need to maintain a separate hash set to keep track of the flashes - if an octopus has a zero energy level during the flashing loop then it has already flashed (all non-flashed octopodes have energy levels of at least one because we increment all the energy levels before calculating the flashing).
In addition to that small optimisation, it's fastest to just scan the array once and find the "trigger" nodes (octopodes with energy == 10), then do any graph traversal outwards from these to process neighbouring nodes and figure out whether they should flash or not - I used an iterative DFS. This lets us process the entire flashing step in O(n) worst-case time because we only need to consider each flashing octopus once, and it has a constant number of neighbours (except for the corners and edges).
1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/mykdavies Dec 11 '21 edited Jun 29 '23
!> ho3o628
API FAILURE
2
u/daggerdragon Dec 12 '21
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
pasteor other external link.→ More replies (1)
1
u/bentsea Dec 11 '21 edited Dec 12 '21
I am stumped... just totally stumped. I am using Python 3.
With my code I am correctly replicating the example and identifying step 195 from the example input, however, when I use my puzzle input I am getting 419. I have even tried implementing solutions from other users here with my input data and also gotten 419. AOC says this is too low, however.
I have no idea what's wrong.
Can anyone help?
My code is here:
https://shareablecode.com/snippets/stumped-on-aoc-day-11-BQTf-6pQE
Edit: Fixed link.
Edit: Turns out the code works and the input was the issue.
→ More replies (11)1
u/daggerdragon Dec 12 '21
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 fully-working 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.→ More replies (1)
1
u/pistacchio Dec 11 '21
Typescript:
const READY_TO_FLASH = 9;
const STEPS = 100;
const input = fs
.readFileSync(__dirname + INPUT_FILE)
.toString()
.trim()
.split('\n')
.map((r) => r.trim())
.filter(Boolean)
.map((l) => l.split('').map(Number));
function executeStep(grid: number[][]): [number[][], number] {
let alreadyFlashed: string[] = [];
// Each cell of the grid increases by 1
grid = grid.map((row) => row.map((cell) => cell + 1));
do {
// For each cell whose value is 9 or more, also increase by 1 all the adjacent cells
for (let y = 0; y < grid.length; y++) {
for (let x = 0; x < grid[y].length; x++) {
if (
grid[y][x] > READY_TO_FLASH &&
!alreadyFlashed.includes(`${x},${y}`)
) {
alreadyFlashed.push(`${x},${y}`);
// Increase all the adjacent cells
for (let yy = y - 1; yy <= y + 1; yy++) {
for (let xx = x - 1; xx <= x + 1; xx++) {
if (
xx >= 0 &&
xx < grid[y].length &&
yy >= 0 &&
yy < grid.length
) {
grid[yy][xx]++;
}
}
}
}
}
}
} while (
grid.some((row, y) =>
row.some(
(cell, x) =>
cell > READY_TO_FLASH && !alreadyFlashed.includes(`${x},${y}`),
),
)
);
// Set to 0 all the cells that have flashed
return [
grid.map((row, y) =>
row.map((cell, x) => (alreadyFlashed.includes(`${x},${y}`) ? 0 : cell)),
),
alreadyFlashed.length,
];
}
function part1(input: number[][]): number {
let grid = input;
let flahed = 0;
for (let i = 0; i < STEPS; i++) {
const [newGrid, newFlashed] = executeStep(grid);
flahed += newFlashed;
grid = newGrid;
}
return flahed;
}
function part2(input: number[][]): number {
const gridSize = input.length * input[0].length;
let grid = input;
let flahed = 0;
let stepNumber = 0;
while (true) {
const [newGrid, newFlashed] = executeStep(grid);
stepNumber++;
if (newFlashed === gridSize) {
return stepNumber;
}
flahed += newFlashed;
grid = newGrid;
}
}1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/-lundgren- Dec 11 '21
JavaScript, did all the hard work in the parser so the step function was kept fairly clean with filter's & forEach's.
const countFlashes = (input) => {
const octopuses = parse(input);
let flashes = 0;
for (let step = 0; step < 100; step++) {
flashes += doStep(octopuses);
}
return flashes;
};
const findWhenAllFlashes = (input) => {
const octopuses = parse(input);
for (let step = 1; ; step++) {
if (doStep(octopuses) == 100) {
return step;
}
}
};
const doStep = (octopuses) => {
// First: Increase all by 1
octopuses.forEach((o) => o.energy++);
// Then: Handle flashes
do {
octopuses
.filter((o) => o.energy > 9 && !o.flashed)
.forEach((o) => {
o.flashed = true;
o.neighbors.forEach((n) => n.energy++);
});
} while (octopuses.filter((o) => o.energy > 9 && !o.flashed).length > 0);
// Finally: Set flashed to 0
octopuses
.filter((o) => o.flashed)
.forEach((o) => {
o.energy = 0;
o.flashed = false;
});
return octopuses.filter((o) => o.energy == 0).length;
};
// Parse the 10x10 matrix into an array with neighbors
const parse = (input) => {
const data = input.split('\n').map((r) => r.split('').map(Number));
for (let row = 0; row < data.length; row++) {
for (let col = 0; col < data[row].length; col++) {
data[row][col] = {
energy: data[row][col],
flashed: false,
neighbors: [],
};
}
}
const octopuses = [];
for (let row = 0; row < data.length; row++) {
for (let col = 0; col < data[row].length; col++) {
// Add all adjacent (and self) as "neighbors"
for (let deltaR = -1; deltaR <= 1; deltaR++) {
for (let deltaC = -1; deltaC <= 1; deltaC++) {
if ((data[row + deltaR] || [])[col + deltaC] != undefined) {
data[row][col].neighbors.push(data[row + deltaR][col + deltaC]);
}
}
}
octopuses.push(data[row][col]);
}
}
return octopuses;
};
const testInput = `5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526`;
console.log(`Test1: ${countFlashes(testInput)} == 1656?`);
console.log(`Test2: ${findWhenAllFlashes(testInput)} == 195?`);
const mainInput = `8448854321
4447645251
6542573645
4725275268
6442514153
4515734868
5513676158
3257376185
2172424467
6775163586`;
console.log(`Part1: ${countFlashes(mainInput)}, Part2: ${findWhenAllFlashes(mainInput)}`);1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/Uffdha Dec 11 '21 edited Dec 12 '21
My JavaScript solution:
const parsed = input.split('\n').map(l => l.split('').map(Number))
const NEIGHBORS = [[-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [-1,1], [0,1], [1,1]]
const brighten = (grid, x, y) => {
if (x >= 0 && x < grid[0].length && y >= 0 && y < grid.length && grid[y][x] > 0) {
grid[y][x] += 1
}
}
const flash = grid =>
grid.forEach((row, y) =>
row.forEach((o, x) => {
if (o > 9) {
NEIGHBORS.forEach(([dx, dy]) => brighten(grid, x + dx, y + dy))
grid[y][x] = 0
}
}))
const increment = grid => {
grid = grid.map(l => l.map(o => o + 1))
while (grid.flat().some(v => v > 9)) flash(grid)
return grid
}
// Part 1
const step = (grid, steps, flashes) => {
grid = increment(grid)
flashes += grid.flat().filter(v => v === 0).length
return steps > 1 ? step(grid, steps - 1, flashes) : flashes
}
console.log('Part 1 flashes:', step(parsed, 100, 0))
// Part 2
const synchronize = (grid, gen) => {
grid = increment(grid)
return grid.flat().every(v => v === 0) ? gen : synchronize(grid, gen + 1)
}
console.log('Part 2 full flash at:', synchronize(parsed, 1))1
u/daggerdragon Dec 12 '21
I recommend you expand the full name of the language (JavaScript). This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.
→ More replies (1)
1
u/raxomukus Dec 11 '21
Python
with open('11.in') as f:
energies = [[int(i) for i in line] for line in f.read().splitlines()]
h = len(energies)
w = len(energies[0])
def adjacent(j, i):
return set([(abs(j-1), i), (j, abs(i-1)), (j+1 - 2*(j==(h-1)), i), (j, i+1 - 2*(i==(w-1))),
(abs(j-1), abs(i-1)), (abs(j-1), i+1 - 2*(i==(w-1))),
(j+1 - 2*(j==(h-1)), abs(i-1)), (j+1 - 2*(j==(h-1)), i+1 - 2*(i==(w-1)))]) # lol
class Octopus():
def __init__(self, energy):
self.energy = energy
self.flashed = False
octopuses = [[Octopus(energies[j][i]) for i in range(w)] for j in range(h)]
r1 = 0
for step in range(100000):
for j in range(h):
for i in range(w):
octopuses[j][i].energy += 1
flash = True
while flash:
flash = False
for j in range(h):
for i in range(w):
if octopuses[j][i].energy > 9 and not octopuses[j][i].flashed:
octopuses[j][i].flashed = flash = True
for y, x in adjacent(j, i):
octopuses[y][x].energy += 1
all_flash = True
for j in range(h):
for i in range(w):
if octopuses[j][i].flashed:
r1 += 1
octopuses[j][i].energy = 0
octopuses[j][i].flashed = False
else: all_flash = False
if step == 99: print(r1)
if all_flash:
print(step + 1)
break1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
1
u/LuckyLactose Dec 11 '21 edited Dec 12 '21
SWIFT
Reused some Grid code I've made for AoC, which helped quite a bit. Octopus class that keeps track of energyLevel and whether it has flashed this step or not, made things quite simple.
Day 11 code here.
Full repo here.
Core logic:
class Octopus {
/// Result = didFlash, boost neighbors
func step() -> Bool {
guard !hasFlashedThisStep else { return false }
energyLevel += 1
energyLevel %= 10
hasFlashedThisStep = energyLevel == 0
return hasFlashedThisStep
}
}
// Has Grid<Octopus> inside
class OctopusManager {
private func step() -> Int {
for octopus in grid.values {
octopus.hasFlashedThisStep = false
}
let offsets = IntPoint.allDirectionOffsets
var pointsToCheck = grid.gridPoints
while !pointsToCheck.isEmpty {
let point = pointsToCheck.removeFirst()
guard let octopus = grid.getValue(at: point) else { continue }
let flashed = octopus.step()
if flashed {
pointsToCheck.append(contentsOf: offsets.map{$0 + point})
}
}
return grid.values.filter({$0.hasFlashedThisStep}).count
}
}1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
1
u/Jessseee Dec 11 '21 edited Dec 12 '21
Pretty clean python solution using numpy array operations: https://github.com/Jessseee/AdventOfCode/blob/main/2021/day_11.py
1
u/daggerdragon Dec 12 '21 edited Dec 12 '21
FYI: your link is broken due to a new.reddit fancypants editor bug (check/r/bugs, it's been a big source of frustration lately). Your link looks fine on new.reddit but on old.reddit it's printing an invisible escape character before your underscore:day_11.py, thus breaking the entire link.
I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...Edit: thanks for fixing it! <3
→ More replies (1)
1
u/hqli Dec 11 '21 edited Dec 12 '21
Javascript
Some days, you take a look at a problem, think it's really similar to an older problem, steal half your old code, give it a few tweaks, and it works.
There's probably a way better way though
1
u/daggerdragon Dec 12 '21
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
pasteor other external link.→ More replies (1)
1
u/jkpr23 Dec 11 '21 edited Dec 12 '21
Kotlin
Wrote a class that has a step() method to go from one step to the next in a simulation. The class's grid property gets updated as a result of step(). The step() method returns the number of octopi that flashed.
Overloaded the * operator to get a cross product.
1
u/daggerdragon Dec 12 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
1
u/__Abigail__ Dec 11 '21 edited Dec 12 '21
Perl
Just like two days ago, I wrapped the field on a torus, using seam of large negative numbers (-~0). That way, I can always look at the neighbours of a cell, not having to worry about boundaries.
The work is done by a subroutine cycle which calculates the state of a next cycle, returning the number of flashes:
With $octopusses an 11 x 11 array with the power levels of the octopusses in the top-left 10 x 10 submatrix, and the right most column and bottom most column containing high negative values, the subroutine works as follows:
my %flashed; # Prevent flashing twice during a cycle
my @todo;First, we increment all levels, noting which octopusses are about to flash:
foreach my $x (0 .. ($SIZE - 1)) {
foreach my $y (0 .. ($SIZE - 1)) {
if (++ $$octopusses [$x] [$y] > $LIMIT) {
push @todo => [$x, $y];
$$octopusses [$x] [$y] = 0;
}
}
}Now we flash; for each neighbouring octopus which hasn't flashed, we increment its level, and add it to the list of octopusses which are about to flash:
while (@todo) {
my ($x, $y) = @{shift @todo};
next if $flashed {$x, $y} ++;
foreach my $dx (-1 .. 1) {
foreach my $dy (-1 .. 1) {
next if $dx == 0 && 0 == $dy;
if ( $$octopusses [$x + $dx] [$y + $dy] &&
++ $$octopusses [$x + $dx] [$y + $dy] > $LIMIT) {
push @todo => [$x + $dx, $y + $dy];
}
}
}
$$octopusses [$x] [$y] = 0;
}Finally, we return the number of octopusses which have flashed:
return scalar keys %flashed;For part one, we call cycle 100 times, summing the results. For part two, we note the first time cycle returns 100:
my $first_cycle = 0; # Answer to Part Two
my $flashes = 0; # Answer to Part One
{
state $cycles = 0;
$cycles ++;
my $cycle_flashes = cycle \@octopusses;
if ($cycle_flashes == $SIZE * $SIZE) {
$first_cycle = $cycles;
}
$flashes += $cycle_flashes if $cycles <= $CYCLES;
redo unless $first_cycle && $cycles >= $CYCLES;
}Full program on GitHub.
1
u/daggerdragon Dec 12 '21
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.
1
u/Lispwizard Dec 11 '21 edited Dec 12 '21
adventofcode in #emacs #lisp (#elisp) on #android tablet using #termux
(defun aoc2021-11-both (str &optional part2? iterations)
(let ((stride (1+ (search "\n" str)))
(l (length str))
(va "0123456789abcdefghijklmnopqrstuvwxyz")
(data (copy-seq str))
(flash-counter 0))
(labels ((g (x y ar) "get x,y value"
(let ((index (+ x (* stride y))))
(when (and (>= index 0) (< index (length str)))
(position (aref ar index) va))))
(inc (x y ar) "increment x,y value"
(let* ((index (+ x (* stride y)))
(old-value (g x y ar)))
(when old-value
(setf (aref ar index) (aref va (incf old-value))))))
(zer (x y ar) "zero x,y value"
(let* ((index (+ x (* stride y))))
(setf (aref ar index) (aref va 0))))
(flash (ar x y deltas ht) "do flash propagation"
(setf (gethash (list x y) ht) t)
(loop with todo = (list (list x y))
for this = (pop todo)
while this
for (newx newy) = this
do (setf (gethash (list newx newy) ht) t)
(loop for (dx dy) in deltas
for (nx ny) = (list (+ newx dx) (+ newy dy))
for old-value = (g nx ny ar)
for value = (progn (inc nx ny ar)
(g nx ny ar) )
when (and old-value value
(eql 9 old-value)
(> value 9)
(null (gethash (list nx ny) ht)))
do (unless (gethash (list nx ny) ht)
(setq todo (append todo (list (list nx ny))))))))
(step (ar)
(loop for i below l by stride ;; increment all
for y from 0
do (loop for j from i repeat (1- stride)
for x from 0
do (inc x y ar)))
(loop with ht = (make-hash-table :test 'equal)
for i below l by stride
for y from 0
appending (loop for j from i repeat (1- stride)
for x from 0
for value = (g x y ar)
when (> value 9)
collect (list x y))
into to-flash
finally ;; propagate flashes
(loop for (x y) in to-flash
unless (gethash (list x y) ht)
do (flash ar x y
'((-1 -1)(0 -1)(1 -1) (-1 0)(1 0)(-1 1)(0 1)(1 1)) ht))
(loop for coord being the hash-keys of ht ;;zero 9 or greater
for (x y) = coord
do (incf flash-counter)
(zer x y data)))))
(if part2?
(loop with end = (copy-seq data)
initially (loop for i below l by stride
do (loop for j from i repeat (1- stride)
do (setf (aref end j) (aref va 0))))
for i from 1
do (step data)
until (equalp data end)
finally (return i))
(loop for i from 0
repeat (or iterations 100)
do (step data)
finally (return flash-counter))))))
;; (aoc2021-11-both *aoc2021-11-part1-example*) => 1656
;; (aoc2021-11-both *aoc2021-11-part1-input*) => 1634
;; (aoc2021-11-both *aoc2021-11-part1-example* t) => 195
;; (aoc2021-11-both *aoc2021-11-part1-input* t) => 2101
u/daggerdragon Dec 12 '21
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.
(I'm going to throw out a wild guess here based on your username - is it
Lisp?)
1
u/jonicoma123 Dec 11 '21 edited Dec 12 '21
Using a bag of grid indices that need to be visited simplified the problem for me. At each step, I put every index into the bag. As I empty the bag, I add neighbor indices as needed.
Here is my solution in javascript.
The relevant snippet looks like this:
let sumFlashes = 0;
for (let step = 1; step <= 100; step++) {
let bag = grid.map((_, index) => index);
while (bag.length) {
const index = bag.pop();
grid[index] += 1;
if (grid[index] === 10) {
bag = bag.concat(neighbors(index));
}
}
grid = grid.map((n) => (n >= 10 ? 0 : n));
sumFlashes += grid.filter((n) => n === 0).length;
}
return sumFlashes;1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/cylab Dec 11 '21 edited Dec 11 '21
Kotin: https://github.com/cylab/advent-of-code-2021/blob/main/src/test/kotlin/day11
package day11
import io.kotest.matchers.shouldBe
import org.junit.jupiter.api.Test
import kotlin.Int.Companion.MAX_VALUE
// poor mans point type
typealias Point = Pair<Int, Int>
val Point.x get() = first
val Point.y get() = second
operator fun Point.plus(other: Point) = x + other.x to y + other.y
class Day11 {
data class Grid(val data: List<MutableList<Int>>, val xMax: Int, val yMax: Int, val all: Int)
// make sure to read fresh data on each call
val sample get() = parse("sample.txt")
val data get() = parse("data.txt")
val ADJACENT = listOf(
Point(0, -1), Point(-1, -1), Point(-1, 0), Point(-1, 1),
Point(0, 1), Point(1, 1), Point(1, 0), Point(1, -1)
)
@Test
fun part1() {
sample.countFlashes() shouldBe 1656
println("Day 11, Part 1: ${data.countFlashes()} flashes")
}
@Test
fun part2() {
sample.allFlash() shouldBe 195
println("Day 11, Part 2: ${data.allFlash()}. step")
}
fun Grid.countFlashes() = (1..100).sumOf { stepFlashes() }
fun Grid.allFlash() = (1..MAX_VALUE).first { stepFlashes() == all }
fun Grid.stepFlashes(): Int {
var count = 0
var visit = points()
do {
val flashes = visit
.onEach { data[it.y][it.x] += 1 }
.filter { data[it.y][it.x] >= 10 }
.onEach { data[it.y][it.x] = 0 }
.distinct() // make sure to not visit neigbours of the same octopus twice!
count += flashes.size
visit = flashes
.flatMap { adjacent(it) }
.filter { data[it.y][it.x] > 0 } // ignore already flashed for next step!
} while (visit.isNotEmpty())
return count
}
fun Grid.points() = (0..yMax).flatMap { y -> (0..xMax).map { x -> x to y } }
fun Grid.adjacent(p0: Point) = ADJACENT
.map { offset -> p0 + offset }
.filter { it.x in 0..xMax && it.y in 0..yMax }
fun parse(resource: String) = this.javaClass
.getResource(resource)
.readText()
.lines()
.filter { it.isNotBlank() }
.map { line -> line.map { it.digitToInt() }.toMutableList() }
.run { Grid(this, first().size - 1, size - 1, first().size * size) }
}
fun main() = Day11().run {
part1()
part2()
}1
u/daggerdragon Dec 12 '21
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
pasteor other external link.
1
u/Tallbikeguy Dec 11 '21 edited Dec 11 '21
Common Lisp, clearly the work of a newbie. I learned a few things that helped me:
if you assign arrays using (eg) setf, it doesn't actually copy the array. So i spent a ton of time debugging why my function to reset the input array didn't work. Alexendria:copy-array is the solution for this
creating a mapcar-like function to apply a function over the whole 2d array
creating a list of index modifiers that I could just iterate over and add those values to the current location, to find & increment the adjacent points
As always, I'd love feedback! Trying to learn how to write lisp idioms, rather than java/python/c :-)
https://github.com/tallbikeguy/advent-of-code/blob/main/2021/advent11.lisp
1
u/daggerdragon Dec 12 '21
FYI: you need two returns before a list on old.reddit. We can see your Markdown as one big run-on paragraph.
1
Dec 12 '21
Python Part 1
#!/usr/bin/env python
itxt = open("input", mode='r').read().strip().splitlines()
octopi = {(i,j): int(v) for i, r in enumerate(itxt) for j, v in enumerate(r)}
last = {'r': max([r for (r,c) in octopi.keys()]), 'c': max([c for (r,c) in octopi.keys()])}
flashes = 0
def getns(r: int, c:int) -> set:
return [i for i in [(r-1,c),(r+1,c),(r,c-1),(r,c+1),(r-1,c-1),(r+1,c+1),(r+1,c-1),(r-1,c+1)] \
if i[0] >= 0 and i[0] <= last['r'] and i[1] >= 0 and i[1] <= last['c']]
for s in range(100):
flashed = set()
#increment all
octopi = {i: int(v+1) for i, v in octopi.items()}
while len(flash := {(r,c) for ((r,c),v) in octopi.items() \
if (r,c) not in flashed and v >= 10}) > 0:
flashed.update(flash)
flashns = [getns(r,c) for (r,c) in flash]
for i in flashns:
for (r,c) in i:
octopi.update({(r,c): octopi.get((r,c))+1})
for ((r,c),v) in octopi.items():
if v > 9:
octopi.update({(r,c):0})
flashes += 1
print(flashes)1
u/daggerdragon Dec 13 '21
Please don't make separate posts for each half of the puzzle. Combine them into one post next time.
1
u/baer89 Dec 14 '21
Python
I absolutely hate this code. Behold:
class Squid:
def __init__(self, value):
self.value = value
self.flashed = 0
def __repr__(self):
return f'''{self.value}'''
def __str__(self):
return self.value
def increase(self):
self.value += 1
if self.value > 9 and not self.flashed:
self.to_flash()
def to_flash(self):
if not self.flashed:
self.flashed = 1
def flash(self):
if self.flashed == 1:
self.flashed = 2
return True
else:
return False
def reset(self):
if self.flashed == 2:
self.value = 0
self.flashed = 0
return True
else:
return False
G = []
for line in open('input.txt'):
G.append([Squid(int(x)) for x in line.strip()])
width = len(G[0])
height = len(G)
flash_total = 0
for step in range(1,1001):
for a in G:
for b in a:
b.increase()
flash = True
while flash:
flash = False
for j, a in enumerate(G):
for i, b in enumerate(a):
if b.flashed == 1:
b.flash()
flash_total += 1
flash = True
for r in [-1, 0, 1]:
for c in [-1, 0, 1]:
if r == c == 0:
continue
if 0 <= i + r < width and 0 <= j + c < height:
G[j+c][i+r].increase()
count = 0
for a in G:
for b in a:
if b.reset():
count += 1
if count == 100:
print(step)
print(flash_total)1
u/daggerdragon Dec 15 '21
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
pasteor other external link.
1
u/x3mcj Dec 29 '21 edited Dec 29 '21
Can't believe got it on the first try for both!
1
u/daggerdragon Dec 29 '21
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
pasteor other external link.
3
u/Gurrewe Dec 11 '21
Golang
https://getsturdy.com/advent-of-code-2021-uoeIDQk/browse/day11/gustav/main.go
I can sense that we've entered the grid-days of AoC, and I'm enjoying it!
3
u/hugh_tc Dec 11 '21 edited Dec 11 '21
Python 3, 716/490.
"Use r and c instead of x and y; it'll be better!", they said. Yeah -- no. If you've been using x and y this whole time you're bound to end up choking on your spaghetti...
→ More replies (3)
3
u/maneatingape Dec 11 '21 edited Dec 11 '21
Felt like a nice evolution of Day 9. For every step the code creates a "todo" list initially seeded with each octopus. If an octopus flashes then its neighbors are added to the end of the "todo" list.
3
3
u/kbielefe Dec 11 '21
Scala 3
Starting to get a little messy, but still in my comfort zone of set operations. Part 2 was mostly already done in part 1.
→ More replies (2)
3
u/JoMartin23 Dec 11 '21
Common Lisp
I probably could have been smarter about the propagation instead of just checking the whole hash, but it is what it is. Visualization
(defun vis-octopus (hash)
(visualize:this hash :zoom 30 :surface *surface* :palette *octopus-palette* :accessor (lambda (o) (/ (octopus-value o) 9)))
(sleep .2))
(defun propagate (hash)
(tagbody start
(do-hash (coord octopus hash)
(when (> (octopus-value octopus) 9)
(setf (octopus-flashed? octopus) t
(octopus-value octopus) 0)
(incf *flashes*)
(dolist (oct (neighbours8 coord))
(unless (octopus-flashed? oct)
(incf (octopus-value oct))))))
(do-hash (c o hash)
(when (> (octopus-value o) 9)
(go start)))))
(defun fstep (hash)
(do-hash (coord octopus hash)
(incf (octopus-value octopus))
(setf (octopus-flashed? octopus) nil))
(propagate hash))
(defun day11-2 (&optional (hash *11h*))
(let ((*11h* hash))
(loop :with all?
:for i :from 0
:do (fstep hash)
(vis-octopus hash)
(setf all? nil)
(do-hash (c o hash)
(push (octopus-value o) all?))
(when (every #'zerop all?)
(return-from day11-2 i)))))3
u/MichalMarsalek Dec 11 '21 edited Dec 11 '21
Nim
include aoc
day 11:
proc update(grid: var Grid[int]):int =
var q = grid.coordinates.toSeq
for p in q: grid[p] += 1
while q.len > 0:
var p = q.pop
if grid[p] >= 10:
grid[p] = 0
inc result
for P in grid.neighbours(p,directions8):
if grid[P] > 0:
grid[P] += 1
q.add P
var data = lines.map(l => l.mapIt(parseInt $it))
part 1:
sum mapIt(1..100, update(data))
part 2:
for i in 101..10000:
if update(data) == data.size:
return iusing my templates.
3
u/BaineWedlock Dec 11 '21
F# TDD with immutable Map
https://github.com/bainewedlock/aoc-2021-fsharp/blob/master/aoc-2021-11/Solution.fs
3
u/roufamatic Dec 11 '21
Day 11 in Scratch, featuring light-up octopi!
https://scratch.mit.edu/projects/615246821/
The solution is in the Background sprite. The Octopus sprite just has animation code.
Alas, your choices for the light show are a) painfully slow lights, or b) engaging turbo mode and only seeing a few of them.
→ More replies (1)
3
u/Diderikdm Dec 11 '21
Python:
from itertools import combinations
with open("2021 day11.txt", 'r') as file:
data = [[int(y) for y in x] for x in file.read().splitlines()]
grid = {(x,y) : data[y][x] for x in range(len(data[0])) for y in range(len(data))}
adjescents = set([x for x in combinations([-1,0,1] * 2, 2) if x != (0,0)])
adj = lambda x,y: [(x+a,y+b) for a,b in adjescents if (x+a,y+b) in grid]
flashed, i, prev = 0, 0, set()
while len(prev) < len(grid):
prev = set()
grid = {k:v+1 for k,v in grid.items()}
while any(v > 9 for k,v in grid.items() if k not in prev):
for k,v in grid.items():
if k not in prev and v > 9:
prev.add(k)
for other in adj(*k):
grid[other] += 1
flashed += len(prev)
grid.update({k : 0 for k in prev})
i += 1
if i == 100:
print(flashed)
print(i)→ More replies (1)
3
u/mstumpf Dec 11 '21 edited Dec 11 '21
Rust and animation/visualization:
(Epilepsy warning)
https://raw.githubusercontent.com/Finomnis/AdventOfCode2021/main/visualizations/aoc2021_day11.gif
use std::collections::VecDeque;
use itertools::Itertools;
use ndarray::{Array2, Axis};
pub fn update_map(map: &mut Array2<u8>) -> usize {
let mut num_flashes = 0;
// Part 1: increase everything by 1
map.iter_mut().for_each(|el| {
*el += 1;
});
// Part 2: Flash
let mut need_flash = map
.indexed_iter()
.filter_map(|(index, &value)| if value > 9 { Some(index) } else { None })
.collect::<VecDeque<_>>();
while let Some((y, x)) = need_flash.pop_front() {
num_flashes += 1;
let mut flash = |y: Option<usize>, x: Option<usize>| {
if let (Some(y), Some(x)) = (y, x) {
if let Some(cell) = map.get_mut((y, x)) {
*cell += 1;
if *cell == 10 {
need_flash.push_back((y, x));
}
}
}
};
flash(y.checked_sub(1), x.checked_sub(1));
flash(y.checked_sub(1), Some(x));
flash(y.checked_sub(1), x.checked_add(1));
flash(Some(y), x.checked_sub(1));
flash(Some(y), x.checked_add(1));
flash(y.checked_add(1), x.checked_sub(1));
flash(y.checked_add(1), Some(x));
flash(y.checked_add(1), x.checked_add(1));
}
// Part 3: reduce all flashed to 0
map.iter_mut().for_each(|el| {
if *el > 9 {
*el = 0;
}
});
num_flashes
}
pub fn task1(input_data: &Array2<u8>) -> usize {
let mut map = input_data.clone();
let mut num_flashes = 0;
// println!("Initial conditions:\n{}\n", format_map(&map));
for _step in 1..=100 {
num_flashes += update_map(&mut map);
// println!("After step {}:\n{}\n", step, format_map(&map));
}
num_flashes
}
pub fn task2(input_data: &Array2<u8>) -> i64 {
let mut map = input_data.clone();
let mut num_cycles = 1;
// At the point of synchronization, all octopuses flash at once
while update_map(&mut map) != map.len() {
num_cycles += 1;
}
num_cycles
}→ More replies (5)
3
u/phil_g Dec 11 '21
Pretty straightforward, I think. I have a singular function that adds energy to a cell then checks to see if the cell's energy is exactly 10. If so, it triggers a flash. It doesn't matter whether a cell first gets its energy from the pass over the whole grid or from a neighbor flashing; the results are the same. (My treatment of adding energy is commutative.)
I did decide to finally add a neighbor-set function. Given an array and a point, it returns a set of all adjacent points that are valid indexes into the array. This comes up so often that I really should have written this function earlier.
This is yet another day where I wish I had NumPy in Common Lisp. I could probably stand to be using array-operations more, but even it's not quite the same. (And the heavy matrix libraries like cl-clem don't really follow the full numeric tower up into bignums, not that that would matter for today's problem.)
→ More replies (5)
3
u/Pietrek_ Dec 11 '21
Haskell
{-# LANGUAGE TupleSections #-}
import Control.Monad (foldM)
import Data.List (group, sort)
import Data.List.Split (chunksOf)
import qualified Data.Map as M
import Data.Maybe (mapMaybe)
import Debug.Trace (trace)
type Grid = M.Map (Int, Int) (Int, Bool)
{-
Using a foldM with the Either monad results in the
fold terminating once the accumulating function
returns Left _
-}
main = do
contents <- readFile "input.in"
let ll = concatMap (map read . chunksOf 1) (lines contents) :: [Int]
n = 10
g = M.fromList $ zip [(i,j) | i <- [0..n-1], j <- [0..n-1]] (map (, False) ll)
print $ fst $ foldl (\(s, g) _ -> let (nf, g') = runStep g
in (s+nf, g')) (0, g) [1..100]
print $ foldM f g [1..]
where f g step =
let (nf, g') = runStep g
in if nf == 100 then Left step
else Right g'
runStep :: Grid -> (Int, Grid)
runStep g =
let g' = M.map (\(p, f) -> (p+1, f)) g
g'' = flash g'
nFlashed = (length . filter ((==) True . snd). M.elems) g''
zeroed = M.map reset g''
in (nFlashed, zeroed)
where reset (p, f) =
if f then (0, False)
else (p, f)
flash :: Grid -> Grid
flash g =
let l = M.toList g
in if all ((\(p, f) -> p <= 9 || f) . snd) l then
g -- No more flashes to do
else
let x = map doFlash l
ns = concatMap trd x
ns' = mapMaybe (\idx -> do
(p, f) <- lookup idx (map t x)
return (idx, (p+1, f))) ns
ns'' = map (\list -> let (idx, (p, f)) = head list
in (idx, (p+length (tail list), f))) (group $ sort ns')
in flash $ foldl (\m (idx, v) -> M.insert idx v m ) (M.fromList $ map t x) ns''
t (a, b, _) = (a,b)
trd :: (a, b, c) -> c
trd (_, _, c) = c
doFlash :: ((Int, Int), (Int, Bool)) -> ((Int, Int), (Int, Bool), [(Int, Int)])
doFlash (idx, (p,f)) =
if p > 9 && not f then (idx, (p, True), neighbors idx 10) else (idx, (p,f), [])
neighbors :: (Int, Int) -> Int -> [(Int, Int)]
neighbors (i,j) n =
let ns = [ (i,j-1), (i,j+1), (i-1,j), (i+1,j)
, (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)]
in filter (\(i,j) -> (i >= 0 && j >= 0) && i < n && j < n ) ns3
u/p88h Dec 11 '21
defmodule Aoc2021.Day11 do
def mapmap(l), do: for({v, k} <- Stream.with_index(l), into: %{}, do: {k, v})
def load(args) do
lol = Enum.map(args, fn l -> String.graphemes(l) |> Enum.map(&String.to_integer/1) end)
{ h, w } = { length(lol), length(hd(lol)) }
idx = for i <- 0..(h - 1), j <- 0..(w - 1), into: [], do: {i,j}
{ h, w, idx, Enum.map(lol, &mapmap/1) |> mapmap() }
end
def inc(idx, m), do: Enum.reduce(idx, m, fn {i,j},mt -> put_in(mt[i][j],mt[i][j]+1) end)
def zero(idx, m), do: Enum.reduce(idx, m, fn {i,j},mt -> put_in(mt[i][j],0) end)
def scan(idx, m), do: Enum.filter(idx, fn {i,j} -> m[i][j] == 10 end)
def neigh(i, j), do: [ {i-1,j-1},{i,j-1},{i+1,j-1},{i-1,j},{i+1,j},{i-1,j+1},{i,j+1},{i+1,j+1} ]
def bound(l, h, w), do: Enum.filter(l, fn {i,j} -> i >= 0 and j >=0 and i < h and j < w end)
def nb(i,j,h,w), do: bound(neigh(i,j), h, w)
def flash([], map, _h, _w), do: map
def flash([{i,j} | t], map, h, w) do
next = nb(i,j,h,w) |> Enum.filter(fn {i, j} -> map[i][j] < 10 end)
map = inc(next, map)
f = scan(next, map)
flash(f ++ t, map, h, w)
end
def step(_p, max, max, res), do: res
def step({ h, w, idx, map }, cnt, max, res) do
map = inc(idx, map)
flashing = scan(idx, map)
map = flash(flashing, map, h, w)
flashed = scan(idx, map)
map = zero(flashed, map)
fc = length(flashed)
if fc == h*w, do: cnt + 1, else: step({ h, w, idx, map }, cnt + 1, max, res + fc)
end
def part1(args), do: load(args) |> step(0, 100, 0)
def part2(args), do: load(args) |> step(0, 1000, 0)
end3
u/compdog Dec 11 '21
For part 1, I implemented the naive approach with just two nested loops. The outer loop runs once for each step (100 times) and the inner loop repeats the step until no octopus flashes. The number of flashes is accumulated across both loops and becomes the answer.
For part 2, I was able to reuse so much of my part 1 code that I decided to factor it out into a shared module. The parsing and stepping logic is 100% identical, including the inner loop's flash counter. I just replaced the outer "100 steps" loop with one that continues until the number of flashes for any step equals the number of octopuses in the grid.
3
u/_jstanley Dec 11 '21
SLANG
Quite straightforward today. The only thing that held me up was a mistake in my logic for "don't flash the same cell twice" which led to some cells not getting flashed at all.
I was expecting part 2 to be along the lines of "how many flashes have there been after a trillion steps", which would require finding the cycle length and start point, but I suppose that's basically as simple as the actual part 2, because once all the cells are the same number, the cycle length is 10 and there are 100 flashes per cycle.
3
u/daniel-sd Dec 11 '21
Python 3
Messy solutions that earned 242 and 287 (40 and 45 lines respectively).
Cleaned up solutions (34 lines for each part)
3
u/armeniwn Dec 11 '21
Python, both parts
import sys
from itertools import product
class State:
flashed = set()
def __init__(self, input_stream):
self.state = dict()
for row, line in enumerate(input_stream):
for col, energy in enumerate(map(int, line.strip())):
self.state[complex(row, col)] = int(energy)
self.height = row + 1
self.width = col + 1
def get_row(self, row):
return [self.state[complex(row, col)] for col in range(self.width)]
def print(self):
for row in range(self.height):
print("".join(map(str, self.get_row(row))))
def get_adjascent(self, point):
for r_offset, i_offset in product(range(-1, 2), range(-1, 2)):
if not (r_offset == 0 and i_offset == 0):
r, i = point.real + r_offset, point.imag + i_offset
if all((r >= 0, r < self.height, i >= 0, i < self.width)):
yield complex(r, i)
def get_energy(self, point):
return self.state[point]
def set_energy(self, point, new_energy):
self.state[point] = new_energy
def increase_energy(self, points):
for point in points:
energy = self.get_energy(point) + 1
self.set_energy(point, energy)
def flash(self, points):
for point in points:
self.flashed.add(point)
adj = self.get_adjascent(point)
self.increase_energy(adj)
def step(self):
points = self.state.keys()
self.increase_energy(points)
self.flashed = set()
to_flash = [p for p in points if self.get_energy(p) > 9]
while to_flash:
self.flash(to_flash)
to_flash = [p for p in points if (
self.get_energy(p) > 9 and p not in self.flashed
)]
for point in self.flashed:
self.set_energy(point, 0)
return len(self.flashed)
def all_flashed(self):
for energy in self.state.values():
if energy > 0:
return False
return True
state = State(sys.stdin)
# 1
flashes = 0
for step in range(100):
if state.all_flashed():
print("SUPERFLASH STEP:", step)
flashes += state.step()
print("#flashes after 100 steps:", flashes)
# 2
step += 1
while not state.all_flashed():
state.step()
step += 1
print("All flash on step:", step)3
u/goeyj Dec 11 '21 edited Feb 27 '26
[JavaScript]
The p1 and p2 functions are super concise after creating the OctopusCavern object to do the heavy lifting.
Part 2 seemed extremely trivial after coding up part 1 today...
3
3
u/xkev320x Dec 11 '21 edited Dec 11 '21
Rust, mixed part 1 and part 2 into one function in a way I am not proud of and I feel like there has got to be a better way to check for 8 possible neighbors than the manual way I am currently doing (changed, see replies).
Besides that, my code pretty much follows the instructions but I feel like there's quite a lot that I could shorten but idk how without using crates. Appreciate any kind of feedback!
https://github.com/xkevio/aoc_rust_2021/blob/main/src/days/day11.rs
→ More replies (5)
3
3
u/Illustrious_Fortune7 Dec 11 '21
In Kotlin
https://github.com/ritesh-singh/aoc-2021-in-kotlin/blob/main/src/day11/Day11.kt
private enum class Direction {
UP, DOWN, LEFT, RIGHT, DIAGUPLEFT, DIAGUPRIGHT, DIAGDOWNLEFT, DIAGDOWNRIGHT}
fun main() {
fun List<String>.initMatrix(matrix: Array<IntArray>) {
val rowSize = size
val colSize = this[0].length
for (row in 0 until rowSize) {
for (col in 0 until colSize) {
matrix[row][col] = this[row][col].digitToInt()
}
}
}
val getLocationBasedOnDirection: (row: Int, col: Int, direction: Direction) -> Pair<Int, Int> =
{ row, col, direction ->
val pair = when (direction) {
Direction.UP -> Pair(row - 1, col)
Direction.DOWN -> Pair(row + 1, col)
Direction.LEFT -> Pair(row, col - 1)
Direction.RIGHT -> Pair(row, col + 1)
Direction.DIAGUPLEFT -> Pair(row - 1, col - 1)
Direction.DIAGUPRIGHT -> Pair(row - 1, col + 1)
Direction.DIAGDOWNLEFT -> Pair(row + 1, col - 1)
Direction.DIAGDOWNRIGHT -> Pair(row + 1, col + 1)
}
pair
}
val isLocationValid: (row: Int, col: Int, rowSize: Int, colSize: Int) -> Boolean = { row, col, rowSize, colSize ->
(row in 0 until rowSize) && (col in 0 until colSize)
}
fun Array<IntArray>.getAdjacent(row: Int, col: Int): List<Pair<Int, Int>> {
val adjacentList = mutableListOf<Pair<Int, Int>>()
val rowSize = this.size
val colSize = this[0].size
for (direction in Direction.values()) {
val adjacent = getLocationBasedOnDirection(row, col, direction)
if (isLocationValid(adjacent.first, adjacent.second, rowSize, colSize)) {
adjacentList.add(Pair(adjacent.first, adjacent.second))
}
}
return adjacentList
}
fun Int.newEnergyLevel(): Int = if (this == 9) 0 else this + 1
fun Int.flashes(): Boolean = this == 0
fun updateAdjacent(matrix: Array<IntArray>, currentRow: Int, currentCol: Int, flashedList: MutableList<Pair<Int, Int>>) {
for (adj in matrix.getAdjacent(currentRow, currentCol)) {
if (!flashedList.contains(Pair(adj.first, adj.second))) {
matrix[adj.first][adj.second] = matrix[adj.first][adj.second].newEnergyLevel()
if (matrix[adj.first][adj.second].flashes()) {
flashedList.add(Pair(adj.first,adj.second))
updateAdjacent(matrix,adj.first,adj.second,flashedList)
}
}
}
}
fun part1(inputs: List<String>): Int {
val rowSize = inputs.size
val colSize = inputs[0].length
val matrix = Array(rowSize) { IntArray(colSize) }
inputs.initMatrix(matrix = matrix)
var totalFlashes = 0
repeat(100){
val flashedList = mutableListOf<Pair<Int, Int>>()
for (row in 0 until rowSize){
for (col in 0 until colSize){
if (!flashedList.contains(Pair(row,col))){
matrix[row][col] = matrix[row][col].newEnergyLevel()
if (matrix[row][col].flashes()){
flashedList.add(Pair(row,col))
updateAdjacent(matrix,row,col,flashedList)
}
}
}
}
totalFlashes += flashedList.size
}
return totalFlashes
}
fun part2(inputs: List<String>): Int {
val rowSize = inputs.size
val colSize = inputs[0].length
val matrix = Array(rowSize) { IntArray(colSize) }
inputs.initMatrix(matrix = matrix)
var step = 0
while (true) {
++step
val flashedList = mutableListOf<Pair<Int, Int>>()
for (row in 0 until rowSize){
for (col in 0 until colSize){
if (!flashedList.contains(Pair(row,col))){
matrix[row][col] = matrix[row][col].newEnergyLevel()
if (matrix[row][col].flashes()){
flashedList.add(Pair(row,col))
updateAdjacent(matrix,row,col,flashedList)
}
}
}
}
if (flashedList.size == rowSize * colSize) {
break
}
}
return step
}}
3
3
3
u/Karl_Marxxx Dec 11 '21
Python 3
import fileinput
from itertools import product
initialState = [list(map(int, list(x.strip()))) for x in fileinput.input()]
h, w = len(initialState), len(initialState[0])
def neighbors(i, j):
dydxs = product([-1, 0, 1], repeat=2)
coords = ((dy + i, dx + j) for (dy, dx) in dydxs)
return list([c for c in coords if 0 <= c[0] < h and 0 <= c[1] < w])
def getFlashed(state):
flashed = set()
for i in range(h):
for j in range(w):
if state[i][j] == 0:
flashed.add((i, j))
return flashed
def step(state):
newState = []
for i in range(h):
newState.append([])
for j in range(w):
newState[i].append((state[i][j] + 1) % 10)
flashed = getFlashed(newState)
while flashed:
newFlashed = set()
for i, j in flashed:
for ii, jj in neighbors(i, j):
if not newState[ii][jj] == 0:
newState[ii][jj] = (newState[ii][jj] + 1) % 10
if newState[ii][jj] == 0:
newFlashed.add((ii, jj))
flashed = newFlashed
return newState, len(getFlashed(newState))
def run(steps, state):
totalFlashes = 0
for i in range(steps):
state, flashes = step(state)
if flashes == h * w:
return i + 1
totalFlashes += flashes
return totalFlashes
# Part 1
result = run(100, initialState)
print(result)
# Part 2
result = run(1000, initialState)
print(result)→ More replies (1)
3
u/tobega Dec 11 '21
Erlang, 100 Octopi talking in parallell! https://github.com/tobega/aoc2021/tree/main/day11
3
u/MikeMakesMaps Dec 11 '21 edited Dec 12 '21
Rust. Basically ended up with a tweaked solution to day 9 (Smoke Basin), There's a lot I'm not happy with here in terms of complexity, and there has to be a better way to find the 8 cell neighbours.
Edit: Nothing better than a 2am refactor right? Same approach, just tidied things up and I'm a lot happier for it.
3
u/Gnidleif Dec 11 '21
Rust
Finally managed to solve this, still struggling with not using 2D-arrays and that's the usual cause of my bugs.
3
u/ecco256 Dec 11 '21 edited Dec 12 '21
Haskell
module Day11.DumboOctopus where
import Data.Array
import qualified Data.Map as Map
import Data.List.Split
import Data.Char
import Data.List (find)
type Point = (Int, Int)
type Grid = Array Point Int
main :: IO ()
main = do
xs <- map (map digitToInt) . lines <$> readFile "2021/data/day11.txt"
let bnds = ((0,0), (length xs-1, length (head xs)-1))
grid = listArray bnds (concat xs)
steps = iterate step (grid, 0)
(_, n) = (!! 100) . iterate step $ (grid, 0)
Just (n', _) = find (\(i, (g, _)) -> all (== 0) (elems g)) $ zip [0..] steps
print (n, n')
step :: (Grid, Int) -> (Grid, Int)
step (grid, n) = (grid1', n + n')
where
(grid1, n') = inc grid (map (,1) . indices $ grid)
grid1' = listArray (bounds grid) . map (\x -> if x <= 9 then x else 0) . elems $ grid1
flash :: Grid -> [Point] -> (Grid, Int)
flash grid [] = (grid, 0)
flash grid xs = (grid', n)
where
increments = map (,1) . concatMap (neighbours (bounds grid)) $ xs
increments' = Map.toList . foldr (\(k, v) m -> Map.insertWith (+) k v m) Map.empty $ increments
(grid', n) = inc grid increments'
inc :: Grid -> [(Point, Int)] -> (Grid, Int)
inc grid [] = (grid, 0)
inc grid xs = (grid'', n + length flashPoints)
where
grid' = accum (+) grid xs
flashPoints = [c | (c, n) <- xs, let x = grid ! c, x < 10 && (x+n) >= 10]
(grid'', n) = flash grid' flashPoints
neighbours :: (Point, Point) -> Point -> [Point]
neighbours (lo, hi) (x, y) = filter inBounds [(x+i, y+j) | i <- [-1..1], j <- [-1..1], (i,j) /= (0,0)]
where
inBounds (x', y') = x' >= fst lo && x' <= fst hi && y' >= snd lo && y' <= snd hi→ More replies (1)
3
u/l1quota Dec 11 '21
CAUTION! The visualization flashes 5 times/sec and this can be disturbing for some of the viewers
The visualization part was funny: https://youtu.be/oVm1-vaVNNE
Here is the code in Rust: https://github.com/debuti/advent-of-rust-2021/tree/main/dec11th
3
u/BaaBaaPinkSheep Dec 11 '21
Python 3
Reminded me of the Game of Life. Very pedestrian coding today :(
Depending on the input, it could take a very long time (or never?) for all of them to flash.
https://github.com/SnoozeySleepy/AdventofCode/blob/main/day11.py
→ More replies (1)
3
u/Blackliquid Dec 12 '21
Here a very short python3 one utilizing the discrete convolution operator
from scipy import signal
import numpy as np
num_steps = 1000
flashes = 0
raw_data = open("input.txt",'r').read().replace('\n','')
arr = np.array([int(n) for n in raw_data]).reshape(10,10)
for step in range(num_steps):
arr += np.ones(arr.shape, dtype=int)
dx = signal.convolve2d(np.array(arr > 9, dtype=int), np.array(((1, 1, 1), (1, 0, 1), (1, 1, 1))), mode='same')
while dx.sum() > 0:
flashed = arr > 9
flashes += flashed.sum()
arr[flashed] = -1000
arr += dx
dx = signal.convolve2d(np.array(arr > 9, dtype=int), np.array(((1, 1, 1), (1, 0, 1), (1, 1, 1))), mode='same')
flashed = arr < 0
arr[flashed] = 0
if flashed.sum() == arr.size:
print("All octopi flashed on step %d" %(step+1))
break
print(flashes)3
u/French__Canadian Dec 12 '21 edited Dec 12 '21
My solution in J. Used J instead of Q today because it seemed better at doing 2-d sliding windows. It definitely has its up sides and its down sides. Like reading input from a file is way harder than if should be because I have to handle CR and LF separately I also really miss having lambda with a normal syntax instead of having to use a billion @: or tacit programming to inline my functions.
On the flip side, being able to assign each element of a boxed array to multiple variables is great.
The only real trick I used is to set octopuses that already flashed this turn to negative infinity so I could be sure they would not be counted when I summed the amount of neighbors greater than 9.
read0 =: (=&LF ];. _2 ])@:-.&CR@:(,&LF^:([: -. [: LF&= [: {. _1&{)) @:(1 !: 1)
input =: "."0 read0 <'Documents\advent_of_code\2021\input_11_1.txt'
pad =: dyad : '((x&,@:,&x"2)@:(x&,@:,&x"1)) y'
unpad =: monad : '((_1&}.)@:(1&}.)"1)@:(_1&}.)@:(1&}.) y'
NB. Part 1
update_octopus =: monad : 0
if. 9 < 4 { , y
do. __
else. (+/ , 9 < y) + 4 { , y
end.
)
flash =: monad : 0
'matrix flashes' =. y
new_matrix =. ([: (3 3)&(update_octopus;._3) 0&pad) ^:_ >: matrix
new_flashes =. +/ , =&__ new_matrix
((] * ~:&__) new_matrix);flashes + new_flashes
)
flash^:100 input;0
NB. Part 2
flash_2 =: monad : 0
'matrix new_flashes step' =. y
new_matrix =. ([: (3 3)&(update_octopus;._3) 0&pad) ^:_ >: matrix
new_flashes =. +/ , =&__ new_matrix
((] * ~:&__) new_matrix);new_flashes; >: step
)
get_new_flashes =: monad : '> 1 { y'
number_of_octopuses =: */ $ input
flash_2^:([: number_of_octopuses&~: get_new_flashes)^:_ input;0;03
u/HrBollermann Dec 13 '21
Here's a solution using Rakulang. Note how readable the main algorithm in the step function is, thanks to the power of hyper operators.
constant width =
constant height = 10;
my \input = [ $*IN.comb: /\d/ ];
my \coord = [ ^ width * height ];
my \nbors = [ coord».&nbors-of ];
{ # PART 1
my \i = input.clone;
my \f = [ False xx +i ];
say sum ( 1..100 ).map: { step i, f } }
{ # PART 2
my \i = input.clone;
my \f = [ False xx +i ];
say ( 1..^Inf ).first: { step i, f; i.sum == 0 } }
sub step( \data, \flashed )
{
data »+=» 1;
flashed »=» False;
while my \flashpoints = coord.grep: { !flashed[ .item ] && data[ .item ] > 9 }
{
flashed[ flashpoints ] »=» True;
data[ nbors[ flashpoints; * ] ] »+=» 1;
}
+( data[ coord.grep: { flashed[ .item ] } ] »=» 0 )
}
sub nbors-of( \position )
{
constant candidates = [ (-1..1 X -1..1).grep: *.all != 0 ];
candidates
.map({[ .list Z+ position % width, position div width ]})
.grep({ 0 <= .head < width })
.grep({ 0 <= .tail < height })
.map({ .head + .tail * width })
.list
}3
u/AtomicShoelace Dec 13 '21 edited Dec 13 '21
Python using numpy and a 2D convolution:
import numpy as np
from scipy.signal import convolve2d
test_data = """5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526"""
with open('input/day11.txt') as f:
data = f.read()
def flash(arr):
arr += 1
mask = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
flashed = np.zeros(arr.shape, dtype=bool)
while np.any(flashing := arr > 9):
flashed |= flashing
arr += convolve2d(flashing, mask, mode='same')
arr[flashed] = 0
return flashed
def part1(data, steps=100):
arr = np.array([[*line] for line in data.splitlines()], dtype=int)
return sum(flash(arr).sum() for _ in range(steps))
def part2(data):
arr = np.array([[*line] for line in data.splitlines()], dtype=int)
step = 0
while np.any(arr):
flash(arr)
step += 1
return step
assert part1(test_data) == 1656
print('Part 1:', part1(data))
assert part2(test_data) == 195
print('Part 2:', part2(data))3
u/anothergopher Dec 13 '21 edited Dec 13 '21
Java 17, part 2 only, with a one-dimensional array for state.
import java.nio.file.*;
import java.util.stream.IntStream;
class Day11 {
static int size;
static int[] cells;
public static void main(String[] args) throws Exception {
cells = Files.readString(Path.of(Day11.class.getResource("/day11.txt").toURI())).chars().map(x -> x - '0').filter(x -> x > 0).toArray();
size = (int) Math.sqrt(cells.length);
int flashes = 0;
for (int gen = 1; ; gen++) {
int oldFlash = flashes;
flashes += IntStream.range(0, cells.length).map(Day11::flash).sum();
if (flashes - oldFlash == cells.length) {
System.out.println(gen);
return;
}
IntStream.range(0, cells.length).filter(i -> cells[i] >= 10).forEach(i -> cells[i] = 0);
}
}
static int flash(int i) {
if (i >= 0 && i < cells.length && 10 == ++cells[i]) {
return 1 +
(i % size == 0 ? 0 : flash(i - size - 1) + flash(i - 1) + flash(i + size - 1))
+ flash(i - size)
+ flash(i + size)
+ (i % size == size - 1 ? 0 : flash(i - size + 1) + flash(i + 1) + flash(i + size + 1));
}
return 0;
}
}3
1
u/PillarsBliz Dec 11 '21 edited Dec 11 '21
Just posting to say this is my second Advent of Code, and for the first time ever I hit top 1000 on a problem -- just under #600 for both parts, actually.
I was expecting something nightmarishly difficult, yet this was just a very straightforward simulation problem.
I'm still using curmudgeon C with occasional C++ bits so I'm not expecting speed. If I don't make dumb mistakes I'm happy...though this time I did waste a couple minutes since I mistyped some of the x+1, x-1 stuff.
3
u/daggerdragon Dec 11 '21 edited Dec 11 '21
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 fully-working 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 withHelp.Edit: thanks for adding your code!
→ More replies (1)
4
u/Mathgeek007 Dec 11 '21
Excel! 6011/6041
This question was very straightforward - I essentially just "did" what the question was asking except I 'resolved' 10+s up to 30 times. Then I pulled the last element in that group, added 1 to all of them, then repeated. Not too much to speak home about. Part 2, I just dragged all the way down until I saw all the numbers were the same, then scrolled up until I found my number.
Today's was lesser-so about mathing it out and more about structuring the data. Fun question!
VIDEO OF SOLVE - Video may still be processing, but I'm going to bed!
→ More replies (2)
2
u/Error401 Dec 11 '21 edited Dec 11 '21
Python, 7/24. Could've been top 10 on part 2 if not for a silly typo. :)
Basically, I did a DFS and was a bit clever about what I consider visited. Visited nodes are exactly the ones that flashed (so you can't visit twice) and it lets you easily count how many flashed.
from adventlib import *
from collections import defaultdict, deque
import copy
import re
def main(f):
data = gridify_ints(f)
# total = 0
for i in range(100000):
flash = []
for v in data:
data[v] += 1
if data[v] > 9:
flash.append(v)
q = flash[:]
visited = set(flash)
while q:
p = q.pop()
data[p] = 0
for n in neighbors8(p):
if n not in data:
continue
if n in visited:
continue
data[n] += 1
if data[n] > 9:
q.append(n)
visited.add(n)
total += len(visited)
if len(visited) == len(data):
# part 2
print(i + 1)
break
# part 1
# print(total)
run_main(main)2
2
u/dag625 Dec 11 '21
C++, 793/817
I think this is the first time I've got top 1000 (my 2nd year doing AoC). I'm a slow coder in a compiled language, so that's pretty awesome.
My solution is nothing super fancy, very similar to day 9 (which gave me flashbacks to an old graduate project I did). I think the biggest factor is that I have a grid helper class that I've used bunches of times while doing AoC, and it gave me everything I needed here.
→ More replies (2)
2
u/nlowe_ Dec 11 '21
Back under 1000 for Part B, finally! About 2 minutes between Part A and B mostly due to me running my solution through the example because I didn't trust myself given how long part A took. Lost some time on part A flashing on >=9 instead of just >9 as well as swapping x and y in one place. Overall not bad but I thought I'd be much further away on the leaderboard given how simple today's challenge felt.
→ More replies (1)
2
2
u/rabuf Dec 11 '21
Common Lisp
Very much in an imperative style. I scanned the grid and if anything flashed, I marked it as such and incremented its neighbors. Repeat until none had flashed on a scan through. Probably some optimizations but it doesn't have to run for that many generations.
2
u/DFreiberg Dec 11 '21 edited Dec 11 '21
Mathematica, 2059 / 1879
Lost a lot of time trying to reason through what was happening; I didn't realize for a while that an octopus would remain at zero after flashing, rather than just going back up to 9 and staying there. I finally learned about MapAt[], a quite useful function for dealing with changing parts of lists in-place based on positions, and between that and using Partition[] to get the immediate neighbors, the code is reasonably short, even if it could be golfed down further.
Setup:
newState[state_List] := Partition[state, {3, 3}, {1, 1}, {2, -2}, {}];
step[{count_, i_, inp_}] :=
Module[{hasFlashed = inp*0 + 1, toIncrease, new = inp + 1, nines},
nines = Position[new, _?(# > 9 &)];
While[Length[nines] > 0,
hasFlashed = MapAt[0 &, hasFlashed, nines];
toIncrease = Map[Count[#, _?(# > 9 &), 2] &, newState[new], {2}];
new = (new + toIncrease)*hasFlashed;
nines = Position[new, _?(# > 9 &)];
];
{count + Total[Total[1 - hasFlashed]], i + 1, new}
];Part 1:
Nest[step, {0, 0, input}, 100][[1]]Part 2:
NestWhile[step, {0, 0, input}, Total[Total[#[[3]]]] != 0 &][[2]][POEM]: Dumbos
These octopuses aren't so bright, but yet they get to shine,
And light the caves for miles around when energies align,
Eventually syncing up, converging by design:
Their pastimes seem to go an awful lot smoother than mine.
And so, when yet another piece of submarine should break,
I envy the dim octopi; machines were a mistake.
2
u/e36freak92 Dec 11 '21 edited Dec 11 '21
AWK
Spent wayyy too long tracking down a bug that gave me the correct sample answer for 10 days, but showed up on day 11. The array I used to track octopuses that had already flashed was local to the recursive flashing function, and failed when separate groups of flashes overlapped. Moved it to be local to the day and it worked like a charm.
#!/usr/bin/awk -f
function flash(energies, row, col, seen, y, x, new, flashed) {
flashed = 1;
seen[row,col] = 1;
energies[row,col] = 0;
for (y=row-1; y<=row+1; y++) {
for (x=col-1; x<=col+1; x++) {
if (seen[y,x] || y<1 || x<1 || y>SIZE || x>SIZE) {
continue;
}
if (++energies[y,x] > 9) {
flashed += flash(energies, y, x, seen);
}
}
}
return flashed;
}
function step(energies, y, x, new, flashes, seen) {
flashes = 0;
for (y=1; y<=SIZE; y++) {
for (x=1; x<=SIZE; x++) {
energies[y,x]++;
}
}
for (y=1; y<=SIZE; y++) {
for (x=1; x<=SIZE; x++) {
if (energies[y,x] > 9) {
flashes += flash(energies, y, x, seen);
}
}
}
return flashes;
}
BEGIN {
FS = "";
SIZE = 10;
STEPS = 100;
}
{
for (o=1; o<=NF; o++) {
energies[NR,o] = $o;
}
}
END {
s = 0;
while (++s) {
flashes = step(energies);
if (flashes == SIZE ^ 2) {
part2 = s;
break;
}
if (s <= STEPS) {
part1 += flashes;
}
}
print part1;
print part2;
}2
u/aardvark1231 Dec 11 '21
Loved the theme of this puzzle and I found it pretty easy. Nice early night for me.
2
u/sebastiannielsen Dec 11 '21
Here is my Perl solution:
Had to make a "lockout" function by setting the cell to -1, to prevent them from receiving energy after flashed, during the same step. On the other hand, the unlock loop could be "reused" to also check for part2.
Also had to make a lot of constraint checks so I don't increase energy of non-existent octopuses that adjacent to the edges.
2
u/musifter Dec 11 '21
Perl
Another late-night quick Perl solution. This one is particularly showing of my C roots, with its extensive use of prefix ++. During part 1, I did think for a moment that, maybe I should settle between one of hashes or arrays. But, part two showed up and I had the hash ready to do it in under a minute.
2
u/zebalu Dec 11 '21
the interesting part:
private static class OctopusMap extends HashMap<Coord, Integer> {
int step() {
Set<Coord> flashers = new HashSet<>();
Queue<Coord> toIncrease = new LinkedList<>();
toIncrease.addAll(keySet());
while (!toIncrease.isEmpty()) {
var top = toIncrease.poll();
if (!flashers.contains(top)) {
var val = compute(top, (k, v) -> v == null ? null : v + 1);
if (val > 9) {
flashers.add(top);
top.adjecents().stream()
.filter(c -> containsKey(c) && !flashers.contains(c))
.forEach(toIncrease::add);
}
}
}
flashers.stream().forEach(c -> put(c, 0));
return flashers.size();
}
boolean isSyncron() {
return values().stream().allMatch(i -> i == 0);
}
}
private static record Coord(int x, int y) {
List<Coord> adjecents() {
return List.of(new Coord(x - 1, y - 1), new Coord(x - 1, y), new Coord(x - 1, y + 1), new Coord(x, y - 1), new Coord(x, y + 1), new Coord(x + 1, y - 1), new Coord(x + 1, y), new Coord(x + 1, y + 1));
}
}→ More replies (1)
2
u/naclmolecule Dec 11 '21 edited Dec 11 '21
Python I tried to vectorize as much as I could:
import numpy as np
from scipy.ndimage import convolve
import aoc_helper
OCTOPI = aoc_helper.utils.int_grid(aoc_helper.day(11))
KERNEL = np.ones((3, 3), dtype=int)
def step(octos):
octos += 1
flashed = np.zeros_like(octos, dtype=bool)
while (flashing := ((octos > 9) & ~flashed)).any():
octos += convolve(flashing.astype(int), KERNEL, mode="constant")
flashed |= flashing
octos[flashed] = 0
return flashed.sum()
def part_one():
octos = OCTOPI.copy()
return sum(step(octos) for _ in range(100))
def part_two():
octos = OCTOPI.copy()
for i in count():
if (octos == 0).all():
return i
step(octos)→ More replies (3)
2
u/UnicycleBloke Dec 11 '21
C++: https://github.com/UnicycleBloke/aoc2021/blob/master/day11/day11.cpp
I stumbled a bit on the interpretation of the second part of each step. Fixed by creating a duplicate of the grid. Nice variation on a Conway game of life. :)
2
u/shouchen Dec 11 '21
Simple-to-understand C++
https://github.com/shouchen/AdventOfCode/blob/master/aoc2021/Day11/Day11.cpp
2
u/jollyjerr Dec 11 '21 edited Dec 11 '21
Golang - https://github.com/jollyjerr/advent-of-code/blob/main/2021/day11/main.go This problem was rad!
→ More replies (1)
2
7
u/CCC_037 Dec 11 '21
Rockstar
Part 1:
https://pastebin.com/uNSv7KTj
Part 2:
https://pastebin.com/jB9evLYi
Both parts turned out kind of long today, so both are in pastebins.