twosum.hs

{-
Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple / list (depending on your language) like so: (index1, index2).

For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.

The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).

Based on: http://oj.leetcode.com/problems/two-sum/

twoSum [1, 2, 3] 4 === (0, 2)

-}
import Data.List ( elemIndices )
import Test.Hspec

twoSum' :: [Int] -> Int -> (Int,Int)
twoSum' arr target = head goodIndices where 
    goodIndices = filter notEqual solutionIndices
    solutionIndices = map getIndices solutions
    solutions =  [(a, b) | a <- arr, b <- arr, a + b == target]
    getIndices (a, b) = (head $ elemIndices a arr, last $ elemIndices b arr)
    notEqual = uncurry (/=)

twoSum :: [Int] -> Int -> (Int,Int)
twoSum xxs n = head [(fst x,fst y) | x <- xs, y <- xs, snd x + snd y == n, fst x < fst y]
  where xs = zip [0..] xxs


    

spec :: Spec
spec = do
  it "finds the matching pair" $ do
    let (i, j) = twoSum [1234, 5678, 9012] 14690
    (min i j, max i j) `shouldBe` (1, 2)
    let (i, j) = twoSum [1, 2, 3] 4
    (min i j, max i j) `shouldBe` (0, 2)
    let (i, j) = twoSum [2, 2, 3] 4
    (min i j, max i j) `shouldBe` (0, 1)
    let (i,j) = twoSum [4,-4,-2,2,3,-6,-3] (-8)
    (min i j, max i j) `shouldBe` (2, 5)

main = hspec spec