משחק הקפיצות

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

אני אתחיל, כרגיל, בדוגמא.
בהינתן מערך  –

A = [1,2,0,3]

אפשר להגיע לאיבר הסופי.
המסלול יהיה 0,1,3 – התחלה באינדקס הראשון, קפיצה של 1 לאינדקס השני, קפיצה של 2 לאינדקס הרביעי והאחרון, וסיימנו.
עכשיו אני אנסה למצוא דוגמא שבה אי אפשר להגיע לאיבר הסופי.

B = [2, 1, 0, 1]

בדוגמא הזו אי אפשר להגיע לאיבר הסופי.
באיבר הראשון גודל הקפיצה המקסימלי הוא 2, ממנו יש שתי אפשרויות –

1. קופצים לאיבר השני, ממנו גודל הקפיצה המקסימלי הוא 1, ממנו מגיעים לאיבר השלישי, ממנו גודל הקפיצה המקסימלי הוא 0 ואז נתקעים.
2. קופצים לאיבר השלישי, ממנו גודל הקפיצה המקסימלי הוא 0 ואז נתקעים.

אפשר להסתכל על הבעיה הזו בצורה רקורסיבית –

אם היה לי מערך בגודל 1, האיבר הראשון שווה לאחרון וסיימתי –

JumpGame([1]) = True

אם היה לי מערך בגודל 2, שהאיבר הראשון בו גדול מ-1, יכולתי לקפוץ לאיבר השני, ולהריץ עליו את הפונקציה.

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

אני אכתוב את האלגוריתם הזה בקווים כללים –

def JumpGame(arr):
	if len(arr) == 1:
		return True
	if arr[0] == 0:
		return False
	for jump_size in range(1,arr[0]+1):
		if JumpGame(arr[i:]):
			return True
	return False

עכשיו, לבדוק את האלגוריתם על שתי הדוגמאות שנתתי למעלה.

JumpGame([1, 2,0,3]): len(arr) = 4 arr[0]=1 jump_size=1 call JumpGame([2,0,3]) JumpGame([2,0,3]): len(arr) = 3 arr[0]=2 jump_size=1 call JumpGame([0,3]) JumpGame([0,3]): len(arr) = 2 arr[0] = 0 return False JumpGame([2,0,3]): JumpGame([0,3]) = False jump_size=2 call JumpGame([3]) JumpGame([3]): len(arr) = 1 return True JumpGame([2,0,3]): JumpGame([3]) = True return True JumpGame([1, 2,0,3]): JumpGame([2,0,3]) = True return True

יאי, הדוגמא עובדת.

עכשיו אני אנסה את הדוגמא השנייה שאמור להחזיר False.

JumpGame([2, 1, 0, 1]): len(arr) = 4 arr[0] = 2 jump_size=1 call JumpGame([1, 0, 1]) JumpGame([1, 0, 1]): len(arr) = 3 arr[0] = 1 jump_size = 1 call JumpGame([0, 1]) JumpGame([0, 1]): len(arr) = 2 arr[0] = 0 return False JumpGame([1, 0, 1]): JumpGame([0, 1]) = False return False JumpGame([2, 1, 0, 1]): JumpGame([1, 0, 1]) = False jump_size = 2 call JumpGame([0, 1]) JumpGame([0, 1]) = False return False

הידד, הדוגמא עבדה, החזרתי False.

עוד נקודה חשובה שהתגלתה במהלך הבדיקה של הדוגמא היא שבקוד שלי יש קריאות שחוזרות על עצמן.

למשל הקריאה JumpGame(arr[0, 1]).

לכן, במקום לבצע את אותה הקריאה שוב ושוב, אפשר לאחסן את תוצאת הקריאה בזיכרון ואז לשלוף אותה משם. אני אוסיף את האחסון בזיכרון לאלגוריתם שלי.

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

(כרגיל, אני משתמשת פה בדוגמאות בזיכרון גלובלי לשם הנוחות של הכתיבה, אבל בקוד פייתון שלי אני אשתמש ב-class עם זיכרון).

global jumps = {}
def JumpGame(arr, i):
	if i == len(arr) - 1:
		return True
	if arr[i] == 0:
		return False
	for jump_size in range(1,arr[i]+1):
		if (i, jump_size) not in jumps:
			jumps[(i, jump_size)] = JumpGame(arr, i + jump_size)
		return jumps[(i, jump_size)]
	return False

אני אריץ שוב את הדוגמא האחרונה, כדי לראות שהזיכרון עובד כמו שציפיתי –

global jumps = {} JumpGame([2, 1, 0, 1],0): i != 3 arr[0] = 2 jump_size=1 jumps[(0,1)] = JumpGame(arr, 1) JumpGame([2, 1, 0, 1],1): i != 3 arr[1] = 1 jump_size = 1 jumps[(1,1)] = JumpGame(arr, 2) JumpGame([2, 1, 0, 1],2): i != 3 arr[2] = 0 return False JumpGame([2, 1, 0, 1],1): jumps[(1,1)] = False return False JumpGame([2, 1, 0, 1],0): jumps[(0,1)] = False jump_size=2 jumps[(0,2)] = JumpGame(arr, 2)

אוקי, אני רואה שמשהו לא כל כך הגיוני קרה פה –

הגעתי לנקודה בה הזיכרון אמור לשרת אותי, אני קוראת לקריאה שכבר קראתי לה – ריצה מהמקום השלישי במערך, אבל המפתח (0,2) לא נמצא לי בזיכרון.

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

אני אעדכן את האלגוריתם בהתאם.

global jumps = {}
def JumpGame(arr, i):
	if i == len(arr) - 1:
		jumps[i] = True
	elif arr[i] == 0:
		jumps[i] = False
	else:
	        for jump_size in range(1,arr[i]+1):
			if i + jump_size not in jumps:
				jumps[i + jump_size] = JumpGame(arr, i + jump_size)
	return jumps[i]

זה כבר נראה יותר הגיוני –

אני מתחילה מהאינדקס הראשון ומייצרת בעצם מערך שבכל אינדקס שלו יש True אם ניתן להגיע מהאינדקס הזה לקצה המערך או לא. האלגוריתם יסיים כאשר נמלא True או False לאינדקס 0, ונדע האם ניתן להגיע לקצה המערך מתחילתו.

אני אריץ את הדוגמאות שוב –

global jumps = {} JumpGame([2, 1, 0, 1],0): i != 3 arr[0] = 2 jump_size=1 jumps[1] = JumpGame(arr, 1) JumpGame([2, 1, 0, 1],1): i != 3 arr[1] = 1 jump_size = 1 jumps[2] = JumpGame(arr, 2) JumpGame([2, 1, 0, 1],2): i != 3 arr[2] = 0 return False JumpGame([2, 1, 0, 1],1): jumps[2] = False return False JumpGame([2, 1, 0, 1],0): jumps[1] = False jump_size=2 jumps[2] = False return False

מעולה. הדוגמא הזו עובדת, עכשיו אני אנסה שוב את הדוגמא הראשונה.

JumpGame([1, 2,0,3], 0): i != 3 arr[0] = 1 jump_size = 1 jumps[1] = JumpGame(arr, 1) JumpGame([1, 2,0,3], 1): i != 3 arr[1] = 2 jump_size = 1 jumps[2] = JumpGame(arr, 2) JumpGame([1, 2,0,3], 2): i != 3 arr[2] = 0 return False JumpGame([1, 2,0,3], 1): jumps[2] = False jump_size = 2 jump[3] = JumpGame(arr, 3) JumpGame([1, 2,0,3], 3): i == 3 return True JumpGame([1, 2,0,3], 1): jumps[3] = True return jumps[1] → Failure

אוי.

למה בעצם נכשלתי פה?

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

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

אני אוסיף את השורה המתאימה.

global jumps = {}
def JumpGame(arr, i):
	if i == len(arr) - 1:
		jumps[i] = True
	elif arr[i] == 0:
		jumps[i] = False
	else:
		jumps[i] = False
		for jump_size in range(1,arr[i]+1):
			if i + jump_size not in jumps:
				jumps[i + jump_size] = JumpGame(arr, i + jump_size)
			jumps[i] = jumps[i] or jumps[i + jump_size]
	return jumps[i]

אני אמשיך את הדוגמא שהתחלתי עם התיקון –

JumpGame([1, 2,0,3], 1): jumps[2] = False jumps[1] = False or False = False jump_size = 2 jump[3] = JumpGame(arr, 3) JumpGame([1, 2,0,3], 3): i == 3 return True JumpGame([1, 2,0,3], 1): jumps[3] = True jumps[1] = False or True = True return jumps[1]

אחלה. עכשיו נשאר לבדוק רק את מקרי הקיצון ואפשר להתחיל לקודד.

מערך ריק –

arr = [] JumpGame([],0): i != -1 arr[0] → Failure

לא ממש אמרו לי בשאלה מה לעשות במקרה של מערך ריק, אבל אני אניח שאני מחזירה False במקרה כזה.

מערך של תא אחד –

arr = [1] JumpGame([],0): i == 0 return True

מעולה.

מה לגבי מקרה שבו קפיצה מוציאה אותי מחוץ לגבולות המערך?

arr = [3,0,0]

המקרה הזה יכול היה להיות מסוכן, אבל איך שהאלגוריתם בנוי עכשיו הוא פשוט לא יקרה.

למה?

נניח שיש קפיצה מהסוג הזה – jump_size = 3 שמוציאה אותי מחוץ לגבולות המערך וגורמת לי לקרוא ל-

JumpGame([3,0,0],3)

אז לפני שאני אגיע אליה בהכרח אעבור ב-jump_size = 2, אגיע לאיבר האחרון ונסיים.

כיוון שהקפיצות תמיד מתחילות מ – jump_size = 1, ואין קפיצות מהאיבר האחרון במערך, תמיד לפני קפיצה שמוציאה אותי מגבולות המערך תגיע קפיצה שמביאה אותי לאיבר האחרון ואז אני אעצור.

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

הסיבוכיות מקום שלי מתחלקת ל-2 חלקים –

הזיכרון עזר שלי, jumps בו אני מחזיקה תוצאות של קפיצות שכבר עשיתי, ועומק הרקורסיה.

1. jumps מחזיק משתנה בוליאני לכל אינדקס במערך, ולכן הוא בגודל N לכל היותר.
2. עומק הרקורסיה שלי יהיה לכל היותר N כי מכל נקודה במערך אני יכולה להחזיק לכל היותר N קפיצות פתוחות קדימה (מעבר לזה בהכרח אעבור את גודל המערך, וכמו שכתבתי למעלה זה לא יכול לקרות).

אם כך, סיבוכיות המקום היא לינארית.

מה לגבי סיבוכיות הזמן שלי?

מספר הקפיצות המקסימלי שאני יכולה לעשות בנקודה k במערך הוא n-k (לכל היותר אני יכולה לקפוץ עד האיבר האחרון, ולא מעבר לא).

אז באינדקס 0 אני יכולה לעשות לכל היותר N קפיצות, באינדקס 1 אני יכולה לעשות לכל היותר N-1 קפיצות וכן הלאה…

אם אסכם את הסדרה החשבונית אראה שמספר ההרצות המקסימלי שלי יהיה N². ולכן סיבוכיות הזמן שלי תהיה O(N²).

עכשיו לכתוב קוד!

אתם יכולים לראות אותו בגיט – https://github.com/mgershovitz/maya_solves/blob/master/jump_game.py