Practice makes you perfect, but learning the best practices from some experts may boost your coding performances.
This page contains the first three problems from the 2019 Reply Code Challenge - Teen Edition. Let’s take a look at them, but before...
Train with the 2019 Reply Code Challenge problems!
Get your own hands dirty and test your skills, trying out the problems of past editions in sandbox mode.
problem 1 _ Quantum Teleportation
Uncover the solution beyond the statement
The solution of the first problem is simple as it only requires implementing the simulation explained in the problem statement.
Given the initial position and the list of teleportation portals, we have to check the nearest portal according to the procedure detailed at each step. That is, the sum of the absolute differences between the two coordinates.
The only two things to watch out for are to implement the correct tie-breaker, in case distances are the same distances, and to remove a portal once it’s used.
Source code of a test case solution:
def solve_testcase(tc):
(X, Y, X0, Y0, N, points) = tc
MOD = 100003
IN = [points[i][:2] for i in range(N)] # Qubit position
OUT = [points[i][-2:] for i in range(N)] # Qubit destination
seen = [False for _ in range(N)] # Qubit remained
# Manhattan distance
def dist(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
# Nearest point and equal distance
def less(pos, a, b):
if dist(pos,a) < dist(pos, b):
return True
elif dist(pos,a) == dist(pos, b):
return a < b
return False
# total distance and actual position
tot = 0
pos = [X0, Y0]
for i in range(N):
# find nearest point
best = None
for p in range(N):
# If already seen, skip
if seen[p]:
continue
# If nearest, select this point
if best == None or less(pos, IN[p], IN[best]):
best = p
tot += dist(pos, IN[best]) # add travelled distance
pos = OUT[best] # teleport to position
seen[best] = True # mark as seen
return tot % MOD
problem 2 _ Riceboard
A little deeper mathematical knowledge for 3 different solutions of increasing difficulty
The second problem is more complicated and can be described simply by calculating the value of the sum:
S = (R0 + R1 + R2 + ... + RX-2 + RX-1) % M
Where R, M and X are given in input and, in particular, X = N2 is the number of cells in a chessboard of size N.
Case R = 2
This is the simplest case, if you know how binary numbers work. According to the binary system we know this important property:
2^0 + 2^1 + 2^2 + ... + 2^(N-1) + 2^N = 2^(N+1) - 1
Given this formula, it’s easy to find the value of S.
Source code to solve the first three levels:
def solve(io):
# read input
[R, N, M] = [int(x) for x in io.readline().strip().split()]
X = pow(N, 2)
return (pow(2,X)-1) % M
Case M prime and R any value
If you’re a good mathematician, you’ll have noticed the problem is actually the calculation of a geometric series. For this problem, a closed formula exists that can be used to find the solution:
S = (1 - R^X)/(1 - R)
Before this using simple formula, we have to pay attention because we’re looking for the values modulo M. As we’re working in modular arithmetic it’s not possible to compute the division in the standard way, but we need to find the multiplicative inverse of (1-R). In python, this can be done using the pow function.
Once we’ve found the multiplicative inverse, computing the value of S is straightforward.
Source code to solve also the 4th level:
def solve_testcase(t):
(R, N, M) = t
X = N**2
num = (pow(R, X, M) - 1) % M # numerator
den = (1-R)%M # denominator
den_inv = pow(den, -1, M) # inverse of denominator
return (num * den_inv) % M
Case M and R any value
For the general case where N, M and R can be any value, we need to work a little to arrive at an efficient solution. The value of S can be found by constructing its value step by step, using some simple mathematical properties.
In particular, the procedure is:
Find the values of R0, R2, R4, R8, R16 until not reaching the power of X. This operation requires only log(X) steps as we can calculate successive powers using previous values, like R16 = (R8)2
Find the values of (R0), (R0+R1), (R0+...+R3), (R0+...+R7), ... until not reaching the power of X. Even this operation requires only log(X) steps and can be calculated using previous values and the value of 1).
Example: (R0+...+R15) = (R0+...+R7) + R8(R0+...+R7) = (R0+...+R7)+(R8+...+R15)
Find the final value of S = (R0 + ... + RX-1) by using the values calculated in 1) and 2).
Example: S = (R0 + ... + R24) = (R0+...+R15) + R16(R0+...+R7) + R16R8(R0)
For the last steps, the values to sum can be found using the binary exponentiation techniques based on the binary decomposition of (X-1).
In this case, 25 = 11001 in base 2 = 2^0 + 2^3 + 2^4 = 16 + 8 + 1
Source code of a test-case solution:
def solve_testcase(t):
(R, N, M) = t
X = (N**2)
powr = [1, R] # 1, R^2, R^4, R^8, ...
sumr = [1, 1+R] # 1, 1+R, 1+R+R^2+R^3, ...
i = 1
# Compute values of powr and sumr
while i < X:
i *= 2
powr.append(powr[-1]*powr[-1] % M)
sumr.append((((1+powr[-1]) % M)*sumr[-1]) % M)
mul, S = 1, 0
b = bin(X)[2:]
# Exponentiation by squaring
for i in range(len(b)):
if b[i] == '0':
continue
i = len(b)-i-1
S = (S + ((mul*sumr[i]) % M)) % M
mul = (mul*powr[i+1]) % M
return S
problem 3 _ T9
Find the most common K passwords according to the probability matrix given by the input data
This problem can be solved using a dynamic programming approach: we can construct our solution starting from the right-most digit, adding a new character step by step.
We’ll start with an empty string. Each time a button is pressed we’ll going to push all its corresponding characters to the last available solution. At each step, we’ll use the probability matrix to find the most likely passwords by adding to the last passwords the new character’s probabilities.
Source code of a test case solution:
class Bucket:
def __init__(self, d, K):
self.K = K
self.buckets = [[] for _ in range(len(MAP[d]))]
def prepend_key(self, d, prob):
b = Bucket(d, self.K)
for i in range(len(MAP[d])):
c = MAP[d][i]
self.fill_bucket(b.buckets[i], c, prob)
return b
def fill_bucket(self, b, c, prob):
indicies = [0 for _ in range(len(self.buckets))]
while len(b) < self.K:
best_index = -1
best_value = -1
for i in range(len(self.buckets)):
if indicies[i] >= len(self.buckets[i]):
continue
suffix = self.buckets[i][indicies[i]]
value = prob[ord(c) - ord('A')][ord(suffix[1]
[0]) - ord('A')] + suffix[0]
if value > best_value:
best_index = i
best_value = value
if best_index < 0:
return
new_suffix = c + self.buckets[best_index][indicies[best_index]][1]
b.append([best_value, new_suffix])
indicies[best_index] += 1
def solve_testcase(t):
[L, K, T, S] = t
T2 = [[0 for _ in range(27)] for _ in range(27)]
for i in range(26):
for j in range(26):
T2[i][j] = T[i][j]
T = T2
keys = []
for s in S:
keys.append(ord(s) - ord('0'))
b = Bucket(keys[L-1], K)
for i in range(len(MAP[keys[L-1]])):
b.buckets[i].append([0, MAP[keys[L - 1]][i:i+1]])
for i in range(L-2, -1, -1):
b = b.prepend_key(keys[i], T)
b = b.prepend_key(0, T)
result = []
for s in b.buckets[0]:
result.append(str(s[1][1:]))
return str(result[K-1])