Google Code Jam 2022- Qualification Round

Here’s a quick walkthrough on the 3/5 questions I was able to solve for the qualification round of this year’s Google Code Jam.

Question 1- Punched Cards

Given a number of rows and a number of columns, print a matrix according to the following rules:
Similar to an R×C matrix without the top-left cell, it has (R⋅C)−1 cells in total. Each cell is drawn in ASCII art as a period (.) surrounded by dashes (-) above and below, pipes (|) to the left and right, and plus signs (+) for each corner. Adjacent cells share the common characters in the border. Periods (.) are used to align the cells in the top row.

Examples:

R = 3, C = 4

..+-+-+-+
..|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+

R = 2, C = 3

..+-+-+
..|.|.|
+-+-+-+
|.|.|.|
+-+-+-+

Logic: Make the top border, make the first row with the first pipe (|) replaced with a period (.), make the remaining rows by column width, make a row separator with the +- pattern. Print out accordingly.

Code:

# top border
tb = ['.', '.']
for i in range(c - 1):
    tb.append("+-")
tb.append("+")
# dots
row = []
for i in range(c):
    row.append('|.')
row.append('|')
# fist row
fr = ['..'] + row[1:]
# row sep
rs = []
for i in range(c):
    rs.append('+-')
rs.append('+')
res = [''.join(tb), ''.join(fr)]
for i in range(r - 1):
    res.append(''.join(rs))
    res.append(''.join(row))
res.append(''.join(rs))
for item in res:
    print(item)

Question 2- 3D Printing

Given 3 printers with 4 cartridges of the same color ink in each printer (not all having the same amount of ink), determine how much ink is needed (if it is possible) to print a logo according to the following rules:

• The logo must have a total of 10⁶ units of ink
• The amount of any color can only be used if all 3 printers has enough ink for that color. So if 2 printers have 10 units of red but one printer has 3 units of red, only 3 units of red can be used from each printer
• If the print is not possible, print IMPOSSIBLE

Many solutions can be returned for this problem- all are accepted.

Examples:

Given the following units of ink by printer:

Printer 1: 300000 200000 300000 500000
Printer 2: 300000 200000 500000 300000
Printer 3: 300000 500000 300000 200000

One solution is:

300000 200000 300000 200000

Logic: Find the minimum color available by printer, if the sum of the minimums is < 10⁶, there is no solution. Iterate by each minimum found, reducing the need of each color until 10⁶ is reached exactly.

Code:

Given printers a, b, c:

cy = min(a[0], b[0], c[0])
m = min(a[1], b[1], c[1])
y = min(a[2], b[2], c[2])
k = min(a[3], b[3], c[3])
if cy + m + y + k < 1000000:
    print("IMPOSSIBLE")
else:
    total = cy + m + y + k
    diff = total - 1000000
# cy
if diff > 0:
    if diff > cy:
        diff -= cy
        cy = 0
    else:
        cy -= diff
        diff = 0
# m
if diff > 0:
    if diff > m:
        diff -= m
        m = 0
    else:
        m -= diff
        diff = 0
# y
if diff > 0:
    if diff > y:
        diff -= y
        y = 0
    else:
        y -= diff
        diff = 0
# k
if diff > 0:
    if diff > k:
        diff -= k
        k = 0
    else:
        k -= diff
        diff = 0

Question 3- d1000000

Given a collection of dice of varying number of faces (4 ≤ number of faces ≤ 10⁶), choose as many dice as necessary to make the longest straight possible.

Straight: A straight of length ℓ starting at x is the list of integers x, x+1, … ,x+(ℓ−1).

Example:

Given the following dice:

5 4 5 4 4 4

The longest straight that can be made is

1 2 3 4 5

Because none of the dice can roll a 6

Logic: The intuitive solution here is to sort and iterate through the dice until you reach a die (or the end), but this is not optimal as it takes O(nlog(n)). However, when we break down the problem to its most basic piece- we need to find the first minimum … then the second minimum … and so on. We quickly notice a min heap will solve our problem:

from heapq import heapify, heappush, heappop
heap = []
heapify(heap)
for di in dice:
    heappush(heap, di)
l = 0
while heap:
    k = heappop(heap)
if l < k:
    l += 1

Me

As always, thank you for reading and I hope you learned something useful! Feel free to check out my GitHub and connect with me on LinkedIn. Thank you for reading!