אתגר Advent Of Code יום שלישי

ynonp · 21 בספטמבר,‏ 2018,‏ 7:32am

הי,

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

@YOEL, @11115, @splintor, @Amirkr, @miryeh

חלק ראשון

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

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

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

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

לדוגמא המספר 9 מרוחק 2 צעדים מהמספר 1: קחו צעד אחד למעלה ואז אחד שמאלה והגעתם.

המספר 12 מרוחק 3 צעדים: קחו שניים שמאלה ואז אחד למטה ואתם שם.

המספר 23 מרוחק רק שני צעדים מ-1: פשוט שני צעדים למעלה ואתם שם.

המספר 1024 מרוחק 31 צעדים מהמספר 1 (אבל את זה כבר לא רואים בציור).

כתבו תוכנית שמקבלת מספר ומדפיסה את המרחק שלו מ-1. אחרי זה לכו לאתר של אריק ונסו אותה על הקלט האישי שלכם כדי לקבל כוכב. זה הקישור לחידה המקורית:
https://adventofcode.com/2017/day/3

ynonp · 21 בספטמבר,‏ 2018,‏ 7:42am

רמזים - איך מתחילים?

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

YOEL · 21 בספטמבר,‏ 2018,‏ 12:47pm

זה באמת קשה
צריך רמזים לרמזים שלך

ynonp · 21 בספטמבר,‏ 2018,‏ 1:00pm

יהיו אל דאגה בוא ניתן לזה להתגלגל בראש עד מוצ״ש ואז יהיה עוד רמז

YOEL · 21 בספטמבר,‏ 2018,‏ 2:09pm

במילון באיזה קי נשים את 1
ואחרי זה איך נמצא את המסלול הקצר ביותר (אריק מזכיר את מסלול המונית) בעזרת רקורסיה?

ynonp · 21 בספטמבר,‏ 2018,‏ 2:24pm

תשתמש באינדקס בתור מפתח - לדוגמא 1 יהיה ב (0, 0)

ואז אורך המסלול הוא פשוט ״שורה״ + ״עמודה״ (סכום שני החלקים של האינדקס)

miryeh · 21 בספטמבר,‏ 2018,‏ 10:59pm

לגמרי brain teaser! אני פה עם דף מקושקש בינתיים, יש התקדמות קלה. אעלה לכאן כשיהיה כיוון רציני.
מכוונת לפתרון ללא בנייה של מודל הזיכרון.

splintor · 22 בספטמבר,‏ 2018,‏ 8:39pm

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

function distance(n) { // n > 1
    let loop = 1;
    let counter = 1;
    while (counter + loop * 8 < n) {
        counter += loop * 8;
        ++loop;
    }

    while (counter + loop * 2 < n) {
        counter += loop * 2;
    }

    return loop + Math.abs(n - (counter + loop));
}

splintor · 22 בספטמבר,‏ 2018,‏ 9:08pm

אבל עכשיו שאני רואה את החלק השני, אני רואה שהשיטה הזו כנראה לא תעבוד שם, ואני אצטרך למצוא משהו אחר…

YOEL · 22 בספטמבר,‏ 2018,‏ 10:41pm

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

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

אני מסתפק אם לשים פה את הקוד כי זה כמה מחלקות ב ג’אווה

ynonp · 23 בספטמבר,‏ 2018,‏ 4:49am

בטח לשים

splintor · 23 בספטמבר,‏ 2018,‏ 5:52am

מותר לשים את הפתרון לחלק השני לפני שתרגמת אותו?
הפתרון שלי ב-JavaScript הוא די אלגנטי:

function sum(n) {
    const maze = {};

    const mazeAt = (x, y) => maze[`x${x}y${y}`] || 0;
    const setMazeAt = (x, y, value) => maze[`x${x}y${y}`] = value;

    let x = 0, y = 0;
    setMazeAt(x, y, 1);
    while (true) {
        if (mazeAt(x, y - 1) && !mazeAt(x - 1, y)) { // has below but not left
            --x; // move left
        } else if (mazeAt(x - 1, y) && !mazeAt(x, y + 1)) { // left but not above
            ++y; // move up
        } else if (mazeAt(x + 1, y) && !mazeAt(x, y - 1)) { // right but not below
            --y; // move down
        } else {
            ++x; // else, move right
        }

        const sum = mazeAt(x + 1, y) + mazeAt(x + 1, y + 1) + mazeAt(x + 1, y - 1) +
            mazeAt(x - 1, y) + mazeAt(x - 1, y + 1) + mazeAt(x - 1, y - 1) +
            mazeAt(x, y + 1) + mazeAt(x, y - 1);
        if (sum > n) {
            return sum;
        } else {
            setMazeAt(x, y, sum);
        }
    }
}

ynonp · 23 בספטמבר,‏ 2018,‏ 6:11am

מה זה פה בית ספר?! בטח מותר

YOEL · 23 בספטמבר,‏ 2018,‏ 7:50am

זו מחלקת עזר להיתמצאות בלוח



public class Memory {

    public Memory(int lang) {
        this.lang = lang;
    }

