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

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

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

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

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

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

miryeh · 21 בספטמבר,‏ 2018,‏ 11:01pm

לגמרי 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:46pm

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

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

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

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

בטח לשים

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

מותר לשים את הפתרון לחלק השני לפני שתרגמת אותו?
הפתרון שלי ב-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:50am

אתחיל באבחנה שכל ספירלה חדשה יוצרת ריבוע (כפי שמסומן בציור), וכל ריבוע מורכב מצלעות בגודל אי זוגי גדל ב-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:37am

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

וכאן:

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

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

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

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

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

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

ynonp · 26 בספטמבר,‏ 2018,‏ 5:03am

הי @itamard וכיף שהצטרפת למשחק!

אם כבר HTML - יהיה מעניין לקחת את הצעד הבא ולהוסיף אנימציה שהלוח מתמלא. מה דעתך?

itamard · 26 בספטמבר,‏ 2018,‏ 4:19pm

לא הפתרון הכי יפה ויזאולית, אבל זה מה שיצא לי:

ynonp · 26 בספטמבר,‏ 2018,‏ 6:36pm

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

itamard · 26 בספטמבר,‏ 2018,‏ 7:30pm

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