פרוייקט "התלמיד והמחשב", בעיה 11

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

הבעיה הולכת כך: יש גרם מדרגות עם לכל היותר 1,000 מדרגות בו. אנחנו יודעים עליו את הדברים הבאים: אם מחלקים את מספר המדרגות ב-2, מקבלים שארית 1; אם מחלקים ב-3, מקבלים שארית 2; חלוקה ב-4 נותנת 3, חלוקה ב-5 נותנת 4, חלוקה ב-6 נותנת 5 וחלוקה ב-7 נותנת 6. כמה מדרגות יש?

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

puts (1..1000).reject{|n| (2..7).find{|k| (n % k) != k-1}}

לא יכלתי להמנע מלתת קוד של שורה אחת, למען ההתלהבות שבדבר, אבל בפועל התוכנית שכתבתי הכילה טיפה יותר שורות:

MAX_STEPS = 1000
JUMP_SIZES = (2..7)

puts (1..MAX_STEPS).reject{|n| JUMP_SIZES.find{|k| (n % k) != k-1}}

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

מה הקוד עושה? הוא מתחיל עם רשימה שכוללת את כל המספרים מ-1 עד 1000 ואז מפעיל עליה את האיטרטור reject שעובר איבר-איבר ברשימה, מעביר את האיבר לבלוק, ובונה רשימה חדשה שאיבריה הם רק אותם איברים ברשימה המקורית שהבלוק החזיר עליהם ערך false. ומה עושה הבלוק במקרה שלנו? עובר על רשימת כל המספרים מ-2 ועד 7 ומפעיל עליה את האיטרטור find שעבור על הרשימה ומחזיר את האיבר הראשון בה שכאשר מפעילים עליו את הבלוק ש-find קיבלה, ערך ההחזרה הוא true. הבדיקה שמתבצעת בתוך הבלוק הזה היא בדיוק האם המספר n, כשמחלקים אותו ב-k ולוקחים את השארית (זה האופרטור %) מחזיר ערך שונה מ-k-1, כלומר התנאי נכשל עבור n.

אז מה קרה פה? ה-find בקוד שלי בעצם אומר “אם אתה מוצא דוגמה נגדית, החזר אותה”. אבל איך זה קשור ל-true ו-false? ומה אם אין דוגמה נגדית. די בבירור חסרים לי דברים בקוד - העניין הוא שברובי קורים כמה דברים מאחורי הקלעים שטרם דיברתי עליהם.

ראשית, אם find לא מוצאת אף איבר ברשימה שניתן להחזיר, היא מחזירה ערך מיוחד שנקרא nil. הערך הזה משמש ברובי בשלל סיטואציות שונות ומשונות, ומטרתו תמיד לציין “אין ערך” (או “ערך לא מוגדר” וכן הלאה). אין יותר מדי דברים שאפשר לעשות עם nil (לנסות לחבר אותו עם מספרים, למשל, יגרום לתוכנית לקרוס) אבל דבר אחד שאפשר לעשות הוא להשתמש בו בתור ערך אמת - כל בדיקת תנאי שיכולה לקבל true או false יכולה לפעול גם על nil, והיא תתייחס אליו בתור false.

זה לא נגמר כאן, כמובן - בעצם, כל בדיקה של תנאי בוליאני ברובי יכולה לקבל כקלט כל דבר. הגישה של רובי היא להתייחס לכל קלט לבדיקה שכזו בתור true אלא אם הוא או הערך הקבוע false, או nil. כלומר, ברובי יש לנו בדיוק שני ערכים שיכולים להיחשב false. יש כאן מלכוד אדיר למתרגלים שמגיעים מהעולם של C: בעולם הזה, 0 נחשב false. ברובי בחרו לא לעשות את זה, ולטעמי בחוכמה רבה. למשל, פעולה נפוצה ברובי היא לבדוק אם תת-מחרוזת מופיעה בתוך מחרוזת נתונה (למעשה, אם ביטוי רגולרי מופיע בתוך מחרוזת נתונה) - ערך ההחזרה של בדיקה כזו הוא האינדקס שממנו תת-המחרוזת מתחילה להופיע, או nil אם היא לא מופיעה בכלל. האינדקס עשוי כמובן להיות 0 בעצמו… וזו לא הדוגמה היחידה.

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

