During an interview I was given the following problem:
From the following puzzle, what would the output of puzzle(power(2022, 100)) be?
function puzzle(N) {
A, B, C, D = 1, 1, 1, 1
.repeat N times {
X = D + 2 * C + 3 * B + 4 * A
a, b, c, d = b, c, d, x
}
return D % 10000000000
}
From looking at the puzzle and by implementing it on my language of choice, I found out that it forms some kind of Fibonacci sequence. However, the code didn't finish running so it was impossible to me to find the output. I answered that the code could be refactored as a sum of fibs to optimize the output but I wasn't able to do it, however, the interviewer said it was a correct reasoning in the right path (he gave me some more time to crack it but I simply failed).
Now, I'm still feeling curious about it, even after failing the interviewer. Could I get some insight?
edit: thanks to the accepted answer I hacked a solution in Python (apart from the one included in the answer update), here's the code if someone is curious:
#reimplemented in python because Ruby is a real pain to work with matrices
def matrix_pow(matrix, power, modulus):
# Initialize result to the identity matrix of the same size as matrix
result = [[int(i == j) for j in range(len(matrix))] for i in range(len(matrix))]
while power > 0:
# If the current bit of the exponent is 1, multiply result by matrix
if power % 2 == 1:
result = matrix_multiply(result, matrix, modulus)
# Square matrix and divide power by 2
matrix = matrix_multiply(matrix, matrix, modulus)
power //= 2
# Return the result
return result
# This function multiplies two matrices modulo a given modulus
def matrix_multiply(matrix1, matrix2, modulus):
# Initialize result to a matrix of the appropriate size filled with zeros
result = [[0] * len(matrix2[0]) for _ in range(len(matrix1))]
# Perform matrix multiplication
for i in range(len(matrix1)):
for j in range(len(matrix2[0])):
for k in range(len(matrix2)):
result[i][j] += matrix1[i][k] * matrix2[k][j]
result[i][j] %= modulus
# Return the result
return result
# This function solves the puzzle
def puzzle(n):
# Initialize matrix M
M = [[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[4, 3, 2, 1]]
# Calculate M^n modulo 10^10
M_pow = matrix_pow(M, n, 10**10)
# Initialize vector v
v = [1, 1, 1, 1]
# Multiply M^n by v to get the solution
result = matrix_multiply(M_pow, [[x] for x in v], 10**10)
# Return the element in the fourth row and first column of the result
return result[3][0]
print(puzzle(10))
# output 30520
print(puzzle(100))
# outputs 720820623
print(puzzle(2022**100))
# outputs 2436815984
I hope you know what matrices are and matrix multiplication
At all points the status of the puzzle can be written as a column vector like this:
[A]
[B]
[C]
[D]
After one step it can be written as:
[B] [0 1 0 0] [A]
[C] -- [0 0 1 0] \/ [B]
[D] -- [0 0 0 1] /\ [C]
[X] [4 3 2 1] [D]
We can write the right hand side as M * v where M is that 4x4 transition matrix, and v is the vertical vector.
After N steps we get M^N * v. We know our starting vector v. And we know how to pick the answer. We just need a good way to get M^N.
And for that, well, there is a trick. It isn't hard to work out the series M, M^2, M^4, M^8, .... And with that series and the base 2 representation of 2022^100 you can figure out the answer to the puzzle. Unfortunately the numbers will get very long. But if you do all calculations modulo 10000000000 (meaning you multiply, then take % 10000000000 to get the remainder), then they stay reasonable and you can generate the answer.
The connection with Fibonacci is that it is computed by a 2x2 transition matrix and you can to identical logic. But I doubt that there is a way to get from Fibonacci to this.
Incidentally I consider this a fun problem, but not a very good interview question. Because the arbitrary skill that it tests for is not very well correlated with most programming work that you might have to do.
Here is a Python version. I verified that it agrees with the naive approach for powers up to 100.
class ModuloValue:
def __init__ (self, n, m):
self.modulo = m
self.value = n % m
def __int__ (self):
return self.value
def __add__ (self, other):
return ModuloValue(self.value + int(other), self.modulo)
def __mul__ (self, other):
return ModuloValue(self.value * int(other), self.modulo)
def __str__ (self):
return str(self.value)
class Matrix:
def __init__ (self, rows):
self.rows = rows
def value (self, i, j):
return self.rows[i][j]
def __add__ (self, other):
rows1 = self.rows
rows2 = other.rows
rows_out = []
for i in range(len(rows1)):
row = []
for j in range(len(rows1[0])):
row.append(rows1[i][j] + rows2[i][j])
rows_out.append(row)
return Matrix(rows_out)
def __mul__ (self, other):
rows1 = self.rows
rows2 = other.rows
rows_out = []
for i in range(len(rows1)):
row = []
for k in range(len(rows2[0])):
value = rows1[i][0] * rows2[0][k]
for j in range(1, len(rows1[0])):
value = value + rows1[i][j] * rows2[j][k]
row.append(value)
rows_out.append(row)
return Matrix(rows_out)
def __str__ (self):
answer = '['
for row in self.rows:
answer += '\n [' + ', '.join((str(x) for x in row)) + ']'
return answer + '\n]'
def pow (self, n):
power = self
answer = None
while 0 < n:
if 1 == n % 2:
if answer is None:
answer = power
else:
answer = answer * power
power = power * power
n = n // 2
return answer
mod = 10000000000
rows = [
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[4, 3, 2, 1],
]
for i in range(len(rows)):
rows[i] = [ModuloValue(x, mod) for x in rows[i]]
m = Matrix(rows)
m_pow = m.pow(2022**100)
v = [[1], [1], [1], [1]]
print((m_pow * Matrix(v)).rows[3][0])