Programmierwettbewerb Übung

[JennyL]

Wer ist denn dieser ominöse Tobias? Ich heiße Jenny.

 

[mrBrown]

Wer ist denn dieser ominöse Tobias? Ich heiße Jenny.

Niemand wichtiges, ist hier nur durch seinen äußerst schlechten Musikgeschmack in Erinnerung geblieben

 

[temi]

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.

Spoiler

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
    }
}

 

[JennyL]

Aber was wäre dann hiermit:

  /-> 2 -\
 /        \
1 --> 3 ---> 5 
 \        /
  \-> 4 -/

Oder ist diese "Raute" gar nicht zulässig?

 

[JennyL]

Die Kanten sollen natürlich unidirektional sein (von links nach rechts)...

 

[kneitzel]

Das ist explizit erlaubt. Die Aussage ist Zyklenfrei. Und der Graph ist auch frei von Zyklen.
https://de.wikipedia.org/wiki/Graph_(Graphentheorie) beschreibt dies und hat auch ein Beispiel für einen zyklenfreien Graphen, das ähnlich Deinem Beispiel ist. (In einem Teil des Graphen und da ging es direkt von 1 nach 5).

 

[httpdigest]

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!*

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:

Spoiler

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());
}

 

[temi]

Aber was wäre dann hiermit:
Oder ist diese "Raute" gar nicht zulässig?

Schade eigentlich, hätte klappen können.

 

[httpdigest]

Aber was wäre dann hiermit:
...die Raute...

Verstehe ich hier was nicht? Das funktioniert doch mit der Methode von @temi . Es kommt korrekterweise 3 heraus.

 

[mrBrown]

Verstehe ich hier was nicht? Das funktioniert doch mit der Methode von @temi . Es kommt korrekterweise 3 heraus.

Mit @temi's Code kommt doch 1 raus?
Der zählt doch einfach nur die Knoten ohne ausgehenden bzw eingehende Kanten, das sind in dem Beispiel nur jeweils ein Knoten.

 

[httpdigest]

Also ich habe nicht geguckt, was der Code macht, sondern ich habe ihn auf der Raute ausgeführt und da kommt 3 raus:

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
  }
}

 

[mihe7]

Also ich habe nicht geguckt, was der Code macht,

Der Vorteil von Java: write once, read never🍵

 

[httpdigest]

Ja, und ich bin auch noch dumm und hab die Raute nicht korrekt modelliert.... okay, es kommt 1 raus.
Heute ist nicht mein Tag.

 

[mrBrown]

Also ich habe nicht geguckt, was der Code macht, sondern ich habe ihn auf der Raute ausgeführt und da kommt 3 raus:

Also bei @temi's Code kommt dabei 1 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);
    }
}

 

[mihe7]

Ja, und ich bin auch noch dumm und hab die Raute nicht korrekt modelliert.... okay, es kommt 1 raus.

ECC Fehler, kommt schon mal vor

 

[LimDul]

Wenn ich nicht über den Graphen traversieren will, müsste man die Zahl der Verbindungen ins Verhältnis zu der Anzahl Knoten setzen. Darüber könnte man vermutlich was errechnen, sofern man Start & Endknoten gesondert behandelt.

Ich hab bei der Raute:
1 Start
1 Ende
5 Knoten insgesamt
6 Kanten

Ohne Formel ist klar, wenn der Graph zyklenfrei ist, bin ich nach spätestens 4 Schritten an einem Endknoten. Ergo kann 1 nicht das korrekte Ergebnis sein. Ich habe 2 Extra Kanten => also zwei Extra Pfade = 3? (Ganz so einfach wird es nicht sein vermutlich, aber wer Spaß dran hat, kann sich mal eine mathematische Formel überlegen)

 

[kneitzel]

Das wird aber nicht so trivial bleiben. Nimm zwei Rauten nacheinander. Also wenn man die letzte Raute nimmt, dann ist Knoten 1 der zweiten Raute der Knoten 5 der ersten.

Daran erkennt man, dass man das im Zusammenhang sehen muss. Die 3 "Druiden", die die Wege der erste Raute durchlaufen, können auch die Wege der zweiten Raute durchlaufen ...

 

[LimDul]

Ok, reicht doch nicht als Formel. Wenn ich bei der Raute den Pfad 2 nach 5 auf 2 nach 3 ändere bin ich immer noch zyklenfrei, die Werte (Anzahl Start,Endknoten, Knotenanzahl und Kantenanzahl) haben sich nicht geändert, ich komme aber mit 2 Druiden aus.

Da bleibt einem wohl nichts übrig als wirklich den Graph zu traversieren.

 

[httpdigest]

Hab meine Lösung von https://www.java-forum.org/thema/programmierwettbewerb-uebung.188579/page-3#post-1223642 noch etwas zusammengedampft:

Spoiler

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();
  }
}

Test mit:

System.out.println(countPaths(readGraph(new StringReader(...))));

 

[JennyL]

Es geht ohne Traversierung Zumindest, wenn es nicht mehrere Zusammenhangskomponenten gibt Aber da es ja ein Wettbewerb ist lasse ich ihn selber suchen.

 

[mrBrown]

Es geht ohne Traversierung Zumindest, wenn es nicht mehrere Zusammenhangskomponenten gibt

Also funktioniert es schon für das eine Beispiel aus der Aufgabe nicht?

 

[JennyL]

Also funktioniert es schon für das eine Beispiel aus der Aufgabe nicht?

Doch doch, wenn man einzelne Startknoten nicht als Zusammenhangskomponente betrachtet.

 

[mrBrown]

Doch doch, wenn man einzelne Startknoten nicht als Zusammenhangskomponente betrachtet.

Häh?

Sowas einfaches wie

1-->2
3-->4

klappt ja dann auch nicht, euch wenn keine einzelnen Startknoten drin vorkommen.

 

[JennyL]

Ach @mrBrown du bist doch nicht dumm, auch du darfst die Birne mal anstrengen.