{-
Copyright (C) 2017 Yuchen Pei.

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU Affero General Public
License along with this program.  If not, see
<https://www.gnu.org/licenses/>.
-}
-- Acknowledgements:
-- https://www.reddit.com/r/adventofcode/comments/7lte5z/2017_day_24_solutions/drs1eml/
-- https://stackoverflow.com/a/4708372/4063224
import Data.List (delete, concatMap)
import Data.List.Split (splitOn)

extBridge :: [Int] -> [[Int]] -> [[Int]]
extBridge xs ys
  | null zs = [xs]
  | otherwise = concatMap f zs
    where x = head xs
          zs = filter (elem x) ys
          f [y, z] = extBridge (if y == x then (z:y:xs) else (y:z:xs)) (delete [y, z] ys)

parseInput :: [Char] -> [[Int]]
parseInput xs = (fmap read . splitOn "/") <$> splitOn "\n" xs

solve1 :: [Char] -> Int
solve1 = maximum . fmap sum . (extBridge [0]) . parseInput

solve2 :: [Char] -> Int
solve2 = snd . maximum . fmap (\xs -> (length xs, sum xs)) . (extBridge [0]) . parseInput

input0 = "0/2\n2/2\n2/3\n3/4\n3/5\n0/1\n10/1\n9/10"

input = "50/41\n19/43\n17/50\n32/32\n22/44\n9/39\n49/49\n50/39\n49/10\n37/28\n33/44\n14/14\n14/40\n8/40\n10/25\n38/26\n23/6\n4/16\n49/25\n6/39\n0/50\n19/36\n37/37\n42/26\n17/0\n24/4\n0/36\n6/9\n41/3\n13/3\n49/21\n19/34\n16/46\n22/33\n11/6\n22/26\n16/40\n27/21\n31/46\n13/2\n24/7\n37/45\n49/2\n32/11\n3/10\n32/49\n36/21\n47/47\n43/43\n27/19\n14/22\n13/43\n29/0\n33/36\n2/6"