The Snake vs the Wind

          The Snake vs the Wind

A group of scientists is doing some experiments with a snake. They want to measure its intelligence by observing the way it moves inside a specific area. The scientists have inserted the snake inside a two-dimensional square. They have filled the area with  mice (one in each small square of the area) in order to motivate the snake to move. The scientists know that the snake is very hungry so the snake will eat all of the mice. In order to make things more difficult for the snake, they will apply a very strong artificial wind blowing towards certain directions (north, south, west or east) that usually disturbs the snake a lot.
The scientists have seen in their previous experiments that the snake hates the wind so much so that it will try to do its best not to move in the opposite direction of the wind because its eyes are very sensitive to the dust. At any instant, the snake (greedily) prefers to move in the same direction as the wind, or if that is not possible, it would not be a problem even moving perpendicularly to the wind. The snake is very hungry so if it can see that the only possible way to eat more is to move in an opposite way to the direction of the wind, it will sacrifice a bit its eyes for its stomach.
image
The snake can make only one move in a second and it can move only up, down, right or left. Also, it cannot move in a place where it was before since we are dealing with a very long snake. The scientists decided to put the snake in one of the four corners of the area and they want you to give them the movement of the snake for each second of the journey.
Note: For a given wind's direction and the initial position of the snake, there exists only one unique path the snake will take to visit all the cells.
Input Format
In the first line, you will be given an integer  where  represents the length and width of the area in which the snake will move. In the second line, you will be given a single character (nsw, or e) which determines the direction towards which the wind blows. In the third line, you will be given the coordinates  of the corner where the snake will start the journey. The upper-left corner has the coordinates  and the lower-right corner has the coordinates .
Constraints
  • The snake will always start the journey in one of the four corners of the grid.
Output Format
Print the whole journey of the snake by outputting the time at which the snake is found in each specific part of the area. Have a look at the sample outputs for better understanding.
Sample Input 0
2
e
1 0
Sample Output 0
4 3 
1 2
Explanation 0
image
Sample Input 1
4
n
0 0
Sample Output 1
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
Explanation 1

image

Code:


Javascript:

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
input_stdin += data;
});

process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("n");
main();
});

function readLine() {
return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

var move = {
e: function(){
return [0, 1]
},
w: function(){
return [0, -1]
},
n: function(){
return [-1, 0]
},
s: function(){
return [1, 0]
}
}

function pos_dir(n, x, y, m){
if(x == 0 && y == 0)
return ['e', 's']
if(x == 0 && y == (n - 1))
return ['w','s']
if(x == n - 1 && y == 0)
return ['e', 'n']
if(x == n-1 && y == n-1)
return ['w', 'n']
return ['n','s','w','e']
}

function isTracingBack(str, nd, n, a, b){
var x = 0 + a, y = 0 + b;
var arr = str.split("");
arr.push(nd);
arr = arr.map(function(d){
var pos = move[d]()
x+= pos[0];
y+= pos[1];
return ((x >= 0 && y >= 0) && (x <= (n - 1) && y <= (n - 1))) ? (x + "," + y) : false
});
arr.unshift(a + "," + b)
var last = arr.pop();
return (last == false && typeof(last) !== "string") ? true : arr.includes(last);
}

function bet_pos(dirs, d, m, x, y, n){
var bet = (d == 'e' || d == 'w') ? 'ns' : 'ew';
if(m.dir)
dirs = dirs.filter(function(e){
return !isTracingBack(m.dir, e, n, x, y)
});
return dirs.length > 1 ? (dirs.includes(d) ? [d] : dirs.join("").match(new RegExp(`[${bet}]`)))[0] : dirs[0];
}

function findIndex(m, x, y){
return m.findIndex(function(e){
return e.join() == x + "," + y
})
}

function main() {
var n = parseInt(readLine());
var d = readLine();
var x_temp = readLine().split(' ');
var x = parseInt(x_temp[0]), a = x;
var y = parseInt(x_temp[1]), b = y;
var m = [];
m.dir = "";
for(var i = 0; i < n; i++)
for(var j = 0; j < n; j++)
m.push([i, j]);
var start = findIndex(m, x, y);
var i = 1;
m[start].push(i);
while(i < n*n){
var dirs = pos_dir(n, x, y, m),
dir = bet_pos(dirs, d, m, a, b, n);
try{
var new_pos = move[dir]();
}
catch(exp){
m[m.findIndex(function(e){
return e.length == 2
})].push(++i)
}
x += new_pos[0];
y += new_pos[1];
m.dir += dir;
try{
m[findIndex(m, x, y)].push(++i)
}
catch(err){
var idx = m.findIndex(function(e){
return e.length == 2
});
idx !== -1 ? m[idx].push(++i) : 0
}
}
var k = 0, counter = 0;
while(k < n*n){
process.stdout.write(m[k++][2] + " ")
if(counter++ == (n - 1)){
process.stdout.write("n")
counter = 0
}
}
}

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *