由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - Python擂台:算24点
相关主题
问个python问题阅读scala中
How to Parsing function in haskell?Scala有一点不好
有每天上班写py的么 会不会疯掉?请问haskell中的underscore
我也来一个, quick sort 只要一行。这么说吧,fp不是否定变量,而是控制变量的范围
关于FP大家有没有觉得Scala不如Haskell美?
抛砖引玉,来谈谈functional programming两个class的交叉引用问题
粉FP的人是因为把电脑想象成图灵机了python得问题
Python is easy and not easy如何取一个list的第i个element
相关话题的讨论汇总
话题: expr话题: lambda话题: xs话题: def话题: solve
进入Programming版参与讨论
1 (共1页)
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
5
这里用python的不多?
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了。。。

相关主题
抛砖引玉,来谈谈functional programming阅读scala中
粉FP的人是因为把电脑想象成图灵机了Scala有一点不好
Python is easy and not easy请问haskell中的underscore
进入Programming版参与讨论
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缓冲,就能“实时”看到最新结果。。。我唰唰!

相关主题
这么说吧,fp不是否定变量,而是控制变量的范围python得问题
大家有没有觉得Scala不如Haskell美?如何取一个list的第i个element
两个class的交叉引用问题请教 C++ std::list iterator 对 template class pointer 的应用问题
进入Programming版参与讨论
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
28
这里用python的不多?
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了。。。

相关主题
什么时候需要调用STL container的destructor?How to Parsing function in haskell?
javascript问题,怎么让浏览器下载一个文件不是直接打开? (转载)有每天上班写py的么 会不会疯掉?
问个python问题我也来一个, quick sort 只要一行。
进入Programming版参与讨论
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的吗?
相关主题
我也来一个, quick sort 只要一行。粉FP的人是因为把电脑想象成图灵机了
关于FPPython is easy and not easy
抛砖引玉,来谈谈functional programming阅读scala中
进入Programming版参与讨论
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()
}
}
相关主题
Scala有一点不好大家有没有觉得Scala不如Haskell美?
请问haskell中的underscore两个class的交叉引用问题
这么说吧,fp不是否定变量,而是控制变量的范围python得问题
进入Programming版参与讨论
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 可以說就是設計來做這種排列組合找解的題目, 其他語言
很難寫得更短了。
1 (共1页)
进入Programming版参与讨论
相关主题
如何取一个list的第i个element关于FP
请教 C++ std::list iterator 对 template class pointer 的应用问题抛砖引玉,来谈谈functional programming
什么时候需要调用STL container的destructor?粉FP的人是因为把电脑想象成图灵机了
javascript问题,怎么让浏览器下载一个文件不是直接打开? (转载)Python is easy and not easy
问个python问题阅读scala中
How to Parsing function in haskell?Scala有一点不好
有每天上班写py的么 会不会疯掉?请问haskell中的underscore
我也来一个, quick sort 只要一行。这么说吧,fp不是否定变量,而是控制变量的范围
相关话题的讨论汇总
话题: expr话题: lambda话题: xs话题: def话题: solve