Архив рубрики: Problem solving

Advent of Code 2023: Day 4: Scratchcards

Про задачу четвертого дня сказать особенно нечего. По условию – проще третей. По парсингу ввода – проще второй. Решается быстро.

Сразу прикинул, что с использованием примитивов или оборачиванием в типы из стандартной библиотеки – будет портяночно. Поэтому – отдельный класс с логикой:

public class Card {
    private static final Predicate<String> EMPTY = s -> " ".equals(s) || "".equals(s);
    Integer cardN, winCnt;
    Set<Integer> win, have;
    List<Card> nextCards = new ArrayList<>(); // added for part 2
    public Card(String cardN, String[] win, String[] have) {
        this.cardN = Integer.parseInt(cardN.replaceAll("^Card\\s+", ""));
        this.win = parseNums(win);
        this.have = parseNums(have);
        this.winCnt = (int) this.have.stream().filter(h -> this.win.contains(h)).count();
    }
    void addNext(List<Card> nextCards) { // added for part 2
        this.nextCards.addAll(nextCards);
    }
    Stream<Card> flat() { // added for part 2
        return Stream.concat(Stream.of(this),
                this.nextCards.stream().flatMap(Card::flat));
    }
    private static Set<Integer> parseNums(String[] nums) {
        return Arrays.stream(nums).filter(not(EMPTY)).map(Integer::parseInt)
                .collect(Collectors.toSet());
    }
};
Читать далее Advent of Code 2023: Day 4: Scratchcards

Advent of Code 2023: Day 3: Gear Ratios

В начале была лень… Стойкое нежелание возиться с границами массивов. Оно, и только оно толкнуло меня на скользкую дорожку замены матрицы примитивов на List<List<>>.

Следующим шагом на пути окунания в пучины многословия – стало создание контейнеров для упаковки данных со “схемы двигателя”. Вот они:

public record Coord(Integer row, Integer column){};
public record Cell(Coord coord, Integer codePoint){
    Set<Coord> border() {return Set.of(
            new Coord(coord.row(), coord.column() - 1), // left
            new Coord(coord.row() - 1, coord.column() - 1), // top-left
            new Coord(coord.row() - 1, coord.column()), // top
            new Coord(coord.row() - 1, coord.column() + 1), // top-right
            new Coord(coord.row(), coord.column() + 1), // right
            new Coord(coord.row() + 1, coord.column() + 1), // bot-right
            new Coord(coord.row() + 1, coord.column()), // bottom
            new Coord(coord.row() + 1, coord.column() - 1) // bot-left
    );}
};
public record Part(List<Cell> cells){
    public Part {
        cells = List.copyOf(cells);
    }
    Set<Coord> border() {
        return cells.stream()
            .flatMap(c -> c.border().stream())
            .filter(bCoord -> cells.stream()
                    .noneMatch(c -> bCoord.equals(c.coord())))
            .collect(Collectors.toSet());
    }
    Integer value() {
        return Integer.parseInt(cells.stream()
                .map(c -> Character.toChars(c.codePoint()))
                .map(String::new).collect(Collectors.joining()));
    }
};
Читать далее Advent of Code 2023: Day 3: Gear Ratios

Advent of Code 2023: Day 2: Cube Conundrum

Страшный, длинный, мучительный парсинг ввода…
Хотелось бы, конечно, иметь возможность сделать по-перловому, что-то типа: echo -e "Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green\nGame 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue" | perl -wlne '@matches = $_ =~ /(?:\G(?!\A)|^Game) (\S+)/g; print join("=",@matches)'.

Немного почистить после, или сразу докрутить регулярку, чтобы не захватывала разделители. Сложить в хэш. И закончить кучей циклов в итоге 🙁

С другой стороны – и возня с java Matcher не вдохновляла, и описывать структуру в виде POJO – для чисто скриптового решения – зачем.

