import functools
import time

import sets

# The encoding used is something I've seen referred to as Von Neuman indices
# Basically, an empty set is 0 and {a, b, c} is 2^a + 2^b + 2^c
# The numbers in the set are also encoded the same way
# For example:
#   13 = 2³ + 2² + 2⁰
# → {3, 2, 0}
#   3 = 2¹ + 2⁰
#   2 = 2¹
# → {{1, 0}, {1}, 0}
#   1 = 2⁰
# → {{{0}, 0}, {{0}}, 0}
# → {{{∅}, ∅}, {{∅}}, ∅}

empty = sets.set()

def I(x):
	"""Converts a number from set representation to an integer"""
	# Algorith works by recursively calling itself
	# I(∅) = 0
	# I({e₁, e₂, e₃, …}) = 2^I(e₁) + 2^I(e₂) + 2^I(e₃) + …
	# For example:
	#   I({{{∅}, ∅}, {{∅}}, ∅})
	# → 2^I({{∅}, ∅}) + 2^I({{∅}}) + 2^I(∅)
	# → 2^(2^I({∅}) + 2^I(∅)) + 2^2^I({∅}) + 2^0
	# → 2^(2^2^I(∅) + 2^0) + 2^2^2^I(∅) + 2^0
	# → 2^(2^2^0 + 2^0) + 2^2^2^0 + 2^0
	# → 2^(2^1 + 1) + 2^2^1 + 1
	# → 2^(2 + 1) + 2^2 + 1
	# → 2^3 + 2^2 + 1
	# → 8 + 4 + 1
	# → 13

	if I == empty:
		return 0
	else:
		return sum(2**I(i) for i in x)

def powers_of_two(x):
	"""Lists the powers of two the number is composed of"""
	assert type(x) == int

	# Look for a power of two bigger than the one we were given
	power = 0
	number = 1
	while number < x:
		number *= 2
		power += 1

	# Find all smaller powers of two
	powers = []
	while x > 0:
		if number <= x:
			powers.append(power)
			x -= number

		number //= 2
		power -= 1

	return powers

def J(x):
	"""Converts an integer into set representation"""
	powers = powers_of_two(x)
	return sets.set(J(i) for i in powers)

def lesser(x, y):
	only_x = x.difference(y)
	only_y = y.difference(x)

	if only_x is empty and only_y is not empty:
		return True
	elif only_y is empty:
		return False
	else:
		x_max_power = functools.reduce(lambda a, b: b if lesser(a,b) else a, only_x)
		y_max_power = functools.reduce(lambda a, b: b if lesser(a,b) else a, only_y)
		return lesser(x_max_power, y_max_power)

def lshift(x, y):
	return sets.set(add(i, y) for i in x)

def double(x):
	return lshift(x, J(1))

def rshift(x, y):
	return sets.set(sub(i, y) for i in x)

def add(x, y):
	only_x = x.difference(y)
	only_y = y.difference(x)
	one = only_x.union(only_y)
	both = x.intersection(y)

	if both is empty:
		return one
	else:
		return add(one, double(both))

def sub(x, y):
	assert not lesser(x, y)
	only_x = x.difference(y)
	only_y = y.difference(x)
	
	if only_y is empty:
		return only_x
	else:
		return sub(add(only_x, only_y), double(only_y))

def mul(x, y):
	total = J(0)
	for power in x:
		total = add(total, lshift(y, power))
	return total

def divmod(x, y):
	assert y is not empty
	powers = []
	shift_amount = J(0)
	shifted_divisor = y

	while lesser(shifted_divisor, x):
		shift_amount = add(shift_amount, J(1))
		shifted_divisor = double(shifted_divisor)

	remaining_dividend = x
	while True:
		if not lesser(remaining_dividend, shifted_divisor):
			powers.append(shift_amount)
			remaining_dividend = sub(remaining_dividend, shifted_divisor)

		if shift_amount is empty:
			break

		shift_amount = sub(shift_amount, J(1))
		shifted_divisor = rshift(shifted_divisor, J(1))

	return sets.set(powers), remaining_dividend

def fibonacci():
	a = J(0)
	b = J(1)

	yield a
	while True:
		yield b
		a, b = b, add(a, b)

def py_fibonacci():
	a = 0
	b = 1
	
	yield a
	while True:
		yield b
		a, b = b, a + b

def pyset_J(x):
	powers = powers_of_two(x)
	return frozenset(pyset_J(i) for i in powers)

def pyset_lesser(x, y):
	only_x = x.difference(y)
	only_y = y.difference(x)

	if only_x == frozenset() and only_y != frozenset():
		return True
	elif only_y == frozenset():
		return False
	else:
		x_max_power = functools.reduce(lambda a, b: b if pyset_lesser(a,b) else a, only_x)
		y_max_power = functools.reduce(lambda a, b: b if pyset_lesser(a,b) else a, only_y)
		return pyset_lesser(x_max_power, y_max_power)

def pyset_lshift(x, y):
	return frozenset(pyset_add(i, y) for i in x)

def pyset_double(x):
	return pyset_lshift(x, pyset_J(1))

def pyset_add(x, y):
	only_x = x.difference(y)
	only_y = y.difference(x)
	one = only_x.union(only_y)
	both = x.intersection(y)

	if both == frozenset():
		return one
	else:
		return pyset_add(one, pyset_double(both))

def pyset_fibonacci():
	a = pyset_J(0)
	b = pyset_J(1)

	yield a
	while True:
		yield b
		a, b = b, pyset_add(a, b)

if __name__ == '__main__':
	start_time = time.monotonic()
	limit = J(2**128)
	for number in fibonacci():
		if lesser(limit, number):
			break
		#print(I(number), tuple(map(I, number)), str(number))
	print(time.monotonic() - start_time)

	start_time = time.monotonic()
	limit = pyset_J(2**128)
	for number in pyset_fibonacci():
		if pyset_lesser(limit, number):
			break
	print(time.monotonic() - start_time)

	start_time = time.monotonic()
	limit = 2**128
	for number in py_fibonacci():
		if limit < number:
			break
	print(time.monotonic() - start_time)