61

Re: Advent of Code

До речі, мій ҐітГаб з AoC/Rust.

Подякували: dot, leofun012

62 Востаннє редагувалося dot (12.12.2021 23:42:13)

Re: Advent of Code

koala написав:

Боюся, що я на тиждень зникну з форуму. Можливо, завтра вранці ще допишу. А потім же доробляти... ех...

Nitcʼ stracnoho! Raptovi spravy tcy ctcosj svojo buvaʼ. Tcekaju za tygdenj! Koly ctco, poskladneni zadatcky zazvytcaj buvajutj na vyxidnyx, jakctco ne pomyljaju sja.

63 Востаннє редагувалося dot (14.12.2021 17:25:14)

Re: Advent of Code

2021, Py.3.9.5

13
from re import findall


def folding(axis: str, number: int) -> list:
    folded = list()
    for n in range(1, number + 1):
        for x, y in set(dots):
            if axis == "x" and x in (number - n, number + n):
                folded.append((number - n, y))
            elif axis == "y" and y in (number - n, number + n):
                folded.append((x, number - n))
    return folded


def visualing() -> None:
    max_x, max_y = [max(el) + 1 for el in [*zip(*dots)]]
    for y in range(max_y):
        for x in range(max_x):
            print("#" if (x, y) in dots else " ", end="")
        print("\n", end="")
    print()


dots = list()
actions = list()
instructions = False

for line in open("input.txt").read().splitlines():
    if not line:
        instructions = True
        continue
    if instructions:
        axis, number = findall(r"([xy])=(\d+)", line)[0]
        actions.append((axis, int(number)))
    else:
        dots.append(tuple(map(int, findall(r"\d+", line))))

for number, action in enumerate(actions):
    dots = folding(*action)
    if number == 1:
        print("Part One:", len(dots))

print("Part Two:")
visualing()
14
from collections import Counter

polymer, _, *rules = open("input.txt").read().splitlines()
rules = dict(rule.split(" -> ") for rule in rules)
pairs = Counter(polymer[i] + polymer[i + 1] for i in range(len(polymer) - 1))
chars = Counter(polymer)
steps = (10, 40)

for i in range(1, steps[-1] + 1):
    for (a, b), count in pairs.copy().items():
        if a + b in rules.keys():
            insert = rules[a + b]
            pairs[a + b] -= count
            pairs[a + insert] += count
            pairs[insert + b] += count
            chars[insert] += count
    if i in steps:
        print("Answer:", max(chars.values()) - min(chars.values()))

64 Востаннє редагувалося dot (16.12.2021 04:54:44)

Re: Advent of Code

2021#15, Py3.9.5
from queue import PriorityQueue
from collections import defaultdict


def plus_form_sides(_y, _x, y_len, x_len):
    for side_y, side_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        y, x = (_y + dr, _x + dc)
        if 0 <= y < y_len and 0 <= x < x_len:
            yield (y, x)


# Updated from:
# https://stackabuse.com/dijkstras-algorithm-in-python
def dijkstra(graf: list) -> int:
    y_len, x_len = len(graf), len(graf[0])
    visited = set()

    start_vertex = (0, 0)
    stop_vertex = (y_len - 1, x_len - 1)

    min_distances = defaultdict(lambda: float("inf"))
    min_distances[start_vertex] = 0

    pq = PriorityQueue()
    pq.put((0, start_vertex))

    while not pq.empty():
        distance, current_vertex = pq.get()

        if current_vertex == stop_vertex:
            return distance

        if current_vertex in visited:
            continue

        visited.add(current_vertex)

        for y, x in plus_form_sides(*current_vertex, y_len, x_len):
            if (y, x) in visited:
                continue

            new_distance = distance + graf[y][x]

            if new_distance < min_distances[(y, x)]:
                min_distances[(y, x)] = new_distance
                pq.put((new_distance, (y, x)))

    return float("inf")


cavern = [list(map(int, list(line))) for line in open("input.txt").read().splitlines()]

print("Part One:", dijkstra(cavern))

blocks = [[[v + s if v + s < 10 else v + s - 9 for v in row] for row in cavern] for s in range(9)]
y_len, x_len = len(blocks), len(blocks[0])

cavern = list()
larger = 5

for s in range(larger):
    for x in range(x_len):
        row = list()
        for y in range(larger):
            row.extend(blocks[y + s if y + s < y_len else y + s - y_len][x])
        cavern.append(row)

print("Part Two:", dijkstra(cavern))
Sutj

Zadatca osnovana na alqoritmi Dejkstry, mogna, hadaju, takog tcerez A* (pro njoho piznav piznjice, ale sprobuju, pry nahodji), hlybynoju i cyrynoju. Ljinjky bulo z nula pysaty, tomu tupo vzjav hotovu funtsiju — vkazano vidky, ale pryiclo sja perepysaty, a potim, sebto dlja druhoji zadatcy, znov perepysaty, bo tak poviljno robylo, ctco mij komp vge vbyvav Xroma, VS Koda i, lybonj, samoho sebe.

Tcas druhoji.

time python3 main.py  
6,05s user 
0,14s system 

65

Re: Advent of Code

І я знову тут!

2021/day13.rs
#[derive(Copy, Clone)]
pub enum Fold {
    X,
    Y,
}

#[derive(Clone)]
pub struct InvisiblePaper {
    dots: std::collections::HashSet<(i32, i32)>,
    folds: Vec<(Fold, i32)>,
}

impl InvisiblePaper {
    fn do_fold(&mut self, fold: (Fold, i32)) {
        self.dots = self.dots
                        .iter()
                        .map(|dot|
                            match fold.0 {
                                Fold::X => (fold.1 - (fold.1-dot.0).abs(), dot.1),
                                Fold::Y => (dot.0, fold.1 - (fold.1-dot.1).abs()),
                            })
                        .collect();
    }
}

pub fn parse_input(input: &str) -> InvisiblePaper {
    let lines = input.lines();
    let mut dots_done = false;
    let mut data = InvisiblePaper {
        dots: std::collections::HashSet::new(), 
        folds: Vec::new(),
    };
    for line in lines {
        if line.is_empty() {
            dots_done = true;
        } else {
            if !dots_done {
                let mut dot = line.split(',');
                data.dots.insert((dot.next().unwrap().parse().unwrap(),
                                dot.next().unwrap().parse().unwrap()));
            } else {
                let mut fold = line.split('=');
                let fold_type = if fold.next().unwrap().chars().nth(11)==Some('x') {
                    Fold::X
                } else {
                    Fold::Y
                };
                data.folds.push((fold_type,fold.next().unwrap().parse().unwrap()));
            }
        }
    }
    data
}

pub fn task1(data: &InvisiblePaper) -> usize {
    let mut data = data.clone();
    data.do_fold(data.folds[0]);
    data.dots.len()
}

pub fn task2(data: &InvisiblePaper) -> usize {
    let folds = &data.folds;
    let mut data = data.clone();
    for &fold in folds {
        data.do_fold(fold);
    }
    let max_x = data.dots.iter().map(|(x, _)|x).max().unwrap() + 1;
    let max_y = data.dots.iter().map(|(_, y)|y).max().unwrap() + 1;
    for y in 0..max_y {
        for x in 0..max_x {
            print!("{}", if data.dots.contains(&(x,y)) {"#"} else {"."});
        }
        println!("");
    }
    0
}

