שלום אורח התחבר

רקורסיה קטנה ומטריפה

נושאים:פיתוח צד-לקוח

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

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

1מהו חידון 24

הגעתי השבוע לבלוג של מרקוס דומינוס ולמדתי ממנו על חידון קטן וחביב עם מספרים שהוא משחק עם הילדות שלו: קחו 4 ספרות ונסו באמצעות פעולות חיבור, חיסור כפל וחילוק להרכיב מהן את המספר 24. יש ממש קלים כמו 1, 2, 6, 8 או 4, 5, 1, 5, ומצד שני יש את 1, 2, 7, 7 שלוקח יותר זמן למצוא את הפיתרון.

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

עכשיו בואו ננסה לתת ל JavaScript לעבוד בשבילנו ולמצוא את הפתרונות.

2אלגוריתם רקורסיבי לפיתרון

השיטה לפתור את החידה מבוססת על סוג של אופטימיות המאפיינת רקורסיות:

  1. לוקחים שני מספרים (או ביטויים) מהרשימה ובוחרים פעולה.
  2. מחליפים את שני המספרים בביטוי שיצרנו.
  3. חוזרים על (1) ו (2) עד שנשארים עם ביטוי יחיד ברשימה.
  4. אם ערך הביטוי הוא 24 ניצחנו.

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

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

נתחיל בהגדרת 4 פעולות החשבון:

function add(x, y) { return x + y; }
function mul(x, y) { return x * y; }
function sub(x, y) { return x - y; }
function div(x, y) { return x / y; }

add.toString = () => '+';
mul.toString = () => '*';
sub.toString = () => '-';
div.toString = () => '/';

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

function value(n) {
  if (typeof n === 'number') {
    return n;
  } else {
    return n.op(value(n.x), value(n.y));
  }
}

וכך נקבל:

value(10) === 10
value({ op: mul, x: 2, y: 5 }) === 10
value({ op: add, x: { op: mul, x: 2, y: 5 }, y: 10 }) === 20

3נעבור לקוד המשחק

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

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


function play(digits) {
  if (digits.length === 1) {
    if (value(digits[0]) === 24) {
      return digits[0];
    }
  }

  for (let i=0; i < digits.length; i++) {
    for (let j=0; j < digits.length; j++) {
      if ( i === j ) { continue; }
      let rest = digits.filter((item, index) => ((index !== i) && (index !== j)));

      let result = (
        play([ { op: add, x: digits[i], y: digits[j] }, ...rest ]) ||
        play([ { op: sub, x: digits[i], y: digits[j] }, ...rest ]) ||
        play([ { op: sub, x: digits[j], y: digits[i] }, ...rest ]) ||
        play([ { op: mul, x: digits[i], y: digits[j] }, ...rest ]) ||
        (j !== 0 && play([ { op: div, x: digits[i], y: digits[j] }, ...rest ])) ||
        (i !== 0 && play([ { op: div, x: digits[j], y: digits[i] }, ...rest ]))
      );
      if (result) { return result; }
    }
  }
}

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

הקוד כבר עובד ומדפיס את הערך אבל בצורה לא הכי קריאה:

console.log(play([2, 2, 5, 7]));
// prints:
// { op: { [Function: add] toString: [Function] },
//  x: { op: { [Function: mul] toString: [Function] }, x: 2, y: 7 },
//  y: { op: { [Function: mul] toString: [Function] }, x: 2, y: 5 } }

אחרי שהבנו את המנגנון הרקורסיבי קל לפתור את זה ולהפוך ביטוי כזה למחרוזת באמצעות רקורסיה שלישית:

function to_s(val) {
  if (typeof val === 'number') {
    return String(val)
  }
  const { x, y, op } = val;
  return `(${to_s(x)} ${op} ${to_s(y)})`;
}

ועכשיו נקבל:

// console.log(to_s(play([2, 2, 5, 7])));
// ((2 * 7) + (2 * 5))

4גבולות הכח

הפיתרון שכתבנו עובד הרבה יותר טוב ממה שאני מצליח לפתור את החידות האלה, אבל עדיין לא מושלם. תנו לו לשבור את הראש עם 3, 3, 8, 8 ותראו שהוא לא יצליח למצוא את התשובה.

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

8 / (3 - 8/3) == 24

אבל זה לא עובד כל כך טוב ב JavaScript:

> 8/(3-8/3) == 24
false

> 8/(3-8/3)
23.99999999999999

התשובה של JavaScript נובעת מהקושי שלה (ושל שפות מחשב רבות נוספות) לייצג מספרים ראציונאליים. אפשר לראות התנהגות דומה בתרגיל הבא:

> 0.1 + 0.2
0.30000000000000004

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

מעדיפים לקרוא מהטלגרם? בקרו אותנו ב:@tocodeil

או הזינו את כתובת המייל וקבלו את הפוסט היומי בכל בוקר אליכם לתיבה:


נהניתם מהפוסט? מוזמנים לשתף ולהגיב