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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
use num::integer::Integer;
use regex::Regex;
use std::collections::HashSet;
use std::io::{self, BufRead};
type CoordType = i32;
type EnergyType = i32;
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Coords {
x: CoordType,
y: CoordType,
z: CoordType,
}
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Moon {
pos: Coords,
vel: Coords,
}
fn read_input() -> Vec<Coords> {
let stdin = io::stdin();
let re = Regex::new(r"<x=(?P<x>[0-9-]*), *y=(?P<y>[0-9-]*), *z=(?P<z>[0-9-]*)").
expect("Regex failed to compile");
stdin.lock().lines()
.map(|line| {
match line {
Ok(l) => {
let caps = match re.captures(&l) {
Some(c) => c,
_ => panic!("Regex issue for line: {:?}", l),
};
Coords {
x: caps["x"].parse().unwrap(),
y: caps["y"].parse().unwrap(),
z: caps["z"].parse().unwrap(),
}
},
_ => panic!("Failed to parse line: {:?}", line),
}
}).collect()
}
// To apply gravity, consider every pair of moons. On each axis (x, y, and z), the velocity of each
// moon changes by exactly +1 or -1 to pull the moons together. However, if the positions on a
// given axis are the same, the velocity on that axis does not change for that pair of moons.
fn apply_gravity(this: &mut Moon, other: &Moon) {
fn vel_change(a: CoordType, b: CoordType) -> CoordType {
if a < b { 1 } else if a > b { -1 } else { 0 }
}
this.vel.x += vel_change(this.pos.x, other.pos.x);
this.vel.y += vel_change(this.pos.y, other.pos.y);
this.vel.z += vel_change(this.pos.z, other.pos.z);
}
// Once all gravity has been applied, apply velocity: simply add the velocity of each moon to its
// own position.
fn apply_velocity(moon: &mut Moon) {
moon.pos.x += moon.vel.x;
moon.pos.y += moon.vel.y;
moon.pos.z += moon.vel.z;
}
// A moon's potential energy is the sum of the absolute values of its x, y, and z position
// coordinates.
fn potential_energy(moon: &Moon) -> EnergyType {
moon.pos.x.abs() + moon.pos.y.abs() + moon.pos.z.abs()
}
// A moon's kinetic energy is the sum of the absolute values of its velocity coordinates. Below,
// each line shows the calculations for a moon's potential energy (pot), kinetic energy (kin), and
// total energy:
fn kinetic_energy(moon: &Moon) -> EnergyType {
moon.vel.x.abs() + moon.vel.y.abs() + moon.vel.z.abs()
}
fn print_moon(moon: &Moon) {
println!("pos=<x={:2}, y={:2}, z={:2}>, vel=<x={:2}, y={:2}, z={:2}>",
moon.pos.x, moon.pos.y, moon.pos.z,
moon.vel.x, moon.vel.y, moon.vel.z,);
}
fn iterations_until_repeat(mut moons: Vec<Moon>) -> usize{
let mut seen = HashSet::new();
seen.insert(moons.clone());
for n in 1.. {
let old_moons = moons.clone();
for (i, moon) in moons.iter_mut().enumerate() {
for (j, old) in old_moons.iter().enumerate() {
if i != j { apply_gravity(moon, old) };
}
}
moons.iter_mut().map(|moon| apply_velocity(moon)).last();
if ! seen.insert(moons.clone()) {
return n;
}
}
0
}
fn main() {
let coords = read_input();
let mut moons: Vec<Moon> = coords.iter()
.map(|pos| Moon { pos: *pos, vel: Coords { x: 0, y: 0, z: 0 }}).collect();
// Simulate the motion of the moons in time steps. Within each time step, first update the
// velocity of every moon by applying gravity. Then, once all moons' velocities have been
// updated, update the position of every moon by applying velocity. Time progresses by one step
// once all of the positions are updated.
for _ in 0..std::env::args().nth(1).unwrap().parse::<i128>().unwrap() {
let old_moons = moons.clone();
for (i, moon) in moons.iter_mut().enumerate() {
for (j, old) in old_moons.iter().enumerate() {
if i != j { apply_gravity(moon, old) };
}
}
moons.iter_mut().map(|moon| apply_velocity(moon)).last();
}
// Then, it might help to calculate the total energy in the system. The total energy for a
// single moon is its potential energy multiplied by its kinetic energy.
let energy = moons.iter()
.map(|moon| potential_energy(moon) * kinetic_energy(moon)).sum::<EnergyType>();
// What is the total energy in the system after simulating the moons given in your scan for
// 1000 steps?
println!("Total energy: {}", energy);
// Determine the number of steps that must occur before all of the moons' positions and
// velocities exactly match a previous point in time.
let moons_x: Vec<Moon> = moons.iter().map(|m| Moon {
pos: Coords { x: m.pos.x, y: 0, z: 0},
vel: Coords { x: m.vel.x, y: 0, z: 0},
}).collect();
let moons_y: Vec<Moon> = moons.iter().map(|m| Moon {
pos: Coords { x: 0, y: m.pos.y, z: 0},
vel: Coords { x: 0, y: m.vel.y, z: 0},
}).collect();
let moons_z: Vec<Moon> = moons.iter().map(|m| Moon {
pos: Coords { x: 0, y: 0, z: m.pos.z },
vel: Coords { x: 0, y: 0, z: m.vel.z },
}).collect();
let repeat_x = iterations_until_repeat(moons_x);
let repeat_y = iterations_until_repeat(moons_y);
let repeat_z = iterations_until_repeat(moons_z);
// Clearly, you might need to find a more efficient way to simulate the universe.
let repeat = repeat_z.lcm(&repeat_x.lcm(&repeat_y));
println!("Iterations until repeat: {}", repeat);
}
|
