paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 座標系での規則的な移動

座標系での規則的な移動 (paizaランク B 相当)

JavaScriptで解いてみました。いくつか解答例を載せましたので、理解しやすいもの、しっくりくるものを参考にしてみてください。

解答例1

考え方

規則性を考えると、東に1歩、南に１歩、歩く歩数が+１増えて、西に2歩、北に2歩、...となっています。

方向

まず、方向について、初め東Eを向いていて南S、西W、北Nの順に変わるので、この順で、移動方向d = ['E','S','W','N']を作ります。

方向の決め方は、dのインデックス directionでします。初期値はdirection = 0(東向き)です。

方向を変える時が来たら、direction+=1することで、右90度に方向を変えられます。directionが4になったら、また0になるように%4します。これで0,1,2,3,0,1,2,3と、4ごとに繰り返されます。

したがって、方向についてはd[direction%4]の形で管理します。

向きを変えるまでの歩数

次に、向きを変えるまでの歩数が1,1,2,2,3,3,...と変わります。

以下を用意します。

steps　//開始地点から、または、向きを変えた地点からの歩数
directionChangeSteps //向きを変えるまでの歩数

これらがsteps = directionChangeStepsとなったら、
方向を右90度変えます。これにはdirectionを+1すれば良いです。

さらに、２回方向を変えたら、向きを変えるまでの歩数が1増えるので、directionChangeStepsを+１します。

具体的には、向きを変えた回数　directionChangeCount　を用意して、方向転換ごとに1,2と増やし、2になったら、0にリセットし、
directionChangeStepsを+1します。

forループに組み込む

以上のシュミレーションを、for (let i = 1; i <= N; i++)(i歩目の移動、移動の歩数 N )のループに組み込んでいきます。

現時点の x , y 座標を用意して、１歩移動ごとに座標を更新していきます。
N歩移動し終えた時点の座標が答えです。

本解答例ではswitch文で方向を切り替えています。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//開始時点の x , y 座標を表す X , Y, 移動の歩数 N 
const [X,Y,N] = lines[0].split(" ").map((num) => num = Number(num));

//現時点の x , y 座標
let [x,y] = [X,Y];

//移動方向 d 
const d = ['E','S','W','N'];
//方向を決めるdのインデックス
let direction = 0;

let steps = 0;　//開始地点から、または、向きを変えた地点から歩いた歩数
let directionChangeSteps = 1; //向きを変えるまでの歩数
let directionChangeCount = 0;　//向きを変えた回数

//i歩目の移動、移動の歩数 N まで
for (let i = 1; i <= N; i++) {
 
    //１歩移動で座標更新(方向はE,S,W,Nを繰り返す)
     switch (d[direction % 4]) {
        //上側（ y 軸の負の向き）を北とする
        case 'N':
            y -= 1;
            break;
        
        case 'S':
            y += 1;
            break;
        
        case 'E':
            x += 1;
            break;
        
        case 'W':
            x -= 1;
            break;
    }

    //一歩移動し終えたら

    //開始地点から、または、向きを変えた地点から、歩いた歩数が１歩増える
    steps += 1;

    //開始地点から、または、向きを変えた地点から、歩いた歩数が
    //向きを変えるまでの歩数に等しい場合
    if (steps === directionChangeSteps) {
        //向きを変える
        direction += 1;
        //向きを変えた回数
        directionChangeCount += 1;
        //歩数リセット
        steps = 0;
    }
   
    //向きを変えた回数２になったら
    if (directionChangeCount === 2) {
        //回数リセット
        directionChangeCount = 0;
        //向きを変えるまで歩く歩数が１増える
        directionChangeSteps += 1;    
    }

} //for

//移動を N 歩行った後の x , y 座標 
console.log(`${x} ${y}`);

解答例2

