Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Vortex

Goal

You must crank an WxH matrix counterclockwise by X positions. To crank a matrix, you must shift each matrix element along the matrix rectangle. For example, for a 7x5 matrix with X = 1 the movements are performed this way:

v < < < < < < 
v v < < < < ^ 
v v 0 0 0 ^ ^
v > > > > ^ ^
> > > > > > ^

where the characters < ^ > v represent the displacement of a value in that position; 0 means no displacement.
 
Input
Line 1: 2 integers W and H representing the width and height (respectively) of a matrix.
Line 2: An integer X representing the number of positions to crank the matrix.
Next H lines: W matrix values v per line.
 
Output
H lines: The cranked matrix.
 
Constraints
1 ≤ W,H ≤ 50
1 ≤ X ≤ 100000000
-100 ≤ v ≤ 100

Solution

I initially wanted to come up with a mapping function, which takes the coordinate of a matrix cell and \(X\) and calculates the new position. It turned out to be a quite complicated function and I stoppd the work on it, since it wasn't that readable anymore. The actual solution I finally came up with is the most intuitive. I start at position (0, 0) and go downwards as long as I can, then continue to the right, to the up and back to the left. For each iteration, I add the elements to an array per ring. A ring is just one round around the matrix at a certain depth. On the linear arrays I can add \(X\) positions modulo the length of the ring and finally bring it back to the original matrix format. But let's do it step by step. We start with reading in the needed information:

function mod(n, m) {
    return (n % m + m) % m;
}

var inputs = readline().split(' ')

var w = +inputs[0];
var h = +inputs[1];
var k = +readline();

var x = 0
var y = 0
var dx = 0, dy = 1
var ring = 0
var rings = []
var map = []

for (var i = 0; i < h; i++) {
    map.push(readline().split(" "))
}

What now follows is exactly what I just have described. I go down, right, up left and continue that pattern one ring deeper in a spiral way:

var cur = []
for (var i = 0; i < w * h; i++) {

  cur.push(map[y][x])

  if (dx === 0 && dy === 1 && y === h - 1 - ring) {
    dx = 1
    dy = 0
  } else if (dx === 1 && dy === 0 && x === w - 1 - ring) {
    dx = 0
    dy = -1
  } else if (dx === 0 && dy === -1 && y === 0 + ring) {
    dx = -1
    dy = 0
  } else if (dx === -1 && dy === 0 && x === 1 + ring) {
    dx = 0
    dy = 1
    rings.push(cur)
    cur = []
    ring++
  }
  x+= dx
  y+= dy
}

rings.push(cur)

We now have all rings in a linear way, run over all of these rings and subtract \(X\) (which I call \(k\) in the source) as long as we are not of the inner ring of an odd height matrix. After that I screw DRY and walk again in a spiral pattern to write back the shifted data:

var x = 0
var y = 0
var dx = 0, dy = 1
for (var ring = 0; ring < rings.length; ring++) {

  if (h % 2 == 1 && ring == rings.length - 1) {
    // void
  } else  {
    rings[ring] = rings[ring].map((a, i, map) => map[mod(i - k, map.length)])
  }

  for (var i = 0; i < rings[ring].length; i++) {

    map[y][x] = rings[ring][i]
    if (dx === 0 && dy === 1 && y === h - 1 - ring) {
      dx = 1
      dy = 0
    } else if (dx === 1 && dy === 0 && x === w - 1 - ring) {
      dx = 0
      dy = -1
    } else if (dx === 0 && dy === -1 && y === 0 + ring) {
      dx = -1
      dy = 0
    } else if (dx === -1 && dy === 0 && x === 1 + ring) {
      dx = 0
      dy = 1
    }
    x+= dx
    y+= dy
  }
}

for (var i = 0; i < map.length; i++) {
  print(map[i].join(" "))
}

« Back to problem overview