הקוד בהסקל עושה בערך את אותו הדבר, רק עם קצת יותר שורות; ועדיין, יש בו נקודה חשובה שאני שמח שסוף סוף יצא לי להציג:

gives_correct_remainder :: [Int] -> Int -> Bool
gives_correct_remainder ms a = length bad_ms == 0
  where
    bad_ms = [m | m <- ms, (a `mod` m) /= m-1]

max_steps = 1000
jump_sizes = [2..7]

result = filter (gives_correct_remainder jump_sizes) [1..max_steps]
main = do
   putStrLn (show(result))

הסקל, מה לעשות, היא שפה קצת יותר קשיחה מאשר רובי ולכן אני צריך להתאמץ יותר ולכתוב פונקציה ייעודית שבודקת האם מספר נתון מקיים את תנאי המדרגות. הפונקציה מקבלת שני קלטים: הקלט הראשון הוא טווח המספרים שבהם צריך לחלק (אצלנו הוא מ-2 עד 7) והקלט השני הוא המספר שבודקים. הבדיקה עצמה היא סטנדרטית: אני בונה את רשימת המספרים שמהווים דוגמה נגדית (=/ הוא הסימון בהסקל לאי-שוויון) ובודק אם אורכה גדולה מאפס או לא. מה שמעניין הוא מה שקורה אחר כך - אני משתמש בפונקציה filter שמזכירה מאוד את reject של רובי אבל עם סדר הפוך - קודם כל היא מקבלת פונקציה להפעיל על איברי מערך, ואז היא מקבלת את המערך, ומפלטרת ממנו החוצה את כל מי שהפונקציה החזירה עליו False. החלק המעניין ביותר בכל הקוד הוא הפונקציה ש-filter מקבלת.

מה ש-filter אמורה לקבל הוא פונקציה שמקבלת פרמטר יחיד ומחזירה ערך בוליאני. אם תשימו לב, אין הגדרה מפורשת של פונקציה כזו בקוד שלי. מה שיש הוא את gives_correct_remainder שמקבלת שני פרמטרים: הפרמטר הראשון הוא מערך, והפרמטר השני הוא המספר שבודקים ביחס לאותו מערך. ומה filter מקבלת? היא מקבלת את gives_correct_remainder jump_sizes, כלומר את מה שמקבלים כאשר לוקחים את gives_correct_remainder ומפעילים אותו לא על זוג קלטים, אלא על קלט אחד - כלומר, הפעלנו את הפונקציה חלקית.

התוצאה של הפעלה חלקית שכזו היא לא ערך ההחזרה הצפוי של gives_correct_remainder, אלא פונקציה חדשה, שמקבלת רק קלט אחד. מכיוון שזה אחד הרעיונות המבלבלים ביותר בהסקל עבור מי שלא נתקל בו אף פעם, בואו נראה איך זה קורה כל הזמן בעולם המתמטי. נניח שיש לנו את הפונקציה הממשית הבאה בשני משתנים: \( f(a,x)=a^x \). הפונקציה הזו נקראת “פונקציה אקספוננציאלית”, עם בסיס \( a \) ומעריך \( x \). למשל, \( f(5,3)=5^3=125 \).

עכשיו, אם נציב \( a=2 \) בפונקציה הזו, נקבל פונקציה במשתנה יחיד: \( g(x)=f(2,x)=2^x \). אפשר גם לכתוב את הפונקציה הזו כך: \( f_2(x)=2^x \), ואפשר גם באופן כללי להגדיר \( f_a(x)=f(a,x)=a^x \). דהיינו, לכל ערך אפשרי של הפרמטר \( a \) אנחנו מקבלים פונקציה אחרת, \( f_a \).

כעת אפשר לשנות קצת את נקודת ההתבוננות שלנו: נגדיר פונקציה, שבכוונה אתן לה סימון מוזר, שמקבלת כקלט מספר ממשי ומחזירה כפלט פונקציה: \( \Phi(a)=f_a \). דהיינו, עבור \( 2 \) נקבל ש-\( \Phi(2)=f_2 \), כלומר הפלט של \( \Phi(2) \) הוא הפונקציה \( 2^x \). זה בדיוק מה שקורה בהסקל, וזה גם מסביר סוף סוף את שיטת הסימון ה”מוזרה” של פונקציות על כמה משתנים: הפונקציה gives_correct_remainder הוגדרה להיות פונקציה מטיפוס שמקבל כקלט מערך של מספרים ומוציא כפלט פונקציה שמקבלת כקלט מספר ומוציאה כפלט ערך בוליאני. זו צורת התבוננות מוזרה במבט ראשון, אבל היא רק מוסיפה לנו כוח: היכולת לקחת פונקציה קיימת ולקבל ממנה פונקציה חדשה על ידי הצבה חלקית בה היא מאוד מועילה לפעמים.

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

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

<html>
<head>
<title>Targil 11</title>
</head>
<body>
  <script type="text/javascript">
    var MAX_STEPS = 1000;
    var JUMP_SIZES = [2,3,4,5,6,7];

    var main = function(){
      var results = [];
      for (var i=1; i <= MAX_STEPS; i++){
      var to_add = true;
	for (var j=0; j < JUMP_SIZES.length; j++){
	  var jump = JUMP_SIZES[j];
	  if (i % jump != jump - 1){
	    to_add = false;
	  }
	}
	if (to_add){
	  results.push(i);
	}
      }
      document.getElementById("result").innerHTML = results;

      drawStairs(results[0])
    }

    var drawStairs = function(n){
      var canvas = document.getElementById('stairs_canvas');
      var context = canvas.getContext('2d');
      var stair_size = parseInt(document.getElementById("stair_size").value);
      canvas.width = stair_size * n;
      canvas.height = stair_size * n;
      for (var i = 0; i < n; i++){
	context.moveTo(stair_size*i,stair_size*i);
	context.lineTo(stair_size*i,stair_size*(i+1));
	context.stroke();

	context.moveTo(stair_size*i,stair_size*(i+1));
	context.lineTo(stair_size*(i+1),stair_size*(i+1));
	context.stroke();
      }
    }

    window.onload = main;
  </script>
  <div id="result"></div>
  <div style="overflow: scroll; width: 500px; height: 500px;">
    <canvas id="stairs_canvas">
      No Canvas for you!
    </canvas>
  </div>
  Stair size = <input type="textbox" id="stair_size" value = "5" onkeyup = "main()"/>
</body>
</html>

הנה לינק עבור מי שרוצה לראות איך הזוועה הזו נראית. הציור מתבצע על ידי שימוש ביישות html שנקראת Canvas ואינה נתמכת בדפדפנים ישנים, כך שאתם עשויים לא לראות אותה. Canvas הוא אחת מהתוספות הברוכות של HTML5 - אולי השימושית ביותר ששמעתי עליה עד כה. הרעיון באובייקט הזה פשוט למדי לכל מי שהתעסק עם כתיבת אפליקציות בעלות GUI (ממשק משתמש גרפי): זה איזור מוגדר במסך שאפשר לצייר בו ויש למשתמש מספר פונקציות פרימיטיביות שמאפשרות זאת - ציור של קו, עיגול וכדומה, אבל גם העתקה של תמונות שלמות. זה מספק למשתמש את הבסיס שנדרש - בעזרת הפונקציות הללו אפשר לצייר פחות או יותר כל מה שרוצים (כמובן, לאו דווקא באופן יעיל במיוחד). אני עצמי השתמשתי ב-canvas בבלוג, בפוסט על נוסחת טאפר (“הנוסחה שמציירת את עצמה”) כשנתתי לקוראים אפשרות לצייר דברים בעצמם (לרוע המזל, מאז שהתחלתי את סדרת הפוסטים הנוכחית הקוד בפוסט ההוא לא עובד - במקום להריץ אותו, הבלוג מציג אותו למשתמש….)

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

