21

Re: Advent of Code

Мені пам'яті не вистачає на третій вкладений цикл. Власної, не комп'ютерної. А тут усе тупо моделюється, як в умові написано, думати не треба.

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

22

Re: Advent of Code

Зовсім трохи бітової арифметики.

2021_3.rs
fn task1(numbers: &[usize], size: usize) -> usize
{
    let (gamma, epsilon) = (0..size).rev()
                                    .map(|i|numbers.iter()
                                                   .filter(|&n|(n>>i)&1==1)
                                                   .count())
                                    .fold((0,0),|(gamma, epsilon), count|
                                    (
                                        (gamma  <<1) | (2*count> numbers.len()) as usize, 
                                        (epsilon<<1) | (2*count<=numbers.len()) as usize,
                                    ));
    gamma*epsilon
}

fn find_by_bit_criteria<F>(numbers: &[usize], size: usize, criteria: F) -> usize
    where F: Fn(usize, bool) -> bool
{
    let mut numbers = Vec::from(numbers);
    for i in (0..size).rev() {
        if numbers.len() == 1 {
            break;
        }
        let more_ones = numbers.iter()
                               .filter(|&n|(n>>i)&1==1)
                               .count()*2 >= numbers.len();
        numbers = numbers.into_iter()
                         .filter(|&n|criteria((n>>i)&1, more_ones))
                         .collect();
    }
    numbers[0]
}

fn task2(numbers: &[usize], size: usize) -> usize
{
    let oxygen = find_by_bit_criteria(numbers, size, 
        |digit, more_ones| (digit == 1) == more_ones);
    let co2 = find_by_bit_criteria(numbers, size, 
        |digit, more_ones| (digit == 0) == more_ones);
    oxygen * co2
}

fn main() {
    let input = aoc::get_input_from_ini_with_year("3","2021").unwrap();
    let mut size = 0;
    let numbers:Vec<_> = input.lines()
                              .map(|line|{size=line.len();usize::from_str_radix(line, 2).unwrap()})
                              .collect();
    println!("Result1: {}", task1(&numbers, size));
    println!("Result2: {}", task2(&numbers, size));
}

Rust не відпускає, доки не доведеш запис до ідеалу. Умову я десь годину оптимізовував, додавав і викидав Ordering і т.д. Зате яка краса в результаті.

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

23

Re: Advent of Code

