aoc-2021-rust

commit 7dda43d51a149382991f9c053a1963fab85b21c3
parent ec29c015d2e9d27129490ecb55969acb371943f7
Author: Louis Burda <quent.burda@gmail.com>
Date:   Tue, 14 Dec 2021 01:07:40 +0100

Add day 11 solution

Diffstat:
A
src/11/Cargo.toml
 | 
7
+++++++
A
src/11/input
 | 
10
++++++++++
A
src/11/input.test
 | 
10
++++++++++
A
src/11/part1
 | 
320
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
src/11/part2
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++
A
src/11/src/main.rs
 | 
108
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

6 files changed, 502 insertions(+), 0 deletions(-)
diff --git a/src/11/Cargo.toml b/src/11/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "aoc"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+
diff --git a/src/11/input b/src/11/input
@@ -0,0 +1,10 @@
+6227618536
+2368158384
+5385414113
+4556757523
+6746486724
+4881323884
+4648263744
+4871332872
+4724128228
+4316512167
diff --git a/src/11/input.test b/src/11/input.test
@@ -0,0 +1,10 @@
+5483143223
+2745854711
+5264556173
+6141336146
+6357385478
+4167524645
+2176841721
+6882881134
+4846848554
+5283751526
diff --git a/src/11/part1 b/src/11/part1
@@ -0,0 +1,320 @@
+--- Day 11: Dumbo Octopus ---
+
+You enter a large cavern full of rare bioluminescent dumbo octopuses! They seem to not like the
+Christmas lights on your submarine, so you turn them off for now.
+
+There are 100 octopuses arranged neatly in a 10 by 10 grid. Each octopus slowly gains
+energy over time and flashes brightly for a moment when its energy is full. Although your lights are
+off, maybe you could navigate through the cave without disturbing the octopuses if you could predict
+when the flashes of light will happen.
+
+Each octopus has an energy level - your submarine can remotely measure the energy level of each
+octopus (your puzzle input). For example:
+
+5483143223
+2745854711
+5264556173
+6141336146
+6357385478
+4167524645
+2176841721
+6882881134
+4846848554
+5283751526
+
+The energy level of each octopus is a value between 0 and 9. Here, the top-left octopus has an
+energy level of 5, the bottom-right one has an energy level of 6, and so on.
+
+You can model the energy levels and flashes of light in steps. During a single step, the following
+occurs:
+
+
+ - First, the energy level of each octopus increases by 1.
+
+ - Then, any octopus with an energy level greater than 9 flashes. This increases the energy level of
+all adjacent octopuses by 1, including octopuses that are diagonally adjacent. If this causes an
+octopus to have an energy level greater than 9, it also flashes. This process continues as long as
+new octopuses keep having their energy level increased beyond 9. (An octopus can only flash
+at most once per step.)
+
+ - Finally, any octopus that flashed during this step has its energy level set to 0, as it used all
+of its energy to flash.
+
+
+Adjacent flashes can cause an octopus to flash on a step even if it begins that step with very
+little energy. Consider the middle octopus with 1 energy in this situation:
+
+Before any steps:
+11111
+19991
+19191
+19991
+11111
+
+After step 1:
+34543
+40004
+50005
+40004
+34543
+
+After step 2:
+45654
+51115
+61116
+51115
+45654
+
+An octopus is highlighted when it flashed during the given step.
+
+Here is how the larger example above progresses:
+
+Before any steps:
+5483143223
+2745854711
+5264556173
+6141336146
+6357385478
+4167524645
+2176841721
+6882881134
+4846848554
+5283751526
+
+After step 1:
+6594254334
+3856965822
+6375667284
+7252447257
+7468496589
+5278635756
+3287952832
+7993992245
+5957959665
+6394862637
+
+After step 2:
+8807476555
+5089087054
+8597889608
+8485769600
+8700908800
+6600088989
+6800005943
+0000007456
+9000000876
+8700006848
+
+After step 3:
+0050900866
+8500800575
+9900000039
+9700000041
+9935080063
+7712300000
+7911250009
+2211130000
+0421125000
+0021119000
+
+After step 4:
+2263031977
+0923031697
+0032221150
+0041111163
+0076191174
+0053411122
+0042361120
+5532241122
+1532247211
+1132230211
+
+After step 5:
+4484144000
+2044144000
+2253333493
+1152333274
+1187303285
+1164633233
+1153472231
+6643352233
+2643358322
+2243341322
+
+After step 6:
+5595255111
+3155255222
+3364444605
+2263444496
+2298414396
+2275744344
+2264583342
+7754463344
+3754469433
+3354452433
+
+After step 7:
+6707366222
+4377366333
+4475555827
+3496655709
+3500625609
+3509955566
+3486694453
+8865585555
+4865580644
+4465574644
+
+After step 8:
+7818477333
+5488477444
+5697666949
+4608766830
+4734946730
+4740097688
+6900007564
+0000009666
+8000004755
+6800007755
+
+After step 9:
+9060000644
+7800000976
+6900000080
+5840000082
+5858000093
+6962400000
+8021250009
+2221130009
+9111128097
+7911119976
+
+After step 10:
+0481112976
+0031112009
+0041112504
+0081111406
+0099111306
+0093511233
+0442361130
+5532252350
+0532250600
+0032240000
+
+After step 10, there have been a total of 204 flashes. Fast forwarding, here is the same
+configuration every 10 steps:
+
+After step 20:
+3936556452
+5686556806
+4496555690
+4448655580
+4456865570
+5680086577
+7000009896
+0000000344
+6000000364
+4600009543
+
+After step 30:
+0643334118
+4253334611
+3374333458
+2225333337
+2229333338
+2276733333
+2754574565
+5544458511
+9444447111
+7944446119
+
+After step 40:
+6211111981
+0421111119
+0042111115
+0003111115
+0003111116
+0065611111
+0532351111
+3322234597
+2222222976
+2222222762
+
+After step 50:
+9655556447
+4865556805
+4486555690
+4458655580
+4574865570
+5700086566
+6000009887
+8000000533
+6800000633
+5680000538
+
+After step 60:
+2533334200
+2743334640
+2264333458
+2225333337
+2225333338
+2287833333
+3854573455
+1854458611
+1175447111
+1115446111
+
+After step 70:
+8211111164
+0421111166
+0042111114
+0004211115
+0000211116
+0065611111
+0532351111
+7322235117
+5722223475
+4572222754
+
+After step 80:
+1755555697
+5965555609
+4486555680
+4458655580
+4570865570
+5700086566
+7000008666
+0000000990
+0000000800
+0000000000
+
+After step 90:
+7433333522
+2643333522
+2264333458
+2226433337
+2222433338
+2287833333
+2854573333
+4854458333
+3387779333
+3333333333
+
+After step 100:
+0397666866
+0749766918
+0053976933
+0004297822
+0004229892
+0053222877
+0532222966
+9322228966
+7922286866
+6789998766
+
+After 100 steps, there have been a total of 1656 flashes.
+
+Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps.
+How many total flashes are there after 100 steps?
+
+
diff --git a/src/11/part2 b/src/11/part2
@@ -0,0 +1,47 @@
+--- Part Two ---
+
+It seems like the individual flashes aren't bright enough to navigate. However, you might have a
+better option: the flashes seem to be synchronizing!
+
+In the example above, the first time all octopuses flash simultaneously is step 195:
+
+After step 193:
+5877777777
+8877777777
+7777777777
+7777777777
+7777777777
+7777777777
+7777777777
+7777777777
+7777777777
+7777777777
+
+After step 194:
+6988888888
+9988888888
+8888888888
+8888888888
+8888888888
+8888888888
+8888888888
+8888888888
+8888888888
+8888888888
+
+After step 195:
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+0000000000
+
+If you can calculate the exact moments when the octopuses will all flash simultaneously, you should
+be able to navigate through the cavern. What is the first step during which all octopuses flash?
+
+
diff --git a/src/11/src/main.rs b/src/11/src/main.rs
@@ -0,0 +1,108 @@
+use std::fs;
+use std::env;
+
+#[derive(PartialEq,Eq)]
+struct Pos {
+    x: i32,
+    y: i32
+}
+
+const SURROUNDING: [Pos; 8] = [
+    Pos { x: -1, y: -1 },
+    Pos { x: -1, y:  0 },
+    Pos { x: -1, y:  1 },
+    Pos { x:  0, y: -1 },
+    Pos { x:  0, y:  1 },
+    Pos { x:  1, y: -1 },
+    Pos { x:  1, y:  0 },
+    Pos { x:  1, y:  1 }
+];
+
+fn main() {
+    let args: Vec<String> = env::args().collect();
+    if args[1] == "1" {
+        part1();
+    } else if args[1] == "2" {
+        part2();
+    } else {
+        eprintln!("No such part\n");
+    }
+}
+
+fn print_octos(octos: &Vec<Vec<u32>>)  {
+    for row in octos {
+        for octo in row {
+            print!("{}", octo);
+        }
+        println!();
+    }
+    println!();
+}
+
+fn inc_check(flashed: &mut Vec<Pos>, octos: &mut Vec<Vec<u32>>, x: usize, y: usize) {
+    let pos = Pos { x: x as i32, y: y as i32 };
+    if flashed.contains(&pos) { return; }
+
+    octos[y][x] += 1;
+    if octos[y][x] < 10 { return; }
+
+    flashed.push(Pos { x: x as i32, y: y as i32 });
+    octos[y][x] -= 10;
+
+    assert!(octos.len() > 0);
+    let height = octos.len();
+    let width = octos[0].len();
+    for d in SURROUNDING {
+        let nx = ((x as i32) + d.x) as usize;
+        let ny = ((y as i32) + d.y) as usize;
+        if (0..width).contains(&nx) && (0..height).contains(&ny) {
+            inc_check(flashed, octos, nx, ny);
+        }
+    }
+}
+
+fn sim_step(octos: &mut Vec<Vec<u32>>) -> usize {
+    let mut flashed: Vec<Pos> = Vec::new();
+
+    assert!(octos.len() > 0);
+    let height = octos.len();
+    let width = octos[0].len();
+    for y in 0..height {
+        for x in 0..width {
+            inc_check(&mut flashed, octos, x, y);
+        }
+    }
+
+    return flashed.len();
+}
+
+fn part1() {
+    let content = fs::read_to_string("input").expect("no file");
+    let mut octos: Vec<Vec<u32>> = content.lines()
+        .map(|l| l.chars().map(|c| c.to_digit(10).unwrap()).collect()).collect();
+
+    let mut flashes: usize = 0;
+    for _i in 0..100 {
+        flashes += sim_step(&mut octos);
+    }
+
+    println!("{}", flashes);
+}
+
+fn part2() {
+    let content = fs::read_to_string("input").expect("no file");
+    let mut octos: Vec<Vec<u32>> = content.lines()
+        .map(|l| l.chars().map(|c| c.to_digit(10).unwrap()).collect()).collect();
+
+    let height = octos.len();
+    let width = octos[0].len();
+
+    let mut step = 0;
+    let mut last = 0;
+    while last != width * height {
+        last = sim_step(&mut octos);
+        step += 1;
+    }
+
+    println!("{}", step);
+}