import random

RAIKOU_START = 42
ENTEI_START = 37

# Burned tower cannot match any of the routes
PLAYER_START = 0

NEXT_ROUTES = {
  29: [30, 46],
  30: [29, 31],
  31: [30, 32, 36],
  32: [36, 31, 33],
  33: [32, 34],
  34: [33, 35],
  35: [34, 36],
  36: [35, 31, 32, 37],
  37: [36, 38, 42],
  38: [37, 39, 42],
  39: [38],
  42: [43, 44, 37, 38],
  43: [42, 44],
  44: [42, 43, 45],
  45: [44, 46],
  46: [45, 29],
}
ALL_ROUTES = list(NEXT_ROUTES)

def newRandomRoute(playerRoute):
  newRoute = random.sample(ALL_ROUTES, 1)[0]
  while newRoute == playerRoute:
    newRoute = random.sample(ALL_ROUTES, 1)[0]
  return newRoute

def chooseNextRoute(route, playerRoute, lastPlayerRoute):
  possibleRoutes = NEXT_ROUTES[route]
  while True:
    a = random.randrange(256)
    a &= 0b00011111
    if a == 0:
      return newRandomRoute(playerRoute)
    a &= 0b11
    if a >= len(possibleRoutes):
      continue
    newRoute = possibleRoutes[a]
    if newRoute == lastPlayerRoute:
      continue
    return newRoute

def odds(path, nSamples):
  successes = [0, 0]

  for i in range(nSamples):
    routes = [RAIKOU_START, ENTEI_START]
    lastPlayerRoute = PLAYER_START
    for x in path:
      routes = [chooseNextRoute(route, x, lastPlayerRoute) for route in routes]
      lastPlayerRoute = x
    if path[-1] == routes[0]:
      successes[0] += 1
    if path[-1] == routes[1]:
      successes[1] += 1
  return [float(x) / nSamples for x in successes]

def main():
  random.seed()
  print('Burned tower B1 -> Ekruteak -> Route 37')
  print(odds([0, 37], 100000))
  
  print('Burned tower B1 -> Ekruteak -> Gate -> Route 38')
  print(odds([0, 0, 38], 100000))

  print('Burned tower B1 -> Burned tower F1 -> Ekruteak -> Route 37')
  print(odds([0, 0, 37], 100000))
  print('Burned tower B1 -> Burned tower F1 -> Ekruteak -> Gate -> Route 38')
  print(odds([0, 0, 0, 38], 100000))

if __name__ == '__main__':
  main()