numoeba.py

import sys
import math
# 再帰の上限の変更
#sys.setrecursionlimit(10000)

class Cell:
	def __init__(self, val):
		self.val = val
		self.link = []

	def calc(self):
		old_val = self.val
		tmp = self.val * 3 + 1
		result = None
		while tmp % 2 == 0:
			tmp //= 2
		if tmp >= 12345678:
			tmp -= 12345678
		self.val = tmp

		del_list = []
		for index,item in enumerate(self.link):
			child = item.calc()
			if child != None:
				del_list.append([index, child])
		if not self.is_dead() and old_val < tmp and len(self.link) == 0:
			new_val = math.ceil((tmp + 1) / 2)
			if new_val % 2 == 0:
				new_val += 1
			self.link.append(Cell(new_val))
		
		leng = len(self.link)
		for del_item in reversed(del_list):
			self.link.pop(del_item[0])
			if del_item[1] != False:
				self.link.append(del_item[1])

		if self.is_dead():
			if leng == 1 and len(self.link) == 1:
				result = self.link[0]
			else:
				self.link[:] = []
				result = False

		return result

	def output(self, no_cl = False):
		sys.stdout.write(str(self.val))
		link_len = len(self.link)
		if link_len > 0:
			sys.stdout.write('[')
			for index,item in enumerate(self.link):
				item.output(True)
				if link_len - 1 != index:
					sys.stdout.write(',')
			sys.stdout.write(']')
		if not no_cl:
			print('')
		return

	def is_dead(self):
		return self.val == 1

	def find_max(self):
		selected = [[self.val, -1]]
		for index,child in enumerate(self.link):
			candidate = child.find_max()
			if candidate[0][0] > selected[0][0]:
				selected = candidate
				selected.insert(0, [candidate[0][0], index])
		return selected

	def find_value(self, value, result):
		if self.val == value:
			result.append(self)
		if len(self.link) != 0:
			for item in self.link:
				item.find_value(value, result)
		return result

	def change_leader(self):
		if self.is_dead():
			return self
		target = self
		to_leader = self.find_max()
		max_values = self.find_value(to_leader[0][0], [])
		if len(max_values) <= 1:
			for _, index in to_leader:
				if index != -1:
					target.link[index].link.append(target)
					next_target = target.link[index]
					del(target.link[index])
					target = next_target
			
			new_val = (target.val + 1) // 2
			if new_val % 2 == 0:
				new_val -= 1
			target.link.append(Cell(new_val))
		return target

	def clock(self):
		self.calc()
		return self.change_leader() 

if len(sys.argv) <= 1:
	exit()
arg = int(sys.argv[1])
#arg = 6
leader = Cell(arg)
i = 1

while not leader.is_dead():
	sys.stdout.write(str(i)+':')
	leader.output()
	#input()
	i += 1
	leader = leader.clock()
print('end')