Skip to content

Instantly share code, notes, and snippets.

@ArianK16a

ArianK16a/postsche_korrespondenzproblem.java

Last active June 25, 2021 13:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ArianK16a/1c52ef16f73536e877922070404e6dd6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ArianK16a/1c52ef16f73536e877922070404e6dd6 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ArianK16a revised this gist Jun 25, 2021. 1 changed file with 13 additions and 0 deletions.
    13 changes: 13 additions & 0 deletions postsche_korrespondenzproblem.java
    View file
    Original file line number Diff line number Diff line change
    @@ -53,3 +53,16 @@ static void breitensuche(Tupel... steine) {
    }

    }

    public class Tupel {
    String x;
    String y;
    String name;

    public Tupel(String x, String y, String name) {
    this.x = x;
    this.y = y;
    this.name = name;
    }
    }

  2. ArianK16a created this gist Jun 25, 2021.
    55 changes: 55 additions & 0 deletions postsche_korrespondenzproblem.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,55 @@
    import java.util.Arrays;

    public class PCP {
    final static int MAX_SIZE = 999999;
    public static void main(String[] args) {
    Tupel stein1 = new Tupel("11", "0", "a");
    Tupel stein2 = new Tupel("11", "111", "b");
    Tupel stein3 = new Tupel("1001", "1", "c");
    breitensuche(stein1, stein2, stein3);

    stein1 = new Tupel("01", "1001", "a");
    stein2 = new Tupel("10", "111", "b");
    stein3 = new Tupel("1111", "111", "c");
    Tupel stein4 = new Tupel("1001", "010", "d");
    breitensuche(stein1, stein2, stein3, stein4);

    stein1 = new Tupel("0", "1", "a");
    stein2 = new Tupel("01", "0", "b");
    stein3 = new Tupel("1", "101", "c");
    breitensuche(stein1, stein2, stein3);
    }

    static void breitensuche(Tupel... steine) {
    Tupel neue_kombinationen[] = new Tupel[MAX_SIZE];
    int i = 0;
    neue_kombinationen[i++] = new Tupel("", "", "");

    Tupel kombinationen[] = new Tupel[MAX_SIZE];

    while(true) {
    kombinationen = Arrays.copyOf(neue_kombinationen, MAX_SIZE);
    neue_kombinationen = new Tupel[MAX_SIZE];
    i = 0;

    for (Tupel kombination : kombinationen) {
    if (kombination == null) break;
    for (Tupel stein : steine) {
    String neux = kombination.x.concat(stein.x);
    String neuy = kombination.y.concat(stein.y);

    if (neux.equals(neuy)) {
    System.out.println("x: " + neux + " y: " + neuy + " name: " + kombination.name + stein.name);
    return;
    }

    int laenge = Math.min(neux.length(), neuy.length());
    if (neux.substring(0, laenge).equals(neuy.substring(0, laenge))) {
    neue_kombinationen[i++] = new Tupel(neux, neuy, kombination.name.concat(stein.name));
    }
    }
    }
    }
    }

    }