גלידה

חם היום!
כמה חם? כל כך חם שהלכתי לחפש שאלת תכנות בנושא גלידה, והנה מה שמצאתי – 

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

הנחות:

1. צילי וגילי תמיד מוציאות את כל הכסף שקיבלו על גלידה.
2. תמיד קיים זוג גלידות יחיד שיתאים לסכום הכסף שצילי וגילי קיבלו.

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

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

ice_cream_costs = [2, 5, 3, 1] money_sums = [3, 8] choose_ice_cream(ice_cream_costs, money_sums) = [[0,3], [1,2]]

אחלה, אפשר להתחיל.
כמו תמיד, אני אתחיל עם הפתרון הנאיבי. הפתרון הנאיבי לשאלה הזו הוא שימוש קלאסי של hash-tables.
נניח שיש לי סכום יחיד x ומערך מחירים. עבור כל מחיר במערך אני רוצה לבדוק האם ההפרש x-cost גם נמצא במערך – אני יכולה לעשות את זה בעזרת hash-table שימפה את כל ההפרשים.
אני אכתוב את האלגוריתם עבור סכום ספציפי – 

def choose_ice_cream_once(ice_cream_costs, money):
	diff_to_cost = {}
	for i in range(0, len(self.ice_cream_costs)):
		cost = self.ice_cream_costs[i]
		if cost in diff_to_cost:
			return diff_to_cost[cost], i
		else:
			diff = money - cost
			diff_to_cost[diff] = i

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

choose_ice_cream_once([2, 5, 3, 1], 8): diff_to_cost = {} i=0 cost = 2 diff = 6 diff_to_cost = {6:0} i=1 cost = 5 diff = 3 diff_to_cost = {6:0, 3:1} i=2 cost = 3 return (1, 2)

יאי! יש תשובה נכונה.
מה הסיבוכיות של האלגוריתם הזה?
הסיבוכיות של מעבר יחיד הוא (O(N. כיוון שבשאלה התבקשתי לחפש זוג גלידות מתאים לכל יום, אז האלגוריתם ירוץ k פעמים, כאשר k הוא גודל מערך הסכומים. אז הסיבוכיות של האלגוריתם כולו תהיה (O(KN.

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

אבל איזה preprocessing יעזור לי פה?

נניח והייתי עוברת מראש על כל זוגות המחירים ומכניסה את סכומי המחירים שלהם לטבלה – טבלה כזו תאפשר לי למצוא את זוג הגלידות המתאים לכל סכום ב-(O(1. מגניב, לא?
הסיבוכיות של יצירת טבלה כזו היא (O(N² (כי צריך לעבור על כל הזוגות) – ולכן ההשקעה הזו תשתלם רק במקרה שבו K≥N.
אני אכתוב את האלגוריתם הזה – 

def preprocess_ice_cream_costs(ice_cream_costs):
	all_possible_costs_sums = {}
	for i in range(0, len(ice_cream_costs)):
   		for j in range(i + 1, len(ice_cream_costs)):
       			costs_sum = ice_cream_costs[i] + ice_cream_costs[j]
       			all_possible_costs_sums[costs_sum] = (i, j)
	return all_possible_costs_sums

def choose_ice_cream_once(all_possible_costs_sums, money):
	return all_possible_costs_sums[money]

האם יש פתרון עוד יותר יעיל במקרה שבו K≥N?
לא הצלחתי למצוא כזה, אבל אשמח מאוד לשמוע אם אתן מצאתן אחד.

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

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/ice_cream.py