101 Востаннє редагувалося koala (06.12.2022 07:54:35)

Re: Advent of Code

Умова: знайти в стрічці першу підстрічку з n різних символів. Повернути номер символу після закінчення цієї підстрічки:
1. n=4
2. n=14

2022#6, Rust
pub fn parse_input(input: &str) -> &str {
    input
}

use std::collections::HashSet;

fn first_different(input: &str, length: usize) -> usize {
    for i in 0..input.len() - length {
        let set: HashSet<_> = input[i..i + length].chars().collect();
        if set.len() == length {
            return i + length;
        }
    }
    unreachable!()
}

pub fn task1(input: &str) -> usize {
    first_different(input, 4)
}

pub fn task2(input: &str) -> usize {
    first_different(input, 14)
}
Подякували: dot1

102

Re: Advent of Code

2022#6, Python
buffer = open("input.txt").read()


def device(length: int):
    for i in range(len(buffer) - length + 1):
        if len(set(buffer[i : i + length])) == length:
            return length + i


print(device(4))  # Part One: 1625
print(device(14))  # Part Two: 2250

103 Востаннє редагувалося koala (07.12.2022 10:35:56)

Re: Advent of Code

Умова: є команди оболонки (обрізані cd і ls), якими пройшлися по всій файловій системі. Треба:
1. Знайти суму місця, займану теками, меншими за 100_000 (з урахуванням підтек);
2. Знайти розмір найменшої теки, видалення якої звільнить 30_000_000 із загального простору в 70_000_000.

2022#7, Rust
pub enum FsRecord {
    File(usize),
    Dir(Box<Directory>),
}

use std::collections::HashMap;

pub struct Directory {
    records: HashMap<String, FsRecord>,
}

impl Directory {
    fn new() -> Directory {
        Directory {
            records: HashMap::new(),
        }
    }
    fn add_file(&mut self, path: &[String], size: usize) {
        if path.len() == 1 {
            self.records
                .insert(path[0].to_string(), FsRecord::File(size));
        } else if let Some(FsRecord::Dir(dir)) = self.records.get_mut(&path[0])
        {
            dir.add_file(&path[1..], size);
        }
    }
    fn add_dir(&mut self, path: &[String]) {
        if path.len() == 1 {
            self.records
                .entry(path[0].to_string())
                .or_insert_with(|| FsRecord::Dir(Box::new(Directory::new())));
        } else if let Some(FsRecord::Dir(dir)) = self.records.get_mut(&path[0])
        {
            dir.add_dir(&path[1..]);
        }
    }
    fn get_sizes<P>(&self, func: P) -> (usize, usize)
    where
        P: Fn(usize) -> usize + Clone,
    {
        let mut inner_size = 0;
        let mut inner_filtered = 0;
        for record in self.records.values() {
            match record {
                &FsRecord::File(size) => inner_size += size,
                FsRecord::Dir(subdir) => {
                    let (total, filtered) = subdir.get_sizes(func.clone());
                    inner_size += total;
                    inner_filtered += filtered;
                }
            }
        }
        inner_filtered += func(inner_size);
        (inner_size, inner_filtered)
    }
    fn get_best_size(&self, target: usize) -> (usize, usize) {
        let mut inner_size = 0;
        let mut best = 0;
        for record in self.records.values() {
            match record {
                &FsRecord::File(size) => inner_size += size,
                FsRecord::Dir(subdir) => {
                    let (total, current_best) = subdir.get_best_size(target);
                    inner_size += total;
                    if current_best > target
                        && (best == 0 || current_best < best)
                    {
                        best = current_best;
                    }
                }
            }
        }
        if best == 0 || (inner_size > target && inner_size < best) {
            best = inner_size;
        }
        (inner_size, best)
    }
}

pub fn parse_input(input: &str) -> Directory {
    let mut root = Directory::new();
    let mut path = vec![];
    for instruction in input.lines() {
        if instruction.starts_with("$ cd") {
            match &instruction[5..] {
                "/" => {
                    path.clear();
                }
                ".." => {
                    path.pop();
                }
                name => {
                    path.push(name.to_string());
                    root.add_dir(&path);
                }
            }
        } else if instruction != "$ ls" {
            //executing ls
            let mut instruction = instruction.split_whitespace();
            let typ = instruction.next().unwrap();
            let name = instruction.next().unwrap();
            path.push(name.to_string());
            if typ == "dir" {
                root.add_dir(&path);
            } else {
                root.add_file(&path, typ.parse().unwrap());
            }
            path.pop();
        }
    }
    root
}

pub fn task1(root: &Directory) -> usize {
    root.get_sizes(|size| if size <= 100_000 { size } else { 0 })
        .1
}

pub fn task2(root: &Directory) -> usize {
    let current_size = root.get_sizes(|_| 0).0;
    let unused = 70_000_000 - current_size;
    let needed = 30_000_000 - unused;
    root.get_best_size(needed).1
}

