DEV Community: Gangbaolede Li

Foobar: Escape Pods

Gangbaolede Li — Tue, 12 Oct 2021 02:53:06 +0000

You've blown up the LAMBCHOP doomsday device and relieved the bunnies of their work duries -- and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.

Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.

Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

For example, if you have:
entrances = [0, 1]
exits = [4, 5]
path = [
[0, 0, 4, 6, 0, 0], # Room 0: Bunnies
[0, 0, 5, 2, 0, 0], # Room 1: Bunnies
[0, 0, 0, 0, 4, 4], # Room 2: Intermediate room
[0, 0, 0, 0, 6, 6], # Room 3: Intermediate room
[0, 0, 0, 0, 0, 0], # Room 4: Escape pods
[0, 0, 0, 0, 0, 0], # Room 5: Escape pods
]

Then in each time step, the following might happen:
0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step. (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final solution remains the same.)

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

Input:
solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])
Output:
6

Input:
solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
Output:
16

from collections import deque
CORRIDOR_CAPACITY = 2000001


# Great ref: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
class EscapePods:
    def __init__(self, entrances, exits, path):
        n = len(path)
        m = n + 2

        # graph[0] is the new single source s
        # graph[-1] is the new single sink t
        self.graph = []
        self.size = m
        for i in range(m):
            self.graph.append([0] * m)

        for i in range(n):
            for j in range(n):
                self.graph[i+1][j+1] = path[i][j]

        for num in entrances:
            self.graph[0][num + 1] = CORRIDOR_CAPACITY

        for num in exits:
            self.graph[num + 1][m - 1] = CORRIDOR_CAPACITY

    def bfs(self):
        parents = [-1] * self.size
        queue = deque()
        queue.append(0)
        while queue and parents[-1] == -1:
            u = queue.popleft()
            for v in range(self.size):
                if self.graph[u][v] > 0 and parents[v] == -1:
                    queue.append(v)
                    parents[v] = u
        path = []
        u = parents[-1]
        while u != 0:
            if u == -1:
                return None
            path.append(u)
            u = parents[u]
        path.reverse()
        return path

    def solve(self):
        max_flow = 0
        path = self.bfs()

        while path:
            cap = CORRIDOR_CAPACITY
            u = 0
            for v in path:
                cap = min(cap, self.graph[u][v])
                u = v
            max_flow += cap
            u = 0
            for v in path:
                self.graph[u][v] -= cap
                self.graph[v][u] += cap
                u = v
            path = self.bfs()
        return max_flow


def solution(entrances, exits, path):
    escape_pods = EscapePods(entrances, exits, path)
    res = escape_pods.solve()
    return res

Foobar: Distract the Guards

Gangbaolede Li — Sun, 10 Oct 2021 08:46:52 +0000

The time for the mass escape has come, and you need to distract the guards so that the bunny prisoners can make it out! Unfortunately for you, they're watching the bunnies closely. Fortunately, this means they haven't realized yet that the space station is about to explode due to the destruction of the LAMBCHOP doomsday device. Also fortunately, all that time you spent working as first a minion and then a henchman means that you know the guards are fond of bananas. And gambling. And thumb wrestling.

The guards, being bored, readily accept your suggestion to play the Banana Games.

You will set up simultaneous thumb wrestling matches. In each match, two guards will pair off to thumb wrestle. The guard with fewer bananas will bet all their bananas, and the other guard will match the bet. The winner will receive all of the bet bananas. You don't pair off guards with the same number of bananas (you will see why, shortly). You know enough guard psychology to know that the one who has more bananas always gets over-confident and loses. Once a match begins, the pair of guards will continue to thumb wrestle and exchange bananas, until both of them have the same number of bananas. Once that happens, both of them will lose interest and go back to guarding the prisoners, and you don't want THAT to happen!

For example, if the two guards that were paired started with 3 and 5 bananas, after the first round of thumb wrestling they will have 6 and 2 (the one with 3 bananas wins and gets 3 bananas from the loser). After the second round, they will have 4 and 4 (the one with 6 bananas loses 2 bananas). At that point they stop and get back to guarding.

How is all this useful to distract the guards? Notice that if the guards had started with 1 and 4 bananas, then they keep thumb wrestling! 1, 4 -> 2, 3 -> 4, 1 -> 3, 2 -> 1, 4 and so on.

Now your plan is clear. You must pair up the guards in such a way that the maximum number of guards go into an infinite thumb wrestling loop!

Write a function answer(banana_list) which, given a list of positive integers depicting the amount of bananas the each guard starts with, returns the fewest possible number of guards that will be left to watch the prisoners. Element i of the list will be the number of bananas that guard i (counting from 0) starts with.

The number of guards will be at least 1 and not more than 100, and the number of bananas each guard starts with will be a positive integer no more than 1073741823 (i.e. 2^30 -1). Some of them stockpile a LOT of bananas.

Languages

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases

Inputs:

    (int list) banana_list = [1, 1]

Output:

    (int) 2

Inputs:

    (int list) banana_list = [1, 7, 3, 21, 13, 19]

Output:

    (int) 0

Solution/Hint:

The condition that two trainers (with x, y bananas) eventually stop if and only if x/y = 2^(n+1) - 1 where (n is integer and x > y). We can create/cache a set of numbers that can be written in 2^(n+1) - 1 form. With this condition, we can transform this problem to graph problem and apply Edmonds Blossom algorithm to construct a maximum matching and count the number of non-connected nodes.

Great resource about matching:
https://www.keithschwarz.com/interesting/code/edmonds-matching/

Foobar: Bomb, Baby!

Gangbaolede Li — Sat, 25 Sep 2021 18:30:19 +0000

You're so close to destroying the LAMBCHOP doomsday device you can taste it! But in order to do so, you need to deploy special self-replicating bombs designed for you by the brightest scientists on Bunny Planet. There are two types: Mach bombs (M) and Facula bombs (F). The bombs, once released into the LAMBCHOP's inner workings, will automatically deploy to all the strategic points you've identified and destroy them at the same time.

But there's a few catches. First, the bombs self-replicate via one of two distinct processes:
Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb, a Facula bomb is created;
Every Facula bomb spontaneously creates a Mach bomb.

For example, if you had 3 Mach bombs and 2 Facula bombs, they could either produce 3 Mach bombs and 5 Facula bombs, or 5 Mach bombs and 2 Facula bombs. The replication process can be changed each cycle.

Second, you need to ensure that you have exactly the right number of Mach and Facula bombs to destroy the LAMBCHOP device. Too few, and the device might survive. Too many, and you might overload the mass capacitors and create a singularity at the heart of the space station - not good!

And finally, you were only able to smuggle one of each type of bomb - one Mach, one Facula - aboard the ship when you arrived, so that's all you have to start with. (Thus it may be impossible to deploy the bombs to destroy the LAMBCHOP, but that's not going to stop you from trying!)

You need to know how many replication cycles (generations) it will take to generate the correct amount of bombs to destroy the LAMBCHOP. Write a function solution(M, F) where M and F are the number of Mach and Facula bombs needed. Return the fewest number of generations (as a string) that need to pass before you'll have the exact number of bombs necessary to destroy the LAMBCHOP, or the string "impossible" if this can't be done! M and F will be string representations of positive integers no larger than 10^50. For example, if M = "2" and F = "1", one generation would need to pass, so the solution would be "1". However, if M = "2" and F = "4", it would not be possible.

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
Input:
solution.solution('4', '7')
Output:
4

Input:
solution.solution('2', '1')
Output:
1

def solution(x, y):
    M, F = max(int(x), int(y)), min(int(x), int(y))
    res = 0
    while F > 0:
        res += M // F
        M, F = F, M % F
    if M != 1:
        return "impossible"
    return str(res - 1)

Foobar: Prepare the Bunnies' Escape

Gangbaolede Li — Sat, 25 Sep 2021 17:56:39 +0000

Prepare the Bunnies' Escape

You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny workers, but once they're free of the work duties the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.

You have maps of parts of the space station, each starting at a work area exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the station is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function solution(map) that generates the length of the shortest path from the station door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Languages

To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
Input:
solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])
Output:
7

Input:
solution.solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])
Output:
11

from collections import deque

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def bfs(row, col, m):
    rows = len(m)
    cols = len(m[0])
    arr = []
    for _ in range(rows):
        arr.append([None] * cols)
    arr[row][col] = 1
    queue = deque()
    queue.append((row, col))

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = (r + dr, c + dc)
            if 0 <= nr < rows and 0 <= nc < cols and arr[nr][nc] is None:
                arr[nr][nc] = arr[r][c] + 1
                if m[nr][nc] != 1:
                    queue.append((nr, nc))
    return arr


def solution(m):
    rows = len(m)
    cols = len(m[0])
    src = bfs(0, 0, m)
    dest = bfs(rows - 1, cols - 1, m)
    res = 20 * 20 + 1
    for i in range(rows):
        for j in range(cols):
            if src[i][j] and dest[i][j]:
                res = min(res, src[i][j] + dest[i][j] - 1)
                if res == rows + cols - 1:
                    return res
    return res

Foorbar: Find the Access Codes

Gangbaolede Li — Fri, 24 Sep 2021 05:03:54 +0000

Find the Access Codes

In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need access to it. But the only door leading to the LAMBCHOP chamber is secured with a unique lock system whose number of passcodes changes daily. Commander Lambda gets a report every day that includes the locks' access codes, but only the Commander knows how to figure out which of several lists contains the access codes. You need to find a way to determine which list contains the access codes once you're ready to go in.

Fortunately, now that you're Commander Lambda's personal assistant, Lambda has confided to you that all the access codes are "lucky triples" in order to make it easier to find them in the lists. A "lucky triple" is a tuple (x, y, z) where x divides y and y divides z, such as (1, 2, 4). With that information, you can figure out which list contains the number of access codes that matches the number of locks on the door when you're ready to go in (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky triple" access codes).

Write a function solution(l) that takes a list of positive integers l and counts the number of "lucky triples" of (li, lj, lk) where the list indices meet the requirement i < j < k. The length of l is between 2 and 2000 inclusive. The elements of l are between 1 and 999999 inclusive. The solution fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0.

For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the solution 3 total.

Input:
solution.solution([1, 2, 3, 4, 5, 6])
Output:
3

Input:
solution.solution([1, 1, 1])
Output:
1

Solution:

def solution(l):
    n = len(l)
    arr = [0] * n
    for i in range(n):
        for j in range(i+1, n):
            if l[j] % l[i] == 0:
                arr[i] += 1
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            if l[j] % l[i] == 0:
                res += arr[j]
    return res

Foobar: Please Pass the Coded Messages

Gangbaolede Li — Fri, 17 Sep 2021 08:06:42 +0000

You need to pass a message to the bunny workers, but to avoid detection, the code you agreed to use is... obscure, to say the least. The bunnies are given food on standard-issue plates that are stamped with the numbers 0-9 for easier sorting, and you need to combine sets of plates to create the numbers in the code. The signal that a number is part of the code is that it is divisible by 3. You can do smaller numbers like 15 and 45 easily, but bigger numbers like 144 and 414 are a little trickier. Write a program to help yourself quickly create large numbers for use in the code, given a limited number of plates to work with.

You have L, a list containing some digits (0 to 9). Write a function solution(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the solution. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

Input:
solution.solution([3, 1, 4, 1])
Output:
4311

Input:
solution.solution([3, 1, 4, 1, 5, 9])
Output:
94311

Solution:
python

def to_int(l):
    if not l:
        return 0
    return int("".join([str(d) for d in l]))

def solution(l):
    l = sorted(l, reverse=True)
    n = len(l)
    s = sum(l)
    if s % 3 == 0:
        # already divisible by 3 => use all digits
        return to_int(l)
    elif s % 3 == 1:
        # check backward if there is a digit that is 1 mod 3
        i = n - 1
        while i >= 0:
            if l[i] % 3 == 1:
                return to_int(l[:i] + l[i+1:])
            i -= 1
        # there must be two digits that each of them is 2 mod 3
        i = n - 1
        while i >= 0:
            if l[i] % 3 == 2:
                break
            i -= 1
        j = i - 1
        while j >= 0:
            if l[j] % 3 == 2:
                break
            j -= 1
        return to_int(l[:j] + l[j+1:i] + l[i+1:])
    else:
        # check backward if there is a digit that is 2 mod 3
        i = n - 1
        while i >= 0:
            if l[i] % 3 == 2:
                return to_int(l[:i] + l[i+1:])
            i -= 1
        # there must be two digits that each of them is 1 mod 3
        i = n - 1
        while i >= 0:
            if l[i] % 3 == 1:
                break
            i -= 1
        j = i - 1
        while j >= 0:
            if l[j] % 3 == 1:
                break
            j -= 1
        return to_int(l[:j] + l[j+1:i] + l[i+1:])

Foobar: I Love Lance & Janice

Gangbaolede Li — Sun, 12 Sep 2021 08:58:57 +0000

I Love Lance & Janice

You've caught two of your fellow minions passing coded notes back and forth -- while they're on duty, no less! Worse, you're pretty sure it's not job-related -- they're both huge fans of the space soap opera ""Lance & Janice"". You know how much Commander Lambda hates waste, so if you can prove that these minions are wasting time passing non-job-related notes, it'll put you that much closer to a promotion.

Fortunately for you, the minions aren't exactly advanced cryptographers. In their code, every lowercase letter [a..z] is replaced with the corresponding one in [z..a], while every other character (including uppercase letters and punctuation) is left untouched. That is, 'a' becomes 'z', 'b' becomes 'y', 'c' becomes 'x', etc. For instance, the word ""vmxibkgrlm"", when decoded, would become ""encryption"".

Write a function called solution(s) which takes in a string and returns the deciphered string so you can show the commander proof that these minions are talking about ""Lance & Janice"" instead of doing their jobs.

Test cases

-- Python cases --
Input:
solution.solution("wrw blf hvv ozhg mrtsg'h vkrhlwv?")
Output:
did you see last night's episode?

Input:
solution.solution("Yvzs! I xzm'g yvorvev Lzmxv olhg srh qly zg gsv xlolmb!!")
Output:
Yeah! I can't believe Lance lost his job at the colony!!

Python Solution

def decode(char):
    if char.islower():
        return chr(ord('a') + ord('z') - ord(char))
    return char

def solution(x):
    return "".join([decode(char) for char in x])

Foobar: Solar Doomsday

Gangbaolede Li — Sat, 04 Sep 2021 06:03:47 +0000

Solar Doomsday

Who would've guessed? Doomsday devices take a LOT of power. Commander Lambda wants to supplement the LAMBCHOP's quantum antimatter reactor core with solar arrays, and you've been tasked with setting up the solar panels.

Due to the nature of the space station's outer paneling, all of its solar panels must be squares. Fortunately, you have one very large and flat area of solar material, a pair of industrial-strength scissors, and enough MegaCorp Solar Tape(TM) to piece together any excess panel material into more squares. For example, if you had a total area of 12 square yards of solar material, you would be able to make one 3x3 square panel (with a total area of 9). That would leave 3 square yards, so you can turn those into three 1x1 square solar panels.

Write a function solution(area) that takes as its input a single unit of measure representing the total area of solar panels you have (between 1 and 1000000 inclusive) and returns a list of the areas of the largest squares you could make out of those panels, starting with the largest squares first. So, following the example above, solution(12) would return [9, 1, 1, 1].

Test cases:
Input: 15324
Output: [15129,169,25,1]

Input: 12
Output: [9,1,1,1]

Python

from math import sqrt

def solution(area):
    res = []
    while area > 0:
        square = int(sqrt(area))**2
        area -= square
        res.append(square)
    return res

Leetcode 56: Merge Intervals

Gangbaolede Li — Sun, 29 Aug 2021 03:44:10 +0000

Problem statement:
https://leetcode.com/problems/merge-intervals/

Straight forward solution is to sort the intervals by start time, iterate them and check if two intervals overlap. If they overlap we take the union of those intervals; Otherwise, we take both of them.

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # sort intervals by start time
        intervals.sort(key=lambda i: i[0])

        res = []
        res.append(intervals[0])
        n = len(intervals)
        for i in range(1, n):
            if res[-1][1] >= intervals[i][0]:
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])
        return res

Leetcode 1351: Count Negative Numbers in a Sorted Matrix

Gangbaolede Li — Sat, 28 Aug 2021 23:05:31 +0000

Problem statement:
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

Let's say we are at i-th row and j-th column. If grid[i][j] < 0, we can say that numbers below grid[i][j] are all negative and count them up. With this, we just start from top right corner to bottom left corner and count the negative numbers column by column.

Runtime: O(M+N)

Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        i = 0
        j = n - 1
        count = 0
        while i < m and j >= 0:
            if grid[i][j] < 0:
                count += m - i
                j = j - 1
            else:
                i = i + 1
        return count

C++

class Solution {
  public:
    int countNegatives(const vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int i = 0;
        int j = n - 1;
        int count = 0;
        while(i < m && j >= 0) {
            if(grid[i][j] < 0) {
                count += m - i;
                j = j - 1;
            } else {
                i = i + 1;
            }                
        }
        return count;
    }
};

Codeforces 4A: Watermelon

Gangbaolede Li — Fri, 27 Aug 2021 17:09:14 +0000

It's easy to see that odd number cannot be sum of two even numbers because sum of two even numbers is even.
On the other hand, even number can always be split into two positive even numbers except 2 because zero is not positive.

Problem statement:
https://codeforces.com/contest/4/problem/A

Python

def solve(weight):
    if weight > 2 and weight % 2 == 0:
        print("YES")
    else:
        print("NO")

w = int(input())
solve(w)

C++

#include <iostream>
using namespace std;

int main() {
    int w;
    cin >> w;
    if (w > 2 && w % 2 == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Let me know your thoughts in the comments section below. Thanks!

Hello World

Gangbaolede Li — Fri, 27 Aug 2021 16:36:48 +0000

print("Hello World!")