שקילת מטבעות

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

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

היום הסתכלתי באתר של חידות תכנותיות וראיתי את החידה הזו, וחשבתי שיהיה ממש נחמד לנסות לפרמל אותה, להסביר את הפתרון, ואולי אפילו להכליל את הפתרון למספרים גדולים יותר.
אז הנה אני מתחילה!

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

האינטואיציה שלי ישר אמרה שצריך לחלק את המטבעות לשלוש קבוצות זהות של 9 מטבעות, את הקבוצות אני יכולה לשקול אחת מול השנייה כדי לקבל עוד מידע.

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

על פניו נראה שאם A ו-B זהות אני מזהה מיד את הקבוצה השונה ואם הן שונות אני צריכה שקילה נוספת כדי לזהות את השקילה השונה – אז יכול להיות שהמינימום שקילות בכלל תלוי במזל? מכאן התחלתי להתפצל לתרשימי זרימה שונים ולספור שקילות ומבלבלת את עצמי לגמרי.

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

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

אלגוריתם שלב 1 – 

def weigh(coins_x, coins_y):
	if coins_x > coins_y:
		return 1
	elif coins_y > coins_x:
		return -1
	else:
		return 0

def find_odd_coin(coins):
	a = coins[0:9]
	b = coins[9:18]
	c = coins[18:27]
	
	odd_group = None
	odd_coin_weight = None

	first_weigh = weigh(a,b)
	second_weigh = weigh(c, a)

	if first_weigh == 0:
		odd_group = c
		odd_coin_weight = second_weigh
	else:
		if second_weigh == 0:
			odd_group = b
			odd_coin_weight = -1 * first_weigh
		else:
			odd_group = a
			odd_coin_weight = -1 * second_weigh

מה בעצם קורה באלגוריתם הזה?
אני משתמשת בפונקציית weigh שמחזירה 1 אם המטבע הראשון כבד מהשני, 1- אם הוא קל מהשני, ו-0 אם הם זהים.
המשקלים עצמם לא משנים לי, רק הכיוון של ההפרש.

מאוחר יותר אני משתמשת בתוצאה של השקילה כדי לקבוע את כיוון המשקל של המטבע השונה.
לדוגמא – 
נניח וקיבלתי first_weigh = 1, ו-second_weigh = 0.
השקילה הראשונה אומרת לי ש-a כבדה מ-b, והשקילה השנייה אומרת לי ש-a ו-c שוקלות אותו הדבר – כלומר, b היא הקבוצה השונה והיא קלה יותר מכל השאר.

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

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

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

def find_odd_group(x,y,z,odd_coin_weight):
	first_weigh = weigh(x, y)
	if first_weigh == 0:
		return z
	else:
		if first_weigh == odd_coin_weight:
			return x
		else:
			return y

גם פה אני משתמשת בטריק דומה לזה שהשתמשתי בו בשלב הראשון, רק שהפעם אני משתמשת בידע על המשקל של המטבע השונה כדי לאתר את הקבוצה השונה ולא להיפך.
לדוגמא – 
אם first_weigh=1, אז זה אומר ש-x כבדה מ-y.
ואז אם odd_coin_weight=1, אז הקבוצה הכבדה יותר היא השונה – כלומר x.
ואם odd_coin_weight=-1, אז הקבוצה הקלה יותר היא השונה – כלומר y.

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

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

עד פה הכל טוב ויפה, ועכשיו דברים מתחילים להסתבך – איך הייתי מכלילה את האלגוריתם למספר מטבעות שונה שמתחלק ב-3, למשל 30?

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

def find_odd_group(x,y,z,extra_coin, odd_coin_weight):
	first_weigh = weigh(x, y)
	if first_weigh == 0:
		second_weigh = (extra_coin, x[0])
		if second_weigh == odd_coin_weight:
			return [extra_coin]
		else:
			return z
	else:
		if first_weigh == odd_coin_weight:
			return x
		else:
			return y

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

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

מה אם הייתי מוסיפה מטבעות לקבוצה שלי כדי לקבל מספר שכן מתחלק בשלוש?
זה רעיון מעניין, אם הייתי לוקחת שתי מטבעות רגילים ומוסיפה אותם לקבוצה השונה הייתה לי עכשיו קבוצה של 12 מטבעות. הייתי יכולה לחלק אותם לשלוש קבוצות של 4 מטבעות כל אחת, ולקרוא לפונקציה find_odd_group שתמצא לי את הקבוצה השונה.

במקרה כזה, אחרי שלוש השקילות הראשונות מצאתי קבוצה של 4 מטבעות שאחד מהם שונה.
עכשיו אני באותה הבעיה – 4 מטבעות לא מתחלקים יפה לשלוש. אני אוסיף שוב שתי מטבעות רגילים לקבוצה שלי כדי לקבל קבוצה של 6 מטבעות, ואקרא לפונקציה find_odd_group שתמצא לי את הקבוצה השונה. עד כה, בארבע שקילות מצאתי קבוצה של 2 מטבעות שאחד מהם שונה.
אני אוסיף מטבע אחת לקבוצה שלי ואקרא לפונקציה שלי בפעם האחרונה ואמצא את המטבע השונה ב-5 שקילות ובלי לשנות יותר מדי את הקוד שלי.

נראה כמו אחלה פתרון, אני אכתוב אותו – 

def find_odd_group(coins,odd_coin_weight):
	x, y, z = divide_group_to_three(coins)
	first_weigh = weigh(x, y)
	if first_weigh == 0:
		return z
	else:
		if first_weigh == odd_coin_weight:
			return x
		else:
			return y

def divide_group_to_three(group):
	groups_size = len(group) / 3
	groups = []
	for i in range(0,3):
		groups.append(coins[groups_size*i: groups_size*i+1])
	return groups

def find_odd_coin(coins):
	a, b, c = divide_group_to_three(coins)
	odd_group = None
	control_group = None
	odd_coin_weight = None

	first_weigh = weigh(a,b)
	second_weigh = weigh(c, a)

	if first_weigh == 0:
		control_group = a
		odd_group = c
		odd_coin_weight = second_weigh
	elif second_weigh == 0:
		control_group = a
		odd_group = b
		odd_coin_weight = -1 * first_weigh
	else:
		control_group = b
		odd_group = a
		odd_coin_weight = -1 * second_weigh

	while len(odd_group) > 1:
		if len(odd_group) % 3 == 1:
			odd_group.extend(control_group[0:2])
		elif len(odd_group) %3 == 2:
			odd_group.extend(control_group[0:1])
		odd_group = find_odd_group(odd_group, odd_coin_weight)

	return odd_group[0]	

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

זה כבר נראה ממש טוב, אבל יש עוד מקרה קצה שלא טיפלתי בו – 
מה קורה אם הקבוצה הראשונית שלי היא בגודל שלא מתחלק ב-3?
אם אני צריכה לבדוק 28 מטבעות – אני לא יכולה להוסיף מאיפשהו שתי מטבעות כדי לעגל ל-30 כמו שעשיתי בחלק השני של האלגוריתם, אני חייבת להוציא את המטבעות המיותרים מהקבוצה ולבדוק אותם בנפרד, במקרה שבו שתי השקילות הראשונות שלי שוות ל-0 – 

def find_odd_group_and_odd_weight(coins)
	x, y, z = divide_group_to_three(coins)
	first_weigh = weigh(x, y)
	second_weigh = weigh(x, z)
	if first_weigh == 0:
		odd_group = z
		odd_coin_weight  = -1 * second_weigh
	elif second_weigh == 0:
		odd_group = y
		odd_coin_weight  = -1 * first_weigh
	else:
		odd_group = x
		odd_coin_weight  = first_weigh
	return odd_group, odd_coin_weight

def add_regular_coins_to_odd_group(odd_group, control_group):
	if len(odd_group) % 3 == 1:
		odd_group.extend(control_group[0:2])
	elif len(odd_group) % 3 == 2:
		odd_group.extend(control_group[0:1])

