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

Word Rectangle (ITA Archived Puzzle, Archived)

9/28/2011

0 Comments

 
Picture

Read More
0 Comments

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