split – дёшево и сердито, fastpath бонусом. К счастью – ввод был одинаков для обеих частей загадки.

Читать далее Advent of Code 2023: Day 2: Cube Conundrum

Advent of Code 2023: Day 1: Trebuchet?!

Снова AoC – и снова начат с опозданием. Дуплет! Основная идея прежняя – решать в jshell, пока это не станет слишком многословным. Экономия на буковках, в общем.

Обвязка для загрузки условий задачи – та же, что для AoC-2022. Тег для задачек 2023 года – adventofcode-2023 (или раздел Problem Solving).

Читать далее Advent of Code 2023: Day 1: Trebuchet?!

HackerRank Bit Manipulation: Counter game

Вторая из ранее сохранённых и ныне обретённых задачек с HackerRank. Как понятно из заголовка – решается через битовые операции.

Хотя – теоретическим можно было бы помучиться с BigInteger и арифметикой… И посмотреть, какое время займёт поиск решения.

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            long n = in.nextLong();
            String result = counterGame(n - 1);
            System.out.println(result);
        }
        in.close();
    }

    private static String counterGame(long n) {
        //long mask = 0x8000000000000000L; //2^63 in hex //W
        //eq:
        //long mask = -9223372036854775808L; //2^63 //W
        long mask;
        int step = 0;
        for (int i = 63; i >= 0; i--) {
            mask = 1L << i;
            //compare with 2 power i
            if ((n & mask) != 0) {
                //we max 2^i
                //step++;
                step = step ^ 1;
            }
            n -= mask;
            //mask >>>= 1;
        }

        return ((step & 1) != 0) ? "Louise" : "Richard";
    }

}

Традиционно – решение на Гитхабе.

https://www.hackerrank.com/challenges/counter-game/problem

HackerRank 30 Days of Code: Day 11: 2D Arrays

Не Литкодом единым, как говорится! Нашёл на диске пару задачек с HackerRank – видимо, показались тогда особо любопытными, и были сохранены.

Впрочем, и сейчас они выглядят интересно. Эта, например (первая из них) – перемещение паттерна в виде “песочных часов” по “игровому полю”, представленному матрицей, с целью найти такой паттерн, сумма цифр в котором будет максимальной.

Здесь у меня получилось два решения – частное (на Java) и общее (на Perl).

Читать далее HackerRank 30 Days of Code: Day 11: 2D Arrays

LeetCode 125. Valid Palindrome

Очередная задачка уровня Easy, но с довольно низким показателем Acceptance (44.4%). Что выражается в достаточно обширном наборе граничных случаев, некоторые из которых делают больно 🙂

Было желание сделать за один проход по исходной строке (без выделения дополнительно памяти). Вроде даже получилось, если ориентироваться на статистику запуска с LeetCode.

class Solution {

    private static final int LETTER_CASE_SHIFT = 32;

    public boolean isPalindrome(String s) {
        if (s.length() == 1) return true;
        char a, b;
        int mid = (s.length() - 1) >>> 1;
        for (int i = 0, j = s.length() - 1; i <= mid; i++, j--) {
            a = s.charAt(i);
            b = s.charAt(j);
            while (isNotAlphaNumeric(a) && i < j) {
                a = s.charAt(++i);
            }
            while (isNotAlphaNumeric(b) && i < j) {
                b = s.charAt(--j);
            }
            if (isComparable(a, b)) {
                if (!equalsIgnoreCase(a, b)) {
                    return false;
                }
            } else {
                return false;
            }
            mid = (i + j) / 2;
        }
        return true;
    }

    private static boolean equalsIgnoreCase(char a, char b) {
        return a == b
            || a - LETTER_CASE_SHIFT == b
            || a == b - LETTER_CASE_SHIFT;
    }

    private static boolean isComparable(char a, char b) {
        return (isLetter(a) && isLetter(b))
            || (!isLetter(a) && !isLetter(b));
    }

    private static boolean isLetter(char ch) {
        return 'a' <= ch && ch <= 'z'
            || 'A' <= ch && ch <= 'Z';
    }

    private static boolean isNotAlphaNumeric(char ch) {
        return !isLetter(ch) && ('0' > ch || ch > '9');
    }

}
Success:
    Runtime:2 ms, faster than 99.92% of Java online submissions.
    Memory Usage:42.3 MB, less than 87.41% of Java online submissions.

Ссылка на решение на Гитхаб.

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
https://leetcode.com/problems/valid-palindrome/

LeetCode 2278. Percentage of Letter in String

Ещё одна простая задачка – определение процентного содержания целевого символа в исходной строке. Пара решений:

  • через стримы (примитивно, без кастомной свёртки, да и помедленней)
  • и через цикл for.

Стримы

public int percentageLetter(String s, char letter) {
    long cnt = s.chars().filter(it -> it == (int) letter).count();
    return (int) (100 * cnt / s.length());
}
Success:
    Runtime:2 ms, faster than 12.22% of Java online submissions.
    Memory Usage:40.6 MB, less than 45.95% of Java online submissions.

Цикл

public int percentageLetter(String s, char letter) {
    int cnt = 0;
    for (char c : s.toCharArray()) {
        cnt += c == letter ? 1 : 0;
    }
    return 100 * cnt / s.length();
}
Success:
    Runtime:0 ms, faster than 100.00% of Java online submissions.
    Memory Usage:40.1 MB, less than 88.72% of Java online submissions.

Решение на гитхабе.

Given a string s and a character letter, return the percentage of characters in s that equal letter rounded down to the nearest whole percent.
https://leetcode.com/problems/percentage-of-letter-in-string/

LeetCode 1935. Maximum Number of Words You Can Type

Тоже забавная задачка – со “сломанной клавиатурой”. Решил в ней Arrays.binarySearch использовать для поиска буквы слова в наборе “сломанных клавишей”, да и чтобы не забыть о его (метода) существовании в целом.

Судя по статистике – нормально получилось, в общем-то.

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        var brL = brokenLetters.toCharArray();
        Arrays.sort(brL);
        var words = text.split(" ");
        int canTypeCnt = 0;
        for (var word : words) {
            boolean canType = true;
            for (int i = 0; i < word.length(); i++) {
                if (Arrays.binarySearch(brL, word.charAt(i)) >= 0) {
                    canType = false;
                    break;
                }
            }
            if (canType) {
                canTypeCnt++;
            }
        }
        return canTypeCnt;
    }
}
Success:
	Runtime:2 ms, faster than 91.93% of Java online submissions.
	Memory Usage:42.7 MB, less than 23.23% of Java online submissions.

То же решение на гитхабе.

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.
https://leetcode.com/problems/maximum-number-of-words-you-can-type/

LeetCode 13. Roman to Integer

Приятная задачка выпала в поиске – хоть и easy, а сделать интересно. Какая-то “практическая применимость” в ней видится.

Вроде, там где-то и обратная проблема была – перевод записи арабскими цифрами в запись римскими.

В общем-то, список валидных префиксов там прямо в условии задачи описан, особо выдумывать тут ничего не требуется.

class Solution {
    private Map<Character, Integer> values = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
    private Map<Character, Set<Character>> prefixes = Map.of('I', Set.of('V', 'X'), 'X', Set.of('L', 'C'), 'C', Set.of('D', 'M'));

    public int romanToInt(String s) {
        int max = s.length() - 1;
        int sum = 0;
        int i = 0;
        while (i <= max) {
            char c = s.charAt(i);
            if (prefixes.containsKey(c) && i < max && prefixes.get(c).contains(s.charAt(i + 1))) {
                sum += values.get(s.charAt(++i)) - values.get(c);
            } else {
                sum += values.get(c);
            }
            i++;
        }
        return sum;
    }
}
Читать далее LeetCode 13. Roman to Integer