import Control.Monad (replicateM)
import Data.Char (intToDigit)
import Data.List
  ( find,
    group,
    intercalate,
    nub,
    sort,
    sortBy,
  )
import Data.Monoid ((<>))
import Data.Ord (comparing)

data Sign
  = Unsigned
  | Plus
  | Minus
  deriving (Eq, Show)



universe :: [[(Int, Sign)]]
universe =
  zip [1 .. 9]
    <$> filter
      ((/= Plus) . head)
      (replicateM 9 [Unsigned, Plus, Minus])

allNonNegativeSums :: [Int]
allNonNegativeSums =
  sort $
    filter
      (>= 0)
      (asSum <$> universe)

uniqueNonNegativeSums :: [Int]
uniqueNonNegativeSums = nub allNonNegativeSums

asSum :: [(Int, Sign)] -> Int
asSum xs =
  n
    + ( case s of
          [] -> 0
          _ -> read s :: Int
      )
  where
    (n, s) = foldr readSign (0, []) xs
    readSign ::
      (Int, Sign) ->
      (Int, String) ->
      (Int, String)
    readSign (i, x) (n, s)
      | x == Unsigned = (n, intToDigit i: s)
      | otherwise =
        ( ( case x of
              Plus -> (+)
              _ -> (-)
          )
            n
            (read (show i <> s) :: Int),
          []
        )

asString :: [(Int, Sign)] -> String
asString = foldr signedDigit []
  where
    signedDigit (i, x) s
      | x == Unsigned = intToDigit i: s
      | otherwise =
        ( case x of
            Plus -> " +"
            _ -> " -"
        )
          <> [intToDigit i]
          <> s


main :: IO ()
main =
  putStrLn $
    unlines
      [ "Sums to 100:",
        unlines
          (asString <$> filter ((100 ==) . asSum) universe),
        "\n10 commonest sums (sum, number of routes to it):",
        show
          ( ((,) <$> head <*> length)
              <$> take
                10
                ( sortBy
                    (flip (comparing length))
                    (group allNonNegativeSums)
                )
          ),
        "\nFirst positive integer not expressible "
          <> "as a sum of this kind:",
        maybeReport
          ( find
              (uncurry (/=))
              (zip [0 ..] uniqueNonNegativeSums)
          ),
        "\n10 largest sums:",
        show
          ( take
              10
              ( sortBy
                  (flip compare)
                  uniqueNonNegativeSums
              )
          )
      ]
  where
    maybeReport ::
      Show a =>
      Maybe (a, b) ->
      String
    maybeReport (Just (x, _)) = show x
    maybeReport _ = "No gaps found"