Ще одна штука, яку Rust ненавидить. З тієї ж причини, що й 2022#5. Рекурсію при побудові дуже складно робити, доводиться всі операції з рута починати і повний шлях проходити.
Хоча зараз подумав, що може не все так погано - треба мувати значення з дерева, модифікувати і класти на місце. Можливо. У мене щось голова зовсім не варить, я кілька хвилин не міг правильно вільне місце обчислити, доки не розбив на дві операції:

    let unused = 70_000_000 - current_size;
    let needed = 30_000_000 - unused;

Правда, вчора я добив 2019#10 з арктангенсами, підозрюю, що це саме через нього.

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

104 Востаннє редагувалося dot (07.12.2022 15:04:33)

Re: Advent of Code

2022#7, Python
import collections, copy


def tree():
    return collections.defaultdict(tree)


filesystem = tree()
path = list()
dirs = set()


def add(keys, value=None, t=filesystem):
    for i, key in enumerate(keys):
        if i == len(keys) - 1 and value:
            continue
        t = t[key]

    if value:
        t[key] = value


def dirSize(keys):
    t = copy.deepcopy(filesystem)
    total = int()

    for k in keys:
        t = t[k]

    for k in t.keys():
        total += t[k] if type(t[k]) == int else dirSize(keys + tuple([k]))

    return total


for line in open("input.txt").read().splitlines():
    match line.split():
        case ["$", "cd", dir]:
            match dir:
                case "..":
                    path.pop()
                case "/":
                    path = ["/"]
                case _:
                    path.append(dir)
                    dirs.add(tuple(path))
                    add(path)
        case ["$", "ls"]:
            pass
        case ["dir", dir]:
            add(path + [dir])
            dirs.add(tuple(path + [dir]))
            pass
        case [size, file]:
            add(path + [file], int(size))


limit: int = 100_000
total_space: int = 70_000_000
need_space: int = 30_000_000
total = int()
for_delete = list()

need_space -= total_space - dirSize(tuple("/"))

for dir in dirs:
    size = dirSize(dir)
    if size < limit:
        total += size
    if size > need_space:
        for_delete.append(size)

print(total)  # Part One: 1325919
print(min(for_delete))  # Part Two: 2050735

Kod povne mêsyvo, treba bude pôdpravyty jakosj.

105 Востаннє редагувалося dot (07.12.2022 15:40:09)

Re: Advent of Code

Kek, moźna bulo bez dereva i rekurcij. I ce ± oćevydno. Tobto nabyrajemo strôćky (abo śćosj take, ale tut najlehśe) i sumujemo vsji strôćky, kotri poćynajutj sja z…

Śće smêśnêśe, śćosj take krutylo sja na jazycê, ale ti rankovi vymyky elektriky — cjoho razu hetj nezvyćni: vkljućaly na 20 xv desj v 2~4 hodyny — mene teź rozumovo dokonaly. Na śćastje, moźlyvo ćerez uspêx perśojê, druha ćastyna bula duźe lehkoju dlja mene, odrazu zdohadav sja pro ce rôvnjannje. I aby bulo śće smêśnêśe, bulo ± podôbna zadaća desj v mynulyx rokax, bo śćosj take pryhaduju i mav same take rêśennje.

Prykald vôd odnoho majstera.

2022#07, Python
    dirsizes = {}
    cwd = '/'
    for line in sys.stdin:
        if m := re.match(r'^\$ cd \.\.$', line):
            cwd, _ = os.path.split(cwd)
        elif m := re.match(r'^\$ cd (\S+)$', line):
            cwd = os.path.join(cwd, m.group(1))
            dirsizes[cwd] = 0
        elif m := re.match(r'^([0-9]+) (\S+)$', line):
            size = int(m.group(1))
            for d in filter(cwd.startswith, dirsizes):
                dirsizes[d] += size

    print(sum(v for v in dirsizes.values() if v <= SIZE_BOUND))
    size_to_delete = SIZE_NEED - (SIZE_DISK - dirsizes['/'])
    print(min(v for v in dirsizes.values() if v >= size_to_delete))

106 Востаннє редагувалося dot (09.12.2022 07:05:42)

Re: Advent of Code

Ne mav elektriky majźe vesj denj abo mav spravy ćy todi ne bulo interneta. Ale ja vstyh zrobyty ce za denj (tak, znaju, śćo pośću vźe pôslja 24, ale ja vźe zapostyv desj v meźax 24). Z sumnoho, zrobleno jak dvê okremi zadaćy. Moźe zhodom sprobuju skombinyty.

2022#8, Python
grid = [[int(x) for x in y.strip()] for y in open("test.txt").readlines()]
onview = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]


def measure(m):
    return len(m[0]), len(m)


