2017/src/day15.cpp


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

#include <iostream>

using namespace std;

namespace {

struct Generator {
	Generator(unsigned long factor, unsigned long prev)
	    : factor{ factor }
	    , prev{ prev }
	{
	}

	unsigned long next()
	{
		prev *= factor;
		prev %= 2147483647;
		return prev;
	}

	unsigned long factor;
	unsigned long prev;
};

void
part1(unsigned long start_a, unsigned long start_b)
{
	Generator GenA(16807, start_a);
	Generator GenB(48271, start_b);

	int count = 0;
	for ( int i = 0; i != 40000000; ++i ) {
		if ( (GenA.next() & 0xFFFF) == (GenB.next() & 0xFFFF) ) {
			++count;
		}
	}
	cout << "Part1: " << count << '\n';
}

void
part2(unsigned long start_a, unsigned long start_b)
{
	Generator GenA(16807, start_a);
	Generator GenB(48271, start_b);

	int count = 0;
	for ( int i = 0; i != 5000000; ++i ) {
		auto value_a = GenA.next();
		while ( value_a % 4 != 0 ) {
			value_a = GenA.next();
		}
		auto value_b = GenB.next();
		while ( value_b % 8 != 0 ) {
			value_b = GenB.next();
		}
		if ( (value_a & 0xFFFF) == (value_b & 0xFFFF) ) {
			++count;
		}
	}
	cout << "Part2: " << count << '\n';
}

} // namespace

int
main()
{
	static const unsigned long start_a = 618;
	static const unsigned long start_b = 814;

	part1(start_a, start_b);
	part2(start_a, start_b);
}