הצלחתי גם ברמה 45 - זה היה יותר קשה למחשב כי הגיע למקסימום עומק רקורסיה (אלף מחזורים) בדוגמא שלהלן נראה איך אפשר למתוח את גבול עומק הרקורסיה כדי לקבל קצת יותר כוח: הקוד: from copy import deepcopy #זה מיועד להעתקה של רשימות בתוך רשימות import sys #זה על מנת להגדיל את מחזורי הרקורסיה sys.setrecursionlimit(1000) Grid=[[10,7,1,10],[1,5,7,10],[6,2,2,1],[3,4,10,4],[8,7,5,3],[7,1,6,2],[5,4,3,4],[3,5,8,8],[2,6,8,6],[],[]] #Grid זה שורת המבחנות שלנו כאשר כל מספר מייצג צבע # מספרי הצבעים בצילום def MovePossibilities (alltubes): """ הפונקציה הזאת מסייעת לנו למצוא את כל האפשריות השונות להעביר כדור אחד ממבחנה אחת לאחרת """ g=deepcopy(alltubes) possgrid=[] #לכאן נזרוק את כל הצירופים של זוגות מבחנות שכדורים יכולים לעבור מאחת לאחרת grids=[] #כאן אנו אוספים את כל המציאויות (שבע מבחנות בכל מציאות) האפשריות כתוצאה ממה שלמדנו קודם for ind,t in enumerate (g): for i, o in enumerate(g): if i!=ind: if len(t) > 0 and len(o) < 4 and (len(o) == 0 or t[-1] == o[-1]): possgrid.append([ind,i])#אנו אוספים רק את האינדקסים של המבחנות שמזיזות כדורים for i in possgrid: g[i[1]].append(g[i[0]].pop()) grids.append(g)#לכאן מצרפים סטים של 7 מבחנות אפשריות בכל פעם g=deepcopy(alltubes)#זה מאפשר לאפס את התמונה על מנת שנמשיך בסדר שקבענו מראש מהמציאות הראשונה return grids def Complete(tube):#בודק אם מבחנה מושלמת = ריקה או עם ארבעה כדורים באותו צבע state=0 if len(tube)==0 or (len(tube)==4 and tube[0]==tube[1]==tube[2]==tube[3]): state=1 return state def Check (grid):#בודק אם סט מבחנות מושלם for tube in grid: if Complete(tube)==1: continue else: return 0 return 1 glib=[] #את זה חייבים כי אחרת מקבלים אופציות שחוזרות על עצמן כדור עובר בלי סוף ממבחנה לאחרת ובחזרה def Solve (grid): global glib if Check(grid): print("Finished:") for t in grid: print(t) print("Very Good!") quit() for g in (MovePossibilities(grid)): if g not in glib:#זה כאמור לעיל כדי שלא יהיה לופ אינסופי של אופציות גרועות שחוזרות על עצמן בלי סוף glib.append(g) print(g) Solve(g) Solve(Grid)

ההסבר לקוד: from copy import deepcopy #זה מיועד להעתקה של רשימות בתוך רשימות Grid=[[2,3,2,1],[2,3,4,1],[1,3,5,5],[4,5,3,2],[4,1,5,4],[],[]] #Grid זה שורת המבחנות שלנו כאשר כל מספר מייצג צבע # 1=red, 2=purple, 3=green, 4=blue, 5= yellow def MovePossibilities (alltubes): """ הפונקציה הזאת מסייעת לנו למצוא את כל האפשריות השונות להעביר כדור אחד ממבחנה אחת לאחרת """ g=deepcopy(alltubes) possgrid=[] #לכאן נזרוק את כל הצירופים של זוגות מבחנות שכדורים יכולים לעבור מאחת לאחרת grids=[] #כאן אנו אוספים את כל המציאויות (שבע מבחנות בכל מציאות) האפשריות כתוצאה ממה שלמדנו קודם for ind,t in enumerate (g): for i, o in enumerate(g): if i!=ind: if len(t) > 0 and len(o) < 4 and (len(o) == 0 or t[-1] == o[-1]): possgrid.append([ind,i])#אנו אוספים רק את האינדקסים של המבחנות שמזיזות כדורים for i in possgrid: g[i[1]].append(g[i[0]].pop()) grids.append(g)#לכאן מצרפים סטים של 7 מבחנות אפשריות בכל פעם g=deepcopy(alltubes)#זה מאפשר לאפס את התמונה על מנת שנמשיך בסדר שקבענו מראש מהמציאות הראשונה return grids def Complete(tube):#בודק אם מבחנה מושלמת = ריקה או עם ארבעה כדורים באותו צבע state=0 if len(tube)==0 or (len(tube)==4 and tube[0]==tube[1]==tube[2]==tube[3]): state=1 return state def Check (grid):#בודק אם סט מבחנות מושלם for tube in grid: if Complete(tube)==1: continue else: return 0 return 1 glib=[] #את זה חייבים כי אחרת מקבלים אופציות שחוזרות על עצמן כדור עובר בלי סוף ממבחנה לאחרת ובחזרה def Solve (grid): global glib if Check(grid): print("Finished:") for t in grid: print(t) print("Very Good!") quit() for g in (MovePossibilities(grid)): if g not in glib:#זה כאמור לעיל כדי שלא יהיה לופ אינסופי של אופציות גרועות שחוזרות על עצמן בלי סוף glib.append(g) print(g) Solve(g) Solve(Grid) """ כך נראה החלק האחרון של הפתרון [[5, 5, 5], [3, 3, 3, 3], [4], [5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[5, 5], [3, 3, 3, 3], [4], [5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[5], [3, 3, 3, 3], [4], [5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[], [3, 3, 3, 3], [4], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3], [3, 3, 3], [4], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3], [3, 3], [4], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3, 3], [3], [4], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3, 3, 3], [], [4], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3, 3, 3], [4], [], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3, 3], [4], [3], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3, 3], [4], [3, 3], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[3], [4], [3, 3, 3], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[], [4], [3, 3, 3, 3], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[4], [], [3, 3, 3, 3], [5, 5, 5, 5], [4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] [[], [], [3, 3, 3, 3], [5, 5, 5, 5], [4, 4, 4, 4], [1, 1, 1, 1], [2, 2, 2, 2]] Finished: [] [] [3, 3, 3, 3] [5, 5, 5, 5] [4, 4, 4, 4] [1, 1, 1, 1] [2, 2, 2, 2] Very Good! """

קוד משופר לראות את הצורות ברור יותר: import time ct = time.time() import copy import matplotlib.pyplot as plt z=[] """ red =10 green=30 yellow=20 blue=40 empty pin=minus """ Board=[[0,-40,0,0,0,0,0,0], [-10,-20,0,0,0,0,0,0], [0,0,0,0,-20,-30,0,0], [0,0,0,0,0,-30,-40,0]] #shapes: R=[[10,1,0],[1,0,0],[10,0,0]] P=[[6,6,6],[0,40,40],[0,0,0]] Z=[[0,2,0],[2,11,0],[2,0,0]] I=[[20,0,0],[3,0,0],[3,0,0]] L=[[5,0,0,0],[41,0,0,0],[5,0,0,0],[5,0,0,0]] V=[[7,30,0],[0,30,0],[0,0,0]] X=[[0,21,0],[4,4,21],[0,0,21]] T=[[8,8,31],[0,31,0],[0,0,0]] def rotateMatrix(matx): N=len(matx[0]) mat = copy.deepcopy(matx) # Consider all squares one by one for x in range(0, 2): # Consider elements in group # of 4 in current square for y in range(x, N - x - 1): # store current cell in temp variable temp = mat[x][y] # move values from right to top mat[x][y] = mat[y][N - 1 - x] # move values from bottom to right mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y] # move values from left to bottom mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x] # assign temp to left mat[N - 1 - y][x] = temp return mat def allShapeForms(shape): s = [] s.append(shape) cp = copy.deepcopy(shape) for i in range(3): x = rotateMatrix(cp) s.append(x) cp = x cp = [] for item in shape: cp.append(item[::-1]) s.append(cp) for i in range(3): x = rotateMatrix(cp) s.append(x) cp = x return s def fitForm2Board (form,tempboard): board=copy.deepcopy(tempboard) combinationFormList=[] collision = 0 for y in range(4): for x in range (8): for index, row in enumerate(form): for ind, cell in enumerate(row): if cell != 0: if (index+y<4 and ind+x<8) and (board[index+y][ind+x] == 0 or board[index+y][ind+x] == -cell or (board[index+y][ind+x]-1) == -cell): board[index+y][ind+x] = cell else: collision += 1 if collision > 0: collision = 0 board = copy.deepcopy(tempboard) else: combinationFormList.append(board) board =copy.deepcopy(tempboard) return combinationFormList def print2d(mat): for item in mat: print(item) #return all bords: def allShapePossibilities (shape,board): allposs=[] for item in allShapeForms(shape): for b1 in fitForm2Board(item, board): allposs.append(b1) return allposs for b1 in allShapePossibilities(X,Board): for b2 in allShapePossibilities(I,b1): for b3 in allShapePossibilities(P,b2): for b4 in allShapePossibilities(L,b3): for b5 in allShapePossibilities(R,b4): for b6 in allShapePossibilities(Z,b5): for b7 in allShapePossibilities(T,b6): for b8 in allShapePossibilities(V,b7): print2d(b8) print(time.time()-ct) z=b8 for ind, row in enumerate (z): for index, num in enumerate (row): if num==10: z[ind][index]=20 if num==1: z[ind][index]=21 if num==11: z[ind][index]=30 if num==2: z[ind][index]=31 if num==20: z[ind][index]=60 if num==3: z[ind][index]=61 if num==21: z[ind][index]=70 if num==4: z[ind][index]=71 if num==30: z[ind][index]=40 if num==7: z[ind][index]=41 if num==31: z[ind][index]=10 if num==8: z[ind][index]=11 if num==40: z[ind][index]=30 if num==6: z[ind][index]=31 if num==41: z[ind][index]=50 if num==5: z[ind][index]=51 fig = plt.figure() ax = fig.add_subplot(111) ax.imshow(z, extent=[1, 8, 1, 4], interpolation='none') plt.show() quit()

חקירה של מספר המהלכים הדרוש מעלה שמספר המהלכים הדרוש הוא הוא 2X+1 ממספר המהלכים (X) הדרוש למספר טבעות בשלב הקודם הקטן יותר ב- 1. כלומר - עבור מגדל עם 3 טבעות דרושים 7 מהלכים, ל- 4 טבעות דרושים 15 מהלכים, ל-5 טבעות דרושים 31 מהלכים וכו'. בסיפור המקורי של המנזר בהאנוי דובר על 64 טבעות. שצריך להזיז לפי הכללים לעמוד שלישי דרך עמוד שני. מספר המהלכים הדרוש: 18,446,744,073,709,551,615 אם מזיזים טבעת אחת בכל שנייה, ידרשו לנזיר - בערך 584 מיליארד שנה.

פתרון רקורסיבי המכיל שלושה שלבים ושתי רקורסיות, הרעיון הוא לחלק את הבעיה לסדרה של בעיות קטנות יותר, אם למשל יש לי 3 טבעות להזיז לעמוד הימני ביותר, אני יודע שאני צריך להזין את שתי הטבעות העליונות לעמוד האמצעי, וכך אני אוכל להזיז את הטבעות האחרונה ליעד שלה, לאחר השלב הזה אני נותר עם מספר טבעות קטן באחד אבל על עמוד אחר (העמוד האמצעי ולא העמוד השמאלי) כך שהעמוד השמאלי הוא הופך להיות עמוד הביניים בדרך ליעד לכן לאחר השלב השני של הזזת הטבעת הבודדות (שזה המהלך היחיד אותו אנו רוצים להדפיס) אנו מפעילים שוב את הפונקציה המקורית רק שהפעם מהעמוד שהיה במקור עמוד הביניים ליעד: def tower(n,s,i,d):#n=מספר הטבעות s=מקור הטבעות i=עמוד מקשר d=היעד של הטבעות if n==0: pass else: tower(n-1,s,d,i) print(s,d) tower(n-1,i,s,d) tower(5,"a","b","c") #for 5 rings >>> b c #- c-ל b-הטבעת הראשונה עוברת מ a c b a c b c a b a b c a c a b c b a c b a b c a c

