Unbalanced Balances...

Once again, I found a challenge in a very common webpage that said the following:

You have a room-full of balances and weights. Each balance weighs ten pounds and is considered perfectly balanced when the sum of weights on its left and right sides are exactly the same. You have placed some weights on some of the balances, and you have placed some of the balances on other balances. Given a description of how the balances are arranged and how much additional weight is on each balance, determine how to add weight to the balances so that they are all perfectly balanced.

There may be more than one way to balance everything, but always choose the way that places additional weight on the lowest balances.

The input file will begin with a single integer, N, specifying how many balances there are.
Balance 0 is specified by lines 1 and 2, balance 1 is specified by lines 3 and 4, etc...
Each pair of lines is formatted as follows:

WL < balances >
WR < balances >

WL and WR indicate the weight added to the left and right sides, respectively. < balances > is a space-delimited list of the other balance that are on that side of this balance. < balances > may contain zero or more elements.

Then, I took this example and developed an approach using Haskell, which of course, you can find the whole source code in Github. Now let explain what is happening starting in the main:

main = do
    zz <- readFile "input001.txt"
--    zz <- getLine
    print zz
    let z = map strToInt $ tail $ lines zz
    print z
--    let inc = increment z
--    print inc
--    let x = missing z
    let allBalances = clasifyBalance 0 z
    print $ map showBalance allBalances
    let x = orderBalance allBalances allBalances 
    print x 
--    writeFile "output.txt" $ show x

Using the same schematic procedure as before, we read from the file "input001.txt" and set parse it to the variable zz, then we split it in lines, cut the first element, then transform the remainder into an array with a list of integers. After that, we transform the raw data into a more structured form: (balance #, WL, WR, Index Left, Index Right) : ...

So, a balance is structured this way, the first value will represent its place in the whole list, then the weights in each side, and a list of indexes to which balances are being put on each side. This structure is not efficient at all, because it requires to provide the list every single time one balance is analyzed, but it worked for learning purposes.

And the following line does what the program is expected to do, call a function that orders all the balances from the input file. The function orderBalance takes two list of organized balances and provides back the list with all of them perfectly weighted, if a balance has this structure: (4, 3, 0, [], [1]):(1,0,0,[],[]), it means that it has assigned the number four, on its left side has weights for 3 pounds and the right side carries the balance number 1. A perfectly weighted object would be: (4, 7, 0, [], []), because we would want this balance to have the same proportion, then adding 7 to the left side would equilibrate the problem. Then we analyze orderBalance:

orderBalance :: [Balance] -> [Balance] -> [Balance]
orderBalance [] _ = []
orderBalance _ [] = []
orderBalance ordered balances = balanceTheBalance 
         (headZeroBal ordered) balances : 
           orderBalance (tailZero ordered) balances

Simple, if you have an ordered balance array, distribute the weight of the first element, and continue with the remaining in the list. If it is is empty in either side, just return that emptiness to the caller. Then we arrive to the interesting method to analyze, balanceTheBalance:

balanceTheBalance :: Balance -> [Balance] -> Balance
balanceTheBalance (num,x,y,xs,ys) bals =
    if (leftWeight == rightWeight)
    then (num,x,y,xs,ys) 
    else        
        if (leftWeight > rightWeight)
        then (num, 0, difference, xs, ys)
        else (num, difference, 0, xs, ys)   
    where
        leftWeight = (x + totalBalance xs bals)
        rightWeight = (y + totalBalance ys bals)
        difference = abs (leftWeight - rightWeight)

Here, if your sides have the same value, then return yourself, if not, verify which side is causing troubles ¿left?¿right? and from there calculate how much is missing and return that difference back to the caller, simple, isn't it?? Of course, at the time of this writing, I spotted a problem, if your balance is like (1,3,3,[2],[4,5]), this function would fail, because the balance is not necessarily balanced, even if 4 and 5 do not have anything on their own, we would still have 13 on one side and 23 on the other side, but this trouble could be fixed in a 1.1v of this program.