בחידה הזאת צריך להגיע מהמצב ההתחלתי כמתואר למעלה למצב הסופי שגם הוא מתואר למעלה. הכללים של החידה -כל יצור אמפיבי יכול לנוע למשבצת ריקה הסמוכה אליו או לדלג מעל יצור אמפיבי אחר. צפרדעים יכולות לנוע ימינה בלבד וקרפדות יכולות לנוע שמאלה בלבד. התנועה יכולה להתבצע בשני אופנים : צפרדע יכולה לגלוש למשבצת ריקה סמוכה שנמצאת מימין בלבד ואילו קרפדות יכולות לגלוש למשבצת ריקה סמוכה לשמאל בלבד. צפרדעים וקרפדות יכולות גם לדלג, (זה כל הקטע בבחירת דו חי מהסוג הזה) כמובן כל ייצור לכיוון שמותר לו, צפרדעים רק ימינה וקרפדות רק שמאלה. הדילוג יכול להתבצע אך ורק כאשר יש בסמוך לכיוון הדילוג ייצור מסוג אחר ויש גם אחריו משבצת ריקה. כלומר, צפרדע לא יכולה לדלג מעל צפרדע וקרפדה לא יכולה לדלג מעל קרפדה (בין אם יש אחרי משבצת ריקה ובין אם לא). אי אפשר לדלג על יותר מייצור אחד (צפרדע לא יכולה לדלג מעל שתי קרפדות) ואי אפשר לדלג מעל ייצור שאין אחריו משבצת ריקה (וכל אחת כזכור רק לכיוון שהיא יודעת לדלג).
צריך לבנות תוכנית, בפייתון (כאילו בזה אנו עוסקים כאן), שתציג מודל של החידה. ותציג את שלבי הפתרון מהמצב ההתחלתי למצב הסופי שבו הצפרדעים והקרפדות מחליפות מקומות.
הראשון שיפתור עם תוכנית מרשימה יזכה בתהילת עולם (בקנה המידה המצומצם יותר של קומץ האנשים הנדירים החברים באתר הזה בפורום).
הפתרון שלי עובד עבור כל n צפרדעים ולוח של 2n+1 - במקרה הזה עבור 5 צפרדעים וחמש קרפדות המחליפות מקום. בפתרון שלי קרפדות מסומנות ב- 0, צפרדעים מסומנות ב- 1 והמקום הריק ב- 2-
#Toads = 0 #Frogs = 1 #Empty Place = 2 class Frogs_and_Toads: def __init__(self, n): self.n = n self.board = [0 for i in range(n)] + [2]+ [1 for i in range(n)] self.solution = [1 for i in range(n)] + [2]+ [0 for i in range(n)] self.steps = [self.board[::]] self.solve() def pm(self, board): # bc stands for board copy - a copy of the board possible_moves = [] for place, item in enumerate(board): try: if item == 0: if board[place+1] == 2: bc = board[::] bc[place] = 2 bc[place+1] = 0 possible_moves.append(bc) if item == 1: if place != 0: if board[place-1] == 2: bc = board[::] bc[place] = 2 bc[place-1] = 1 possible_moves.append(bc) except: pass if place < len(board)-2: if item == 0 and board[place+1] == 1 and board[place+2] == 2: bc = board[::] bc[place] = 2 bc[place+2] = 0 possible_moves.append(bc) if place > 1: if item == 1 and board[place-1] == 0 and board[place-2] == 2: bc = board[::] bc[place] = 2 bc[place-2] = 1 possible_moves.append(bc) return possible_moves def solve(self): if self.solution in self.steps: for item in self.steps: print(item) exit() else: for item in self.pm(self.steps[-1]): self.steps.append(item) self.solve() self.steps.pop() Frogs_and_Toads(5)
>>>
[0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 2, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 2, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 1]
[0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 1]
[0, 0, 0, 2, 1, 0, 1, 0, 1, 1, 1]
[0, 0, 2, 0, 1, 0, 1, 0, 1, 1, 1]
[0, 0, 1, 0, 2, 0, 1, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 0, 1, 0, 2, 1, 1]
[0, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1]
[0, 0, 1, 0, 1, 0, 1, 2, 1, 0, 1]
[0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1]
[0, 0, 1, 2, 1, 0, 1, 0, 1, 0, 1]
[0, 2, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0]
[1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 0]
[1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 0]
[1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0]
[1, 2, 1, 0, 1, 0, 1, 0, 1, 0, 0]
[1, 1, 2, 0, 1, 0, 1, 0, 1, 0, 0]
[1, 1, 1, 0, 2, 0, 1, 0, 1, 0, 0]
[1, 1, 1, 0, 1, 0, 2, 0, 1, 0, 0]
[1, 1, 1, 0, 1, 0, 1, 0, 2, 0, 0]
[1, 1, 1, 0, 1, 0, 1, 2, 0, 0, 0]
[1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 2, 0, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 0, 2, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0]
הפתרון מראה את כל התהליך של החלפת המקומות בין הצפרדעים לקרפדות.
טבע ארבילי