Problems I’m currently thinking about

2012-06-10

I’ve been in a bit of a problem-posing mood recently. Hopefully I’ll do some problem-solving soon. Here are a few questions I’ve thought of but haven’t got solutions for. I haven’t done any literature searching, so these might have been done before.

All the problems are quite computery. Maybe I’m a computer scientist, really.

Problem 1: Reordering the alphabet

What reordering of the letters of the alphabet contains the most (contiguous) English words? This is a big search space problem. I did a little bit of tinkering in python, trying first of all to find the single word which contains the most smaller words.

import sys import pickle import operator import itertools alphabet = 'abcdefghijklmnopqrstuvwxyz' #test if a word uses letters at most once def monoglyphic(word): word = sorted(word) for i in range(1,len(word)): if word[i]==word[i-1]: return False return True #make forwards and backwards trees of words #forwards has all substrings (x1,..,xn),(x2,..,xn),... (xn) for words (x1,...,xn) #backwards has all substrings (xn),(xn,xn-1),...,(xn,...,x1) #use to calculate word overlaps def make_prefs(): forwards = {} backwards = {} for word in words: fbase = forwards bbase = backwards l = len(word) for i in range(0,l): fbase,fbucket = fbase.setdefault(word[i],({},[])) bbase,bbucket = bbase.setdefault(word[l-i-1],({},[])) fbucket.append(word) bbucket.append(word) return (forwards,backwards) def gather(base): l = [] for b2,bucket in base.values(): l += bucket l += gather(b2) return l #return all words which overlap with the left of word #eg 'dog' overlaps with 'ogle' def left_overlaps(word,backwards): overlaps = [] l = len(word) base = backwards for i in range(l,0,-1): base,bucket = base[word[i-1]] w2 = bucket[0][:l-i]+word if monoglyphic(w2): overlaps += bucket overlaps += gather(base) return overlaps # def calc_subs(): subs = {} for word in words: d = subs[word] = [] l=len(word) for i in range(0,l-1): j=i base=forwards while j<l and word[j] in base: base,bucket=base[word[j]] d+=bucket j+=1 d.sort() return subs #load words with no repeated letters words = [word.strip() for word in open('monoglyphs.txt').readlines()] #compute spelling trees forwards and backwards (for prefix/suffix overlaps) forwards,backwards = make_prefs() #for each word, calculate a list of all the subwords it contains subs = calc_subs() if __name__=='__main__': #sort words by the number of words they contain ranking = sorted([(word,len(subs[word])) for word in words],key=operator.itemgetter(1)) #operator.itemgetter(1) means sort by the second part of the tuple print('Top words') for word,score in ranking[-10:]: print('%s %i' %(word,score)) word,score=ranking[-1] print(word+' contains '+', '.join(subs[word]))

The output: (I can only apologise for the rather rude result!)

Top words blameworthy 16 cabinetwork 16 clothespin 16 discourage 16 housewarming 16 malnourished 16 metalworking 16 unprofitable 16 filamentous 17 motherfucking 17 motherfucking contains fuck, fucking, he, her, i, in, kin, king, mot, moth, mother, motherfucking, o, other, r, the, u

My current line of thinking is that if you draw out the complete graph on 26 vertices (one for each letter), words are paths on that, and the question is to find the Hamiltonian cycle which traces over the most complete paths. Not sure if that helps matters or not.

Problem 2: graph symmetries

Suppose you have a graph $G$ and its automorphism group $A u t (G)$ . In particular, suppose you know all the “lines of symmetry” of the graph – pairs of edges around a vertex which can be swapped, or pairs of vertices at the ends of an edge which can be reflected.

If you add an edge (or a vertex) to the graph, can you work out how the automorphism group changes?

This is probably a problem for a) 5 minutes on google scholar, b) 5 minutes on mathoverflow, or c) 5 minutes’ thinking.

Problem 3: A princess kidnapped by a robot on a graph

This is a further generalisation of the princess in a castle puzzle. The princess still inhabits a graph, but the way she moves is changed. In the classic puzzle she could move to any adjacent room. What if her movements are determined by a nondeterministic finite state automaton? If you know how the automaton works but not its input, for which graphs can you catch the princess?

FSAs, if you don’t care about what the input is, are equivalent to directed graphs, and extending the princess on a graph puzzle to directed graphs is already hard enough. But that’s a bit of a red herring, because if you draw out the transition diagram of the FSA, where “room the princess is in” is an extra bit of state, you have multiple vertices for each room. That might make things easier or just more complicated.