From bf5747e9925988c8cf053f974fdcc35ca76df361 Mon Sep 17 00:00:00 2001 From: Gard Spreemann Date: Sun, 11 Dec 2022 16:14:28 +0100 Subject: Days 8 and 9 --- 08/Cargo.toml | 15 + 08/input.txt | 99 +++ 08/src/part-1.rs | 91 +++ 08/src/part-2.rs | 90 +++ 08/src/tensor.rs | 171 +++++ 08/test.txt | 5 + 09/Cargo.toml | 15 + 09/input.txt | 2000 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 09/src/part-1.rs | 59 ++ 09/src/part-2.rs | 65 ++ 09/test-1.txt | 8 + 09/test-2.txt | 8 + 12 files changed, 2626 insertions(+) create mode 100644 08/Cargo.toml create mode 100644 08/input.txt create mode 100644 08/src/part-1.rs create mode 100644 08/src/part-2.rs create mode 100644 08/src/tensor.rs create mode 100644 08/test.txt create mode 100644 09/Cargo.toml create mode 100644 09/input.txt create mode 100644 09/src/part-1.rs create mode 100644 09/src/part-2.rs create mode 100644 09/test-1.txt create mode 100644 09/test-2.txt diff --git a/08/Cargo.toml b/08/Cargo.toml new file mode 100644 index 0000000..644d264 --- /dev/null +++ b/08/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "day-08" +version = "0.1.0" +authors = ["Gard Spreemann "] +edition = "2021" + +[[bin]] +name = "part-1" +path = "src/part-1.rs" + +[[bin]] +name = "part-2" +path = "src/part-2.rs" + +[dependencies] diff --git a/08/input.txt b/08/input.txt new file mode 100644 index 0000000..d46e623 --- /dev/null +++ b/08/input.txt @@ -0,0 +1,99 @@ +313213123212200312011243203120214010202554420335045116203101005212525131015305511140012431022113113 +222021333112322244231542054023354511304431216312534453560105660253445311020244233130144313440030322 +200012220300132310233100025524032003355144536126232161330106115213441450552235514000243120210031130 +102111124044033113241415155401056014506203413216651520206613342353052505445000321043121021430440021 +221134021010031320101542213340113552161113350123516154134654046250223033000413443321231233142213010 +112241233114245202523201433013460320664034202602144006022621253536213222400131120345151014014131133 +132211130114141401325141212460540656525106651152012063404633651340223361443201520054113541144043031 +323140320024314005210155316202152552621415660063112177564603241212312025036551350313225504314404112 +014013242041230510442265205625331115540222744516266167254216354043533020346502032534231121044441220 +233414030101315255335126055263144512111777464611565216157441673706100506241423030403420343112342030 +133144314412553330012446404244433465434666762135116677765213463444460612511131340332552424201204120 +010320402332512110363213044530335655613562223756572424746437567672262256431540210005310544243444101 +324403411232230200215144254550257275144535323452276762234354361552536153612012260502425410505314212 +044143021304533036524115200363122146144443357746134567133417572143572217253466665420004544002052304 +031301205442313664253200353721523337451137554555385833341715227554331566151244334446363035232422032 +412021132254126340642250212415471513377143653545744364662761514364426436251422450305502445230351142 +423013525424334650512351242132544127615655738268233852527877887577454317715373566210510633013145020 +314013042244622602006117664713652263528475833433263846468763678447134716635345050225504112315124312 +210530032555051320514661111414734263472852682724485772623266565822423365264512541061226540103142223 +202523210140346233027372362557125436368725536228624865344774378537888747171665564143331101501212340 +312102150200503360534132445517484678583587678756766763747725475724228724317675166660536246102044404 +014501150514404506226424155762432386227846258625478334768375862827476433553651311460116133631440213 +145345025402132601222234271268834838244287765994936689397836424284644676342577451356463132062234232 +030520533600060465674743543832435622275594666933473957864637427284284528866426734257033413611153542 +111125222126126664625217555874224623337857863456948836785373353757744683247375632677514312554402024 +454344234313551645731724622525365832657894545768964536939387863978465673442253722125752553236132004 +141351656653224237252122854224855258938593946648537669944575478986734723225856761571634036114323202 +301354130411223555466416844555847677853855433636774857897563386873392265447728545634555234214003555 +324351500351156142554654722557458488698547355994463766454687489898485753473777574124613414652504004 +000202526603566624271288867428799685358698759656849978553895836996388433252545546266753551322305123 +142140450656776227714466585833798874975635767795445874946645465477849772464684527525213236023524220 +324262353505673315724236445748536388973668654588599896854469535494838643744387872721615221063235321 +552206463167666154577658258569744567339446596474586868848866645743399869362886626547344767533546153 +352323434663437355725427826449799477395999565764668865854945787936654594832633678767541225131001503 +440166362233562667478335763956389857755767497475848959778498799895595785387844464757513162265652640 +104122124642766642664452283555537376598457767558647554969995685645795999475473687336165523560052001 +255352243015641217534667849769975859955778464876555786747474774794864778373768452562637255330444232 +456220432747476336866782246873698697677699688678997975678548856759743777979632262638565415133210633 +354641641663166247236463863687744889449497969668886767686756898498698544578857834482516366746042103 +125201564115437683566423743488648645944969969766988857659599646944656843556585768447477145122536100 +565166453317161563746425435958546648857589858689866779576599554476785965354884443284615264253254316 +121246126671552573824643637663796768749697876859599686798755755668478994537789677336675255111501306 +360355134677155672632437676667797548778989878956585555755888869798448799556895227877387243567410342 +201045427623176635776469999883749944896899977995889968875595559556975886998744463243563112165201326 +352250115546124536536769454447786744475757988989886986985776968688899563536676844455461472345336201 +444012305276547277522595375654994558855859877987996678887769879954854599865599846623773465534004160 +003621673437674224248486547979885878957565757686996887766986595599447858644667462254244517674205046 +045265132276456334554365893935749649965989576778789869677576755756899986563778785582684657425224532 +256151375615717542563666894835779554876779596976976699887778577957456866545674477228666746346403631 +161152464371764263643334333389748956969597666797767878866755966565484647664843525828682412373755454 +502011544714165463843278447485479797867666888668797796768977767569575788836334565474627531473704246 +151460364232447443233565968759985868786557997798976867676959589967898874545836432537554441566122314 +325354014323767722264889584534897666569996596668678778968696799996649764974489874252576563221244356 +300165663442414468382638967476995984959988868887699967676597986577798947648889527728225341345144126 +523044146537227284236854867884546566896896589678689877799567996884747789569869374746443236356121631 +623520016256236672238393557665746588457977578897867867689877778857948885353767526367472655634211324 +513112323743777428355697564974758755988785986568979868979685685997847967586943842248473255451053311 +450020506764535784366644976997588757498856779786876686775868855996746554394579645638756632417635430 +333302106653766675873339799535474646879996789788987875587977755587884588498366525263657241244563411 +021603345313213632267754575346995947848565695878969885767869775868759846376874235783854235221066060 +451051105676415353834239879477689664878678578559658579558858859685656646333643282578751361221450043 +323133151167312457234657559765757999468467698869969666865897797857485499569838464565771443341433624 +351226435216677645378442636393858569688464696659679658777559879978765539986842833528347477142364355 +312522015134552576843564246393479975856585945659576986575979678487794748787843877358147735663364153 +436221405132742616333723774335457748498747869445768557777496645469557694497322763335217424704452516 +531453464276746646458848784658447874499485559877948986585644748765566863496685884585514544145343261 +124004035175455643547236885494794479865464946999998568586788689967343377758845738571672264321061003 +200155306351543777457257657968974568856495865454798449784799858884637386375422526864243565062364102 +445601414321444235648773664866559437996644487476459565964785659539635568456223755627145663416360463 +450034302502443262354377457789598776596746648495968457946465588399656898646426472411777146341644150 +023146264504256441756645634487555664987468946766784647877558359936934483654774826324735714633603030 +333342045300642417421427522458538378785933374679488696549488964673985948667688553344343522163201010 +455545402043235615564685485576228935958544883643955984493945756635487843653852747147246556553523510 +521503005555124536565566284723484688885348465998948435535997783785742684873228712152117622054235215 +312504066020457274731625463858577544637764966338466339435677364997568623562286441516367015430243140 +205031053461063473777474186844553532897797357638539497889554739476455778658267742121765420506102155 +234254241452503617412556672484735427269749864873783849964559983463526474536714377341620430652445005 +005122256601541121767617243673775345873688335643477574686454362545566824655271216641353663405312143 +433412443503526366274346321587248483458325774873734889987843368227357425636513234740304061623033442 +150425005143315445343366357776572258884478742563678357783845862235758564513525337622046146253440425 +225155323264631456635462325511885764326675428846268646575225734474437376612544667111053406332354205 +035014011000365630427277363261244836668367562448734772533252234588746775752633154601553624254020455 +012332415442566650666617225747354638747746384682743326746678826728355131225614470132623462424342514 +013524113311511615516563562155256314453777643324383464236254565752742637247411046651633511302344051 +212122212430404140032134131564756752725322885466434352224875446515552517267614410524244004301240143 +311400235445132520254065617566464245641623888587556667385287735312776421161334445544251524420400232 +440215452341344043062300567544524332733611636552822742567416277354477557756312354353622415135520342 +212430430313114143406656305336551452762327233736172563224242725162751616161102623013055041203553040 +321010353433305435042151016603142762425754273737777221111751751754217734105034366116400050235001301 +141012030043441152515110066520525231112547624256173331346341451761472053411546323404310404443302411 +133133034522454043232213312145664546126452755453724144154261454733124054403605004150535010413000334 +331412441152240551104612131344064131112564126362561532523311462604061151623121543003234021543312303 +010301442302500534021525552205536466144454523741535255444641345430402356234514221410435324321440211 +222301014410242404221240250563134040056104626021173454550103400400616550340400310015454450242211021 +233412422204111420244300456264320032401430366334634641441411125102262216452333414201235210001133200 +132244430320123233143125240232350142156620032556633233042303530460352401020133104323414224314240333 +003213243020203044035550441012322051645661162162123160565554312321050133555533333123214002014231123 +000032030402033315113220225514041611664662663525144303562161423513133325130431534323303033322212313 +101211324120322333355055001035515221630532526633042003421442155144120444232152535003241233413001002 diff --git a/08/src/part-1.rs b/08/src/part-1.rs new file mode 100644 index 0000000..1bbd75a --- /dev/null +++ b/08/src/part-1.rs @@ -0,0 +1,91 @@ +mod tensor; + +use std::io::{BufRead}; + +use tensor::{Index, Shape, Tensor}; + +fn main() { + let stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let mut tmp: Vec<(i8, bool)> = Vec::new(); + let mut m: usize = 0; + let mut n: usize = 0; + let mut n_check: usize = 0; + + loop { + let buf = handle.fill_buf().expect("IO error"); + let bytes_read = buf.len(); + if bytes_read == 0 { break; } + + for & b in buf.into_iter() { + if b >= b'0' && b <= b'9' { + tmp.push(((b - b'0').try_into().unwrap(), false)); + if m == 0 { + n += 1; + } + n_check += 1; + } + if b == b'\n' { + m += 1; + assert_eq!(n_check, n); + n_check = 0; + } + } + + handle.consume(bytes_read); + } + + let mut x: Tensor<(i8, bool), 2> = Tensor::new_from([m, n], tmp); + let shape = x.shape().clone(); + let mut tallest: i8; + + // Look north-south. + for j in 0..shape[1] { + // Look from north. + tallest = -1; + for i in 0..shape[0] { + let tree = &mut x[[i, j]]; + if tree.0 > tallest { + tree.1 = true; + tallest = tree.0; + } + } + + // Look from south. + tallest = -1; + for i in (0..shape[0]).rev() { + let tree = &mut x[[i, j]]; + if tree.0 > tallest { + tree.1 = true; + tallest = tree.0; + } + } + } + + // Look east-west. + for i in 0..shape[0] { + // Look from west. + tallest = -1; + for j in 0..shape[1] { + let tree = &mut x[[i, j]]; + if tree.0 > tallest { + tree.1 = true; + tallest = tree.0; + } + } + + // Look from east. + tallest = -1; + for j in (0..shape[1]).rev() { + let tree = &mut x[[i, j]]; + if tree.0 > tallest { + tree.1 = true; + tallest = tree.0; + } + } + } + + let num_visible = x.data().into_iter().filter(|(_, vis)| *vis).count(); + println!("{}", num_visible); +} diff --git a/08/src/part-2.rs b/08/src/part-2.rs new file mode 100644 index 0000000..94bf4d5 --- /dev/null +++ b/08/src/part-2.rs @@ -0,0 +1,90 @@ +mod tensor; + +use std::cmp::{max}; +use std::io::{BufRead}; + +use tensor::{Index, Shape, Tensor}; + +fn main() { + let stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let mut tmp: Vec = Vec::new(); + let mut m: usize = 0; + let mut n: usize = 0; + let mut n_check: usize = 0; + + loop { + let buf = handle.fill_buf().expect("IO error"); + let bytes_read = buf.len(); + if bytes_read == 0 { break; } + + for & b in buf.into_iter() { + if b >= b'0' && b <= b'9' { + tmp.push((b - b'0').try_into().unwrap()); + if m == 0 { + n += 1; + } + n_check += 1; + } + if b == b'\n' { + m += 1; + assert_eq!(n_check, n); + n_check = 0; + } + } + + handle.consume(bytes_read); + } + + let mut x: Tensor = Tensor::new_from([m, n], tmp); + let shape = x.shape().clone(); + + let mut highest_score: usize = 0; + + for i in 0..m { + for j in 0..n { + let h = x[[i, j]]; + + // Look north + let mut north_dist = 0; + for a in (0..i).rev() { + north_dist += 1; + if x[[a, j]] >= h { + break; + } + } + + // Look south. + let mut south_dist = 0; + for a in i+1..m { + south_dist += 1; + if x[[a, j]] >= h { + break; + } + } + + // Look east. + let mut east_dist = 0; + for a in j+1..n { + east_dist += 1; + if x[[i, a]] >= h { + break; + } + } + + // Look west. + let mut west_dist = 0; + for a in (0..j).rev() { + west_dist += 1; + if x[[i, a]] >= h { + break; + } + } + + highest_score = max(highest_score, north_dist*south_dist*east_dist*west_dist); + } + } + + println!("{}", highest_score); +} diff --git a/08/src/tensor.rs b/08/src/tensor.rs new file mode 100644 index 0000000..2635886 --- /dev/null +++ b/08/src/tensor.rs @@ -0,0 +1,171 @@ +#![allow(dead_code)] + +pub type Shape = [usize; D]; +pub type Index = Shape; + +pub struct Tensor { + data: Vec, + shape: Shape, + strides: Shape +} + +pub type Tensor1 = Tensor; +pub type Tensor2 = Tensor; +pub type Tensor3 = Tensor; +pub type Tensor4 = Tensor; +pub type Index1 = Index<1>; +pub type Index2 = Index<2>; +pub type Index3 = Index<3>; +pub type Index4 = Index<4>; + + +impl Tensor { + pub fn new(shape: Shape, x: T) -> Self { + if D == 0 { panic!("Empty shape not allowed."); } + + let mut len = shape[D-1]; + let mut strides: Shape = [0; D]; + strides[D-1] = 1; + for d in (1..D).rev() { // d=D-1, …, 1. + strides[d-1] = shape[d]*strides[d]; + len *= shape[d-1]; + } + if len == 0 { panic!("Empty dimensions not allowed."); } + + Self { + data: vec![x; len], + shape: shape, + strides: strides, + } + } + + pub fn new_from(shape: Shape, x: Vec) -> Self { + if D == 0 { panic!("Empty shape not allowed."); } + + let mut len = shape[D-1]; + let mut strides: Shape = [0; D]; + strides[D-1] = 1; + for d in (1..D).rev() { // d=D-1, …, 1. + strides[d-1] = shape[d]*strides[d]; + len *= shape[d-1]; + } + if len == 0 { panic!("Empty dimensions not allowed."); } + + if len != x.len() { panic!("Vector of length {} cannot fill tensor with {} entries.", x.len(), len); } + + Self { + data: x, + shape: shape, + strides: strides, + } + } + + + #[inline(always)] + fn flatten_idx(self: & Self, idx: & Index) -> usize { + // NOTE: This is a very hot code path. Should benchmark versus explicit loop. + idx.iter().zip(self.strides.iter()).fold(0, |sum, (i, s)| sum + i*s) + } + + fn bound_check_panic(self: & Self, idx: & Index) -> () { + for d in 0..D { + let i = *(unsafe { idx.get_unchecked(d) }); + if i >= self.shape[d] { + panic!("{}-dimensional tensor index is out of bounds in dimension {} ({} >= {}).", D, d, i, self.shape[d]) + } + } + } + + pub fn in_bounds(self: & Self, idx: & Index) -> bool { + for d in 0..D { + let i = *(unsafe { idx.get_unchecked(d) }); + if i >= self.shape[d] { + return false; + } + } + true + } + + pub fn shape(self: & Self) -> & Shape { &self.shape } + + pub fn el(self: & Self, idx: & Index) -> Option<& T> { + if self.in_bounds(idx) { Some(unsafe { self.el_unchecked(idx) }) } + else { None } + } + + pub unsafe fn el_unchecked(self: & Self, idx: & Index) -> & T { self.data.get_unchecked(self.flatten_idx(idx)) } + + pub unsafe fn el_unchecked_mut(self: &mut Self, idx: & Index) -> &mut T { + let flat_idx = self.flatten_idx(idx); + self.data.get_unchecked_mut(flat_idx) + } + + pub fn flat_len(self: & Self) -> usize { self.data.len() } + pub fn size(self: & Self) -> usize { self.flat_len()*std::mem::size_of::() } + + pub fn fill_with(self: &mut Self, x: & [T]) -> () { + // Already panics on size mismatch. + self.data.copy_from_slice(x) + } + + pub fn fill(self: &mut Self, x: T) -> () { + self.data.fill(x); + } + + pub fn data(self: & Self) -> & [T] { & self.data } +} + +impl Tensor { + pub fn dirty_print(self: & Self) { + for i in 0..self.shape[0] { + for j in 0..self.shape[1] { + print!("{} ", self[[i, j]]); + } + println!(""); + } + } +} + +impl std::ops::Index> for Tensor { + type Output = T; + + fn index(self: & Self, idx: Index) -> & Self::Output { + self.bound_check_panic(&idx); + unsafe { self.el_unchecked(&idx) } + } +} + +impl std::ops::Index<& Index> for Tensor { + type Output = T; + + fn index(self: & Self, idx: & Index) -> & Self::Output { + self.bound_check_panic(idx); + unsafe { self.el_unchecked(idx) } + } +} + +impl std::ops::IndexMut> for Tensor { + fn index_mut(self: &mut Self, idx: Index) -> &mut Self::Output { + self.bound_check_panic(&idx); + unsafe { self.el_unchecked_mut(&idx) } + } +} + +impl std::ops::IndexMut<& Index> for Tensor { + fn index_mut(self: &mut Self, idx: & Index) -> &mut Self::Output { + self.bound_check_panic(idx); + unsafe { self.el_unchecked_mut(idx) } + } +} + +impl IntoIterator for Tensor { + type Item = T; + type IntoIter = std::vec::IntoIter; + + fn into_iter(self) -> Self::IntoIter { self.data.into_iter() } +} + + +// FIXME: Should have a proper IntoIter implementing IntoIter for &'a Tensor. + +// Note: Tensor is also sliceable (due to the Index implementations) diff --git a/08/test.txt b/08/test.txt new file mode 100644 index 0000000..16d6fbd --- /dev/null +++ b/08/test.txt @@ -0,0 +1,5 @@ +30373 +25512 +65332 +33549 +35390 diff --git a/09/Cargo.toml b/09/Cargo.toml new file mode 100644 index 0000000..100567b --- /dev/null +++ b/09/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "day-09" +version = "0.1.0" +authors = ["Gard Spreemann "] +edition = "2021" + +[[bin]] +name = "part-1" +path = "src/part-1.rs" + +[[bin]] +name = "part-2" +path = "src/part-2.rs" + +[dependencies] diff --git a/09/input.txt b/09/input.txt new file mode 100644 index 0000000..68e6657 --- /dev/null +++ b/09/input.txt @@ -0,0 +1,2000 @@ +D 1 +L 2 +D 2 +L 1 +R 1 +D 1 +R 2 +U 1 +R 1 +D 2 +R 1 +L 2 +U 1 +D 2 +R 1 +L 2 +R 1 +U 2 +D 2 +L 1 +U 2 +R 2 +D 1 +R 2 +D 1 +U 2 +D 2 +L 1 +U 1 +R 1 +D 1 +U 1 +D 1 +U 2 +L 2 +R 1 +U 1 +R 2 +L 2 +U 2 +R 1 +L 1 +U 1 +L 2 +R 1 +D 1 +L 1 +D 2 +U 1 +D 1 +R 1 +L 2 +D 1 +R 2 +L 2 +U 1 +D 2 +R 2 +D 1 +U 1 +R 2 +D 1 +L 1 +U 2 +R 2 +D 1 +U 2 +R 1 +D 2 +R 1 +D 1 +U 2 +R 2 +U 1 +R 1 +U 1 +L 1 +U 2 +D 1 +R 2 +D 2 +R 2 +D 1 +L 2 +D 2 +L 1 +R 1 +U 1 +D 2 +L 2 +D 2 +L 1 +D 2 +R 1 +D 1 +R 2 +L 2 +R 2 +D 2 +R 1 +D 2 +R 2 +U 2 +L 2 +R 1 +U 1 +R 1 +U 1 +D 1 +U 1 +R 2 +L 1 +R 1 +D 2 +U 3 +R 1 +L 2 +D 1 +R 3 +U 1 +D 2 +R 1 +D 1 +R 2 +L 1 +R 2 +L 2 +D 3 +R 3 +D 1 +U 2 +D 2 +R 1 +D 2 +R 1 +L 3 +D 1 +L 1 +R 2 +D 3 +R 2 +D 3 +R 3 +L 2 +U 3 +D 3 +L 2 +R 3 +L 1 +U 1 +L 2 +D 2 +U 1 +D 2 +U 1 +D 2 +R 1 +U 1 +D 2 +U 1 +L 1 +R 2 +L 2 +D 3 +U 2 +L 3 +D 2 +U 1 +D 3 +L 1 +U 1 +D 2 +R 2 +U 1 +L 2 +D 3 +L 3 +D 3 +U 1 +R 1 +U 2 +D 1 +R 3 +L 1 +D 1 +U 3 +D 1 +L 2 +U 1 +L 3 +D 2 +L 2 +R 1 +L 3 +U 3 +R 3 +U 1 +R 2 +D 1 +L 3 +U 3 +D 3 +L 2 +D 1 +U 2 +D 2 +U 2 +R 3 +U 2 +L 1 +U 1 +R 2 +L 3 +D 3 +U 3 +R 1 +L 1 +U 1 +D 1 +U 2 +R 1 +D 3 +L 1 +R 3 +L 4 +D 3 +R 2 +U 3 +R 1 +L 4 +R 1 +L 3 +R 3 +U 2 +D 1 +L 3 +D 4 +U 4 +L 3 +U 4 +R 4 +L 1 +R 4 +D 1 +R 1 +L 3 +R 3 +L 1 +R 4 +D 2 +L 3 +D 2 +U 1 +R 3 +D 2 +L 3 +R 4 +L 3 +U 3 +D 3 +R 1 +D 2 +U 4 +L 1 +R 1 +L 4 +R 3 +U 1 +L 4 +R 1 +U 3 +R 1 +L 1 +U 3 +R 3 +U 2 +R 2 +L 4 +U 1 +R 1 +D 3 +L 2 +D 1 +L 3 +R 3 +D 3 +L 4 +U 2 +L 3 +U 4 +L 2 +U 2 +D 4 +L 3 +D 1 +U 2 +L 3 +R 4 +U 1 +L 4 +R 4 +L 3 +U 2 +D 4 +L 1 +R 3 +D 2 +L 3 +U 1 +L 3 +U 4 +R 2 +U 2 +R 1 +D 2 +L 4 +R 3 +D 2 +L 3 +U 3 +D 3 +L 1 +D 4 +R 3 +U 1 +R 3 +L 1 +U 3 +R 2 +D 3 +L 3 +U 3 +L 3 +D 5 +U 4 +L 5 +D 2 +R 1 +D 2 +U 5 +R 1 +U 2 +D 2 +R 4 +U 2 +L 3 +U 2 +R 5 +D 4 +L 3 +U 3 +D 1 +R 2 +L 3 +U 1 +R 5 +D 1 +U 2 +R 1 +U 3 +L 2 +U 5 +R 4 +D 5 +L 4 +D 4 +L 2 +U 4 +R 5 +L 1 +D 1 +R 2 +U 2 +D 5 +R 2 +U 4 +L 3 +D 2 +R 4 +L 1 +R 1 +L 2 +U 4 +D 4 +R 5 +D 3 +R 1 +D 4 +L 4 +U 5 +L 2 +U 2 +L 3 +R 4 +U 5 +L 4 +U 2 +D 1 +R 2 +U 4 +L 1 +U 3 +R 1 +U 5 +D 5 +U 4 +D 3 +L 3 +U 3 +D 2 +U 4 +R 3 +D 1 +U 5 +D 3 +R 1 +U 2 +R 1 +D 4 +R 4 +L 4 +U 1 +L 5 +R 3 +D 2 +U 2 +L 5 +R 1 +L 1 +U 3 +D 4 +R 5 +L 4 +D 5 +L 2 +U 1 +D 1 +U 3 +R 4 +D 4 +L 4 +U 3 +L 2 +D 2 +L 5 +U 1 +R 6 +U 4 +R 3 +D 2 +R 6 +D 2 +R 6 +L 3 +R 4 +L 3 +D 5 +U 2 +R 5 +L 5 +R 4 +U 6 +R 6 +D 1 +U 4 +D 4 +L 3 +D 2 +U 5 +R 2 +U 5 +D 2 +U 3 +R 2 +D 5 +R 2 +D 6 +R 1 +U 5 +D 2 +L 6 +U 2 +L 4 +R 6 +L 6 +D 6 +L 3 +D 5 +L 1 +R 5 +D 4 +L 4 +U 1 +R 3 +D 6 +R 6 +U 2 +R 4 +D 1 +R 4 +U 4 +L 6 +U 6 +D 6 +R 2 +D 2 +L 4 +R 6 +L 1 +U 5 +D 4 +U 4 +R 3 +U 1 +D 3 +R 6 +D 4 +U 5 +R 3 +D 5 +R 5 +D 4 +U 4 +D 3 +U 6 +L 1 +D 4 +U 6 +L 3 +R 3 +D 6 +U 4 +R 3 +L 3 +R 1 +D 6 +R 4 +U 2 +R 6 +L 3 +D 3 +L 4 +R 3 +L 4 +R 3 +U 4 +R 3 +D 4 +R 6 +D 2 +U 1 +D 2 +L 3 +D 4 +L 1 +D 5 +L 6 +U 4 +L 7 +R 6 +U 7 +R 7 +L 5 +D 1 +U 3 +R 6 +U 6 +R 2 +U 5 +R 4 +U 7 +R 1 +L 3 +D 7 +L 4 +D 6 +U 1 +L 1 +R 3 +D 2 +L 5 +R 1 +U 1 +L 1 +R 6 +L 6 +D 2 +U 3 +L 6 +R 6 +L 3 +D 3 +R 2 +L 1 +U 5 +R 6 +D 2 +L 5 +U 1 +D 4 +R 3 +L 6 +R 2 +L 4 +D 4 +R 5 +D 3 +R 2 +L 5 +U 7 +D 5 +L 3 +R 2 +D 5 +U 5 +D 2 +U 2 +L 2 +R 5 +L 2 +D 5 +R 3 +U 4 +R 4 +D 1 +L 6 +U 2 +R 7 +L 3 +U 4 +D 2 +R 5 +L 6 +R 7 +L 1 +U 5 +L 3 +U 7 +D 6 +R 3 +D 3 +U 7 +L 4 +R 2 +U 1 +L 1 +R 6 +D 5 +R 7 +U 4 +D 2 +R 2 +D 4 +L 1 +U 4 +D 2 +R 2 +D 5 +U 7 +D 1 +U 7 +R 3 +U 5 +L 1 +R 7 +L 2 +R 5 +U 5 +R 5 +D 4 +U 5 +L 7 +D 3 +R 5 +L 3 +R 1 +U 8 +L 4 +U 3 +D 4 +U 1 +L 2 +D 5 +L 5 +D 4 +U 3 +L 2 +R 3 +D 6 +L 4 +U 3 +R 1 +U 1 +D 3 +R 5 +D 4 +L 7 +U 7 +R 7 +L 6 +D 7 +U 5 +L 2 +U 4 +R 8 +L 4 +U 4 +R 5 +U 1 +R 1 +D 7 +R 6 +L 8 +R 1 +D 4 +U 5 +R 6 +L 3 +R 7 +L 4 +D 7 +U 8 +R 5 +D 5 +U 4 +L 3 +D 4 +U 1 +L 8 +R 8 +U 2 +L 5 +R 7 +D 5 +L 5 +D 3 +L 5 +U 4 +D 1 +U 6 +R 7 +D 5 +R 4 +D 6 +U 4 +L 5 +D 8 +U 5 +L 7 +D 1 +U 8 +R 3 +U 4 +R 5 +U 7 +R 6 +L 3 +U 4 +L 7 +R 5 +U 6 +L 2 +R 2 +U 7 +R 4 +D 2 +L 2 +D 6 +L 5 +D 5 +L 1 +R 5 +D 1 +U 5 +L 8 +R 3 +D 4 +R 2 +U 2 +L 5 +D 4 +U 7 +D 9 +R 9 +U 9 +R 3 +L 2 +D 8 +U 6 +L 1 +R 1 +D 4 +L 9 +R 9 +L 3 +U 4 +D 7 +U 9 +D 5 +R 8 +D 6 +R 9 +U 2 +R 2 +U 8 +R 5 +U 6 +L 8 +D 7 +L 2 +U 3 +R 3 +U 6 +L 5 +R 4 +D 6 +U 6 +R 6 +D 5 +U 5 +D 6 +L 4 +D 2 +U 6 +L 8 +U 3 +D 6 +U 1 +L 7 +D 6 +R 3 +D 7 +U 6 +D 4 +U 5 +R 3 +D 7 +L 5 +U 6 +L 6 +R 2 +D 7 +L 7 +U 5 +D 9 +R 6 +L 9 +R 1 +L 6 +U 5 +R 4 +U 7 +L 2 +U 5 +L 9 +U 3 +R 2 +L 5 +R 2 +U 6 +L 3 +D 7 +R 9 +D 3 +L 4 +R 2 +D 8 +L 6 +D 9 +L 5 +D 1 +R 8 +D 4 +U 5 +L 7 +D 2 +R 2 +L 7 +D 6 +L 7 +R 1 +D 4 +U 3 +D 3 +U 8 +R 8 +L 3 +D 8 +U 7 +R 4 +D 9 +L 3 +U 10 +L 4 +D 4 +R 7 +U 1 +L 10 +U 10 +R 9 +U 3 +L 3 +R 1 +D 10 +L 4 +U 9 +L 4 +U 7 +L 8 +R 7 +D 1 +U 3 +L 3 +U 2 +R 4 +U 5 +D 9 +L 5 +U 10 +L 2 +U 1 +L 7 +D 9 +L 8 +R 10 +D 7 +U 9 +L 4 +U 10 +L 3 +U 1 +D 1 +L 1 +D 6 +U 8 +R 8 +L 6 +U 9 +L 3 +U 6 +R 6 +U 3 +R 7 +U 2 +D 4 +L 4 +R 8 +D 3 +R 8 +U 2 +R 3 +D 6 +U 4 +R 9 +L 4 +D 4 +L 6 +R 2 +D 10 +L 7 +R 9 +L 7 +D 8 +R 2 +D 2 +U 9 +R 2 +U 1 +R 10 +U 1 +D 2 +U 10 +D 10 +U 5 +R 3 +U 5 +R 10 +L 3 +R 5 +U 5 +L 4 +D 3 +L 7 +D 3 +U 10 +R 7 +L 3 +D 2 +L 1 +D 1 +L 7 +R 2 +L 10 +D 6 +R 4 +L 8 +R 9 +D 5 +L 2 +D 4 +R 1 +L 4 +R 8 +D 5 +R 10 +D 1 +L 10 +D 11 +L 10 +R 4 +L 3 +D 1 +U 4 +L 9 +D 6 +U 2 +R 4 +L 2 +U 5 +D 1 +R 6 +L 5 +U 7 +D 2 +R 5 +D 9 +R 11 +U 9 +D 9 +R 2 +L 9 +D 4 +U 7 +L 10 +D 7 +U 4 +D 1 +U 4 +D 10 +L 8 +D 3 +L 8 +D 8 +R 7 +D 10 +R 5 +U 1 +L 11 +D 2 +L 11 +U 4 +L 8 +D 10 +U 3 +D 11 +R 10 +L 1 +D 2 +U 11 +L 4 +U 2 +L 6 +D 7 +R 10 +L 2 +D 7 +R 9 +U 6 +D 5 +R 9 +U 1 +D 3 +R 8 +D 7 +L 3 +D 8 +U 4 +D 4 +R 8 +L 7 +R 1 +D 3 +U 7 +D 4 +L 10 +R 1 +D 6 +R 1 +L 5 +D 2 +L 9 +R 1 +U 5 +D 4 +U 11 +L 6 +R 11 +D 11 +R 6 +U 9 +R 1 +L 5 +U 3 +R 10 +L 8 +R 6 +L 2 +R 8 +D 11 +L 5 +R 3 +L 1 +R 3 +L 8 +R 10 +U 2 +R 2 +D 7 +L 9 +U 2 +L 8 +D 3 +U 1 +L 11 +D 1 +U 6 +L 2 +R 7 +D 5 +R 1 +D 11 +U 12 +D 10 +L 11 +U 3 +D 10 +L 6 +U 3 +D 12 +R 4 +D 9 +R 2 +U 12 +R 11 +L 2 +R 7 +L 11 +U 12 +R 12 +U 1 +R 2 +D 8 +R 10 +U 2 +D 8 +U 8 +D 5 +U 10 +R 4 +U 8 +D 4 +R 8 +D 8 +R 2 +U 4 +L 10 +D 2 +L 10 +R 2 +D 9 +U 6 +L 2 +D 10 +L 2 +D 11 +R 11 +U 2 +L 6 +D 3 +U 3 +R 4 +U 9 +L 9 +R 8 +D 5 +L 9 +U 8 +L 11 +D 8 +R 12 +U 1 +D 1 +U 7 +L 11 +U 2 +L 12 +R 11 +U 8 +R 12 +U 11 +L 7 +U 5 +L 4 +R 4 +D 1 +U 6 +D 7 +U 5 +R 5 +U 10 +D 2 +R 9 +L 12 +D 9 +U 6 +L 11 +D 7 +L 6 +D 10 +L 9 +D 11 +R 7 +D 10 +L 1 +R 9 +D 10 +L 1 +U 1 +L 13 +R 10 +D 9 +L 9 +U 7 +L 10 +R 1 +U 12 +R 13 +U 8 +L 9 +U 5 +L 11 +D 11 +U 8 +R 2 +D 2 +R 7 +D 3 +L 3 +R 2 +L 6 +U 11 +L 6 +U 8 +L 11 +U 12 +L 13 +D 4 +L 8 +U 11 +D 9 +U 11 +D 10 +U 4 +D 9 +L 12 +D 6 +L 11 +U 11 +L 1 +D 6 +R 12 +U 9 +D 1 +L 4 +R 9 +L 13 +R 10 +D 9 +L 2 +R 3 +D 10 +L 13 +R 3 +L 8 +R 8 +L 1 +R 5 +L 12 +D 10 +R 6 +U 7 +R 11 +U 11 +R 10 +D 9 +R 12 +D 8 +U 6 +L 8 +D 6 +L 10 +R 2 +L 2 +D 12 +U 12 +R 11 +L 8 +U 2 +R 2 +L 11 +U 11 +L 7 +D 2 +U 2 +L 9 +D 4 +R 2 +U 7 +D 3 +R 1 +D 6 +U 13 +R 11 +D 1 +U 4 +R 9 +D 7 +L 12 +U 12 +L 10 +U 9 +L 1 +D 1 +U 6 +L 1 +D 13 +U 14 +L 2 +D 6 +U 8 +D 8 +L 9 +D 1 +R 11 +D 6 +L 8 +R 11 +U 4 +L 5 +R 5 +D 10 +U 10 +R 7 +D 7 +L 8 +U 9 +R 1 +L 5 +D 4 +L 13 +D 4 +R 14 +D 13 +R 9 +L 13 +R 7 +L 14 +R 12 +D 1 +U 8 +L 10 +U 7 +D 9 +U 7 +D 13 +L 1 +R 1 +D 14 +L 9 +U 5 +R 7 +U 2 +L 11 +D 5 +U 7 +D 1 +L 13 +U 14 +L 1 +D 3 +R 3 +D 1 +L 3 +U 4 +R 14 +U 11 +R 4 +L 13 +U 3 +R 8 +D 5 +U 8 +L 6 +R 14 +L 3 +D 2 +L 5 +U 11 +R 8 +L 11 +U 8 +D 11 +U 14 +R 14 +L 4 +D 10 +R 11 +U 1 +D 4 +U 11 +D 5 +L 5 +R 14 +U 12 +L 1 +D 4 +R 11 +L 5 +R 9 +U 9 +D 2 +U 12 +D 2 +R 8 +U 6 +L 11 +U 8 +L 6 +U 9 +L 5 +U 3 +D 10 +R 10 +D 6 +U 1 +R 13 +U 5 +R 8 +U 11 +L 11 +D 10 +R 11 +U 2 +D 3 +R 10 +D 2 +L 9 +R 7 +L 8 +U 1 +R 6 +L 3 +D 10 +U 14 +D 4 +U 7 +L 6 +R 8 +U 15 +D 14 +U 5 +D 15 +U 2 +D 4 +L 11 +U 8 +L 10 +U 15 +R 8 +U 14 +D 6 +R 9 +L 15 +R 9 +L 11 +R 3 +D 2 +U 10 +L 12 +D 2 +L 5 +D 1 +R 8 +U 7 +L 7 +D 7 +L 15 +D 11 +U 3 +L 4 +U 10 +L 14 +U 10 +D 10 +U 11 +D 1 +L 3 +R 11 +L 3 +U 10 +L 2 +D 8 +R 8 +L 12 +D 15 +U 10 +L 14 +R 4 +L 9 +R 11 +U 10 +R 7 +D 13 +U 11 +D 10 +R 3 +U 6 +R 9 +L 15 +R 11 +D 6 +R 14 +L 7 +D 7 +L 3 +D 13 +U 10 +R 14 +U 2 +D 4 +U 1 +R 1 +D 8 +R 12 +L 15 +R 4 +L 15 +U 13 +D 12 +L 8 +D 1 +R 3 +U 11 +R 3 +U 2 +R 4 +D 15 +U 4 +L 6 +D 6 +L 9 +D 2 +L 15 +R 5 +U 2 +R 7 +D 7 +U 15 +L 4 +D 7 +R 9 +D 11 +R 8 +L 4 +R 6 +L 11 +U 16 +L 10 +U 10 +L 11 +U 9 +R 8 +U 13 +R 13 +L 5 +R 8 +L 12 +U 11 +L 4 +D 10 +R 2 +U 13 +R 4 +L 15 +D 15 +L 15 +R 16 +L 7 +R 14 +D 5 +L 16 +U 6 +D 3 +L 13 +D 8 +L 11 +U 13 +L 9 +U 6 +L 4 +U 11 +R 1 +L 13 +R 11 +L 13 +R 13 +L 9 +D 15 +R 1 +L 15 +R 14 +L 14 +U 7 +L 1 +R 6 +D 16 +L 2 +R 12 +L 4 +D 12 +R 8 +U 9 +D 10 +R 1 +L 2 +D 5 +L 3 +R 15 +L 8 +D 1 +L 1 +D 8 +U 13 +R 1 +L 2 +D 1 +R 3 +L 6 +U 12 +L 4 +D 13 +U 2 +L 4 +D 10 +R 16 +D 1 +U 1 +L 11 +D 8 +L 12 +R 8 +L 5 +R 1 +D 12 +R 2 +D 7 +U 16 +D 11 +L 15 +R 4 +U 4 +D 4 +U 4 +L 17 +U 3 +D 8 +U 1 +L 1 +U 4 +L 7 +U 9 +L 13 +D 10 +L 2 +U 7 +L 13 +D 16 +U 6 +L 10 +D 16 +L 8 +U 10 +L 6 +U 16 +L 5 +U 4 +R 9 +D 12 +R 1 +U 14 +L 14 +R 16 +D 5 +L 16 +R 14 +U 10 +R 4 +U 9 +L 15 +D 4 +U 15 +L 11 +R 14 +L 10 +D 14 +L 10 +D 12 +R 2 +D 3 +R 1 +U 1 +L 17 +U 9 +D 13 +R 7 +D 7 +U 13 +D 1 +R 14 +U 10 +R 16 +L 17 +R 7 +D 17 +U 11 +L 2 +U 16 +L 8 +U 13 +R 17 +U 5 +L 7 +R 3 +D 17 +L 10 +U 9 +D 16 +R 3 +U 5 +L 15 +R 16 +D 11 +U 9 +L 3 +R 14 +D 4 +L 4 +U 12 +D 9 +U 10 +D 15 +L 12 +R 6 +D 4 +L 14 +D 5 +L 4 +U 7 +R 15 +D 6 +L 15 +U 14 +D 10 +L 3 +D 9 +L 15 +R 9 +U 1 +L 4 +D 15 +U 12 +D 9 +R 8 +D 14 +R 15 +D 7 +U 18 +L 5 +U 6 +L 6 +D 10 +L 18 +R 3 +L 11 +D 10 +L 13 +U 13 +L 13 +R 3 +L 1 +U 3 +D 7 +L 9 +R 6 +U 18 +R 18 +U 15 +R 9 +U 4 +R 12 +L 12 +D 6 +U 10 +D 13 +L 6 +R 13 +L 13 +D 12 +U 4 +D 15 +L 12 +D 10 +U 12 +R 8 +L 13 +D 11 +L 13 +U 12 +D 5 +U 12 +R 10 +L 9 +U 13 +R 7 +D 2 +L 6 +U 13 +D 15 +R 3 +U 4 +D 5 +L 2 +D 10 +U 7 +L 2 +D 5 +L 5 +D 11 +R 5 +U 18 +L 9 +D 8 +U 12 +R 3 +U 8 +R 14 +D 1 +R 4 +L 5 +D 10 +R 18 +D 2 +R 9 +L 14 +U 4 +R 15 +D 4 +R 2 +L 4 +U 13 +R 6 +U 18 +D 4 +U 7 +L 15 +D 1 +L 6 +D 3 +U 15 +L 17 +U 15 +R 14 +L 9 +U 5 +L 4 +U 13 +R 5 +D 17 +U 17 +L 15 +U 14 +R 5 +L 1 +R 9 +U 8 +R 15 +U 18 +L 12 +R 13 +D 15 +R 5 +L 11 +R 5 +U 12 +R 8 +L 6 +R 1 +L 10 +U 17 +L 16 +U 12 +L 14 +D 16 +U 13 +D 18 +L 5 +U 16 +L 11 +D 15 +U 2 +L 9 +D 5 +L 17 +D 17 +L 4 +D 4 +L 19 +R 6 +D 6 +U 18 +R 16 +U 12 +D 2 +L 4 +U 19 +R 6 +U 1 +D 15 +R 13 +U 18 +D 12 +L 9 +U 1 +R 13 +D 18 +L 4 +D 17 +L 9 +D 8 +U 3 +D 5 +R 7 +L 16 +U 3 +L 1 +D 13 +R 17 +D 8 +R 9 +U 17 +L 2 +U 17 +D 16 +L 8 +R 9 +D 7 +L 16 +R 10 +L 16 +D 10 +L 15 +U 17 +L 2 +U 10 +D 16 +R 1 +L 2 +D 4 +R 13 +L 12 +D 8 +U 10 +L 6 +D 14 +L 6 +D 11 +R 1 +D 10 +L 18 +D 12 +R 14 +L 3 +D 7 +L 12 +R 19 +U 5 +R 19 +D 3 +L 15 +U 13 diff --git a/09/src/part-1.rs b/09/src/part-1.rs new file mode 100644 index 0000000..f61c09d --- /dev/null +++ b/09/src/part-1.rs @@ -0,0 +1,59 @@ +use std::collections::{HashSet}; +use std::io::{BufRead}; + + +fn main() { + let stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let mut buf: Vec = Vec::new(); + let mut seen: HashSet<[isize; 2]> = HashSet::new(); + let mut head_pos: [isize; 2] = [0; 2]; + let mut tail_pos: [isize; 2] = head_pos.clone(); + seen.insert(tail_pos.clone()); + + loop { + buf.clear(); + let num_bytes = handle.read_until(b'\n', &mut buf).expect("IO error"); + if num_bytes == 0 { break; } + + if buf[buf.len() - 1] == b'\n' { buf.pop(); } + + let direction = buf[0]; + let num_steps: usize = std::str::from_utf8(& buf[2..]).expect("Malformed input") + .parse().expect("Malformed input"); + + for dir in std::iter::repeat(direction).take(num_steps) { + match dir { + b'L' => head_pos[0] -= 1, + b'R' => head_pos[0] += 1, + b'U' => head_pos[1] += 1, + b'D' => head_pos[1] -= 1, + _ => panic!("Malformed input") + }; + let delta: [isize; 2] = { + let mut ret: [isize; 2] = [0; 2]; + for i in 0..2 { ret[i] = head_pos[i] - tail_pos[i]; } + ret + }; + if delta[0].abs() == 2 { + tail_pos[0] += delta[0].signum(); + if delta[1].abs() == 1 { + tail_pos[1] += delta[1].signum(); + } + seen.insert(tail_pos.clone()); + } + else if delta[1].abs() == 2 { + tail_pos[1] += delta[1].signum(); + if delta[0].abs() == 1 { + tail_pos[0] += delta[0].signum(); + } + seen.insert(tail_pos.clone()); + } + } + } + + println!("{}", seen.len()); + + +} diff --git a/09/src/part-2.rs b/09/src/part-2.rs new file mode 100644 index 0000000..1773d2e --- /dev/null +++ b/09/src/part-2.rs @@ -0,0 +1,65 @@ +// Ugh, weird motion in this grid world! + +use std::collections::{HashSet}; +use std::io::{BufRead}; + +const NUM_SEGMENTS: usize = 10; + +type Pos = [isize; 2]; + +fn main() { + let stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let mut buf: Vec = Vec::new(); + let mut seen: HashSet<[isize; 2]> = HashSet::new(); + let mut positions: [Pos; NUM_SEGMENTS] = [[0; 2]; NUM_SEGMENTS]; + seen.insert(positions[NUM_SEGMENTS-1].clone()); + + loop { + buf.clear(); + let num_bytes = handle.read_until(b'\n', &mut buf).expect("IO error"); + if num_bytes == 0 { break; } + + if buf[buf.len() - 1] == b'\n' { buf.pop(); } + + let direction = buf[0]; + let num_steps: usize = std::str::from_utf8(& buf[2..]).expect("Malformed input") + .parse().expect("Malformed input"); + + for dir in std::iter::repeat(direction).take(num_steps) { + match dir { + b'L' => positions[0][0] -= 1, + b'R' => positions[0][0] += 1, + b'U' => positions[0][1] += 1, + b'D' => positions[0][1] -= 1, + _ => panic!("Malformed input") + }; + + for i in 1..NUM_SEGMENTS { + let delta: [isize; 2] = { + let mut ret: [isize; 2] = [0; 2]; + for d in 0..2 { ret[d] = positions[i-1][d] - positions[i][d]; } + ret + }; + if delta[0].abs() == 2 { + positions[i][0] += delta[0].signum(); + if delta[1].abs() == 1 { + positions[i][1] += delta[1].signum(); + } + } + if delta[1].abs() == 2 { + positions[i][1] += delta[1].signum(); + if delta[0].abs() == 1 { + positions[i][0] += delta[0].signum(); + } + } + } + seen.insert(positions[NUM_SEGMENTS-1].clone()); + } + } + + println!("{}", seen.len()); + + +} diff --git a/09/test-1.txt b/09/test-1.txt new file mode 100644 index 0000000..9874df2 --- /dev/null +++ b/09/test-1.txt @@ -0,0 +1,8 @@ +R 4 +U 4 +L 3 +D 1 +R 4 +D 1 +L 5 +R 2 diff --git a/09/test-2.txt b/09/test-2.txt new file mode 100644 index 0000000..60bd43b --- /dev/null +++ b/09/test-2.txt @@ -0,0 +1,8 @@ +R 5 +U 8 +L 8 +D 3 +R 17 +D 10 +L 25 +U 20 -- cgit v1.2.3