הפתרון שלנו ליצירת מודל של החידה עושה שימוש בספריית random המאפשרת, בין היתר, ערבוב, של רשימות. לאחר שיצרנו מודל של החידה, אנו רואים שהכדור האחרון שיישאר בשק הוא כדור כחול. (אלא אם נשנה את מספר הכדורים הלבנים למספר אי זוגי) import random b='b'*10 w='w'*10 lista=[i for i in (b+w)] random.shuffle(lista) print(lista) while len (lista)>1: a=lista.pop() b=lista.pop() if a==b: lista.append('b') else: lista.append('w') print(lista) random.shuffle(lista) כך נראה הפתרון שלנו - ['w', 'b', 'w', 'b', 'b', 'w', 'w', 'b', 'b', 'w', 'w', 'b', 'w', 'w', 'w', 'b', 'b', 'w', 'b', 'b'] ['w', 'b', 'w', 'b', 'b', 'w', 'w', 'b', 'b', 'w', 'w', 'b', 'w', 'w', 'w', 'b', 'b', 'w', 'b'] ['w', 'b', 'w', 'w', 'b', 'b', 'b', 'w', 'b', 'b', 'w', 'b', 'w', 'w', 'w', 'w', 'w', 'b'] ['w', 'b', 'w', 'w', 'w', 'b', 'w', 'w', 'w', 'b', 'b', 'b', 'w', 'b', 'w', 'b', 'w'] ['w', 'b', 'w', 'w', 'w', 'b', 'w', 'w', 'w', 'b', 'b', 'w', 'b', 'w', 'b', 'w'] ['w', 'b', 'w', 'w', 'b', 'w', 'b', 'b', 'w', 'w', 'b', 'w', 'b', 'w', 'b'] ['b', 'b', 'w', 'b', 'w', 'b', 'w', 'w', 'b', 'w', 'w', 'w', 'w', 'b'] ['w', 'b', 'w', 'b', 'w', 'b', 'b', 'w', 'w', 'w', 'b', 'b', 'b'] ['b', 'b', 'w', 'b', 'w', 'w', 'w', 'b', 'w', 'b', 'b', 'w'] ['b', 'w', 'w', 'b', 'w', 'b', 'b', 'w', 'b', 'w', 'w'] ['b', 'w', 'w', 'w', 'w', 'w', 'b', 'b', 'w', 'b'] ['b', 'w', 'w', 'b', 'w', 'w', 'b', 'b', 'b'] ['w', 'b', 'b', 'b', 'b', 'w', 'w', 'w'] ['w', 'b', 'w', 'w', 'b', 'w', 'b'] ['w', 'b', 'w', 'w', 'b', 'w'] ['w', 'w', 'b', 'b', 'b'] ['b', 'b', 'w', 'w'] ['b', 'w', 'w'] ['b', 'b'] ['b']

