gistfile1.hs

{-
 - Author: Michael Kelly, mkelly01@my.fit.edu
 - Course: CSE 4510, Spring 2011
 - Project: game, The Triangle Game
 -}

module Main where
import List(delete)

-- Main function
main :: IO()
main = interact (unlines . splitTestCases . lines)

-- Splits out each test case from the input
splitTestCases :: [String] -> [String]
splitTestCases [] = []
splitTestCases xs = (parseTestCase (take 6 xs)) : (splitTestCases (drop 7 xs))

-- A Triangle is simply three sides. The first is the "left", second is the
-- "outside", and the third is the "right"
data Triangle = Tri Int Int Int deriving (Show, Eq)

-- A TestCase is a list of remaining triangles, the left side value for the
-- hexagon, the "outside" score, and the right side value
data TestCase = TC [Triangle] Int Int Int deriving (Show)


-- Parses a single test case
parseTestCase :: [String] -> String
parseTestCase xs
    | ans < 6   = "none"
    | otherwise = show ans
    where triangles = (map (parseTriangle . words) xs)
          ans = selectTriangle (TC triangles 0 0 0)


-- Parses a single string into a list representing the three sides of a triangle
parseTriangle :: [String] -> Triangle
parseTriangle [a,b,c] = (Tri (read a::Int) (read b::Int) (read c::Int) )
parseTriangle _ = error "Invalid triangle" 

-- Selects each triangle in the list and tries placing it into the current hexagon
selectTriangle :: TestCase -> Int
selectTriangle (TC triangles hLeft hScore hRight) = maximum [permuteAndSolve tri (TC (delete tri triangles) hLeft hScore hRight) | tri <- triangles]

-- Generates all 3 possible rotations of a triangle and solves for each one
permuteAndSolve :: Triangle -> TestCase -> Int
permuteAndSolve triangle testCase = maximum [placeTriangle tri testCase | tri <- (rotateTriangle triangle)]

-- Generates all valid rotations of a single triangle
rotateTriangle :: Triangle -> [Triangle]
rotateTriangle (Tri a b c) = [(Tri a b c), (Tri b c a), (Tri c a b)]

-- Places the given triangle on the left or right open sides of the hexagon,
-- and selects which choice returns the highest score
-- Also handles the base case of when there is only one slot left to fill
placeTriangle :: Triangle -> TestCase -> Int
placeTriangle (Tri tLeft tScore tRight) (TC [] hLeft hScore hRight)
    | hLeft == tRight && hRight == tLeft = (tScore + hScore)
    | otherwise = -1
placeTriangle (Tri tLeft tScore tRight) (TC triangles 0 0 0) = selectTriangle (TC triangles tLeft tScore tRight)
placeTriangle triangle testCase =
    let placeAtLeft = addTriangleToLeft triangle testCase
        placeAtRight = addTriangleToRight triangle testCase
    in maximum [placeAtLeft, placeAtRight]

-- Adds the given triangle to the "left" open side of the hexagon if possible,
-- and solves the resulting state
addTriangleToLeft :: Triangle -> TestCase -> Int
addTriangleToLeft (Tri tLeft tScore tRight) (TC triangles hLeft hScore hRight)
    | tRight == hLeft = selectTriangle (TC triangles tLeft (hScore + tScore) hRight)
    | otherwise = -1

-- Adds the given triangle to the "right" open side of the hexagon if possible,
-- and solves the resulting state
addTriangleToRight :: Triangle -> TestCase -> Int
addTriangleToRight (Tri tLeft tScore tRight) (TC triangles hLeft hScore hRight)
    | tLeft == hRight = selectTriangle (TC triangles hLeft (hScore + tScore) tRight)
    | otherwise = -1