Jump to 0 top | 1 navigation | 2 content | 3 extra information (sidebar) | 4 footer | 5 toolbar

Content

让我们从游戏开始──点灯(4)

第三天
到目前为止，我们的进展都很顺利。不过我们的代码速度还不是很快，应该还有改进的余地。
昨天我们使用第一行生成了一个包含2^n个序列的list，我们认真看看，就会发现中间很多是对称的，比如n=3的时候100,001对称， 110,011对称。按照我们的算法，这些对称的的序列最后得到的开关桩状态也是对称的，那么我们把每得到一个解，就可以把对称的第一行组合去掉。那么同 理，如果第一行的某一个组合不是解，那么我们也可以把他去掉。这样不就减少了很多的循环次数啦。
首先判断list是否对称：

  1. def symmetric(alist):#判断list是否对称
  2. leng=len(alist)
  3. le=alist[:(leng/2)]
  4. ri=alist[-(leng/2):]
  5. ri.reverse()
  6. if le!=ri:
  7. alist.reverse()
  8. return alist
  9. else:
  10. return None

其他的都一样，我们在昨天的基础上修改一下就好了：

  1. def light(n):
  2. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  3. solution=zeros((n, n))#解
  4. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  5. try:
  6. for i in range(len(PosSol)):
  7. i=PosSol[i][:]
  8. solution[0:1]=i
  9. tmpArray[0, :]=0
  10. tmpArray[1,1:-1]=i
  11. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  12. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  13. tmpArray[:,1:-1]=solution[line:line+2, :]
  14. if sum(lightstats(tmpArray, n))==n:
  15. steps=sum(sum(solution))
  16. print solution
  17. print "Total steps:%d" % steps
  18. rev=symmetric(i)
  19. if rev!=None:
  20. print solution[:,::-1]
  21. print "Total steps:%d" % steps
  22. PosSol.remove(rev)
  23. except:
  24. pass

