#!/usr/local/bin/node
/*
 * ========================================
 * Super Science High Schools 科学探求
 * 数学課題研究で作ったもの
 *
 * Version 10-2017
 *
 * Licence
 *
 * Copyright 2017 2017年度2-1 SSH数学班
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * ライセンスは変更することがあります。このバージョンでは上記のライセンスが有効です。
 *
 * なるべくわかり易く書くつもり。
 * ========================================
 */

//環境変数(スネークケース...)
const X_SIZE = 31;
const Y_SIZE = 31;
const NUM_OBSTACLES = 23;
const STEP_OBSTACLE = 5;//障害物乗り越えにかかるステップ

//estateクラス
class Estate{
	/*
	 *statusの数値の意味
	 *0:道路
	 *1:住宅
	 *2:障害物
	 *3:行方不明者の位置
	 */
	constructor(x,y,numOfObstacles){
		this.size = new Object();
		this.size.x = ++x;//0~xまでのマスを作る(わかりやすくするため)
		this.size.y = ++y;//0~yまでのマスを作る(わかりやすくするため)

		this.status = new Array(x*y);//二次元配列(配列の中に配列入れることで実現)は生成がしんどいのとめんどい(ついでに少し遅い)

		for(var i=0;i<this.estate.length;i++)this.estate[i]=0;//0で初期化

		this._makeHouses();
		this._initLost();
		this._makeObstacles(numOfObstacles || 3);//default:3
	}

	posToAddr(pos){
		//TODO:範囲外Error Throw
		return (pos.x !== undefined && pos.y !== undefined)?(pos.y * this.estateSize.y + pos.x):-1;
	}

	addrToPos(addr){
		//TODO:範囲外Error Throw
		return (addr>=0)?{x: addr % this.estateSize.y, y: Math.floor(addr / this.estateSize.y)}:{x:-1,y:-1};
	}

	_fillBlock(offset_x,offset_y,size_x,size_y,num){
		if((offset_x + size_x > this.size.x)||(offset_y + size_y > this.estateSize.y))return;
		for(var y = offset_y;y < offset_y + size_y ;y++){
			for(var x = offset_x;x < offset_x + size_x;x++){
				this.estate[this.posToAddr({x:x,y:y})] = num;
			}
		}
	}

	_makeHouses(){
		//住宅生成(2x2で今は固定)
		for(var y = 1;y<this.estateSize.y;y+=1/*住宅のy間隔*/){
			for(var x = 1;x<this.estateSize.x;x+=1/*住宅のx間隔*/){
				this._fillBlock(x,y,2,2,1);
				x+=2;
			}
			y+=2;
		}
	}

	_makeObstacles(num){
		if(num>0)for(var i=0;i<num;i++)this.estate[this._selectFreeArea()]=2;
	}

	_selectFreeArea(){
		var i;
		Math.round(Date.now());
		while(i = Math.floor(Math.random() * this.estate.length),(this.estate[i] !== 0)||(i === 0));
		return i;
	}

	_initLost(){
		this.estate[this._selectFreeArea()]=3;
	}

	set lostAddr(pos){//疑似privateにすべきか
		if(pos.x === undefined || pos.y === undefined)return;
		_fillBlock(pos.x,pos.y,1,1,3);
	}

	get lostAddr(){
		return this.addrToPos(this.estate.indexOf(3));
	}

	get obstacles(){
		var list = new Array(),i = 0;//0番地は0であるという前提がある = -1;/*下で+1され0になる*/
		while(i = this.estate.indexOf(2,++i),i != -1){
			list.push(this.addrToPos(i));
		}
		return list;
	}

	get estate(){//将来のアクセス制御
		return this.status;
	}

	get estateSize(){
		return this.size;
	}
}

//Walker(捜索者)クラス
class Walker{
	constructor(){
		this.pos = {x:0,y:0};
	}

	_walk(estate,x,y){//一歩しか進めません。戻り値:かかったステップ数(0:進んでない)
		x = x || 0;
		y = y || 0;
		if(!(x && y) && (Math.abs(x+y) != 1))return 0;//一歩しか進まない
		if((this.pos + x == estate.estateSize.x))return 0;
		if((this.pos + y == estate.estateSize.y))return 0;
		var s;
		switch (estate.estate[estate.posToAddr({x:this.pos.x + x,y:this.pos.y + y})]) {
			case 0:
				this.pos.x += x;
				this.pos.y += y;
				s = 1;
				break;
			case 1:
				s  = 0;
				break;
			case 2:
				this.pos.x += x;
				this.pos.y += y;
				s = STEP_OBSTACLE;
				break;
			default:
				s = 0;
		}
		return s;
	}

