Skip to content

Instantly share code, notes, and snippets.

@0e4ef622

0e4ef622/solution.rs

Last active December 16, 2018 01:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save 0e4ef622/86961bd63a5ba9b7c41f26523ea7ca28 to your computer and use it in GitHub Desktop.
Save 0e4ef622/86961bd63a5ba9b7c41f26523ea7ca28 to your computer and use it in GitHub Desktop.
Download ZIP
aoc day 15 2018
Raw
solution.rs
macro_rules! iter {
($item:expr) => (std::iter::once($item));
($item:expr, $($rest:tt)*) => (std::iter::once($item).chain(iter!($($rest)*)));
}
use std::collections::*;
#[derive(PartialOrd, Ord, PartialEq, Eq, Clone, Copy, Hash, Debug)]
enum Unit {
Elf,
Gnome,
}
use std::io::Write;
pub fn part1(input: &str) -> usize {
let mut map = vec![];
let mut width = 0;
let mut units = vec![];
for (y, line) in input.lines().enumerate() {
width = line.len();
for (x, &ch) in line.as_bytes().iter().enumerate() {
map.push(ch);
match ch {
b'G' => {
units.push((y, x, Unit::Gnome, 200));
}
b'E' => {
units.push((y, x, Unit::Elf, 200));
}
_ => (),
}
}
}
let mut round = 0;
let mut distances_thingo = vec![None::<(u64, usize, Option<usize>)>; map.len()];
'l: loop {
units.sort_unstable();
let mut unit_inde: isize = 0;
while unit_inde < units.len() as isize {
let unit_index = unit_inde as usize;
let gnomes: Vec<_> = units.iter().cloned().filter(|v| v.2 == Unit::Gnome).collect();
let elves: Vec<_> = units.iter().cloned().filter(|v| v.2 == Unit::Elf).collect();
if gnomes.len() == 0 || elves.len() == 0 {
break 'l;
}
let unit = units[unit_index];
let mut unit = unit.0*width+unit.1;
let mut spots_in_range: Vec<_> = match units[unit_index].2 {
Unit::Elf => &gnomes,
Unit::Gnome => &elves,
}.iter()
.map(|v| v.0*width+v.1)
.flat_map(|i| iter![i+1, i-1, i+width, i-width])
.filter(|&i| map[i] == b'.' || i == unit)
.map(|i| (i, ((i%width) as isize-(unit%width) as isize).abs()+((i/width) as isize - (unit/width) as isize).abs()))
.collect();
spots_in_range.sort_unstable_by_key(|v| v.1);
if spots_in_range.get(0).map(|v| v.0) != Some(unit) {
// breadth first flood fill and dijkstra's alg
let mut queue = VecDeque::new();
// distance, current, previous
queue.push_back((1u64, unit+1, unit, None));
queue.push_back((1u64, unit-1, unit, None));
queue.push_back((1u64, unit+width, unit, None));
queue.push_back((1u64, unit-width, unit, None));
// let mut hashmap: HashMap<usize, (u64, Vec<usize>)> = HashMap::new();
for v in &mut distances_thingo { *v = None; }
while queue.len() != 0 {
let c = queue.pop_front().unwrap();
if map[c.1] != b'.' { continue; }
match &mut distances_thingo[c.1] {
Some(v) => if c.0 < v.0 {
*v = (c.0, c.2, c.3);
} else if c.0 == v.0 {
v.2 = Some(c.2);
continue;
} else {
continue;
}
v @ None => {
*v = Some((c.0, c.2, c.3));
}
}
queue.push_back((c.0+1, c.1+1, c.1, None));
queue.push_back((c.0+1, c.1-1, c.1, None));
queue.push_back((c.0+1, c.1+width, c.1, None));
queue.push_back((c.0+1, c.1-width, c.1, None));
}
// println!("{:?}", hashmap);
let mut sorted: Vec<_> = spots_in_range
.iter()
.filter_map(|v| distances_thingo.get(v.0).unwrap().as_ref().map(|d| (v.0, d)))
.collect();
sorted.sort_unstable_by_key(|v| (v.1 .0, v.0));
// println!("{}: {:?}", map[unit] as char, spots_in_range.iter().map(|v| (v.0%width, v.0/width, v.1)).collect::<Vec<_>>());
// println!("{}: {:?}", map[unit] as char, sorted.iter().map(|v| (v.0%width, v.0/width, v.1)).collect::<Vec<_>>());
// let stdout = std::io::stdout();
// let mut stdout = stdout.lock();
// for y in 0..map.len()/width {
// for x in 0..width {
// if spots_in_range.iter().any(|v| v.0 == y*width+x) {
// stdout.write(b"?");
// } else {
// stdout.write(&[map[y*width+x]]);
// }
// }
// stdout.write(b"\n");
// }
sorted.first()
.map(|(c, (_, y, z))| {
let c = std::iter::once(y).chain(z).map(|&(mut p)| {
let mut c = *c;
while p != unit {
c = p;
let whathaveidone = *distances_thingo.get(p).unwrap().as_ref().unwrap();
p = whathaveidone.2.map(|v| v.min(whathaveidone.1)).unwrap_or(whathaveidone.1);
}
c
}).min().unwrap();
units[unit_index].0 = c/width;
units[unit_index].1 = c%width;
map[unit] = b'.';
map[c] = match units[unit_index].2 {
Unit::Gnome => b'G',
Unit::Elf => b'E',
};
unit = c;
});
}
// check for adjacent and attacc
let mut adjacent = match units[unit_index].2 {
Unit::Elf => &gnomes,
Unit::Gnome => &elves,
}.iter().filter(|v| (v.0 as isize - units[unit_index].0 as isize).abs() == 1
&& (v.1 as isize - units[unit_index].1 as isize).abs() == 0
|| (v.1 as isize - units[unit_index].1 as isize).abs() == 1
&& (v.0 as isize - units[unit_index].0 as isize).abs() == 0).collect::<Vec<_>>();
adjacent.sort_unstable_by_key(|v| (v.3, v.0*width+v.1));
if let Some(v) = adjacent.first() {
let it = {
let mut it = units.iter_mut().enumerate().find(|(_, x)| x == v).unwrap();
it.1 .3 -= 3;
(it.0, *it.1)
};
// println!("unit at {},{} attacks unit at {},{}", units[unit_index].1, units[unit_index].0, it.1 .1, it.1 .0);
if it.1 .3 <= 0 {
units.remove(it.0);
if it.0 < unit_index { unit_inde -= 1; }
map[it.1 .0*width+it.1 .1] = b'.';
if units.iter().filter(|v| v.2 == Unit::Gnome).count() == 0 ||
units.iter().filter(|v| v.2 == Unit::Elf).count() == 0 {
break 'l;
}
}
}
// println!("{}: {:?}", map[unit] as char, adjacent);
unit_inde += 1;
}
// println!("{:?}", units);
// let stdout = std::io::stdout();
// let mut stdout = stdout.lock();
// for y in 0..map.len()/width {
// for x in 0..width {
// stdout.write(&[map[y*width+x]]);
// }
// stdout.write(b"\n");
// }
round += 1;
// std::thread::sleep(std::time::Duration::from_millis(100));
}
// println!("{} rounds, {:?}", round, units);
round as usize * units.iter().map(|v| v.3).sum::<i32>() as usize
}
pub fn part2(input: &str) -> usize {
let mut map = vec![];
let mut width = 0;
let mut units = vec![];
let mut elf_attack_power = 4;
for (y, line) in input.lines().enumerate() {
width = line.len();
for (x, &ch) in line.as_bytes().iter().enumerate() {
map.push(ch);
match ch {
b'G' => {
units.push((y, x, Unit::Gnome, 200));
}
b'E' => {
units.push((y, x, Unit::Elf, 200));
}
_ => (),
}
}
}
let mut round;
let mut distances_thingo = vec![None::<(u64, usize, Option<usize>)>; map.len()];
let units = 'a: loop {
round = 0;
let mut units = units.clone();
let mut map = map.clone();
'l: loop {
units.sort_unstable();
let mut unit_inde: isize = 0;
while unit_inde < units.len() as isize {
let unit_index = unit_inde as usize;
let gnomes: Vec<_> = units.iter().cloned().filter(|v| v.2 == Unit::Gnome).collect();
let elves: Vec<_> = units.iter().cloned().filter(|v| v.2 == Unit::Elf).collect();
if gnomes.len() == 0 || elves.len() == 0 {
break 'l;
}
let unit = units[unit_index];
let mut unit = unit.0*width+unit.1;
let mut spots_in_range: Vec<_> = match units[unit_index].2 {
Unit::Elf => &gnomes,
Unit::Gnome => &elves,
}.iter()
.map(|v| v.0*width+v.1)
.flat_map(|i| iter![i+1, i-1, i+width, i-width])
.filter(|&i| map[i] == b'.' || i == unit)
.map(|i| (i, ((i%width) as isize-(unit%width) as isize).abs()+((i/width) as isize - (unit/width) as isize).abs()))
.collect();
spots_in_range.sort_unstable_by_key(|v| v.1);
if spots_in_range.get(0).map(|v| v.0) != Some(unit) {
// breadth first flood fill and dijkstra's alg
let mut queue = VecDeque::new();
// distance, current, previous
queue.push_back((1u64, unit+1, unit, None));
queue.push_back((1u64, unit-1, unit, None));
queue.push_back((1u64, unit+width, unit, None));
queue.push_back((1u64, unit-width, unit, None));
// let mut hashmap: HashMap<usize, (u64, Vec<usize>)> = HashMap::new();
for v in &mut distances_thingo { *v = None; }
while queue.len() != 0 {
let c = queue.pop_front().unwrap();
if map[c.1] != b'.' { continue; }
match &mut distances_thingo[c.1] {
Some(v) => if c.0 < v.0 {
*v = (c.0, c.2, c.3);
} else if c.0 == v.0 {
v.2 = Some(c.2);
continue;
} else {
continue;
}
v @ None => {
*v = Some((c.0, c.2, c.3));
}
}
queue.push_back((c.0+1, c.1+1, c.1, None));
queue.push_back((c.0+1, c.1-1, c.1, None));
queue.push_back((c.0+1, c.1+width, c.1, None));
queue.push_back((c.0+1, c.1-width, c.1, None));
}
// println!("{:?}", hashmap);
let mut sorted: Vec<_> = spots_in_range
.iter()
.filter_map(|v| distances_thingo.get(v.0).unwrap().as_ref().map(|d| (v.0, d)))
.collect();
sorted.sort_unstable_by_key(|v| (v.1 .0, v.0));
// println!("{}: {:?}", map[unit] as char, spots_in_range.iter().map(|v| (v.0%width, v.0/width, v.1)).collect::<Vec<_>>());
// println!("{}: {:?}", map[unit] as char, sorted.iter().map(|v| (v.0%width, v.0/width, v.1)).collect::<Vec<_>>());
// let stdout = std::io::stdout();
// let mut stdout = stdout.lock();
// for y in 0..map.len()/width {
// for x in 0..width {
// if spots_in_range.iter().any(|v| v.0 == y*width+x) {
// stdout.write(b"?");
// } else {
// stdout.write(&[map[y*width+x]]);
// }
// }
// stdout.write(b"\n");
// }
sorted.first()
.map(|(c, (_, y, z))| {
let c = std::iter::once(y).chain(z).map(|&(mut p)| {
let mut c = *c;
while p != unit {
c = p;
let whathaveidone = *distances_thingo.get(p).unwrap().as_ref().unwrap();
p = whathaveidone.2.map(|v| v.min(whathaveidone.1)).unwrap_or(whathaveidone.1);
}
c
}).min().unwrap();
units[unit_index].0 = c/width;
units[unit_index].1 = c%width;
map[unit] = b'.';
map[c] = match units[unit_index].2 {
Unit::Gnome => b'G',
Unit::Elf => b'E',
};
unit = c;
});
}
// check for adjacent and attacc
let mut adjacent = match units[unit_index].2 {
Unit::Elf => &gnomes,
Unit::Gnome => &elves,
}.iter().filter(|v| (v.0 as isize - units[unit_index].0 as isize).abs() == 1
&& (v.1 as isize - units[unit_index].1 as isize).abs() == 0
|| (v.1 as isize - units[unit_index].1 as isize).abs() == 1
&& (v.0 as isize - units[unit_index].0 as isize).abs() == 0).collect::<Vec<_>>();
adjacent.sort_unstable_by_key(|v| (v.3, v.0*width+v.1));
if let Some(v) = adjacent.first() {
let it = {
let mut it = units.iter_mut().enumerate().find(|(_, x)| x == v).unwrap();
match it.1 .2 {
Unit::Gnome => it.1 .3 -= elf_attack_power,
Unit::Elf => it.1 .3 -= 3,
}
(it.0, *it.1)
};
// println!("unit at {},{} attacks unit at {},{}", units[unit_index].1, units[unit_index].0, it.1 .1, it.1 .0);
if it.1 .3 <= 0 {
if it.1 .2 == Unit::Elf {
elf_attack_power += 1;
continue 'a;
}
units.remove(it.0);
if it.0 < unit_index { unit_inde -= 1; }
map[it.1 .0*width+it.1 .1] = b'.';
}
}
// println!("{}: {:?}", map[unit] as char, adjacent);
unit_inde += 1;
}
// println!("{:?}", units);
// let stdout = std::io::stdout();
// let mut stdout = stdout.lock();
// for y in 0..map.len()/width {
// for x in 0..width {
// stdout.write(&[map[y*width+x]]);
// }
// stdout.write(b"\n");
// }
round += 1;
}
break units;
};
// println!("{} rounds, {:?}", round, units);
round * units.iter().map(|v| v.3).sum::<i32>() as usize
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment