{"id":39794,"date":"2018-07-23T09:26:53","date_gmt":"2018-07-23T09:26:53","guid":{"rendered":"https:\/\/www.flubu.com\/blog\/?p=39794"},"modified":"2018-07-23T09:53:58","modified_gmt":"2018-07-23T09:53:58","slug":"optimized-solution-for-periodic-words","status":"publish","type":"post","link":"https:\/\/www.flubu.com\/blog\/2018\/07\/23\/optimized-solution-for-periodic-words\/","title":{"rendered":"Optimized solution for periodic words"},"content":{"rendered":"

The previous solution I coded<\/a> for the problem of finding words written in periodic element symbols didn’t sit well with me. It worked, but it was sub-optimal and was too rigid in how it tried to find matches. A more complete and elegant solution is below and will discover *all* possible variants of elements for a given word. At each position in the word, it uses both 1- and 2-letter elements and branches out. The initial recursion will generate many more incomplete\/partial matches, but then the finalizing pass will recompose and flatten all paths through the graph and then cleanup after itself. This makes me happy.<\/p>\n

When running this code, the results are:<\/p>\n

Number of words found: 9092 \/\/ a 22% increase<\/b><\/p>\n

Longest word: Internationalisation
\nI, N, Te, Rn, At, I, O, N, Al, I, S, At, I, O, N
\nIn, Te, Rn, At, I, O, N, Al, I, S, At, I, O, N
\nI, N, Te, Rn, At, I, O, Na, Li, S, At, I, O, N<\/p>\n

Longest word with unique variants: Bureaucratisation
\nB, U, Re, Au, Cr, At, I, S, At, I, O, N
\nB, U, Re, Au, C, Ra, Ti, S, At, I, O, N<\/p>\n

Longest word with most variants: Consciousnesses
\nC, O, N, S, C, I, O, U, S, Ne, S, Se, S
\nC, O, N, S, C, I, O, U, S, Ne, S, S, Es
\nC, O, N, S, C, I, O, U, S, N, Es, Se, S
\nC, O, N, S, C, I, O, U, S, N, Es, S, Es
\nC, O, N, Sc, I, O, U, S, Ne, S, Se, S
\nC, O, N, Sc, I, O, U, S, Ne, S, S, Es
\nC, O, N, Sc, I, O, U, S, N, Es, Se, S
\nC, O, N, Sc, I, O, U, S, N, Es, S, Es
\nC, O, N, S, C, I, O, U, SN, Es, Se, S
\nC, O, N, S, C, I, O, U, SN, Es, S, Es
\nCo, N, S, C, I, O, U, S, Ne, S, Se, S
\nCo, N, S, C, I, O, U, S, Ne, S, S, Es
\nCo, N, S, C, I, O, U, S, N, Es, Se, S
\nCo, N, S, C, I, O, U, S, N, Es, S, Es<\/p>\n

Longest word with most unique variants: Carbines
\nC, Ar, B, I, Ne, S
\nC, Ar, B, I, N, Es
\nCa, Rb, I, Ne, S
\nCa, Rb, I, N, Es
\nC, Ar, Bi, Ne, S
\nC, Ar, Bi, N, Es
\nC, Ar, B, In, Es<\/p>\n

Elements that were never used in any word:
\nBk, Cd, Cf, Cm, Fm, Gd, Hg, Md, Mg, Sg, Sr, Zn, Zr<\/p>\n

\r\nimport java.io.*;\r\nimport java.util.*;\r\n\r\npublic class PeriodicWordFinder {\r\n\r\n    private TreeSet<String> words;\r\n    private TreeSet<String> elements;\r\n    private ArrayList<PeriodicWord> periodicWords;\r\n\r\n    public PeriodicWordFinder() {\r\n        \r\n        try {\r\n            words = read("wordlist.txt");\r\n            elements = new TreeSet<>((s1, s2) -> {\r\n                int lenthComparison = Integer.compare(s1.length(), s2.length());\r\n                if (lenthComparison == 0)\r\n                    return s1.compareTo(s2);\r\n                else\r\n                    return lenthComparison;\r\n            });\r\n            elements.addAll(read("elements.txt"));\r\n            periodicWords = new ArrayList<>();\r\n            System.out.println("words.size() = " + words.size());\r\n            System.out.println("elements.size() = " + elements.size());\r\n        } catch (Exception e) {\r\n            e.printStackTrace();\r\n        }\r\n    }\r\n\r\n    private TreeSet<String> read(String fileName) throws Exception {\r\n\r\n        TreeSet<String> retval = new TreeSet<>();\r\n        InputStream stream = getClass().getClassLoader().getResourceAsStream(fileName);\r\n        BufferedReader in = new BufferedReader(new InputStreamReader(stream));\r\n        String line;\r\n        while ((line = in.readLine()) != null) {\r\n            line = line.toUpperCase().trim();\r\n            \/\/no elements contain Q or J\r\n            if (line.contains("Q") || line.contains("J")) {\r\n                continue;\r\n            }\r\n            retval.add(line);\r\n        }\r\n        in.close();\r\n        return retval;\r\n\r\n    }\r\n\r\n    private void findWords() {\r\n\r\n        for (String word : words) {\r\n            PeriodicWord pWord = new PeriodicWord(word);\r\n            if (periodicWord(1, pWord)) {\r\n                periodicWords.add(pWord);\r\n            }\r\n        }\r\n\r\n        \/\/the new variant searcher algo will find partial\/incomplete matches\r\n        \/\/this needs to be filtered out by the finalizeVariants method\r\n        finalizeVariants();\r\n        for (PeriodicWord pWord : periodicWords) {\r\n            System.out.println("found: " + pWord.getInitialWord());\r\n        }\r\n    }\r\n\r\n    private boolean periodicWord(long variantId, PeriodicWord word) {\r\n\r\n        if (word.getWord(variantId).length() == 0)\r\n            return true;\r\n\r\n        \/*COSEU\r\n        -- 11 C  -- 111  O  -- 1111 S  -- 11111 Eu\r\n                 -- 111  O  -- 1112 Se -- 11121 U\r\n                 -- 112  Os -- 1121 Eu\r\n        -- 12 Co -- 121  S  -- 1211 Eu\r\n                 -- 122  Se -- 1221 U\r\n         *\/\r\n\r\n        long ndx = 1;\r\n        boolean matchFound = false;\r\n        for (String element : elements) {\r\n            if (word.getWord(variantId).startsWith(element)) {\r\n                matchFound = true;\r\n                long newVariantId = variantId * 10 + ndx++;\r\n                String alreadyPresent = word.setElement(newVariantId, element);\r\n                \/\/if (alreadyPresent != null) {\r\n                \/\/    System.err.println("Should not already be element " + alreadyPresent + \r\n                \/\/    " at newVariantId " + variantId + " for word" + word.getInitialWord());\r\n                \/\/}\r\n                word.setWord(newVariantId, word.getWord(variantId).substring(element.length()));\r\n                if (!periodicWord(newVariantId, word)) {\r\n                    \/\/we found a partial match\r\n                    \/\/it will be dealt with in finalize\r\n                }\r\n            }\r\n        }\r\n        return matchFound;\r\n\r\n    }\r\n\r\n    private void finalizeVariants() {\r\n\r\n        for (Iterator<PeriodicWord> it = periodicWords.iterator(); it.hasNext(); ) {\r\n\r\n            PeriodicWord pWord = it.next();\r\n\r\n            TreeMap<Long, String> elementVariants = pWord.getElementVariants();\r\n            boolean allFound = false;\r\n            while (!allFound && !elementVariants.isEmpty()) {\r\n\r\n                \/\/start from the end of the collection and work your way backwards,\r\n                \/\/collapsing the paths in the graph\r\n                String lastElement = elementVariants.lastEntry().getValue().toUpperCase();\r\n                if (pWord.getInitialWord().toUpperCase().endsWith(lastElement)) {\r\n                    \/\/build a word\r\n                    List<String> elementVariant = buildVariant(elementVariants);\r\n                    \/\/add last sanity check, check that you don't return a partial word\r\n                    String elVarStr = String.join("", elementVariant).toUpperCase();\r\n                    if (pWord.getInitialWord().equals(elVarStr)) {\r\n                        pWord.addElementWordVariant(elementVariant);\r\n                    }\r\n                    \/\/remove tail of collection and continue\r\n                    elementVariants.remove(elementVariants.lastKey());\r\n\r\n                } else {\r\n                    \/\/all words found, stop loop\r\n                    allFound = true;\r\n                }\r\n            }\r\n\r\n            \/\/if only partial words were mapped - no full words - remove as invalid\r\n            if (pWord.elementWordVariants.isEmpty()) {\r\n                it.remove();\r\n            }\r\n        }\r\n\r\n    }\r\n\r\n    private List<String> buildVariant(TreeMap<Long, String> elementVariants) {\r\n\r\n        \/*COSEU\r\n                -- 11 C  -- 111  O  -- 1111 S  -- 11111 Eu\r\n                         -- 111  O  -- 1112 Se -- 11121 U\r\n                         -- 112  Os -- 1121 Eu\r\n                -- 12 Co -- 121  S  -- 1211 Eu\r\n                         -- 122  Se -- 1221 U\r\n         *\/\r\n        List<String> retval = new ArrayList<>();\r\n        boolean done = false;\r\n        long key = elementVariants.lastKey();\r\n        while (!done) {\r\n            String val = elementVariants.get(key);\r\n            if (val != null) {\r\n                retval.add(0, val);\r\n            } else {\r\n                done = true;\r\n            }\r\n            key = key \/ 10;\r\n        }\r\n        return retval;\r\n    }\r\n\r\n    public List<PeriodicWord> getPeriodicWords() {\r\n        return periodicWords;\r\n    }\r\n\r\n    public Set<String> getElements() {\r\n        return elements;\r\n    }\r\n\r\n    public static void main(String[] args) {\r\n\r\n        PeriodicWordFinder ew = new PeriodicWordFinder();\r\n        ew.findWords();\r\n\r\n        \/\/now we have fun\r\n        List<PeriodicWord> pWords = ew.getPeriodicWords();\r\n        System.out.println("Number of words found: " + pWords.size());\r\n\r\n        \/\/longest word\r\n        pWords.sort((o1, o2) -> Integer.compare(o1.getInitialWord().length(), o2.getInitialWord().length()));\r\n        System.out.println("Longest word: " + pWords.get(pWords.size() - 1));\r\n\r\n        \/\/longest word with only unique elements\r\n        pWords.sort((o1, o2) -> {\r\n            String s1 = String.join("", o1.getVariantWithMostElements(true));\r\n            String s2 = String.join("", o2.getVariantWithMostElements(true));\r\n            int lenthComparison = Integer.compare(s1.length(), s2.length());\r\n            if (lenthComparison == 0)\r\n                return s1.compareTo(s2);\r\n            else\r\n                return lenthComparison;\r\n        });\r\n        System.out.println("Longest word with unique variants: " + pWords.get(pWords.size() - 1));\r\n\r\n        \/\/longest word with with most variants\r\n        pWords.sort((o1, o2) -> {\r\n            int numberComparison = Integer.compare(o1.getNumberOfVariants(false), o2.getNumberOfVariants(false));\r\n            if (numberComparison == 0) {\r\n                int lenthComparison = Integer.compare(o1.getInitialWord().length(), o2.getInitialWord().length());\r\n                if (lenthComparison == 0)\r\n                    return o1.getInitialWord().compareTo(o2.getInitialWord());\r\n                else\r\n                    return lenthComparison;\r\n            } else {\r\n                return numberComparison;\r\n            }\r\n        });\r\n        System.out.println("Longest word with most variants: " + pWords.get(pWords.size() - 1));\r\n\r\n        \/\/longest word with most unique variants\r\n        pWords.sort((o1, o2) -> {\r\n            int numberComparison = Integer.compare(o1.getNumberOfVariants(true), o2.getNumberOfVariants(true));\r\n            if (numberComparison == 0) {\r\n                int lenthComparison = Integer.compare(o1.getInitialWord().length(), o2.getInitialWord().length());\r\n                if (lenthComparison == 0)\r\n                    return o1.getInitialWord().compareTo(o2.getInitialWord());\r\n                else\r\n                    return lenthComparison;\r\n            } else {\r\n                return numberComparison;\r\n            }\r\n        });\r\n        System.out.println("Longest word with most unique variants: " + pWords.get(pWords.size() - 1));\r\n\r\n        \/\/is there any element that was not used?\r\n        TreeSet<String> elements = new TreeSet<>(ew.getElements());\r\n        for(PeriodicWord pWord : pWords){\r\n            for (List<String> variantElements : pWord.elementWordVariants ){\r\n                elements.removeAll(variantElements);\r\n                if (elements.isEmpty()){\r\n                    break;\r\n                }\r\n            }\r\n        }\r\n        System.out.println("Elements not used: " + elements);\r\n    }\r\n\r\n    private class PeriodicWord {\r\n\r\n        private TreeMap<Long, String> wordVariants; \/\/will get mangled during recursion\r\n        private String initialWord; \/\/keep track of initial word\r\n        private TreeMap<Long, String> elementVariants;  \/\/will get updated during recursion\r\n        private List<List<String>> elementWordVariants;\r\n\r\n        public int getNumberOfVariants(boolean onlyUnique) {\r\n            List<List<String>> sorted = new ArrayList<>();\r\n            sorted.addAll(elementWordVariants);\r\n            if (onlyUnique) {\r\n                sorted.removeIf(this::containsDuplicateElements);\r\n            }\r\n            return sorted.size();\r\n        }\r\n\r\n        public List<String> getVariantWithMostElements(boolean onlyUnique) {\r\n            if (elementWordVariants.size() == 1) {\r\n                return elementWordVariants.get(0);\r\n            } else {\r\n                List<List<String>> sorted = new ArrayList<>();\r\n                sorted.addAll(elementWordVariants);\r\n                if (onlyUnique) {\r\n                    sorted.removeIf(this::containsDuplicateElements);\r\n                }\r\n                sorted.sort((o1, o2) -> Integer.compare(o1.size(), o2.size()));\r\n                if (sorted.size() > 0) {\r\n                    return sorted.get(sorted.size() - 1);\r\n                } else {\r\n                    return new ArrayList<>();\r\n                }\r\n            }\r\n        }\r\n\r\n        private boolean containsDuplicateElements(List<String> elementVariant) {\r\n            return new HashSet<>(elementVariant).size() != elementVariant.size();\r\n        }\r\n\r\n        public PeriodicWord(String word) {\r\n            initialWord = word;\r\n            elementVariants = new TreeMap<>();\r\n            wordVariants = new TreeMap<>();\r\n            wordVariants.put(1l, word);\r\n            elementWordVariants = new ArrayList<>();\r\n        }\r\n\r\n        public void setWord(long variantId, String word) {\r\n            wordVariants.put(variantId, word);\r\n        }\r\n\r\n        public TreeMap<Long, String> getElementVariants() {\r\n            return elementVariants;\r\n        }\r\n\r\n        public String getWord(long variantId) {\r\n            return wordVariants.get(variantId);\r\n        }\r\n\r\n        public String setElement(long variantId, String element) {\r\n            return elementVariants.put(variantId, element);\r\n        }\r\n\r\n        public String getInitialWord() {\r\n            return initialWord;\r\n        }\r\n\r\n        public void addElementWordVariant(List<String> elementWordVariant) {\r\n            elementWordVariants.add(elementWordVariant);\r\n        }\r\n\r\n        @Override\r\n        public String toString() {\r\n            return "PeriodicWord{" +\r\n                    "initialWord='" + initialWord + '\\'' +\r\n                    ", elementWordVariants=" + elementWordVariants +\r\n                    '}';\r\n        }\r\n\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
The previous solution I coded for the problem of finding words written in periodic element symbols didn’t sit well with me. It worked, but it was sub-optimal and was too rigid in how it tried to find matches. A more complete and elegant solution is below and will discover *all* possible variants of elements for…<\/p>\n
Read More “Optimized solution for periodic words”<\/span> »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[17],"class_list":["post-39794","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-geek"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3u9vK-alQ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/posts\/39794","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/comments?post=39794"}],"version-history":[{"count":5,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/posts\/39794\/revisions"}],"predecessor-version":[{"id":39799,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/posts\/39794\/revisions\/39799"}],"wp:attachment":[{"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/media?parent=39794"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/categories?post=39794"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.flubu.com\/blog\/wp-json\/wp\/v2\/tags?post=39794"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}