Hackerrank - Weighted Uniform Strings

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Nájdem si zoznam všetkých podreťazcov, ktoré obsahujú za sebou idúce znaky. Keď mám ich zoznam, vytvorím si všetky možné váhy podľa zadania.
Tzn, že každý podreťazec si rozdelím na n častí, kde n je dĺžka podreťazca. Takto získam všetky možné váhy v celom zadanom reťazci.

Nakoniec pre každé query zistím či sa nachádza vo vypočítaných váhach.

Príklad zo zadania
"abccddde":
– všetky podreťazce
— „a“ (jednotková váha 1)
— „b“ (jednotková váha 2)
— „cc“ (jednotková váha 2)
— „ddd“ (jednotková váha 4)
— „e“ (jednotková váha 5)

Potom vypočítam všetky váhy pre n častí
– „a“ -> 1
– „b“ -> 2
– „cc“ -> 1 * 3, 2 * 3 -> 3, 6
– „ddd“ -> 1 *4, 2 * 4. 3 * 4 -> 4, 8, 12
– „e“ -> 5

Všetky možné váhy : 1, 2, 3, 4, 5, 6, 8, 12

Vytvoril som riešenie v týchto programovacích jazykoch:

Scala
Java
Javascript

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Scala

import scala.io.Source

object Solution extends App {
  val lines = Source.stdin.getLines().toList
  val string = lines.head
  val queries = lines.tail.tail.map(_.toInt)

  val subs = uniformSubstrings(string)
  val substringWeights = subs.flatMap(s => {
    val c = s.charAt(0).toInt - 'a'.toInt + 1
    (1 to s.length).map(i => i * c)
  }).toSet

  queries.foreach(q => {
    val msg = if(substringWeights.contains(q)) "Yes" else "No"
    println(msg)
  })

  def uniformSubstrings(s: String): List[String] = {
    if(s.length <= 0) {
      return Nil
    }
    val c = s.charAt(0)
    val substring = s.takeWhile(_ == c)
    substring :: uniformSubstrings(s.drop(substring.length))
  }
}

import scala.io.Source

object Solution extends App {

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

val string = lines.head

val queries = lines.tail.tail.map(_.toInt)

val subs = uniformSubstrings(string)

val substringWeights = subs.flatMap(s => {

val c = s.charAt(0).toInt - 'a'.toInt + 1

(1 to s.length).map(i => i * c)

}).toSet

queries.foreach(q => {

val msg = if(substringWeights.contains(q)) "Yes" else "No"

println(msg)

})

def uniformSubstrings(s: String): List[String] = {

if(s.length <= 0) {

return Nil

}

val c = s.charAt(0)

val substring = s.takeWhile(_ == c)

substring :: uniformSubstrings(s.drop(substring.length))

}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class WeightedUniformStrings {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        String line = stdin.nextLine();
        List<Integer> queries = new ArrayList<>();
        while (stdin.hasNext()) {
            int q = Integer.parseInt(stdin.nextLine());
            queries.add(q);
        }
        queries = queries.subList(1, queries.size());
        List<String> subs = uniformSubstrings(line, new ArrayList<>());
        Set<Integer> substringWeights = subs.stream().flatMap(s -> {
            int c = s.charAt(0) - 'a' + 1;
            List<Integer> lengts = new ArrayList<>();
            for(int i = 1; i <= s.length(); i++) {
                lengts.add(i * c);
            }
            return lengts.stream();
        }).collect(Collectors.toSet());

        for(int q : queries) {
            if(substringWeights.contains(q)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static List<String> uniformSubstrings(String s, List<String> strings) {
        if(s.length() > 0) {
            char c = s.charAt(0);
            int substringIndex = takeWhile(s, c);
            String substring = s.substring(0, substringIndex);
            strings.add(substring);
            return uniformSubstrings(s.substring(substringIndex), strings);
        }
        return strings;
    }

    private static int takeWhile(String s, char c) {
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) != c) {
                return i;
            }
        }
        return s.length();
    }
}

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

import java.util.Set;

import java.util.stream.Collectors;

import java.util.stream.Stream;

public class WeightedUniformStrings {

public static void main(String[] args) {

Scanner stdin = new Scanner(System.in);

String line = stdin.nextLine();

List<Integer> queries = new ArrayList<>();

while (stdin.hasNext()) {

int q = Integer.parseInt(stdin.nextLine());

queries.add(q);

}

queries = queries.subList(1, queries.size());

List<String> subs = uniformSubstrings(line, new ArrayList<>());

Set<Integer> substringWeights = subs.stream().flatMap(s -> {

int c = s.charAt(0) - 'a' + 1;

List<Integer> lengts = new ArrayList<>();

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

lengts.add(i * c);

}

return lengts.stream();

}).collect(Collectors.toSet());

for(int q : queries) {

if(substringWeights.contains(q)) {

System.out.println("Yes");

} else {

System.out.println("No");

}

private static List<String> uniformSubstrings(String s, List<String> strings) {

if(s.length() > 0) {

char c = s.charAt(0);

int substringIndex = takeWhile(s, c);

String substring = s.substring(0, substringIndex);

strings.add(substring);

return uniformSubstrings(s.substring(substringIndex), strings);

}

return strings;

}

private static int takeWhile(String s, char c) {

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

if(s.charAt(i) != c) {

return i;

}

return s.length();

}

Javascript

'use strict';

Array.prototype.flatMap = function(lambda) {
    return Array.prototype.concat.apply([], this.map(lambda));
};

const processData = input => {
    const lines = input.split('\n');
    const line = lines[0];
    const queries = lines.slice(2).map(s => parseInt(s));

    const subs = uniformSubstrings(line, []);
    const substringWeights = subs.flatMap(s => {
        const c = s.charCodeAt(0) - 'a'.charCodeAt(0) + 1;
        const lengts = [];
        for(let i = 1; i <= s.length; i++) {
            lengts.push(i * c);
        }
        return lengts;
    });

    for(let q = 0; q < queries.length; q++) {
        const query = queries[q];
        if(substringWeights.indexOf(query) != -1) {
            console.log("Yes");
        } else {
            console.log("No");
        }
    }
};

const uniformSubstrings = (s, strings) => {
    if(s.length > 0) {
        const c = s.charAt(0);
        const substringIndex = takeWhile(s, c);
        const substring = s.slice(0, substringIndex);
        const substring2 = s.substring(substringIndex);
        strings.push(substring);
        return uniformSubstrings(substring2, strings);
    }
    return strings;
}

const takeWhile = (s, c) => {
    for(let i = 0; i < s.length; i++) {
        if(s.charAt(i) !== c) {
            return i;
        }
    }
    return s.length;
}

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

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

'use strict';

Array.prototype.flatMap = function(lambda) {

return Array.prototype.concat.apply([], this.map(lambda));

};

const processData = input => {

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

const line = lines[0];

const queries = lines.slice(2).map(s => parseInt(s));

const subs = uniformSubstrings(line, []);

const substringWeights = subs.flatMap(s => {

const c = s.charCodeAt(0) - 'a'.charCodeAt(0) + 1;

const lengts = [];

for(let i = 1; i <= s.length; i++) {

lengts.push(i * c);

}

return lengts;

});

for(let q = 0; q < queries.length; q++) {

const query = queries[q];

if(substringWeights.indexOf(query) != -1) {

console.log("Yes");

} else {

console.log("No");

}

};

const uniformSubstrings = (s, strings) => {

if(s.length > 0) {

const c = s.charAt(0);

const substringIndex = takeWhile(s, c);

const substring = s.slice(0, substringIndex);

const substring2 = s.substring(substringIndex);

strings.push(substring);

return uniformSubstrings(substring2, strings);

}

return strings;

}

const takeWhile = (s, c) => {

for(let i = 0; i < s.length; i++) {

if(s.charAt(i) !== c) {

return i;

}

return s.length;

}

process.stdin.resume();

process.stdin.setEncoding("ascii");

let _input = "";

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

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

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Weighted Uniform Strings

Hackerrank – Popis problému

Riešenie

Scala

Java

Javascript

Leave a Reply Cancel reply