Solve games in Countdown numbers game

countdown.py

from itertools import *

def program(ndigits):
	for i in range(2**ndigits):
		ones = 0
		zeros = 0
		valid = True # optimism
		instructions = "{:0{ndigits}b}".format(i, ndigits=ndigits)
		for j in instructions:
			if j=="1": ones += 1
			if j=="0": zeros += 1
			if zeros > ones:
				valid = False
				break
		if valid and ones==zeros: 
			yield "1"+instructions

def run(program,p,n,target):
	stack = []
	how = ""
	for instruction in program:
		if instruction=="1":
			stack.append(n[0])
			how += str(n[0])+" "
			n = n[1:]
		else:
			how += p[0]+" "
			a = stack.pop()
			b = stack.pop()
			if p[0]=="+": stack.append(b+a)
			if p[0]=="-": stack.append(b-a)
			if p[0]=="*": stack.append(b*a)
			if p[0]=="/": 
				if a==0 or b%a!=0: return None
				stack.append(b/a)
			p = p[1:]
		if stack[0]==target:
			return how
	if stack[0]==target:
		return how
	return None

def operators():
	for p1 in "+-*/":
		for p2 in "+-*/":
			for p3 in "+-*/":
				for p4 in "+-*/":
					for p5 in "+-*/":
						yield(p1+p2+p3+p4+p5)

def executePermutations(numbers, program, target):
	for p in operators():
		for n in permutations(numbers):
			how = run(program,p,n,target)
			if how:
				yield how

def main():
	numbers = [75,100,50,25,6,1]
	target = 997
	for b in program(10):
		for result in executePermutations(numbers, b, target):
			print(result)
			return

if __name__ == '__main__':
	main()