考え方は解答例1と一緒です。ただ、1,1,2,2,3,3,...と歩くところを、加える歩数addStepにして、方向転換する歩数turnStepに、 1,2,4,6,9,12,...と累積して考えています。
加える歩数addStepは、方向転換を２回したら、1歩増えます。
また、座標x,yの移動にmove = [[1, 0], [0, 1], [-1, 0], [0, -1]];//右、下、左、上を用いてます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//開始時点の x , y 座標を表す X , Y, 移動の歩数 N 
const [X, Y, N] = lines[0].split(" ").map(Number);
//現在のx , y 座標を表す
let [x, y] = [X, Y];
//移動
let move = [[1, 0], [0, 1], [-1, 0], [0, -1]];//右、下、左、上
//moveの方向
let d = 0;//最初右向き

let turnStep = 1;//方向転換する歩数
let turnCount = 0;//転換回数
let addStep = 1;//次に方向転換する歩数分を増やす
for (let step = 1; step <= N; step++) {
    //移動する
    [x, y] = [x + move[d][0], y + move[d][1]];
    //方向転換する歩数になったら
    if (step === turnStep) {
        //方向転換
        d = (d + 1) % 4;
        turnCount += 1;
        
        //２回方向転換したら、足す歩数を１増やす
        if (turnCount === 2) {
            addStep += 1;
            turnCount = 0;//リセットする
        }
        //次に方向転換する歩数を決める
        turnStep += addStep;
    }
}
console.log(x, y);

解答例(Ruby の場合を参考)

let move = [[0, 1], [1, 0], [0, -1], [-1, 0]]を用意します。
moveの要素は[y, x]の移動量を表します。方向はインデックスcount%4で決めます。東0、南1、西2、北3となります。countは方向転換回数も兼ねています。

let timeのforループの始まりは、初期値time=0,移動幅width=0なので、方向転換をしてから進みます。方向転換をするので、turned に現在時刻time=0を代入して、count+=1で東向きcount=0に方向転換して(なのでcount初期値は-1)、移動幅width+=1してから、進みます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//開始時点の x , y 座標を表す X , Y, 移動の歩数 N 
let [x, y, N] = lines[0].split(" ").map(Number);

//移動[y, x]  方向、東0、南1、西2、北3
let move = [[0, 1], [1, 0], [0, -1], [-1, 0]];

let turned = 0;//前回の方向転換時の時刻を保持
let width = 0;//方向転換をせずに移動する幅を保持
let count = -1;//方向転換をした回数とmoveの方向を決めるインデックスを兼ねる。
               //move の定義の都合上(東が0なので)、初期値は -1

//time : 時刻(現在、何回目の移動かを保持)
for (let time = 0; time < N; time++) {

    //方向転換は決められた幅の移動を行った後
    //つまり time-turned=width が成立するとき
    //(turnedを出発してtimeまでの差がwidthの時)
    if (time - turned === width) {
        //1.turned に現在時刻を代入
        turned = time;
        //2.count を +1 する(方向転換と方向転換回数を兼ねる)
        count += 1;
        //3.count % 4 == 0 || count % 4 == 2 のとき width を +1 する
        //(方向転換0,2,4,6,...回目の時、移動幅が広がる)
        if (count % 4 === 0 || count % 4 === 2) {
            width += 1;
        }
    }
    //進む
    y += move[count % 4][0];//方向転換した回数と連動できる
    x += move[count % 4][1];
}
console.log(x, y);

解答例(C++の場合を参考)

移動を move という関数にすることでコードをみやすくしています。
現在残っている移動マス数を length で、現在の移動マス数を now で管理しています。
1マス移動するたびに length-- して、length==0 になったら、
その移動マス数での移動が 2 回目の場合と、
その移動マス数での移動が 1 回目の場合で分けます。

その移動マス数での移動が 2 回目の場合 → 方向転換をして、移動回数を 1 増やして、移動させます。

その移動マス数での移動が 1 回目の場合 → 方向転換をして、その回数でもう一度移動させます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

