Algorithms and puzzles ...

Algorithms are interesting !! They are well defined instructions for completing a sequential task ...A really complicated can be this



A simpler challenge is this :

A friend of mine asked me to design an algorithm to determine the length of an Island. The description of the problem is as follows:

An Island can be described by a set of points - Imagine discretization of a continuous boundary. The Island can contain lakes which are again discretized.

Thus Island can be given as a matrix I : [x1, y1 ; x2, y2 ; ..... xn, yn]. Similarly the lakes inside the island can be described with L1 :[ x1, y1 ; x2, y2 ; ..... xn, yn], L2 [x1, y1 ; x2, y2 ; ..... xn, yn] ... etc.

Here is the exact problem.
Starting from any point on the island, you can get to another point on the island with a shortest possible path. Consider lakes -- you can not cross a lake. For a particular point, a collection of such paths can be made by changing the other point recursively. Call it C1 for point P1. The length of the island is described as longest of (longest of C1, longest of C2, .... longest of Cm).

Design an algorithm to find the length of the island.
==================================================================

These days I am solving similar puzzles and interesting algorithmic problems. If you have any collection of difficult but interesting puzzles, please send that to me.

Who knows I might start a puzzle blog !

Much love.
Rohit

Solution of a simple case - An Island without the lakes.
Part 1 - Calculating the shortest path on an island without a lake.

My algorithm goes like this:

1. Select a rotation direction say-Anticlockwise. On any figure if you select one point, you know the next point for a clockwise direction. For now we will assume that with a code this can be found.

2. Select a point on the contour. Call it point 1. Find the shortest path from 1 to 2, 1 to 3 up to 1 to n. The max of (shortest paths) = length of island.

Definitions:
==============
** Convexity

Now let us define convexity of an angle. Considering an angle 1-2-3 of a
polygon. Consider these as vectors connecting 1-2 and connecting 2-3. By
starting at point 1 - measure the angle from the left side of the
segment 1-2 to left side of segment 2-3. If this angle is > 180 deg, then this point is called concave. Otherwise it will be called convex.

A convex angle is thus less than 180.

Shortest distance- uses the definition of convexity.
==============

Now lets define the minimum distance between two points on the contour.
The minimum distance between two points which are inside the island
is the straight line connecting the two points. If suppose a structure
similar to the following figure protrudes in the lake

island side
--0-1 4------
/ \
2---------------------3
lake side

The shortest path from 0 to 3 ofcourse goes around point 1- which is 0-1-3.
So how to avoid point 2 ?

Starting from point 0 and sequence 0-1-2, we will build up sequence
which will represent the shortest path.
Check if angle 0-1-2 is concave. If yes, the sequence will be built to
0-1-2-3. Check if the last abgle that is angle 1-2-3 is concave -- Its
not, so the sequence if modiified to 0-1-3. Now we will have to carry
out the same operation in reverse direction in order to see if the path
did not pass over the lake. Consider following figure

If I start with 3 and get the shortest path between 3 and 6, My
anticlockwise algorithm will give me the shortest path as 3-6, whereas
the clockwise algorithm will give me the shortest path as 3-2-6.
I will select the longer distance sequence as the shortest path between the two points.

6-------------------5
| -------------------|
| -------------------|
| -------------------|
| ------ island --- | lake
2 ------------------|
\ -------------------|
\ -------------------|
/ -------------------|
3--------------------4