DEEPAK.SURTI
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About

Palindromic Pangrams (ITA Archived Puzzle, Analyzed)

6/6/2011

0 Comments

 
Picture
Please refer to the palindromic pangram problem on this page.

Analysis

Let \(A_{p}\) represent a word and let \(A_{pr}\) represent its reverse. Let \(A_{1}\), \(A_{2}\), ..., \(A_{n-1}\), \(A_{n}\) be the subsequences of \(A_{pr}\) such that all of \(A_{1}\)  \(A_{2}\)  ..., \(A_{n-1}\) are valid words while \(A_{n}\) could be a valid word, but must be a palindrome. Then we can say that the following is a pangram for word \(A_{p}\):
$$Pangram_{A_{p}} \leftarrow \sum_{i = 1}^{i = n-1} A + A_{p}$$

Let us verify if this holds true with the following two examples cited in the problem statement:

$$Pangram_{daffodil} \leftarrow lid + off + a + daffodil$$
where $A_{n}$ = 'd' which is a palindrome, but not a valid word!

and,
$$Pangram_{ayatollahs} \leftarrow shallot + ayatollahs$$
where \(A_{n}\) = 'aya' which is a palindraome, but not a valid word!

It can be easily observed here that \(A_{1}\), \(A_{2}\), ...,\(A_{n}\) are all prefixes of \(A_{pr}\). Or we can think of them as substring q of string \(A_{pr}\). We also know then that a suffix tree is a good data structure to do string matching! 

Algorithm

  • Build a suffix tree of the words in the dictionary.
  • Now for each word in the dictionary, find it reverse. For the reverse word, find the prefixes that are actually words in the dictionary. If you can find matches for the entire reverse word, it implies it is a pangram. If it is a pangram, add the actual word and number of distinct characters in it to a list.
  • Sort the pangrams by the distinct number of letters it contains.
  • Now starting with the largest pangram, merge it with the next largest pangram that contains as many letters as possible that the largest pangram does not contain. Continue the merging process, till all letters of the alphabet are accounted for.
  • All the pangrams found in the previous step can then be merged as explained in the previous section to find the palindromic pangram that contains all letters of the alphabet.
0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Picture

    Me

    I am a 3D graphics software engineer.

    profile for dmsurti at Stack Overflow, Q&A for professional and enthusiast programmers

    Archives

    December 2011
    November 2011
    October 2011
    September 2011
    August 2011
    July 2011
    June 2011
    May 2011
    April 2011
    August 2010
    January 2010
    December 2009
    September 2009
    August 2009

    Categories

    All
    Automator
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Productivity
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
Powered by Create your own unique website with customizable templates.
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About