1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
use std::io::{self, Read};
struct GenA(u64);
impl Iterator for GenA {
type Item = u64;
fn next(&mut self) -> Option<u64> {
self.0 = self.0.wrapping_mul(16807) % 2147483647;
Some(self.0)
}
}
struct GenB(u64);
impl Iterator for GenB {
type Item = u64;
fn next(&mut self) -> Option<u64> {
self.0 = self.0.wrapping_mul(48271) % 2147483647;
Some(self.0)
}
}
struct GenA2(u64);
impl Iterator for GenA2 {
type Item = u64;
fn next(&mut self) -> Option<u64> {
loop {
self.0 = self.0.wrapping_mul(16807) % 2147483647;
if self.0 % 4 == 0 {
return Some(self.0);
}
}
}
}
struct GenB2(u64);
impl Iterator for GenB2 {
type Item = u64;
fn next(&mut self) -> Option<u64> {
loop {
self.0 = self.0.wrapping_mul(48271) % 2147483647;
if self.0 % 8 == 0 {
return Some(self.0);
}
}
}
}
fn judge1(a: u64, b: u64) -> usize {
GenA(a).zip(GenB(b))
.take(40_000_000)
.filter(|&(a, b)| a & 0xFFFF == b & 0xFFFF)
.count()
}
fn judge2(a: u64, b: u64) -> usize {
GenA2(a).zip(GenB2(b))
.take(5_000_000)
.filter(|&(a, b)| a & 0xFFFF == b & 0xFFFF)
.count()
}
fn solve1(input: &str) -> usize {
let mut iter = input.split_whitespace();
let a = iter.clone().nth(4).unwrap().parse().unwrap();
let b = iter.nth(9).unwrap().parse().unwrap();
judge1(a, b)
}
fn solve2(input: &str) -> usize {
let mut iter = input.split_whitespace();
let a = iter.clone().nth(4).unwrap().parse().unwrap();
let b = iter.nth(9).unwrap().parse().unwrap();
judge2(a, b)
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
println!("Part 1: {}", solve1(input.trim()));
println!("Part 2: {}", solve2(input.trim()));
}
#[test]
fn part1() {
assert_eq!(588, judge1(65, 8921));
}
#[test]
fn part2() {
assert_eq!(309, judge2(65, 8921));
}
|