החידה הבאה הגיעה אליי במקרה בטלגרם:

מבלי לשנות את סדר המספרים, עליכם להציב 3 סימני חיבור או חיסור ביניהם כך שתקבלו משוואה נכונה: 100 = 9 8 7 6 5 4 3 2 1

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

1. איך מחשב ניגש לכזאת שאלה

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

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

[1, 234]

כלומר פלוס אחד ואז פלוס 234, אז יש בסך הכל 3 אפשרויות לצעד הבא:

[1, 234, -5]
[1, 234, 5]
[1, 2345]

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

2. והקוד ברובי

שרשרת תהיה בסך הכל סוג-של מערך שיש לו פונקציית expand שמחזירה את שלוש השרשראות שיכולות להמשיך אותה. אני מגדיר את המחלקה ומספר פוקנציות עזר:

class Chain
  attr_accessor :values

  def initialize(values)
    @values = values
  end

  def last
    @values[-1] || 0
  end

  def sum
    @values.sum
  end

  def to_s
    "Chain: #{values}"
  end
end

והפונקציה המעניינת, expand, היא זו שלוקחת שרשרת ומוסיפה לה סיפרה, או בתור סיפרה חדשה למספר האחרון בשרשרת או בתור מספר חדש:

  def expand
    return if last.abs % 10 == 9
    return if values.length > 4

    value = last.abs
    next_value = (value % 10) + 1
    concatenated_value = (value * 10 + value % 10 + 1) * (last >= 0 ? 1 : -1)

    [
      Chain.new([*values, next_value]),
      Chain.new([*values, -1 * next_value]),
      Chain.new(values[0..-2].concat([concatenated_value]))
    ]
  end

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

ואחרי כל ההשקעה במחלקה Chain אפשר לסיים את התרגיל עם לולאה פשוטה שמתחילה עם מערך של Chain יחיד וריק, ובכל איטרציה מפעילה expand על כל השרשראות במערך ומחפשת אם הסכום של אחת מהן הוא 100:

state = [Chain.new([])]
loop do
  state = state.flat_map(&:expand).reject(&:nil?)
  if (final = state.find { |chain| chain.values.size == 4 && chain.sum == 100 })
    puts final
    break
  end
end

כל התוכנית לקחה פחות מ 50 שורות קוד והרבה פחות זמן ממה שהיה לוקח לי למצוא את השרשרת המתאימה ב Brute Force בראש.