יום 6 - הקצאות זיכרון

aoc2017
#1

הי,
@YOEL, @11115, @splintor, @Amirkr, @miryeh, @itamard
לא מאמין שכבר יום שלישי וזה הזמן לחידה השניה שלנו לשבוע. לא המון אנשים ענו על החידה הקודמת וקצת חבל כי היא היתה די קלה וזו הזדמנות טובה לקבל כוכב בפחות מעשר שורות. בכל מקרה כלום עדיין לא אבוד ואפשר עוד להוסיף גם לדיונים ישנים.

יום 6: הקצאות זיכרון

(אני משנה קצת את ניסוח החידה כדי שיהיה יותר קצר. כדאי לקרוא גם את הטקסט המקורי של אריק)

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

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

לדוגמא נדמיין תרחיש עם 4 עמודים ובהם 0, 2, 7 ו-0 חישוקים בהתאמה כלומר משמאל לימין זה יראה כך:

      *
      *
      *
      *
      *
   *  *
   *  *
_  _  _  _

עכשיו מתחילים לסדר מחדש את החישוקים אז ברור שבעמוד השלישי יש הכי הרבה חישוקים ונתחיל לרוקן אותו. ה-7 חישוקים שלו מתחלקים בין העמודים האחרים: קודם חישוק לרביעי, אחרי זה לראשון, לשני, לשלישי ועוד אחד לרביעי ועוד אחד לראשון וחישוק אחרון לעמוד השני. סך הכל יש לנו עכשיו תרחיש שנראה כך:

   *
   *
*  *     *
*  *  *  *
_  _  _  _

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

3, 1, 2, 3

בסיבוב הבא יש תיקו בין העמוד הראשון לרביעי ולכן מפרקים את העמוד הראשון ומקבלים:

0, 2, 3, 4

נמשיך עוד שני סיבובים ונקבל:

1, 3, 4, 1
2, 4, 1, 2

סך הכל אחרי 5 סיבובים הגענו לסידור שכבר ראינו בעבר ולכן אפשר לעצור והתשובה היא 5.

המשימה שלכם: כתבו תוכנית שמחשבת את כל זה ומדפיסה כמה סיבובים זה לקח. בונוס מיוחד למי שיוסיפו UI יפה (אפשר כמובן גם בטקסט כמו שציירתי כאן). אחרי שסיימתם לכו לקרוא את החידה המקורית של אריק וגם קחו ממנו את הכוכב שלכם
https://adventofcode.com/2017/day/6

#2

זה הקוד שלי:

הצלחתי ליצור gui שמציג את ה"עמודים" וה"חישוקים" אבל הוא עובד רק על קלטים קצרים
מסיבה שלא הצלחתי להבין שורות 16-17 תוקעות את הסקריפט עבור מערכים גדולים
למישהו יש רעיון?

(בכל אופן - קיבלתי עוד כוכב מאריק :slight_smile: :star: )

#3

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

https://www.tocode.co.il/bundles/es6/lessons/promises

https://www.tocode.co.il/bundles/es6/lessons/async-await

https://www.tocode.co.il/bundles/es6/lessons/async-generators

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

#4

ניסיתי לממש את ה-Async generators אך ללא הצלחה…
זו התוצאה בינתיים:

(השערה: יש מצב ש-CodePen מחמירים במספר הפעמים שלולאה יכולה לרוץ?)

#5

חלק שני

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

בדוגמא שראינו הסידור:

2 4 1 2

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

#6

פיתרון שלי באליקסיר לשני החלקים:

defmodule Day6 do
  def next_index(map, index) do
    rem(index+1, map_size(map))
  end

  def redistribute(map, _, 0) do
    map
  end

  def redistribute(map, index, count) do
    redistribute(
      Map.update!(map, index, fn(x) -> x + 1 end),
      next_index(map, index),
      count - 1
    )
  end

  def list_to_indexed_map(list) do
    list
    |> Enum.with_index(0)
    |> Enum.map(fn({k,v}) -> {v,k} end)
    |> Map.new
  end

  def next(acc) do
    { index, val } = Enum.max_by(acc, fn({_, v}) -> v end)    
    el = redistribute(
        Map.replace(acc, index, 0),
        next_index(acc, index),
        val)
    { el, el }
  end

  def run_till_dup(stream) do
    Stream.transform(stream, MapSet.new, fn(el, acc) ->
      if MapSet.member?(acc, el) do
        { :halt, acc }
      else
        { [el], MapSet.put(acc, el) }
      end
    end)
  end
end

banks = IO.stream(:stdio, :line)
        |> Enum.at(0)
        |> String.split
        |> Enum.map(&String.trim/1)
        |> Enum.map(&String.to_integer/1)
        |> Day6.list_to_indexed_map

s1 = Stream.unfold(banks, &Day6.next/1)

count = s1
        |> Day6.run_till_dup
        |> Enum.count

count = count + 1

loop_start = s1
             |> Day6.run_till_dup
             |> Enum.at(-1)

loop_count = Stream.unfold(loop_start, &Day6.next/1)
             |> Day6.run_till_dup
             |> Enum.count

IO.puts(count)
IO.puts(loop_count)
#7

דוקא אני בפיירפוקס רואה יופי של אנימציה - אבל נראה שיש בעיה בתנאי העצירה כי היא לא נפסקת אף פעם
(קודפן מפסיק בשלב מסוים ומתלונן על לולאה אין סופית)