Challenge 15

19/01/26 08:13
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) {
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        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);
        }
    }
}