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

aoc2017
#21

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

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

לייק 1
#22

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

#23

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

2 לייקים
#24

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

לייק 1
#25

פתרון לחלק א ללא בניית לוח (Python)
הפתרון מבוסס על האלגוריתם הבא:

  1. מציאת שורש למספר הקלט
  2. מציאת אורך הצלע
  3. מציאת מרכזי הצלעות בטבעת הרלוונטית למספר הקלט
  4. מציאת המרחק הקצר ל 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
#26

לא נראה לי שאפשר לפתור את החלק השני ללא בניית הלוח
אבל לא ממש הבנתי איך לבנות אותו באמצעות מילון כמו שהסברת קודם
מה המשמעות שהמפתח הוא (0,0)?
איך התוכנית יודעת שמדובר בשורה ועמודה?

#27

התוכנית לא יודע - אתה יודע

שים לב לקטע הבא:

d = {}
d[(0, 0)] = 1
d[(0, 1)] = 2
d[(-1, 1)] = 3

ויצרת מילון.

עכשיו רק צריך להכניס את זה ללולאה ולדעת מתי להפסיק :slight_smile:

#28

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

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

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

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

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

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

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

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
#29

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

#30

עוד לא הסתכלתי :slight_smile: אני אוהב בומבות.

#31

למה d[(0, 1)] = 2 ולא 3?
ולמה d[(-1, 1)] = 3? אין ערך כזה במטריצה !

#32

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

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

פתרון חלק ראשון שלי בפייתון3 ב"גישה המתמטית":

def f(n):
    root = int((n - 1) ** 0.5)
    if root % 2 == 0:
        root -= 1
    side = root + 1
    steps_around = n - root ** 2
    v = steps_around % side
    return max(v, side - v)


assert f(12) == 3
assert f(23) == 2
assert f(1024) == 31
#34

פתרון חלק שני בפייתון3 עם מספרים מרוכבים:

around = [x + y * 1j for x in (-1, 0, 1) for y in (-1, 0, 1) if x or y]


def f2(x):
    d = {}
    p = 0 + 0j  # STARTING POINT
    v = 1  # first value
    edge = 2
    while True:
        for c in [1j, -1, -1j, 1]:  # UP, LEFT, DOWN, RIGHT
            for i in range(edge):
                d[p] = v
                if c == 1j and i == 0:
                    # Instead of edge steps UP, we need to do:
                    # 1 step RIGHT and (edge-1) steps UP
                    p += 1 + 0j
                else:
                    p += c
                v = sum(d.get(p + a, 0) for a in around)
                # print(f"{p.real:3.0f}:{p.imag:3.0f} {v:6}")
                if v > x:
                    return v

        edge += 2


assert f2(100) == 122
assert f2(300) == 304
assert f2(800) == 806