/*	配列 direct と、カウント変数 d で移動方向の管理をしています。 */
let direct = ['N','E','S','W'];
let d = 1;//方角directを決めるインデックス初めはdirect[1]=E東

let [x, y] = [0, 0];//移動量

/* 移動を move という関数にすることでコードをみやすくしています。*/
//移動量を関数定義
const move = (D) => {
    if(D === 'N'){
        y--;
    }else if(D === 'S'){
        y++;
    }else if(D === 'E'){
        x++;
    }else{
        x--;
    }
};

//開始時点のx座標sxとy座標sy,歩数 N
let [sx, sy, N] = lines[0].split(" ").map(Number);

/* 現在残っている移動マス数を length で、現在の移動マス数を now で管理しています。*/
let length = 1;
let now = 1;//今の移動する長さ

/*first で、その移動マス数が1回目かどうかを管理しています。*/
let first = true;

//移動
for (let i = 0; i < N; i++) {
/*1マス移動するたびに length-- して、length==0 になったら、
その移動マス数での移動が 2 回目の場合と、
その移動マス数での移動が 1 回目の場合で分けます*/
    
    move(direct[d % 4]);//移動する。ここで移動量x,yが増減する。
    length--;//移動した分長さ１減る

/* その移動マス数での移動が 2 回目の場合 → 方向転換をして、移動回数を 1 増やして、移動させます。*/

    //２回目方向転換と長さ伸ばす
    if (!first && length === 0) {//移動が１回目じゃないかつ長さが0になった
        first = true;//次は1回目、交互なので
        now++;//長さを伸ばして
        length = now;//移動リセット
        d++;//方向転換

/* その移動マス数での移動が 1 回目の場合 → 方向転換をして、その回数でもう一度移動させます。*/

    //１回目方向転換のみ    
    } else if (length === 0) {
        length = now;//移動リセットだけ
        first = false;//次は２回目、交互なので
        d++;//方向転換
    }

}
//初期値と移動量の合計を出力
console.log(sx + x, sy + y);

解答例(Python3の場合を参考)

移動を関数moveで定義してみやすくしています。
その移動マス数での移動が 1 回目の場合と ２ 回目の場合で分けています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

let [x, y, n] = lines[0].split(" ").map(Number);

//リスト directions と、カウント変数 now_direction で移動方向の管理をしています。
let directions = ["E", "S", "W", "N"];
let now_direction = 0;

//現在の移動マス数を count で、現在の方角へ進む最大のマス数を max_count で表します。
let count = 0;
let max_count = 1;

//first で、その移動マス数が1回目かどうかを管理しています。
let first = true;

//移動を move という関数にすることでコードをみやすくしています。
const move = (D, x, y) => {
    if(D === 'N'){
        y--;
    }else if(D === 'S'){
        y++;
    }else if(D === 'E'){
        x++;
    }else{
        x--;
    }
    return [x, y];//移動後のx,y座標を返す
};

//移動
for (let i = 0; i < n; i++) {
    //移動関数実行,移動後のx,y座標が返ってくる.
    [x, y] = move(directions[now_direction], x, y);

    //1マス移動するたびに count += 1 して、
    count += 1;
    //count == max_count になったら1回目、２回目で場合分け

    //その移動マス数での移動が 1 回目の場合 → 方向転換をして、その回数でもう一度移動させます。
    if (first && count === max_count) {
        first = false;//次は２回目
        count = 0;//移動マス数リセット
        now_direction = (1 + now_direction) % 4;//右90度方向転換

    //その移動マス数での移動が 2 回目の場合 → 方向転換をして、移動マス数を 1 増やして、移動させます。    
    } else if (count === max_count) {
        first = true;//次は１回目
        count = 0;//移動マス数リセット
        max_count += 1;//最大移動マス数を 1 増やす
        now_direction = (1 + now_direction) % 4;//右90度方向転換
    }    
}
//初期値と移動量の合計を出力
console.log(x, y);