פתרון הכולל 16 מהלכים - המודל שלנו מסתמך על רשימה שהתא הראשון שלה למטה משמאל, והמספרים נעים במעגל עד לתא השמיני שהוא מימין לתא הראשון. (האמצע לא חשוב לחידה הזאת). class Night: def __init__(self,color,location,grid): self.color=color self.location=location self.grid=grid self.grid[self.location]=f"{self.color}{self.location}" def __str__(self): return f"{self.color}{self.location}" def posibleClockeiseMoves(self): if self.location == 1: return 4 if self.location == 2: return 5 if self.location == 3: return 6 if self.location == 4: return 7 if self.location == 5: return 8 if self.location == 6: return 1 if self.location == 7: return 2 if self.location == 8: return 3 def posible_moves(self): lista=[] if self.location==1: for i in (4,6): if self.grid[i]==0: lista.append(i) return lista if self.location==2: for i in (5,7): if self.grid[i] == 0: lista.append(i) return lista if self.location==3: for i in (8,6): if self.grid[i] == 0: lista.append(i) return lista if self.location==4: for i in (1,7): if self.grid[i] == 0: lista.append(i) return lista if self.location==5: for i in (2,8): if self.grid[i] == 0: lista.append(i) return lista if self.location==6: for i in (1,3): if self.grid[i] == 0: lista.append(i) return lista if self.location==7: for i in (2,4): if self.grid[i] == 0: lista.append(i) return lista if self.location==8: for i in (3,5): if self.grid[i] == 0: lista.append(i) return lista def move_to(self,destiny): if grid[destiny] !=0: print(f"location {destiny} is occupide") else: self.grid[self.location]=0 self.location=destiny self.grid[self.location] = f"{self.color}{self.location}" grid=['Grid',0,0,0,0,0,0,0,0] w1=Night('w',1,grid) w2=Night('w',7,grid) b1=Night('b',3,grid) b2=Night('b',5,grid) allNights=[w1,w2,b1,b2] for night in allNights: n=night.location grid[n]=night.__str__() nightDict={'w1':w1.__str__(),'w2':w2.__str__(),'b1':b1.__str__(),'b2':b2.__str__()} n=0 for i in range(4): for night in allNights: p=night.posibleClockeiseMoves() grid=night.grid if grid[p]==0: night.move_to(p) print(grid) n+=1 if grid[3]=='w3' and grid[5]=='w5' and grid[1]=='b1' and grid[7]=="b7": print(f"works!!! {n} moves") break הפתרון לאחר הרצת התוכנית נראה כך - ['Grid', 0, 0, 'b3', 'w4', 'b5', 0, 'w7', 0] ['Grid', 0, 'w2', 'b3', 'w4', 'b5', 0, 0, 0] ['Grid', 0, 'w2', 0, 'w4', 'b5', 'b6', 0, 0] ['Grid', 0, 'w2', 0, 'w4', 0, 'b6', 0, 'b8'] ['Grid', 0, 'w2', 0, 0, 0, 'b6', 'w7', 'b8'] ['Grid', 0, 0, 0, 0, 'w5', 'b6', 'w7', 'b8'] ['Grid', 'b1', 0, 0, 0, 'w5', 0, 'w7', 'b8'] ['Grid', 'b1', 0, 'b3', 0, 'w5', 0, 'w7', 0] ['Grid', 'b1', 'w2', 'b3', 0, 'w5', 0, 0, 0] ['Grid', 'b1', 'w2', 'b3', 0, 0, 0, 0, 'w8'] ['Grid', 0, 'w2', 'b3', 'b4', 0, 0, 0, 'w8'] ['Grid', 0, 'w2', 0, 'b4', 0, 'b6', 0, 'w8'] ['Grid', 0, 0, 0, 'b4', 'w5', 'b6', 0, 'w8'] ['Grid', 0, 0, 'w3', 'b4', 'w5', 'b6', 0, 0] ['Grid', 0, 0, 'w3', 0, 'w5', 'b6', 'b7', 0] ['Grid', 'b1', 0, 'w3', 0, 'w5', 0, 'b7', 0] works!!! 16 moves

פתרון שמצאתי כשרק התחלתי ללמוד פייתון - מי נותן פתרון רקורסיבי ? r=[i for i in range(1,9)]#n discs on the first stick need to be moved to the third one (range(1,9)=8 discs a=r[::-1] b=[] c=[] l=a[0] pop=0 count=0 last_move=('a','b') def move(a,b): global pop,last_move, my_dict pop=a.pop() b.append(pop) last_move=(a,b) def posible_moves (): global last_move ,a,b,c if b==[] and c==[]: return (a,b) if l%2==0: if a==[] and c==[]: return (b,a) if last_move==(a,b): if c==[]: return (b,c) if c[-1]>b[-1]: return (b, c) if c[-1]<b[-1]: return (c,b) if last_move==(b,a): if c==[]: return (b,c) if b==[]: return (c,b) if c[-1]>b[-1]: return (b,c) if c[-1] < b[-1]: return (c,b) if last_move==(b,c): if b==[]: return (a,b) if a==[]: return (b,a) if b[-1]>a[-1]: return (a,b) if b[-1] < a[-1]: return (b,a) if last_move == (c, b): if a == []: return (b, a) if b[-1] > a[-1]: return (a, b) if b[-1] < a[-1]: return (b, a) while len (c)<l: pm1= posible_moves()[0] pm2=posible_moves()[1] move(pm1,pm2) count+=1 print('',a,'\n',b,'\n',c,'\n',count,' moves') הפתרון ארוך והוא מתחיל כך: [8,7,6,5,4,3,2,1] [ ] [ ] ומסתיים כך: [ ] [ ] [8,7,6,5,4,3,2,1] כל רשימה מייצגת עמוד, וכל מספר מייצג טבעת בגודל שונה, המספר הגדול ביותר הוא כמובן הטבעת הגדולה ביותר. בסוף התהליך התוכנית גם סופרת כמה מהלכים בוצעו. תעתיקו ותריצו ותגלו כמה זמן היה לוקח לכם לפתור את החידה.

