Anagramic squares

2016-12-11

Problem 098: Anagramic squares

Description:

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36^2. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96^2. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt, a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

Solution:

vXXX #   #################################################################################################### #   A
XXX #   #################################################################################################### #   ACCESS
XX  #   #################################################################################################### #   ACROSS
XX  #   #################################################################################################### #   ADDITIONAL
XXX #   #################################################################################################### #   ADVISE
X   #   #################################################################################################### #   AGAINST
     #   #################################################################################################### #   AIM
     #   #################################################################################################### #   ALRIGHT
     #   #################################################################################################### #   ANALYSIS
$   #   #################################################################################################### #   ANYBODY
         #################################################################################################### #   APPEARANCE
         #################################################################################################### #   ARGUE
         #################################################################################################### #   ART
         #################################################################################################### #   ASSET
         #################################################################################################### #   ATTEMPT
0        #################################################################################################### #   AVAILABLE
1        #################################################################################################### #   BACKGROUND
9        #################################################################################################### #   BASIC
p                           v             \<          v        !:\<                                           #   BED
>0>:: 0\ :9%82**"r"+\9/  10p>:1+\10gg:84*-#^_$$   0\:!vv-1\5< v*\<+                                           #   BELONG
                                                  v   <>:  >| >\:|$                                           #   BIG
  |                   -*"&/" :+1 p /"d"\+9%"d": \$_"A"-0\: ^$>|  >^                                           #   BLOODY
  $                                                      >:#<^>1\^                          v         \+1\<   #   BOTH
  >011p>11g1+21p             >11g:"d"%9+\"d"/g 21g:"d"%9+\"d"/g - #v_ 11g:9%82**"r"+\9/10p0\>:1+\10gg84*-#^_v #   BRIDGE
>"&/"*-|                     |!`*"&/"p12:+1g12    <                <   >\*v >55+\1-v    >\*v >55+\1-v       $ #   BURN
^ p11:+1p/"d"\+9%"d":\"#":g11<                                         |:\< |:<    <    |:\< |:<    <         #   CAMPAIGN
       9                                           v   p02:p010-1 \ -1$<  ^$< ^   \0 \ $<  ^$< ^   \0-1p13::<     ...
       g                                           vp01g03_v#-g01:_v#- <                                          ...
       .                                           >:30p:20 g\/+2/: 30g^              vp01g03_v#-g01:_v#- <       ...
       @                                                   >       >$30g1+12p 010p:20p>:30p:20 g\/+2/: 30g^
                                                  ^                              <            >       >$30gv
                                           vp\"n"\"|":<+*297<vp\5\"|":<9p32*:g31_^#!`g22 p31:<g21       p22<
                                           >:1-\      |      >:1-\    |   >        13g1+:13p ^
         v-"A"g/9\+g41+"r"**28%9:g11  <p41<-1g13     $<     ^        $<   ^                    < <
                        v-1\+55<  v*\<|p41    -1:g41                                            <
                        >:    >|  >\:|                              >v                   >v
         >24p 31g1-14g- 0\:   ^>$:|  >   $23g\/55+%34p  "n"24gg:"|"-|>34g-|>   534gg:"|"-|>24g-|
                                  >1\^                              >$    v              >$    v
        v                     p410p510<                        vpg42"n"g43<       vpg435+"A"g42<
                                                  >v           >           ^      >             ^
        >21g:9%82**"r"+14g+\9/g"A"-24p"n"24gg"|"-!|>           >>                                ^
                                                  >"n"24gg14g+!|
        |-g13p41:+1g41                       p51+gg42"n"*+55g51<
                              >                                 ^
        >15g23g`  15g19g` *  !|                                         > 15g19p v
                              1                         >       >$30gv> |        >               ^
                              5                 vp01g03_^#-g01:_^#- <:  >        ^
                              g                 >:30p:20 g\/+2/: 30g^*
                                  >           >#^ #p #0 2 #<$      v
                              >     :88*%"9"`#^_:88+%:9`#v_:2-#v_v   2
                                       >     >     >     > #     >$>$0^
                                  |!-8_^#-7:_^#-6:_^#-5:_^# -3:<     g
                                             >     ^<   0 <^:p010 <^<-!
                                  >:55+%:7-!#^_:3-!#^_2-!#^_:3%2-#^_^>^

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

With this problem I tried a little bit differen methology with designing the problem. Programs with massive (16k) input are always kind of ugly in befunge because all of the data must be in the program code, so I thought I can at least try a little bit around.

In this program I seperated the code, as much as I could, into independent subprograms. All subprograms can use the [1,0]-[9,0] fields as temporary values, get their input from the stack and write their output also to the stack. Then I combined them together to build the whole program.

All the subprograms are in my BefungePrograms git repo

This resulted in more readable code and (hopefully) snippets that I can reuse in other programs. But the code doesn't compress as good (which nobody cares about in this problem, cause of the giant input size) and I'm sure I could optimize it a lot by using more global state and shared variables etc.

I think for my next programs I will continue as I did before and sometimes use independent code snippets (for example for the integer-squareroot function) but for the big main program I will write it all together.

The program works like so:

First we calculate a "palindromic hash value" for each input word, this is a hash algorithm that has no collisions as long as there are max five repeated letters in a word and has the same value for palindroms. Practically it is a 26-digit number in base-5 where each digit denotes the amount a specific letter occurs in our word. We can not use a larger number than 5 for our base because then we would overflow our 64bit numbers.
Next we go through our palindromic list and search for palindroms (words with the same hash) With some clever sorting tricks we could do this in log2(n), but I will leave this as an exercise for ther reader and and implement in naively in n^2
For each word we iterate through all the squares with the correct digit count. This means we start with j, where j = 10^(len - 1) and wnd with k, where k = (10^len) - 1
Now (for each square) we can generate the numeric value for word B with word A + square as our map. When we generate our char->digit map (as an 26 element array) we also generate a digit->char map to test if any digit is mapped to multiple different characters (a failure criteria)
Now we have square A and (possible) square B, with our optimized is-integer-squareroot function from problem 086 we test if B is a square number. And if this is the case (and B is bigger than our current candidate) we set B as our current result candidate
After we have done this for all pairs we can return (= print out) our current best candidate.