	lookOutOverX(estate){
		var lost = estate.lostAddr;
		if(lost.y != this.pos.y)return false;
		var lostAddr = estate.posToAddr(lost);
		var myAddr = estate.posToAddr(this.pos);

		//行方不明者の方向へ動き、途中に障害物がないか調べる
		var s = (myAddr < lostAddr)?1:-1;
		myAddr += s;
		while(myAddr != lostAddr){
			if(estate.estate[myAddr] !== 0)return false;//注意:Walkerの位置に何か数値をつけている場合、if文に条件を加えること
			myAddr += s;
		}
		return true;
	}

	lookOutOverY(estate){
		var lost = estate.lostAddr;
		if(lost.x != this.pos.x)return false;
		var lostAddr = estate.posToAddr(lost);
		var myAddr = estate.posToAddr(this.pos);

		//行方不明者の方向へ動き、途中に障害物がないか調べる
		var s = (myAddr < lostAddr)?estate.estateSize.x:-(estate.estateSize.x);
		myAddr += s;
		while(myAddr != lostAddr){
			if(estate.estate[myAddr] !== 0)return false;//注意:Walkerの位置に何か数値をつけている場合、if文に条件を加えること
			myAddr += s;
		}
		return true;
	}

	lookOutOver(estate){
		return this.lookOutOverX(estate) || this.lookOutOverY(estate);
	}

	search(estate,rule_func){//ルールファンクションに沿って探し回る　戻り値:かかったステップ数(見つからなかった)
		var step = 0;
		var desk = new Object();
		while(!this.lookOutOver(estate)){
			var move = rule_func(estate,this.pos.x,this.pos.y,desk);
			var s = this._walk(estate,move.x,move.y);
			if(!s){
				step=-1;
				break;
			}
			step += s;
		}
		return step;
	}
}

//estate画面表示クラス
class EstatePrinter{
	constructor(){
		this.buf="";
	}

	_put(s){
		this.buf+=s;
	}

	_flush(){
		console.log(this.buf);
		this.buf="";
	}

	printAscii(estate){
		this._put("  |");
		for(var i =0;i<estate.estateSize.x;i++)this._put(i+" ");
		this._flush();

		for(var cnt_y = 0;cnt_y < estate.estateSize.y;cnt_y++,this._flush()){
			this._put(((cnt_y<10)?" ":"")+cnt_y+"|");
			for(var cnt_x = 0;cnt_x < estate.estateSize.x;cnt_x++){
				if(cnt_x>=10)this._put(" ");
				this._put(estate.estate[estate.posToAddr({x:cnt_x,y:cnt_y})]+" ");
			}
		}
	}

	log(estate){
		var pos = estate.lostAddr;
		this._put("Lost:("+pos.x+","+pos.y+");");
		this._put("Obstacles:");
		var oblist = estate.obstacles;
		for(var i = 0,len = oblist.length;i < len;i++)this._put((i?",":"")+"("+oblist[i].x+","+oblist[i].y+")");
		this._put(";");
		this._flush();
	}
}

var estate = new Estate(X_SIZE,Y_SIZE,NUM_OBSTACLES);
var printer = new EstatePrinter();
var walker = new Walker();

printer.printAscii(estate);
printer.log(estate);

//Test
var rule  = function(estate,x,y,desk){
	var pos;
	//初期化用
	if(desk.cnt_step === undefined)desk.cnt_step = estate.estateSize.x;
	if(desk.direction === undefined)desk.direction = 0;

	//方向転換
	if(!--desk.cnt_step)desk.cnt_step = (++desk.direction > 2)?((estate.estateSize.x -1) - 3*Math.floor((desk.direction -1) / 2 )):(estate.estateSize.x - 1);
	switch (desk.direction % 4) {
		case 0:
			pos = {x:1,y:0};
			break;
		case 1:
			pos = {x:0,y:1};
			break;
		case 2:
			pos = {x:-1,y:0};
			break;
		case 3:
			pos = {x:0,y:-1};
			break;
		default:
			break;
	}

	/*
	if((x == (estate.estateSize.x-1) - y)&&y<x)pos = {x:0,y:1};
	else if(x == ((estate.estateSize.y - 1) - y ))pos = {x:0,y:-1};
	else if((y > x + 3)&&  ((estate.estateSize.y - 1) - y) >=x)pos = {x:0,y:-1};
	else if( x < (estate.estateSize.x -1) - y)pos = {x:1,y:0};
	else if((x == y)&&(x>(estate.estateSize.x -1)/2)/*&&(y>(estate.estateSize.y -1)/2)/)pos = {x:-1,y:0};
	else if((((estate.estateSize.y - 1) - y) <x)&&y>x)pos = {x:-1,y:0};
	else if(y == x + 3)pos = {x:1,y:0};
	else{
		console.log("Dead!!!!");
		pos = {x:0,y:0};
	}*/
	return pos;
};

var step = walker.search(estate,rule);
console.log(step==-1?"Not found.":"Found when step is "+step+".");