From aad72387c57e226c984cb6d5cc67e113d9141358 Mon Sep 17 00:00:00 2001 From: June McEnroe Date: Thu, 15 Dec 2016 23:24:33 -0500 Subject: Day 13 --- src/bin/day13.rs | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 101 insertions(+) create mode 100644 src/bin/day13.rs (limited to 'src/bin/day13.rs') diff --git a/src/bin/day13.rs b/src/bin/day13.rs new file mode 100644 index 0000000..a953b28 --- /dev/null +++ b/src/bin/day13.rs @@ -0,0 +1,101 @@ +use std::collections::{HashMap, VecDeque}; +use std::io::{self, Read}; + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Point { + x: u32, + y: u32, +} + +const START: Point = Point { x: 1, y: 1 }; + +impl Point { + fn north(self) -> Option { + if self.y == 0 { + None + } else { + Some(Point { x: self.x, y: self.y - 1 }) + } + } + + fn east(self) -> Point { + Point { x: self.x + 1, y: self.y } + } + + fn south(self) -> Point { + Point { x: self.x, y: self.y + 1 } + } + + fn west(self) -> Option { + if self.x == 0 { + None + } else { + Some(Point { x: self.x - 1, y: self.y }) + } + } + + fn neighbors(self) -> [Option; 4] { + [self.north(), Some(self.east()), Some(self.south()), self.west()] + } +} + +#[derive(Clone, Copy)] +struct Layout { + constant: u32, +} + +impl Layout { + fn is_open(&self, point: Point) -> bool { + let Point { x, y } = point; + let sum = x * x + 3 * x + 2 * x * y + y + y * y + self.constant; + sum.count_ones() % 2 == 0 + } +} + +fn solve(goal: Point, constant: u32) -> u32 { + let layout = Layout { constant: constant }; + + let mut frontier = VecDeque::new(); + frontier.push_back(START); + + let mut previous = HashMap::new(); + previous.insert(START, START); + + while !frontier.is_empty() { + let current = frontier.pop_front().unwrap(); + if current == goal { break; } + + let neighbors = current.neighbors(); + let iter = neighbors.iter() + .filter_map(|&p| p) + .filter(|&p| layout.is_open(p)); + + for next in iter { + if !previous.contains_key(&next) { + frontier.push_back(next); + previous.insert(next, current); + } + } + } + + let mut steps = 0; + let mut current = goal; + while current != START { + current = *previous.get(¤t).unwrap(); + steps += 1; + } + + steps +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(Point { x: 31, y: 39 }, input.trim().parse().unwrap())); +} + +#[test] +fn part1() { + assert_eq!(11, solve(Point { x: 7, y: 4 }, 10)); +} -- cgit 1.4.1 id=6e854fc0a6decc3f4fa0e3b3ad255918d0504ed3&follow=1'>Load dates from ~/.config/when/datesJune McEnroe 2022-08-15Allow names with prefixes of months and daysJune McEnroe 2022-08-15Add named dates to whenJune McEnroe 2022-08-14Remove tweets text fileJune McEnroe 2022-08-09Fix all copyright noticesJune McEnroe 2022-08-04Add Conversations With FriendsJune McEnroe 2022-07-30Add Normal PeopleJune McEnroe 2022-07-26Rewrite glitch from new pngoJune McEnroe 2022-07-26Update Care with time-to-ID and piercingsJune McEnroe 2022-07-26Add -w to upJune McEnroe 2022-07-13Set push.autoSetupRemoteJune McEnroe 2022-07-08Remove TOURJune McEnroe 2022-07-03Add The Bone Shard EmperorJune McEnroe 2022-06-25Bump xterm font size to 12June McEnroe 2022-06-10Handle subshells (and functions) inside substitutionsJune McEnroe 2022-06-10Switch to jorts Install scriptJune McEnroe 2022-06-08Indicate if still reading or no resultsJune McEnroe 2022-06-08Add Maiden, Mother, CroneJune McEnroe 2022-06-05FIRST SHOW IN 2.5 YEARS BABEY!!!June McEnroe 2022-06-03Set line number on File linesJune McEnroe 2022-06-03Stop polling stdin after EOFJune McEnroe 2022-06-02Set TABSIZE=4June McEnroe 2022-06-02Do basic match highlightingJune McEnroe 2022-06-02Clean up parsing a littleJune McEnroe 2022-06-02Don't duplicate path stringJune McEnroe 2022-06-02Use stderr instead of /dev/tty, realloc buffer if lines too longJune McEnroe 2022-06-02Add initial working version of qfJune McEnroe 2022-05-29Set prompt for okshJune McEnroe'/pounce/commit/client.c?h=1.4p1&id=19cafa40a1ad37bf95d2b2464d203f2792449d48&follow=1'>Implement some amount of client connectionJune McEnroe 2019-10-23Set clients non-blockingJune McEnroe 2019-10-23Clean up state.c and factor out parsingJune McEnroe 2019-10-23Respond to pingsJune McEnroe 2019-10-23Add verbose flagJune McEnroe 2019-10-23Set NOSIGPIPE on server connectionJune McEnroe 2019-10-23Set an initial loop capJune McEnroe 2019-10-23Fix rest parsingJune McEnroe 2019-10-23Add dynamic poll listJune McEnroe 2019-10-23Don't assume commands have targets and handle ERRORJune McEnroe 2019-10-23Clean up state somewhatJune McEnroe 2019-10-23Actually send the buffer...June McEnroe 2019-10-23Add stateJune McEnroe