А оце я щось розійшовся. І Rust не допоміг :(
Працює, звісно, але шукав тупу помилку дуже довго.

2021_4.rs
const BINGO_SIZE :usize = 5;

struct Board ([[usize; BINGO_SIZE];BINGO_SIZE] );

impl Board {
    fn position(&self, value: usize) -> Option<(usize, usize)> {
        for row in 0..BINGO_SIZE {
            for col in 0..BINGO_SIZE {
                if self.0[row][col] == value {
                    return Some((row, col));
                }
            }
        }
        None
    }
}

struct BingoSettings
{
    calls: Vec<usize>,
    boards: Vec<Board>,
}

impl BingoSettings
{
    fn from_str(s: &str) -> BingoSettings {
        let mut s = s.lines();
        let calls = s.next()
                     .unwrap()
                     .split(",")
                     .map(|s|s.parse().unwrap())
                     .collect();
        let mut boards = Vec::new();
        let mut idx = 0;
        for line in s {
            if line.is_empty() {
                boards.push(Board([[0, 0, 0, 0, 0, ],
                                   [0, 0, 0, 0, 0, ],
                                   [0, 0, 0, 0, 0, ],
                                   [0, 0, 0, 0, 0, ],
                                   [0, 0, 0, 0, 0, ],]));
                idx = 0;
            } else {
                let mut board = boards.last_mut().unwrap();
                for (i, n) in line.split_whitespace().enumerate() {
                    board.0[idx][i] = n.parse().unwrap();
                }
                idx = (idx+1) % 5;
            }
        }
        BingoSettings {
            calls,
            boards,
        }
    }
}

type StrikeBoard = [[bool; BINGO_SIZE];BINGO_SIZE];

struct Bingo<'a>
{
    settings: &'a BingoSettings,
    winners: Vec<(usize, usize)>,
    striked: Vec<StrikeBoard>,
}

impl Bingo<'_>
{
    fn new(settings: &BingoSettings) -> Bingo
    {
        Bingo {
            settings,
            winners: Vec::new(),
            striked: std::iter::repeat([[false, false, false, false, false, ],
                                        [false, false, false, false, false, ],
                                        [false, false, false, false, false, ],
                                        [false, false, false, false, false, ],
                                        [false, false, false, false, false, ],])
            .take(settings.boards.len())
            .collect(),
        }
    }

    fn task(&mut self, nwinner:usize) -> usize {
        for &call in &self.settings.calls {
            self.strikeout(call);
            if self.winners.len() == nwinner {
                break;
            }
        }
        self.last_winner_score()
    }

    fn strikeout(&mut self, call: usize) {
        for board_idx in 0..self.striked.len() {
            if let Some((row, col)) = self.settings.boards[board_idx].position(call) {
                self.striked[board_idx][row][col] = true;
                self.check_winner(board_idx, row, col, call);
            };
        }
    }

    fn check_winner(&mut self, board_idx:usize, row_idx: usize, col_idx:usize, call: usize)
    {
        if !self.winners.iter().find(|&&(board, _)|board == board_idx).is_some() {
            if     (0..BINGO_SIZE).map(|i|self.striked[board_idx][row_idx][i])
                                  .all(|striked|striked)
                || (0..BINGO_SIZE).map(|i|self.striked[board_idx][i][col_idx])
                                  .all(|striked|striked) {
                let mut score = 0;
                for row in 0..BINGO_SIZE {
                    for col in 0..BINGO_SIZE {
                        if !self.striked[board_idx][row][col] {
                            score += self.settings.boards[board_idx].0[row][col];
                        }

                    }
                }
                self.winners.push((board_idx, call * score));
            }
        }
    }

    fn last_winner_score(&self) -> usize {
        self.winners.last().unwrap().1
    }
}

fn task1(bingo: &BingoSettings) -> usize
{
    Bingo::new(bingo).task(1)
}

fn task2(bingo: &BingoSettings) -> usize
{
    Bingo::new(bingo).task(bingo.boards.len())
}

#[cfg(test)]
mod tests {
    // Note this useful idiom: importing names from outer (for mod tests) scope.
    use super::*;
    const DATA: &str = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19

 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

14 21 17 24  4
10 16 15  9 19
18  8 23 26 20
22 11 13  6  5
 2  0 12  3  7";

    #[test]
    fn test_task1() {
        let bingo = BingoSettings::from_str(&DATA);
        assert_eq!(task1(&bingo), 4512);
    }


    #[test]
    fn test_task2() {
        let bingo = BingoSettings::from_str(&DATA);
        assert_eq!(task2(&bingo), 1924);
    }
}

fn main() {
    let input = aoc::get_input_from_ini_with_year("4","2021").unwrap();
    let bingo = BingoSettings::from_str(&input);
    println!("Result1: {}", task1(&bingo));
    println!("Result2: {}", task2(&bingo));
}

24

Re: Advent of Code

Спершу хотів погратися з інтервалами, потім вирішив, що 1000х1000 - не надто велике поле.

2021/5.py
import aoc

import os

NUMBER = os.path.basename(__file__).removesuffix('.py')

def is_non_diagonal(pts: list[list[int]]) -> bool:
    diff = [pts[0][0]-pts[1][0], pts[0][1]-pts[1][1]]
    return 0 in diff


def task(data: str, *, filter: bool) -> int:
    field = [[0]*1000 for _ in range(1000)]
    for line in data.splitlines():
        line = [[int(x) for x in part.split(',')] for part in line.split('->')]
        if filter and not is_non_diagonal(line):
            continue
        x,y = line[0]
        dx = 1 if line[1][0]>x else -1 if line[1][0]<x else 0
        dy = 1 if line[1][1]>y else -1 if line[1][1]<y else 0
        while True:
            field[x][y] += 1
            if [x,y]==line[1]:
                break
            x += dx
            y += dy
    return sum(1 for line in field for vent in line if vent>1)


def task1(data: str) -> int:
    return task(data, filter=True)
        
def task2(data: str) -> int:
    return task(data, filter=False)

if __name__ == '__main__':
    data = aoc.load_data(NUMBER, verbose=True)
    
    print('Task1:', task1(data))
    print('Task2:', task2(data))
Подякували: dot1

25 Востаннє редагувалося koala (05.12.2021 10:21:51)

Re: Advent of Code

А до біса, Rust так само:

2021_5.rs
type Line = ((i32, i32),(i32, i32));

const FIELD_SIZE: usize = 1000;

fn parse_vents(lines: &str) -> Vec<Line> {
    lines.lines()
         .map(|line|{
            let mut line = line.split(" -> ");
            let mut pt1 = line.next().unwrap().split(',');
            let mut pt2 = line.next().unwrap().split(',');
            ((pt1.next().unwrap().parse().unwrap(), pt1.next().unwrap().parse().unwrap()),
             (pt2.next().unwrap().parse().unwrap(), pt2.next().unwrap().parse().unwrap()))
        })
        .collect()
}

fn is_diagonal(line: &Line) -> bool {
    line.0.0 != line.1.0 && line.0.1 != line.1.1
}

fn ordering_to_i32(order: std::cmp::Ordering) -> i32{
    match order {
        std::cmp::Ordering::Greater =>  1,
        std::cmp::Ordering::Equal   =>  0,
        std::cmp::Ordering::Less    => -1,
    }
}

fn task(vents: &[Line], is_diagonals_needed: bool) -> i32
{
    let mut field: Vec<Vec<i32>> = std::iter::repeat(std::iter::repeat(0).take(FIELD_SIZE).collect()).take(FIELD_SIZE).collect();
    for vent in vents {
        if is_diagonals_needed || !is_diagonal(vent) {
            let (mut x, mut y) = vent.0;
            let (dx, dy) = (-ordering_to_i32(x.cmp(&vent.1.0)),-ordering_to_i32(y.cmp(&vent.1.1)));
            loop {
                field[x as usize][y as usize] += 1;
                if (x,y) == vent.1 {
                    break;
                }
                x += dx;
                y += dy;
            }
        }
    }
    field.iter().map(|line|line.iter().filter(|&&x|x>1).count() as i32).sum()
}

fn task1(vents: &[Line]) -> i32
{
    task(vents, false)
}


fn task2(vents: &[Line]) -> i32
{
    task(vents, true)
}

fn main() {
    let input = aoc::get_input_from_ini_with_year("5","2021").unwrap();
    let vents = parse_vents(&input);
    println!("Result1: {}", task1(&vents));
    println!("Result2: {}", task2(&vents));
}
Подякували: dot1

26 Востаннє редагувалося dot (05.12.2021 12:05:09)

Re: Advent of Code

2021#5 Py3.9.5
import re, itertools

vents = list()

with open("input.txt") as file:
    for line in file:
        x1, y1, x2, y2 = map(int, re.findall(r"\d+", line))
        xo = 1 if x1 <= x2 else -1
        yo = 1 if y1 <= y2 else -1

        # For Part One
        # if x1 == x2 or y1 == y2:

        for x, y in itertools.zip_longest(
            range(x1, x2 + xo, xo),
            range(y1, y2 + yo, yo),
            fillvalue=x1 if x1 == x2 else y1 if y1 == y2 else None,
        ):
            vents.append((x, y))

overlaps = {}

for e in vents:
    overlaps[e] = overlaps.get(e, 0) + 1

points = 0

for _, o in overlaps.items():
    if o > 1:
        points += 1

print("Answer:", points)  # 7436, 21104

Ja vzahalji obijcov sja bez matritsjy, tupo tcerez spyskiv koordynat, qeq. Ja navitj tcomusj, nespodjivano dlja sebe, zadovolenyj svojym rezultatom — vse vidnosno lehko tcytaljno, bez gaxlyvyx perenasytcenj dugok (jakctco propustyty movu pro efektivnistj).

27 Востаннє редагувалося koala (05.12.2021 19:30:03)

Re: Advent of Code

Модифікував

2021/5a.py
import aoc

import os
from collections import defaultdict

NUMBER = os.path.basename(__file__).removesuffix('a.py')

def is_non_diagonal(pts: list[list[int]]) -> bool:
    diff = [pts[0][0]-pts[1][0], pts[0][1]-pts[1][1]]
    return 0 in diff


def task(data: str, *, filter: bool) -> int:
    vents = defaultdict(int)
    for line in data.splitlines():
        line = [[int(x) for x in part.split(',')] for part in line.split('->')]
        if filter and not is_non_diagonal(line):
            continue
        x,y = line[0]
        dx = 1 if line[1][0]>x else -1 if line[1][0]<x else 0
        dy = 1 if line[1][1]>y else -1 if line[1][1]<y else 0
        while True:
            vents[(x,y)]+=1
            if [x,y]==line[1]:
                break
            x += dx
            y += dy
    return sum(1 for count in vents.values() if count>1)


def task1(data: str) -> int:
    return task(data, filter=True)
        
def task2(data: str) -> int:
    return task(data, filter=False)

if __name__ == '__main__':
    data = aoc.load_data(NUMBER, verbose=True)
    print('Task1:', task1(data))
    print('Task2:', task2(data))

Відсотків на 10 повільніше за попереднє (0.18c проти 0.16c)

28 Востаннє редагувалося koala (05.12.2021 18:59:30)

Re: Advent of Code

2021_5a.rs
type Line = ((i32, i32),(i32, i32));

fn parse_vents(lines: &str) -> Vec<Line> {
    lines.lines()
         .map(|line|{
            let mut line = line.split(" -> ");
            let mut pt1 = line.next().unwrap().split(',');
            let mut pt2 = line.next().unwrap().split(',');
            ((pt1.next().unwrap().parse().unwrap(), pt1.next().unwrap().parse().unwrap()),
             (pt2.next().unwrap().parse().unwrap(), pt2.next().unwrap().parse().unwrap()))
        })
        .collect()
}

fn is_diagonal(line: &Line) -> bool {
    line.0.0 != line.1.0 && line.0.1 != line.1.1
}

fn ordering_to_i32(order: std::cmp::Ordering) -> i32{
    match order {
        std::cmp::Ordering::Greater =>  1,
        std::cmp::Ordering::Equal   =>  0,
        std::cmp::Ordering::Less    => -1,
    }
}

fn task(vents: &[Line], is_diagonals_needed: bool) -> i32
{
    use std::collections::HashMap;
    let mut known_vents : HashMap<(i32, i32), i32>= HashMap::new();
    for vent in vents {
        if is_diagonals_needed || !is_diagonal(vent) {
            let (mut x, mut y) = vent.0;
            let (dx, dy) = (-ordering_to_i32(x.cmp(&vent.1.0)),-ordering_to_i32(y.cmp(&vent.1.1)));
            loop {
                *known_vents.entry((x,y)).or_insert(0) += 1;
                if (x,y) == vent.1 {
                    break;
                }
                x += dx;
                y += dy;
            }
        }
    }
    known_vents.values().filter(|&&x|x>1).count() as i32
}

fn task1(vents: &[Line]) -> i32
{
    task(vents, false)
}


fn task2(vents: &[Line]) -> i32
{
    task(vents, true)
}

fn main() {
    let input = aoc::get_input_from_ini_with_year("5","2021").unwrap();
    let vents = parse_vents(&input);
    println!("Result1: {}", task1(&vents));
    println!("Result2: {}", task2(&vents));
}

Друге рішення - 25мс, перше - 4мс (у релізі, звісно, дебажні - 0,5с на 0,25с).
І так, на жаль, bench досі доступний лише на нестабільній гілці.

29

Re: Advent of Code

koala написав:

Модифікував

2021/5a.py

import aoc

import os
from collections import defaultdict

NUMBER = os.path.basename(__file__).removesuffix('a.py')

def is_non_diagonal(pts: list[list[int]]) -> bool:
    diff = [pts[0][0]-pts[1][0], pts[0][1]-pts[1][1]]
    return 0 in diff


def task(data: str, *, filter: bool) -> int:
    vents = defaultdict(int)
    for line in data.splitlines():
        line = [[int(x) for x in part.split(',')] for part in line.split('->')]
        if filter and not is_non_diagonal(line):
            continue
        x,y = line[0]
        dx = 1 if line[1][0]>x else -1 if line[1][0]<x else 0
        dy = 1 if line[1][1]>y else -1 if line[1][1]<y else 0
        while True:
            vents[(x,y)]+=1
            if [x,y]==line[1]:
                break
            x += dx
            y += dy
    return sum(1 for count in vents.values() if count>1)


def task1(data: str) -> int:
    return task(data, filter=True)
       
def task2(data: str) -> int:
    return task(data, filter=False)

if __name__ == '__main__':
    data = aoc.load_data(NUMBER, verbose=True)
    print('Task1:', task1(data))
    print('Task2:', task2(data))

Відсотків на 10 повільніше за попереднє (0.18c проти 0.16c)

Treba quote zaminyty na code

І так, на жаль, bench досі доступний лише на нестабільній гілці.

Ja protupyv dekiljka sekund: nabrav «Rudy…» zamistj «Ruby bench» i menji pokazuvalo lavotcky.

30

Re: Advent of Code

Дякую, виправив.

Це взагалі Rust, але то таке :)