66

Re: Advent of Code

Z povernennjem! A ja sprobuju vge pidkljutcyty sja pislja/zavtra.

67

Re: Advent of Code

Перша частина є:

year2021/day14.rs
#[derive(Clone)]
pub struct PolymerData {
    polymer: Vec<char>,
    rules: std::collections::HashMap<(char, char), char>,
}

pub fn parse_input(input: &str) -> PolymerData {
    let mut lines = input.lines();
    let mut polymer_data = PolymerData {
        polymer: lines.next().unwrap().chars().collect(),
        rules: std::collections::HashMap::new(),
    };
    lines.next();
    for line in lines {
        let mut parts = line.split(" -> ");
        let left = parts.next().unwrap();
        let right = parts.next().unwrap();
        polymer_data.rules.insert(
            (left.chars().nth(0).unwrap(), left.chars().nth(1).unwrap()),
            right.chars().nth(0).unwrap(),
        );
    }
    polymer_data
}

pub fn task1(data: &PolymerData) -> usize {
    let mut polymer = data.polymer.clone();
    for _ in 0..10 {
        let mut new_polymer = vec![polymer[0]];
        for pair in polymer.windows(2) {
            if let &[left, right] = pair {
                match data.rules.get(&(left, right)) {
                    Some(&v) => new_polymer.push(v),
                    _ => (),
                }
                new_polymer.push(right);
            }
        }
        polymer = new_polymer;
    }

    let mut counter = std::collections::HashMap::new();
    for element in polymer {
        *counter.entry(element).or_insert(0) += 1;
    }
    let min = counter.values().min().unwrap();
    let max = counter.values().max().unwrap();
    max - min
}

pub fn task2(data: &PolymerData) -> usize {
    let mut polymer = data.polymer.clone();
    for _ in 0..40 {
        let mut new_polymer = vec![polymer[0]];
        for pair in polymer.windows(2) {
            if let &[left, right] = pair {
                match data.rules.get(&(left, right)) {
                    Some(&v) => new_polymer.push(v),
                    _ => (),
                }
                new_polymer.push(right);
            }
        }
        polymer = new_polymer;
    }

    let mut counter = std::collections::HashMap::new();
    for element in polymer {
        *counter.entry(element).or_insert(0) += 1;
    }
    let min = counter.values().min().unwrap();
    let max = counter.values().max().unwrap();
    max - min
}

Другу скопіював з першої, дістав

memory allocation of 34359738368 bytes failed

Завтра зроблю мемоїзацію, ніби очевидно, як.

68

Re: Advent of Code

Rust і очевидно - речі несумісні.

Подякували: mamkin haker, dot2

69

Re: Advent of Code

year2021/day14.rs
type Counter = std::collections::HashMap<char, usize>;

type Polymer = Vec<char>;
type PolymerRules = std::collections::HashMap<(char, char), char>;

#[derive(Clone)]
pub struct PolymerData {
    polymer: Polymer,
    rules: PolymerRules,
    counters: std::collections::HashMap<(char, char, usize), Counter>,
}

impl PolymerData {
    fn from_str(input: &str) -> PolymerData {
        let mut lines = input.lines();
        let mut polymer_data = PolymerData {
            polymer: lines.next().unwrap().chars().collect(),
            rules: std::collections::HashMap::new(),
            counters: std::collections::HashMap::new(),
        };
        lines.next();
        for line in lines {
            let mut parts = line.split(" -> ");
            let left = parts.next().unwrap();
            let right = parts.next().unwrap();
            polymer_data.rules.insert(
                (left.chars().nth(0).unwrap(), left.chars().nth(1).unwrap()),
                right.chars().nth(0).unwrap(),
            );
        }
        polymer_data
    }

    fn composition_recursive(&mut self, polymer: (char, char), steps: usize) -> Counter {
        let (left, right) = polymer;
        if !self.counters.contains_key(&(left, right, steps)) {
            let counters = if steps == 0 {
                [(right, 1)].into()
            } else {
                match self.rules.get(&(left, right)) {
                    Some(&v) => {
                        let mut left = self.composition_recursive((left, v), steps - 1);
                        for (element, count) in self.composition_recursive((v, right), steps - 1) {
                            *left.entry(element).or_insert(0) += count;
                        }
                        left
                    }
                    None => [(right, 1)].into(),
                }
            };
            self.counters.insert((left, right, steps), counters);
        }
        self.counters.get(&(left, right, steps)).unwrap().clone()
    }

    fn composition(&mut self, steps: usize) -> usize {
        let mut counter: Counter = [(self.polymer[0], 1)].into();
        for i in 0..self.polymer.len() - 1 {
            for (element, count) in
                self.composition_recursive((self.polymer[i], self.polymer[i + 1]), steps)
            {
                *counter.entry(element).or_insert(0) += count;
            }
        }

        let min = counter.values().min().unwrap();
        let max = counter.values().max().unwrap();
        max - min
    }
}

pub fn parse_input(input: &str) -> PolymerData {
    PolymerData::from_str(input)
}

fn task(data: &PolymerData, steps: usize) -> usize {
    let mut data = data.clone();
    data.composition(steps)
}

pub fn task1(data: &PolymerData) -> usize {
    task(data, 10)
}

pub fn task2(data: &PolymerData) -> usize {
    task(data, 40)
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let input = "NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C";

        assert_eq!(task1(&parse_input(input)), 1588);
    }
}

Зробив. Відчуваю, що нагородив фігні, але воно значно коротше за те, що було раніше, і працює як слід, а це Rust, тому, мабуть, небагато.

70

Re: Advent of Code

Дейкстра.

year2021/day15.rs
type Cave = Vec<Vec<usize>>;

pub fn parse_input(input: &str) -> Cave {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|risk| risk.to_digit(10).unwrap() as usize)
                .collect()
        })
        .collect()
}

pub fn dijkstra(cave: &Cave) -> usize {
    use std::collections::BTreeMap;
    let size = cave.len();
    let mut len_cave = vec![vec![None::<usize>; size]; size];
    len_cave[0][0] = Some(0);
    let mut to_search: BTreeMap<usize, Vec<(usize, usize)>> = [(0, [(0, 0)].into())].into();
    while !to_search.is_empty() {
        let min_key = *to_search.keys().next().unwrap();
        let (x, y) = to_search.get_mut(&min_key).unwrap().pop().unwrap();
        if to_search[&min_key].is_empty() {
            to_search.remove(&min_key);
        }
        for (dx, dy) in [(0, 1), (1, 0), (-1, 0), (0, -1)] {
            let x = x as i32 + dx;
            let y = y as i32 + dy;
            if 0 <= x && x < size as i32 && 0 <= y && y < size as i32 {
                let x = x as usize;
                let y = y as usize;
                let old = len_cave[x][y];
                len_cave[x][y] = Some(match len_cave[x][y] {
                    Some(risk) => std::cmp::min(risk, min_key + cave[x][y]),
                    None => min_key + cave[x][y],
                });
                if len_cave[x][y] != old {
                    to_search
                        .entry(len_cave[x][y].unwrap())
                        .or_insert(Vec::new())
                        .push((x, y));
                }
            }
        }
    }
    len_cave[size - 1][size - 1].unwrap() - len_cave[0][0].unwrap()
}

