In today’s Programming Praxis exercise, our goal is to determine the smallest amount of sequential numbers (starting from 1) needed to sum up to a given value, using the fact that each term may be either positive or negative. Let’s get started, shall we?
import Data.List import Text.Printf
We use the same algorithm as the provided solution and the Stackoverflow topic where this exercise originated: find the smallest sum larger than our target number that has the same parity modulo 2 and flip the sign of terms totalling half the difference.
jack :: Int -> [Int] jack n = snd $ head [ mapAccumR (\r x -> if x <= r then (r-x,-x) else (r,x)) (div (t-n) 2) [1..i] | (i,t) <- scanl (\(_,s) x -> (x, s+x)) (0,0) [1..] , t >= abs n, mod (t+n) 2 == 0]
A test to see if everything is working properly:
main :: IO () main = mapM_ putStrLn [printf "%3d %2d %s" n (length j) (show j) | n <- [-24..24], let j = jack n]