• בלוג
  • בואו נמצא מספרים שמחים עם Elixir

בואו נמצא מספרים שמחים עם Elixir

14/05/2022

מספר שמח הוא מספר שסכום ריבועי הספרות שלו בסוף יוצא 1. מספר עצוב הוא מספר שסכום ריבועי הספרות שלו לא יוצא 1, לא משנה כמה פעמים מעלים בריבוע ומחברים. ככה יוצא ש 7 הוא מספר שמח, כי כשמעלים אותו בריבוע מקבלים 49, וכשמעלים בריבוע את שתי הספרות של 49 מקבלים 16 ו 81 שסכומם יוצא 97, ממשיכים עוד סיבוב ומקבלים את 49 ו 81 שסכומם הוא 130, ועכשיו אנחנו מתקרבים למשהו כי 3 בריבוע זה 9 ו 1 בריבוע נשאר 1, יחד הם נותנים 10, שסכום ריבועי הספרות שלו הוא פשוט 1 בריבוע ועוד אפס בריבוע כלומר המספר 1.

לעומתו 4 הוא מספר עצוב כי בריבוע הוא נותן 16, וכשמעלים בריבוע את 1 ו 6 מקבלים 1 ו 36, שזה יחד 37, הסכום הבא הוא 58, אחרי זה 89, ואז 145, 42, 20 ושוב 4.

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

1. איך סוכמים את ריבועי הספרות

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

  1. פיצול מספר לספרות
  2. העלאה של כל סיפרה בריבוע
  3. חישוב הסכום

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

Stream.unfold(n, fn 
  0 -> nil
  n -> { rem(n, 10), div(n, 10) }
end)

אנחנו לא עוצרים בחלוקה לספרות ורוצים גם להעלות בריבוע כל סיפרה (map) ואחרי זה לסכום את התוצאות (sum). סך הכל אני יכול לכתוב פונקציה ראשונה כזאת:

def sum_squared_digits(n) do
  Stream.unfold(n, fn 
    0 -> nil
    n -> { rem(n, 10), div(n, 10) }
  end)
  |> Enum.map(&(&1 ** 2))
  |> Enum.sum
end

2. איך בודקים אם מספר הוא שמח

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

  1. המספר 1 הוא שמח.

  2. מספר שאינו 1 ושנמצא ברשימת המספרים שראינו הוא עצוב.

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

בתרגום לאליקסיר זה נראה כך:

def is_happy(n, seen \\ %{}) do
  cond do
    n == 1 ->
      true

    Map.has_key?(seen, n) ->
      false

    true -> 
      is_happy(
        sum_squared_digits(n),
        Map.put(seen, n, true)
      )
  end
end

3. איך מוצאים את כל המספרים השמחים עד 100

בשביל להתחיל למצוא מספרים שמחים אני יכול לרוץ בלולאה על רשימה של מספרים ולהפעיל את הפונקציה filter, שמסננת מהרשימה רק את המספרים שמתאימים לתנאי. הדפסת המספרים השמחים עד 100 היא:

def main() do
  1..100
  |> Enum.filter(&is_happy/1)
  |> IO.inspect
end

והקוד המלא באליקסיר הוא:

defmodule HappyNumbers do
  def main() do
    1..100
    |> Enum.filter(&is_happy/1)
    |> IO.inspect
  end

  def is_happy(n, seen \\ %{}) do
    cond do
      n == 1 ->
        true

      Map.has_key?(seen, n) ->
        false

      true -> 
        is_happy(
          sum_squared_digits(n),
          Map.put(seen, n, true)
        )
    end
  end

  def sum_squared_digits(n) do
    Stream.unfold(n, fn 
      0 -> nil
      n -> { rem(n, 10), div(n, 10) }
    end)
    |> Enum.map(&(&1 ** 2))
    |> Enum.sum
  end
end

HappyNumbers.main()

ובגירסה אינטרקטיבית אם אתם קוראים את הפוסט בדפדפן: