二零一三年，PyCon 上有一個『競賽問題』︰
Pcarbonn 先生寫了兩個 pyDatalog 的程式︰
”’
Created on 2 avr. 2013
The HASHTAG problem was the subject of a contest at PyCon 2013.
Problem description : https://picasaweb.google.com/lh/photo/u_6ZWCrTUNVADkPAyyFvfKbReIcFkkE5l5WZw-QBbLc
Discussion : http://uthcode.appspot.com/2013/03/Hashtag-at-pycon
Below is a solution based on pyDatalog
@author: pcarbonn
”’
執行結果如下︰
《hashtag.py》
pi@raspberrypi ~ ![python3 Python 3.2.3 (default, Mar 1 2013, 11:53:50) [GCC 4.6.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from pyDatalog import pyDatalog, pyEngine >>> import time >>> pyDatalog.create_terms('star, move,solution,X,Y,N,N1,N2') >>> pyDatalog.create_terms('X1,X2,X3,X4,X5,X6,X7,X8,X9') >>> pyDatalog.create_terms('Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9') # X has a star in position N1 or N2 >>> star(X,N1,N2) <= (X[N1]=='*') star(X,N1,N2) <= ==((X[N1),'*') >>> star(X,N1,N2) <= (X[N2]=='*') star(X,N1,N2) <= ==((X[N2),'*') # valid moves are exchange of 1<->2, 1<->4, ... >>> X19 = (X1,X2,X3,X4,X5,X6,X7,X8,X9) # short hand >>> move(X19, '1-2,', Y) <= star(X19, 0, 1) & (Y==(X2,X1,X3,X4,X5,X6,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '1-4,', Y) <= star(X19, 0, 3) & (Y==(X4,X2,X3,X1,X5,X6,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '2-3,', Y) <= star(X19, 1, 2) & (Y==(X1,X3,X2,X4,X5,X6,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '2-5,', Y) <= star(X19, 1, 4) & (Y==(X1,X5,X3,X4,X2,X6,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '3-6,', Y) <= star(X19, 2, 5) & (Y==(X1,X2,X6,X4,X5,X3,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '4-5,', Y) <= star(X19, 3, 4) & (Y==(X1,X2,X3,X5,X4,X6,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '4-7,', Y) <= star(X19, 3, 6) & (Y==(X1,X2,X3,X7,X5,X6,X4,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '5-6,', Y) <= star(X19, 4, 5) & (Y==(X1,X2,X3,X4,X6,X5,X7,X8,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '5-8,', Y) <= star(X19, 4, 7) & (Y==(X1,X2,X3,X4,X8,X6,X7,X5,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '6-9,', Y) <= star(X19, 5, 8) & (Y==(X1,X2,X3,X4,X5,X9,X7,X8,X6)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '7-8,', Y) <= star(X19, 6, 7) & (Y==(X1,X2,X3,X4,X5,X6,X8,X7,X9)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" >>> move(X19, '8-9,', Y) <= star(X19, 7, 8) & (Y==(X1,X2,X3,X4,X5,X6,X7,X9,X8)) move('["('f', 'X1')", "('f', 'X2')", "('f', 'X3')" # a solution to go from X to Y is a direct move, # or a solution from X to Z, followed by a direct move from Z to Y >>> Z19 = (Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9) >>> (solution[X,Y]==N) <= move(X, N, Y) solution[2]==(*,X,Y,N) <= move(X,N,Y) >>> (solution[X,Y]==N) <= (solution[X,Z19]==N1) & move(Z19,N2,Y) & (N==N1+N2) solution[2]==(*,X,Y,N) <= solution[2]==(*,X,'["('f >>> start_time = time.time() >>> print((solution[list('HAAHS*T*G'), list('HASHTAG**')]==N) >= N) 7-8,5-6,2-5,2-3,3-6,5-6,5-8,8-9,7-8, # ?? prints 5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8, >>> print("Computed in %f seconds" % (time.time() - start_time)) Computed in 91.675539 seconds # For better performance, X19 would be a string, and 'move' would be implemented # with a Python Resolver </pre> 《<a href="https://bitbucket.org/pcarbonn/pydatalog/src/280de5f8ef28dca2a584523080d427ddc597f712/pyDatalog/examples/hashtag_optimized.py?at=default">hashtag_optimized.py</a>》 <pre class="lang:sh decode:true ">pi@raspberrypi ~](http://www.freesandal.org/wp-content/ql-cache/quicklatex.com-1fdc852b36d559cc65c8e56278d81615_l3.png "Rendered by QuickLaTeX.com")
python3
Python 3.2.3 (default, Mar 1 2013, 11:53:50)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from pyDatalog import pyDatalog, pyEngine
>>> import time
>>> pyDatalog.create_terms('solution,move,X,Y,Z, Path,Path1,Path2, Steps,Steps1,Steps2')
# valid moves are exchange of 1<->2, 1<->4, ...
>>> @pyDatalog.predicate()
... def move3(X,N,Y):
... for n1,n2 in ((0,1),(0,3),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)):
... if X.id[n1]=='*' or X.id[n2]=='*':
... y = list(X.id)
... y[n1], y[n2] = y[n2], y[n1]
... yield (X.id, '%s-%s,' % (n1+1, n2+1), ''.join(y))
...
# a solution to go from X to Y is a direct move,
# or a solution from X to Z, followed by a direct move from Z to Y
>>> (solution[X,Y]==(Steps,Path)) <= ( (solution[X,Z]==(Steps1,Path1)) & move(Z,Steps2,Y)
... )
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> (solution[X,Y]==(Steps,Path)) <= ( (solution[X,Z]==(Steps1,Path1)) & move(Z,Steps2,Y) & (Path==Path1+[Z]) & (Steps==Steps1+Steps2))
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> (solution[X,Y]==(Steps,Path)) <= move(X, Steps, Y) & (Path==[])
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> start_time = time.time()
>>> print((solution['HAAHS*T*G', 'HASHTAG**']==(Steps,Path)) >= Steps)
5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8,
# prints 5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8,
>>> print("Computed in %f seconds" % (time.time() - start_time))
Computed in 54.467103 seconds
現在的問題是這兩個程式『都對』嗎？還是某一個『有錯』的呢？我們要如何『確認』的耶！
