24 game/Solve: Difference between revisions
(→{{header|Tcl}}: Make the code only report the first solution by default) |
(→{{header|Python}}: Updated to also find solutions involving two sets of brackets) |
||
Line 15: | Line 15: | ||
brackets, (), show how to make an answer of 24. |
brackets, (), show how to make an answer of 24. |
||
An answer of "q" will quit the game. |
An answer of "q" will quit the game. |
||
An answer of "!" will generate a new set of four digits. |
An answer of "!" will generate a new set of four digits. |
||
An answer of " |
An answer of "!!" will ask you for a new set of four digits. |
||
An answer of "?" will compute an expression for the current digits. |
|||
Otherwise you are repeatedly asked for an expression until it evaluates to 24 |
Otherwise you are repeatedly asked for an expression until it evaluates to 24 |
||
Line 32: | Line 33: | ||
import random, ast, re |
import random, ast, re |
||
import sys |
import sys |
||
if sys.version_info[0] < 3: |
if sys.version_info[0] < 3: |
||
Line 39: | Line 39: | ||
else: |
else: |
||
from itertools import zip_longest |
from itertools import zip_longest |
||
def choose4(): |
def choose4(): |
||
'four random digits >0 as characters' |
'four random digits >0 as characters' |
||
return [str(random.randint(1,9)) for i in range(4)] |
return [str(random.randint(1,9)) for i in range(4)] |
||
def ask4(): |
|||
'get four random digits >0 from the plaayer' |
|||
digits = '' |
|||
while len(digits) != 4 or not all(d in '123456789' for d in digits): |
|||
digits = input('Enter the digits to solve for: ') |
|||
digits = ''.join(digits.strip().split()) |
|||
return list(digits) |
|||
def welcome(digits): |
def welcome(digits): |
||
Line 61: | Line 70: | ||
def solve(digits): |
def solve(digits): |
||
'''\ |
|||
>>> |
>>> for digits in '3246 4788 1111 123456 1127'.split(): |
||
⚫ | |||
⚫ | |||
Solution found: 2 + 3 * 6 + 4 |
Solution found: 2 + 3 * 6 + 4 |
||
'2 + 3 * 6 + 4' |
'2 + 3 * 6 + 4' |
||
⚫ | |||
Solution found: ( 4 + 7 - 8 ) * 8 |
Solution found: ( 4 + 7 - 8 ) * 8 |
||
'( 4 + 7 - 8 ) * 8' |
'( 4 + 7 - 8 ) * 8' |
||
>>> solve(list('3322')) |
|||
⚫ | |||
⚫ | |||
>>> solve(list('1111')) |
|||
No solution found for: 1 1 1 1 |
No solution found for: 1 1 1 1 |
||
'!' |
'!' |
||
>>> solve(list('123456')) |
|||
Solution found: 1 + 2 + 3 * ( 4 + 5 ) - 6 |
Solution found: 1 + 2 + 3 * ( 4 + 5 ) - 6 |
||
'1 + 2 + 3 * ( 4 + 5 ) - 6' |
'1 + 2 + 3 * ( 4 + 5 ) - 6' |
||
⚫ | |||
⚫ | |||
'( 1 + 2 ) * ( 1 + 7 )' |
|||
⚫ | |||
digilen = len(digits) |
digilen = len(digits) |
||
# length of an exp without brackets |
# length of an exp without brackets |
||
Line 86: | Line 94: | ||
opcomb = list(product('+-*/', repeat=digilen-1)) |
opcomb = list(product('+-*/', repeat=digilen-1)) |
||
# All the bracket insertion points: |
# All the bracket insertion points: |
||
brackets = [()] + [(x,y) |
brackets = ( [()] + [(x,y) |
||
for x in range(0, exprlen, 2) |
for x in range(0, exprlen, 2) |
||
for y in range(x+4, exprlen+2, 2) |
for y in range(x+4, exprlen+2, 2) |
||
if (x,y) != (0,exprlen+1)] |
if (x,y) != (0,exprlen+1)] |
||
+ [(0, 3+1, 4+2, 7+3)] ) # double brackets case |
|||
for d in digiperm: |
for d in digiperm: |
||
for ops in opcomb: |
for ops in opcomb: |
||
Line 95: | Line 104: | ||
for b in brackets: |
for b in brackets: |
||
exp = ex[::] |
exp = ex[::] |
||
for insertpoint, bracket in zip(b, '()'*(len(b)//2)): |
|||
exp.insert( |
exp.insert(insertpoint, bracket) |
||
exp.insert(b[1], ')') |
|||
txt = ''.join(exp) |
txt = ''.join(exp) |
||
try: |
try: |
||
Line 121: | Line 129: | ||
chk = check(answer, digits) |
chk = check(answer, digits) |
||
if answer == '?': |
if answer == '?': |
||
solve(digits) |
|||
answer = '!' |
|||
if answer.lower() == 'q': |
if answer.lower() == 'q': |
||
break |
break |
||
if answer == '!': |
if answer == '!': |
||
digits = choose4() |
digits = choose4() |
||
trial = 0 |
|||
print ("\nNew digits:", ' '.join(digits)) |
|||
continue |
|||
if answer == '!!': |
|||
digits = ask4() |
|||
trial = 0 |
|||
print ("\nNew digits:", ' '.join(digits)) |
|||
continue |
continue |
||
if not chk: |
if not chk: |
Revision as of 05:20, 4 November 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Write a function that given four digits subject to the rules of the 24 game, computes an expression to solve the game if possible.
Show examples of solutions generated by the function
Python
The function is called solve, and is integrated into the game player. The docstring of the solve function shows examples of its use when isolated at the Python command line. <lang Python>
The 24 Game Player
Given any four digits in the range 1 to 9, which may have repetitions, Using just the +, -, *, and / operators; and the possible use of brackets, (), show how to make an answer of 24.
An answer of "q" will quit the game. An answer of "!" will generate a new set of four digits. An answer of "!!" will ask you for a new set of four digits. An answer of "?" will compute an expression for the current digits. Otherwise you are repeatedly asked for an expression until it evaluates to 24
Note: you cannot form multiple digit numbers from the supplied digits, so an answer of 12+12 when given 1, 2, 2, and 1 would not be allowed.
from __future__ import division, print_function from itertools import permutations, combinations, product, \
chain
from pprint import pprint as pp import random, ast, re import sys
if sys.version_info[0] < 3:
input = raw_input from itertools import izip_longest as zip_longest
else:
from itertools import zip_longest
def choose4():
'four random digits >0 as characters' return [str(random.randint(1,9)) for i in range(4)]
def ask4():
'get four random digits >0 from the plaayer' digits = while len(digits) != 4 or not all(d in '123456789' for d in digits): digits = input('Enter the digits to solve for: ') digits = .join(digits.strip().split()) return list(digits)
def welcome(digits):
print (__doc__) print ("Your four digits: " + ' '.join(digits))
def check(answer, digits):
allowed = set('() +-*/\t'+.join(digits)) ok = all(ch in allowed for ch in answer) and \ all(digits.count(dig) == answer.count(dig) for dig in set(digits)) \ and not re.search('\d\d', answer) if ok: try: ast.parse(answer) except: ok = False return ok
def solve(digits):
\ >>> for digits in '3246 4788 1111 123456 1127'.split(): solve(list(digits))
Solution found: 2 + 3 * 6 + 4 '2 + 3 * 6 + 4' Solution found: ( 4 + 7 - 8 ) * 8 '( 4 + 7 - 8 ) * 8' No solution found for: 1 1 1 1 '!' Solution found: 1 + 2 + 3 * ( 4 + 5 ) - 6 '1 + 2 + 3 * ( 4 + 5 ) - 6' Solution found: ( 1 + 2 ) * ( 1 + 7 ) '( 1 + 2 ) * ( 1 + 7 )' >>> digilen = len(digits) # length of an exp without brackets exprlen = 2 * digilen - 1 # permute all the digits digiperm = sorted(set(permutations(digits))) # All the possible operator combinations opcomb = list(product('+-*/', repeat=digilen-1)) # All the bracket insertion points: brackets = ( [()] + [(x,y) for x in range(0, exprlen, 2) for y in range(x+4, exprlen+2, 2) if (x,y) != (0,exprlen+1)] + [(0, 3+1, 4+2, 7+3)] ) # double brackets case for d in digiperm: for ops in opcomb: ex = list(chain.from_iterable(zip_longest(d, ops, fillvalue=))) for b in brackets: exp = ex[::] for insertpoint, bracket in zip(b, '()'*(len(b)//2)): exp.insert(insertpoint, bracket) txt = .join(exp) try: num = eval(txt) except ZeroDivisionError: continue if num == 24: ans = ' '.join(exp).rstrip() print ("Solution found:",ans) return ans print ("No solution found for:", ' '.join(digits)) return '!'
def main():
digits = choose4() welcome(digits) trial = 0 answer = chk = ans = False while not (chk and ans == 24): trial +=1 answer = input("Expression %i: " % trial) chk = check(answer, digits) if answer == '?': solve(digits) answer = '!' if answer.lower() == 'q': break if answer == '!': digits = choose4() trial = 0 print ("\nNew digits:", ' '.join(digits)) continue if answer == '!!': digits = ask4() trial = 0 print ("\nNew digits:", ' '.join(digits)) continue if not chk: print ("The input '%s' was wonky!" % answer) else: ans = eval(answer) print (" = ", ans) if ans == 24: print ("Thats right!") print ("Thank you and goodbye")
main()</lang>
Sample Output
The 24 Game Player Given any four digits in the range 1 to 9, which may have repetitions, Using just the +, -, *, and / operators; and the possible use of brackets, (), show how to make an answer of 24. An answer of "q" will quit the game. An answer of "!" will generate a new set of four digits. An answer of "?" will compute an expression for the current digits. Otherwise you are repeatedly asked for an expression until it evaluates to 24 Note: you cannot form multiple digit numbers from the supplied digits, so an answer of 12+12 when given 1, 2, 2, and 1 would not be allowed. Your four digits: 6 7 9 5 Expression 1: ? Solution found: 6 - ( 5 - 7 ) * 9 Thank you and goodbye
Tcl
This is a complete Tcl script, intended to be invoked from the command line. <lang tcl># Encoding the various expression trees that are possible set patterns {
{((A x B) y C) z D} {(A x (B y C)) z D} {(A x B) y (C z D)} {A x ((B y C) z D)} {A x (B y (C z D))}
}
- Encoding the various permutations of digits
set permutations {
{A a B b C c D d} {A a B b C d D c} {A a B c C b D d} {A a B c C d D b} {A a B d C c D b} {A a B d C b D c} {A b B a C c D d} {A b B a C d D c} {A b B c C a D d} {A b B c C d D a} {A b B d C c D a} {A b B d C a D c} {A c B b C a D d} {A c B b C d D a} {A c B a C b D d} {A c B a C d D b} {A c B d C a D b} {A c B d C b D a} {A d B b C c D a} {A d B b C a D c} {A d B c C b D a} {A d B c C a D b} {A d B a C c D b} {A d B a C b D c}
} set stopAtFirst 1
proc findSolution {values} {
global patterns permutations stopAtFirst set found 0 # For each possible structure with numbers at the leaves... foreach pattern $patterns {
foreach permutation $permutations { set p [string map [subst { a [lindex $values 0].0 b [lindex $values 1].0 c [lindex $values 2].0 d [lindex $values 3].0 }] [string map $permutation $pattern]]
# For each possible structure with operators at the branches...
foreach x {+ - * /} { foreach y {+ - * /} { foreach z {+ - * /} { set e [string map [subst {x $x y $y z $z}] $p]
# Try to evaluate (div-zero is an issue!) and print if it is 24
catch { if {[expr $e] == 24.0} { puts [string map {.0 {}} $e]
if {$stopAtFirst} return
incr found } } } } } }
} if {!$found} {
puts "no solution possible"
} else {
puts "$found solutions total (may include duplicates)"
}
} findSolution $argv</lang> Demonstrating it in use:
$ tclsh8.4 24player.tcl 3 2 8 9 ((9 - 3) * 8) / 2