pub fn task1(cave: &Cave) -> usize {
    dijkstra(cave)
}

pub fn task2(cave: &Cave) -> usize {
    let size = cave.len();
    let mut real_cave = vec![vec![0; size * 5]; size * 5];
    for i_mult in 0..5 {
        for j_mult in 0..5 {
            for i in 0..size {
                for j in 0..size {
                    real_cave[i_mult * size + i][j_mult * size + j] =
                        (cave[i][j] + i_mult + j_mult - 1) % 9 + 1;
                }
            }
        }
    }
    dijkstra(&real_cave)
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let input = "1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581";
        assert_eq!(task1(&parse_input(input)), 40);
    }
}

71

Re: Advent of Code

year2021/day16.rs
pub enum PacketContent {
    Literal(usize),
    Operator(Box<Vec<Packet>>),
}

pub struct Packet {
    version: u8,
    type_id: u8,
    content: PacketContent,
}

const LITERAL_ID: u8 = 4;
const BIT_LENGTH_SIZE: usize = 15;
const PACKETS_COUNT_SIZE: usize = 11;

#[derive(Debug)]
enum Error {
    UnexpectedEndOfStream,
}

fn get_number(input: &[u8]) -> usize {
    let mut number = 0_usize;
    for &bit in input {
        number = number << 1 | bit as usize;
    }
    number
}

fn parse_packet(input: &[u8]) -> Result<(Packet, &[u8]), Error> {
    if input.len() < 7 {
        return Err(Error::UnexpectedEndOfStream);
    }
    let version = get_number(&input[..3]) as u8;
    let type_id = get_number(&input[3..6]) as u8;
    if type_id == LITERAL_ID {
        let mut number = 0;
        let mut ptr = 6;
        loop {
            let next_part = get_number(&input[ptr..ptr + 5]);
            ptr += 5;
            number = (number << 4) | (next_part & 0xF);
            if next_part & 0x10 == 0 {
                break;
            }
        }
        Ok((
            Packet {
                version,
                type_id,
                content: PacketContent::Literal(number),
            },
            &input[ptr..],
        ))
    } else {
        let length_type_id = get_number(&input[6..7]);
        match length_type_id {
            0 => {
                let header_end = 7 + BIT_LENGTH_SIZE;
                let bit_length = get_number(&input[7..header_end]);
                let mut subpackets = Box::new(vec![]);
                let mut own_input = &input[header_end..header_end + bit_length];
                while own_input.len() > 0 {
                    let (packet, rest) = parse_packet(own_input)?;
                    subpackets.push(packet);
                    own_input = rest;
                }
                Ok((
                    Packet {
                        version,
                        type_id,
                        content: PacketContent::Operator(subpackets),
                    },
                    &input[header_end + bit_length..],
                ))
            }
            1 => {
                let header_end = 7 + PACKETS_COUNT_SIZE;
                let packet_count = get_number(&input[7..header_end]);
                let mut subpackets = Box::new(Vec::with_capacity(packet_count));
                let mut own_input = &input[header_end..];
                for _ in 0..packet_count {
                    let (packet, rest) = parse_packet(own_input)?;
                    subpackets.push(packet);
                    own_input = rest;
                }
                Ok((
                    Packet {
                        version,
                        type_id,
                        content: PacketContent::Operator(subpackets),
                    },
                    own_input,
                ))
            }
            _ => panic!("Wrong length type id: {}", length_type_id),
        }
    }
}

pub fn parse_input(input: &str) -> Packet {
    let bit_stream: Vec<u8> = input
        .chars()
        .flat_map(|hex_digit| {
            (0..4).rev().map(move |i| {
                ((hex_digit.to_digit(16).unwrap() >> i) & 1) as u8
            })
        })
        .collect();
    parse_packet(&bit_stream).unwrap().0
}

impl Packet {
    fn version_sum(&self) -> usize {
        self.version as usize
            + match &self.content {
                PacketContent::Literal(_) => 0,
                PacketContent::Operator(subpackets) => {
                    subpackets.iter().map(|p| p.version_sum()).sum()
                }
            }
    }
    fn calculate(&self) -> usize {
        match (&self.content, self.type_id) {
            (PacketContent::Operator(subpackets), 0) => {
                subpackets.iter().map(|p| p.calculate()).sum()
            }
            (PacketContent::Operator(subpackets), 1) => {
                subpackets.iter().map(|p| p.calculate()).product()
            }
            (PacketContent::Operator(subpackets), 2) => {
                subpackets.iter().map(|p| p.calculate()).min().unwrap()
            }
            (PacketContent::Operator(subpackets), 3) => {
                subpackets.iter().map(|p| p.calculate()).max().unwrap()
            }
            (&PacketContent::Literal(value), 4) => value,
            (PacketContent::Operator(subpackets), 5) => {
                if subpackets[0].calculate() > subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            (PacketContent::Operator(subpackets), 6) => {
                if subpackets[0].calculate() < subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            (PacketContent::Operator(subpackets), 7) => {
                if subpackets[0].calculate() == subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            _ => panic!("Wrong type_id: {}", self.type_id),
        }
    }
}

pub fn task1(input: &Packet) -> usize {
    input.version_sum()
}

pub fn task2(input: &Packet) -> usize {
    input.calculate()
}

Тут я спершу дещо намутив із ітераторами і отримав майже stack overflow на побудові рекурсивного темплейта. Також я дізнався, що Rust підтримує 128 вкладених шаблонів, але це число можна змінити в налаштуваннях проєкта (сподіваюся, що мені ніколи це не знадобиться).
А ще це, здається, перша задача цього року, де я не відкривав вхідні дані в браузері взагалі, і ніяк на них не дивився. Лише запускав код.

72

Re: Advent of Code

2021#16 Py3.9.5
from math import prod


class Transmission:
    def __init__(self, insert) -> None:
        self.bin = bin(int(insert, 16))[2:].zfill(len(insert) * 4)
        self.pos = 0

    def to_dec(self, step) -> int:
        decimal = int(self.bin[self.pos : self.pos + step], 2)
        self.pos += step
        return decimal

    def packet(self):
        version = self.to_dec(3)
        type_id = self.to_dec(3)
        data = self.packet_data(type_id)
        return version, type_id, data

    def n_packets(self, n, type=True):
        packets = list()
        if type:
            packets = [self.packet() for _ in range(n)]
        else:
            stop = self.pos + n
            while self.pos < stop:
                packets.append(self.packet())
        return packets

    def packet_data(self, type_id):
        if type_id == 4:
            return self.literal_value()
        if self.to_dec(1):
            return self.n_packets(self.to_dec(11))
        return self.n_packets(self.to_dec(15), False)

    def literal_value(self) -> int:
        value = str()
        last = 1
        while last:
            last = self.to_dec(1)
            value += self.bin[self.pos : self.pos + 4]
            self.pos += 4
        return int(value, 2)


def sum_versions(packet) -> int:
    version, type_id, data = packet
    return version if type_id == 4 else version + sum(map(sum_versions, data))


def calculation(packet):
    _, type_id, data = packet
    if type_id == 4:
        return data
    values = map(calculation, data)

    if type_id == 0:
        return sum(values)
    if type_id == 1:
        return prod(values)
    if type_id == 2:
        return min(values)
    if type_id == 3:
        return max(values)

    a, b = values
    if type_id == 5:
        return int(a > b)
    if type_id == 6:
        return int(a < b)
    return int(a == b)


packet = Transmission(open("input.txt").readline().strip()).packet()
print("Part One:", sum_versions(packet))
print("Part Two:", calculation(packet))

73

Re: Advent of Code

year2021/day18.rs
use std::boxed::Box;
use std::str::Chars;

#[derive(Clone)]
pub enum SnailfishNumber {
    Regular(u32),
    Pair(Box<(SnailfishNumber, SnailfishNumber)>),
}

impl std::fmt::Debug for SnailfishNumber {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            SnailfishNumber::Regular(value) => value.fmt(fmt),
            SnailfishNumber::Pair(pair) => {
                write!(fmt, "[{:?},{:?}]", &pair.0, &pair.1)
            }
        }
    }
}

impl SnailfishNumber {
    fn pair(left: SnailfishNumber, right: SnailfishNumber) -> SnailfishNumber {
        SnailfishNumber::Pair(Box::new((left, right)))
    }
    fn regular(value: u32) -> SnailfishNumber {
        SnailfishNumber::Regular(value)
    }
    fn regpair(left: u32, right: u32) -> SnailfishNumber {
        SnailfishNumber::pair(
            SnailfishNumber::regular(left),
            SnailfishNumber::regular(right),
        )
    }
}

fn read_snailfish_number<'a>(input: &mut Chars<'a>) -> SnailfishNumber {
    let first = input.next().unwrap();
    if first == '[' {
        let left = read_snailfish_number(input.by_ref());
        assert_eq!(input.next().unwrap(), ',');
        let right = read_snailfish_number(input.by_ref());
        assert_eq!(input.next().unwrap(), ']');
        SnailfishNumber::pair(left, right)
    } else {
        SnailfishNumber::regular(first.to_digit(10).unwrap())
    }
}

enum Explosion {
    Not,
    Both(u32, u32),
    FromLeft(u32),
    FromRight(u32),
    Did,
}

impl Explosion {
    fn to_bool(&self) -> bool {
        match self {
            Explosion::Not => false,
            _ => true,
        }
    }
}

impl SnailfishNumber {
    fn reduce(&mut self) {
        loop {
            //println!("Calling explode for {:?}", self);
            if !self.explode(1).to_bool() {
                //println!("Calling split for {:?}", self);
                if !self.split() {
                    //println!("Done: {:?}", self);
                    break;
                }
            }
        }
    }

    fn explode(&mut self, level: u32) -> Explosion {
        //println!("Exploding level={}: {:?}", level, self);
        match self {
            SnailfishNumber::Regular(_) => Explosion::Not,
            SnailfishNumber::Pair(pair) => {
                if let (
                    SnailfishNumber::Regular(left),
                    SnailfishNumber::Regular(right),
                ) = **pair
                {
                    if level > 4 {
                        Explosion::Both(left, right)
                    } else {
                        Explosion::Not
                    }
                } else {
                    match pair.0.explode(level + 1) {
                        Explosion::Both(left_left, left_right) => {
                            pair.0 = SnailfishNumber::regular(0);
                            pair.1.insert_from_left(left_right);
                            Explosion::FromLeft(left_left)
                        }
                        Explosion::FromRight(left_right) => {
                            pair.1.insert_from_left(left_right);
                            Explosion::Did
                        }
                        Explosion::Not => match pair.1.explode(level + 1) {
                            Explosion::Both(right_left, right_right) => {
                                pair.0.insert_from_right(right_left);
                                pair.1 = SnailfishNumber::regular(0);
                                Explosion::FromRight(right_right)
                            }
                            Explosion::FromLeft(right_left) => {
                                pair.0.insert_from_right(right_left);
                                Explosion::Did
                            }
                            other => other, //Did, Not, Right
                        },
                        other => other, //Did, Not, LEft
                    }
                }
            }
        }
    }

    fn insert_from_left(&mut self, value: u32) {
        //println!("Insert left {:?} into {:?}", value, self);
        match self {
            SnailfishNumber::Regular(self_value) => {
                *self_value += value;
            }
            SnailfishNumber::Pair(pair) => {
                pair.0.insert_from_left(value);
            }
        }
    }

    fn insert_from_right(&mut self, value: u32) {
        //println!("Insert right {:?} into {:?}", value, self);
        match self {
            SnailfishNumber::Regular(self_value) => {
                *self_value += value;
            }
            SnailfishNumber::Pair(pair) => {
                pair.1.insert_from_right(value);
            }
        }
    }

    fn split(&mut self) -> bool {
        match self {
            SnailfishNumber::Regular(value) => {
                if *value >= 10 {
                    *self =
                        SnailfishNumber::regpair(*value / 2, (*value + 1) / 2);
                    true
                } else {
                    false
                }
            }
            SnailfishNumber::Pair(pair) => pair.0.split() || pair.1.split(),
        }
    }

    fn magnitude(&self) -> u32 {
        //println!("Finding magnitude of {:?}", self);
        match self {
            SnailfishNumber::Regular(v) => *v,
            SnailfishNumber::Pair(pair) => {
                3 * pair.0.magnitude() + 2 * pair.1.magnitude()
            }
        }
    }
}

fn add(left: SnailfishNumber, right: SnailfishNumber) -> SnailfishNumber {
    let mut result = SnailfishNumber::pair(left, right);
    result.reduce();
    result
}

fn sum_vec(numbers: &Vec<SnailfishNumber>) -> SnailfishNumber {
    numbers
        .iter()
        .skip(1)
        .fold(numbers[0].clone(), |acc, num| add(acc, num.clone()))
}

pub fn parse_input(input: &str) -> Vec<SnailfishNumber> {
    input
        .lines()
        .map(|line| read_snailfish_number(&mut line.chars()))
        .collect()
}

pub fn task1(input: &Vec<SnailfishNumber>) -> u32 {
    sum_vec(input).magnitude()
}

pub fn task2(input: &Vec<SnailfishNumber>) -> u32 {
    let mut best = 0;
    for i in 0..input.len() {
        for j in 0..input.len() {
            if i != j {
                best = std::cmp::max(
                    best,
                    add(input[i].clone(), input[j].clone()).magnitude(),
                );
            }
        }
    }
    best
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_reduce() {
        let data = "[[[[[9,8],1],2],3],4]
[[6,[5,[4,[3,2]]]],1]
[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]
[[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]";
        let expected = "[[[[0,9],2],3],4]
[[6,[5,[7,0]]],3]
[[3,[2,[8,0]]],[9,[5,[7,0]]]]
[[[[0,7],4],[[7,8],[6,0]]],[8,1]]";
        let mut nums = parse_input(&data);
        for (input, expected) in nums.iter_mut().zip(expected.lines()) {
            input.reduce();
            assert_eq!(format!("{:?}", input), expected);
        }
    }

    #[test]
    fn test_magnitude() {
        for (input, expected) in parse_input(
            "[[1,2],[[3,4],5]]
[[[[0,7],4],[[7,8],[6,0]]],[8,1]]
[[[[1,1],[2,2]],[3,3]],[4,4]]
[[[[3,0],[5,3]],[4,4]],[5,5]]
[[[[5,0],[7,4]],[5,5]],[6,6]]
[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]",
        )
        .iter()
        .zip([143, 1384, 445, 791, 1137, 3488].into_iter())
        {
            assert_eq!(input.magnitude(), expected);
        }
    }

    #[test]
    fn test_add1() {
        let nums = &parse_input(
            "[1,1]
[2,2]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(format!("{:?}", sum), "[[1,1],[2,2]]");
    }

    #[test]
    fn test_add3() {
        let nums = &parse_input(
            "[[[[4,3],4],4],[7,[[8,4],9]]]
[1,1]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(format!("{:?}", sum), "[[[[0,7],4],[[7,8],[6,0]]],[8,1]]");
    }

    #[test]
    fn test_add2() {
        let nums = &parse_input(
            "[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(
            format!("{:?}", sum),
            "[[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]"
        );
    }

    #[test]
    fn test_sum1() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[1,1],[2,2]],[3,3]],[4,4]]");
    }

    #[test]
    fn test_sum2() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]
[5,5]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[3,0],[5,3]],[4,4]],[5,5]]");
    }

    #[test]
    fn test_sum3() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[5,0],[7,4]],[5,5]],[6,6]]");
    }

    #[test]
    fn test_task1() {
        let data = "[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]";

        assert_eq!(task1(&parse_input(&data)), 4140);
    }
}

Довелося додавати купу тестів і дебажити. Ну і Rust опирається.
17 поки що пропустив.

Подякували: dot1

74

Re: Advent of Code

year2021/day20.rs
#[derive(Clone)]
struct Algo(Vec<u8>);

#[derive(Clone)]
struct Image(Vec<Vec<u8>>);

pub struct ImageData {
    algo: Algo,
    image: Image,
}

impl std::fmt::Debug for Image {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for line in self.0.iter() {
            for &ch in line {
                write!(f, "{}", if ch == 1 { '#' } else { '.' })?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

fn char_to_bit(c: char) -> u8 {
    match c {
        '#' => 1,
        '.' => 0,
        _ => panic!("Wrong char in input: {}", c),
    }
}

pub fn parse_input(input: &str) -> ImageData {
    let mut input = input.lines();
    let algo = Algo(input.next().unwrap().chars().map(char_to_bit).collect());
    let image = Image(
        input
            .skip(1)
            .map(|line| line.chars().map(char_to_bit).collect())
            .collect(),
    );
    ImageData { algo, image }
}

impl Image {
    fn enhance(&mut self, algo: &Algo, step: usize) {
        let height = self.0.len();
        let width = self.0[1].len();
        let outer = algo.get_outer_symbol(step);
        self.0 = (0..height + 2)
            .map(|y| {
                (0..width + 2)
                    .map(|x| {
                        algo.0
                            [self.get_binary(x as i32 - 1, y as i32 - 1, outer)]
                    })
                    .collect()
            })
            .collect();
    }

    fn get_binary(&self, x: i32, y: i32, outer: u8) -> usize {
        let mut binary = 0;
        for i in y - 1..y + 2 {
            for j in x - 1..x + 2 {
                let v = if 0 <= i
                    && i < self.0.len() as i32
                    && 0 <= j
                    && j < self.0[0].len() as i32
                {
                    self.0[i as usize][j as usize]
                } else {
                    outer
                };
                binary = (binary << 1) | v as usize;
            }
        }
        binary
    }

    fn lit_pixels(&self) -> usize {
        self.0
            .iter()
            .flat_map(|line| line.iter().map(|&bit| bit as usize))
            .sum()
    }
}

impl Algo {
    fn get_outer_symbol(&self, step: usize) -> u8 {
        if step == 0 || *self.0.first().unwrap() == 0 {
            0
        } else if *self.0.last().unwrap() == 1 {
            1
        } else {
            (step % 2) as u8
        }
    }
}

pub fn task(input: &ImageData, count: usize) -> usize {
    let mut image = input.image.clone();
    for i in 0..count {
        image.enhance(&input.algo, i);
    }
    image.lit_pixels()
}

pub fn task1(input: &ImageData) -> usize {
    task(input, 2)
}

pub fn task2(input: &ImageData) -> usize {
    task(input, 50)
}

#[cfg(test)]
mod test {
    use super::*;

    fn get_test_data() -> ImageData {
        let data = "..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#

#..#.
#....
##..#
..#..
..###";
        parse_input(&data)
    }

    #[test]
    fn test_get_binary() {
        let data = get_test_data();
        assert_eq!(data.image.get_binary(2, 2, 0), 34);
    }

    #[test]
    fn test_task1() {
        assert_eq!(task1(&get_test_data()), 35);
    }

    #[test]
    fn test_task2() {
        assert_eq!(task2(&get_test_data()), 3351);
    }
}

Щось зі складністю недороблене, друге завдання - тупо з параметром 50 замість 2.

Подякували: dot1

75

Re: Advent of Code

year2021/day21
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Player {
    position: usize,
    score: usize,
}

impl Player {
    fn new(position: usize) -> Player {
        Player { position, score: 0 }
    }
}

#[derive(Clone)]
pub struct Game {
    players: Vec<Player>,
    turn: usize,
    dice_value: usize,
    dice_rolled: usize,
}

pub fn parse_input(input: &str) -> Vec<usize> {
    input
        .lines()
        .map(|line| line.split(": ").skip(1).next().unwrap().parse().unwrap())
        .collect()
}

impl Game {
    const WIN_SCORE: usize = 1000;
    const BOARD_SIZE: usize = 10;
    const DICE_SIZE: usize = 100;

    fn new(player_pos: &Vec<usize>) -> Game {
        Game {
            players: player_pos.iter().map(|&pos| Player::new(pos)).collect(),
            turn: 0,
            dice_value: 1,
            dice_rolled: 0,
        }
    }
    fn step(&mut self) {
        let whos_turn = self.turn % self.players.len();
        self.players[whos_turn].position = (self.players[whos_turn].position
            + self.roll()
            + self.roll()
            + self.roll()
            - 1)
            % Game::BOARD_SIZE
            + 1;
        self.players[whos_turn].score += self.players[whos_turn].position;
        self.turn += 1;
    }
    fn roll(&mut self) -> usize {
        let roll = self.dice_value;
        self.dice_rolled += 1;
        self.dice_value = self.dice_value % Game::DICE_SIZE + 1;
        roll
    }
    fn ended(&self) -> bool {
        self.players
            .iter()
            .any(|player| player.score >= Game::WIN_SCORE)
    }
    fn less_score(&self) -> usize {
        self.players
            .iter()
            .map(|player| player.score)
            .min()
            .unwrap()
    }
}

pub fn task1(input: &Vec<usize>) -> usize {
    let mut game = Game::new(input);
    while !game.ended() {
        game.step();
    }
    game.less_score() * game.dice_rolled
}

#[derive(Clone, Debug)]
pub struct DiracGame {
    //universes: Vec<(Vec<Player>, u128)>,
    universes: std::collections::HashMap<Vec<Player>, u128>,
    wins: Vec<u128>,
    turn: usize,
}

impl DiracGame {
    //roll, number of universes
    const DIRAC_CUBE: [(usize, u128); 7] =
        [(3, 1), (4, 3), (5, 6), (6, 7), (7, 6), (8, 3), (9, 1)];
    const WIN_SCORE: usize = 21;
    const BOARD_SIZE: usize = 10;

    fn new(pos: &Vec<usize>) -> DiracGame {
        DiracGame {
            universes: [(
                pos.iter().map(|&position| Player::new(position)).collect(),
                1,
            )]
            .into(),

            wins: vec![0; pos.len()],
            turn: 0,
        }
    }
    fn ended(&self) -> bool {
        self.universes.is_empty()
    }

    fn step(&mut self) {
        let whos_turn = self.turn % self.wins.len();
        let mut universes = std::collections::HashMap::new();
        for (players, old_universes) in &self.universes {
            for (roll, roll_universes) in DiracGame::DIRAC_CUBE {
                let new_position = (players[whos_turn].position + roll - 1)
                    % DiracGame::BOARD_SIZE
                    + 1;
                let new_score = players[whos_turn].score + new_position;
                if new_score >= DiracGame::WIN_SCORE {
                    self.wins[whos_turn] += old_universes * roll_universes;
                } else {
                    let mut new_players = players.clone();
                    new_players[whos_turn].position = new_position;
                    new_players[whos_turn].score = new_score;
                    *universes.entry(new_players).or_insert(0) +=
                        old_universes * roll_universes;
                }
            }
        }
        self.universes = universes;
        self.turn += 1;
    }
}

pub fn task2(input: &Vec<usize>) -> u128 {
    let mut game = DiracGame::new(input);
    while !game.ended() {
        game.step();
    }
    *game.wins.iter().max().unwrap()
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let data = parse_input(
            &"Player 1 starting position: 4
Player 2 starting position: 8",
        );
        assert_eq!(task1(&data), 739785);
    }

    #[test]
    fn test_task2() {
        let data = parse_input(
            &"Player 1 starting position: 4
Player 2 starting position: 8",
        );
        assert_eq!(task2(&data), 444356092776315);
    }
}
Подякували: dot1

76

Re: Advent of Code

year2021/day25.rs - task1
#[derive(Clone, Copy, PartialEq)]
enum Cucumber {
    Right,
    Down,
    Empty,
}

impl From<char> for Cucumber {
    fn from(c: char) -> Cucumber {
        match c {
            '>' => Cucumber::Right,
            'v' => Cucumber::Down,
            '.' => Cucumber::Empty,
            _ => panic!(),
        }
    }
}

impl Cucumber {
    fn to_char(self) -> char {
        match self {
            Cucumber::Right => '>',
            Cucumber::Down => 'v',
            Cucumber::Empty => '.',
        }
    }
}

#[derive(Clone)]
pub struct Seafloor {
    cucumbers: Vec<Vec<Cucumber>>,
    turn: usize,
}

impl std::fmt::Debug for Seafloor {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "Turn = {}", self.turn)?;
        for line in &self.cucumbers {
            writeln!(
                f,
                "{}",
                line.iter().map(|c| c.to_char()).collect::<String>()
            )?;
        }

        Ok(())
    }
}

impl Seafloor {
    fn step(&mut self) -> bool {
        let height = self.cucumbers.len();
        let width = self.cucumbers[0].len();
        let mut changed = false;

        for cucumber_kind in [Cucumber::Right, Cucumber::Down] {
            let mut new_field = vec![vec![Cucumber::Empty; width]; height];
            for line_idx in 0..height {
                for col_idx in 0..width {
                    if self.cucumbers[line_idx][col_idx] == cucumber_kind {
                        let (line_tgt, col_tgt) =
                            self.target(cucumber_kind, line_idx, col_idx);
                        if self.cucumbers[line_tgt][col_tgt] == Cucumber::Empty
                        {
                            new_field[line_tgt][col_tgt] = cucumber_kind;
                            changed = true;
                        } else {
                            new_field[line_idx][col_idx] = cucumber_kind;
                        }
                    } else if self.cucumbers[line_idx][col_idx]
                        != Cucumber::Empty
                    {
                        new_field[line_idx][col_idx] =
                            self.cucumbers[line_idx][col_idx];
                    }
                }
            }
            self.cucumbers = new_field;
        }
        self.turn += 1;
        changed
    }

    fn target(
        &self,
        kind: Cucumber,
        line: usize,
        col: usize,
    ) -> (usize, usize) {
        match kind {
            Cucumber::Right => (line, (col + 1) % self.cucumbers[line].len()),
            Cucumber::Down => ((line + 1) % self.cucumbers.len(), col),
            _ => panic!(),
        }
    }
}

pub fn parse_input(input: &str) -> Seafloor {
    Seafloor {
        cucumbers: input
            .lines()
            .map(|line| line.chars().map(|c| c.into()).collect())
            .collect(),
        turn: 0,
    }
}

pub fn task1(seafloor: &Seafloor) -> usize {
    let mut seafloor = seafloor.clone();
    while seafloor.step() {
        //println!("{:?}", seafloor);
    }
    seafloor.turn
}

pub fn task2(_seafloor: &Seafloor) -> usize {
    0
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_task1() {
        let input = "v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>";
        let seafloor = parse_input(&input);
        assert_eq!(task1(&seafloor), 58);
    }
}
Подякували: dot1

77 Востаннє редагувалося koala (27.12.2021 23:48:19)

Re: Advent of Code

Так, тепер те, на чому я зламався. Ну добре, не зламався, просто недокрутив. Сподіваюся, що тут розпишу і зрозумію, як розв'язувати.
День 17. Стріляємо з точки (0,0) об'єктом із початковою швидкістю (vx,vy). Кожен крок симуляції vx та vy додаються до координат об'єкта, після чого зменшуються на 1 - vx до 0, vy іде в мінус нескінченість. Яка має бути початкова швидкість, щоб об'єкт піднявся на максимальну висоту, а потім на певному кроці опинився в прямокутній зоні (x1..x2)x(y1..y2)?
Для початку - горизонтальна координата. За vx кроків горизонтальна швидкість падає до 0, положення по x в момент t визначається як vx*t-t*(t-1)/2 до цього моменту і, очевидно, vx*(vx+1)/2 після. Якщо таке значення потрапляє в x1..x2 - беремо саме його, щоб не залежати від часу, інакше у нас лише кілька моментів, поки об'єкт в зоні, і поки не будемо про погане. У прикладі і моїх початкових даних x1 та x2 захоплюють потрібну точку, далі не думаємо.
Вертикальна координата. Тут y=vy*t-t*(t-1)/2 постійно; це - перевернута парабола з вершиною в vy+1/2, що досить логічно: в момент t=vy вертикальна швидкість падає до 0, і  в y(t=vy) та y(t=vy+1) буде однаковим. Висота у цей момент буде vy*vy-vy*(vy-1)/2 = vy*(vy+1)/2. Іншими словами, треба максимізувати vy серед прийнятних. А далі іде падіння, і в певний момент має настати y1<=vy*t-t*(t-1)/2<=y2. А от далі я щось гальмую. Треба знати максимальне vy, при якому t буде лишатися цілим. Перша нерівність (з y1) задає для t інтервал між коренями квадратного рівняння t∈ [t1_1;t1_2]; друге - виключає аналогічний інтервал: t ∉ (t2_1;t2_2). Із загальних міркувань це має дати інтервал t2_2<=t<=t1_2. Гм.
t^2-(2*vy+1)*t+2*y1 = 0
D = 4vy^2+4vy+1-8*y1
t1_2 = (2*vy+1+sqrt(4vy^2+4vy+1-8*y1))/2
Аналогічно,
t2_2 = (2*vy+1+sqrt(4vy^2+4vy+1-8*y2))/2
А тепер треба задати умову, щоб між цими двома значеннями має бути ціле число. І тут щось пішло не так. Хтось щось підкаже? Чи тупо перебором vy шукати? А як зупиняти? Де гарантія, що в районі 1000000 не буде такого значення, що воно туди потрапить?

Подякували: mamkin haker, dot2

78

Re: Advent of Code

Як і слід було очікувати, сам факт розписування відповіді надав мені потрібний поштовх (але чомусь коли я розписував це в коментарях, воно не спрацювало).

приховаю, може, хтось ще подумає

Координата за y, якщо дивитися з вершини параболи, утворює послідовність 1, 3, 6, 10 (трикутні числа) - спершу в зворотному порядку, потім у прямому. На кроці 2*vy+1 координата буде така сама, як і перед запуском. Відповідно, наступні кроки після перетину початкової горизонталі будуть послідовністю vy+1, vy+1 + vy+2 і т.д. Найбільше можливе vy у цих умовах - це 1-y2 (перший крок під нульову горизонталь потрапляє в y2). Навіть рахувати не треба.

Друга частина дещо цікавіша, але із цими формулами буде легко.

Подякували: dot, leofun012

79 Востаннє редагувалося koala (29.12.2021 11:45:00)

Re: Advent of Code

year2021/day17.rs
type Rect = ((i32, i32), (i32, i32));

pub fn parse_input(input: &str) -> Rect {
    let mut parts = input["target area: ".len()..].split(", ");
    let mut xs = parts.next().unwrap()["x=".len()..]
        .split("..")
        .map(|x| x.parse().unwrap());
    let mut ys = parts.next().unwrap()["x=".len()..]
        .split("..")
        .map(|x| x.parse().unwrap());
    (
        (xs.next().unwrap(), ys.next().unwrap()),
        (xs.next().unwrap(), ys.next().unwrap()),
    )
}

pub fn task1(input: &Rect) -> i32 {
    let &((x1, y1), (x2, _y2)) = input;
    //x1<=vx*(vx+1)/2<=x2
    //2*x1<=vx**2 + vx<=2*x2
    let vx = (((1 + 8 * x2) as f64).sqrt() as i32 - 1) / 2;
    assert!(vx * (vx + 1) / 2 >= x1, "Probe don't stop, vx={}", vx);
    let vy = (y1 + 1).abs();
    vy * (vy + 1) / 2
}

fn get_all_velocities(input: &Rect) -> std::collections::HashSet<(i32, i32)> {
    let &((x1, y1), (x2, y2)) = input;
    let max_t = 2 * y1.abs();

    let mut result = std::collections::HashSet::new();

    for t in 1..=max_t {
        let mut vx_min = (x1 + t * (t - 1) / 2 + t - 1) / t;
        if vx_min < t {
            vx_min = ((((1 + 8 * x1) as f64).sqrt() - 1.0) / 2.0).ceil() as i32;
        }
        let mut vx_max = (x2 + t * (t - 1) / 2) / t;
        if vx_max < t {
            vx_max = ((((1 + 8 * x2) as f64).sqrt() - 1.0) / 2.0) as i32;
        }
        let vy_min = ((y1 + t * (t - 1) / 2) as f64 / t as f64).ceil() as i32;
        let vy_max = ((y2 + t * (t - 1) / 2) as f64 / t as f64).floor() as i32;
        /*let r = std::cmp::max(0, vx_max - vx_min + 1) as usize
            * std::cmp::max(0, vy_max - vy_min + 1) as usize;
        println!(
            "t={}, vx={}..{}, vy={}..{}, total={}",
            t, vx_min, vx_max, vy_min, vy_max, r
        );*/
        for vx in vx_min..=vx_max {
            for vy in vy_min..=vy_max {
                result.insert((vx, vy));
            }
        }
    }
    result
}

pub fn task2(input: &Rect) -> usize {
    get_all_velocities(input).len()
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        assert_eq!(task1(&((20, -10), (30, -5))), 45);
    }

    #[test]
    fn test_task2() {
        assert_eq!(task2(&((20, -10), (30, -5))), 112);
    }

    use itertools::Itertools;

    #[test]
    fn test_get_all_velocities() {
        let expected_str = "23,-10  25,-9   27,-5   29,-6   22,-6   21,-7   9,0     27,-7   24,-5
25,-7   26,-6   25,-5   6,8     11,-2   20,-5   29,-10  6,3     28,-7
8,0     30,-6   29,-8   20,-10  6,7     6,4     6,1     14,-4   21,-6
26,-10  7,-1    7,7     8,-1    21,-9   6,2     20,-7   30,-10  14,-3
20,-8   13,-2   7,3     28,-8   29,-9   15,-3   22,-5   26,-8   25,-8
25,-6   15,-4   9,-2    15,-2   12,-2   28,-9   12,-3   24,-6   23,-7
25,-10  7,8     11,-3   26,-7   7,1     23,-9   6,0     22,-10  27,-6
8,1     22,-8   13,-4   7,6     28,-6   11,-4   12,-4   26,-9   7,4
24,-10  23,-8   30,-8   7,0     9,-1    10,-1   26,-5   22,-9   6,5
7,5     23,-6   28,-10  10,-2   11,-1   20,-9   14,-2   29,-7   13,-3
23,-5   24,-8   27,-9   30,-7   28,-5   21,-10  7,9     6,6     21,-5
27,-10  7,2     30,-9   21,-8   22,-7   24,-9   20,-6   6,9     29,-5
8,-2    27,-8   30,-5   24,-7";
        let expected = expected_str
            .split_whitespace()
            .map(|pair| {
                pair.split(',')
                    .map(|n| n.parse().unwrap())
                    .collect_tuple()
                    .unwrap()
            })
            .collect();
        let result = get_all_velocities(&((20, -10), (30, -5)));
        if result != expected {
            let extra: Vec<_> = result.difference(&expected).collect();
            if !extra.is_empty() {
                println!("Extra values: {:?}", extra);
            }
            let lost: Vec<_> = expected.difference(&result).collect();
            if !lost.is_empty() {
                println!("Lost values: {:?}", lost);
            }
            assert!(false);
        }
    }
}

Довелося трохи помучитися з округленням негативних значень. Ну і прогальмував, що деякі пари дають кілька потраплянь у зону, тому все ж таки потрібен HashSet.

Тепер день 19: є множини координат зондів в системах координат різних сканерів. Сканери завжди ведуть відлік від себе в (0,0,0) і можуть бути розвернути по всіх осях як завгодно по 90°, але бачать лише на певну відстань навколо. Скільки там зондів?
Планую шукати унікальні відстані між зондами (для простоти - квадрати відстаней) і суміщати по них.

80 Востаннє редагувалося koala (05.01.2022 09:42:11)

Re: Advent of Code

Щось за день 19 ніяк не візьмуся. Поки зробив

year2021/day22.rs
#[derive(Clone)]
pub enum State {
    On,
    Off,
}

#[derive(PartialEq, Clone)]
pub struct Zone {
    limits: [std::ops::RangeInclusive<i32>; 3],
}

enum Intersection {
    Intersects(usize),
    Equals,
    None,
}

impl Zone {
    fn intersects(&self, other: &Zone) -> Intersection {
        if self.limits == other.limits {
            return Intersection::Equals;
        }
        for coordinate in 0..3 {
            if self.limits[coordinate].start() > other.limits[coordinate].end()
                || self.limits[coordinate].end()
                    < other.limits[coordinate].start()
            {
                return Intersection::None;
            }
        }
        for coordinate in 0..3 {
            if self.limits[coordinate].start()
                != other.limits[coordinate].start()
                || self.limits[coordinate].end()
                    != other.limits[coordinate].end()
            {
                return Intersection::Intersects(coordinate);
            }
        }

        unreachable!("Zone::intersects fails");
    }
}

#[derive(Clone)]
pub struct Command {
    state: State,
    zone: Zone,
}

impl Command {
    fn new(input: &str) -> Command {
        lazy_static::lazy_static! {
            //on x=-20..26,y=-36..17,z=-47..7
            static ref INPUT_REGEX: regex::Regex = regex::Regex::new(r"(on|off) x=(-?[\d]+)..(-?[\d]+),y=(-?[\d]+)..(-?[\d]+),z=(-?[\d]+)..(-?[\d]+)").unwrap();
        }
        let captures = INPUT_REGEX.captures(input).unwrap();
        let mut iter = captures.iter().skip(1);
        let mut result = Command {
            state: if iter.next().unwrap().unwrap().as_str() == "on" {
                State::On
            } else {
                State::Off
            },
            zone: Zone {
                limits: [0..=0, 0..=0, 0..=0],
            },
        };
        for coordinate in 0..3 {
            result.zone.limits[coordinate] =
                iter.next().unwrap().unwrap().as_str().parse().unwrap()
                    ..=iter.next().unwrap().unwrap().as_str().parse().unwrap();
        }
        result
    }
}

struct Reactor {
    cubes: Vec<Zone>,
}

impl Reactor {
    fn new() -> Reactor {
        Reactor { cubes: Vec::new() }
    }

    fn add(&mut self, command: &Command) {
        let mut idx = 0;
        while idx < self.cubes.len() {
            match self.cubes[idx].intersects(&command.zone) {
                Intersection::Equals => {
                    if let State::Off = command.state {
                        self.cubes.remove(idx);
                    }
                    return;
                }
                Intersection::Intersects(coordinate) => {
                    match self.cubes[idx].limits[coordinate]
                        .start()
                        .cmp(&command.zone.limits[coordinate].start())
                    {
                        std::cmp::Ordering::Less => {
                            let removed = self.cubes.remove(idx).clone();
                            let mut left = removed.clone();
                            left.limits[coordinate] = *removed.limits
                                [coordinate]
                                .start()
                                ..=*command.zone.limits[coordinate].start() - 1;
                            let mut right = removed;
                            right.limits[coordinate] =
                                *command.zone.limits[coordinate].start()
                                    ..=*right.limits[coordinate].end();
                            self.cubes.push(left);
                            self.cubes.push(right);
                        }
                        std::cmp::Ordering::Greater => {
                            let mut left = command.clone();
                            left.zone.limits[coordinate] = *command.zone.limits
                                [coordinate]
                                .start()
                                ..=*self.cubes[idx].limits[coordinate].start()
                                    - 1;
                            let mut right = command.clone();
                            right.zone.limits[coordinate] =
                                *self.cubes[idx].limits[coordinate].start()
                                    ..=*command.zone.limits[coordinate].end();
                            self.add(&left);
                            self.add(&right);
                            return;
                        }
                        std::cmp::Ordering::Equal => {
                            match self.cubes[idx].limits[coordinate]
                                .end()
                                .cmp(&command.zone.limits[coordinate].end())
                            {
                                std::cmp::Ordering::Greater => {
                                    let removed = self.cubes.remove(idx);
                                    let mut left = removed.clone();
                                    left.limits[coordinate] =
                                        *removed.limits[coordinate].start()
                                            ..=*command.zone.limits[coordinate]
                                                .end();
                                    let mut right = removed.clone();
                                    right.limits[coordinate] =
                                        *command.zone.limits[coordinate].end()
                                            + 1
                                            ..=*removed.limits[coordinate]
                                                .end();
                                    self.cubes.push(right);
                                    self.cubes.push(left);
                                }
                                std::cmp::Ordering::Less => {
                                    let mut left = command.clone();
                                    left.zone.limits[coordinate] = *command
                                        .zone
                                        .limits[coordinate]
                                        .start()
                                        ..=*self.cubes[idx].limits[coordinate]
                                            .end();
                                    let mut right = command.clone();
                                    right.zone.limits[coordinate] =
                                        *self.cubes[idx].limits[coordinate]
                                            .end()
                                            + 1
                                            ..=*command.zone.limits[coordinate]
                                                .end();
                                    self.add(&left);
                                    self.add(&right);
                                    return;
                                }
                                _ => unreachable!(
                                    "Both ranges shoun't be equal!"
                                ),
                            }
                        }
                    }
                }
                _ => idx += 1,
            }
        }
        if let State::On = command.state {
            self.cubes.push(command.zone.clone());
        }
    }

    fn count(&self) -> usize {
        self.cubes
            .iter()
            .map(|zone| {
                zone.limits
                    .iter()
                    .map(|range| (range.end() - range.start() + 1) as usize)
                    .product::<usize>()
            })
            .sum()
    }
}

pub fn parse_input(input: &str) -> Vec<Command> {
    input.lines().map(|line| Command::new(line)).collect()
}

pub fn task1(commands: &Vec<Command>) -> usize {
    let mut reactor = Reactor::new();
    for command in commands {
        if command
            .zone
            .limits
            .iter()
            .all(|range| *range.start() <= 50 && *range.end() >= -50)
        {
            reactor.add(command);
        }
    }
    reactor.count()
}

pub fn task2(commands: &Vec<Command>) -> usize {
    let mut reactor = Reactor::new();
    for command in commands {
        reactor.add(command);
    }
    reactor.count()
}

Щось я перемудрив і недооптимізував (треба вектор на якесь дерево замінити, чи що), але в будь-якому разі воно виконується в релізній версії за 1.7 секунди. В дебажній досі чекаю :)

Подякували: dot1