<commit_before>{-# LANGUAGE NoMonomorphismRestriction #-}
module ProjectEuler.Problem149
  ( problem
  ) where

import Control.Monad
import Control.Monad.ST
import Data.Int
import Petbox
import Data.List

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

import ProjectEuler.Types

problem :: Problem
problem = pureProblem 149 Unsolved result

{-
  Idea:

  I don't think this is a particularly large array to build,
  but it might improve performance if we just compute the value
  on the fly knowing the coordinate.
  Then rest of it is just generic algorithm for figuring out max adjacent sum
  (with negative elements taking into account)

  might be helpful: https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator
  perhaps, given that it is designed for generating random numbers,
  we aren't supposed to find any patterns that can help speeding up the process.
  but I'll need to take a closer look.

  Assuming that we can learn nothing of use from the way that these numbers are generated,
  we can still use Kadane's algorithm as describe from:
  https://en.wikipedia.org/wiki/Maximum_subarray_problem
 -}

result = genLineCoords (4 :: Int) -- (numTable VU.! 10, numTable VU.! 100)

genLineCoords l = rows <> cols <> diags0 <> diags1
  where
    rows = [ [(r,c) | c <- [1..l]] | r <- [1..l] ]
    cols = [ [(r,c) | r <- [1..l]] | c <- [1..l] ]
    -- let's say diags0 is of the direction that keeps r + c = k a constant.
    diags0 =
      [ [ (r,c) | r <- [1..k-1], let c = k - r ] | k <- [2 .. l+1] ]
      <> [ [ (r,c) | r <- [k-l..l], let c = k - r ] | k <- [l+2 .. l+l] ]
    -- diags1 keeps r - c = k a constant. (TODO)
    diags1 =
      [ [ (r,c) | r <- [1 .. l+k], let c = r - k ] | k <- [1-l .. 0]]
      <> [ [ (r,c) | r <- [k+1 .. l] , let c = r - k] | k <- [1 .. l-1] ]

{-
  Kadane's algorithm to compute sum of adjacent numbers.
  Note that if the array (or the sequence of things) are all negative,
  the algorithm will return 0, which is fine for our case, because
  there are definitely positive numbers in our array (for example, s_100 = 86613)
 -}
maxSubArray :: (Foldable t, Num a, Ord a) => t a -> a
maxSubArray = fst . foldl' kadaneAux (0, 0)
  where
    kadaneAux (bestSum, prevSum) curVal = (bestSum', curSum)
      where
        curSum = max 0 (prevSum + curVal)
        bestSum' = max bestSum curSum


numTableSmall :: VU.Vector Int32
numTableSmall =
  VU.fromList
    [ -1 -- reserved so that we can index starting from 1 for the purpose of being consistent with the problem.<commit_msg>p149: putting it together.<commit_after>{-# LANGUAGE NoMonomorphismRestriction #-}
module ProjectEuler.Problem149
  ( problem
  ) where

import Control.Monad
import Control.Monad.ST
import Data.Int
import Petbox
import Data.List

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

import ProjectEuler.Types

problem :: Problem
problem = pureProblem 149 Unsolved result

{-
  Idea:

  I don't think this is a particularly large array to build,
  but it might improve performance if we just compute the value
  on the fly knowing the coordinate.
  Then rest of it is just generic algorithm for figuring out max adjacent sum
  (with negative elements taking into account)

  might be helpful: https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator
  perhaps, given that it is designed for generating random numbers,
  we aren't supposed to find any patterns that can help speeding up the process.
  but I'll need to take a closer look.

  Assuming that we can learn nothing of use from the way that these numbers are generated,
  we can still use Kadane's algorithm as describe from:
  https://en.wikipedia.org/wiki/Maximum_subarray_problem
 -}

result = maximum (findMax numTable 2000 (genLineCoords 2000))

genLineCoords l = rows <> cols <> diags0 <> diags1
  where
    rows = [ [(r,c) | c <- [1..l]] | r <- [1..l] ]
    cols = [ [(r,c) | r <- [1..l]] | c <- [1..l] ]
    -- let's say diags0 is of the direction that keeps r + c = k a constant.
    diags0 =
      [ [ (r,c) | r <- [1..k-1], let c = k - r ] | k <- [2 .. l+1] ]
      <> [ [ (r,c) | r <- [k-l..l], let c = k - r ] | k <- [l+2 .. l+l] ]
    -- diags1 keeps r - c = k a constant. (TODO)
    diags1 =
      [ [ (r,c) | r <- [1 .. l+k], let c = r - k ] | k <- [1-l .. 0]]
      <> [ [ (r,c) | r <- [k+1 .. l] , let c = r - k] | k <- [1 .. l-1] ]

getVal :: VUM.Unbox a => VU.Vector a -> Int -> (Int, Int) -> a
getVal vec l (r,c) = vec VU.! ((r-1)*l + c)

findMax :: VU.Vector Int32 -> Int -> [[(Int, Int)]] -> [Int32]
findMax vec l = fmap (maxSubArray . getVecLine)
  where
    getVecLine :: [(Int,Int)] -> [Int32]
    getVecLine = fmap (getVal vec l)

{-
  Kadane's algorithm to compute sum of adjacent numbers.
  Note that if the array (or the sequence of things) are all negative,
  the algorithm will return 0, which is fine for our case, because
  there are definitely positive numbers in our array (for example, s_100 = 86613)
 -}
maxSubArray :: (Foldable t, Num a, Ord a) => t a -> a
maxSubArray = fst . foldl' kadaneAux (0, 0)
  where
    kadaneAux (bestSum, prevSum) curVal = (bestSum', curSum)
      where
        curSum = max 0 (prevSum + curVal)
        bestSum' = max bestSum curSum


numTableSmall :: VU.Vector Int32
numTableSmall =
  VU.fromList
    [ -1 -- reserved so that we can index starting from 1 for the purpose of being consistent with the problem.
{'fraction_non_alphanumeric': 0.12197358767424799, 'fraction_numerical': 0.020176082171680116, 'mean_word_length': 2.8186274509803924, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 25, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2951187', 'n_tokens_mistral': 1961, 'n_tokens_neox': 1817, 'n_words': 726}