aoc/year2017/
day18.rs

1//! # Duet
2//!
3//! Reverse engineering the code shows that the program is broken into 2 sections.
4//! Each input differs only in the number specified on line 10.
5//!
6//! The first section is only executed by program 0 and generates a pseudorandom sequence of
7//! 127 numbers between 0 and 9999. The programs then take turns implementing the innner loop of
8//! the [imfamous bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) in descending order.
9//!
10//! The partially sorted sequence is passed back and forth between each program until in final
11//! sorted order. Assembly code annotated with Rust pseduocode:
12//!
13//! ```none
14//!     set i 31
15//!     set a 1
16//!     mul p 17
17//!     jgz p p         if p == 0 {
18//!     mul a 2             let a = 2 ^ 31 - 1 = 0x7fffffff;
19//!     add i -1
20//!     jgz i -2
21//!     add a -1
22//!     set i 127
23//!     set p SEED          let mut p = SEED;
24//!     mul p 8505          for _ in 0..127 {
25//!     mod p a                 p = (p * 8505) % a;
26//!     mul p 129749
27//!     add p 12345
28//!     mod p a                 p = (p * 129749 + 12345) % a;
29//!     set b p
30//!     mod b 10000
31//!     snd b                   send(p % 10000)
32//!     add i -1
33//!     jgz i -9            }
34//!     jgz a 3         }
35//!     rcv b           // These two lines deadlock the program
36//!     jgz b -1        // once the list is sorted.
37//!     set f 0         while swapped { // f is 0 when list is sorted
38//!     set i 126           a = receive();
39//!     rcv a               for _ in 0..126 {
40//!     rcv b                   b = receive();
41//!     set p a
42//!     mul p -1
43//!     add p b
44//!     jgz p 4                 if b <= a {
45//!     snd a                       send(a);
46//!     set a b                     a = b;
47//!     jgz 1 3                 } else {
48//!     snd b                       send(b);
49//!     set f 1                     swapped = true;
50//!     add i -1                }
51//!     jgz i -11           }
52//!     snd a
53//!     jgz f -16       }
54//!     jgz a -19       // Jump to deadlock section.
55//! ```
56use crate::util::parse::*;
57
58/// Generate a pseudorandom sequence of 127 numbers, based on a
59/// starting seed different for each input.
60pub fn parse(input: &str) -> Vec<u64> {
61    // Read the starting seed from the input.
62    let mut p: u64 = input.lines().nth(9).unwrap().unsigned();
63    let mut numbers = Vec::with_capacity(127);
64
65    // Generate pseudorandom sequence.
66    for _ in 0..127 {
67        p = (p * 8505) % 0x7fffffff;
68        p = (p * 129749 + 12345) % 0x7fffffff;
69        numbers.push(p % 10000);
70    }
71
72    numbers
73}
74
75/// Part one is the last number sent in the sequence.
76pub fn part1(input: &[u64]) -> u64 {
77    input[126]
78}
79
80/// Bubble sort the sequence into descending order, counting the number of passes.
81/// Starting with program 1 each program alternates sorting the input by sending it to the other
82/// program, so the number of passes that program 1 takes is the total divided by two rounding up.
83pub fn part2(input: &[u64]) -> usize {
84    let mut numbers = input.to_vec();
85    let mut swapped = true;
86    let mut count = 0;
87
88    // Bubble sort in descending order.
89    while swapped {
90        swapped = false;
91
92        // "Optimized" version skipping the last count elements as these are already sorted.
93        for i in 1..127 - count {
94            if numbers[i - 1] < numbers[i] {
95                numbers.swap(i - 1, i);
96                swapped = true;
97            }
98        }
99
100        count += 1;
101    }
102
103    // The sequence countains 127 numbers so the final result is multiplied by that factor.
104    127 * count.div_ceil(2)
105}
aoc/year2017/day18.rs

aoc/year2017/
day18.rs
