heh
2016/24
| -rw-r--r-- | src/inp.txt | 71 | ||||
| -rw-r--r-- | src/main.rs | 77 | ||||
| -rw-r--r-- | src/util.rs | 73 |
3 files changed, 149 insertions, 72 deletions
diff --git a/src/inp.txt b/src/inp.txt index b036326..d832ce3 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,26 +1,45 @@ -cpy a b -dec b -cpy a d -cpy 0 a -cpy b c -inc a -dec c -jnz c -2 -dec d -jnz d -5 -dec b -cpy b c -cpy c d -dec d -inc c -jnz d -2 -tgl c -cpy -16 c -jnz 1 c -cpy 97 c -jnz 79 d -inc a -inc d -jnz d -2 -inc c -jnz c -5 +################################################################################################################################################################################# +#...................#.#.#.........#.........#...............#.....#.....#.........#.............#.............#...#.......#.......#...#...#.......#...#...#.#...#.........#...#.# +#.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.###.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#######.#####.###.#.###.#.#.#.#.#.#.#.#.###.#.#.#########.#.###.###.#.#.#####.#.#.#####.###.#.#.#.#.# +#...#.....#.#...#...#...#.#...#...#.....#...#.#.....#...#.......#.#.....#...........#.........#.#.....#.#...#.........#.#.....#.........#...#.....#.....#.....#...#.#.....#.....# +#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.###.#####.#.###.###.#.###.###.#.#.#.#####.#####.#.#.#.#.###.#.#.#.#.#.#.#######.#.#.#####.#.#####.###.###.#.#.###.#.#.#.###.###.#.#.#.###.#.#.#.# +#.#.#...#...#...........#.......#...#.#.#.#.....#.#.......#...#...#.#.....#...#...#.#.#...........#.#...#...#...#.....#...........#...#0....#...#.#.#.....#.......#.....#...#...# +#.#.#.#.#.#.#.###########.###.###.###.#.#.#.#.#.#.#########.#####.#.#.###.#.#.#.#.#####.#.#.#.###.#.#.###.###.###.#.#.#.###.#.#.#.#.#######.#.#.#.#.#.###.#######.#######.#####.# +#.....#...#...#.#3........#.......#.#...#.#.#...#.......#.#.......#.#...#...#.#.....#...#.....#...#.#.....#.#.......#.......#...............#...#.......#.......#.#.............# +#.#.#.###.###.#.###.#.###.#.#.#.###.#.###.#.#.#######.#.#.###.#.###.#.#.#.#########.#.#.#####.#.#.#.#.#.#.#.#.#.#####.#####.#.###.###.###.###.#.#.###.#.#.###.###.###.#.###.#.### +#...#.....#.......#.#.#...#.............#...........#...........#.....#.#.......#.....#.......#.......#.#.....#.....#.....#.....#.#...#.......#.......#.#.....#.#...#.....#...#.# +#####.###.###.#.###.###.#.#.#####.#.###.#####.#.#.#.#########.#.#.###.#.#.#.#.#.#.###.###.#.#.###.###.#.#####.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.#####.#####.###.#.#.#.# +#.....#.........#.......#.#.......#.#.....#...#...#.............#.....#.......#.#...#...#...#...#.....#...#.....#.....#...#.....#...#.#...#...#...#.....#.....#.......#.#...#...# +#.#.#.#.###.#.#.#.#.#.#.#.#.#####.###.###.#####.#.#.#####.#.###.#.#.#.###.#.#.###.#.###.#.#.#.###.###.#.#.#.#########.###.#.#.#.#.#.#.#.#####.#.###.#.#.#.#.###.#.#.#.#.#.#####.# +#.....#.#.....#.....#.....#.#...............#.#.........#.....#.#.....#.....#...#.....#.#.#.#.#...#...#...............#...#.#...#...#.#.#...#.#.#.....#.....#...#...#.#...#...#.# +#.###.#.#.#.#.#.#.#.#.#####.#.#.###.#.#.###.#.#######.#.#.#.#.#.#.#########.###.#.###.###.#.#.#.#########.#.#.###.#.#.#.###.###.###.###.#.###.#.#.#.#.#.###.#.#.###.#.#.#.#.#.#.# +#.#.#.#.#.#...#...#...#.........#...........#...#...#...#.....#...#.#.#.......#.#.....#...........#.........#.......#...#.#.#...#.........#1#.#...#.#.............#...#.........# +###.#.#.###.#.#.#.#.#.#####.#########.###.#.#.#####.###.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#####.#.#.#####.#######.###.#.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.###.#.#####.###.##### +#...#.#.....#.....#.........#...#...#...#...#...#.......#.......#.....#.........#.#...#.....#.#...#.....#...#...#.#.#.......#.....#.....#.#...#.#.............#.#...........#.#.# +#.#.#.#.#.###.###.#.#.###.###.###.#.#.#.#####.#.###.###.#.###.#######.###.#.###.#.#.#.#.#.#.#####.###.#.#.#.#.#.#.###########.#.#.#.#.#.#.#.#.#.#.###.###.#.###.#.#.#.###.#.#.#.# +#.........#...#.....#.#...#...#...............#.....#.......#...#.....#...#.#...#.#...#.#.........#...#.#.#.....#.....#.......#.......#.....#.#...........#.....#.#...........#.# +#####.#.#.#.#.#.###.#.#.#.#.#.#.#####.###.#.#.#.###.#.###.#.#.#.#.#.#.###.#.#.###.#.#.#.#.###.#.#.#.#####.#.#####.###.#.#.#.###.#.#.###.###.###.#####.#.#.#.#.#.#.#.###.#####.#.# +#2..........#...#...#.#...#.#.............#.#.#.......#...#.....#...........#.#...#.#.#.....#.#...#.#.#.........#...#...#.#...#.....#.........#...#...#...#.....#.....#.....#...# +#####.#.#.###.#.#####.###.#.#.#.###.###.###.###.#.###.#.#.#####.#.#.#########.#.###.#.#####.#.#####.#.#.###.#.#.#.#.###.###.#.###.#######.#############.###.###.###.###.###.#.### +#.#.......#...#...#...#.......#...........#...#.#.....#...#.......#.....#...#.....#.#.......#.........#...#.#.....#.#...#.............#.....#.............#.#...#.#...#.......#.# +#.#.#.#####.#.#.###.###.###.#.#.#.#.#.#####.#.#.#.#.###.###.#.#####.#.#####.#.#.###.#.#####.#.###.###.###.#.###.#.#.#.#.#.#########.###.###.#######.###.#.#.#.###.#####.###.#.#.# +#.....#.#...#.#.....#...#.....#...#...#...#.#...#...#.#.......#.#...#.......#.#.#.............#...#...#...#.....#.#.........#...#.#.#...#...#...........#...#.#7#.#.....#.....#.# +###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.###.#.#.#.###.#.#.#.#.#.#####.#.#######.#.###.#.#.#.#.#.#####.###.#.#.#.#.#.#.#.#.#.#.#.###.###.#.#.#.#.###.#.#.###.#.#.#.###.#.###.#.#.###.#.# +#.#...#.....#.#...#.#.......#.#.......#.........#.#.#.#...............#.....#...#.#.........#.......#.#.#.#...#...#.#.#.....#.....#.#.#...#...#...#.#.#.....#...#.....#...#...#.# +#.#####.#######.#.#########.#.#.###.###.#.#####.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#####.###.#.#.#.#.#.###.#######.#.#.###.#.#.#.###.###.#.###.###.#.#.###.#.###.#.#.#.#####.#.# +#.#.........#.#.#...#.....#.....#...#.............#...#...#.#.......#...#.#.......#.......#...#.....#...#...#.............#.#.........#...#...#...........#...#.......#.#.....#.# +#.#.#.#######.#.#.#.###.#.#.#.#.###.#.#.#.#.#.#.#.#.#####.#.#.###.#.#.#.#.#.#.#.#.###.###.###.#####.#.#.#####.#.#######.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.#####.#.#.#.#######.#.# +#...#.#.......#.#...#...........#...#.......#.....#...#.....#.........#.....#...#.........#.#...#...#...#.....#.......#...#.............#.#.........#.....#.....#.....#.#...#.#.# +#.###.#.###.#.###.#.###########.#######.###.#########.#.#.#.#.#.###.###.#.#.#.###.#.###.###.#.#.#.#.#.#.#.###.#.#####.#####.#.###.###.#.#.#.#######.###.#.#.#####.###.#.#.###.#.# +#.#.....#.....#.#.....#4........#...#...#.#.....#...#.#.#...#.#.........#.....#.......#.#.......#.#.....#.....#...............#.....#.#.#.#...#.........#...#...#.........#...#.# +###.#####.#.#.#.#########.#.#.#####.#.#.#.###.###.#.#.#.#.#.###.#.#.###.###.#.###.###.#.###########.###.#.#.#.#.###.#####.#.#.#.#.###.###.#.#.#.#.#.#.#.#.###.###.#.###.#.#.#.#.# +#.........#.#.....#.....#.#.....#.#.#.#...#.....#.......#...#.#...#.....#.......#.....#.........#.......#...#.#.#.......#.......#...#...#...#...#.#.#...#.....#...#...#...#.....# +#.#.###.###.###.###.#.###.#.#.###.###.###.#.#.#.#.#####.###.#.#.#.#.#.###.#.#####.#.###.#.#.#.#.#.#.###.#.###.#.#.#.#.#########.#.#####.#.#.#.#.#####.#.#.#######.#.#.###.###.#.# +#.............#.#...#.#.....#.#...#.........#.....#...#.......#...#.......#.......#...........#...#...#.#...#...#.....#...........#.....#.#...#.....#.....#.#.........#.....#.#.# +#.#.#.###.#.#.#####.###.#.#.#.#.#.#.#.#####.###.#.#.#####.#.#.#.#.#####.#.###.#####.#############.#.#.###.#.#.#.#####.#.#.#.#.#.#.#.###.###.###.#.#.#.###.#.#.#.#.#.#.###.#.###.# +#.#...#.#.#.....#.............#...#.........#...#.#...#...#...#...#...........#.#.#.#.....#...#.....#.#.#...#...#.#.........#.....#.........#...........#.....#...#...#.......#.# +#.#.#.#.#.###.#.#.###.#.#######.#.#.#.#.#.#.#.#.#.###.#.###.###.###.#####.#.###.#.#.###.#.#.#######.#.#.#.###.###.#.###.#####.#.#.#####.#.#.#.#.#####.#.#.#####.#.#####.######### +#.......#.....#...#...#.....#...........#...#.#...#.........#...#.....#...........#.....#.#.....#...#...#.#...#...#...#.....#...........#...#.#...#...#.....#.....#...........#6# +#.#.#.#.#######.###.#.#.###.#.#.###.#####.#.###.#.#######.#.#####.#.#.#.#########.#.###.#.#.#####.#.#.###.#.#########.###.#.#####.###.#.###.#.#.#.###.#.###.#.#.#.#.#.#.#.#####.# +#.....#.............#...#.#...#...#.#5......#...#...#.....#.............#.#.......#.....#.....#...........#.........#...#.#.....#.#.#.#...#...........#.#.#.......#.............# +################################################################################################################################################################################# diff --git a/src/main.rs b/src/main.rs index 6215947..83a7ffe 100644 --- a/src/main.rs +++ b/src/main.rs @@ -40,6 +40,7 @@ extern crate test; pub mod util; +pub use atools::prelude::*; use atools::{CollectArray, prelude::*}; use itertools::chain; use lower::apply; @@ -60,53 +61,47 @@ type u32x3 = Simd<u32, 3>; #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] -pub unsafe fn p1(x: &'static str) -> impl Display { - let mut x = x - .行() - .map(|x| x.μₙ(b' ').collect::<Vec<_>>()) - .collect::<Vec<_>>(); - let mut ptr = 0i32; - let mut regis = - HashMap::<&[u8], i32>::from_iter([(&b"a"[..], 12), (b"b", 0), (b"c", 1), (b"d", 0)]); - while let Some(i) = x.get(ptr as usize).cloned() { - let p = |j: usize| i[j].str().parse::<i32>().unwrap_or_else(|_| regis[i[j]]); - match i[0] { - b"tgl" => { - x.get_mut((regis[i[1]] + ptr as i32) as usize).map(|x| { - let x = &mut x[0]; - *x = match *x { - b"inc" => b"dec", - b"dec" | b"tgl" => b"inc", - b"jnz" => b"cpy", - b"cpy" => b"jnz", - x => unreachable!("{x:?}"), - } - }); +pub unsafe fn p1(x: &[u8; ISIZE]) -> impl Display { + let grid = x.chunked::<178>(); + let map = (0..8) + .tuple_combinations() + .map_w(|(a, b)| { + util::steps( + grid.find(a + b'0'), + |x| { + Dir::ALL + .iter() + .flat_map(move |&d| d + x) + .filter(|&(x, y)| grid[y][x] != b'#') + }, + |&x| x == grid.find(b + b'0'), + ) + .unwrap() + .1 + }) + .collect_twm(); + (1..8) + .permutations(7) + .map(|x| { + chain! { + once(0), + x, + once(0) // p2 } - b"cpy" => *regis.get_mut(i[2]).unwrap() = p(1), - b"inc" => *regis.get_mut(i[1]).unwrap() += 1, - b"dec" => *regis.get_mut(i[1]).unwrap() -= 1, - b"jnz" if p(1) != 0 => { - ptr += p(2); - continue; - } - _ => {} - } - ptr += 1; - } - for e in x { - println!("{}", e.p()); - } - - regis[&b"a"[..]] + .tuple_windows() + .map(|(a, b)| map[&(a, b)]) + .sum::<usize>() + }) + .min() + .unwrap() } - +const ISIZE: usize = include_bytes!("inp.txt").len(); fn main() { - unsafe { println!("{}", p1(include_str!("inp.txt"))) }; + unsafe { println!("{}", p1(include_bytes!("inp.txt"))) }; } #[bench] fn benc(b: &mut test::Bencher) { - let i = boxd(include_str!("inp.txt")); + let i = boxd(include_bytes!("inp.txt")); b.iter(|| unsafe { p1(i) }); } diff --git a/src/util.rs b/src/util.rs index 482b9ec..9613bf1 100644 --- a/src/util.rs +++ b/src/util.rs @@ -21,11 +21,12 @@ use std::{ pub mod prelude { pub use super::{ - BoolTools, DigiCount, Dir, FilterBy, FilterBy3, GreekTools, IntoCombinations, IntoLines, - IterͶ, MapWith, NumTupleIterTools, ParseIter, PartitionByKey, Printable, Skip, SplitU8, - Str, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, - UnifiedTupleUtils, UnsoundUtilities, Widen, countmap, even, gcd, gt, infinite_successors, - l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, twice, Ͷ, Α, Ι, Κ, Λ, Μ, + BoolTools, DigiCount, Dir, FilterBy, FilterBy3, GreekTools, GridFind, IntoCombinations, + IntoLines, IterͶ, MapWith, NumTupleIterTools, ParseIter, PartitionByKey, Printable, Skip, + SplitU8, Str, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, + TwoWayMapCollect, UnifiedTupleUtils, UnsoundUtilities, Widen, countmap, even, gcd, gt, + infinite_successors, l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, twice, Ͷ, + Α, Ι, Κ, Λ, Μ, }; #[allow(unused_imports)] pub(crate) use super::{C, bits, dang, leek, mat, shucks}; @@ -504,6 +505,44 @@ pub fn dijkstra_h<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16) dang!() } +pub fn steps<N: Debug + Eq + Hash + Clone + Ord, I: Iterator<Item = N>>( + start: N, + graph: impl Fn(N) -> I, + end: impl Fn(&N) -> bool, +) -> Option<(N, usize)> { + bfs( + (start, 0usize), + |(n, steps)| graph(n).map(move |x| (x, steps + 1)), + |x| end(&x.0), + ) +} + +pub fn bfs<N: Debug + Eq + Hash + Clone, I: Iterator<Item = N>>( + start: N, + graph: impl Fn(N) -> I, + end: impl Fn(&N) -> bool, +) -> Option<N> { + let mut q = VecDeque::with_capacity(1024); + let mut s = HashSet::default(); + q.push_back(start); + while let Some(n) = q.pop_front() { + if end(&n) { + return Some(n); + } + if !s.insert(n.clone()) { + continue; + } + for n in graph(n) { + if s.contains(&n) { + continue; + } + // print!("{n:?} "); + q.push_back(n); + } + } + None +} + pub fn dijkstra<N: Debug + Eq + Hash + Clone + Ord, I: Iterator<Item = (N, u16)>>( start: N, graph: impl Fn(N) -> I, @@ -1898,3 +1937,27 @@ impl BoolTools for bool { self } } + +pub trait GridFind { + fn find(self, c: u8) -> (usize, usize); +} +impl<const N: usize, const M: usize> GridFind for [[u8; N]; M] { + fn find(self, c: u8) -> (usize, usize) { + let i = memchr::memchr(c, self.as_flattened()).ψ(); + (i % N, i / N) + } +} + +pub trait TwoWayMapCollect<K, V>: Iterator { + fn collect_twm(self) -> HashMap<(K, K), V>; +} +impl<K: Eq + Hash + Clone, V: Clone, I: Iterator<Item = ((K, K), V)>> TwoWayMapCollect<K, V> for I { + fn collect_twm(self) -> HashMap<(K, K), V> { + let mut m = HashMap::default(); + for ((a, b), c) in self { + m.insert((a.clone(), b.clone()), c.clone()); + m.insert((b, a), c); + } + m + } +} |