#!/usr/bin/env python3
from heapq import *

start = '111010100011101100101'
start = tuple([int(c) for c in start])
goal = tuple([1] * len(start))

def make_neighbors(node):
  l = len(node)
  for i in range(l):
    neighbor = list(node)
    def toggle(i):
      neighbor[i] = 1 if neighbor[i] == 0 else 0
    for j in range(-1, 2):
      idx = i + j
      if idx >= 0 and idx < l:
        toggle(idx)
    yield tuple(neighbor)

def distance(node, goal):
  d = 0
  for i in range(len(node)):
    if node[i] != goal[i]:
      d += 1
  return d

def reconstruct_path(came_from, current_node):
  if current_node in came_from:
    p = reconstruct_path(came_from, came_from[current_node])
    return p + [current_node]
  return [current_node]

def a_star():
  open_set = set()
  open_set.add(start)
  closed_set = set()
  came_from = {}
  g = {start: 0}
  h = {start: distance(start, goal)}
  # f = {start: 0}
  f = []
  heappush(f, (0, start))
  while open_set:
    _, x = heappop(f)
    if x not in open_set:
      continue
    # x = min(open_set, key=lambda n: f[n])
    if x == goal:
      return reconstruct_path(came_from, goal)
    print(x, len(open_set), len(closed_set), _)
    open_set.remove(x)
    closed_set.add(x)
    for y in make_neighbors(x):
      if y in closed_set:
        continue
      t_g = g[x] + distance(x, y)
      better = False
      if y not in open_set:
        better = True
      elif t_g < g[y]:
        better = True
      if better:
        came_from[y] = x
        g[y] = t_g
        h[y] = distance(y, goal)
        heappush(f, (g[y] + h[y], y))
        # f[y] = g[y] + h[y]
        open_set.add(y)
  return None


if __name__ == '__main__':
  for i, path in enumerate(a_star()):
    print(i, ''.join([str(i) for i in path]))