Challenge 15

19/01/26 08:13
package net.p3consulting.so.challenges;

import java.util.*;
import java.util.stream.Collectors;

public class Challenge15 {

  private static class Pair {
  char a ;
  char b ;

  @Override
  public boolean equals(Object o) {
   nbsp;if (this == o) return true;
   nbsp;if (o == null || getClass() != o.getClass()) return false;
   nbsp;Pair pair = (Pair) o;
   nbsp;return a == pair.a && b == pair.b;
  }

  @Override
  public int hashCode() {
    return Objects.hash(a, b);
  }

    public Pair(final char from, final char to) {
    this.a = from ;
    this.b = to ;
  }

  @Override
  public String toString() {
    return "Pair{" + a +
    " -> " + b +
    '}';
    }
  }

  private static final String[] dictionary = {
    "⪏⊕⪏⊥⊛", "⪏⊕⇲⊢⪏", "⪏⊟⊞⊝◴⇲◉", "⪏⊞⊢⪏◉", "⪏⨙↪⊡⇲", "⪏⊛⊟⇲⊣↔", "⪏⊝⊛∭⊞↔⪏", "⪏⊣⊞৲⇲◉" ,
    "⊚⪏⊢⇲◉", "⊚↔⊚⊝↔⇲", "⊚⇲⊤⊣⇲", "⊚⊢⇲⚆⊛",
    "⊕⪏⊝⪏", "⊕⊛", "⊕⊢⪏৲৲⪏", "⊕⊤⊣⪏↔⊠⪏",
    "⊟⪏◉⇲◉", "⊟⊞⊣⊡⊢⇲", "⊟⊢⇲৲⇲◉",
    "⊞⊟↪", "⊞↔⊠⇲⊣⪏", "⊞⊝⊞⊤∭⊞⊢↔⪏", "⊞⊝⊥↔⊟⪏", "⊞⊗⇲⊟⇲◉", "⊞⊢↪⊡⪏",
    "⊛⊝↔⇲◉", "⊛৲⊞⊢⪏",
    "∭⪏⊝⪏◉◉⪏", "∭⊞⇲◉",
    "↔⊟⊞⪏", "↔◉⇲◉", "↔◉⊡⇲⊢↔⪏", "↔⚆∭⊤◉",
    "⊠⪏⨙⪏⊣↔", "⊠⪏⊠⇲◉", "⊠⪏⊝⇲◉", "⊠⪏⊢⊟↔⪏", "⊠⇲◉৲⇲◉",
    "⊝⊞⊗⊛", "⊝↔৲⊣⊛", "⊝⇲⊕⇲◉",
    "৲⪏⨙↔", "৲⪏⊡↔", "৲⊞⊝↔", "৲⊞⊢⪏",
    "⊣⊞⊢⇲", "⊣⊛◉↔", "⊣⊤⚆⊡⪏",
    "⊗⊞⊣⇲◉", "⊗⊤⊝⇲",
    "⇲৲⇲⊢◴⇲", "⇲⊣⊞↔⊢⇲", "⇲⊗⊤", "⇲⊢⇲◉",
    "⊥⪏↔⊟↔", "⊥⇲⊝⊛", "⊥⇲⊡⪏৲⇲◉", "⊥⊤⊢", "⊢↔⨙⪏", "⊢⇲⊟⇲",
    "◉⊥↔⊡↔", "◉⊡⇲৲⪏",
    "⊡⪏⊗⊛", "⊡⊞⚆⊣⊛", "⊡⇲⊥⇲◉",
    "⊤⊕⊢⇲", "⊤⊥⊣⇲◉",
    "◴↔⊝⇲◉", "◴⊤◉⊛", "◴↪◉",
    "⚆⪏⊢⪏", "⚆⊢⇲⊣⇲◉", "⚆↪⊢⪏",
    "⊜⪏⊢↔", "⊜⊤⚆⊛",
    "↪⊠⊞⪏⊣⇲◉", "↪⊢⪏"
  };

  public static void main(final String[] args) {
    final Set pairs = new HashSet<>();
    final Set origins = new HashSet<>();
    final Set ends = new HashSet<>();

    for (int startRn = 0 ; startRn < dictionary.length ; startRn++) {
      for (int idx = 0; idx < dictionary[startRn].length() ; idx++) {
        int pivotRn = -1;
        // look for the first data greater than the current char position
        for (int rn = startRn; rn < dictionary.length; rn++) {
          if (dictionary[rn].length() > idx) {
            pivotRn = rn;
            break;
          }
        }

        char charToCompare = dictionary[pivotRn].charAt(idx);
        origins.add(charToCompare);

        final String commonPrefix = dictionary[pivotRn].substring(0, idx) ;

        // all characters at pos idx in entries > pivotRn must be a pair
        for (int nextRn = pivotRn; nextRn < dictionary.length; nextRn++) {

          if (dictionary[nextRn].length() > idx) {
        // the string is larger enough
        // the commonPrefix must be common
        final String curPrefix = dictionary[nextRn].substring(0, idx) ;

        if (commonPrefix.equals(curPrefix) &&
          charToCompare != dictionary[nextRn].charAt(idx)) {
            // don't add a cycle on itself
            final char end = dictionary[nextRn].charAt(idx);
            final Pair p2Add = new Pair(charToCompare, end);
            if (!pairs.contains(p2Add)) {
              pairs.add(p2Add);
              ends.add(end);
            }
          }
        }
      }
    }
  }

    // here we have all the pairs (a,b) where a < b according to the given info
    // we must find the Pairs where A is not a B in any other, to get start of alphabet
    Set possibleNexts = origins.stream()
    .filter(x -> !ends.contains(x)).collect(Collectors.toSet());
    if (possibleNexts.isEmpty()) {
  System.err.println("No possible start of alphabet found: cycles my be present");
  }
  else if (possibleNexts.size() > 1) {
    System.err.println("Ambiguities: several characters may start the alphabet: " + possibleNexts);
  }
  else {
    String alphabet = "" ;
    final Set processed = new HashSet<>();

    Character processing = possibleNexts.iterator().next();
    // System.out.println("Alphabet:\n" + processing);
    processed.add(processing);
    alphabet += processing ;

    boolean doContProcessing = true;
    while (doContProcessing) {
      // START -> X? find the Pair P having A == processing
      // and where not exists another Pair P1 where P1.B = P.B and P1.A not in processed
      possibleNexts = pairs.stream().filter(
      p-> pairs.stream().noneMatch(
        p1 -> p1.b == p.b && !processed.contains(p1.a)
      )
    ).map(p -> p.b)
    .filter(c -> !processed.contains(c))
    .collect(Collectors.toSet()) ;

          if (possibleNexts.isEmpty()) {
            if (processed.size() != origins.size()) {
              System.err.println("No possible next character: cycles may be present");
              System.err.println("# processed: " + processed.size() + ", origins: " + origins.size());
            }
            doContProcessing = false;
          }
          else if (possibleNexts.size() > 1) {
            System.err.println("Ambiguities: several characters may continue the alphabet: " + possibleNexts);
            doContProcessing = false;
          }
          else {
            processing = possibleNexts.iterator().next();
            processed.add(processing);
            alphabet += processing ;
          }
        }
        System.out.println(alphabet);
        }
      }
    }