הפתרון מורכב משתי פונקציות בלבד - הראשונה מוצאת מה האפשרויות הנובעות מכל מצב - כאשר המצב ההתחלתי שלנו הוא [12,0,0] כלומר כלי אחד מלא ב- 12 ליטר מים ושני כלים ריקים. כל רשימה כוללת שלושה איברים, השמאלי ביותר מייצג כלי בנפח 12 ליטר, האמצעים כלי בנפח 8 ליטר והימני כלי בנפח 5 ליטר. כל מספר ברשימה מייצג כמה מים יש בכלי. def desert_options(lista): options=[] max_opt=[] max_opt.append(12-lista[0]) max_opt.append(8-lista[1]) max_opt.append(5-lista[2]) for place, item in enumerate (lista): for p,i in enumerate(max_opt): if item>0: if place !=p: if i>0: if item>i: opt=lista[::] #מוכרחים לייצר אובייקט חדש ולא מצביע בלבד opt[place]=item-i opt[p]=opt[p]+i options.append(opt) if item<i: opt = lista[::] opt[place]=0 opt[p]=opt[p]+item options.append(opt) return options answer = [[12,0,0]] #השלב ההתחלתי שלנו def solve_desert(): #הפונקציה השניה הפותרת את החידה if [6,6,0] in answer: #ששה ליטרים בשני הכלים הגדולים זה מה שמחפשים print(answer) exit() else: for item in desert_options(answer[-1]): #אנו תמיד עובדים על האיבר האחרון בתהליך if item not in answer: #על מנת שלא נשוב לנקודה שכבר היינו בה answer.append(item) solve_desert() #זו הרקורסיה answer.pop() #זה מחזיר את המצב לקדמותו solve_desert() #כאן קוראים לפונקציה הפונקציה הרקורסיבית שלנו מכילה תנאי מפסיק והוא שיהיה שלב בתהליך השווה ל- [6,6,0] כלומר חילקנו 12 ליטרים של מים בין שני המתייבשים שלנו. הפתרון הראשון המתקבל (שלאחריו הפונקציה מפסיקה לעבוד הוא - answer: >>> [[12, 0, 0], [4, 8, 0], [0, 8, 4], [8, 0, 4], [8, 4, 0], [3, 4, 5], [3, 8, 1], [11, 0, 1], [11, 1, 0], [6, 1, 5], [6, 6, 0]] אבל זה אינו הפתרון הקצר ביותר - הוא כולל עשרה שלבים אחרי המצב ההתחלתי. אם נותנים לפונקציה לרוץ מגלים גם פתרון יותר קצר - answer: [[12, 0, 0], [4, 8, 0], [4, 3, 5], [9, 3, 0], [9, 0, 3], [1, 8, 3], [1, 6, 5], [6, 6, 0]] הכולל שבעה שלבים אחרי המצב ההתחלתי 12,0,0 - קבלו משימה לשנות את הקוד כך שיפלוט את הפתרון הקצר ביותר בלבד.

טבע פרסם פתרון בפוסט נפרד (משום מה)

כל הכבוד אביר

כתבנו רבות על הספרייה itertools ונפלאותיה, כמו על יכולתה, בעיקר כאשר לא עוסקים ברשימה ארוכה מידי, לייצר במהירות את כל האפשרויות (במקרה שלנו לסידור החיות בשורה) כאשר אין חזרה על חיה אחת פעמיים (במקרה הזה המתודה נקראת permutations). כל מה שנותר לנו לעשות הוא לבחון את קיום כל תנאי החידה ובום... יש פתרון - import itertools zoo=["cat","dog","elefant","horse","giraffe","lion","monkey"] def check_zoo(zoo): if zoo.index("cat")-zoo.index("dog")==1: if zoo.index("giraffe")>zoo.index("elefant")>zoo.index("horse") or zoo.index("horse")>zoo.index("elefant")>zoo.index("giraffe"): if zoo.index("lion")==3: if abs(zoo.index("dog")-zoo.index("monkey"))==2: if abs(zoo.index("giraffe")-zoo.index("dog"))==4: if zoo.index("cat")>zoo.index("horse"): return True return False zoo_permutations=itertools.permutations(zoo) for line in zoo_permutations: if check_zoo(line): print(line) הפתרון היחיד המתקבל - ('giraffe', 'elefant', 'horse', 'lion', 'dog', 'cat', 'monkey')

