NP-Hard Pancake Game

https://replit.com/@ineedasername/NP-Hard-Pancake-Game#main.py

by ineedasername • 5 years ago

2 2 5 years ago

The link will take you to a replit... not sure how much traffic they will take. Here's the source below. Try no to judge too harshly, Python is where I glue things together, not a primary dev language for me and this was just a quick PoC before work.

Source:

  from random import randrange
  
  def play_game():
      stack = get_stack()
      stack_ar = get_layer_size_array(stack)
      ar = get_layer_size_array(stack)
      ar.sort()
      print("\n".join(stack))
      score = 0
      print("\nI was inspired by a recent HN post involving NP problems, and found an interesting one: Pancake flipping. Sort the stack! Select a layer. It will reverse that pancake with all above. Goal: smallest (top) to largest. Try not to judge too hard... I use python as \"glue\", not everyday, and threw this together in the morning before work\n")
      while ar != stack_ar:
        print (str(score) + " Is your current score (lower is better)\n")
        layer = input("Which layer would you like to flip? layer #: ")
        stack = flip(int(layer),stack)
        stack_ar = get_layer_size_array(stack)
        score = score + 1
      print("Congratulations! Your score for this round was: " + str(score) + "\ncan you beat that?")
  
  def get_pan(m_size = 43):
      pancake_char = '\u25ae' #character use for pancake shape e.g., ▮▮▮▮▮
      #pad_char = '-' #padding character
      size = randrange(1,m_size,2)
      pancake = pancake_char * size
      pancake = pancake.center(m_size, '~')
      return pancake
  
  def get_stack(st_size = 20):
      pan_stack = []
      for i in range(st_size):
          line_num = (str(i+1) + ') ').rjust(4)
          pan_stack.append(line_num + get_pan())
          pan_stack
      return pan_stack
  
  
  def flip(layer, stack):
      sub_stack = stack[0:layer]
      sub_stack.reverse()
      sub_stack.extend(stack[layer:])
      sub_stack = [e[4:] for e in sub_stack]
      sub_stack = [(str(i+1) + ') ').rjust(4) +sub_stack[i] for i in range(len(sub_stack))]
      print("\n".join(sub_stack))
      return sub_stack
  
  def get_layer_size_array(stack):
      ar = []
      for i in range(0,len(stack)):
          ar.append(stack[i].count('\u25ae'))
      return ar
  
  play_game()

ineedasername2• 5 years ago

Note: efficient algorithms (one by Bill Gates) estimate minimum flips to be between 1.07n and 1.64n.

On lucky random draws I've come close to 1.64n, never 1.07. but I also have been doing it by eyeing it up, I haven't tried following one of the efficient algorithms.

NP-Hard Pancake Game

Related Stories