Hackerrank - Cavity Map - Pavol Pidanič

Problem Statement
A description of the problem can be found on Hackerrank.

Solution
Filter all matrix indexes that are at the periphery. For all the rest choose one index and compare its value with all neighbours (left, right, up, down). If it is greater than all neighbours, replace it with 'X'.

I created solution in 4 languages:

Scala
Java
JavaScript
Ruby

All solutions are also available on my GitHub.

Scala

import scala.io.Source

object CavityMap extends App {

  val lines = Source.stdin.getLines().toList
  val n = lines.head.toInt
  val map = lines.tail.mkString

  val innerIndexes = map.indices.filter(
    i => i > n && i < n * (n - 1) - 1 && Set(Range(1, n - 1, 1) :_*).contains(i % n))
  val cavitiesIndexes = innerIndexes.filter(isCavity(map, _, n)).toSet
  println(map.indices.map(toCavity(map, cavitiesIndexes, _))
    .mkString.grouped(n).mkString("\n"))

  def neighbours(index: Int, n: Int): List[Int] = {
    List(index - 1, index + 1, index - n, index + n)
  }

  def isCavity(map: String, index: Int, n: Int): Boolean = {
    val depth = Character.digit(map.charAt(index), 10)
    neighbours(index, n).forall(i => Character.digit(map.charAt(i), 10) < depth)
  }

  def toCavity(map: String, cavities: Set[Int], index: Int) = {
    if(cavities.contains(index)) 'X' else map.charAt(index)
  }
}

import scala.io.Source

object CavityMap extends App {

val lines = Source.stdin.getLines().toList

val n = lines.head.toInt

val map = lines.tail.mkString

val innerIndexes = map.indices.filter(

i => i > n && i < n * (n - 1) - 1 && Set(Range(1, n - 1, 1) :_*).contains(i % n))

val cavitiesIndexes = innerIndexes.filter(isCavity(map, _, n)).toSet

println(map.indices.map(toCavity(map, cavitiesIndexes, _))

.mkString.grouped(n).mkString("\n"))

def neighbours(index: Int, n: Int): List[Int] = {

List(index - 1, index + 1, index - n, index + n)

}

def isCavity(map: String, index: Int, n: Int): Boolean = {

val depth = Character.digit(map.charAt(index), 10)

neighbours(index, n).forall(i => Character.digit(map.charAt(i), 10) < depth)

}

def toCavity(map: String, cavities: Set[Int], index: Int) = {

if(cavities.contains(index)) 'X' else map.charAt(index)

}

Java

import java.util.Arrays;
import java.util.Scanner;

public class CavityMap {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String[] map = new String[n];
        for (int i = 0; i < n; i++) {
            map[i] = in.nextLine();
        }
        String[] cavity = cavity(map);
        for (int i = 0; i < cavity.length; i++) {
            System.out.println(cavity[i]);
        }
        in.close();
    }

    private static String[] cavity(String[] map) {
        String[] result = Arrays.copyOf(map, map.length);
        for (int i = 1; i < map.length - 1; i++) {
            for (int j = 1; j < map.length - 1; j++) {
                if (isCavity(map, i, j)) {
                    char[] c = Arrays.copyOf(result[i].toCharArray(), result[i].toCharArray().length);
                    c[j] = 'X';
                    result[i] = String.valueOf(c);
                }
            }
        }
        return result;
    }

    private static boolean isCavity(String[] map, int i, int j) {
        int depth = Character.digit(map[i].charAt(j), 10);
        if (depth <= Character.digit(map[i - 1].charAt(j), 10)) {
            return false;
        }
        if (depth <= Character.digit(map[i].charAt(j - 1), 10)) {
            return false;
        }
        if (depth <= Character.digit(map[i + 1].charAt(j), 10)) {
            return false;
        }
        if (depth <= Character.digit(map[i].charAt(j + 1), 10)) {
            return false;
        }
        return true;
    }
}

import java.util.Arrays;

import java.util.Scanner;

public class CavityMap {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = Integer.parseInt(in.nextLine());

String[] map = new String[n];

for (int i = 0; i < n; i++) {

map[i] = in.nextLine();

}

String[] cavity = cavity(map);

for (int i = 0; i < cavity.length; i++) {

System.out.println(cavity[i]);

}

in.close();

}