אבל רגע, מה עם הפתרון המתמטי לחידה שהבטחתי בתחילת הפוסט? ובכן, הבעיה נפתרת מייד בעזרת משפט השאריות הסיני, שכבר היה לי עליו פוסט רציני ולכן לא אחזור על כל פרטיו כאן. בואו נבין איך אפשר להשתמש פה במשפט: אנחנו בעצם רוצים לפתור מערכת של משוואות מודולריות עבור המודולוסים 2,3,4,5,6,7. הבעיה היא שלא כולם זרים ולכן אי אפשר להשתמש במשפט השאריות הסיני כמות שהוא - תחת זאת, אני לוקח מודולוסים שהם החזקות הגדולות ביותר של הראשוניים שמעורבים במשוואות ומתפלל לעצמי שהכל יעבוד כמו שצריך (כי ייתכן מאוד שלא יהיה בכלל פתרון). במקרה הזה, פירוש הדבר הוא שאני לוקח את המודולוסים 3,4,5,7. השמטתי את 2 ואת 6.

כעת, כאשר \( x \) הוא 3 מודולו 4, הוא בפרט 1 מודולו 2, כך שאני רגוע - התנאי על 4 מכליל את התנאי על 2. כמו כן, כאשר \( x \) הוא 2 מודולו 3, אז מודולו 6 הוא יכול להיות רק 2 או 5. אבל אם הוא 2 מודולו 6 הוא זוגי ולכן לא יכול להיות 1 מודולו 2, כך שגם התנאי על 6 מסתדר לי. במילים אחרות - כל פתרון למערכת המשוואות עבור המודולוסים 3,4,5,7 הוא גם פתרון לבעיה המקורית.

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

class Array
  def sum
    self.inject(0){|sum, x| sum+x}
  end
  def prod
    self.inject(1){|prod, x| prod*x}
  end
end

class Integer
  def extended_gcd(b)
    return [self,1,0] if b == 0
    q = self / b
    r = self % b
    gcd, x, y = b.extended_gcd(r)
    return [gcd, y, x-q*y]
  end

  def inverse_modulo(n)
    return nil unless self.gcd(n) == 1
    (n.extended_gcd(self).last) % n
  end
end

def chinese_remainder_theorem(a_vector, m_vector)
  b_m = m_vector.prod
  y_vector = m_vector.collect{|m_i| t=(b_m / m_i); t*t.inverse_modulo(m_i)}
  return (0...a_vector.length).collect{|i| a_vector[i]*y_vector[i]}.sum % b_m
end

puts chinese_remainder_theorem([2,3,4,6],[3,4,5,7])

הקוד הזה מחזיר רק 419. כדי לקבל את הפתרון השני צריך להוסיף לו 420, שהוא המכפלה של ארבעת המודולוסים (למה זה עובד? שוב, זה נובע ממשפט השאריות הסיני). העובדה שהפתרון הוא 419 ומכפלת המודולוסים היא 420 הגדולה ממנו ב-1 עשויה להקפיץ אצלכם נורת אזהרה - ואכן, בעצם יש פתרון פשוט עוד יותר לחידת המדרגות (שהוצג בספר המקורי) ולא מצריך כלום מלבד עט, נייר וטיפה מחשבה.

הרעיון הוא כזה: עכשיו, בואו נניח שיש לנו מספר \( x \) שמחזיר שארית 1 בחלוקה ב-2 - זה אומר שאם נוסיף לו 1, נקבל מספר שמתחלק ב-2. הוא מחזיר 2 בחלוקה ב-3, כלומר אם נוסיף לו 1 נקבל מספר שמתחלק ב-3, וכן הלאה. המסקנה היא שהמספר שאנחנו מחפשים הוא כזה שאם נוסיף לו 1, נקבל מספר שמתחלק בו זמנית ב-2,3,4,5,6,7. כעת, 420 הוא הכפולה המשותפת המינימלית של 2,3,4,5,6,7…