טוב אם ניסיתם במשך כמה ימים ולא הצלחתם , הנה פתרון באמצעות מחלקה -class - וגם רקורסיה - וגם backtracking . לא פתרון של שתי שורות (למי שיש לו רעיון שידביק כאן בשמחה אני לא משלם לפי מספר העמודים באתר), אלא פתרון כזה שאפשר, אולי, ללמוד ממנו משהו - האסטרטגיה של- backtracking מחפשת את הפתרון הנכון מבין האופציות שיש בכל סיטואציה (במדריך יש אנלוגיה של עץ וענפים שזה סבבה), כאשר לא מוצאת בענף מסוים, משיבה את המצב לקדמותו וממשיכה לחפש (למשל אם הסתבר שלהזיז צפרדע לא נותן פתרון, אזי בסיבוב הבא, באותה סיטואציה, התוכנית תקפיץ קרפדה (לא לבעלי קיבה חלשה). תחילה מקימים מחלקה בשם Creature המתאימה לכל הייצורים האמפיביים, הן צפרדעים והן קרפדות. המחלקה כוללת את הפונקציות הבאות __init__ המספרת לנו מה יש במחלקה - type הוא attribute המטפל בסוג האמפיבי שלנו, צפרדע "f" או קרפדה "t" (באנגלית toad). בהמשך location מטפלת במיקום של הייצור בביצה שלנו שהיא רשימה בשם line (האיבר הראשון משמאל הוא [line[0 כך שהמיקום של מי שנמצא שם הוא 0). על מנת שנוכל להזיז את הייצורים יש לנו מתודות (שהן פונקציות בתוך מחלקה) כמו move , jump undo_move המותאמות לכל ייצור בנפרד. יש לנו מתודה option המתארת את אפשרות התזוזה של כל ייצור, ויש גם מתודה __repr__ כדי לייצג באופן הולם את הדרך שבה אנו רוצים לראות את הייצור כאשר נבקש להדפיס אותו למשל. class Creature: def __init__(self,type,location,line): self.type=type self.location=location self.line=line def move(self): self.last_location=self.location if self.type=="f" and self.location<6 and self.line[self.location+1]==0: self.line[self.location+1]=self self.line[self.location]=0 self.location += 1 if self.type == "t" and self.location>0 and self.line[self.location-1]==0: self.line[self.location - 1] = self self.line[self.location] = 0 self.location -= 1 def jump(self): self.last_location = self.location if self.type == "f" and self.location<5 and self.line[self.location+1].type=="t" and self.line[self.location + 2] == 0: self.line[self.location + 2] = self self.line[self.location] = 0 self.location += 2 if self.type == "t" and self.location>1 and self.line[self.location-1].type=="f" and self.line[self.location - 2] == 0: self.line[self.location - 2] = self self.line[self.location] = 0 self.location -= 2 def option(self): option=[] if self.type == "f" and self.location<6 and self.line[self.location + 1] == 0: option.append("m") elif self.type == "t" and self.location>0 and self.line[self.location - 1] == 0: option.append("m") elif self.type == "f" and self.location<5 and self.line[self.location + 1].type == "t" and self.line[self.location + 2] == 0: option.append("j") elif self.type == "t" and self.location>1 and self.line[self.location - 1].type == "f" and self.line[self.location - 2] == 0: option.append("j") else: option.append("n") return option[-1] def undo_move(self): if self.line[self.last_location]==0: self.line[self.location]=0 self.line[self.last_location]=self self.location,self.last_location=self.last_location,self.location def __repr__(self): return f"{self.type}{self.location}" #: מכאן אנו מתחילים לייצר את המופעים של המחלקה שלנו Line=[] Line.append(Creature("f",0,Line)) Line.append(Creature("f",1,Line)) Line.append(Creature("f",2,Line)) Line.append(0) Line.append(Creature("t",4,Line)) Line.append(Creature("t",5,Line)) Line.append(Creature("t",6,Line)) #-זו פונקציה שאומרת מתי סיימנו עם החידה הזו def check_solve(line): if line[3]==0: if line[0].type=="t" and line[1].type=="t"and line[2].type=="t" and line[4].type=="f" and line[5].type=="f" and line[6].type=="f": return True # -כאן אנו מתחילים עם הפונקציה הרקורסיבית שפותרת את החידה def solve (line): l=line[::] #מתוך הרשימה אנו יוצרים אובייקט חדש ולא רק מצביע נוסף לאותה רשימה print(line) if check_solve(line): print(line,"the end") exit() else: for p,v in enumerate(l): #כאן מתחילים את האיטרציה על האובייקט החדש שהופק מהרשימה moj = 0 #זה מיועד להראות שאכן ביצענו קפיצה או תזוזה של משהו if v==0 or v.option()=="n": #כאשר אנו נתקלים ב-0 או כשאין אפשרות תזוזה ממשיכים continue z = l.index(0) #המיקום של 0 ברשימה ילמד אותנו לאן עתיד היצור לזוז if v.option()=="j": line[p].jump() moj+=1 elif v.option() == "m": line[p].move() moj += 1 solve(line) #זאת הרקורסיה בהתגלמותה if moj>0: line[z].undo_move() #כך משיבים הכל למקום כשלא הושלם הפתרון solve(Line) #כך משתמשים במחלקה שבנינו >>> הפתרון כתוצאה מהרצת התוכנית נראה כך - [f0, f1, f2, 0, t4, t5, t6] [f0, f1, 0, f3, t4, t5, t6] [f0, 0, f2, f3, t4, t5, t6] [0, f1, f2, f3, t4, t5, t6] [f0, f1, t2, f3, 0, t5, t6] [f0, f1, t2, 0, f4, t5, t6] [f0, 0, t2, f3, f4, t5, t6] [0, f1, t2, f3, f4, t5, t6] [t0, f1, 0, f3, f4, t5, t6] [t0, 0, f2, f3, f4, t5, t6] [t0, f1, 0, f3, f4, t5, t6] [t0, 0, f2, f3, f4, t5, t6] [t0, f1, f2, t3, f4, 0, t6] [t0, f1, f2, t3, 0, f5, t6] [t0, f1, 0, t3, f4, f5, t6] [t0, 0, f2, t3, f4, f5, t6] [t0, t1, f2, 0, f4, f5, t6] [t0, t1, 0, f3, f4, f5, t6] [t0, t1, f2, 0, f4, f5, t6] [t0, t1, 0, f3, f4, f5, t6] [t0, t1, f2, f3, t4, f5, 0] [t0, t1, f2, f3, t4, 0, f6] [t0, t1, f2, 0, t4, f5, f6] [t0, t1, 0, f3, t4, f5, f6] [t0, t1, t2, f3, 0, f5, f6] [t0, t1, t2, 0, f4, f5, f6] [t0, t1, t2, 0, f4, f5, f6] the end זו לא הדרך הקצרה ביותר, אבל זו דרך לדעת שיש פתרון לחידה שלנו.

כל הכבוד טבע, הרעיון יפה מאוד. אם היית מנסה itertools. permutations או כל ורסיה אחרת העוברת על כל האפשרויות, היית מבין שזה יקח נצח, לכן לצמצם אפשרויות זו דרך מאוד יפה.