Deepak Surti
  • Blog
  • Mobile Apps
  • Projects
  • Graphics Demo
  • Me

The digital diary of a
​programmable programmer!!!

The Mystery M Function (ITA Puzzle Archive, Analyzed)

5/30/2011

0 Comments

 
Please refer to the mystery M function problem on this page.

Analysis

(defun m (i j k)
  (cond ((= i 0) (1+ k))
        ((and (= i 1) (= k 0)) j)
        ((and (= i 2) (= k 0)) 0)
        ((= k 0) 1)
        (t (m (1- i) j (m i j (1- k))))))

Let us look at the exit conditions for this recursive function ’m’. One of the exit conditions is when k equals zero. Now look at the recursive call. The recursive call fetches a value of k by replacing it with a call to ’m’ while decrementing k. As such k will reach 0, when it will return 1.

So it can be seen that the terminating condition of k equals zero returns 1 which is used as a value for k itself.

Evaluation

The evaluation will never terminate!
0 Comments

Landmarks Web App (ITA Archived Puzzle, Analyzed)

5/24/2011

0 Comments

 
Please refer to the landmarks web app problem on this page.

Analysis

The key part to solve here is to pick the nearby landmarks. As such we need to define what nearby means. Since each landmark’s latitutde and longitude are defined, we can define for a given landmark lm, whose latitude and longitude are \(lm_{lat}\)and \(lm_{long}\) respectively; a nearby landmark nlm with latitude and longitude \(nlm_{lat}\) and \(nlm_{long}\) such that:

The nearest \(nlm_{lat} < lm_{lat}\)OR

The nearest \(nlm_{lat} > lm_{lat}\) OR

The nearest \(nlm_{long} < lm_{long}\) OR

The nearest \(nlm_{long} > lm_{long}\)

In other words, the nearest landmark in any direction to the given landmark assuming the given landmark as a center. If we can now think of a landmkark as a vertex on a graph, then the neighboring vertexes of a given landmark will be those landmarks that satisfy the above definition.

Algorithm

Build a B-Tree where key is latitude and another where key is longitude. Now do a inorder traversal of this BTree while adding a landmark as a key to a hash table and its nearest landmarkes as values. Then given a landmark, we just look up in the hash table to find the nearest landmarks.

Implementation

In order to make the web application responsive, it would be nice to load the page with a javscript hashtable of landmarks and its nearby landmarks.
0 Comments

Decrypting the two-time pad (ITA Archived Puzzle, Analyzed)

5/17/2011

0 Comments

 
Please refer to the decrypting the two time pad problem on this page.

Analysis

The following are the problem characteristics. It is an instance of:
  • Caesar shifts. However it is not a case of monoalphabetic substitution. It is a case of polyalphabetic substitution.
  • It will be a good idea to simply add the two ciphers and consider it as a single cipher.
  • We can use a sufficiently large reference text (from Project Gutenberg) as a reference to identify the decoded symbols.
  • We have to decode upto a point where it is not hard for a human reader to detect the actual text. We can make use of Lisp restarts , to the user, to stop or continue the decoding process.

Algorithm

  1. Build a table of symbols for the chosen reference text which stores a symbol and its frequency within the reference text. The reference table can contain symbols consisting of 1 to 3 (or may be 4) characters. Next build a single cipher from the two ciphers. Build a table for the cipher again containing symbols and its frequency.
  2. Now match the symbol in the cipher with the maximum frequency with a corresponding symbol of maximum frequency in the reference table. The actual frequency count does not matter.
  3. Now susbsitute these reference symbols in the cipher and do pattern matching,which will be a case of approximate string matching, to identify possible matches in the cipher. Provide the possible matches to the user as a restart. With the chosen match, update the table with the symbol mapping and restart the same process of symbol matching till the user chooses to stop.

Implementation

I have not implemented this algorithm. But the analysis and the requirements of the problem do indicate that an approximate solution is requi Ared and the quality of it will hence depend upon (drawn from the algorithm) the chosen reference text. As such we may have to try out the implementation with mulitple chosen texts.

References

  • Cryptograph
  • Approximate String Matching
0 Comments

Ascii-A-Maze (ITA Archived Puzzle, Analyzed)

5/12/2011

0 Comments

 
Please refer to the ascii a-maze problem on this page.

Analysis

A maze is a grid of n * m cells. Given a maze, we can detect from a given cell k, which cell you can move to next. This is a defintion of a directed graph. Thus we can model a maze as a directed graph where each cell of the maze is a vertex and its neighbors are the cells you can navigate to from the given cell.

Now the start and end cells are defined as the bottom left and top right cells. Counting the lowest row as 1st row and left most column as 1st column while assuming m rows and n rows in the maze, the start cell is (1,1) while the end cell is (m, n). The problem then becomes of finding the shortest path between the start and end cells.

Algorithm

0 Comments

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

5/4/2011

0 Comments

 
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
    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
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
To see a miracle, be the miracle
  • Blog
  • Mobile Apps
  • Projects
  • Graphics Demo
  • Me
✕