3 ms·

NP-Hard Pancake Game

ineedasername 5y 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()
ineedasername 5y 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.

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()

ineedasername 5y 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.