注意for i in range(len(PosSol))这句，这个是很多初学python的人在循环上犯的错。但是我们这里这么作是有原因的。在如果直接写for i in PosSol，那么在循环体中间对PosSol的操作不会得到你想要的结果，所以我们这样避免了这样的问题。i=PosSol[i][:]是产生一个拷 贝。免得对PosSol里面产生影响。
下面就是代码：

  1. #!/usr/bin/python
  2. # -*- coding: utf8 -*-
  3. #Filename:third2.py

  5. from numarray import *
  6. import numarray.strings as nastr
  7. from bin import bstr

  9. def lightstats(switchstats, n):
  10. TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]
  11. [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
  12. return [(sum(sum(item)))%2 for item in TxT]

  14. def symmetric(alist):#判断list是否对称
  15. leng=len(alist)
  16. le=alist[:(leng/2)]
  17. ri=alist[-(leng/2):]
  18. ri.reverse()
  19. if le!=ri:
  20. alist.reverse()
  21. return alist
  22. else:
  23. return None

  25. def light(n):
  26. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  27. solution=zeros((n, n))#解
  28. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  29. try:
  30. for i in range(len(PosSol)):
  31. i=PosSol[i][:]
  32. solution[0:1]=i
  33. tmpArray[0, :]=0
  34. tmpArray[1,1:-1]=i
  35. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  36. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  37. tmpArray[:,1:-1]=solution[line:line+2, :]
  38. if sum(lightstats(tmpArray, n))==n:
  39. steps=sum(sum(solution))
  40. print solution
  41. print "Total steps:%d" % steps
  42. rev=symmetric(i)
  43. if rev!=None:
  44. print solution[:,::-1]
  45. print "Total steps:%d" % steps
  46. PosSol.remove(rev)
  47. except:
  48. pass

  50. if __name__ == "__main__":
  51. tests = [2,3,4,5,6,7,8,9,10]
  52. for xx in tests:
  53. print "solution for %d*%d" % (xx,xx)
  54. light(xx)

既然可以用对称得到解，那么也可以用对称排除不是解的组合：

  1. def light(n):
  2. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  3. solution=zeros((n, n))#解
  4. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  5. try:
  6. for i in range(len(PosSol)):
  7. i=PosSol[i][:]
  8. solution[0:1]=i
  9. tmpArray[0, :]=0
  10. tmpArray[1,1:-1]=i
  11. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  12. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  13. tmpArray[:,1:-1]=solution[line:line+2, :]
  14. rev=symmetric(i)
  15. if sum(lightstats(tmpArray, n))==n:
  16. steps=sum(sum(solution))
  17. print solution
  18. print "Total steps:%d" % steps
  19. if rev!=None:
  20. print solution[:,::-1]
  21. print "Total steps:%d" % steps
  22. PosSol.remove(rev)
  23. else:
  24. if rev!=None:
  25. PosSol.remove(rev)
  26. except:
  27. pass

这是新的light函数。不过我们想想，我们可以把解进行旋转，得到的就是其他的解，但是不是解的组合不能旋转排除哦，原因嘛，想想就明白了。我们写一个旋转的函数：

  1. def rotatearray(array):
  2. o=zeros(shape(transpose(a)))
  3. for i in range(len(a)):
  4. b[:,i]=a[i,::-1]
  5. return o

那么就是修改以后的light函数：

  1. def light(n):
  2. allSolutions=[]
  3. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  4. solution=zeros((n, n))#解
  5. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  6. try:
  7. for i in range(len(PosSol)):
  8. i=PosSol[i][:]
  9. solution[0:1]=i
  10. tmpArray[0, :]=0
  11. tmpArray[1,1:-1]=i
  12. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  13. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  14. tmpArray[:,1:-1]=solution[line:line+2, :]
  15. if sum(lightstats(tmpArray, n))==n:
  16. steps=sum(sum(solution))
  17. temp=solution
  18. for j in range(2):
  19. for k in range(4):
  20. temp=rotateArray(temp)
  21. if temp.tolist() not in allSolutions:
  22. allSolutions.append(temp.tolist())
  23. print temp
  24. print "Total steps:%d" % steps
  25. try:
  26. PosSol.remove(temp[0, :].tolist())
  27. except:
  28. pass
  29. temp=transpose(temp)
  30. else:
  31. try:
  32. PosSol.remove(rev)
  33. except:
  34. pass
  35. except:
  36. pass

我们去掉了判断对称的函数，直接使用remove，跳过错误信息。定义了allSolutions来避免重复。
现在来总测试一下我们的成果吧：
程序 n 时间

first.py 2~4 real 3m16.271s

second.py 2~10 real 2m32.655s

second2.py 2~10 real 2m38.275s
third.py 2~10 real 2m28.386s

third2.py 2~10 real 1m32.934s
third3.py 2~10 real 1m17.786s

posted by LuluKen on May 1, 2007 8:59 PM | 0 comments
Tags: ,

  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • 0 ratings

让我们从游戏开始──点灯(3)

第二天
我们完成了一个求解的程序，但是我们还不能高兴，注意到first.py最后的注释没？因为运算量太大，连5×5都完成不了（或者很难完成），就别说更大的了。看来我们还要作一些大的改进才行。
让我们再琢磨琢磨我们的在理论分析中得到的一些信息。嗯~既然灯泡的状态之和“影响格”有关，那么是否意味着开关开启的顺序是无关的？看来我们有了一个突破口。一行一行的求解的可能性是有的，但是我们要怎么作呢？让我们先来分析一下。
我们从上往下考虑，如果先确定了第一行的开关状态，那么能影响这一行的就只有第二行;确定了第二行以后能影响它的就只有第三行……这样类推的话，我们只要 穷举第一行可能的情况，然后从下面一行开始，保证上面一行的灯泡全亮。这样循环下去，到最后一行完成的时候如果就能确定这是否是一个解。看来我们从2** (n*n)已经化简到了2*n。好~好的很。
为了避免不停计算灯泡的状态，我们专门为灯泡状态添加一个表。有了昨天的基础，今天看来可以很快完成。：）
首先得到得到第一行的所有组合：

  1. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]

嗯~让我们停下来一下。当我们得到了第一行的灯泡状态以后，我们就确定了第二行的开关状态。由于能影响第一行的只剩第二行的开关，那么我们其实只要 把第一行的灯泡状态取反就得到了第二行的开关状态。对开关状态的判断也简单了，只需要对上两行的灯泡状态判断就可以了，真是比昨天的简单多了。

  1. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]
  2.   lightStats=zeros((n, n))#灯泡的状态
  3.   solution=zeros((n, n))#解
  4.   tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  5.   for i in PosSol:
  6.     solution[0:1]=i.copy()
  7.     tmpArray[0, :]=0
  8.     tmpArray[1,1:-1]=i.copy()
  9.     for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算     
  10.       TxT = [take(tmpArray, [x, x+1, x+2], axis=1) for x in range(n)] 
  11.       [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#我们要由上一行得到下一行的状态
  12.       solution[line+1:line+2, :]=[(sum(sum(item))+1)%2 for item in TxT]

然后计算最后一行的灯泡状态得到是否是解：

  1. TxT = [take(tmpArray, [x, x+1, x+2], axis=1) for x in range(n)] 
  2. [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]
  3. if sum([(sum(sum(item)))%2 for item in TxT])==n:
  4.    print solution
  5.    print "Total steps:%d" % sum(sum(solution))

把重复代码提取出来成一个函数：

  1. def lightstats(switchstats, n):
  2.    TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)] 
  3.    [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
  4.    return [(sum(sum(item)))%2 for item in TxT]

好了，配件齐全，开始组装：

  1. #!/usr/bin/python
  2. # -*- coding: utf8 -*-
  3. #Filename:second2.py
  4.  
  5. from numarray import *
  6. import numarray.strings as nastr
  7. from bin import bstr
  8.  
  9. def lightstats(switchstats, n):
  10.    TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)] 
  11.    [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
  12.    return [(sum(sum(item)))%2 for item in TxT]
  13.  
  14. def light(n):
  15.    PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]
  16.    solution=zeros((n, n))#解
  17.    tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  18.    for i in PosSol:
  19.       solution[0:1]=i.copy()
  20.       tmpArray[0, :]=0
  21.       tmpArray[1,1:-1]=i.copy()
  22.       for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算     
  23.          solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  24.          tmpArray[:,1:-1]=solution[line:line+2, :]
  25.       if sum(lightstats(tmpArray, n))==n:
  26.          print solution
  27.          print "Total steps:%d" % sum(sum(solution))
  28.  
  29. tests = [2,3,4,5,6]
  30. for xx in tests:
  31.    print "solution for %d*%d" % (xx,xx)
  32.    light(xx)

现在就算算10×10也不会很久啦，哈哈~~不过代码还有可以商量的地方，明天继续。

posted by LuluKen on May 1, 2007 8:54 PM | 0 comments
Tags: ,

  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • 0 ratings

让我们从游戏开始──点灯(2)

第一天
对于这样的问题，我们最直接的想法就是穷举法：把所有的组合都试一次，有此来找到所有可能的解。
那么我们怎么的到这所有的组合呢？让我们来回想一下前面理论分析的内容。所有灯的状态都用0和1来表示，如果我们把这个4×4的二维数组组合成一个0、1序列，那么我们这个得到的0、1序列的是[0, 2^16)中所有的整数．我们用如下的语句得到这个整数序列：

  1. [x for x in xrange(2**16)]#由于数量比较大，我们没有使用range。两者之间的额区别google一下就可以了。

现在我们把这些整数变成二进制！由于python里面没有直接的函数可以转换，所有我们要自己完成：

  1. bstr = lambda n, l=16: n<0 and binarystr((2L<>1).lstrip('0')+str(n&1) or '0'

>>>bstr(5)
‘101′

注意一下返回的是一个字符串（这个是肯定的，想想就知道了）。zfill可以补齐我们需要的位数。那么生成序列的语句就出来了：

  1. [bstr(x).zfill(16) for x in xrange(2**16)]

现在我们把得到的序列变成数组。numarray是不错的选择。

>>> import numarray.strings as nastr
>>> a=nastr.array(’101010101′, itemsize=1)
>>> a
CharArray([’1′, ‘0′, ‘1′, ‘0′, ‘1′, ‘0′, ‘1′, ‘0′, ‘1′])
>>> numarray.reshape(a,3,3)
CharArray([[’1′, ‘0′, ‘1′],
[’0′, ‘1′, ‘0′],
[’1′, ‘0′, ‘1′]]))

还要把字符转换成数字，用eval就好了。
Hoho, 看来我们需要的东西基本已经齐全了，我们现在先把得到的东西都组合一下。得到下面的代码：

  1. from numarray import *
  2. import numarray.strings as nastr
  3. PosSol=[reshape(nastr.array(bstr(x).zfill(16), itemsize=1),4,4).eval() for x in xrange(2**16)]#PosSol:Possible Solutions

当然，我们现在是限定一个4×4的情况，如果要解n×n，小小改动一下就可以了。如果你对上面的代码的结果有些怀疑，那试试2×2的情况，代码怎么修改相信你应该很清楚，看看结果吧。好了，让我们继续吧。
现在我们有了开关状态的所有组合，那么我们就要根据这些组合计算出灯泡状态。让我们想想灯泡状态的代码要怎么写。我们用x（表示列），y（表示行）表示给 定的灯泡位置，我们根据开关状态计算它是否被点亮。相信很多人的第一想法就是按照给定的x，y得到x+1,x-1,y+1,y-1这些，还要自己判断是否 在给定的元素处于数组的边界……天，我不要再想这种方法了。虽然很直接，但是一点都不好。让我们在脑子里面最后想想这种充满臭味的代码，你难道忍心你的代 码是这样的吗？看来我们要用其他的方法来作，至少看上去要聪明一些的方法。
不如我们不考虑边界的问题，这样不就简单了。：）由于我们计算的是“1”的个数，所以我们把一个4×4的数组加一个由“0”组成的边框。这样就没有“出界”问题了。由于我们的数组是4×4,那么我们这么写：

  1. tmpArray=zeros((6,6))
  2. tmpArray[1:5,1:5]=PosSol.copy()