    public static int lang;

    public int[] positionArray = new int[2];

    public int[] toArrayPosition(int position) {
        positionArray[0] = position / lang;
        positionArray[1] = position % lang;
        return positionArray;
    }

    public int toIntPosition(int[] positionArr) {
        int positionInt = (positionArr[0] * lang) + positionArr[1];
        return positionInt;
    }

    public int rowP(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]++;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int rowM(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]--;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int colP(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[1]++;

        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int colM(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[1]--;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int slantLeftUp(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]--;
        positionArray[1]--;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int slantRightUp(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]--;
        positionArray[1]++;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int slantRightDown(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]++;
        positionArray[1]++;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }

    public int slantLeftown(int positionInt) {
        int[] positionArray = toArrayPosition(positionInt);
        positionArray[0]++;
        positionArray[1]--;
        positionInt = toIntPosition(positionArray);
        return positionInt;
    }


}

זה בונה את הלוח

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Board {
    Map<Integer, Integer> map = new HashMap();
    int position, value;
    int LANG = 200;
    Memory memory = new Memory(LANG);

    public void generator(int num) {

        int start = LANG / 2;
        int midale = (LANG * start) + start;
        position = midale;
        map.put(position, 1);
        position = memory.colP(position);
        map.put(position, getValue());
        position = memory.rowM(position);
        map.put(position, getValue());

        loppGanerator(num);
    }

    public void loppGanerator(int num) {
        while (value < num) {
            goLeft();
            goDown();
            goRight();
            goUp();
        }

    }

    public int getValue() {
        value= getAroundValue();
        System.out.println("value " + value);

        return value;
        //פה אני מחליף מהתרגיל הראשון לשני
//        value++;
//        return value;
    }

    public void goLeft() {
        int down = memory.rowP(position);
        while (map.get(down) != null) {
            position = memory.colM(position);
            map.put(position, getValue());
            down = memory.rowP(position);
        }
    }

    public void goDown() {
        int right = memory.colP(position);
        while (map.get(right) != null) {
            position = memory.rowP(position);
            map.put(position, getValue());
            right = memory.colP(position);
        }
    }

    public void goRight() {
        int up = memory.rowM(position);
        while (map.get(up) != null) {
            position = memory.colP(position);
            map.put(position, getValue());
            up = memory.rowM(position);
        }
    }

    public void goUp() {
        int left = memory.colM(position);
        while (map.get(left) != null) {
            position = memory.rowM(position);
            map.put(position, getValue());
            left = memory.colM(position);
        }
    }

    public int getAroundValue() {
        int sum = 0;

        if (map.get(memory.colP(position)) != null) sum += map.get(memory.colP(position));
        if (map.get(memory.colM(position)) != null) sum += map.get(memory.colM(position));
        if (map.get(memory.rowM(position)) != null) sum += map.get(memory.rowM(position));
        if (map.get(memory.rowP(position)) != null) sum += map.get(memory.rowP(position));
        if (map.get(memory.slantLeftown(position)) != null) sum += map.get(memory.slantLeftown(position));
        if (map.get(memory.slantLeftUp(position)) != null) sum += map.get(memory.slantLeftUp(position));
        if (map.get(memory.slantRightDown(position)) != null) sum += map.get(memory.slantRightDown(position));
        if (map.get(memory.slantRightUp(position)) != null) sum += map.get(memory.slantRightUp(position));
        return sum;
    }


}

וזה מפעיל את האופרציה הזו

public class MainBoard {
    public static void main(String[] args) {

        Board board = new Board();
        board.generator(361527);//זה הקלט של הפאזל שלי

    }
}

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

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

miryeh · 24 בספטמבר,‏ 2018,‏ 7:45am

אתחיל באבחנה שכל ספירלה חדשה יוצרת ריבוע (כפי שמסומן בציור), וכל ריבוע מורכב מצלעות בגודל אי זוגי גדל ב-2.
צלע הריבוע הראשון באורך 1 יח’ ושטח 1, צלע הריבוע השני באורך 3 יח’ ושטח 9 וכן הלאה, כאשר השטח הוא הערך המופיע בפינה התחתונה-ימנית. כך אפשר לדעת מה יהיו הערכים עבור כל פינה תחתונה-ימנית בריבועים שנוצרים. (1*1, 3*3, 5*5, 7*7...)
מרחק כל פינה בריבוע שווה ערך למרחק בין קצה הצלע לאמצע כפול 2. (לדוג’, מרחק ערך 9 שווה ל- root(9) - 1)

דרך פתרון:

חישוב שורש הערך המבוקש (ע"מ למצוא את הריבוע אליו שייך)
חישוב אורך הצלע ומציאת נקודת אמצע
קירוב הערך המבוקש לצלע התחתונה (לדוג’, מרחק הערך 12 שווה ערך למרחקים עבור ערכים 16, 20 ו-24)
חישוב מרחק הערך מהאמצע.

פתרון לחלק א’

/* Find distance of given value from value '1' in a spiral DS*/
	public static int distance(int value, boolean toPrint) {
		int edgeLen = getEdge(value);
		int corner = edgeLen * edgeLen;
		if(corner == value)
			return edgeLen - 1;
		
		int midVal = corner - (edgeLen - 1) / 2;
		while(value < corner)
			value += edgeLen - 1; //advance to next edge
		value -= edgeLen - 1;
		if(toPrint)
			System.out.printf("\t edge = %d, corner = %d, mid = %d, value = %d \n",
			edgeLen, corner, midVal, value);
		return edgeLen/2 + (Math.abs(value - midVal));
	}
	
	/* Get edge of given value according to the square it belongs to*/
	public static int getEdge(int value) {
		double root = Math.sqrt(value);
		int edge = (int)root;
		if (edge % 2 == 0) //if even number, get next odd number
			edge++;
		else if (edge < root) //if not whole odd number, get next odd number
			edge += 2;
		return edge;
	}

ynonp · 25 בספטמבר,‏ 2018,‏ 7:13am

הי,

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

חלק שני

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

משבצת ראשונה מקבלת את הערך 1
משבצת שניה מקבלת את הערך 1 כי היא צמודה למשבצת הראשונה בלבד
משבצת שלישית סמוכה לשתי המשבצות הקודמות ולכן מקבלת את הערך 2 (1+1)

כמה משבצות קדימה ונקבל את הלוח:

147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...

והשאלה: בהינתן מספר - מהו הערך הראשון שגדול יותר מאותו המספר?

ynonp · 25 בספטמבר,‏ 2018,‏ 8:22am

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

defmodule Directions do
  def up({x, y}), do: { x, y - 1 }
  def down({x, y}), do: { x, y + 1 }
  def left({x, y}), do: { x - 1, y }
  def right({x, y}), do: { x + 1, y }

  def next(dir) do
    directions = [ &Directions.right/1, &Directions.up/1, &Directions.left/1, &Directions.down/1 ]
    
    idx = Enum.find_index(directions, fn(x) -> x == dir end)
    Enum.at(directions, rem(idx + 1, 4))
  end

  def available?(matrix, xy) do
    !Map.has_key?(matrix, xy)
  end
end

defmodule Day3 do

  def go1(steps, part \\&Day3.part1/3, matrix \\ %{ {0, 0} => 1 }, xy \\ {0, 0}, val \\ 1, pd \\ &Directions.down / 1)

  def go1(steps, part, matrix, xy, val, pd) when steps > 1 do
    { next_xy, next_val, next_matrix, pd } = next(matrix, xy, val, pd, part)
    go1(steps - 1, part, next_matrix, next_xy, next_val, pd)
  end

  def go1(_, _, _, {x, y}, _, _) do
    abs(x) + abs(y)
  end

  def go2(steps, part \\&Day3.part2/3, matrix \\ %{ {0, 0} => 1 }, xy \\ {0, 0}, val \\ 1, pd \\ &Directions.down / 1)

  def go2(steps, part, matrix, xy, val, pd) when val < 277678 do
    { next_xy, next_val, next_matrix, pd } = next(matrix, xy, val, pd, part)
    go2(steps - 1, part, next_matrix, next_xy, next_val, pd)
  end

  def go2(_, _, matrix, _, val, _) do
    val
  end

  def part1(_, _, val) do
    val + 1
  end

  def part2(matrix, xy, _) do
    [
      Map.get(matrix, Directions.up(xy), 0),
      Map.get(matrix, Directions.down(xy), 0),
      Map.get(matrix, Directions.left(xy), 0),
      Map.get(matrix, Directions.right(xy), 0),
      Map.get(matrix, Directions.up(Directions.right(xy)), 0),
      Map.get(matrix, Directions.up(Directions.left(xy)), 0),
      Map.get(matrix, Directions.down(Directions.left(xy)), 0),
      Map.get(matrix, Directions.down(Directions.right(xy)), 0),
    ]
    |> Enum.sum
  end

  def next(matrix, xy, val, pd, part) do
    direction = if Directions.available?(matrix, Directions.next(pd).(xy)) do
                  Directions.next(pd)
                else
                  pd
                end

    next_val = part.(matrix, direction.(xy), val)

    { direction.(xy), next_val , Map.put(matrix, direction.(xy), next_val), direction }
  end
end

System.argv()
|> Enum.at(0)
|> String.to_integer
|> Day3.go2
|> IO.inspect

splintor · 25 בספטמבר,‏ 2018,‏ 9:27am

וואו. אני לא מכיר אליקסיר בכלל, וממבט ראשון הקוד נראה לא ברור בכלל…

ynonp · 25 בספטמבר,‏ 2018,‏ 9:34am

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

וכאן:

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

בעצם הפקודה הכי חשוב היא:

Map.put(matrix, direction.(xy), next_val)

שזה מה שמוסיף את הערך החדש ללוח
(הפונקציה direction אחראית על התנועה בכיוון המתאים ו next_val מייצג את הערך הבא שצריך לכתוב)

itamard · 25 בספטמבר,‏ 2018,‏ 9:28pm

הקוד שלי לחלק הראשון של החידה: