| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next


Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

Kenzaburo Oe: The Changeling; Peach Jam; Taste Test; Strawberry and Raspberry Jam; flac to mp3 on OpenSuse 42.1; Also, Sebald; Kenzaburo Oe Interview; Otake (Kitani Minoru) move Black 121; Is free speech in British universities under threat?; I am actually good at computers; Was This Mansplaining?; WebFaction / LetsEncrypt / General Disappointment; Sensible Philosophy of Science; George Ellis; Misplaced Intuition and Online Communities; More Reading About Japan; Visibilty / Public Comments / Domestic Violence; Ferias de Santiago; More (Clearly Deliberate); Deleted Obit Post; And then a 50 yo male posts this...; We Have Both Kinds Of Contributors; Free Springer Books; Books on Religion; Books on Linguistics; Palestinan Electronica; Books In Anthropology; Taylor Expansions of Spacetime; Info on Juniper; Efficient Stream Processing; The Moral Character of Crypto; Hearing Aid Info; Small Success With Go!; Re: Quick message - This link is broken; Adding Reverb To The Echo Chamber; Sox Audio Tools; Would This Have Been OK?; Honesty only important economically before institutions develop; Stegangraphy via PS4; OpenCL Mess; More Book Recommendations; Good Explanation of Difference Between Majority + Minority; Musical Chairs - Who's The Privileged White Guy; I can see straight men watching this conversation and laffing; Meta Thread Defending POC Causes POC To Close Account; Indigenous People Of Chile; Curry Recipe; Interesting Link On Marginality; A Nuclear Launch Ordered, 1962; More Book Recs (Better Person); It's Nuanced, And I Tried, So Back Off; Marx; The Negative Of Positive; Jenny Holzer Rocks; Huge Article on Cultural Evolution and More; "Ignoring language theory"; Negative Finger Counting; Week 12; Communication Via Telecomm Bids; Finding Suspects Via Relatives' DNA From Non-Crime Databases; Statistics and Information Theory; Ice OK in USA; On The Other Hand; (Current Understanding Of) Chilean Taxes / Contributions; M John Harrison; Playing Games on a Cloud GPU; China Gamifies Real Life; Can't Help Thinking It's Thoughtcrime; Mefi Quotes; Spray Painting Bike Frame; Weeks 10 + 11; Change: No Longer Possible To Merge Metadata; Books on Old Age; Health Tree Maps; MRA - Men's Rights Activists; Writing Good C++14; Risk Assessment - Fukushima; The Future of Advertising and Surveillance; Travelling With Betaferon; I think I know what I dislike so much about Metafilter; Weeks 8 + 9; More; Pastamore - Bad Italian in Vitacura; History Books; Iraq + The (UK) Governing Elite; Answering Some Hard Questions; Pinochet: The Dictator's Shadow; An Outsider's Guide To Julia Packages; Nobody gives a shit; Lepton Decay Irregularity; An Easier Way; Julia's BinDeps (aka How To Install Cairo); Good Example Of Good Police Work (And Anonymity Being Hard); Best Santiago Burgers; Also; Michael Emmerich (Vibrator Translator) Interview (Japanese Books); Clarice Lispector (Brazillian Writer); Books On Evolution; Looks like Ara (Modular Phone) is dead; Index - Translations From Chile; More Emotion in Chilean Wines

© 2006-2015 Andrew Cooke (site) / post authors (content).


From: andrew cooke <andrew@...>

Date: Sun, 6 Feb 2011 07:01:49 -0300

A palindrome is a word that reads the same backwards as forwards.

Some letters look like letters when they are upside down, which suggests that
there should be something like a palindromes that work when a word is rotated
by 180 degress about its middle.  I will call these spindromes.

This seemed like an obvious use for Lepl, which will give multiple matches - 
all we need to do is
  1 - Identify which letters work
  2 - Write a parser that matches words consisting of such letters
  3 - Run that parser against a list of words


from lepl import *

# What letters can we match?  I don't know how to generate this except by
# checking each letter by eye, which gives the following (I'll use either case
# in the hope of getting more matches):
pairs = [('b', 'q'), ('d', 'p'), ('h', 'y'), ('i', 'i'), ('l', 'l'), ('m', 'w'), 
         ('n', 'u'), ('o', 'o'), ('s', 's'), ('x', 'x'), ('z', 'z'),
         ('H', 'H'), ('I', 'I'), ('M', 'W')]

# Some of those are self-images so can occur in the middle of words with an
# odd number of letters
def single(pair):
    return pair[0] == pair[1]
singles = [pair[0] for pair in pairs if single(pair)] 

# We want to do caseless matching but return the correct case (so we can
# see when capitals are used).  So we need a matcher that does that.  Lepl
# doesn't have anything built-in, but we can write our own (following Lepl's
# convention of using capitals to indicate matcher factories).
def Caseless(letter):
    Given a letter, this returns a matcher that will match the first character
    of a stream if the letter appears (ignoring case), returning the letter
    as the match.
    def matcher(support, stream):
        if stream and stream[0].lower() == letter.lower():
            return ([letter], stream[1:])
    return matcher

# And then we can use that to match and of the central letters:
central = Or(*map(Caseless, singles))

# The final matcher is going to be recursive (matching repeated pairs "inside"
# itself).  That's going to be recursive; we handle that by introducing 
# the name so that we can reference it later.
outer = Delayed()

# To define a matcher for any pair we'll first write a function that can
# generate one for a single pair (note how this calls the pre-defined outer)
def Bracket(pair, inner):
    a, b = [Caseless(letter) for letter in pair]
    if single(pair):
        return a + inner + b
        return a + inner + b | b + inner + a 
def Outer(pair):
    return Bracket(pair, outer | Empty())

# Finally, we can "tie the knot" (we put the central matcher here so that
# we can match single letters)
outer += Or(*[Outer(pair) for pair in pairs]) | central

# Some simple tests:
assert outer.parse('o') == ['o']
assert outer.parse('O') == ['o']
assert outer.parse('pod') == ['pod']
assert outer.parse('pboQd') == ['pboqd']

# But that takes WAY too long.  Instead, we need to restrict backtracking by
# adjusting the matcher to the word length.  We'll make a matcher for a given
# length then cache/build matchers as necessary.
def CountedOuter(n):
    if n == 0:
        return Empty()
    elif n == 1:
        return central
        inner = CountedOuter(n-2)
        return Or(*[Bracket(pair, inner) for pair in pairs])

# And cache by length
cache = {}
def parse(word):
    n = len(word)
    if n not in cache:
        cache[n] = CountedOuter(n)
        # I tried compiling to a regular expression here (re lib), but it
        # doesn't work too well (hangs dues to exponential complexity on 
        # longer words)
    return cache[len(word)].parse_string(word)

assert parse('o') == ['o']
assert parse('O') == ['o']
assert parse('pod') == ['pod']
assert parse('pboQd') == ['pboqd']

# Now let's run that against the contents of the dictionary:
with open('/usr/share/dict/words', encoding='latin_1') as words:
    for word in words:
        word = word.strip()
            print(parse(word)[0]) # will be a list containing a single word

The results are less exciting than I had hoped:


Final Code

From: andrew cooke <andrew@...>

Date: Thu, 10 Feb 2011 08:45:47 -0300



Comment on this post