def rotate(m):
    row, col = measure(m)

    for i in range(row // 2):
        m[i], m[col - i - 1] = m[col - i - 1], m[i]

    for i in range(row):
        for j in range(i):
            m[i][j], m[j][i] = m[j][i], m[i][j]

    return m


for side in range(4):
    i, j = measure(grid)

    for y in range(i):
        tallest = grid[y][0]
        onview[y][0] = 1

        for x in range(j):
            if grid[y][x] > tallest:
                tallest = grid[y][x]
                onview[y][x] = 1
            elif grid[y][x] == 9:
                break
            else:
                continue
    if side == 4:
        break
    grid = rotate(grid)
    onview = rotate(onview)

print(sum(map(sum, onview)))  # Part One: 1543
grid = [[int(x) for x in y.strip()] for y in open("input.txt").readlines()]
hor, ver = len(grid[0]), len(grid)
scenes = [[1 for _ in range(hor)] for _ in range(ver)]


def view(opt: int, length: int, route: int = 1) -> int:
    tallest: int = grid[y][x]
    trees: int = 0
    m = list(zip(*grid) if opt else grid)
    i, j = (x, y) if opt else (y, x)

    for step in range(1, length):
        trees += 1

        if tallest <= m[i][j + step * route]:
            break

    return trees


for y in range(hor):
    for x in range(ver):
        for opts in [(0, ver - x), (0, x + 1, -1), (1, hor - y), (1, y + 1, -1)]:
            scenes[y][x] *= view(*opts)

print(max(map(max, scenes)))  # Part Two: 595080

107

Re: Advent of Code

Умова: є матриця висот дерев у лісі (посадці рівними рядками і стовпчиками).
1. Дерево вважається видимим, якщо вгору, вниз, праворуч чи ліворуч від нього всі нижчі. Знайти кількість дерев, невидимих іззовні лісу.
2. Для кожного дерева вводиться оцінка - добуток відстаней, на які можна подивитися з нього, до найближчого не нижчого дерева чи краю лісу. Знайти дерево з максимальною оцінкою.

2022#8, Rust
pub fn parse_input(input: &str) -> Vec<Vec<i32>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| c.to_digit(10).unwrap() as i32)
                .collect()
        })
        .collect()
}

pub fn task1(trees: &[Vec<i32>]) -> usize {
    let mut count = 0;
    for (y, row) in trees.iter().enumerate() {
        for (x, &h) in row.iter().enumerate() {
            if row[..x].iter().all(|&tree| tree < h)
                || row[x + 1..].iter().all(|&tree| tree < h)
                || trees[..y].iter().all(|row| row[x] < h)
                || trees[y + 1..].iter().all(|row| row[x] < h)
            {
                count += 1;
            }
        }
    }
    count
}