def find_odd_coin(coins):
	coins_remainder_group_size = len(coins) % 3
	main_groups_size = len(coins) - len(coins_remainder_group_size)
	coins_remainder_group = coins[main_groups_size:]
	coins = [:main_groups_size]

	a, b, c = divide_group_to_three(coins)
	odd_group = None
	control_group = None
	odd_coin_weight = None

	first_weigh = weigh(a,b)
	second_weigh = weigh(c, a)

	if first_weigh == 0 and second_weigh == 0:
		add_regular_coins_to_odd_group(coins_remainder_group, coins)
		odd_group, _ = find_odd_group_and_odd_weight(coins_remainder_group)
		return odd_group[0]

	if first_weigh == 0:
		control_group = a
		odd_group = c
		odd_coin_weight = second_weigh
	elif second_weigh == 0:
		control_group = a
		odd_group = b
		odd_coin_weight = -1 * first_weigh
	else:
		control_group = b
		odd_group = a
		odd_coin_weight = -1 * second_weigh

	while len(odd_group) > 1:
		add_regular_coins_to_odd_group(odd_group, control_group)
		odd_group = find_odd_group(odd_group, odd_coin_weight)

	return odd_group[0]	

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

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

def find_odd_group_and_odd_weight(coins)
	x, y, z = divide_group_to_three(coins)
	first_weigh = weigh(x, y)
	second_weigh = weigh(x, z)

	if first_weigh == 0 and second_weigh == 0:
		return None, None, None
	
	if first_weigh == 0:
		odd_group = z
		control_group = x
		odd_coin_weight  = -1 * second_weigh
	elif second_weigh == 0:
		odd_group = y
		control_group = x
		odd_coin_weight  = -1 * first_weigh
	else:
		odd_group = x
		control_group = y
		odd_coin_weight  = first_weigh
	return odd_group, control_group, odd_coin_weight

def find_odd_coin(coins):
	coins_remainder_group_size = len(coins) % 3
	main_groups_size = len(coins) - len(coins_remainder_group_size)
	coins_remainder_group = coins[main_groups_size:]
	coins = [:main_groups_size]

	odd_group, control_group, odd_coin_weight = \
		find_odd_group_and_odd_weight(coins)
	
	if odd_group is None:
		add_regular_coins_to_odd_group(coins_remainder_group, coins)
		odd_group, _, _ = find_odd_group_and_odd_weight(coins_remainder_group)
		return odd_group[0]

	while len(odd_group) > 1:
		add_regular_coins_to_odd_group(odd_group, control_group)
		odd_group = find_odd_group(odd_group, odd_coin_weight)

	return odd_group[0]	

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

אני אתחיל מקבוצה של 3 מטבעות – 

arr = [1,1,0] find_odd_coin([1,1,0]): coins_remainder_group_size = 0 main_groups_size = 3 coins_remainder_group = [] coins = [1,1,0] call find_odd_group_and_odd_weight([1,1,0]) find_odd_group_and_odd_weight([1,1,0]): x, y, z = [1],[1],[0] first_weigh = 0 second_weigh = 1 first_weigh == 0 → odd_group = [0] control_group = [1] odd_coin_weight = -1 return [0], [1], -1 len(odd_group) = 1 → return 0

מעולה, עכשיו מה לגבי מקרה של קבוצה ריקה? או קבוצה שיש בה רק מטבע אחד?
בקבוצה ריקה, בקבוצה של מטבע אחד ובקבוצה של שתי מטבעות אין משמעות למטבע “שונה”, כי בין אם יש אחד ובין אם יש שניים שונים, אי אפשר לדעת מיהו “הרגיל” ומיהו “השונה” אז במקרה כזה הייתי רוצה שהפונקציה שלי תחזיר תשובה ריקה, אני אוסיף את זה לקוד.
עכשיו אני רוצה לבדוק מקרה של קבוצה שלא מתחלקת ב-3, ומגיעה לשלב השני, אז אני ארוץ על קבוצה של 7 מטבעות.

