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

Tour the T (ITA Archived Puzzle, Analyzed)

9/2/2011

0 Comments

 
Picture
Please refer to the Tour the T problem on this page.

Analysis

This is an instance of the Traveling Salesman Problem. We can model the entire subway as a weighted graph G=(V,E) where V is a station and E is an edge that connects two stations and w is the weight of the edge that represents the travel time between the two stations.

Algorithm

  • Build the weighted graph of the subway, while collecting those stations that are hubs connecting multiple lines. For example, Park St is a hub.
  • Now find the minimum spanning tree and do a depth first traversal of the tree.
  • Find the shortest path between the successive vertices sorted in depth first order. This will build a route that traverses all the stations at least once.
  • Now on the route, find out the hubs where line has been changed and add the waiting time for such line changes.
  • If your start station is not Kendall square, then find the shortest route between the penultimate station on the route and Kendall square, to build the final route.
0 Comments

Strawberry Fields (ITA Archived Puzzle, Analyzed)

8/19/2011

0 Comments

 
Picture
Please refer to the strawberry fields problem on this page

Analysis

Think of each strawberry as a point on an XY plane. Then we can find out the concave hull which is the smallest polygon that contains all the ponits or strawberries.


Picture
Assume for some given strawberry field, the concave hull is something like this

Picture
Now walk through the vertices of the concave hull in succsession. For each pair of successive vertexes, find the point of intersection that is outside the concave hull. This will now result in an updated polygon as shown.

Picture
Finally pick the largest edge and from the two edges, one of which succeeds the largest edge and the other which precedes it, pick the larger one. Form a rectangle between the largest edge and the selected succeessive or preceding edge. This is depicted here.

Picture
Now choose all points of the concave polygon that lie outside the rectangle that we just derived. Add to this set of points, a point that would have been derived as a result of deriving the rectangle. Repeat the process of forming the rectangle till all points of concave polygon are covered. For the sample, the final result is shown.

Algorithm

The steps of the algorithm are enumerated below.
  • Assuming the lowest row of the starwberry field as the X axis and the left most column as the Y axis, read the starwberries as points on XY plane.
  • Find out the concave hull of the strawberry points.
  • For the largest edge of the concave hull, pair it with the larger of the edge that succeeds or precedes it. Build a rectangle from this pair. Add a point that might have been generated as a part of building the rectangle to the set of points S of the concave hull that lie outside the built rectangle.
  • Repeate the process in the previous step for the set of points S of the concave hull that are yet to be covered till no more points remain.
0 Comments

Setless Set (ITA Archived Puzzle, Analyzed)

7/3/2011

0 Comments

 
Picture
Please refer to the setless set problem on this page.

Analysis

It can be easily deduced that the collection of 81 cards, contiains 27 SETs where each set contains the same cards.

Now in order to find the number of ways in which we can collect 20 cars such that it contains no set, we can use the following formula:
$$ N_{20\,cards\,without\,set} = N_{all\,possible\,collections\,of\,20\,cards} - N_{collection\,of\,20\,cards\,with\,atleast\,1\,set}$$


Find out set with different cards

Now if \(n_{same}\) is the number of sets with same cards, we already know that
$$n_{same} = 27$$

If we want to form a set that contains different cards, we can first pick an equal set and then pick a card from that set. Repeating this thrice will give us a set that contains different cards.

Thus total number of sets with different cards  \(n_{different}\) can be defined as 
$$n_{different} = (27 * 3) * (26 * 3) * (25 * 3) $$

Thus total number of possible sets \(n_{sets}\) can be defined as:
$$n_{sets} = n_{same} + n_{different}$$

Now we can easily find out the number of ways to pick k sets from \(n_{sets}\). A collection of 20 cards will contain a minimum of 1 set and a maximum of 6 sets. Thus number of ways to collect 'at the most' 6
sets can be defined as
$$n_{6\,sets} = \sum_{k = 1}^{k = 6} \binom {n_{sets}} {k}$$

Thus to find out N ways in which we can collect 20 cards that does not contain a set is
$$ N = \binom {81} {20} - n_{6\,sets}$$

Implementation

We can now write code that
  • Computes \(n_{6\,sets}\)
  • For a given j (j = 20 in the example), finds out the maximum number of ’k’ sets possible
  • Computes the number of ways in which you can pick k sets that is \(n_{k\,sets}\)
  • Computers the number of ways in which you can pick j cards from 81 cards
  • Finally computes the number of ways in which you can pick j cards such that it contains no set.
0 Comments

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

The Mystery M Function (ITA Puzzle Archive, Analyzed)

5/30/2011

0 Comments

 
Picture
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

 
Picture
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

 
Picture
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

 
Picture
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

This is the Breadth-First-Search algorithm to find shortest path between two vertexes.

The important piece here will be to transform the ascii maze into the graph and ignoring the cyclic vertexes while finding the shortest path.
0 Comments

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
<<Previous
Forward>>
    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