31

Re: Advent of Code

Ctcosj ja sjoʼdnja vzahalji neuvagnyj, xex.

32 Востаннє редагувалося koala (06.12.2021 00:15:19)

Re: Advent of Code

День 5. 1. Є цілочисельні координати відрізків прямих: горизонтальних, вертикальних і діагональних під 45°. Треба знайти кількість цілочисельних точок перетину чи накладання цих відрізків, крім діагональних. 2. І діагональних теж.

33 Востаннє редагувалося koala (06.12.2021 08:48:38)

Re: Advent of Code

День 6. 1. Є популяція риб. Кожна риба народжує кожні 7 днів, крім новонароджених, які народжують на 9-й день. Є початковий стан (вік/час до народження) риб, обчислити кількість риб за 80 днів. 2. За 256 днів.

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

2021/6.py
import aoc

import os

NUMBER = os.path.basename(__file__).removesuffix('.py')

def simulate(data: str, time: int) -> int:
    fishes = [0]*9
    for age in data.split(','):
        fishes[int(age)] += 1
    for _ in range(time):
        fishes = fishes[1:]+fishes[:1]
        fishes[6] += fishes[8]
    return sum(fishes)

def task1(data: str) -> int:
    return simulate(data, 80)
        
def task2(data: str) -> int:
    return simulate(data, 256)

if __name__ == '__main__':
    data = aoc.load_data(NUMBER, verbose=True)
    print('Task1:', task1(data))
    print('Task2:', task2(data))
2021_6.rs
fn simulate(mut state: [usize; 9], time: usize) -> usize
{
    for _ in 0..time {
        let giving_birth = state[0];
        for i in 0..8 {
            state[i] = state[i+1];
        }
        state[6] += giving_birth;
        state[8] = giving_birth;
    }
    state.iter().sum()
}

fn task1(state: &[usize; 9]) -> usize
{
    simulate(*state, 80)
}


fn task2(state: &[usize; 9]) -> usize
{
    simulate(*state, 256)
}

fn main() {
    let input = aoc::get_input_from_ini_with_year("6","2021").unwrap();
    let mut state = [0; 9];
    for fish in input.split(',').map(|x|x.parse::<usize>().unwrap()) {
        state[fish] += 1;
    };
    println!("Result1: {}", task1(&state));
    println!("Result2: {}", task2(&state));
}
Подякували: dot1

34 Востаннє редагувалося dot (06.12.2021 17:39:59)

Re: Advent of Code

Ex, tcerez druhu zadatcu musyv pererobjaty, v pidsumku otrymav duge korotku proqu, bo tut tupo zsuv masyva z dekotrymy vidminostjamy.

