Yesterday, I participated in a virtual event: Turing Jump Start for Python.
During the event it was proposed a coding puzzle, which the participants who wanted could try their hands at. I did try, and I'm posting my solutions here.
The puzzle was composed of two problems.
- In one problem it was asked that we calculate the nth element of, what was called in the puzzle, a “Gibonacci” sequence. This sequence was similar in formation with the Fibonacci sequence in the sense that both sequences were made by an arithmetic operation on the previous two numbers.
The difference between the two sequences is that while the most famous one uses addition to generate its numbers, the Gibonacci sequence uses subtraction. Other than that, they are identical in its formation.
- The other problem was to check if given a round of games everybody played against everybody. The problem was a little more complicated than that, but it's enough for now.
Here are my solutions:
Gibonacci Sequence
from typing import List
def solution(n: int, x: int, y: int) -> int:
#
# First let's deal with the obvious
#
if (n < 0):
raise Exception("Invalid argument")
if (n == 0):
return x
if (n == 1):
return y
#
# Calculate the third "gibonacci" number
#
n1 = y - x
n2 = n1 - y
if (n == 2):
return n1
#
# Follow the progression
#
# I'm sure that there might be a mathematical way to calculate
# the nth "gibonacci" number, just like there is a mathematical
# way to calculate the nth Fibonacci number.
#
# I just don't want to spend the time to develop such calculation.
#
# To with, though, the nth Fibonacci number is calculated by:
#
# math.floor ( ( ( (1 + math.sqrt(5)) / 2 ) ** n - ( (1 - math.sqrt(5)) / 2 ) ** n ) * ( 1 / math.sqrt(5) ) )
#
for n in range(n - 3):
n2 = n2 - n1
n1 = n2
return n2
if __name__ == '__main__':
n = int(input())
b = int(input())
d = int(input())
print(solution(n, b, d))
Player Pairs Problem
def solution(m: int, n: int, games) -> bool:
#
# If I understood the problem, games contains a list of lists.
#
# Each list in games represents one game, where the first
# half of the list is one team and the second half od the list
# is another team.
#
# For instance: [1, 2, 3, 4, 5, 6]
# one team <--|--> another team
#
# So I need to find if everybody played against everybody.
#
# On the second example [[1, 2, 3, 4], [4, 3, 1, 2]] = False
# I understand that the first game was players [1, 2] x players [3, 4]
# and the second game was players [4, 3] x players [1, 2], which
# means that it was the 'same' game, meaning there were no variaton of
# players.
#
# On the third example [[1, 2, 3, 4], [1, 3, 2, 4]] = True
# I understand that the first game was players [1, 2] x players [3, 4]
# and the second game was players [1, 3] x players [2, 4], which
# means that there were 'different' games.
#
# However, the problem asks to check "all pairs of players played
# against each other".
#
# Hold on, let me examine the second example again.
#
# We have for four players we have the following pairs:
# (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
#
# The first game on the second example is [1, 2] x [3, 4],
# which generates the pairs of players (1, 3) (1, 4) (2, 3) (2, 4)
#
# Meaning then that the round represented by the example generated
# only four pairs of the possible six. Therefore not everybody played
# aginst everybody.
#
# All right, I think I see it now.
#
#
# Generate the pair of players
#
pairs = {}
for a in range (1, m):
for b in range(a + 1, m + 1):
pairs[(a * 100000) + b] = 0
#
# Iterate through the games
#
k = int (m / 2)
for g in games:
#
# Mark the pairs of the game
#
i = int(0)
while (i < k):
j = k
while (j < m):
s = sorted({ g[i], g[j] })
pairs[(s[0] * 100000) + s[1]] = 1
j = j + 1
i = i + 1
#
# Check if there are any pair that didn't play
#
for p in pairs:
if (pairs[p] == 0):
return False
return True
if __name__ == "__main__":
m = int(input())
n = int(input())
mtx = [[int(val) for val in pair.split()] for pair in input().strip().split(',')]
output = solution(m, n, mtx)
if (optput == True):
print("true")
else:
print("false")
Edited to add:
After posting this solution, someone pointed to me that the Gibonacci function could be optimized. That the sequence was cyclic and therefore did not need to be calculated further than the cycle. As soon as I have a little time on my hands I'll update the code here.
Labels: coding puzzle, python, Turing
