יום 5 - מבוך הטרמפולינות

מבוך הטרמפולינות

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

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

אבל מה שבאמת מפחיד זה שהפקודות משתנות תוך כדי ריצה: כך אם הגעתם למקפצה עם הערך 2, אחרי הקפיצה ערכה יעלה ל-3. אני חושב שדוגמא קצרה תעזור להבהיר את הכוונה.

נניח שקיבלנו את רשימת הפקודות:

0
3
0
1
-3

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

(0) 3  0  1  -3

סימן סוגריים עגולים מציין את המקום הנוכחי.

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

(1) 3  0  1  -3 

עכשיו אפשר לקפוץ לפקודה הבאה ולכן נקבל:

2 (3) 0  1  -3

עזבנו את ה-1 ולכן הוא הפך ל-2, ואנחנו עכשיו ב-3. מכאן ממשיכים ל:

2  4  0  1 (-3)

ואז ל:

2 (4) 0  1  -2

ועוד צעד אחד ואנחנו בחוץ!

2  5  0  1  -2 

סך הכל תוך 5 צעדים יצאנו מהמבוך.

כתבו תוכנית שמקבלת כזה מבוך ומספרת כמה צעדים ייקח להגיע ליציאה. אחרי זה תמשיכו לאתר של אריק לקחת את הכוכב שלכם:
https://adventofcode.com/2017/day/5

הפתרון שלי:

לי היה פתרון דומה, עם הקוד שמנתח את הקלט:

function machine(s) {
    const steps = s.split(/[\r\n]+/).map(l => Number(l));
    let counter = 0, index = 0;
    while (index < steps.length) {
        const step = steps[index];
        ++steps[index];
        index += step;
        ++counter;
    }

    return counter;
}

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

function machine2(s) {
    const steps = s.split(/[\r\n]+/).map(l => Number(l));
    let counter = 0, index = 0;
    while (index < steps.length) {
        const step = steps[index];
        if (step >= 3) {
            --steps[index];
        } else {
            ++steps[index];
        }
        index += step;
        ++counter;
    }

    return counter;
}

אגב JavaScript - גירסא שכתבתי בריאקט להמחשת התנועה:

פיתרון מלא שלי ב perl:

use strict;
use v5.18;

my @program = <>;
my $pc = 0;
my $steps = 0;

while ($pc < @program) {
  $pc += $program[$pc] >= 3 ? $program[$pc]-- : $program[$pc]++;
  $steps++;
}

say "Took $steps steps";

הזכיר לי כמה אני אוהב את השפה הזו