Day 3

2 files changed, 278 insertions, 8 deletions

diff --git a/2023/inputs/day_3.txt b/2023/inputs/day_3.txt
new file mode 100644
index 0000000..f16d6e0
--- /dev/null
+++ b/2023/inputs/day_3.txt
@@ -0,0 +1,140 @@
+.....180.........230..........................218.....189......415.......................322....507..................206..............111...
+........*.602.........571-.......................*...*.............199.....$.........181.......*......980....292............................
+..509.923.=....................+......835*......608.984..............-.801..922.156...*.........533.....$.......*678.......&................
+...*............273..........307..........393................@..........*.......*...231..................................106.339............
+.906..............*.350..........................322...938..582.372....160...................411........197.........42.................$81..
+...............944.....*......473........80*..............#.....*............340.......107....*...........&..................893............
+...........937........32........./..12......199.......440......32.785..........*......*.....50......198......37.....710.......$..740.691+...
+....304....*...870.......*787.........@..$......462.............................264....420........#..........*........*...........*.........
+...&......395...*.....545...............539..............................491.......................318.=410...10.....16.....364..188.=891...
+......../.....423.337......42....430........554................614.90.......*702....*587......$................................*............
+...269.267..........*......*.....*............*........%.930.....*......864......675........133...-.......707...318.908...629.776...........
+.....*......884......345...979..780..917.....942.....875........826......................*......28...254..&.......*...=.....................
+...270...95*...........................*....................289...................307..431..............*.....%.........................611.
+.....................+.............890.970..+...........235......*...........@...............405.........817...242./991...........*.........
+..............137...63....../......*.......478.255.739.....*.....584......399..367..........#....51........................403.908.175......
+761....582...=.............740..143.....*.........*.........722......151......*.........-.....................23......476....*..............
+....49...*............444.............537......*......791....................37...212...60.444....-728.+......*...778..*...31.....895.@534..
+......*...108....942....*......463...........39.616.........40.........*...........*........*...........446...........268........*..........
+..50#.625...........+..838........*.....................105*....250..409......+......425....101.914.............................876.+386....
+..............116..............848..111.......14..................&..........816.......*........*..........548...........*....@.............
+................./........#........*.........@...58......................181..........792....565..750...........767....%..81..525......770..
+716......439.498...........942....719..................697@...............*.....&688...............*..421........&..847................&....
+...*261.....*.......*.................=..........................5.....800................-......471..%......753...............880.../......
+.................289.715............832........120...=............&...........*126.........258..............*.........300.......*...909.....
+.676.........432................757.................309..............311...903..................422.......335..38......*.....521............
+..../..742...*..............#....*.......574..198.*......852..............................751...-.....531.......&.......849.........449.....
+........*....116......../.839..712............*...402......*.....865.894.........964.................../..*........288......................
+......568........295.547....................471.........................*.......*........640*......457...193..599*....*.......137.......888.
+..................@..........345.189...849.........181...........879.....339.730...32........734...*..............793.289....*....&....#....
+........%854....*.....*976......*........*.872....*.................%.............*......167.......2......................747......814......
+.454............322.........*.........930........696..28........9.....................-..................890...17*..........................
+...........912.......133&...87.....*.................+.........*............412........473.....781.778.......................*801..676#.867.
+.605......*.....................685.345.......545.+.............636.....665*......................*...................19..933...............
+....*..678.......844.881*.................667...*.940..52...................................336/..................51...@...........927.455..
+.779..............*......221................/.657.......*..@1....220*....100.....=.................320..............=.................*.....
+..........991......198........419.283..................414..................@..833...........334.....&...................567..235&..........
+.............=................*...=..............944........188........61.......................%.........508..130...*.....*........*205....
+.............................357.........$619......*....674*.....*262..&..479...912.421%..74.........261....#..*...68.708.795....695........
+....594....432........521.......................794...........636............*............*...................315........................568
+...%..........*..909.....#..........................*...720........419..603*..256.........386..........150............149.-.........=.......
+............492..*...172.........701...109-.176..641......&....235.$...........................915.......=..+636......*....643......515.....
+484...695........857.$..../.......*...........+......2..........*.................@..383.........*.254................103......665..........
+.........%..543..........20..@....113....102..........*884.............12.......685...-.........40..*......231............@.........*...219.
+.918.......@................633..........*...+901.......................%.................&.........145.................109...538...653.$...
+......................668...............845..............=..................611...........30.............20.....166.............$...........
+............627.........&........617..................179.............776.....-................&.....823*...98&....*.................203#...
+.575..........*.............338..............216.229...........-..304*...........*960..........876.................539......................
+......-284.655.....188......*....=.787..../....*....$.56.+....892.............792..........................-...........37.......546.993.....
+...............134..=.....945..392....*...663..639........567.......298...277........665...........702......706.........*..........*.....328
+...#..502..598..-..................611................................*......*...172*........607......#.....................................
+425......*....*.....%677...260*214.............#....@759...............260.935...........247*...............779......430............=...84..
+......159...156.......................99.642...42.........825..+720..................&..........+27....@...@.........*........611...240.....
+.............................402..798*.../..............-...*.......218..........371..491...........314.......*372....601......*............
+..310.........+263.266...............................721...431.....*.........342....-.............+........211.................397......253.
+......................*........60...................................83..........*..................435..........=...........................
+............458@.......424........909....241......611..................109..934..476..356...571..............900..495.....57................
+...125...86........356..............=........................653=..402*........*......*....&........540..........*..............126.........
+......*.%.......#...*..................82.227..713*868.36...............248...698.....399..............*.......276.564.820...69.............
+....458.......294..58......890*1...44...@..................-.83....783....&.................*326..246.981............#...=.....*.........549
+....................................*...............*...677...@..............538*463.....493........*......63.................63..930.......
+.......253.................$...916..549...974.......319.............................................451.....*.48..206..996...........*370...
+...#..*...............655..15.*..............*616........................................................934....%.@.......+.../827..........
+.292.699....*.....94...........782......492...............21*........+....182....................818........................................
+...........789................................812...759......394......870../....50*351...................690..........*.....................
+...............361...141*467......923............*.$.......................................349......*....*.....780...621...619..............
+....11....920..*....................*..........34..............................987.....$....*......143..448.....+...........................
+..............777.83....../.616....706...115............503...........................267.....229.................645.....488..839......%...
+..........411...........801.#...........*.........298.......20*.......@587...930.................*770.....................@...-........989..
+.....672+.............*...........887.307.....922*.............315..............$.........878*.........261.......317.............624........
+..........640......411.25...$981...................37...357..........#984..684@...............310......*...&.....*..................#.......
+...........*............................/.%............%.......541.........................=.........812....67.902....956.....-.........824.
+285*118.606....274.......272*956..498.825.244...754./.............*..717......./............798..........................*....841..999..=...
+................../................*..............*.5............566...*....830..................286.........683/......967.........+........
+...........................=....761.............458.....125&............88..........217.411/.879*................................/...418....
+982......47..............167............*100..%...................%818...............*......................805&..%.....934...896.......*...
+.....987.....525...................@.911.......802............120...........808.......164................./........212.*...............720..
+.....*.........%..730.5*330......47....................752....*......520/..../...............964.......166.............392..................
+....260...........*......................473....163.....*..875..........................760..................532.............*.....&827.....
+...............211.......*........&..299..&..%....%.80.30........560.............326...........834*148..411......572......304.716...........
+628........+.......119..7.854....936..*......128...........38.=....*.....281......&...............................*...................753...
+....109..116......*..................98................269.=...327..910.....*823............773.....+..%237........411.....*803...175*......
+.....*............727.............................................................109....*.....$.897....................................779.
+...406.................#3.......%......454....109.........823.........................877.774.........298....+..........@..678..............
+............962............*.428........*....................*.........752..............................$.380.........687../.........963*649
+......323...*.....+286..914........834....893..124...494......785.......*.....806.................179.............85........................
+.......&...778./...................*.......*......*..%....866............500..&...327....970..........821.................+.863.......-663..
+..829..........626............569...164....197.401.......*..................................*.....784.../..224......117.22..*.....24........
+.....*.994..............................................609.&467............870..............811...............$....*.......386.............
+..207..*........816....................#..141......587...........*......218...+......536=......................337..927..85......194....802.
+......846......%.....+...............336......................846.398.....*..........................144.................*.........*....+...
+.160..............258......517...943...........128......33..............151..272.......124../...427....*............648.451....242..498.....
+......779.879................*.....*...%.........*........@...................*.........../.969....*..143............*............*.........
+.........*....354.417.......112.......409.........681........=....117.......241.$....#..........240........698.508.32....958*339.356........
+..915...........*........$...................194........48....600..*.............326.590.....................*..............................
+.....*250..781.503.....94........+877........*......88.....69.......693....757........................61..362......@...871.@................
+..........................................349..405....*539.#....855.......*............+902.......898.*...........121...=..541......959.....
+......541....712...927&.*370...339...............&..............*.......297........................+..571.881.......................*...260.
+.....*....#...........................392...........884.935..710............=......%./........................332.944.............575..*....
+..246....99............316..970...71..$.......606.......@........339...#..#..181.343.693.........542...729=........*..................357...
+...............781....&.......#.....*.........../.................#..172.761......................*................360...93&................
+251.............*..................980....368-...............977@.................489............729....537..........................41.....
+.................235.....631........................+....=...................818.........755............/..................$855.....*.......
+.............*...................250....708.623..380...890...........51..........598........*..............557..........*.......1.656....360
+..749.........368.............@....+......*......................660....862.866$...@./634.757..745........*.......209....652............*...
+.......379..#...............577........835.............312*913.....*......*.......................*......872..747........................168
+........#....346.329.........................852.=9..............%.....972...-...............604..198.67...........711.............247@.....
+..................*....&.........@5.....*....../........*467......839......159........&..941............-..........*........................
+....195.......711...509.....298@.......633.......936..=........*......990......903..833.*.....................&...72....=.....614...........
+613....*.....*......................................*..236..594.......&..................851.............760.850.........980........*980....
+......9.....130......549...549...................895.......................=....................840.....@........................989........
+....................*..................750...842.....27.804..@............950.....682.....586../.............166..481.......461.............
+.......881.....189..954.....513...45..@......*...........*...279...438.............*.........+...........740....&...+........*..............
+.568......@.............153...=...............690.......174.........../.............122..............867.=............451.906........324....
+...............&........*...&..........730........987.......................%.......................@.........*190...*...........672....%...
+................109...183..493.841@.......*...984*.......................857....39....635*653..519.........144.......896.$.......*...$......
+.........990...........................340..............+134...741...*...........%................=.....74................498....145..485...
+.../227....*.-.............990.............963.891..............=..553.....348.............965*.....$..*................#...................
+........641...100..*.............866.........$..*.......451*531.........-...*...185............762...4..178..690%........481.$....589..@216.
+....................65.164*697......*977.......96.......................184.514....*591......................................506....*.......
+...........334..................773.................226..253.511............................761..........607.....*532....909.....415........
+..548..668....*843.....23.824%..*....71.....411......../..*....#......656....................@.......=...*....452.......*..............+....
+.........@.=....................719.....804.*............653......................698....296.........613.29............749...........197....
+..705-......214....428#....633@...........*...................642....%986............*....*................................779...484........
+...................................228..........605...%237......*..................666..906.................296........736..%.....*.........
+.............593%.38...........129.*...............*...........474.....487.269@....................681.862....*.......@........517..........
+........539.......&..781.......*............895.876..336*794...........*............................*....*....621....................145....
+...815...*............$....484.54............*..........................953....564.......246.513...601...488......................&.........
+...*......776................&............840.....................974.............*471......*...................250....*....106#.548........
+437..............@.............#979............752%.798......97....#......*726.....................990*155.778.....*.78.....................
+................358.+706.....................*......*..................621..................&................-...757...................456..
+.....132....................44.....368....637.......209..............................464.242.......376..................492....=439.....#...
+......%...592........48*....-.....+......................897.799..108*...........432...&..............*472.261............@.................
+.........*.....$487.....471............236...944=..407......*.........337.........-...........................................270.....265...
+....$.....988...........................*...........*.....................713..................910..680..297*549......518.....&...727*......
+.....267.......634......202....../.....726.285..76...408..864.....377.....&................*..*........*.........289.*.....-................
+..............*..........*......782..........................@......*................460.172..768.......934......=....119.921..........$....
+........315.850......850.3..........322..439.....................784...........612.....*............................+.........310.813...819.
+.........*.............+.............*....*....457.......371.829.....215.......*......117...757...727$.....538......561.730..*..............
+......231......%....................604.725......*.=710.=.............*....974.329..............*.........*....747..........600.............
+..............688...869.........15............222.....................366....................120.10....539........................934.97....
diff --git a/2023/src/bin/day_3.rs b/2023/src/bin/day_3.rs
index b3a610b..06e1300 100644
--- a/2023/src/bin/day_3.rs
+++ b/2023/src/bin/day_3.rs
@@ -1,19 +1,149 @@
-use nom::IResult;
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::{digit1, line_ending, none_of},
+    combinator::{map, map_res},
+    multi::{many1, separated_list1},
+    IResult,
+};
 use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let input = fs::read_to_string("inputs/day_3.txt")?;
+    let parsed = PartInventory::parser(&input).unwrap().1;
+    dbg!(&parsed.part_number_sum());
+    dbg!(&parsed.gear_ratio_sum());
 
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct PartInventory {
+    parts: Vec<Part>,
+    symbols: Vec<Symbol>,
+}
+
+#[derive(Debug)]
+struct Part {
+    number: u32,
+    symbols: Vec<char>,
+    y: usize,
+    min_x: usize,
+    max_x: usize,
+}
+
+#[derive(Debug, Clone)]
+struct Symbol {
+    symbol: char,
+    parts: Vec<u32>,
+    x: usize,
+    y: usize,
+}
+
+#[derive(Debug)]
+enum LexToken {
+    Space(usize),
+    Part(usize, u32),
+    Symbol(char),
+}
+
+impl PartInventory {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(LexToken::parser, |tokens| {
+            let mut parts = Vec::new();
+            let mut symbols = Vec::new();
+
+            for (y, row) in tokens.iter().enumerate() {
+                let mut x = 0;
+                for token in row {
+                    match token {
+                        LexToken::Space(_) => {}
+                        LexToken::Part(len, number) => parts.push(Part {
+                            number: *number,
+                            symbols: Vec::new(),
+                            y,
+                            min_x: x,
+                            max_x: x + len - 1,
+                        }),
+                        LexToken::Symbol(symbol) => symbols.push(Symbol {
+                            symbol: *symbol,
+                            parts: Vec::new(),
+                            y,
+                            x,
+                        }),
+                    }
+                    x += token.len();
+                }
+            }
+
+            for part in &mut parts {
+                part.symbols = symbols
+                    .iter()
+                    .filter(|symbol| part.touches(symbol))
+                    .map(|symbol| symbol.symbol)
+                    .collect();
+            }
+
+            for symbol in &mut symbols {
+                symbol.parts = parts
+                    .iter()
+                    .filter(|part| part.touches(symbol))
+                    .map(|part| part.number)
+                    .collect();
+            }
+
+            PartInventory { parts, symbols }
+        })(input)
+    }
+
+    fn part_number_sum(&self) -> u32 {
+        self.parts
+            .iter()
+            .filter(|part| part.symbols.len() > 0)
+            .map(|part| part.number)
+            .sum()
+    }
+
+    fn gear_ratio_sum(&self) -> u32 {
+        self.symbols
+            .iter()
+            .filter(|symbol| symbol.symbol == '*' && symbol.parts.len() == 2)
+            .map(|symbol| symbol.parts[0] * symbol.parts[1])
+            .sum()
+    }
+}
+
+impl LexToken {
+    fn parser(input: &str) -> IResult<&str, Vec<Vec<Self>>> {
+        separated_list1(
+            line_ending,
+            many1(alt((
+                map(many1(tag(".")), |dots| LexToken::Space(dots.len())),
+                map_res(digit1, |num_s: &str| {
+                    num_s
+                        .parse()
+                        .map(|num_i| LexToken::Part(num_s.len(), num_i))
+                }),
+                map(none_of("\n"), |s| LexToken::Symbol(s)),
+            ))),
+        )(input)
+    }
+
+    fn len(&self) -> usize {
+        match self {
+            Self::Space(len) => *len,
+            Self::Part(len, _) => *len,
+            Self::Symbol(_) => 1,
+        }
+    }
+}
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+impl Part {
+    fn touches(&self, symbol: &Symbol) -> bool {
+        let part = self;
+        symbol.x >= part.min_x.saturating_sub(1)
+            && symbol.x <= part.max_x.saturating_add(1)
+            && symbol.y >= part.y.saturating_sub(1)
+            && symbol.y <= part.y.saturating_add(1)
     }
 }