25/11 p1 - aoc

heh

master 1Branch 0Tags

Clone

HTTPS

SSH

Open with VS Code

25/11 p1

Browse Source

bendn 3 months ago

parent 16d1342 · commit 09f8d8a

Diffstat

-rw-r--r--

src/main.rs

1602

-rw-r--r--

src/util.rs

2 files changed, 26 insertions, 1583 deletions

diff --git a/src/main.rs b/src/main.rs
index 25ef7f5..409cee4 100644
--- a/src/main.rs
+++ b/src/main.rs

@@ -63,6 +63,7 @@ use rustc_hash::FxBuildHasher;

use std::{

arch::x86_64::*,

cmp::{Reverse, minmax},

+ collections::HashMap,

hash::Hash,

hint::{assert_unchecked, unreachable_unchecked},

mem::{MaybeUninit, take, zeroed},

@@ -79,1571 +80,40 @@ mod rah;

use atools::prelude::*;

use crate::util::UnionFind;

-pub unsafe fn p2(x: &'static [u8]) -> impl Debug {

- let x = x

- .行()

- .map(|x| {

- let (expected, buttons) = x.μ(' ');

- let mut c = vec![];

- let mut c_ = 0;

- let mut r = vec![];

- let (mut buttons, power) = buttons.rsplit_once(|x| *x == b' ').unwrap();

- while let Some(x) = buttons.get(0) {

- match x {

- b'(' => {}

- d @ b'0'..=b'9' => {

- c_ *= 10;

- c_ += (d - b'0') as u32

- }

- b',' => {

- c.push(c_);

- c_ = 0;

- }

- b')' => {

- c.push(c_);

- c_ = 0;

- r.push(c.clone());

- c.clear();

- }

- b' ' => {}

- x => panic!("{}", *x as char),

- }

- buttons = &buttons[1..];

- }

- let mut power = &power[1..];

- let mut pvec = vec![];

- let mut c = 0;

- while let Some(x) = power.get(0) {

- match x {

- d @ b'0'..=b'9' => {

- c *= 10;

- c += (d - b'0') as u32

- }

- b',' => {

- pvec.push(c);

- c = 0;

- }

- b'}' => {

- pvec.push(c);

- break;

- }

- b' ' => {}

- x => panic!("{}", *x as char),

- }

- power = &power[1..];

- }

- (

- expected[1..expected.len() - 1]

- .iter()

- .map(|x| *x == b'#')

- .collect::<Vec<_>>(),

- r,

- pvec,

- )

- })

- .collect::<Vec<_>>();

- let mut sum = 0;

- z3::with_z3_config(&z3::Config::default(), || {

- for (xpected, buttons, power) in x {

- let o = z3::Optimize::new();

- let p = (0..buttons.len())

- .map(|_| Int::fresh_const("p"))

- .inspect(|x| o.assert(&x.ge(0)))

- .collect::<Vec<_>>();

- for j in 0..power.len() {

- let sat = &buttons

- .iter()

- .enumerate()

- .filter(|(_, b)| b.contains(&(j as u32)))

- .map(|(x, _)| p[x].clone())

- .reduce(|a, b| a + b)

- .unwrap()

- .eq(power[j]);

- o.assert(sat);

- }

- let s = p.iter().cloned().reduce(|a, b| a + b).unwrap();

- o.minimize(&s);

- assert_eq!(o.check(&[]), z3::SatResult::Sat);

- let m = o.get_model().unwrap();

- sum += m.eval(&s, true).unwrap().as_i64().unwrap();

- }

- });

- sum

#[unsafe(no_mangle)]

#[implicit_fn::implicit_fn]

-pub unsafe fn p1(x: &'static [u8]) -> impl Debug {

- let mut place = u16x16::from_array([0; 16]);

- let mut p = x.as_ptr();

- let end = p.add(x.len());

- let mut sum = 0;

- while p != end {

- let mut wide = 0;

- _ = p.λ();

- let mut xpected = 0;

- let mut i = 0u32;

- while let x = p.λ()

- && x != b']'

- {

- xpected |= (x as u16 & 1) << i;

- i += 1;

- }

- p.λ(); // 32

- while p.λ() == b'(' {

- let mut bt = 0;

- loop {

- bt |= 1 << (p.λ() - b'0');

- if p.λ() == b')' {

- p.λ();

- break;

- }

- place[wide] = bt;

- wide += 1;

- }

- // dont simdify this

- while let x = p.λ()

- && x != b'\n'

- {}

- // let bt = C! { &place[..wide] };

- // let n = bt.len();

- sum += 'out: {

- // each bit is a button; one button ought only be pressed once.

- for pressed in 1..wide {

- let things = MASKS[pressed][wide];

- for &set in things {

- // }

- // // let mut set = (1 << pressed) - 1;

- // // let limit = (1u32 << wide) - 1;

- // // println!("--");

- // while set < limit {

- // println!("{set}");

- // let mut mk = set;

- let mk = mask16x16::from_bitmask(set as _);

- if mk.select(place, u16x16::splat(0)).reduce_xor() == xpected {

- break 'out pressed as u32;

- }

- // while mk != 0 {3

- // st ^= C!(bt[mk.trailing_zeros() as usize]);

- // mk ^= mk & mk.wrapping_neg();

- // }

- // if st == 0 {

- // break 'out pressed as u32;

- // }

- // le gosper

- // let c = set & set.wrapping_neg();

- // let s = set + c;

- // core::hint::assert_unchecked(c != 0);

- // set = (((s ^ set) >> 2) / c) | s;

- }

+pub unsafe fn p1(x: &'static [u8; ISIZE]) -> impl Debug {

+ let mut g = HashMap::<_, Vec<_>>::new();

+ x.行()

+ .map(|x| {

+ let (start, dest) = x.μ(':');

+ for lem in dest.str().split_ascii_whitespace() {

+ g.entry(start).or_default().push(lem.as_bytes());

}

- wide as u32

- };

- }

- sum

+ })

+ .θ();

+ let mut n = 0;

+ util::countg(

+ b"you".as_slice(),

+ &mut |x| g[x].clone().into_iter(),

+ &mut |x| x == b"out",

+ &mut n,

+ &mut HashSet::default(),

+ );

+ n

}

-// index by k, n

-// const MASKS: [[&[u16]; 14]; 14] = include!("../xaxa");

-// pub(crate) const ISIZE: usize = include_bytes!("inp.txt").len();

-static mut MASKS: [[&[u16]; 14]; 14] = [

- [&[]; 14],

- [

- &[],

- &[1, 2],

- &[1, 2, 4],

- &[1, 2, 4, 8],

- &[1, 2, 4, 8, 16],

- &[1, 2, 4, 8, 16, 32],

- &[1, 2, 4, 8, 16, 32, 64],

- &[1, 2, 4, 8, 16, 32, 64, 128],

- &[1, 2, 4, 8, 16, 32, 64, 128, 256],

- &[1, 2, 4, 8, 16, 32, 64, 128, 256, 512],

- &[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024],

- &[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048],

- &[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096],

- ],

- [

- &[],

- &[3, 5, 6],

- &[3, 5, 6, 9, 10, 12],

- &[3, 5, 6, 9, 10, 12, 17, 18, 20, 24],

- &[3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516,

- 520, 528, 544, 576, 640, 768,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516,

- 520, 528, 544, 576, 640, 768, 1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280,

- 1536,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516,

- 520, 528, 544, 576, 640, 768, 1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280,

- 1536, 2049, 2050, 2052, 2056, 2064, 2080, 2112, 2176, 2304, 2560, 3072,

- ],

- &[

- 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129,

- 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516,

- 520, 528, 544, 576, 640, 768, 1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280,

- 1536, 2049, 2050, 2052, 2056, 2064, 2080, 2112, 2176, 2304, 2560, 3072, 4097, 4098,

- 4100, 4104, 4112, 4128, 4160, 4224, 4352, 4608, 5120, 6144,

- ],

- [

- &[],

- &[7, 11, 13, 14],

- &[7, 11, 13, 14, 19, 21, 22, 25, 26, 28],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56,

- ],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69,

- 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112,

- ],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69,

- 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140,

- 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224,

- ],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69,

- 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140,

- 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261,

- 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328,

- 336, 352, 385, 386, 388, 392, 400, 416, 448,

- ],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69,

- 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140,

- 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261,

- 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328,

- 336, 352, 385, 386, 388, 392, 400, 416, 448, 515, 517, 518, 521, 522, 524, 529, 530,

- 532, 536, 545, 546, 548, 552, 560, 577, 578, 580, 584, 592, 608, 641, 642, 644, 648,

- 656, 672, 704, 769, 770, 772, 776, 784, 800, 832, 896,

- ],

- &[

- 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69,

- 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140,

- 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261,

- 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328,

- 336, 352, 385, 386, 388, 392, 400, 416, 448, 515, 517, 518, 521, 522, 524, 529, 530,

- 532, 536, 545, 546, 548, 552, 560, 577, 578, 580, 584, 592, 608, 641, 642, 644, 648,

- 656, 672, 704, 769, 770, 772, 776, 784, 800, 832, 896, 1027, 1029, 1030, 1033, 1034,

- 1036, 1041, 1042, 1044, 1048, 1057, 1058, 1060, 1064, 1072, 1089, 1090, 1092, 1096,

- 1104, 1120, 1153, 1154, 1156, 1160, 1168, 1184, 1216, 1281, 1282, 1284, 1288, 1296,

- 1312, 1344, 1408, 1537, 1538, 1540, 1544, 1552, 1568, 1600, 1664, 1792,