pub fn task2(trees: &[Vec<i32>]) -> usize {
    let mut best = 0;

    for (y, row) in trees.iter().enumerate() {
        for (x, &h) in row.iter().enumerate() {
            let mut score = 1;

            let mut count = 0;
            let mut max = 0;
            for &tree in row[..x].iter().rev() {
                count += 1;
                if tree > max {
                    max = tree;
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for &tree in &row[x + 1..] {
                count += 1;
                if tree > max {
                    max = tree;
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for r in trees[..y].iter().rev() {
                count += 1;
                if r[x] > max {
                    max = r[x];
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for r in trees[y + 1..].iter() {
                count += 1;
                if r[x] > max {
                    max = r[x];
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            best = std::cmp::max(best, score);
        }
    }
    best
}

Щось у другому з ітераторами перемутив, ну і біс із ним.

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

108 Востаннє редагувалося koala (09.12.2022 08:53:32)

Re: Advent of Code

Умова: є мотузка з сегментів на дискретній площині. Коли тягнуть голову мотузки на 1 клітинку, кожен наступний сегмент, що відірвався від попереднього, робить 1 крок по діагоналі, горизонталі чи вертикалі у його бік (пріоритет у діагоналі). Для заданого маршруту знайти кількість точок, відвіданих хвостом, якщо довжина мотузки: 1. 2 сегменти; 2. 10 сегментів.

2022#9, Rust
pub fn parse_input(input: &str) -> Vec<(char, usize)> {
    input
        .lines()
        .map(|l| (l.chars().next().unwrap(), l[2..].parse().unwrap()))
        .collect()
}

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Rope(i32, i32);

impl Rope {
    fn pull(&mut self, dir: char) {
        match dir {
            'L' => self.0 -= 1,
            'R' => self.0 += 1,
            'U' => self.1 += 1,
            'D' => self.1 -= 1,
            _ => unimplemented!(),
        }
    }
    fn step(&mut self, after: Rope) {
        if (self.0 - after.0).abs() > 1 || (self.1 - after.1).abs() > 1 {
            self.0 += num::signum(after.0 - self.0);
            self.1 += num::signum(after.1 - self.1);
        }
    }
}
use std::collections::HashSet;

fn run_rope(path: &[(char, usize)], len: usize) -> usize {
    let mut visited = HashSet::new();
    let mut rope = vec![Rope(0, 0); len];
    for &(dir, num) in path {
        for _ in 0..num {
            rope[0].pull(dir);
            for i in 1..len {
                let after = rope[i - 1];
                rope[i].step(after);
            }
            visited.insert(rope[len - 1]);
        }
    }
    visited.len()
}

pub fn task1(path: &[(char, usize)]) -> usize {
    run_rope(path, 2)
}

pub fn task2(path: &[(char, usize)]) -> usize {
    run_rope(path, 10)
}

Більше б таких задач :)

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

109

Re: Advent of Code

Perśu ćastynu ustyh zrobyty vrancê do vymyku. Druhu dorobyv śćojno.

2022#09
motions = open("input.txt").read().split("\n")
routes = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}


def touching(knots, i):
    if not knots[i]:
        return (0, 0)

    px, py = knots[i - 1]
    mx, my = knots[i]
    kx, ky = knots[i]

    for x in (mx - 1, mx, mx + 1):
        for y in (my - 1, my, my + 1):
            if x == px and y == py:
                return knots[i]

    if kx == px:
        ky += 1 if py - ky > 0 else -1

    if ky == py:
        kx += 1 if px - kx > 0 else -1

    if kx == mx and ky == my:
        kx += 1 if px - kx > 0 else -1
        ky += 1 if py - ky > 0 else -1

    return (kx, ky)


def simulation(knots: int = 1) -> int:
    knots = [(0, 0)] + [None for _ in range(knots)]
    history = set()

    for motion in motions:
        route, steps = motion.split(" ")

        for _ in range(int(steps)):
            knots[0] = list(map(lambda a, b: a + b, knots[0], routes[route]))

            for i in range(1, len(knots), 1):
                knots[i] = touching(knots, i)

            history.add(knots[-1])

    return len(history)


print(simulation())  # Part One: 6470
print(simulation(9))  # Part Two: 2658

110 Востаннє редагувалося dot (09.12.2022 14:45:59)

Re: Advent of Code

koala написав:

Умова: є мотузка з сегментів на дискретній площині. Коли тягнуть голову мотузки на 1 клітинку, кожен наступний сегмент, що відірвався від попереднього, робить 1 крок по діагоналі, горизонталі чи вертикалі у його бік (пріоритет у діагоналі). Для заданого маршруту знайти кількість точок, відвіданих хвостом, якщо довжина мотузки: 1. 2 сегменти; 2. 10 сегментів.

2022#9, Rust
pub fn parse_input(input: &str) -> Vec<(char, usize)> {
    input
        .lines()
        .map(|l| (l.chars().next().unwrap(), l[2..].parse().unwrap()))
        .collect()
}

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Rope(i32, i32);

impl Rope {
    fn pull(&mut self, dir: char) {
        match dir {
            'L' => self.0 -= 1,
            'R' => self.0 += 1,
            'U' => self.1 += 1,
            'D' => self.1 -= 1,
            _ => unimplemented!(),
        }
    }
    fn step(&mut self, after: Rope) {
        if (self.0 - after.0).abs() > 1 || (self.1 - after.1).abs() > 1 {
            self.0 += num::signum(after.0 - self.0);
            self.1 += num::signum(after.1 - self.1);
        }
    }
}
use std::collections::HashSet;

fn run_rope(path: &[(char, usize)], len: usize) -> usize {
    let mut visited = HashSet::new();
    let mut rope = vec![Rope(0, 0); len];
    for &(dir, num) in path {
        for _ in 0..num {
            rope[0].pull(dir);
            for i in 1..len {
                let after = rope[i - 1];
                rope[i].step(after);
            }
            visited.insert(rope[len - 1]);
        }
    }
    visited.len()
}

pub fn task1(path: &[(char, usize)]) -> usize {
    run_rope(path, 2)
}

pub fn task2(path: &[(char, usize)]) -> usize {
    run_rope(path, 10)
}

Більше б таких задач :)

Ehe, zadaćka pryjmna. Tam mytj, koly Rast rôvnyj abo koroće za Pajton. Baću, moźna dobrjaće pokraśćyty moju funkciju touching, ale poky lênjky. Dorećy, vêtaju zô vzjattjem — sota povêdoma.

111

Re: Advent of Code

Тим часом він одне завдання зафейлив і відстав на кілька днів.

112 Востаннє редагувалося koala (12.12.2022 09:39:49)

Re: Advent of Code

Я повернувся (і до AoC теж).
Умова: є комп'ютер з двома командами (noop і addx) і одним регістром x. noop виконується 1 такт, addx - 2 такти. Такти нумеруються з 1, початкове значення x=1.
1. Знайти суму #такта * x в моменти #такта =20+40n.
2. Є екран 6x40. По рядках пробігає спрайт (позиції 0..39 включно) синхронно з комп'ютером. Якщо під час такту t спрайт знаходиться в межах x-1..x+1 - на екрані у відповідному місці #, якщо ні - . Прочитати літери з екрана.

2022#10, Rust
pub fn parse_input(input: &str) -> Vec<Option<i32>> {
    input
        .lines()
        .map(|line| {
            line.split_whitespace()
                .skip(1)
                .next()
                .map(|v| v.parse().unwrap())
        })
        .collect()
}

struct Computer<'code> {
    code: &'code [Option<i32>],
    x: i32,
    ip: usize,
    wait: bool,
}

impl<'code> Computer<'code> {
    fn new(code: &'code [Option<i32>]) -> Computer<'code> {
        Computer {
            code, //code.iter().copied().collect(),
            x: 1,
            ip: 0,
            wait: false,
        }
    }
    fn clock(&mut self) {
        if self.wait {
            self.wait = false;
            self.x += self.code[self.ip].unwrap();
            self.ip += 1;
        } else {
            match self.code[self.ip] {
                Some(_) => self.wait = true,
                None => self.ip += 1,
            }
        }
    }
}

pub fn task1(input: &[Option<i32>]) -> i32 {
    let mut computer = Computer::new(input);
    (1..240)
        .filter_map(|cycle| {
            let r = if cycle % 40 == 20 {
                Some(cycle * computer.x)
            } else {
                None
            };
            computer.clock();
            r
        })
        .sum()
}

use itertools::Itertools;

pub fn task2(input: &[Option<i32>]) -> String {
    let mut computer = Computer::new(input);
    (0..6)
        .map(|_row| {
            (0..40)
                .map(|pixel| {
                    let lit = (computer.x - pixel).abs() <= 1;
                    computer.clock();
                    if lit {
                        '#'
                    } else {
                        ' '
                    }
                })
                .collect::<String>()
        })
        .join("\n")
}
Подякували: dot1

113

Re: Advent of Code

Умова: мавпи вкрали речі і граються ними. Кожній речі присвоєний рівень хвилювання (за цю річ). У кожної мавпи є: номер, список речей, формула перетворення рівня хвилювання (new=old+n,new=old*n чи new=old*old), формула перевірки (чи ділиться рівень хвилювання на число t) і номери мавп, яким річ перекидається залежно від формули перевірки.
Кожна послідовно взята за номером мавпа бере речі по одній, оглядає (при цьому рівень хвилювання зростає за формулою) і кидає іншій, поки в останньої не закінчаться речі. Знайти добуток двох найбільших кількостей оглядів у мавп.
1. Змоделювати 20 циклів перекидання, рівень хвилювання після застосування формули перетворення ділити націло на 3.
2. Змоделювати 10_000 циклів перекидання, рівень хвилювання не ділити.

2022#11, Rust
#[derive(Clone)]
pub enum Operation {
    Add(usize),
    Mult(usize),
    Square,
}

impl Operation {
    fn apply(&self, item: usize) -> usize {
        match self {
            Operation::Add(x) => item + x,
            Operation::Mult(x) => item * x,
            Operation::Square => item * item,
        }
    }
}

#[derive(Clone)]
pub struct Monkey {
    items: std::collections::VecDeque<usize>,
    operation: Operation,
    test: usize,
    if_true: usize,
    if_false: usize,
    inspected: usize,
}

pub fn parse_input(input: &str) -> Vec<Monkey> {
    let mut monkeys = vec![];
    let mut input = input.lines();
    loop {
        input.next();
        let items = input
            .next()
            .unwrap()
            .split(": ")
            .nth(1)
            .unwrap()
            .split(", ")
            .map(|item| item.parse().unwrap())
            .collect();

        let operator: String;
        let operand: String;
        text_io::scan!(
            input.next().unwrap().bytes() =>
            "  Operation: new = old {} {}",
            operator,
            operand
        );
        let operation = if operator == "+" {
            Operation::Add(operand.parse().unwrap())
        } else if operand == "old" {
            Operation::Square
        } else {
            Operation::Mult(operand.parse().unwrap())
        };

        let test;
        text_io::scan!(input.next().unwrap().bytes() => "  Test: divisible by {}", test);

        let if_true;
        text_io::scan!(input.next().unwrap().bytes() => "    If true: throw to monkey {}", if_true);

        let if_false;
        text_io::scan!(
            input.next().unwrap().bytes() =>
            "    If false: throw to monkey {}",
            if_false
        );

        monkeys.push(Monkey {
            items,
            operation,
            test,
            if_true,
            if_false,
            inspected: 0,
        });

        if input.next().is_none() {
            break;
        }
    }
    monkeys
}

fn simulate(monkeys: &[Monkey], time: usize, div3: bool) -> usize {
    let mut monkeys = monkeys.to_owned();
    let common: usize = monkeys.iter().map(|m| m.test).product();
    for _round in 0..time {
        for i in 0..monkeys.len() {
            while let Some(item) = monkeys[i].items.pop_front() {
                let item = if div3 {
                    monkeys[i].operation.apply(item) / 3
                } else {
                    monkeys[i].operation.apply(item) % common
                };
                monkeys[i].inspected += 1;
                let target = if item % monkeys[i].test == 0 {
                    monkeys[i].if_true
                } else {
                    monkeys[i].if_false
                };
                monkeys[target].items.push_back(item);
            }
        }
    }
    let mut inspected: Vec<_> = monkeys.iter().map(|m| m.inspected).collect();
    inspected.sort();
    inspected[inspected.len() - 1] * inspected[inspected.len() - 2]
}

pub fn task1(monkeys: &[Monkey]) -> usize {
    simulate(monkeys, 20, true)
}

pub fn task2(monkeys: &[Monkey]) -> usize {
    simulate(monkeys, 10000, false)
}
Подякували: dot1

114

Re: Advent of Code

Умова: є прямокутна мапа висот з малих літер від a до z. На ній також позначені початок маршруту (S) і кінець (E). Висота S=a, E=z. Переходити на сусідню клітку можна лише якщо її висота не більша за поточну +1 (тобто з k можна перейти на l чи a, але не на n). Треба знайти:
1. Довжину найкоротшого шляху з S до E.
2. Найкоротшу довжину можливого шляху з будь-якого a до E.

2022#12, Rust
pub fn parse_input(input: &str) -> Vec<Vec<u8>> {
    input.lines().map(|line| line.bytes().collect()).collect()
}

fn value(f: u8) -> u8 {
    if f == b'S' {
        b'a'
    } else if f == b'E' {
        b'z'
    } else {
        f
    }
}

fn can_move(
    map: &[Vec<u8>],
    path: &[Vec<usize>],
    field: (i32, i32),
    neighbor: (i32, i32),
) -> bool {
    if neighbor.0 < 0
        || neighbor.0 >= map.len().try_into().unwrap()
        || neighbor.1 < 0
        || neighbor.1 >= map[0].len().try_into().unwrap()
        || path[neighbor.0 as usize][neighbor.1 as usize] != 0
    {
        false
    } else {
        let field = value(map[field.0 as usize][field.1 as usize]);
        let neighbor = value(map[neighbor.0 as usize][neighbor.1 as usize]);
        neighbor <= field + 1
    }
}

fn shortest_way(start: (i32, i32), map: &[Vec<u8>]) -> Option<usize> {
    let mut path = vec![vec![0; map[0].len()]; map.len()];
    let mut to_check = vec![start];
    for step in 1.. {
        let mut new_check = vec![];
        for field in to_check {
            for shift in &[(1i32, 0i32), (0, 1), (-1, 0), (0, -1)] {
                let neighbor = (field.0 + shift.0, field.1 + shift.1);
                if can_move(&map, &path, field, neighbor) {
                    if map[neighbor.0 as usize][neighbor.1 as usize] == b'E' {
                        return Some(step);
                    }
                    path[neighbor.0 as usize][neighbor.1 as usize] = step;
                    new_check.push(neighbor);
                }
            }
        }
        if new_check.is_empty() {
            return None;
        }
        to_check = new_check;
    }
    unreachable!()
}

pub fn task1(map: &[Vec<u8>]) -> usize {
    let start = map
        .iter()
        .enumerate()
        .filter_map(|(i, line)| {
            line.iter()
                .position(|&symbol| symbol == b'S')
                .map(|j| (i as i32, j as i32))
        })
        .next()
        .unwrap();
    shortest_way(start, map).unwrap()
}

pub fn task2(map: &[Vec<u8>]) -> usize {
    map.iter()
        .enumerate()
        .map(|(i, line)| {
            line.iter()
                .enumerate()
                .filter_map(|(j, &symbol)| {
                    if symbol == b'S' || symbol == b'a' {
                        shortest_way((i as i32, j as i32), map)
                    } else {
                        None
                    }
                })
                .min()
        })
        .min()
        .unwrap()
        .unwrap()
}

115

Re: Advent of Code

Є потік пар "пакетів" - вкладених масивів чисел (на кшталт "[[1],[2,3,4]]"). Пакети порівнюються послідовно таким чином:
- якщо мають різні числа - за величиною чисел;
- якщо число порівнюється з масивом, то число "загортається" в масив перед порівнянням;
- якщо масиви мають різну довжину і всі однакові елементи перед тим - то порівнюються довжини.
1. Знайти суму індексів (від 1) неправильно впорядкованих пар
2. Додати до пакетів ще два ([[2]] і [[6]]), відсортувати усі пакети і знайти добуток індексів (від 1) цих двох доданих пакетів.

2022#13, Rust
use serde_json::Value;

pub fn parse_input(input: &str) -> Vec<Value> {
    input
        .lines()
        .filter_map(|line| {
            if line.is_empty() {
                None
            } else {
                Some(serde_json::from_str(line).unwrap())
            }
        })
        .collect()
}

fn cmp(left: &Value, right: &Value) -> std::cmp::Ordering {
    match (left, right) {
        (Value::Number(left), Value::Number(right)) => {
            left.as_i64().unwrap().cmp(&right.as_i64().unwrap())
        }
        (Value::Number(_), Value::Array(_)) => {
            cmp(&Value::Array(vec![left.clone()]), right)
        }
        (Value::Array(_), Value::Number(_)) => {
            cmp(left, &Value::Array(vec![right.clone()]))
        }
        (Value::Array(left), Value::Array(right)) => {
            if let Some(c) = left
                .iter()
                .zip(right.iter())
                .map(|(l, r)| cmp(l, r))
                .find(|&c| c != std::cmp::Ordering::Equal)
            {
                c
            } else {
                left.len().cmp(&right.len())
            }
        }
        _ => unimplemented!(),
    }
}

pub fn task1(input: &[Value]) -> usize {
    input
        .chunks(2)
        .enumerate()
        .filter_map(|(i, pair)| {
            if cmp(&pair[0], &pair[1]) == std::cmp::Ordering::Less {
                Some(i + 1)
            } else {
                None
            }
        })
        .sum()
}

pub fn task2(input: &[Value]) -> usize {
    let mut packets = input.to_vec();
    let start: Value = serde_json::from_str("[[2]]").unwrap();
    let end: Value = serde_json::from_str("[[6]]").unwrap();
    packets.push(start.clone());
    packets.push(end.clone());
    packets.sort_by(cmp);
    let start = packets.iter().position(|v| v == &start).unwrap() + 1;
    let end = packets.iter().position(|v| v == &end).unwrap() + 1;
    start * end
}

Викинув якийсь старий пакет json, поставив стандартний serde_json. Особливо приємно, що функція порівняння, яку я написав для першого завдання, зайшла і для другого.

116 Востаннє редагувалося koala (14.12.2022 00:07:07)

Re: Advent of Code

Зробив 2019-13 (код комп'ютера див. вище... хоча, здається, його ще довелося потім трохи модифікувати)
Умова: програма для комп'ютера видає "зображення" гри на кшталт арканоїда у вигляді трійок (x,y,t) - координат і типу комірки.
1. Порахувати кількість блоків з кодом 2 - це я в 2019 зробив.
2. Замінивши перший байт пам'яті комп'ютера перед запуском на 2, зіграти в арканоїд. На вхід очікується -1, 0 або 1 - ліво, на місці або право відповідно. Також комп'ютер іноді видає рахунок у вигляді (-1, 0, рахунок). Коли будуть збиті усі блоки, який буде рахунок?

2019-13, Rust
use super::computer::Computer;

pub fn parse_input(input: &str) -> Vec<isize> {
    Computer::prepare_code(input)
}

use std::collections::HashMap;

const EMPTY: isize = 0;
const WALL: isize = 1;
const BLOCK: isize = 2;
const PADDLE: isize = 3;
const BALL: isize = 4;

pub fn task1(code: &[isize]) -> usize {
    let mut computer = Computer::new(code);
    computer.run();
    let mut grid = HashMap::new();
    while let (Some(x), Some(y), Some(t)) =
        (computer.read(), computer.read(), computer.read())
    {
        grid.insert((x, y), t);
    }
    grid.values().filter(|&&v| v == BLOCK).count()
}

pub fn task2(code: &[isize]) -> isize {
    //pre-run to calculate parameters of field
    let mut computer = Computer::new(code);
    computer.run();
    let mut grid = HashMap::new();
    while let (Some(x), Some(y), Some(t)) =
        (computer.read(), computer.read(), computer.read())
    {
        grid.insert((x, y), t);
    }
    let width = grid.keys().map(|&p| p.0).max().unwrap() + 1;
    //let height = grid.keys().map(|&p| p.1).max().unwrap();
    let last_row = code
        .windows(width as usize)
        .enumerate()
        .fold(None, |last, (i, wnd)| {
            if wnd[0] == WALL
                && wnd[1..wnd.len() - 1].iter().all(|&x| x == EMPTY)
                && wnd[wnd.len() - 1] == WALL
            {
                Some(i)
            } else {
                last
            }
        })
        .unwrap();
    let mut blocks: HashMap<_, _> =
        grid.iter().filter(|(_, &t)| t == BLOCK).collect();

    let mut code = code.to_vec();
    code[0] = 2;
    for i in 1..width - 1 {
        code[last_row + i as usize] = WALL;
    }
    let mut computer = Computer::new(&code);
    let mut score = 0;
    loop {
        computer.run();
        while let (Some(x), Some(y), Some(t)) =
            (computer.read(), computer.read(), computer.read())
        {
            if x >= 0 {
                if t != BLOCK {
                    blocks.remove(&(x, y));
                }
            } else {
                score = t;
            }
        }
        computer.write(0);
        if blocks.is_empty() {
            break;
        }
    }
    score
}
Нотатки

Спершу спробував додати ncurses і реально "пограти", але платформа шириною 1 клітинку, а блоків у мене 341. Тому я "хакнув" програму, домалювавши знизу стінку. Гадаю, правильний варіант - рухати платформу за м'ячем, але хай уже колись іншим разом :)

117

Re: Advent of Code

Умова: є мапа блоків, на які зверху (з однієї точки) сиплеться пісок. Кожна піщинка намагається спершу "впасти" униз, потім униз-ліворуч, потім униз-праворуч.
1. Скільки піщинок впаде, доки вони досягнуть дна?
2. Скільки піщинок впаде, доки взагалі можна буде додавати піщинки?

2022#14, Rust
pub fn parse_input(input: &str) -> Vec<Vec<u8>> {
    let input = input
        .lines()
        .map(|line| {
            line.split(" -> ")
                .map(|pair| {
                    let (x, y);
                    text_io::scan!(pair.bytes()=>"{},{}", x, y);
                    (x, y)
                })
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>();
    let (max_x, max_y) = input.iter().flat_map(|line| line.iter()).fold(
        (i32::MIN, i32::MIN),
        |(max_x, max_y), &(x, y)| {
            (std::cmp::max(max_x, x), std::cmp::max(max_y, y))
        },
    );
    let width = (2 * max_x) as usize;
    let height = (max_y + 1) as usize;
    let mut map = vec![vec![b' '; width]; height];
    for line in input {
        for pair in line.windows(2) {
            if pair[0].0 == pair[1].0 {
                let range = if pair[0].1 <= pair[1].1 {
                    pair[0].1..=pair[1].1
                } else {
                    pair[1].1..=pair[0].1
                };
                for y in range {
                    map[y as usize][pair[0].0 as usize] = b'#';
                }
            } else {
                let range = if pair[0].0 <= pair[1].0 {
                    pair[0].0..=pair[1].0
                } else {
                    pair[1].0..=pair[0].0
                };
                for x in range {
                    map[pair[0].1 as usize][x as usize] = b'#';
                }
            }
        }
    }
    map
}

pub fn task1(map: &[Vec<u8>]) -> usize {
    let mut map = map.to_vec();
    for sandgrain in 0.. {
        assert_eq!(map[0][500], b' ');
        let (mut x, mut y) = (500, 0);
        loop {
            if y == map.len() - 1 {
                return sandgrain;
            } else if map[y + 1][x] == b' ' {
            } else if map[y + 1][x - 1] == b' ' {
                x -= 1;
            } else if map[y + 1][x + 1] == b' ' {
                x += 1;
            } else {
                map[y][x] = b'o';
                break;
            }
            y += 1;
        }
    }
    unreachable!()
}

pub fn task2(map: &[Vec<u8>]) -> usize {
    let mut map = map.to_vec();
    map.push(vec![b' '; map[0].len()]);
    for sandgrain in 0.. {
        if map[0][500] != b' ' {
            return sandgrain;
        }
        let (mut x, mut y) = (500, 0);
        loop {
            if y == map.len() - 1 {
                map[y][x] = b'o';
                break;
            } else if map[y + 1][x] == b' ' {
            } else if map[y + 1][x - 1] == b' ' {
                x -= 1;
            } else if map[y + 1][x + 1] == b' ' {
                x += 1;
            } else {
                map[y][x] = b'o';
                break;
            }
            y += 1;
        }
    }
    unreachable!()
}
Подякували: leofun011

118 Востаннє редагувалося koala (15.12.2022 22:19:19)

Re: Advent of Code

За цей код мені дещо соромно, але в релізній збірці на моєму Ryzen 5 1600 вкладається в 4 секунди, а це головне, правильно? Я абсолютно певен, що цей код можна дуже сильно оптимізувати

Умова: є набір сенсорів і маячків на цілочисельній площині. Сенсори показують координати свої і найближчого до себе (за манхеттенською відстанню) маячка.
1. На прямій y=2_000_000 знайти кількість клітин, де не може бути маячка (тобто вони ближче до якогось сенсора, ніж його маячок).
2. У квадраті (x=0..4_000_000, y=0..4_000_000) знайти єдину точку, про яку сенсори нічого не кажуть.

2022#15, Rust
pub fn parse_input(input: &str) -> Vec<((i32, i32), (i32, i32))> {
    input.lines()
         .map(|line|{let (x,y,bx,by);
            text_io::scan!(line.bytes()=>"Sensor at x={}, y={}: closest beacon is at x={}, y={}",x,y,bx,by);
            ((x,y),(bx,by))
     }).collect()
}

fn generate_row(
    sensors: &[((i32, i32), (i32, i32))],
    row_y: i32,
) -> Vec<(i32, i32)> {
    let mut list: Vec<_> = sensors
        .iter()
        .filter_map(|((x, y), (bx, by))| {
            let dist = (bx - x).abs() + (by - y).abs();
            let dy = dist - (row_y - y).abs();
            if dy >= 0 {
                Some((x - dy, x + dy))
            } else {
                None
            }
        })
        .collect();
    list.sort_by_key(|&(left, _right)| left);
    let mut i = 0;
    while i < list.len() - 1 {
        if list[i + 1].0 <= list[i].1 + 1 {
            list[i].1 = std::cmp::max(list[i].1, list[i + 1].1);
            list.remove(i + 1);
        } else {
            i += 1;
        }
    }
    list
}

pub fn task1(sensors: &[((i32, i32), (i32, i32))]) -> i32 {
    const ROW_Y: i32 = 2_000_000;
    let list = generate_row(sensors, ROW_Y);

    let mut beacons: Vec<_> = sensors
        .iter()
        .filter_map(|&(_, (bx, by))| if by == ROW_Y { Some(bx) } else { None })
        .collect();
    beacons.sort();
    beacons.dedup();

    list.iter()
        .map(|(left, right)| right - left + 1)
        .sum::<i32>()
        - beacons.len() as i32
}

pub fn task2(sensors: &[((i32, i32), (i32, i32))]) -> usize {
    const SIZE: i32 = 4_000_000;
    for row_y in 0..=SIZE {
        let mut list = generate_row(sensors, row_y);
        loop {
            let last = list.len() - 1;
            if list[last].0 > SIZE {
                list.remove(last);
            } else if list[last].0 > SIZE {
                list[last].0 = SIZE;
                break;
            } else {
                break;
            }
        }
        loop {
            if list[0].1 < 0 {
                list.remove(0);
            } else if list[0].0 < 0 {
                list[0].0 = 0;
                break;
            } else {
                break;
            }
        }
        if list.len() == 1 {
            if list[0].0 > 0 {
                return row_y as usize;
            } else if list[0].1 < SIZE {
                return SIZE as usize * SIZE as usize + row_y as usize;
            }
        } else {
            return (list[0].1 as usize + 1) * SIZE as usize + row_y as usize;
        }
    }
    unreachable!();
}

119

Re: Advent of Code

Так, почалося.
#16 - які будуть ідеї? Познаходити довжини шляхів між ненульовими кранами і далі перебором лише серед них?

120

Re: Advent of Code

Тетрис!