Hackerrank - Flatland Space Stations

Hackerrank – Problem Statement

A description of the problem can be found on Hackerrank.

Solution

Fist I sorted the Space station, because they are not always ordered. Then I found out how many cities are between each pair of space stations i and i+1:

$((i + 1) - i - 1)$

Then I calculated the maximum distance for each city in between 2 space stations.

$ceil(towns / 2)$

In the end I compared the maximum with the distances between first no-space-station city (index 0) and first space station and the last city (index n - 1) and last space station.

I created solution in:

Scala
Java
JavaScript
Ruby

All solutions are also available on my GitHub.

Java

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        int cities = stdin.nextInt();
        int stationCount = stdin.nextInt();
        int[] stations = new int[stationCount];
        for(int i = 0; i < stationCount; i++) {
            stations[i] = stdin.nextInt();
        }
        Arrays.sort(stations);
        int max = 0;
        for(int i = 0; i < stations.length - 1; i++) {
            int citiesInside = stations[i + 1] - stations[i] - 1;
            int d = (int) Math.ceil(citiesInside / 2.0);
            if(d > max) {
                max = d;
            }
        }
        if(stations[0] - 0 > max) {
            max = stations[0] - 0;
        }
        if(cities - 1 - stations[stationCount - 1] > max) {
            max = cities - 1 - stations[stationCount - 1];
        }
        System.out.println(max);
        stdin.close();
    }
}

import java.util.*;

public class Solution {

public static void main(String[] args) {

Scanner stdin = new Scanner(System.in);

int cities = stdin.nextInt();

int stationCount = stdin.nextInt();

int[] stations = new int[stationCount];

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

stations[i] = stdin.nextInt();

}

Arrays.sort(stations);

int max = 0;

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

int citiesInside = stations[i + 1] - stations[i] - 1;

int d = (int) Math.ceil(citiesInside / 2.0);

if(d > max) {

max = d;

}

if(stations[0] - 0 > max) {

max = stations[0] - 0;

}

if(cities - 1 - stations[stationCount - 1] > max) {

max = cities - 1 - stations[stationCount - 1];

}

System.out.println(max);

stdin.close();

}

JavaScript

'use strict';

const processData = input => {
    const lines = input.split('\n');
    const [cities, stationCount] = lines[0].split(' ').map(i => parseInt(i));
    const stations = lines[1].split(' ').map(i => parseInt(i));
    stations.sort((a, b) => a - b);
    let max = 0;
    for(let i = 0; i < stations.length - 1; i++) {
        const citiesInside = stations[i + 1] - stations[i] - 1;
        const d = parseInt(Math.ceil(citiesInside / 2.0));
        if(d > max) {
            max = d;
        }
    }
    if(stations[0] - 0 > max) {
        max = stations[0] - 0;
    }
    if(cities - 1 - stations[stationCount - 1] > max) {
        max = cities - 1 - stations[stationCount - 1];
    }
    console.log(max);
};

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

let _input = "";
process.stdin.on("data", input => _input += input);
process.stdin.on("end", () => processData(_input));

'use strict';

const processData = input => {

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

const [cities, stationCount] = lines[0].split(' ').map(i => parseInt(i));

const stations = lines[1].split(' ').map(i => parseInt(i));

stations.sort((a, b) => a - b);

let max = 0;

for(let i = 0; i < stations.length - 1; i++) {

const citiesInside = stations[i + 1] - stations[i] - 1;

const d = parseInt(Math.ceil(citiesInside / 2.0));

if(d > max) {

max = d;

}

if(stations[0] - 0 > max) {

max = stations[0] - 0;

}

if(cities - 1 - stations[stationCount - 1] > max) {

max = cities - 1 - stations[stationCount - 1];

}

console.log(max);

};

process.stdin.resume();

process.stdin.setEncoding("ascii");

let _input = "";

process.stdin.on("data", input => _input += input);

process.stdin.on("end", () => processData(_input));

Scala

import scala.io.Source

object FlatlandSpaceStations extends App {
  val lines = Source.stdin.getLines().toList
  val nk = lines.head.split(" ").map(_.toInt)
  val n = nk(0)
  val spaceStations = lines(1).split(" ").map(_.toInt).sorted.toList
  val citiesInside = if(spaceStations.size > 1) spaceStations.sliding(2, 1)
    .map(item => (item(1) - item(0)).abs - 1) else Nil
  val maxDistance = ((spaceStations(0) - 0)
    :: citiesInside.map(c => (c / 2.0).ceil.toInt).toList
    ::: List((n - 1) - spaceStations.last)).max

  println(maxDistance)
}

import scala.io.Source

object FlatlandSpaceStations extends App {

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

val nk = lines.head.split(" ").map(_.toInt)

val n = nk(0)

val spaceStations = lines(1).split(" ").map(_.toInt).sorted.toList

val citiesInside = if(spaceStations.size > 1) spaceStations.sliding(2, 1)

.map(item => (item(1) - item(0)).abs - 1) else Nil

val maxDistance = ((spaceStations(0) - 0)

:: citiesInside.map(c => (c / 2.0).ceil.toInt).toList

::: List((n - 1) - spaceStations.last)).max

println(maxDistance)

}

Ruby

(cities, stationCount) = gets.strip.split.map(&:to_i)
stations = gets.strip.split.map(&:to_i).sort

max = 0
for i in (0...(stations.length - 1)) do
  cities_inside = stations[i + 1] - stations[i] - 1;
  d = (cities_inside / 2.0).ceil.to_i;
  max = d if(d > max)
end

max = stations[0] if(stations[0] - 0 > max)
max = cities - 1 - stations[stationCount - 1] if(cities - 1 - stations[stationCount - 1] > max)

puts max;

(cities, stationCount) = gets.strip.split.map(&:to_i)

stations = gets.strip.split.map(&:to_i).sort

max = 0

for i in (0...(stations.length - 1)) do

cities_inside = stations[i + 1] - stations[i] - 1;

d = (cities_inside / 2.0).ceil.to_i;

max = d if(d > max)

end

max = stations[0] if(stations[0] - 0 > max)

max = cities - 1 - stations[stationCount - 1] if(cities - 1 - stations[stationCount - 1] > max)

puts max;

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Flatland Space Stations