summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Silverstone <dsilvers@digital-scurf.org>2020-12-22 08:19:54 +0000
committerDaniel Silverstone <dsilvers@digital-scurf.org>2020-12-22 08:19:54 +0000
commitbcf50f82e706ac458933a3eeae015551fb5085b9 (patch)
tree5576348461dcdeddf8f367f92d08bdd51bb62982
parent17b02f9e0564bc85a3ccdc57c82aa31e5ffba5dd (diff)
downloadaoc-bcf50f82e706ac458933a3eeae015551fb5085b9.tar.bz2
2020: Optimise day 22 by not storing whole decks into the prevgames hash
Signed-off-by: Daniel Silverstone <dsilvers@digital-scurf.org>
-rw-r--r--2020/src/bin/2020day22.rs17
1 files changed, 15 insertions, 2 deletions
diff --git a/2020/src/bin/2020day22.rs b/2020/src/bin/2020day22.rs
index 9d055d7..9c1e6c2 100644
--- a/2020/src/bin/2020day22.rs
+++ b/2020/src/bin/2020day22.rs
@@ -1,3 +1,6 @@
+use std::collections::hash_map::DefaultHasher;
+use std::hash::{Hash, Hasher};
+
use aoc2020::*;
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
@@ -6,6 +9,15 @@ struct Decks {
p2: VecDeque<u8>,
}
+impl Decks {
+ fn fpr(&self) -> u64 {
+ let mut hasher = DefaultHasher::new();
+ self.p1.hash(&mut hasher);
+ self.p2.hash(&mut hasher);
+ hasher.finish()
+ }
+}
+
impl FromStr for Decks {
type Err = GenError;
@@ -60,11 +72,12 @@ fn recursive_game(mut game: Decks) -> (u8, Decks) {
// During a recursive game, we can't repeat arrangements
let mut seen = HashSet::new();
while !(game.p1.is_empty() || game.p2.is_empty()) {
- if seen.contains(&game) {
+ let fpr = game.fpr();
+ if seen.contains(&fpr) {
// We've seen this arrangement before, p1 wins by default
return (1, game);
}
- seen.insert(game.clone());
+ seen.insert(fpr);
// Okay, unique arrangement, play a round...
let p1card = game.p1.pop_front().unwrap() as usize;
let p2card = game.p2.pop_front().unwrap() as usize;