arr = [1,1, 1, 1, 0, 1, 1] find_odd_coin([1,1, 1, 1, 0, 1, 1]): coins_remainder_group_size = 1 main_groups_size = 6 coins_remainder_group = [1] coins = [1,1, 1, 1, 0, 1] call find_odd_group_and_odd_weight([1,1, 1, 1, 0, 1]) find_odd_group_and_odd_weight([1,1, 1, 1, 0, 1]): x, y, z = [1, 1],[1, 1],[0, 1] first_weigh = 0 second_weigh = 1 first_weigh == 0 → odd_group = [0, 1] control_group = [1, 1] odd_coin_weight = -1 return [0, 1], [1, 1], -1 find_odd_coin([1,1, 1, 1, 0, 1, 1]): odd_group, control_group, odd_coin_weight = [0, 1], [1, 1], -1 len(odd_group) % 3 = 2 → odd_group = [0, 1, 1] odd_group = find_odd_group([0, 1, 1], -1) find_odd_group([0, 1, 1], -1): x, y, z = [0],[1],[1] first_weigh = -1 second_weigh = -1 odd_group = [0] control_group = [1] odd_coin_weight = -1 return [0], [1], -1 find_odd_coin([1,1, 1, 1, 0, 1, 1]): len(odd_group) = 1 → return 0

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

מה בעצם אני עושה באלגוריתם שלי?

בשלב הראשון, לא משנה מה גודל הקבוצה, אני תמיד עושה שתי שקילות – למצוא את הקבוצה השונה, ואת המשקל של המטבע השונה.
מעבר לכך, אני כל פעם מחלקת את הקבוצה השונה ב-3, ועושה עליה שקילה אחת נוספת..
מה הסיבוכיות של אלגוריתם שכל פעם מחלק את n לחלקים ורץ רק על חלק אחד? סיבוכיות לוגריתמית. בדרך כלל סיבוכיות לוגריתמית היא לוג בבסיס 2 – כמו למשל במקרה של חיפוש בינארי, שתמיד מחלק את המערך לחצי, אבל פה אני תמיד מחלקת את המערך ל-3, אז הלוג שלי הוא בבסיס 3. מצאתי את הסיבוכיות של האלגוריתם, והיא (O(logn.

מה לגבי מספר השקילות המדויק? אני מבצעת שקילה אחת על כל חלוקה ל-3, ומלבד זאת יש לי אקסטרה שקילה אחת בהתחלה, כלומר, מספר השקילות יהיה שווה ללוג בבסיס 3 ועוד אחת.
במקרה של 27 – 

log₃27 = 3 → 4 weighs

הלוג של 27 הוא כמובן 3 (כי 3³=27) ומספר השקילות הוא אכן 4.
מה אם היו לי 100 מטבעות?

log₃100 =~ 4 → 5 weighs

הלוג של 100 הוא קצת יותר מ-4, האם הנוסחא עדיין עובדת פה? אני אבדוק – 

• חלוקה ראשונה ל-3 קבוצות של 30 – שתי שקילות.
• חלוקה שנייה ל-3 קבוצות של 10 – שקילה אחת.
• מוסיפה 2, ועושה חלוקה שלישית ל-3 קבוצות של 4 – שקילה אחת.
• מוסיפה 2 ועושה חלוקה רביעית -ל3 קבוצות של 2 – שקילה אחת.
• מוסיפה 1 ועושה חלוקה אחרונה ל-3 קבוצות של 1 – שקילה אחת.

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

round_up(log₃100) = 5 → 6 weighs

זהו, יש לי פתרון מלא, אני יכולה לגשת לקודד, ובפעם הבאה שמישהו ישאל את השאלה הזו באירוע חברתי אני יכולה להגיד להם ש-27 זה קל, אבל האם הם יודעים כמה שקילות צריך למצוא את המטבע השונה בין 100,000 מטבעות? כי אני יודעת 🙂

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

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