w****w 发帖数: 521 | 1 跟儿子一起学Python,发现它表达力很强,很适合算24点这样的程序。网上搜了一下,
没发现一个像样的逻辑清晰,简洁,充分利用Python语言特点的24点程序。我习惯了过
程式,想学点函数式编程的实际运用,希望这里碰到高手。
要求:
写一个函数solve(lst,target,all)
lst是自然数列表,可以超过4。
target是24,也可以是其他数。
运算是加减乘除,如能加指数对数等则更好。
如果all是True,打出所有解答,否则打一个就够了。
程序行数最好不要超过50行,不然直接从C#/java翻过来没意思。
测试:
solve([2,3,4,5],24,True)
solve([2,5,7,11,13],19,True)
solve([1,2,3,4,5,6,7,8,9,10,11,12],37,False) | l*******G 发帖数: 1191 | 2 expression = list[1] op[1] list[2] .....list[i] op[i] list[i+1] ...list[n-
1]op[n-1] list[n]
where list[1] ... list[n] are any permutation of list
op[1] ... op[n-1] are any of + - * /
evaluate all possibilities of expression by putting expression in a string
and return
(eval(expression_string)==24)
e.g. expression_string='2*4*3*1'
eval(expression_string)==24 | l*******G 发帖数: 1191 | 3 #!/usr/bin/python
def permu(xs):
if xs:
r , h = [],[]
for x in xs:
if x not in h:
ts = xs[:]; ts.remove(x)
for p in permu(ts):
r.append([x]+p)
h.append(x)
return r
else:
return [[]]
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
def solve(mylist,target,all):
#Howto : solve([1,2,3,4],24,True)
listlength=len(mylist);
ops=product('+-*/',repeat=listlength-1);
m=map(str,ops);
listpermu=permu(mylist);
lengthpermu=len(listpermu);
for j in range(0,lengthpermu):
for i in range(0,len(m)):
op1d=m[i][2::5];
nop=len(op1d);
expr="";
for k in range(0,nop):
expr=expr+(str(listpermu[j][k]))+'.';
expr=expr+(op1d[k]);
expr=expr+str(listpermu[j][listlength-1])+'.';
good=(eval(expr)+0.0==target);
if all:
if good:
print expr;
else :
if good:
print expr;
return
#test 1
#solve([1,2,3,4],24,True);
#test 2
solve([1,2,3,4],24,False);
#test 3
solve([2,4,6,8],24,False); | w****w 发帖数: 521 | 4 这里有没有投票功能?
下面这几个方面1-5分:
1。正确性
2。可读性
3。易维护,debug
4。可扩充性 (加算子**,log ...)
5。运行效率(时间/空间)
如认为哪里可以改进,欢迎改进版。 | w****w 发帖数: 521 | | h***s 发帖数: 1716 | 6 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的
多。
其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能
力,就是函数式编程的核心。所以换到haskell了。。。
【在 w****w 的大作中提到】 : 这里用python的不多?
| a********x 发帖数: 1502 | 7 最近在学haskell,这个monad transformer真是brain torting啊
【在 h***s 的大作中提到】 : 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的 : 多。 : 其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能 : 力,就是函数式编程的核心。所以换到haskell了。。。
| h***s 发帖数: 1716 | 8 呵呵,Monad就是折磨脑子的,原因就是把数学里抽象的那一面给整进来了。我的经验
是,先别去化时间钻抽象的那一面,把monad当作定义好了interface的container看待
,map/filter的应用和其他container“一样”看待。
【在 a********x 的大作中提到】 : 最近在学haskell,这个monad transformer真是brain torting啊
| w****w 发帖数: 521 | 9 搞了两个礼拜,对python有点感觉了。
import math
_expr=lambda x,y,z:"(%s%s%s)"%(x,y,z)
_plus=lambda x,y: (x[0]+y[0],_expr(x[1],"+",y[1]))
_minus=lambda x,y: (x[0]-y[0],_expr(x[1],"-",y[1]))
_rminus=lambda x,y: _minus(y,x)
_mul=lambda x,y: (x[0]*y[0],_expr(x[1],"*",y[1]))
_div=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]/y[0],_expr(x[1],"/",y[1]))
_rdiv=lambda x,y: _div(y,x)
_mod=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]%y[0],"mod(%s,%s)"%(x[1],y[
1]))
_rmod=lambda x,y: _mod(y,x)
def _power(x,y):
try: return (x[0]**y[0],_expr(x[1],"**",y[1]))
except: return (0,"err")
_pow=lambda x,y: _power(x,y)
_rpow=lambda x,y: _power(y,x)
def _logarithm(x,y):
try: return (math.log(x[0],y[0]),"log(%s,%s)"%(x[1],y[1]))
except: return (0,"err")
_log=lambda x,y: _logarithm(x,y)
_rlog=lambda x,y: _logarithm(y,x)
def _pick2combination(base,num):
if num<2:return
for x in _pick2combination(base+1,num-1): yield x
for x in range(1,num): yield (base,base+x)
class Math24(object):
def __init__(self,level=1):
self.ops=[_plus,_minus,_rminus,_mul,_div,_rdiv]
if level>=2: self.ops+=[_log,_rlog]
if level>=3: self.ops+=[_pow,_rpow]
if level>=4: self.ops+=[_mod,_rmod]
def _eval(self,lst):
if len(lst)==1: yield lst[0]
for idx in _pick2combination(0,len(lst)):
nl=lst[:]
u,v=nl.pop(idx[1]),nl.pop(idx[0])
for op in self.ops:
nv=op(u,v)
if nv[1]!="err":
for x in self._eval(nl+[nv]): yield x
def solve(self,lst,target):
for y in self._eval([(float(x),str(x)) for x in lst]):
if abs(y[0]-target)<1.0e-9: yield y[1]
if __name__ == '__main__':
for x in Math24(2).solve([2,3,27,10],24): print x | w****w 发帖数: 521 | 10 haskell太不同了,找个人来没法train。
【在 h***s 的大作中提到】 : 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的 : 多。 : 其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能 : 力,就是函数式编程的核心。所以换到haskell了。。。
| | | A*********n 发帖数: 158 | 11 赞,最近在学haskell,来学习下
【在 h***s 的大作中提到】 : 呵呵,Monad就是折磨脑子的,原因就是把数学里抽象的那一面给整进来了。我的经验 : 是,先别去化时间钻抽象的那一面,把monad当作定义好了interface的container看待 : ,map/filter的应用和其他container“一样”看待。
| h***s 发帖数: 1716 | 12 下面是haskell的写法 - 我只想了个简单的算法,作了简单的过滤,还可能有很多重
复的答案表达,这个可以在算法上进一步优化细调,就没搞了。简单的测试可了。如果
用GHC编译运行如下:
> ghc -O3 solve.hs
....
> solve
-------------------------
import Data.List
import System.IO
opBoxes = [((+), "+"), ((-), "-"), ((*), "*"), ((divi), "/")]
divi x y = round $ toRational(x) / toRational(y)
divisible x y = case y of 0 -> False
y -> mod (abs x) (abs y) == 0
runOp opBox ((x1,s1):(x2,s2):xs) = ((fst opBox x1 x2), ss):xs
where ss = showSolution (snd opBox) s1 s2
showSolution opStr s1 s2
| opStr=="+" || opStr=="*" = showWrapUp opStr (min s1 s2) (max s1 s2)
| otherwise = showWrapUp opStr s1 s2
showWrapUp opStr sx sy = "(" ++ sx ++ opStr ++ sy ++ ")"
initializeProblem [] = []
initializeProblem (x:xs) = (x, show x):initializeProblem xs
unDuplicatedPerm :: Eq a => [a] -> [[a]]
unDuplicatedPerm = Data.List.nub . Data.List.permutations
oneStepMap xs@((x1,s1):(x2,s2):ys)
= map (\x -> runOp x xs) $ oneStepOps x1 x2
oneStepOps x1 x2 = if (divisible x1 x2) then opBoxes
else
(init opBoxes)
completeMap xs@(x:ys)
| length x == 1 = xs
| otherwise = completeMap (xs >>= unDuplicatedPerm >>= oneStepMap)
solve xs target all =
if (null zs) then print " No Solution Found!"
else if all then mapM_ print zs
else mapM_ print $ head zs
where ys = [initializeProblem xs]
zs = showResult $ nub $
filter (\y -> fst (head y) == target) (completeMap ys)
showResult xs
= map (\x -> let s=(head x) in snd s ++ "=" ++ show (fst s)) xs
main = do
solve [2,3,27,10] 24 True
-- solve [1,2,7,13] 24 True
【在 w****w 的大作中提到】 : haskell太不同了,找个人来没法train。
| h***s 发帖数: 1716 | 13 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好
了,我不费劲了。
【在 A*********n 的大作中提到】 : 赞,最近在学haskell,来学习下
| A*********n 发帖数: 158 | 14 ghc 还是认出来了
【在 h***s 的大作中提到】 : 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好 : 了,我不费劲了。
| j*a 发帖数: 14423 | 15 可以贴pastebin去
【在 h***s 的大作中提到】 : 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好 : 了,我不费劲了。
| h***s 发帖数: 1716 | 16 haskell spec只要求你合理的空格就行了,而求haskell的函数特点是短而一般化,不
需要太多行,所以一般小的对不齐不会影响代码的正确性。
【在 A*********n 的大作中提到】 : ghc 还是认出来了
| w****w 发帖数: 521 | 17 haskell里list的evaluation都是lazy的吗? | h***s 发帖数: 1716 | 18 忘了说了,这段代码可以解任意个整数的情况,比如:[1,2,3,4,5,6,7 。。]
,不限于24点,就是LZ的原始问题。当然这只是逻辑算法和原理上来说,至于bug,就
不负责了。。哈!只要算法允许,haskell表达总是可以做到更简洁,这个负责是没问
题的。
当然我喜欢haskell,只是个人观点而已。。
【在 h***s 的大作中提到】 : 下面是haskell的写法 - 我只想了个简单的算法,作了简单的过滤,还可能有很多重 : 复的答案表达,这个可以在算法上进一步优化细调,就没搞了。简单的测试可了。如果 : 用GHC编译运行如下: : > ghc -O3 solve.hs : .... : > solve : ------------------------- : import Data.List : import System.IO : opBoxes = [((+), "+"), ((-), "-"), ((*), "*"), ((divi), "/")]
| h***s 发帖数: 1716 | 19 对,语言的纯函数性和这个有内在的关联。
比如,你给一个有很大解案空间的问题,你总是能在线地得到当前的答案子集,如果你
想刷新IO缓冲,就能“实时”看到最新结果。。。我唰唰!
【在 w****w 的大作中提到】 : haskell里list的evaluation都是lazy的吗?
| w****w 发帖数: 521 | 20 这个python不如,还得另写generator.
【在 h***s 的大作中提到】 : 对,语言的纯函数性和这个有内在的关联。 : 比如,你给一个有很大解案空间的问题,你总是能在线地得到当前的答案子集,如果你 : 想刷新IO缓冲,就能“实时”看到最新结果。。。我唰唰!
| | | a*******e 发帖数: 14 | 21 写了个 Common Lisp 的解法,就十几行(Lisp 算子有联结到对应说明,很好理解):
http://paste.lisp.org/+2V0T
(defun twenty-four (numbers &optional (target 24) all)
"Show arithmetic expression(s), composed of the given NUMBERS and the
four basic arithmetic operators, that evaluates to the TARGET number."
(labels ((fa (x)
(if (cdr x)
(loop for (i . u) on x thereis (fb i u p) collect i into p)
(and (= target (caar x)) (print (cdar x)) (not all))))
(fb (i u p)
(loop for (j . v) on u thereis (fc i j (append v q p))
collect j into q))
(fc (i j x)
(or (and (/= 0 (car j)) (fd '/ i j x))
(and (/= 0 (car i)) (fd '/ j i x))
(fd '+ i j x) (fd '* i j x) (fd '- i j x) (fd '- j i x)))
(fd (o i j x)
(fa `((,(funcall o (car i) (car j)) ,o ,(cdr i) ,(cdr j)) ,@x))
))
(fa (map 'list (lambda (x) (cons x x)) numbers))))
;;; Examples:
;;
;; CL-USER> (twenty-four '(2 3 7 10))
;; (+ (- (* 2 10) 3) 7)
;; CL-USER> (twenty-four '(2 3 7 10) 24 'show-all-solutions)
;; (+ (- (* 2 10) 3) 7)
;; (- 7 (- 3 (* 2 10)))
;; (- (+ (* 2 10) 7) 3)
;; (- (* 2 10) (- 3 7))
;; (+ (- 7 3) (* 2 10))
;; (- (* 10 2) (- 3 7))
;; (+ (* 10 2) (- 7 3))
;; (/ (+ (* 7 10) 2) 3) | h***s 发帖数: 1716 | 22 有意思.
看有没有C/C++, Java, Perl的版本能写成十几行的... 哦, 对了, 还有javascript,
visual basic, C#/F#的干活, 哈!
p)
【在 a*******e 的大作中提到】 : 写了个 Common Lisp 的解法,就十几行(Lisp 算子有联结到对应说明,很好理解): : http://paste.lisp.org/+2V0T : (defun twenty-four (numbers &optional (target 24) all) : "Show arithmetic expression(s), composed of the given NUMBERS and the : four basic arithmetic operators, that evaluates to the TARGET number." : (labels ((fa (x) : (if (cdr x) : (loop for (i . u) on x thereis (fb i u p) collect i into p) : (and (= target (caar x)) (print (cdar x)) (not all)))) : (fb (i u p)
| b*******s 发帖数: 5216 | 23 c++更快,先枚举所有组合,然后建立hash table,以后只要你一输入,我就查表
【在 w****w 的大作中提到】 : 跟儿子一起学Python,发现它表达力很强,很适合算24点这样的程序。网上搜了一下, : 没发现一个像样的逻辑清晰,简洁,充分利用Python语言特点的24点程序。我习惯了过 : 程式,想学点函数式编程的实际运用,希望这里碰到高手。 : 要求: : 写一个函数solve(lst,target,all) : lst是自然数列表,可以超过4。 : target是24,也可以是其他数。 : 运算是加减乘除,如能加指数对数等则更好。 : 如果all是True,打出所有解答,否则打一个就够了。 : 程序行数最好不要超过50行,不然直接从C#/java翻过来没意思。
| w****w 发帖数: 521 | 24 跟儿子一起学Python,发现它表达力很强,很适合算24点这样的程序。网上搜了一下,
没发现一个像样的逻辑清晰,简洁,充分利用Python语言特点的24点程序。我习惯了过
程式,想学点函数式编程的实际运用,希望这里碰到高手。
要求:
写一个函数solve(lst,target,all)
lst是自然数列表,可以超过4。
target是24,也可以是其他数。
运算是加减乘除,如能加指数对数等则更好。
如果all是True,打出所有解答,否则打一个就够了。
程序行数最好不要超过50行,不然直接从C#/java翻过来没意思。
测试:
solve([2,3,4,5],24,True)
solve([2,5,7,11,13],19,True)
solve([1,2,3,4,5,6,7,8,9,10,11,12],37,False) | l*******G 发帖数: 1191 | 25 expression = list[1] op[1] list[2] .....list[i] op[i] list[i+1] ...list[n-
1]op[n-1] list[n]
where list[1] ... list[n] are any permutation of list
op[1] ... op[n-1] are any of + - * /
evaluate all possibilities of expression by putting expression in a string
and return
(eval(expression_string)==24)
e.g. expression_string='2*4*3*1'
eval(expression_string)==24 | l*******G 发帖数: 1191 | 26 #!/usr/bin/python
def permu(xs):
if xs:
r , h = [],[]
for x in xs:
if x not in h:
ts = xs[:]; ts.remove(x)
for p in permu(ts):
r.append([x]+p)
h.append(x)
return r
else:
return [[]]
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
def solve(mylist,target,all):
#Howto : solve([1,2,3,4],24,True)
listlength=len(mylist);
ops=product('+-*/',repeat=listlength-1);
m=map(str,ops);
listpermu=permu(mylist);
lengthpermu=len(listpermu);
for j in range(0,lengthpermu):
for i in range(0,len(m)):
op1d=m[i][2::5];
nop=len(op1d);
expr="";
for k in range(0,nop):
expr=expr+(str(listpermu[j][k]))+'.';
expr=expr+(op1d[k]);
expr=expr+str(listpermu[j][listlength-1])+'.';
good=(eval(expr)+0.0==target);
if all:
if good:
print expr;
else :
if good:
print expr;
return
#test 1
#solve([1,2,3,4],24,True);
#test 2
solve([1,2,3,4],24,False);
#test 3
solve([2,4,6,8],24,False); | w****w 发帖数: 521 | 27 这里有没有投票功能?
下面这几个方面1-5分:
1。正确性
2。可读性
3。易维护,debug
4。可扩充性 (加算子**,log ...)
5。运行效率(时间/空间)
如认为哪里可以改进,欢迎改进版。 | w****w 发帖数: 521 | | h***s 发帖数: 1716 | 29 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的
多。
其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能
力,就是函数式编程的核心。所以换到haskell了。。。
【在 w****w 的大作中提到】 : 这里用python的不多?
| a********x 发帖数: 1502 | 30 最近在学haskell,这个monad transformer真是brain torting啊
【在 h***s 的大作中提到】 : 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的 : 多。 : 其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能 : 力,就是函数式编程的核心。所以换到haskell了。。。
| | | h***s 发帖数: 1716 | 31 呵呵,Monad就是折磨脑子的,原因就是把数学里抽象的那一面给整进来了。我的经验
是,先别去化时间钻抽象的那一面,把monad当作定义好了interface的container看待
,map/filter的应用和其他container“一样”看待。
【在 a********x 的大作中提到】 : 最近在学haskell,这个monad transformer真是brain torting啊
| w****w 发帖数: 521 | 32 搞了两个礼拜,对python有点感觉了。
import math
_expr=lambda x,y,z:"(%s%s%s)"%(x,y,z)
_plus=lambda x,y: (x[0]+y[0],_expr(x[1],"+",y[1]))
_minus=lambda x,y: (x[0]-y[0],_expr(x[1],"-",y[1]))
_rminus=lambda x,y: _minus(y,x)
_mul=lambda x,y: (x[0]*y[0],_expr(x[1],"*",y[1]))
_div=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]/y[0],_expr(x[1],"/",y[1]))
_rdiv=lambda x,y: _div(y,x)
_mod=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]%y[0],"mod(%s,%s)"%(x[1],y[
1]))
_rmod=lambda x,y: _mod(y,x)
def _power(x,y):
try: return (x[0]**y[0],_expr(x[1],"**",y[1]))
except: return (0,"err")
_pow=lambda x,y: _power(x,y)
_rpow=lambda x,y: _power(y,x)
def _logarithm(x,y):
try: return (math.log(x[0],y[0]),"log(%s,%s)"%(x[1],y[1]))
except: return (0,"err")
_log=lambda x,y: _logarithm(x,y)
_rlog=lambda x,y: _logarithm(y,x)
def _pick2combination(base,num):
if num<2:return
for x in _pick2combination(base+1,num-1): yield x
for x in range(1,num): yield (base,base+x)
class Math24(object):
def __init__(self,level=1):
self.ops=[_plus,_minus,_rminus,_mul,_div,_rdiv]
if level>=2: self.ops+=[_log,_rlog]
if level>=3: self.ops+=[_pow,_rpow]
if level>=4: self.ops+=[_mod,_rmod]
def _eval(self,lst):
if len(lst)==1: yield lst[0]
for idx in _pick2combination(0,len(lst)):
nl=lst[:]
u,v=nl.pop(idx[1]),nl.pop(idx[0])
for op in self.ops:
nv=op(u,v)
if nv[1]!="err":
for x in self._eval(nl+[nv]): yield x
def solve(self,lst,target):
for y in self._eval([(float(x),str(x)) for x in lst]):
if abs(y[0]-target)<1.0e-9: yield y[1]
if __name__ == '__main__':
for x in Math24(2).solve([2,3,27,10],24): print x | w****w 发帖数: 521 | 33 haskell太不同了,找个人来没法train。
【在 h***s 的大作中提到】 : 学函数编程,干嘛不用haskell,纯函数式编程语言,比这种multi-paradigm表达强的 : 多。 : 其实像lisp这种的,也不纯。但我个人喜欢lisp的地方,是很强的一般化和抽象化的能 : 力,就是函数式编程的核心。所以换到haskell了。。。
| A*********n 发帖数: 158 | 34 赞,最近在学haskell,来学习下
【在 h***s 的大作中提到】 : 下面是haskell的写法 - 我只想了个简单的算法,作了简单的过滤,还可能有很多重 : 复的答案表达,这个可以在算法上进一步优化细调,就没搞了。简单的测试可了。如果 : 用GHC编译运行如下: : > ghc -O3 solve.hs : .... : > solve : ------------------------- : import Data.List : import System.IO : opBoxes = [((+), "+"), ((-), "-"), ((*), "*"), ((divi), "/")]
| h***s 发帖数: 1716 | 35 下面是haskell的写法 - 我只想了个简单的算法,作了简单的过滤,还可能有很多重
复的答案表达,这个可以在算法上进一步优化细调,就没搞了。简单的测试可了。如果
用GHC编译运行如下:
> ghc -O3 solve.hs
....
> solve
-------------------------
import Data.List
import System.IO
opBoxes = [((+), "+"), ((-), "-"), ((*), "*"), ((divi), "/")]
divi x y = round $ toRational(x) / toRational(y)
divisible x y = case y of 0 -> False
y -> mod (abs x) (abs y) == 0
runOp opBox ((x1,s1):(x2,s2):xs) = ((fst opBox x1 x2), ss):xs
where ss = showSolution (snd opBox) s1 s2
showSolution opStr s1 s2
| opStr=="+" || opStr=="*" = showWrapUp opStr (min s1 s2) (max s1 s2)
| otherwise = showWrapUp opStr s1 s2
showWrapUp opStr sx sy = "(" ++ sx ++ opStr ++ sy ++ ")"
initializeProblem [] = []
initializeProblem (x:xs) = (x, show x):initializeProblem xs
unDuplicatedPerm :: Eq a => [a] -> [[a]]
unDuplicatedPerm = Data.List.nub . Data.List.permutations
oneStepMap xs@((x1,s1):(x2,s2):ys)
= map (\x -> runOp x xs) $ oneStepOps x1 x2
oneStepOps x1 x2 = if (divisible x1 x2) then opBoxes
else
(init opBoxes)
completeMap xs@(x:ys)
| length x == 1 = xs
| otherwise = completeMap (xs >>= unDuplicatedPerm >>= oneStepMap)
solve xs target all =
if (null zs) then print " No Solution Found!"
else if all then mapM_ print zs
else mapM_ print $ head zs
where ys = [initializeProblem xs]
zs = showResult $ nub $
filter (\y -> fst (head y) == target) (completeMap ys)
showResult xs
= map (\x -> let s=(head x) in snd s ++ "=" ++ show (fst s)) xs
main = do
solve [2,3,27,10] 24 True
-- solve [1,2,7,13] 24 True
【在 w****w 的大作中提到】 : haskell太不同了,找个人来没法train。
| h***s 发帖数: 1716 | 36 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好
了,我不费劲了。
【在 A*********n 的大作中提到】 : 赞,最近在学haskell,来学习下
| A*********n 发帖数: 158 | 37 ghc 还是认出来了
【在 h***s 的大作中提到】 : 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好 : 了,我不费劲了。
| j*a 发帖数: 14423 | 38 可以贴pastebin去
【在 h***s 的大作中提到】 : 这个HTML对齐代码太费劲了,删两遍都还是对不好,算了,你们自己想象着怎么对齐好 : 了,我不费劲了。
| h***s 发帖数: 1716 | 39 haskell spec只要求你合理的空格就行了,而求haskell的函数特点是短而一般化,不
需要太多行,所以一般小的对不齐不会影响代码的正确性。
【在 A*********n 的大作中提到】 : ghc 还是认出来了
| w****w 发帖数: 521 | 40 haskell里list的evaluation都是lazy的吗? | | | h***s 发帖数: 1716 | 41 忘了说了,这段代码可以解任意个整数的情况,比如:[1,2,3,4,5,6,7 。。]
,不限于24点,就是LZ的原始问题。当然这只是逻辑算法和原理上来说,至于bug,就
不负责了。。哈!只要算法允许,haskell表达总是可以做到更简洁,这个负责是没问
题的。
当然我喜欢haskell,只是个人观点而已。。
【在 h***s 的大作中提到】 : 下面是haskell的写法 - 我只想了个简单的算法,作了简单的过滤,还可能有很多重 : 复的答案表达,这个可以在算法上进一步优化细调,就没搞了。简单的测试可了。如果 : 用GHC编译运行如下: : > ghc -O3 solve.hs : .... : > solve : ------------------------- : import Data.List : import System.IO : opBoxes = [((+), "+"), ((-), "-"), ((*), "*"), ((divi), "/")]
| h***s 发帖数: 1716 | 42 对,语言的纯函数性和这个有内在的关联。
比如,你给一个有很大解案空间的问题,你总是能在线地得到当前的答案子集,如果你
想刷新IO缓冲,就能“实时”看到最新结果。。。我唰唰!
【在 w****w 的大作中提到】 : haskell里list的evaluation都是lazy的吗?
| w****w 发帖数: 521 | 43 这个python不如,还得另写generator.
【在 h***s 的大作中提到】 : 对,语言的纯函数性和这个有内在的关联。 : 比如,你给一个有很大解案空间的问题,你总是能在线地得到当前的答案子集,如果你 : 想刷新IO缓冲,就能“实时”看到最新结果。。。我唰唰!
| a*******e 发帖数: 14 | 44 写了个 Common Lisp 的解法,就十几行(Lisp 算子有联结到对应说明,很好理解):
http://paste.lisp.org/+2V0T
(defun twenty-four (numbers &optional (target 24) all)
"Show arithmetic expression(s), composed of the given NUMBERS and the
four basic arithmetic operators, that evaluates to the TARGET number."
(labels ((fa (x)
(if (cdr x)
(loop for (i . u) on x thereis (fb i u p) collect i into p)
(and (= target (caar x)) (print (cdar x)) (not all))))
(fb (i u p)
(loop for (j . v) on u thereis (fc i j (append v q p))
collect j into q))
(fc (i j x)
(or (and (/= 0 (car j)) (fd '/ i j x))
(and (/= 0 (car i)) (fd '/ j i x))
(fd '+ i j x) (fd '* i j x) (fd '- i j x) (fd '- j i x)))
(fd (o i j x)
(fa `((,(funcall o (car i) (car j)) ,o ,(cdr i) ,(cdr j)) ,@x))
))
(fa (map 'list (lambda (x) (cons x x)) numbers))))
;;; Examples:
;;
;; CL-USER> (twenty-four '(2 3 7 10))
;; (+ (- (* 2 10) 3) 7)
;; CL-USER> (twenty-four '(2 3 7 10) 24 'show-all-solutions)
;; (+ (- (* 2 10) 3) 7)
;; (- 7 (- 3 (* 2 10)))
;; (- (+ (* 2 10) 7) 3)
;; (- (* 2 10) (- 3 7))
;; (+ (- 7 3) (* 2 10))
;; (- (* 10 2) (- 3 7))
;; (+ (* 10 2) (- 7 3))
;; (/ (+ (* 7 10) 2) 3) | h***s 发帖数: 1716 | 45 有意思.
看有没有C/C++, Java, Perl的版本能写成十几行的... 哦, 对了, 还有javascript,
visual basic, C#/F#的干活, 哈!
p)
【在 a*******e 的大作中提到】 : 写了个 Common Lisp 的解法,就十几行(Lisp 算子有联结到对应说明,很好理解): : http://paste.lisp.org/+2V0T : (defun twenty-four (numbers &optional (target 24) all) : "Show arithmetic expression(s), composed of the given NUMBERS and the : four basic arithmetic operators, that evaluates to the TARGET number." : (labels ((fa (x) : (if (cdr x) : (loop for (i . u) on x thereis (fb i u p) collect i into p) : (and (= target (caar x)) (print (cdar x)) (not all)))) : (fb (i u p)
| b*******s 发帖数: 5216 | 46 c++更快,先枚举所有组合,然后建立hash table,以后只要你一输入,我就查表
【在 w****w 的大作中提到】 : 跟儿子一起学Python,发现它表达力很强,很适合算24点这样的程序。网上搜了一下, : 没发现一个像样的逻辑清晰,简洁,充分利用Python语言特点的24点程序。我习惯了过 : 程式,想学点函数式编程的实际运用,希望这里碰到高手。 : 要求: : 写一个函数solve(lst,target,all) : lst是自然数列表,可以超过4。 : target是24,也可以是其他数。 : 运算是加减乘除,如能加指数对数等则更好。 : 如果all是True,打出所有解答,否则打一个就够了。 : 程序行数最好不要超过50行,不然直接从C#/java翻过来没意思。
| w****w 发帖数: 521 | 47 八皇后50几种语言:
http://rosettacode.org/wiki/N-queens_problem
【在 h***s 的大作中提到】 : 有意思. : 看有没有C/C++, Java, Perl的版本能写成十几行的... 哦, 对了, 还有javascript, : visual basic, C#/F#的干活, 哈! : : p)
| w******p 发帖数: 166 | 48 python code can be under 20 lines too:
import sys, operator, itertools, math;
def reverseOp(op):
def reverseFun(*args): return op(*reversed(args))
return reverseFun
binaryOps = { '+': operator.add, '/': operator.div, '*': operator.mul, '^
': operator.pow, '-': operator.sub, 'L': math.log, '!-': reverseOp(
operator.sub), '!/': reverseOp(operator.div), '!^': reverseOp(operator.pow),
'!L': reverseOp(math.log), }
def appl(ops, nums):
r, repr = nums[0], '{0}'.format(nums[0])
try:
for i, op in enumerate(ops):
r = binaryOps[op](r, float(nums[i+1]))
if i != 0: repr = '(%s)' % repr
if op[0] == '!': repr = '{2} {1} {0}'.format(repr, op[-1], nums[
i+1])
else: repr = '{0} {1} {2}'.format(repr, op[-1], nums[
i+1])
except: return [None, None]
return [r, repr]
def solve(nums, target, full=False):
res = (repr for [x, repr] in (appl(ops, perm) for perm in itertools.
permutations(nums) for ops in itertools.product(binaryOps.keys(), repeat=len
(nums)-1)) if x is not None and math.fabs(x-target) < 1e-6)
return [next(res)] if not full else set(res)
for sol in solve([2,5,7,11,13],19): print sol | c*********n 发帖数: 128 | 49 这程序恰好我以前写过,哈哈。interface稍微不一样,懒得改了,直接贴过来。
import sys
from itertools import permutations
#from operator import __add__
EPS = 0.0000001
isEqual = lambda x, y: [False, True][abs(x-y)
def main():
line = sys.stdin.readline()
numbers = map(float, line.split())
if(len(numbers) == 0): numbers = [2.0, 2.0, 3.0, 5.0]
xs = map(X, numbers, map(str, map(int, numbers)))
expressions = []
findExpression(expressions, 24.0, xs)
print '\n'.join(set(expressions))
class myoperator:
sign = ''
op = None
def __init__(self, sign_, op_):
self.sign = sign_
self.op = op_
opUniverse = [myoperator('+', (lambda x, y: x+y)),
myoperator('-', (lambda x, y: x-y)),
myoperator('*', (lambda x, y: x*y)),
myoperator('/', (lambda x, y: x/y))
]
class X(float):
ex = ''
def __new__(self, value_, ex=''):
return float.__new__(self, value_)
def __init__(self, value_, ex_=''):
self.ex = ex_
def __div__(self, another_):
return sys.float_info.max if abs(another_)<1e-6 else float(self)/
float(another_)
def findExpression(expressions, target, xs, newX = None):
if len(xs) == 0:
if isEqual(target, newX):
expressions.append(newX.ex)
return
_xs = list(xs)
if newX != None: _xs.append(newX)
print "Try to combine [%s] | [%s]" % (', '.join(map(str, _xs)), ', '.
join(map(lambda x: x.ex, _xs)))
map(lambda duo: tryTwo(expressions, target, duo, _xs), permutations(_xs,
2))
def tryTwo(expressions, target, duo, xs):
print "Try [%s] from [%s]" % (', '.join(map(str, duo)), ', '.join(map(
str, xs)))
subXs = list(xs)
map(lambda x: subXs.remove(x), duo)
map(lambda f: findExpression(expressions, target, subXs, X(f.op(duo[0],
duo[1]), '(%s %s %s)'%(duo[0].ex, f.sign, duo[1].ex))), opUniverse)
if __name__ == '__main__':
main() | s****0 发帖数: 117 | 50 贴一个scala的。正在学习,书还没完全看完。初学乍练,多多指教
package myTest
import scala.collection.mutable.Map
import scala.collection.mutable.Stack
class Test3(lst: Array[Int], target: Int, all: Boolean) {
def solve() = {
for (inst <- genInstr(lst.length); op <- ops(lst.length - 1); l <- lst.
permutations) {
val rst = exec(inst, op, l);
if (rst == target) {
println(inst + ", " + op)
}
}
}
def genInstr(n: Int): IndexedSeq[String] = {
if (n == 1)
return Array("g");
for (i <- 1 to n - 1; left <- genInstr(i); right <- genInstr(n - i))
yield {
left + right + "+";
}
}
def ops(n: Int): Array[String] = {
if (n == 0) return Array("");
for (op <- "+-*/".toCharArray(); opst <- ops(n - 1)) yield op + opst
}
def exec(inst: String, ops: String, data: Array[Int]): Int = {
var cp = 0; var opsc = 0; var l = 0; var r = 0; var stk = Stack[Int]();
var opmap = Map[Char, (Int, Int) => Int]('+' -> (_ + _), '-' -> (_ - _),
'*' -> (_ * _), '/' -> ((x, y) => { if (y == 0 || x < y) 1000007 else (x /
y) }));
for (op <- inst.toCharArray()) {
op match {
case 'g' => { stk.push(data(cp)); cp += 1; }
case '+' => { stk.push(opmap(ops(opsc))(stk.pop(), stk.pop())); opsc
+= 1; }
}
if (stk.top == 1000007) { return (-1); }
}
stk.pop();
}
}
object Test3 {
def main(args: Array[String]) {
val tst = new Test3(Array(1, 2, 3, 4), 24, true)
tst.solve()
}
} | | | d********g 发帖数: 10550 | 51 两个礼拜搞成这个水平,很不错啊
))
y[
【在 w****w 的大作中提到】 : 搞了两个礼拜,对python有点感觉了。 : import math : _expr=lambda x,y,z:"(%s%s%s)"%(x,y,z) : _plus=lambda x,y: (x[0]+y[0],_expr(x[1],"+",y[1])) : _minus=lambda x,y: (x[0]-y[0],_expr(x[1],"-",y[1])) : _rminus=lambda x,y: _minus(y,x) : _mul=lambda x,y: (x[0]*y[0],_expr(x[1],"*",y[1])) : _div=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]/y[0],_expr(x[1],"/",y[1])) : _rdiv=lambda x,y: _div(y,x) : _mod=lambda x,y: (y[0]==0 and (0,"err")) or (x[0]%y[0],"mod(%s,%s)"%(x[1],y[
| w****w 发帖数: 521 | 52 终于见到超一流选手了。
两行解sudoku:
def r(a):i=a.find('0');~i or exit(a);[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/
3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1]) | b*******k 发帖数: 21 | 53 Using the recursive approach:
#!/usr/bin/env python
def solve24(numbers, goal):
"""Give a set of non duplicate positive numbers, can we use +, -, *, /
to get the goal?
Return one solution or None."""
if len(numbers) == 0:
return None
if len(numbers) == 1:
if numbers[0] == goal:
return '%d' % numbers[0]
else:
return None
ops = [
('+', lambda a, b: a - b),
('-', lambda a, b: b - a),
('*', lambda a, b: a / b if b and a % b == 0 else None),
('/', lambda a, b: b * a if a and b % a == 0 else None),
]
for index, n in enumerate(numbers):
for op_symbol, predict in ops:
# n op solve24(remaining) == goal => solve24(remaining, goal rev
_op n)
next_goal = predict(goal, n)
if next_goal:
next_numbers = list(numbers)
next_numbers.pop(index)
solution = solve24(next_numbers, next_goal)
if solution:
# Eureka!
return '%d %s (%s)' % (n, op_symbol, solution)
return None
if __name__ == "__main__":
import unittest
class TestSolve24(unittest.TestCase):
def test_sample(self):
samples = [
([6, 6, 6, 6], 24, True),
([2, 3, 4, 5], 24, True),
([3, 5, 4, 2], 24, True),
([2, 2, 2, 2], 24, False),
([1, 2, 3, 4], 24, True),
([2, 5, 7, 11, 13], 19, True),
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 37, True),
]
for numbers, goal, expected in samples:
output = solve24(numbers, goal)
if expected:
print '%d = %s' %(goal, output)
self.assertTrue(output)
else:
print '%d != %s' %(goal, output)
self.assertFalse(output)
unittest.main() | E*****m 发帖数: 25615 | 54 我也來湊個熱鬧, Prolog, 11 行。
del([H|T],H,T).
del([H|T1],X,[H|T]):- del(T1,X,T).
evaluate(X,'-',Y,Z):- Z is X-Y.
evaluate(X,'+',Y,Z):- Z is X+Y.
evaluate(X,'*',Y,Z):- Z is X*Y.
evaluate(X,'/',Y,Z):- Y =\= 0, Z is X/Y.
solve1([X],X, []).
solve1([HH|L],X, [Operator,H1|Sol1]):- del(L,H1,L1), evaluate(HH,Operator,H1
,H), solve1([H|L1],X,Sol1).
solve0(L,X,Ans):- del(L,H,T), solve1([H|T],X,Sol),concat_atom([H|Sol],Ans).
solve(List,Target,true):- findall(Sol,solve0(List,Target,Sol), Sols), print(
Sols),!.
solve(List,Target,false):- solve0(List,Target,Sol), print(Sol),!.
測試
?- solve([2,3,7,10],24,false).
2*10-3+7
true.
?- solve([2,3,7,10],24,true).
[2*10-3+7,2*10+7-3,7*10+2/3,10*2-3+7,10*2+7-3,10*7+2/3]
true. | w****w 发帖数: 521 | 55 上两楼都有漏解吧?试一下11,13,17,29。 | E*****m 发帖数: 25615 | 56
我大概沒搞懂規則, 規則在哪裡?
【在 w****w 的大作中提到】 : 上两楼都有漏解吧?试一下11,13,17,29。
| w****w 发帖数: 521 | 57 简单递归会把((a,b),(c,d))形式的解漏掉。
【在 E*****m 的大作中提到】 : : 我大概沒搞懂規則, 規則在哪裡?
| E*****m 发帖数: 25615 | 58 原來不知道可以用括號,改了一下
ev(('-',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X-Y.
ev(('+',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X+Y.
ev(('*',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X*Y.
ev(('/',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Y =\= 0, Z is X/Y.
ev(X, X).
term([X,Y], (Op1, X,Y), Ops):-member(Op1, Ops).
term([H|T], (Op1, H,YT), Ops):- member(Op1, Ops), term(T,YT,Ops).
term([X,Y|T], (Op1, (Op2, X,Y), YT), Ops):- member(Op1, Ops), member(Op2,
Ops),term(T,YT,Ops).
solve1(List, Target, Term):- permutation(List, L1), term(L1, Term, ['-','+',
'*','/']), ev(Term,Target).
solve(List,Target,true):- findall(Sol,(solve1(List,Target,Sol0),infix(Sol0,
Sol)), Sols), print(Sols),!.
solve(List,Target,false):- solve1(List,Target,Sol),infix(Sol,Sol1), print(
Sol1),!.
infix((Op,X,Y),R):-!, infix(X,X1),infix(Y,Y1),concat_atom(['(',X1,Op,Y1,')']
,R).
infix(X,X).
測試
?- solve([11,13,17,29],24, true).
[ ((11-13)*(17-29)), ((13-11)*(29-17)), ((17-29)*(11-13)), ((29-17)*(13-11))]
true.
【在 w****w 的大作中提到】 : 简单递归会把((a,b),(c,d))形式的解漏掉。
| E*****m 发帖数: 25615 | 59 Prolog 可以說就是設計來做這種排列組合找解的題目, 其他語言
很難寫得更短了。 |
|