fairseq.sml

(* fairseq.sml *)

local
  (* function to read input *)
  fun parse file =
    let
      fun readInt input =
        Option.valOf (TextIO.scanStream (Int.scan StringCvt.DEC) input)
      val inStream = TextIO.openIn file
      val n = readInt inStream
      val _ = TextIO.inputLine inStream
      fun readInts 0 acc = acc 
        | readInts i acc = readInts (i-1) (readInt inStream::acc)
    in
      (readInts n [])
    end

  (* count the total sum of the sequence *)
  fun sum [] = 0  
    | sum (h::[]) = h
    | sum (h::t) = (h + sum t)
  
  (* solve function *)
  fun solve (nil,nil,_,total,_) = total
    | solve (l1,nil,curr,total,_) = abs(total-2*curr)  
    | solve (nil,l2,curr,total,mid) =
    let
      val (h2::t2) = l2
      in 
      if curr > mid then Int.min(abs(total-2*curr) ,
                       solve(nil,t2,(curr-h2),total,mid))
      else abs(total-2*curr) 
    end
    | solve (l1,l2,curr,total,mid) =
    let
      (* First list to add *)
      val (h1::t1) = l1
      (* Second list to sub *)
      val (h2::t2) = l2
    in 
      if (curr < mid) then Int.min( abs(total-2*curr) , (solve (t1,l2,(curr+h1),total,mid)))
      else if (curr > mid) then Int.min( abs(total-2*curr) , (solve (l1,t2,(curr-h2),total,mid))) 
      else abs(total-2*curr)
    end
in

(* Final function *)
fun fairseq input = 
  let 
    val seq = (parse input)
    val total = (sum seq)
    val mid = (total div 2)
  in
  print(Int.toString(solve(seq,seq,total,total,mid)))
  end
end