Created
June 8, 2023 15:21
-
-
Save karagog/616428628cd60d9db66f65f230637597 to your computer and use it in GitHub Desktop.
This is a small program I wrote to search a dictionary for palindromic word squares of any size. See code for documentation comments.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// This program searches a dictionary for palindromic word squares, such as | |
// the famous SATOR square: | |
// | |
// SATOR | |
// AREPO | |
// TENET | |
// OPERA | |
// ROTAS | |
// | |
// Palindromic word squares read the same forwards, backwards and up and down. | |
// | |
// The order (or size) of the square is cutomizable via the --word_size flag, and you | |
// can optionally customize the dictionary file with the --dict flag. | |
// | |
// The algorithm supports unicode characters, and so should work with any language dictionary. | |
package main | |
import ( | |
"bufio" | |
"flag" | |
"fmt" | |
"io" | |
"os" | |
"strings" | |
) | |
var ( | |
wordSize = flag.Int("word_size", 5, "The word size determines the size of the SATOR square") | |
dictFile = flag.String("dict", "dict/scrabble.txt", "The dictionary file contains all the possible words on separate lines") | |
) | |
// LoadDict loads the given dictionary file with only words of the given size. | |
func loadDict(filePath string) map[string]bool { | |
f, err := os.Open(filePath) | |
if err != nil { | |
panic(err) | |
} | |
ret := make(map[string]bool) | |
addWord := func(w string) { | |
w = strings.TrimSpace(w) | |
if len(w) == *wordSize { | |
// Avoid possible casing errors by making everything upper case. | |
ret[strings.ToUpper(w)] = true | |
} | |
} | |
// Read the file line by line. | |
r := bufio.NewReader(f) | |
for { | |
l, err := r.ReadString('\n') | |
if err == io.EOF { | |
break | |
} | |
if err != nil { | |
panic(err) | |
} | |
addWord(l) | |
} | |
if len(ret) == 0 { | |
panic("The dictionary is empty") | |
} | |
return ret | |
} | |
// Reversed returns the reversed string. E.g. "DOG" becomes "GOD". | |
func reversed(w string) string { | |
var rev []rune | |
runes := []rune(w) | |
for i := range w { | |
rev = append(rev, runes[len(runes)-i-1]) | |
} | |
return string(rev) | |
} | |
// TrieNode indexes the words by first and last characters. | |
// | |
// It makes it quick and easy to find words that begin with X and end in Y | |
// without having to search through all the words. Every node represents a single | |
// prefix and suffix character. | |
// | |
// Create with NewNode(). | |
type TrieNode struct { | |
// The child nodes are indexed by a single prefix and suffix character. The key of this | |
// map is a concatenation of those characters. | |
// | |
// For example if the prefix is "P" and suffix is "S" then the key of that child would be "PS". | |
// Then if that child had a child node with key "AT", then it represents the word "PATS". | |
// | |
// There is a special case where the key may be a single character, which only happens when | |
// --word_size is odd. Then the odd-numbered character in the middle of the string acts as | |
// both the prefix and suffix for the leaf node. | |
children map[string]*TrieNode | |
} | |
// NewNode creates a valid new TrieNode. | |
func NewNode() *TrieNode { | |
return &TrieNode{children: make(map[string]*TrieNode)} | |
} | |
// Inserts the word into the trie so it is indexed. | |
func (root *TrieNode) Insert(word string) { | |
dec := []rune(word) // decode the word into unicode runes | |
if len(dec) < 2 { | |
panic("word is too small") | |
} | |
cur := root | |
for { | |
var key string | |
if len(dec) >= 2 { | |
// Use the prefix and suffix characters from the word as the key for this node. | |
key = string([]rune{dec[0], dec[len(dec)-1]}) | |
// Shrink the word by trimming the prefix and suffix, so we don't reevaluate them. | |
dec = dec[1 : len(dec)-1] | |
} else if len(dec) == 1 { | |
// An odd-numbered character in the middle of the string will have a single char key. | |
key = string(dec[0]) | |
dec = nil | |
} | |
// Grab the child node at the key, creating a new node if this prefix/suffix combo has not been seen. | |
child, ok := cur.children[key] | |
if !ok { | |
child = NewNode() | |
cur.children[key] = child | |
} | |
if len(dec) == 0 { | |
return // the full word has successfully been inserted into the trie | |
} | |
cur = child | |
} | |
} | |
// Search returns a list of strings that have the given prefix and suffix. | |
// If the prefix and suffix are both empty strings, then all strings will be returned. | |
func (root *TrieNode) Search(prefix, suffix string) []string { | |
pre := []rune(prefix) | |
suf := []rune(suffix) | |
if len(pre) != len(suf) { | |
panic("prefix and suffix must be the same size") | |
} | |
// Iterate through each prefix/suffix character, finding TrieNodes if the word exists. | |
cur := root | |
for i := 0; ; i++ { | |
if i < len(pre) { | |
key := string([]rune{pre[i], suf[len(pre)-1-i]}) | |
child, ok := cur.children[key] | |
if !ok { | |
break // no match | |
} | |
cur = child | |
} | |
if i < len(pre)-1 { | |
continue // to search for the next prefix/suffix character in the child node | |
} | |
// Found a match for the full prefix/suffix. Report all words under this node. | |
// Create a buffer and build up the words from their prefixes/suffixes. | |
wordBuffer := make([]rune, *wordSize) | |
for j := range pre { | |
wordBuffer[j] = pre[j] | |
wordBuffer[*wordSize-1-j] = suf[len(pre)-1-j] | |
} | |
return cur.assembleStrings(wordBuffer, len(pre)) | |
} | |
return nil | |
} | |
// Iterates recursively through the node and its children, assembling the prefixes and suffixes | |
// into the original strings and returns the list of strings. | |
// `buf` is a buffer that holds the temporary string as its being built. | |
// `index` indicates the location in the string that is being mutated at the current | |
// level of recursion. Each TrieNode holds a single pre | |
func (n *TrieNode) assembleStrings(buf []rune, index int) []string { | |
firstIndex := index | |
lastIndex := len(buf) - 1 - index | |
if lastIndex < firstIndex { | |
// We reached the leaf node, report the current buffer. | |
// This condition terminates recursion. | |
return []string{string(buf)} | |
} | |
var ret []string | |
for key, child := range n.children { | |
keyDec := []rune(key) | |
buf[firstIndex] = keyDec[0] | |
buf[lastIndex] = keyDec[len(keyDec)-1] // don't assume there is an index 1, as the size is not always 2 | |
ret = append(ret, child.assembleStrings(buf, index+1)...) | |
} | |
return ret | |
} | |
// FindPalindromicSquares recursively searches for palindromic squares and prints them to the console. | |
// | |
// At the first level of recursion, all strings in the trie are checked if they work as the | |
// first word in the square (the last word is also known because it is simply the reverse of | |
// the first word). At the second level, only the words that begin with the second letter | |
// of the first word, and end with the second letter of the last word are checked if they work | |
// as the second word in the square, and so on. Thereby the word square is assembled from | |
// the outside in, aborting only when no word is found that fits. This effectively searches all | |
// combinations of words in the dictionary to see if they work. | |
func (root *TrieNode) FindPalindromicSquares() { | |
// Instantiate a buffer for bufferSquare space. | |
var bufferSquare [][]rune | |
for i := 0; i < *wordSize; i++ { | |
bufferSquare = append(bufferSquare, make([]rune, *wordSize)) | |
} | |
root.findPalindromicSquares(bufferSquare, "", "") | |
} | |
// This is an internal recursion helper function that searches for palindromic squares. | |
// | |
// `buf` is the word square buffer that is used to build temporary squares for checking. | |
// `prefix` and `suffix` are the prefix and suffix that need to be satisfied at the current | |
// level of recursion. | |
func (root *TrieNode) findPalindromicSquares(buf [][]rune, prefix, suffix string) { | |
matches := root.Search(prefix, suffix) | |
if len(matches) == 0 { | |
return | |
} | |
index := len([]rune(prefix)) | |
finalIndex := (*wordSize / 2) + (*wordSize % 2) | |
for _, word := range matches { | |
// Update the square buffer with the candidate word at the index that corresponds to the prefix/suffix. | |
for i, c := range word { | |
buf[index][i] = c | |
buf[i][index] = c | |
buf[*wordSize-1-index][*wordSize-1-i] = c | |
buf[*wordSize-1-i][*wordSize-1-index] = c | |
} | |
nextIndex := index + 1 | |
if nextIndex == finalIndex { | |
// We have successfully found a palindromic square! Show it and keep searching for more squares. | |
fmt.Println("") // separate each square by an empty line | |
for _, l := range buf { | |
fmt.Println(string(l)) | |
} | |
continue | |
} | |
// The square works so far, but is incomplete. Descend to the next recursion level. | |
var nextPrefix, nextSuffix []rune | |
for i := 0; i < nextIndex; i++ { | |
nextPrefix = append(nextPrefix, buf[nextIndex][i]) | |
nextSuffix = append(nextSuffix, buf[nextIndex][*wordSize-nextIndex+i]) | |
} | |
root.findPalindromicSquares(buf, string(nextPrefix), string(nextSuffix)) | |
} | |
} | |
// The main application workflow. | |
func main() { | |
flag.Parse() | |
// Load the dictionary file into an in-memory index for fast word lookups. | |
allWords := loadDict(*dictFile) | |
// Find all the words in the dictionary that form words when read backwards, | |
// and insert them into the trie. | |
trie := NewNode() | |
for w := range allWords { | |
if allWords[reversed(w)] { | |
trie.Insert(w) | |
} | |
} | |
// Use the trie to search for squares. | |
trie.FindPalindromicSquares() | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment