Hackerrank - Manasa and Stones

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

Solution
The result is set of leaves of a tree in depth n with a stating root 0 and every child is calculated as: parent + a and parent + b.

I created solution in:

Java
JavaScript
Scala
Ruby

All solutions are also available on my GitHub.

Java

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class ManasaAndStones {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        int tests = stdin.nextInt();
        for(int i = 0; i < tests; i++) {
            int n = stdin.nextInt();
            int a = stdin.nextInt();
            int b = stdin.nextInt();
            Set<Integer> set = new TreeSet<Integer>();
            set.add(0);
            for(int j = 1; j < n; j++) {
                Set<Integer> newSet = new TreeSet<Integer>();
                for(int el : set) {
                    newSet.add(el + a);
                    newSet.add(el + b);
                }
                set = newSet;
            }
            System.out.println(set.stream()
                    .map(item -> item.toString()).collect(Collectors.joining(" ")));
        }
    }
}

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

import java.util.stream.Collectors;

public class ManasaAndStones {

public static void main(String[] args) {

Scanner stdin = new Scanner(System.in);

int tests = stdin.nextInt();

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

int n = stdin.nextInt();

int a = stdin.nextInt();

int b = stdin.nextInt();

Set<Integer> set = new TreeSet<Integer>();

set.add(0);

for(int j = 1; j < n; j++) {

Set<Integer> newSet = new TreeSet<Integer>();

for(int el : set) {

newSet.add(el + a);

newSet.add(el + b);

}

set = newSet;

}

System.out.println(set.stream()

.map(item -> item.toString()).collect(Collectors.joining(" ")));

}

JavaScript

function processData(input) {
    var numbers = input.split("\n").map(function(i) {return parseInt(i); });
    var index = 0;
    var tests = numbers[index++];

    for(var i = 0; i < tests; i++) {
        var n = numbers[index++];
        var a = numbers[index++];
        var b = numbers[index++];
        var hashMap = {};
        hashMap[0] = 1;
        for(var j = 0; j < n - 1; j++) {
            var newHashMap = {};
            for(prop in hashMap) {
                if(hashMap.hasOwnProperty(prop)) {
                    var depth = hashMap[prop];
                    var newA = parseInt(prop) + a;
                    var newB = parseInt(prop) + b;
                    var newDepth = depth + 1;
                    newHashMap[newA] = newDepth;
                    newHashMap[newB] = newDepth;
                }
            }
            hashMap = newHashMap;
        }

        var res = [];
        for(p in hashMap) {
            if(hashMap.hasOwnProperty(p)) {
                res.push(parseInt(p));
            }
        }

        console.log(res.join(" "));
    }
}

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 numbers = input.split("\n").map(function(i) {return parseInt(i); });

var index = 0;

var tests = numbers[index++];

for(var i = 0; i < tests; i++) {

var n = numbers[index++];

var a = numbers[index++];

var b = numbers[index++];

var hashMap = {};

hashMap[0] = 1;

for(var j = 0; j < n - 1; j++) {

var newHashMap = {};

for(prop in hashMap) {

if(hashMap.hasOwnProperty(prop)) {

var depth = hashMap[prop];

var newA = parseInt(prop) + a;

var newB = parseInt(prop) + b;

var newDepth = depth + 1;

newHashMap[newA] = newDepth;

newHashMap[newB] = newDepth;

}

hashMap = newHashMap;

}

var res = [];

for(p in hashMap) {

if(hashMap.hasOwnProperty(p)) {

res.push(parseInt(p));

}

console.log(res.join(" "));

}

process.stdin.resume();

process.stdin.setEncoding("ascii");

_input = "";

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

_input += input;

});

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

processData(_input);

});

Scala

import scala.collection.immutable.TreeSet
import scala.io.Source

object ManasaAndStones extends App {
  val console = Source.stdin.bufferedReader()
  val t = console.readLine().toInt
  (1 to t).foreach {
    i =>
      val n = console.readLine().toInt
      val a = console.readLine().toInt
      val b = console.readLine().toInt
      println(treasures(Set(0), 1, n, a, b).mkString(" "))
  }

  def treasures(l: Set[Int], depth: Int, n: Int, a: Int, b: Int): Set[Int] = {
    if(depth == n) l
    else treasures(TreeSet((l.map(_ + a).toList ++ l.map(_ + b).toList) :_*), depth + 1, n, a, b)
  }
}

import scala.collection.immutable.TreeSet

import scala.io.Source

object ManasaAndStones extends App {

val console = Source.stdin.bufferedReader()

val t = console.readLine().toInt

(1 to t).foreach {

i =>

val n = console.readLine().toInt

val a = console.readLine().toInt

val b = console.readLine().toInt

println(treasures(Set(0), 1, n, a, b).mkString(" "))

}

def treasures(l: Set[Int], depth: Int, n: Int, a: Int, b: Int): Set[Int] = {

if(depth == n) l

else treasures(TreeSet((l.map(_ + a).toList ++ l.map(_ + b).toList) :_*), depth + 1, n, a, b)

}

Ruby

require "set"

tests = gets.to_i
tests.times do
  n = gets.to_i
  a = gets.to_i
  b = gets.to_i
  set = SortedSet.new([0])
  (n - 1).times do
    new_set = SortedSet.new
    set.each do |element|
      new_set << element + a
      new_set << element + b
    end
    set = new_set
  end
  puts set.to_a.join(" ")
end

require "set"

tests = gets.to_i

tests.times do

n = gets.to_i

a = gets.to_i

b = gets.to_i

set = SortedSet.new([0])

(n - 1).times do

new_set = SortedSet.new

set.each do |element|

new_set << element + a

new_set << element + b

end

set = new_set

end

puts set.to_a.join(" ")

end

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Manasa and Stones