coder . cl

As you know I am doing a series of exercises that were used in the ACM ICPC. This time I have solved the problem b of the 1991 contest. The problem consists on validating figure points in a trimatrix, where from a given set of points, you must determine if those points are vertex of triangles, parallelograms and hexagons, otherwise they are invalid points. Currently I am using Haskell to practice the Haskell programming language and acquire more ability using Haskell solving algorithmic problems.

Note that if we number the points from left to right and top to bottom, then groups of these points form the vertex of certain geometric shapes. For example, the sets of points {1,2,3} and {7,9,18} are the vertex of triangles, the sets {11,13,26,24} and {2,7,9,18} are the vertex of parallelograms, and the sets {4,5,9,13,12,7} and {8,10,17,21,32,34} are the vertex of hexagons.

Write a program which will repeatedly accept a set of points on this triangular grid, analyze it, and determine whether the points are the vertex of one of the following “acceptable” figures: triangle, parallelogram, or hexagon. In order for a figure to be acceptable, it must meet the following two conditions: 1. Each side of the figure must coincide with an edge in the grid; 2. All sides of the figure must be of the same length.

[ACM ICPC 1991-B]

Trimatrix, Figure Holder

So, I have prepared first the proper data types under Haskell, made the trimatrix, and placed the nodes inside the trimatrix using Haskell data types. But I have omitted the second rule, so all sizes are allowed, for example in parallelograms where they require that they must have the same size on opposed sides, so each vertex distance should be equal on all figures and opposed sides should have the same length, except for the triangle figure.

data TNode = TNode {
  x     :: Int
  , y   :: Int
  , n   :: Int
  } deriving (Eq, Show)

data TNodeType = Triangle
               | Parallel
               | Hexa
               | NotAcceptable
                 deriving (Eq, Show)

data TFigure = TFigure {
  ntype    :: TNodeType
  , nodes  :: [TNode]
  } deriving (Eq, Show)


mkLeft :: Int -> [Int]
mkLeft n = fmap ( x -> x * (x - 1) `div` 2 + 1 )
           [1 .. n]

mkRight :: Int -> [Int]
mkRight n = fmap ( x -> (x ^ 2 + x) `div` 2 )
            [1 .. n]

mkTriangle :: Int -> [[Int]]
mkTriangle n = zipWith (x y -> [x .. y])
               (mkLeft n) (mkRight n)

So, each side of the trimatrix is made from two series on the Haskell equations above. Then they just require to fill the points between each side of the trimatrix. Also, my algorithm supports inverted triangles. Once the data is retrieved from the list of points that represents each vertex, they are sorted so I can handle the position of each vertex and using Haskell data types to store the figure information, so I can calculate the distance between vertex.

findPos :: [[Int]] -> Int -> TNode
findPos n m = TNode { x = r, y = s, n = t }
              where r = findRow m 0 n
                    s = findCol m 0 n
                    t = n !! r !! s

buildPos :: [[Int]] -> [Int] -> [TNode]
buildPos t n = fmap (findPos t) $ sort n

buildFig :: [TNode] -> TFigure
buildFig tn = x
              where l = length tn
                    x = case l of
                      3 -> TFigure { ntype = Triangle, nodes = tn }
                      4 -> TFigure { ntype = Parallel, nodes = tn }
                      6 -> TFigure { ntype = Hexa, nodes = tn }
                      _ -> TFigure { ntype = NotAcceptable, nodes = tn }

And the main function with its Monadic IO() form. Here I am not using an input file, instead the point lists are placed as hard code inside the program, but if you want to modify the program to use an input file you should use the liftLine function which was defined as fmap ( read . strip ) $ split " " l with l as the input line.

isAcceptable :: TFigure -> Bool
isAcceptable t = ntype t /= NotAcceptable

figureDistance :: TFigure -> (TFigure, Bool)
figureDistance x = case ( ntype x ) of
                        Triangle -> (x, triangleDis x)
                        Parallel -> (x, parallelDis x)
                        Hexa     -> (x, hexagonDis x)
                        _        -> (x, False)


main :: IO()
main = do let rows = [[1, 2, 3],
                      [16, 19, 40],
                      [4, 5, 9, 13, 12, 7],
                      [41, 37, 37],
                      [24, 13, 11, 26],
                      [2, 3, 9, 10],
                      [11, 13, 29, 31],
                      [1, 2, 3, 4, 5],
                      [47],
                      [11, 13, 23, 25]]
              trg = mkTriangle 10
              figs = filter isAcceptable
                     $ fmap (buildFig . buildPos trg) rows
              vals = join "n" $ fmap (showFig . figureDistance) figs
              in putStrLn vals

Finally the output of my algorithm is as follows, which does not follows the exercise required output, and seems to be more informational than the required output. Probably in the future I will implement a visualization for this algorithm, because it looks interesting. I am thinking to use OpenGL or Gtk2Hs (with GDK) as drawing toolkit, I must see which one offers me the best option for this drawing.

Figure: Triangle
Nodes: 0, 0: 1; 1, 0: 2; 1, 1: 3
Valid: True

Figure: Triangle
Nodes: 5, 0: 16; 5, 3: 19; 8, 3: 40
Valid: True

Figure: Hexa
Nodes: 2, 0: 4; 2, 1: 5; 3, 0: 7; 3, 2: 9; 4, 1: 12; 4, 2: 13
Valid: True

Figure: Triangle
Nodes: 8, 0: 37; 8, 0: 37; 8, 4: 41
Valid: True

Figure: Parallel
Nodes: 4, 0: 11; 4, 2: 13; 6, 2: 24; 6, 4: 26
Valid: False

Figure: Parallel
Nodes: 1, 0: 2; 1, 1: 3; 3, 2: 9; 3, 3: 10
Valid: False

Figure: Parallel
Nodes: 4, 0: 11; 4, 2: 13; 7, 0: 29; 7, 2: 31
Valid: False

Figure: Parallel
Nodes: 4, 0: 11; 4, 2: 13; 6, 1: 23; 6, 3: 25
Valid: False