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

Add-A-Gram (ITA Archived Puzzle, Analyzed)

5/4/2011

0 Comments

 
Picture
Please refer to the add-a-gram problem on this page.

Analysis

Given a 3 letter word, let us assume, we can find out the 4 letter words that are its add-a-grams. We can then expand this to a n letter word pointing to its (n + 1)th add-a-gram. We can obviously model this as a directed graph where each word points to its add-a-grams.

Further since there is no possibility of an add-a-gram pointing to its possible source, this will be an acylic graph. Thus we have a directed acyclic graph representing the add-a-grams.

Algorithm

The problem then is of finding the ’longest path’ in the directed acyclic graph. In our case each edge will have a weight of 1.

First we build a hash table where key is the length of the word and values are the words of those length. Then we build the directed acylic graph such that each vertex is the word ’w’ and its neighbors are its add-a-grams obtained by searching through the hash table those words which are 1 more character in length than the given word ’w’.
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