2021#6, Py3.9.5
fishes = [list(map(int, open("input.txt").readline().split(","))).count(i) for i in range(9)]

for _ in range(256):  # For Part One: 80
    fishes = fishes[1:7] + [fishes[0] + fishes[7], fishes[8], fishes[0]]

print("Answer:", sum(fishes))

Pro vsjak, ja znaju, ge mnogyna do fish je fish.

35

Re: Advent of Code

О, за що я люблю Пайтон - це за можливість дуже коротко записати купу операцій.
Ваш код взагалі 9 разів відкриває файл, читає і парсить з нього стрічку, причому два останніх - гарантовано з результатом 0 :)
Але в один рядок.

36 Востаннє редагувалося dot (06.12.2021 21:07:28)

Re: Advent of Code

Ваш код взагалі 9 разів відкриває файл, читає і парсить з нього стрічку, причому два останніх - гарантовано з результатом 0 :)

Slucno, prytomnjice bulo by vynesty, np:

data = list(map(int, open("input.txt").read().split(",")))
fishes = [data.count(i) for i in range(9)]

Ale podurkuvaty zarady odnoji stritcky — beztsjino, :D.

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

37

Re: Advent of Code

fishes = list(map(data.count, range(9)))

як вже на те. Гм...

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

38 Востаннє редагувалося koala (07.12.2021 20:32:35)

Re: Advent of Code

День 7. 1. Є масив чисел, треба знайти таке, сума відстаней від якого до кожного іншого буде мінімальною, і повернути цю суму відстаней. 2. Те саме, але функція відстані між числами a та b - |a-b|*(|a-b|+1)/2.

Перше завдання - це просто медіана. Я так і зробив спершу. А от друге - треба трохи з математикою пововтузитися, там має бути розв'язок через похідні і бісекцію, але мені ліньки, тому досить тупо шукаю бісекцію з додатковими перевірками сусідів (фактично за градієнтом). Для загальності перше теж переробив.

2021/7.py
import aoc

import os
#import statistics
from typing import List, Callable
from functools import cache
import unittest

NUMBER = os.path.basename(__file__).removesuffix('.py')

#def task1_old(data: str) -> int:
#    data = [int(x) for x in data.split(',')]
#    median = int(statistics.median(data))
#    return sum(abs(position - median) for position in data)

def task(data: List[int], fuel: Callable[[int, int], int]) -> int:
    @cache
    def func(pos):
        return sum(fuel(crab, pos) for crab in data)
    pos = (data[-1]-data[0])//2
    step = (data[-1]-data[0])//4
    
    while True:
        dist = func(pos)
        dist_l = func(pos-1)
        dist_r = func(pos+1)
        if dist_l>=dist<=dist_r:
            return dist
        elif dist_r<dist:
            pos += step            
        else:
            pos -= step
        step = step//2 or 1        step = step//2 or 1

def task1(data: List[int]) -> int:
    return task(data, lambda crab, pos: abs(pos-crab))

def task2(data: List[int]) -> int:
    return task(data, lambda crab, pos: abs(pos-crab)*(abs(pos-crab)+1)//2)

class Test(unittest.TestCase):
    def test_task1(self):
        data = sorted(int(x) for x in [16,1,2,0,4,2,7,1,2,14])
        self.assertEqual(task1(data),37)
    def test_task2(self):
        data = sorted(int(x) for x in [16,1,2,0,4,2,7,1,2,14])
        self.assertEqual(task2(data),168)

if __name__ == '__main__':
    #unittest.main()
    data = aoc.load_data(NUMBER, verbose=True)
    data = sorted(int(x) for x in data.split(','))
    print('Task1:', task1(data))
    print('Task2:', task2(data))

UPD: трохи прибрав код в task

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

39 Востаннє редагувалося dot (07.12.2021 14:26:02)

Re: Advent of Code

2021#7 Py3.9.5
data = list(map(int, open("input.txt").read().split(",")))
one = list()
two = list()

for t in data:
    one.append(0)
    two.append(0)
    for f in data:
        one[-1] += abs(f - t)
        two[-1] += sum(range(1, abs(f - t) + 1))

print("Part One:", min(one))
print("Part Two:", min(two))

Tupo brutfors, kompjuternoji mitsjy vystatcylo: aby zrobyty i aby potcekaty v megax 2~3 sek.

40 Востаннє редагувалося koala (07.12.2021 20:37:02)

Re: Advent of Code

Ну тоді вже

- two[-1] += sum(range(1, abs(f - t) + 1))
+ two[-1] += (abs(f - t)*(abs(f - t) + 1)//2
Подякували: dot1