private static String[] cavity(String[] map) {

String[] result = Arrays.copyOf(map, map.length);

for (int i = 1; i < map.length - 1; i++) {

for (int j = 1; j < map.length - 1; j++) {

if (isCavity(map, i, j)) {

char[] c = Arrays.copyOf(result[i].toCharArray(), result[i].toCharArray().length);

c[j] = 'X';

result[i] = String.valueOf(c);

}

return result;

}

private static boolean isCavity(String[] map, int i, int j) {

int depth = Character.digit(map[i].charAt(j), 10);

if (depth <= Character.digit(map[i - 1].charAt(j), 10)) {

return false;

}

if (depth <= Character.digit(map[i].charAt(j - 1), 10)) {

return false;

}

if (depth <= Character.digit(map[i + 1].charAt(j), 10)) {

return false;

}

if (depth <= Character.digit(map[i].charAt(j + 1), 10)) {

return false;

}

return true;

}

JavaScript

function processData(input) {
    var lines = input.split('\n');
    var n = parseInt(lines[0]);
    var result = lines[1] + "\n";
    for(var i = 2; i < lines.length - 1; i++) {
        result += lines[i][0];
        for(var j = 1; j < lines[i].length - 1; j++) {
            if(isCavity(lines, i, j)) {
                result += 'X'
            } else {
                result += lines[i][j];
            }
        }
        result += lines[i][n - 1];
        result += "\n";
    }
    if(n > 1) {
        result += lines[lines.length - 1];
    }
    console.log(result);
}

function isCavity(map, i, j) {
    var depth = parseInt(map[i][j], 10);
    if (depth <= parseInt(map[i - 1][j], 10)) {
        return false;
    }
    if (depth <= parseInt(map[i][j - 1], 10)) {
        return false;
    }
    if (depth <= parseInt(map[i + 1][j], 10)) {
        return false;
    }
    if (depth <= parseInt(map[i][j + 1], 10)) {
        return false;
    }
    return true;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

function processData(input) {

var lines = input.split('\n');

var n = parseInt(lines[0]);

var result = lines[1] + "\n";

for(var i = 2; i < lines.length - 1; i++) {

result += lines[i][0];

for(var j = 1; j < lines[i].length - 1; j++) {

if(isCavity(lines, i, j)) {

result += 'X'

} else {

result += lines[i][j];

}

result += lines[i][n - 1];

result += "\n";

}

if(n > 1) {

result += lines[lines.length - 1];

}

console.log(result);

}

function isCavity(map, i, j) {

var depth = parseInt(map[i][j], 10);

if (depth <= parseInt(map[i - 1][j], 10)) {

return false;

}

if (depth <= parseInt(map[i][j - 1], 10)) {

return false;

}

if (depth <= parseInt(map[i + 1][j], 10)) {

return false;

}

if (depth <= parseInt(map[i][j + 1], 10)) {

return false;

}

return true;

}

process.stdin.resume();

process.stdin.setEncoding("ascii");

_input = "";

process.stdin.on("data", function (input) {

_input += input;

});

process.stdin.on("end", function () {

processData(_input);

});

Ruby

def is_cavity(map, i, j)
  depth = map[i][j].to_i
  return false if (depth <= map[i - 1][j].to_i)
  return false if (depth <= map[i][j - 1].to_i)
  return false if (depth <= map[i + 1][j].to_i)
  return false if (depth <= map[i][j + 1].to_i)
  return true;
end

n = gets.to_i
map = []
n.times do
  map << gets
end

new_map = []
map.each do |m|
  new_map << m.reverse.reverse!
end

for i in 1...(n - 1) do
  for j in 1...(n - 1) do
    new_map[i][j] = 'X' if is_cavity(map, i, j)
  end
end

new_map.each do |m|
  puts m
end

def is_cavity(map, i, j)

depth = map[i][j].to_i

return false if (depth <= map[i - 1][j].to_i)

return false if (depth <= map[i][j - 1].to_i)

return false if (depth <= map[i + 1][j].to_i)

return false if (depth <= map[i][j + 1].to_i)

return true;

end

n = gets.to_i

map = []

n.times do

map << gets

end

new_map = []

map.each do |m|

new_map << m.reverse.reverse!

end

for i in 1...(n - 1) do

for j in 1...(n - 1) do

new_map[i][j] = 'X' if is_cavity(map, i, j)

end

new_map.each do |m|

puts m

end

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Cavity Map