Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Speedy category for Number Guess by coells
# extended GCD
def egcd(a, b):
if a == 0: return (b, 0, 1)
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
# solve system of two congruences
def cong(r1, d1, r2, d2):
return r1 + d1 * (r2 - r1) * (egcd(d1, d2)[1] % d2), d1 * d2
# find number using CRT
def checkio(attempts):
# find optimal modulus
if len(attempts) < 3:
for i in [9, 8, 7, 5]:
if all([egcd(i,d)[0] == 1 for r,d in attempts]):
return [i, 99]
# solve congruences
(r1, d1), (r2, d2), (r3, d3) = attempts[0], attempts[1], attempts[2]
r4, d4 = cong(r1, d1, r2, d2)
r5, d5 = cong(r4, d4, r3, d3)
return [2, r5 % d5]
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
MAX_ATTEMPT = 8
def initial_referee(data):
data["attempt_count"] = 0
data["guess"] = 0
return data
def check_solution(func, goal, initial):
prev_steps = [initial]
for attempt in range(MAX_ATTEMPT):
divisor, guess = func(prev_steps[:])
if guess == goal:
return True
if divisor <= 1 or divisor > 10:
print("You gave wrong divisor range.")
return False
if guess < 1 or guess > 100:
print("You gave wrong guess number range.")
return False
prev_steps.append((goal % divisor, divisor))
print("Too many attempts.")
return False
assert check_solution(checkio, 47, (2, 5)), "1st example"
assert check_solution(checkio, 94, (3, 7)), "1st example"
assert check_solution(checkio, 52, (0, 2)), "1st example"
April 1, 2014
Comments:
