Niemand wichtiges, ist hier nur durch seinen äußerst schlechten Musikgeschmack in Erinnerung gebliebenWer ist denn dieser ominöse Tobias? Ich heiße Jenny.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.Scanner;
public class Droid {
public static int calcDroids(Reader reader) throws IOException {
BufferedReader br = new BufferedReader(reader);
int numPlanets = Integer.valueOf(br.readLine());
int[] in = new int[numPlanets];
int[] out = new int[numPlanets];
for (int from = 0; from < numPlanets; from++) {
try (Scanner s = new Scanner(br.readLine())) {
int numOut = s.nextInt();
if (numOut > 0) {
out[from]++;
}
for (int to = 0; to < numOut; to++) {
in[s.nextInt()]++;
}
}
}
int numOuts = 0;
for (int o : out) {
if (o == 0) numOuts++;
}
int numIns = 0;
for (int i : in) {
if (i == 0) numIns++;
}
return Math.max(numIns, numOuts);
}
public static void main(String[] args) throws IOException {
// Erstes Beispiel in der Aufgabe
System.out.println(calcDroids(new StringReader(
"4\n" +
"1 1\n" +
"1 2\n" +
"0\n" +
"1 1"
))); // <- 2
// Zweites Beispiel in der Aufgabe
System.out.println(calcDroids(new StringReader(
"6\n" +
"0\n" +
"1 2\n" +
"2 4 5\n" +
"1 2\n" +
"0\n" +
"0"
))); // <- 3
// httpdigest eigenes Beispiel
System.out.println(calcDroids(new StringReader(
"10\n" +
"1 4\n" +
"1 4\n" +
"1 4\n" +
"1 4\n" +
"1 5\n" +
"1 6\n" +
"3 7 8 9\n" +
"0\n" +
"0\n" +
"0\n"
))); // <- 4
// mrBrowns Gegenbeispiel
System.out.println(calcDroids(new StringReader(
"3\n" +
"2 1 2\n" +
"0\n" +
"0\n"
))); // <- 2
// httpdigests Gegenbeispiel
System.out.println(calcDroids(new StringReader(
"7\n" +
"1 2\n" +
"1 2\n" +
"4 3 4 5 6\n" +
"0\n" +
"0\n" +
"0\n" +
"0"
))); // <- 4
}
}
Die Lösung finde ich richtig super! Man könnte eventuell noch BitSet nutzen, um sich ein paar Schleifen (und ein bisschen Speicher) zu sparen, aber ändert selbstverständlich nichts an der Natur des Algorithmus:Reicht es evtl. aus, zu zählen wieviele Startpunkte es gibt, die keine Endpunkte sind, und wieviele Endpunkte, die keine Startpunkte sind? Die Lösung ist dann der größere der beiden Werte.
*snip von wirklich coolem Code!*
public static int calcDroids(Reader reader) throws IOException {
BufferedReader br = new BufferedReader(reader);
int numPlanets = Integer.valueOf(br.readLine());
BitSet in = new BitSet(numPlanets), out = new BitSet(numPlanets);
for (int from = 0; from < numPlanets; from++)
try (Scanner s = new Scanner(br.readLine())) {
int numOut = s.nextInt();
out.set(from, numOut > 0);
for (int to = 0; to < numOut; to++)
in.set(s.nextInt());
}
return numPlanets - Math.min(in.cardinality(), out.cardinality());
}
Schade eigentlich, hätte klappen können.Aber was wäre dann hiermit:
Oder ist diese "Raute" gar nicht zulässig?
Verstehe ich hier was nicht? Das funktioniert doch mit der Methode von @temi . Es kommt korrekterweise 3 heraus.Aber was wäre dann hiermit:
...die Raute...
Mit @temi's Code kommt doch 1 raus?Verstehe ich hier was nicht? Das funktioniert doch mit der Methode von @temi . Es kommt korrekterweise 3 heraus.
import static java.lang.Integer.parseInt;
import static java.lang.Math.min;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.BitSet;
import java.util.Scanner;
public class Droid {
// Folgendes ist 100% äquivalent zu temis Code:
public static int calcDroids(Reader reader) throws IOException {
BufferedReader br = new BufferedReader(reader);
int numPlanets = parseInt(br.readLine());
BitSet in = new BitSet(numPlanets), out = new BitSet(numPlanets);
for (int from = 0; from < numPlanets; from++)
try (Scanner s = new Scanner(br.readLine())) {
int numOut = s.nextInt();
out.set(from, numOut > 0);
for (int to = 0; to < numOut; to++)
in.set(s.nextInt());
}
return numPlanets - min(in.cardinality(), out.cardinality());
}
public static void main(String[] args) throws IOException {
// Raute
System.out.println(calcDroids(new StringReader(
"5\n" +
"1 1 2 3\n" +
"1 4\n" +
"1 4\n" +
"1 4\n" +
"0\n"
))); // <- 3
}
}
Der Vorteil von Java: write once, read never🍵Also ich habe nicht geguckt, was der Code macht,
Also bei @temi's Code kommt dabei 1 rausAlso ich habe nicht geguckt, was der Code macht, sondern ich habe ihn auf der Raute ausgeführt und da kommt 3 raus:
import java.io.*;
import java.util.*;
public class Droid {
public static int calcDroids(Reader reader) throws IOException {
BufferedReader br = new BufferedReader(reader);
int numPlanets = Integer.parseInt(br.readLine());
int[] in = new int[numPlanets];
int[] out = new int[numPlanets];
for (int from = 0; from < numPlanets; from++) {
try (Scanner s = new Scanner(br.readLine())) {
int numOut = s.nextInt();
if (numOut > 0) {
out[from]++;
}
for (int to = 0; to < numOut; to++) {
in[s.nextInt()]++;
}
}
}
int numOuts = 0;
for (int o : out) {
if (o == 0) {
numOuts++;
}
}
int numIns = 0;
for (int i : in) {
if (i == 0) {
numIns++;
}
}
return Math.max(numIns, numOuts);
}
public static void main(String[] args) throws IOException {
int droids = calcDroids(new StringReader("""
5
3 1 2 3
1 4
1 4
1 4
0
"""
));
assert droids == 3 : "Drei Droiden benötigt";
System.out.println(droids);
}
}
ECC Fehler, kommt schon mal vorJa, und ich bin auch noch dumm und hab die Raute nicht korrekt modelliert.... okay, es kommt 1 raus.
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.of;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.Scanner;
import java.util.function.Function;
public class PathCover {
static class Node {
List<Node> in = new ArrayList<>();
List<Node> out = new ArrayList<>();
boolean deleted;
}
private static boolean walk(Node n, Function<Node, List<Node>> l) {
return (
nextNode(l.apply(n)).map(vt -> walk(vt, l)).orElse(true) &&
!nextNode(l.apply(n)).isPresent()
) && (n.deleted = true);
}
private static Optional<Node> nextNode(List<Node> l) {
return l.stream().filter(n -> !n.deleted).findFirst();
}
private static boolean walk(Node n) {
return walk(n, no -> no.in) && walk(n, no -> no.out);
}
public static Node[] readGraph(Reader r) throws IOException {
BufferedReader br = new BufferedReader(r);
int numVertices = Integer.valueOf(br.readLine());
Node[] vs = range(0, numVertices).mapToObj(__ -> new Node()).toArray(Node[]::new);
for (int i = 0; i < numVertices; i++) {
try (Scanner s = new Scanner(br.readLine())) {
int numOut = s.nextInt();
for (int j = 0; j < numOut; j++) {
int o = s.nextInt();
vs[i].out.add(vs[o]);
vs[o].in.add(vs[i]);
}
}
}
return vs;
}
public static int countPaths(Node[] ns) {
return (int) of(ns).filter(n -> !n.deleted).peek(PathCover::walk).count();
}
}
System.out.println(countPaths(readGraph(new StringReader(...))));
Also funktioniert es schon für das eine Beispiel aus der Aufgabe nicht?Es geht ohne Traversierung Zumindest, wenn es nicht mehrere Zusammenhangskomponenten gibt
Doch doch, wenn man einzelne Startknoten nicht als Zusammenhangskomponente betrachtet.Also funktioniert es schon für das eine Beispiel aus der Aufgabe nicht?
Häh?Doch doch, wenn man einzelne Startknoten nicht als Zusammenhangskomponente betrachtet.
1-->2
3-->4