commit 846df490e7b4a48b2ab4b8cdc404f848c88329aa
parent 98ac6de253757ae00925bd20541caf2c0197282a
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Fri, 6 Dec 2019 09:39:54 -0500
Add Rust solution for day 06
Diffstat:
3 files changed, 1000 insertions(+), 0 deletions(-)
diff --git a/day-06/Makefile b/day-06/Makefile
@@ -0,0 +1,9 @@
+CC := g++
+CCFLAGS := --std=c++17 -Wall
+
+all: day-06-rust day-06.jl
+ julia day-06.jl
+ ./day-06-rust
+
+day-06-rust: day-06.rs
+ rustc $^ -o $@
diff --git a/day-06/day-06.rs b/day-06/day-06.rs
@@ -0,0 +1,96 @@
+use std::collections::HashMap;
+use std::collections::VecDeque;
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+
+fn main() {
+ let input = BufReader::new(File::open("input.txt").unwrap())
+ .lines()
+ .map(|line| {
+ line.unwrap()
+ .trim()
+ .split(")")
+ .map(|x| x.to_string())
+ .collect::<Vec<String>>()
+ })
+ .collect::<Vec<Vec<String>>>();
+
+ println!("Rust:");
+ println!("Part 1: {}", part_1(&input));
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn part_1(input: &Vec<Vec<String>>) -> usize {
+ // Map from orbiting planets to center planet.
+ let orbit_map = input
+ .iter()
+ .map(|x| (x[1].clone(), x[0].clone()))
+ .collect::<HashMap<String, String>>();
+
+ let mut orbit_count = HashMap::<String, usize>::new();
+ for (planet, mut center) in &orbit_map {
+ let mut path = VecDeque::<String>::new();
+ let mut root_count = 0;
+
+ path.push_front(planet.to_string());
+
+ loop {
+ path.push_front(center.to_string());
+ if let Some(ob_count) = orbit_count.get(center) {
+ root_count = *ob_count;
+ break;
+ } else {
+ if let Some(next) = orbit_map.get(center) {
+ center = next;
+ } else {
+ break;
+ }
+ }
+ }
+
+ while let Some(root) = path.pop_front() {
+ *orbit_count.entry(root).or_default() = root_count;
+ root_count += 1;
+ }
+ }
+
+ orbit_count.values().sum::<usize>()
+}
+
+fn part_2(input: &Vec<Vec<String>>) -> usize {
+ // Map from orbiting planets to center planet.
+ let orbit_map = input
+ .iter()
+ .map(|x| (x[1].clone(), x[0].clone()))
+ .collect::<HashMap<String, String>>();
+
+ // Build SAN path.
+ let mut santa_path = HashMap::<String, usize>::new();
+ {
+ let mut center = orbit_map.get("SAN").unwrap();
+ let mut orbit_count = 0;
+ loop {
+ santa_path.insert(center.clone(), orbit_count);
+ if let Some(next) = orbit_map.get(center) {
+ center = next;
+ orbit_count += 1;
+ } else {
+ break;
+ }
+ }
+ }
+ // Trace back YOU path until we get a hit.
+ {
+ let mut center = orbit_map.get("YOU").unwrap();
+ let mut orbit_count = 0;
+ loop {
+ if let Some(san_count) = santa_path.get(center) {
+ return orbit_count + san_count;
+ } else {
+ center = orbit_map.get(center).unwrap();
+ orbit_count += 1;
+ }
+ }
+ }
+}
diff --git a/day-06/input.txt b/day-06/input.txt
@@ -0,0 +1,895 @@
+S5F)4L5
+7BP)2V1
+DHC)KGY
+JZG)PN7
+RV4)123
+2DJ)LPW
+19G)31B
+H4Z)TC6
+3YP)XTQ
+H9Q)QXJ
+R77)3FM
+JD3)GXY
+3WS)YHL
+X9K)BWP
+656)7PW
+9S2)LGY
+CZB)VXR
+1YS)Y5H
+1XY)L9Y
+NH1)YW5
+HVD)2PS
+Y1C)4SY
+LKH)1PV
+7HZ)GZD
+TJZ)WV7
+V8K)Z28
+DB4)S1Q
+TRV)4TM
+3L3)6YN
+LD1)4PR
+1XP)3YF
+B6Q)QRX
+QSL)JV7
+MFC)QSJ
+TC2)9JZ
+PLS)2TK
+T6Y)DNB
+HDT)BY7
+44G)FF3
+682)PLS
+91Z)DNX
+WKK)JWP
+FF3)F32
+CGL)F92
+YCF)8XZ
+VKQ)J6C
+DP4)6JF
+DWB)5RF
+5TG)WRP
+LWN)N2C
+5QB)34Z
+LK9)FB9
+VK9)WQM
+PLR)DP7
+BLV)KL4
+2XT)R7V
+CP3)TJT
+7GT)1XP
+5J1)Z44
+Z8V)MDX
+RQK)RVX
+K55)PSY
+LK4)2CR
+3FL)L74
+BDW)531
+XQZ)GST
+5DP)7G2
+78T)1VZ
+H41)4GK
+7PW)B9Q
+XSH)GF8
+QJ8)YTT
+RS9)844
+GRL)LD1
+K2Z)682
+961)25P
+FT4)2RJ
+SCW)P4C
+7QD)L3G
+K2T)J8P
+948)NFS
+FB9)M3G
+7J9)JLP
+T44)PGK
+RFG)BKG
+NBJ)DZL
+6RR)BLV
+MCF)5F9
+83D)X5V
+X3Z)Q8H
+1HP)Y7X
+THT)S1K
+2DL)Z75
+9YN)KD7
+SKM)6LN
+VRY)3RX
+ZCB)66N
+T95)THD
+SYS)3FL
+2TK)H9F
+CH7)P49
+LYT)XDG
+FF3)LTR
+92Q)C8J
+ZRB)MB8
+MLT)GK7
+2D1)534
+2Q9)1GT
+4MP)H4Z
+VB9)HJJ
+RBR)WFF
+Y2N)XZS
+D2F)FMW
+4R6)PJY
+2TK)R7K
+F8N)ZJ8
+R99)4B6
+WDW)ZXK
+YJM)LWY
+CFR)Y1C
+3YF)3L3
+MT1)LYT
+6GC)ZX4
+LJ6)LWN
+FH1)PP2
+L89)Z9V
+3W9)BDW
+ZYT)RS5
+GK7)DNV
+2RJ)THS
+KGV)N5R
+KF8)P78
+DM1)2QX
+FDZ)LTT
+6BG)LRC
+HFL)GXZ
+LQY)B5J
+YD8)7XZ
+6BQ)Y1R
+MQ9)46Z
+DMQ)BZN
+F8L)KGV
+CG8)YJM
+3Q6)JT6
+F1T)SX8
+GL3)NWX
+PTR)4MP
+LWY)S92
+CQ5)1XY
+TM4)8DK
+M7B)D1G
+27S)YD8
+2MY)5LF
+MYK)RBR
+9ZB)KZF
+4G3)CFR
+52N)RS9
+9PF)687
+CGL)XQZ
+JRY)T9W
+GYT)MMC
+JWP)KZ5
+TTD)QBG
+5LF)53T
+C9C)XBY
+1JF)F8N
+WQM)QHS
+17L)3MX
+5BP)7FJ
+531)D2D
+7X9)YMW
+9XQ)B6Q
+6QG)RHS
+GQF)W6N
+R3T)SQ3
+PRL)KL3
+4XW)N2S
+1QH)V5H
+MXH)82H
+8GN)KJT
+Y7D)8VF
+H8K)9GG
+XFM)6B5
+R1C)GYT
+QG4)YBY
+8CR)CKP
+R74)ZNT
+H9F)RKT
+SJN)7FZ
+3VH)RSQ
+BWB)SF1
+H6V)Y1G
+ZVG)HFL
+VHL)TG2
+KNJ)CHP
+COM)YCD
+X4G)6BG
+T62)XM8
+QKZ)YPJ
+P1X)5F8
+7RX)VXM
+V93)9S5
+HKY)5ZW
+QLR)GZZ
+N41)WPZ
+D94)J9X
+SHQ)STJ
+N3P)W37
+L9Y)K3X
+9T5)HVD
+L7M)JYG
+FBZ)CBW
+L78)N12
+R6M)2Q9
+YJN)HDT
+F92)9DM
+WPZ)ZT2
+GF3)XDB
+PCL)HPZ
+3TN)NMH
+S5D)JKP
+KC2)MGQ
+MYN)KJF
+BZN)7X8
+VQY)WB1
+73H)61M
+6WW)73B
+Y1G)SRS
+D4C)ZRB
+4JT)LK4
+79C)PVF
+Z5K)6QG
+7RG)QNJ
+RLM)D26
+1Z9)58H
+655)JD3
+GFV)S8S
+XF3)SZW
+X6T)B57
+RFG)T6X
+TC6)MCF
+RYF)7J9
+4GK)17L
+PW2)441
+KGY)S75
+YD8)LJ6
+W5W)SHQ
+BDP)K2T
+B9Q)4JT
+JYX)ZL9
+8HW)BBN
+QSJ)MT5
+T18)GZC
+GZD)T5J
+VXM)3WS
+PGM)N41
+WPB)CSZ
+4WW)PMQ
+M37)L4B
+ST4)1XQ
+7T9)9YN
+5NW)RLM
+17N)R8S
+8XZ)7RX
+CKD)5VM
+CBW)83D
+LM1)H6Q
+K2Y)656
+1VZ)NKV
+DT8)PPB
+N7M)FT4
+P2K)5J1
+HGB)FDB
+BLF)L89
+37S)MYD
+FFC)YCF
+K4Q)77S
+6JF)VVP
+KLM)8T1
+N7M)5V5
+FRW)6BQ
+B78)35G
+91D)W3W
+34Z)Z3J
+WB1)DY8
+L4B)NBJ
+N5R)PY8
+SVK)R1C
+FX2)QSL
+N2S)T62
+82H)F6M
+7FZ)B64
+9JZ)8TM
+4TM)Q5T
+84W)57M
+5CL)355
+4W4)KTK
+23R)V8K
+LTT)CQ5
+SZW)3GH
+XRM)PTR
+BT5)Q5H
+QJ1)XF3
+V9C)ZYT
+Y1G)NYQ
+DN6)9GX
+5ZW)3VH
+7LP)5D4
+NWX)6VP
+D26)BW5
+MT5)MMM
+QMY)4LX
+73B)CGK
+PF5)H9Q
+MB7)KB1
+WTR)1YS
+HPZ)FRW
+KWJ)XR4
+8RN)9T5
+KTK)QLR
+TFQ)VQY
+Q97)3YP
+452)L19
+T33)WJ9
+QG4)459
+6WP)QMY
+KD7)G1M
+YGC)QF3
+67W)DT8
+RK8)TBP
+JKZ)MQ9
+KHP)M4P
+3RX)MXL
+7XZ)VRY
+GZC)T3X
+S99)5RY
+441)GL3
+38N)P2K
+37J)Z5K
+GTT)5G4
+QHT)4GJ
+1PV)961
+5RN)3JQ
+H4P)8CR
+SSW)LSP
+S58)SAN
+YHL)PQL
+Q8M)9NV
+FKZ)VJR
+T8J)3TN
+4PC)PCL
+RS9)THT
+3FM)FFJ
+8DK)RYF
+XTQ)92W
+P78)CFW
+BW5)PRL
+S75)G2N
+JKN)3QG
+J7G)MD9
+SWJ)52N
+S8S)9L3
+H8X)K2Y
+W1R)9PF
+5SX)RK8
+1HP)3V4
+ZCB)BLF
+88M)ZGM
+QHS)Z6Z
+DNV)H6S
+SPZ)R9K
+Z7M)JKZ
+R7V)TJB
+WRF)HFN
+5JM)DJH
+ZN2)RSH
+61M)PGM
+CBN)8NX
+RRW)3SH
+LYM)92Q
+RJK)XRM
+534)S8T
+CP1)KNJ
+8XZ)C56
+SZW)JHV
+H9F)5RN
+SX8)1L1
+74B)4XW
+1GT)WDW
+64W)PTS
+158)7B1
+2S3)VFY
+TJT)43T
+35G)MXP
+YY6)R6M
+V53)64C
+Y29)8WD
+QF3)T44
+4GJ)W1R
+K4Q)CP1
+GR4)Q1P
+K6J)HHR
+R6H)1S1
+XMH)GHQ
+BWP)ZJ7
+274)HKY
+553)LLP
+T5J)1KT
+Q5H)LYM
+HQ1)HXW
+1GT)PQZ
+PPB)TM4
+NWG)VXQ
+P23)Y14
+2PS)37S
+2V1)VGY
+MYD)2R4
+1L1)D85
+XDG)39V
+MR1)78T
+VFK)HN7
+6W5)JHS
+F32)698
+GRB)33M
+GX6)SSL
+L71)T18
+Y7X)6HM
+JKN)7Z9
+YBY)17N
+V29)DP4
+FN3)2DJ
+33Y)K55
+Y63)N9H
+T8W)TFQ
+XYN)M6D
+KSQ)RV4
+66N)3W9
+Y1R)79C
+TG2)MT1
+QVR)5DC
+3JJ)QKM
+698)RNB
+6VP)655
+8L8)4G9
+RS5)VK9
+D85)44G
+225)7X9
+QPD)VG9
+39V)5TV
+T7S)K4Q
+LV1)21W
+8R4)6WW
+2PR)JRS
+D1G)19G
+7G2)K6J
+2SY)5CL
+QPZ)QHT
+3SH)H8K
+123)YGC
+7B1)1XC
+SK7)8GN
+RNB)5TG
+3JQ)WKF
+SF1)KC2
+P49)JGH
+4HQ)X6T
+QH4)32W
+Y8B)Q7W
+SK4)4XH
+WYS)CQ3
+33M)FBZ
+R56)635
+CFW)1DL
+4L5)R95
+6QH)PFR
+7Z9)91Z
+RDQ)CKV
+PVF)MFC
+MMM)73H
+BHH)LK9
+Q5T)FX2
+JHV)6WB
+8TM)931
+JYG)VRC
+DXD)Q91
+XQ3)R6H
+5RL)CKD
+92W)F31
+SQ3)JYX
+Z6Z)XQ3
+5RF)P23
+DP7)QVR
+HXW)C1F
+3SH)FVW
+WV7)5NW
+PNZ)RM4
+C56)TS1
+BVV)F97
+9S5)H5L
+355)9GD
+YQC)DWZ
+FPW)F9K
+459)HQ1
+YPJ)F1T
+XZS)8RN
+5V5)DMQ
+9HH)3JJ
+GZZ)1J8
+C41)DHC
+H3D)KSQ
+J6C)WQD
+WM3)CZB
+J9X)7J7
+CKV)KHJ
+53L)96R
+PSR)5BP
+7X8)TXF
+SCW)XC2
+DZL)S58
+Z9V)LZF
+FD8)X4G
+9TD)Y31
+M4P)LS4
+3GH)QKZ
+S58)DXN
+258)452
+31B)DXD
+GL3)2MY
+9GG)64M
+NYQ)9ZB
+RM9)3Q6
+1S1)6GC
+431)W3V
+W3V)CSN
+QDH)234
+52N)MXH
+QNJ)1Z9
+WJ9)1JF
+6WY)CH7
+21W)JJR
+Y31)5QB
+K4V)QPD
+TS1)8VX
+GR6)HLJ
+1KT)7Y5
+PSX)64W
+YJN)R99
+PTG)CM7
+1XC)C32
+M1T)G48
+7XW)TW6
+Q7W)TYV
+ZWB)X9K
+YGM)2Y3
+3GH)C1J
+6ZQ)4W4
+BY7)WRB
+BBN)CX6
+1XQ)ZC6
+G2N)RRW
+DT8)7QT
+RSH)P2F
+JGH)ZGL
+XC2)8HW
+MD9)JPQ
+S92)DFS
+B43)PL5
+C1W)MYN
+QQP)2SY
+SRY)S3L
+3QG)XYX
+XBY)XYN
+LS4)53L
+V8K)FH1
+LZF)SRV
+1DL)HDR
+Y5H)RM9
+931)R77
+LYR)666
+DFS)C4D
+Z28)Y7D
+H6B)M1T
+CSN)TBD
+VMP)5DP
+91D)KHP
+PLH)LV1
+PGK)DB4
+2QX)93G
+TJB)Z7M
+W9K)L71
+C8J)9TD
+PN7)8JC
+94X)FD8
+GWY)258
+RM4)L64
+WPB)1HP
+1J8)H6B
+NZ5)YY6
+4B6)2PR
+9NV)W5W
+6LN)SJN
+GF8)RDQ
+P6S)HJ8
+G2N)6WP
+F92)BVV
+JV7)TQL
+Q91)PCG
+PFR)KF8
+Q1P)7BP
+L64)6WY
+ZRD)PWW
+HFN)88M
+MZN)SYS
+PQL)Y26
+234)225
+VVP)37J
+PL5)T11
+CGK)PTG
+LZY)Z8V
+N9H)P6S
+CZQ)FBR
+TBP)MLT
+LLP)6S5
+YTT)9Q6
+H6S)SPZ
+R9K)XMH
+6PY)PLR
+4PC)HBK
+WFF)W9K
+P2F)FTY
+F97)SK7
+YCD)M6H
+2CR)84W
+LSP)GTT
+Z3J)QQP
+CCF)QJ1
+YW5)B68
+7FJ)83Q
+QKM)GQF
+ZJ7)752
+Y5H)83G
+Y14)V53
+5G4)LHR
+GZZ)MR1
+46Z)4HQ
+T6X)FMD
+FBR)R74
+Q8H)3WR
+SVK)FKZ
+YXD)H4P
+NKV)WM3
+RDQ)GF3
+L3G)CP3
+HN7)VHL
+HBK)G8C
+WRB)WLY
+1V8)M37
+KHJ)BHH
+GL4)D94
+XR4)S5D
+XM8)ZWB
+5RY)2XT
+FCM)5DS
+KZ5)XXB
+T91)Y8B
+KNJ)F8L
+D2D)ST4
+QQ6)TC2
+GF3)RJK
+69P)7GT
+Y26)TJZ
+B5J)8L8
+NMH)4YK
+SXJ)9S2
+752)CBN
+ZGM)NZ5
+S1K)MZN
+MMC)Y29
+7QT)LM1
+8NX)JZG
+R95)GR4
+ZXK)QQ6
+DNX)158
+QRX)GR6
+LRC)L7M
+X5V)SK4
+D4C)Y2N
+83Q)134
+GST)LQR
+R7K)6RR
+4G9)M8F
+C32)5SX
+YMW)RPN
+HHR)S99
+5D4)C9C
+SSL)KWJ
+FPW)H6V
+JT6)Q8M
+53T)QDH
+4YK)B42
+VFY)KLM
+HVD)SCW
+88F)V93
+6S5)5JM
+R8S)YBP
+2R4)C8G
+8VF)WYS
+CSZ)SSW
+JRB)WXM
+ZT2)7HZ
+KJT)9DV
+M8F)SKM
+N12)SXJ
+MD9)6QH
+9GD)7T9
+ZC6)LQY
+H6Q)R56
+S8T)27S
+B68)VFF
+P9B)88F
+666)PNZ
+MXL)NZY
+3MX)2M7
+3WR)T8J
+DNB)VC7
+84R)XNZ
+656)K4V
+BSK)FLM
+MB8)B43
+K3X)D2J
+7J7)JDF
+Z44)JMX
+QF3)FCM
+5F9)VKQ
+GXZ)1SF
+4JT)4PC
+W3W)R3T
+PMQ)69P
+3YF)9HH
+L74)CGL
+8T1)VPX
+Y26)9XQ
+635)SSP
+7BP)PF5
+9L3)WPB
+JLP)YOU
+25P)7RG
+4R6)YJN
+9GD)PSX
+T3X)XFM
+8JC)CCF
+RPN)6FZ
+NZY)67W
+NXG)GL4
+6YN)6NP
+GX6)RQK
+G48)5RL
+CSZ)GX7
+YBP)P1X
+KJF)CG8
+43T)B78
+Y5V)SSH
+DJH)2DL
+KL3)QN4
+5DS)4WW
+VG9)84R
+B64)8M8
+6FZ)94X
+ZL9)Y5V
+68Y)MYK
+M7Y)JRY
+QSJ)K2Z
+JJR)J7G
+MXP)1QH
+M6H)WRF
+64C)FFC
+PJY)HGB
+ZGL)LKH
+687)PSR
+7QD)TTD
+FLM)QH4
+57M)ZRD
+WQD)JRB
+STJ)N7M
+RHS)2D1
+NFS)V9C
+P4C)NH1
+ZJ8)431
+D2J)H8X
+JDF)C41
+64M)H1Z
+JRS)T95
+WXM)GRB
+MK2)8W1
+6NP)D4C
+N2C)SWJ
+TBD)JKN
+PTS)FN3
+1SF)VJV
+6WB)VB9
+F9K)M7B
+134)1V8
+RSQ)GVK
+S3L)V29
+4SY)DM1
+FCM)4G3
+QN4)T33
+FDB)WKK
+PQZ)LZY
+HS9)MB7
+CHP)74B
+LHR)TRV
+7Y5)NXG
+QBG)JWB
+ZWF)T6Y
+WKF)BWB
+4XH)4R6
+JWB)GRL
+DWZ)D2F
+THD)4DJ
+H1Z)GWS
+KZF)CCN
+VGY)L78
+MDX)RFG
+HJ8)38N
+L9Y)C1W
+C8G)VFK
+1KT)PLH
+CCN)Q97
+8VX)WTR
+RVX)H3D
+PCG)PDC
+58H)7XW
+MYK)77T
+B42)N3P
+CKP)HH3
+PY8)HS9
+844)T91
+GHQ)YQC
+C1J)GX6
+FMW)Y63
+9DM)68Y
+FFJ)ZVG
+CGK)274
+CX6)NWG
+JPQ)VMP
+H5L)BDP
+VRC)MK2
+CCX)948
+JHS)ZWF
+B6Q)6W5
+R77)FDZ
+VJR)FPW
+S1Q)GLD
+XDB)P9B
+3WR)33Y
+DZL)T8W
+8M8)LYR
+TW6)T7S
+4PR)7LP
+ZNT)553
+5F8)S5F
+XNZ)F43
+32W)N7K
+5TV)PW2
+BKG)91D
+8W1)SRY
+5VM)2S3
+M6D)CCX
+77S)BSK
+G8C)CZQ
+DXN)23R
+LQR)GWY
+SHQ)YGM
+9DM)SVK
+ZYT)YXD
+KL4)QG4
+HDR)XSH
+77T)DN6
+HH3)BT5
+SSP)QJ8
+5G4)ZN2
+6HM)H41
+JMX)7QD
+B57)DWB
+3V4)M7Y
+HJJ)6PY
+WLY)QPZ
+G1M)ZCB
+VFF)VGC
+VJV)X3Z
+W37)GFV
+X3Z)HGT
+FVW)8R4
+XYX)6ZQ