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
100
101
102
103
104
105

//! # Duet
//!
//! Reverse engineering the code shows that the program is broken into 2 sections.
//! Each input differs only in the number specified on line 10.
//!
//! The first section is only executed by program 0 and generates a pseudorandom sequence of
//! 127 numbers between 0 and 9999. The programs then take turns implementing the innner loop of
//! the [imfamous bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) in descending order.
//!
//! The partially sorted sequence is passed back and forth between each program until in final
//! sorted order. Assembly code annotated with Rust pseduocode:
//!
//! ```none
//!     set i 31
//!     set a 1
//!     mul p 17
//!     jgz p p         if p == 0 {
//!     mul a 2             let a = 2 ^ 31 - 1 = 0x7fffffff;
//!     add i -1
//!     jgz i -2
//!     add a -1
//!     set i 127
//!     set p SEED          let mut p = SEED;
//!     mul p 8505          for _ in 0..127 {
//!     mod p a                 p = (p * 8505) % a;
//!     mul p 129749
//!     add p 12345
//!     mod p a                 p = (p * 129749 + 12345) % a;
//!     set b p
//!     mod b 10000
//!     snd b                   send(p % 10000)
//!     add i -1
//!     jgz i -9            }
//!     jgz a 3         }
//!     rcv b           // These two lines deadlock the program
//!     jgz b -1        // once the list is sorted.
//!     set f 0         while swapped { // f is 0 when list is sorted
//!     set i 126           a = receive();
//!     rcv a               for _ in 0..126 {
//!     rcv b                   b = receive();
//!     set p a
//!     mul p -1
//!     add p b
//!     jgz p 4                 if b <= a {
//!     snd a                       send(a);
//!     set a b                     a = b;
//!     jgz 1 3                 } else {
//!     snd b                       send(b);
//!     set f 1                     swapped = true;
//!     add i -1                }
//!     jgz i -11           }
//!     snd a
//!     jgz f -16       }
//!     jgz a -19       // Jump to deadlock section.
//! ```
use crate::util::parse::*;

/// Generate a pseudorandom sequence of 127 numbers, based on a
/// starting seed different for each input.
pub fn parse(input: &str) -> Vec<u64> {
    // Read the starting seed from the input.
    let mut p: u64 = input.lines().nth(9).unwrap().unsigned();
    let mut numbers = Vec::with_capacity(127);

    // Generate pseudorandom sequence.
    for _ in 0..127 {
        p = (p * 8505) % 0x7fffffff;
        p = (p * 129749 + 12345) % 0x7fffffff;
        numbers.push(p % 10000);
    }

    numbers
}

/// Part one is the last number sent in the sequence.
pub fn part1(input: &[u64]) -> u64 {
    input[126]
}

/// Bubble sort the sequence into descending order, counting the number of passes.
/// Starting with program 1 each program alternates sorting the input by sending it to the other
/// program, so the number of passes that program 1 takes is the total divided by two rounding up.
pub fn part2(input: &[u64]) -> usize {
    let mut numbers = input.to_vec();
    let mut swapped = true;
    let mut count = 0;

    // Bubble sort in descending order.
    while swapped {
        swapped = false;

        // "Optimized" version skipping the last count elements as these are already sorted.
        for i in 1..127 - count {
            if numbers[i - 1] < numbers[i] {
                numbers.swap(i - 1, i);
                swapped = true;
            }
        }

        count += 1;
    }

    // The sequence countains 127 numbers so the final result is multiplied by that factor.
    127 * count.div_ceil(2)
}