ФейкПрофил

Днешното беше гадно, мразя да се занимавам с графи (графове ?) :(

И аз мъчих малко графи, реших първата, но после нещо ми светна, че може и с една проста рекурсия :д

westy

ФейкПрофил

Днешното беше гадно, мразя да се занимавам с графи (графове ?) :(

И аз мъчих малко графи, реших първата, но после нещо ми светна, че може и с една проста рекурсия :д

Така съм решил първа част - два пъти, лол. Сега с новото ми решение от 8000 микросекунди падна на 150 микросекунди :) Но втората част ме мързи да я оптимизирам - нея съм я направил с една опашка, щото рекурсията е хуй с две остриета в ръст.

А също се оказа, че регулярните изрази не са чак толкова бавни - входа го парсвам за 700ус с регекс и за 250 с търсене за спейсове :Д

Отначало ме притесняваше, че може да има цикъл, но като се оказа, че няма се опростиха нещата

Двете втори задачи от вчера и предния ден бяха тегави. Хем знам, че могат да се решат с динамично, хем не мога да го измисля ;д

Втората от вчера я написах първо със brute-force, но беше супер бавно 😒. После добавих едно мемо и минава за 5ms заедно с четене на входа и сортиране так че съм quite happy :)

Ден-10 ми бяха лесни:

Първа част > 1500 наносекунди :)

Втора част > 1700 наносекунди

Само за втората част се измъчих докато си променя решението да ползва константно количество памет.

В първата част забелязах много интересен феномен,който не мога да си го обясня:

Вариант 1:

fn solve_part_one_1(input: &mut [i32]) -> Option<i32> {
    input.sort_unstable();

    let mut ones = 0;
    let mut threes = 1; 
    let mut prev = 0;

    for &i in input.iter() {
        let diff = i - prev;
        if diff == 1 {
            ones += 1;
        } else if diff == 3 {
            threes += 1;
        }

        prev = i;
    }

    if cfg!(debug_assertions) {
        println!("O:{}; T: {}; Result: {}", ones, threes, ones * threes);
    }

    Some(ones * threes)
}

Вариант 2:

fn solve_part_one_2(input: &mut [i32]) -> Option<i32> {
    input.sort_unstable();

    let mut sums = [0, 0, 1];
    let mut prev = 0;

    for &i in input.iter() {
        let diff = (i - prev) as usize;
        if diff <= 3 {
            sums[diff-1] += 1;
            prev = i;
        }
    }

    if cfg!(debug_assertions) {
        println!("O:{}; T: {}; Result: {}", sums[0], sums[2], sums[0] * sums[2]);
    }

    Some(sums[0] * sums[2])
}

Та това което не мога да си обясня е, защо вариант 1 се изпълнява за 2800 наносекунди, а вариант 2 - само за 1500. Толкова ли са бавни ИФовете ?

Ден девет бяха доста забавни задачите, защото бях забравил онзи трик за 2-sum където ходиш с два пойнтера - един от лява и един от дясно - та си го припомних.

Част 1 > 130 микросекунди (може и малко побързо, ако се ползва insertion sort) Част 2 > 1 микросекунда :)

Вчерашната задача ми беше гадна - много бъгове направих докато я подкарам, кода ми стана страшно грозен и рънва страшно бавно - цели 6мс за част 1 и 18 за част 2. Някакъв беше направил решение на ръст със СИМД, което рънваше за 170 микросекунди :)

Почти не остана :]

Днешната (Jurassic Jigsaw) обаче беше ужасна. Радвам се, че реших още първата част "правилно" с нареждане на пъзела та поне втората беше сравнително лесна.

Няколко часа, които никога няма да си върна 😀

Да, днешната беше гадна, а и ме болеше главата и почти се бях отказал. Но вчерашната беше по-гадна. Част 2 ме измъчи, въпреки че трябваше да направя съвсем малко промени. Просто тези милярди нива на рекурсия не можех да ги проследя и да дебъгна какво не работи като хората. Обаче като преспах и тази сутрин я подкарах от раз :Д

ФейкПрофил

.... щото рекурсията е хуй с две остриета в ръст. ....

Тази мъдрост ми хареса

Доста я намразих рекурсията, Лесно се пише, но после трудно се разбира и дебъгва.