然后把我们需要的3×3的“抠出来”：

  1. TxT=take(take(tmpArray, [x,x+1,x+2]),[y,y+1,y+2], axis=1)#TxT:Three X Three Square

好了，现在我们只要去掉四个角的数，然后求和判断是不是奇数就知道灯泡是不是点亮了：

  1. putmask(TxT,[1,0,1,0,0,0,1,0,1],0)
  2. value=sum(sum(finalSquare),1)

现在我们全部汇总就得到了游戏的解法，顺便作些小的改动就得到了n×n的算法了：

  1. #!/usr/bin/python
  2. # -*- coding: gb2312 -*-
  3. #Filename:first.py


  6. from numarray import *
  7. import numarray.strings as nastr
  8. from bin import bstr

  10. def light(n):
  11. PosSol=[reshape(nastr.array(bstr(x).zfill(n*n), itemsize=1),n,n).eval() for x in xrange(2**(n*n))]#PosSol:Possible Solutions
  12. tmpArray=zeros((n+2,n+2))
  13. for i in PosSol:
  14. tmpArray[1:n+1,1:n+1]=i.copy()
  15. Neg=False
  16. for x in range(n):
  17. if Neg:
  18. break
  19. for y in range(n):
  20. if Neg:
  21. break
  22. TxT=take(take(tmpArray, [x,x+1,x+2]),[y,y+1,y+2], axis=1)#TxT:Three X Three Square
  23. putmask(TxT, [1,0,1,0,0,0,1,0,1], [0])
  24. value=sum(sum(TxT))
  25. if not (value%2):#找到一个没有点亮就不用判断剩余的了
  26. Neg=True
  27. if not Neg:
  28. print i
  29. print "Total steps:%d" % sum(sum(i))

  31. tests = [2, 3, 4]
  32. for xx in tests
  33. print "solution for %d*%d" % (xx,xx)
  34. light(xx)

太晚了，趁还没下班先把东西收拾了，下班回家睡觉。：）

posted by LuluKen on May 1, 2007 8:52 PM | 0 comments
Tags: ,

  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • 0 ratings

让我们从游戏开始──点灯(1)

一次上班无聊，把同事的手机拿来打游戏，发现有个叫“点灯”的小游戏，开始不太在意，玩了一会儿以后发现非常有趣，想想很久没有写过程序了，便决定用这个来练练手。
关于游戏
点灯游戏规则非常简单，简单到什么人都可以一学就会。但是简单的规则并不意味着游戏也简单，这恰恰就是我所喜欢的，在简单中充满变化。因为规则简单，我在这里就不多说了。
[swf]http://games.wuhan.cc/flash/flash/flash_swf/3015.swf,1400,550,7,#FFFFFF[/swf]
这个是网上找到的，所不同的就是他在开始的时候有些灯已经点亮了。让我们简化一下，4×4的正方形，一开始所有灯都是关闭状态，我们的目的就是把所有的灯都打开。等我们把这个简化的问题解决了，在来看看这个大的问题。

一些理论
这个游戏真是让人恼火啊，为了让程序能够解出答案，我们需要想想这个游戏到底是什么。
也许我们应该这样看这个游戏：这16个格子是16个开关，每个开关控制着灯泡的状态。如果一个开关的状态改变，那么其所在格子与相邻格子的灯泡状态反转。 这样我们就可以初始化一个4×4,全部是0的数组，表示所有开关全部是关闭的，当某一格的开关打开，我们就把这格变成1。而且我们可以发现，某一格的开关 状态变化偶数次，那么灯泡的状态和最初的状态是一样的（0->1->0）。那么我们用0和1来表示开关的状态是成立的。
好了，现在我们有个一个新的问题：如何从开关状态得到灯泡的状态？问题其实很简单，从上面我们知道，某一格的灯泡受到
自己所在的格子与周围四格的影响（我们为了简单称这些格子叫“影响格”），由于一开始灯泡是关闭的，而且只有两种状态（灯亮，灯灭），所以我们可以知道：对于某一格的灯泡，如果影响格内有奇数个开关打开，这格灯泡就被点亮，反之关闭。
天，我的文笔实在太差，写这些理论真是很痛苦，也不知道有多少人能看懂。
现在我们开始写程序吧。

posted by LuluKen on Apr 27, 2007 5:14 PM | 0 comments
Tags: ,

  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • 0 ratings
Pages: 1 (1 - 4 / 4)

» Next Space