אבל עכשיו שאני רואה את החלק השני, אני רואה שהשיטה הזו כנראה לא תעבוד שם, ואני אצטרך למצוא משהו אחר…
אתגר Advent Of Code יום שלישי
לייק 1
הרגע סיימתי את החידה
את הראשון עברתי רק אחרי ההסבר המתמטי של ספילינטור
אז זה לא באמת חכמה שלי
אבל עברתי את החלק השני
הלכתי בדרך הקשה ביותר בלי פיתרון מתמטי או משהו כזה
כתבתי המון המון קוד בניתי טבלא כזו עם קי ואליו ממש כמו שינון הציע וסיימתי את החלק השני
אני מסתפק אם לשים פה את הקוד כי זה כמה מחלקות ב ג’אווה
בטח לשים 
לייק 1
מותר לשים את הפתרון לחלק השני לפני שתרגמת אותו?
הפתרון שלי ב-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);
}
}
}
לייק 1
מה זה פה בית ספר?! בטח מותר 
לייק 1
זו מחלקת עזר להיתמצאות בלוח
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);//זה הקלט של הפאזל שלי
}
}
כשאני מסתכל בפלט של ההדפסות אני רואה את הערך שגדול מהקלט שלי (יכלתי לעשות פונקציה מדויקת שמחזירה מייד אבל זה בסדר)
הקוד טיפה מבולבל ולא ערוך לגמרי
אבל הוא בונה את הלוח וזה אומר שהוא פותר את הבעיה השניה ולא הראשונה
אתחיל באבחנה שכל ספירלה חדשה יוצרת ריבוע (כפי שמסומן בציור), וכל ריבוע מורכב מצלעות בגודל אי זוגי גדל ב-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;
}
4 לייקים
הי,
מרוב שרצתם קדימה כמעט שכחתי לתרגם את החלק השני ולהעלות פיתרון שלי לשניהם, נתחיל בתרגום.
חלק שני
כחלק מתהליך הבדיקות של רכיב הזיכרון שבנינו המערכת החליטה להגביר את העומס על הרכיב ולבצע חישוב קצת שונה. הפעם שוב מתחילים ב-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---> ...
והשאלה: בהינתן מספר - מהו הערך הראשון שגדול יותר מאותו המספר?
פיתרון שלי באליקסיר לשני החלקים עם חישוב מלא של המטריצה בלי המתמטיקה:
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
וואו. אני לא מכיר אליקסיר בכלל, וממבט ראשון הקוד נראה לא ברור בכלל…
זאת שפה מגניבה - היא כולה פונקציונאלית וכל המידע שם הוא Immutable. לכן אין לולאות אלא רק רקורסיות. כתבתי עליה קצת כאן:
וכאן:
הנקודה שכדאי להתחיל להסתכל ממנה על התוכנית שלי היא הפונקציה next: היא בעצם לוקחת את ה Dictionary של הלוח ומוסיפה לו ערך חדש במקום המתאים. הפונקציה שקוראת לה - go היא זו שמריצה את הלולאה.
בעצם הפקודה הכי חשוב היא:
Map.put(matrix, direction.(xy), next_val)
שזה מה שמוסיף את הערך החדש ללוח
(הפונקציה direction אחראית על התנועה בכיוון המתאים ו next_val מייצג את הערך הבא שצריך לכתוב)
לייק 1
הקוד שלי לחלק הראשון של החידה:
לייק 1
הי @itamard וכיף שהצטרפת למשחק!
אם כבר HTML - יהיה מעניין לקחת את הצעד הבא ולהוסיף אנימציה שהלוח מתמלא. מה דעתך?
לייק 1
לא הפתרון הכי יפה ויזאולית, אבל זה מה שיצא לי:
שמת לב שהלוח אצלך מופיע ״במכה אחת״ במקום באנימציה. אני חושב שמה שהיית רוצה זה להוסיף סוג של ״sleep״ בתוך לולאת ה for שלך בין ציור כל מספר. כאן יש הסבר שכתבתי על מימוש sleep כזה שייתן לך את הציור באנימציה:
2 לייקים
הצלחתי ליצור אנימציה ככה שכל פעם יודפסו שתי צלעות נוספות של הריבוע.
לייק 1
פתרון לחלק א ללא בניית לוח (Python)
הפתרון מבוסס על האלגוריתם הבא:
- מציאת שורש למספר הקלט
- מציאת אורך הצלע
- מציאת מרכזי הצלעות בטבעת הרלוונטית למספר הקלט
- מציאת המרחק הקצר ל 1 ע"י חישוב של מחצית אורך הצלע + נק’ האמצע הקרובה למספר הקלט
"Part 1: find the minimal way to 1 in spiral board"
import math
dif_list = []
input_num = float(raw_input("Enter No "))
num = math.sqrt(input_num)
dot,number = math.modf(num)
if dot == 0 and number % 2 != 0:
res = num -1
else: #
number += 1
if number % 2 == 0:
number += 1
side_dis = number - 1 #side distance
middle1 = number **2 - side_dis/2 #find the middle of each side
middle2 = middle1 - side_dis
middle3 = middle2 - side_dis
middle4 = middle3 - side_dis
value_list = [middle1,middle2,middle3,middle4]
for i in value_list: #find the shortest distance from input_num to the middle point
dif = input_num - i
if dif < 0:
dif *= -1
dif_list.append(dif)
res = min(dif_list) + side_dis/2 #find the shortest distance to 1
print int(res)
לייק 1
לא נראה לי שאפשר לפתור את החלק השני ללא בניית הלוח
אבל לא ממש הבנתי איך לבנות אותו באמצעות מילון כמו שהסברת קודם
מה המשמעות שהמפתח הוא (0,0)?
איך התוכנית יודעת שמדובר בשורה ועמודה?
התוכנית לא יודע - אתה יודע
שים לב לקטע הבא:
d = {}
d[(0, 0)] = 1
d[(0, 1)] = 2
d[(-1, 1)] = 3
ויצרת מילון.
עכשיו רק צריך להכניס את זה ללולאה ולדעת מתי להפסיק
הפתרון שלי לחלק הראשון, בג’אווה סקריפט. מאמין שאפשר יהיה לכתוב משהו יעיל יותר. אחרי כמה שעות של חקירה של המטריצה המיוחדת הזאת (הכרחתי את עצמי לא להסתכל בפתרונות או ויקיפדיה) עשיתי לעצמי רשימה של תת בעיות על מנת להגיע לפתרון הגדול.
בהתחלה חיפשתי כל מיני אלגוריתמים שיתנו לי באמת את הדרך הקצרה לאמצע, אחת הדרכים שזללה לי קצת יותר מידי זמן (בסוף בחרתי בדרך אחרת, בהמשך) היא ללכת כל פעם למספר הקטן ביותר שנמצא מימין\שמאל\מעל\מתחת למספר שבו אני נמצא כרגע, אך בשביל זה הייתי צריך לבנות את המטריצה, זה קצת עצבן אותי אז חיפשתי דרך קלה יותר.
הדרך היותר קלה היא ללכת תמיד לכיוון האנך האמצעי הקרוב מהמרכז. בשביל זה פירקתי את הבעיה לתתי בעיות הבאות:
- מציאת רדיוס (מרחק מהאמצע) בהינתן מספר.
- יצירת מערך של מערכי המספרים בגבולות. יעזור לי למצוא את הגבול שעליו נמצא המספר הנתון.
- מציאת מרחק למרכז הגבול (האנך האמצעי למרכז)
- חישוב המרחק הסופי.
כמה נקודות מעניינות שהצלחתי למצוא:
- המספר הנתון תמיד ימצא על הגבול, זאת אומרת ברדיוס מסויים מהמרכז, אין טעם לחפש בגבולות רחוקים יותר.
- את הרדיוס מאוד פשוט לחשב על ידי מציאת תקרת השורש של המספר, אם הוא אי זוגי אז זהו הרדיוס, אם הוא זוגי תוסיף אחד וזהו הרדיוס.
בקיצור זהו הקוד שלי בסופו של דבר, אני אוליי אנסה למצוא חידודים לפונקצייה שבונה את הגבולות
function getRadius(number){
let sqr = Math.ceil(Math.sqrt(number));
return sqr % 2 == 1 ? sqr : sqr + 1;
}
function getBordersFor(radius){
let outer = radius * radius;
let borders = [[outer],[],[],[]];
outer--;
for(let i = 0; i < 4; i++){
let border = [];
for(let j = 0; j < radius - 1; j++){
border.push(outer - (i + j));
}
borders[i] = borders[i].concat(border);
outer -= (radius - 2);
}
return borders;
}
function getBorderForInput(input){
let borders = getBordersFor(getRadius(input));
return borders.find(b => b.indexOf(input) > -1);
}
function getDistance(input){
let radius = getRadius(input);
let border = getBorderForInput(input);
let middle = border[Math.floor(((border.length-1)/2))];
let stepsToMiddle = Math.abs(middle - input);
return stepsToMiddle + Math.floor(radius / 2);
}
לייק 1