## DEV Community is a community of 757,079 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #99 - Balance the Scales

Write a function that will read `scaleArr`. In this array, there will be two elements. The first will contain two positive integers that represent the left and right sides of a scale respectively. The second array represents the available weights that can be added to either side.

Balance the scale by using the least amount of weight from the list. You can only use an integer from available weights once.

For example: If `scaleArr` is ["[9,4]","[1,2,6,7]"], you must add 2 to the left side and 7 to the right side to balance the scale. Both sides will equal 11!

If it is not possible to balance the scale using the weight available, return `not possible`

Test cases:
["[1,2]","[10,3,6,6]"]
["[20,5]","[1,6,10,4]"]
["[0,13]","[4,6,3,7]"]

Good luck, happy coding!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (5) Note: I'm really unsure about what I have done since I'm pretty new to Haskell and that there are no expected result for the test cases (or I'm both blinded & tired).

Note 2: it seems like in the example given, 1 & 6 can be used to balance the result. Since 1 & 6 are lower than 2 & 7, it makes them the least amounts to use for balance. Or I didn't understand the problem well enough.

Note 3: this implementation assumes that there will always be an input of format which is described above. Of course this will fail if the strings are differents.

``````import Data.List (find)

combinationPairs :: [Int] -> [(Int, Int)]
combinationPairs integers =
(,) <\$> integers <*> integers

equalizer :: [Int] -> (Int, Int) -> Bool
equalizer balance (left, right) =
left + head balance == right + last balance

scale :: [String] -> Maybe (Int, Int)
scale strings =
find (equalizer balance) combinations
where
balance :: [Int]

weights :: [Int]
weights = readIntegersFrom \$ last strings

combinations :: [(Int, Int)]
combinations = combinationPairs weights

main :: IO ()
main = do
print \$ scale ["[9,4]", "[1,2,6,7]"]    -- Just (1, 6)
print \$ scale ["[1,2]","[10,3,6,6]"]    -- Nothing
print \$ scale ["[20,5]","[1,6,10,4]"]   -- Nothing
print \$ scale ["[0,13]","[4,6,3,7]"]    -- Nothing
``````

Playground

Try it online here. Just spent a few moments reading through your code. Here is some feedback I have, but I'm also kinda new so don't take it too seriously.

1. You should consider converting the first input array to a 2-tuple. You use it as a tuple in `equalizer` so having the type be a tuple will make the code clearer. It also forces you to do a little bit of input validation, which is always nice :D

2. Some functions don't have a great name. Specifically, `equalizer` and `combinationPairs`. Personally, they should probably be verbs. `combinations = combinePairs weights` sounds a bit nicer, in my opinion.

Also, I like the use of applicative functors for the `combinePairs` function :) C#!

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
List<int[][]> testCases = new List<int[][]>
{
new int[][]{new int[]{9, 4}, new int[]{1,2,6,7}},
new int[][]{new int[]{1, 2}, new int[]{10,3,6,6}},
new int[][]{new int[]{20, 5}, new int[]{1,6,10,4}},
new int[][]{new int[]{0, 13}, new int[]{4,6,3,7}},
new int[][]{new int[]{0, 53}, new int[]{4,6,3,7}},
new int[][]{new int[]{12, 12}, new int[]{4,6,3,7}},
};

foreach (var testCase in testCases)
{
var solution = Balance(testCase);
Console.Write("Input = [" + testCase + ", " + testCase + "], [" + string.Join(", ", testCase) + "]    Solution = ");
if (solution is string)
Console.WriteLine(solution);
else
{
var s = solution as (List<int> lWeights, List<int> rWeights)?;
Console.WriteLine("[" + string.Join(", ", s.Value.lWeights) + "], [" + string.Join(", ", s.Value.rWeights) + "]");
}
}
}

public static object Balance(int[][] scaleArr)
{
int left = scaleArr;
int right = scaleArr;
int[] weights = scaleArr;
var solution = BalanceRec(left, right, weights);
if (solution != null)
{
solution.Value.lWeights.Reverse();
solution.Value.rWeights.Reverse();
return solution;
}
else
{
return "not possible";
}
}

private static (List<int> lWeights, List<int> rWeights)? BalanceRec(int left, int right, int[] weights)
{
if (left == right)
return ( new List<int>(), new List<int>() );
if (weights.Length == 0)
return null;

var solutions = new (List<int> lWeights, List<int> rWeights)?[weights.Length];
for (int i = 0; i < weights.Length; i++)
{
if (left < right)
{
solutions[i] = BalanceRec(left + weights[i], right, weights.Where((source, index) => index != i).ToArray());
if (solutions[i] == null) continue;
}
else
{
solutions[i] = BalanceRec(left, right + weights[i], weights.Where((source, index) => index != i).ToArray());
if (solutions[i] == null) continue;
}
}
return solutions.Where(x => x != null).OrderBy(x => x.Value.lWeights.Count + x.Value.rWeights.Count).FirstOrDefault();
}
}
}
`````` Ed Reeseg

Naive solution here - basically construct a dictionary with the sum of all possible weight combinations for initial weight `a` and then add all possible combinations of weights to initial weight `b` to determine which is the smallest number of weights to achieve equilibrium.

I will be working on refactoring to make this more efficient, but I figured I'd code out a naive implementation as a baseline first before moving on and improving time complexity.

## Python

``````import itertools

def balance(scaleArr):
a, b = scaleArr
weights = scaleArr
lowest_quantity = None
a_weight = None
b_weight = None
sum_dict = { a: () }
combo_dict = {}
for i in range(len(weights)):
combos = list(itertools.combinations(weights, i))
combo_dict[i] = combos
for x in range(len(combos)):
sum = a
for n in combos[x]:
sum += n
if sum == b:
lowest_quantity = i
a_weight = combos[x]
b_weight = ()
if sum in sum_dict:
if x < len(sum_dict[sum]):
sum_dict[sum] = combos[x]
else:
sum_dict[sum] = combos[x]
for i in range(len(weights)):
combos = combo_dict[i]
for x in range(len(combos)):
sum = b
for n in combos[x]:
sum += n
if sum in sum_dict:
current_quantity = i + len(sum_dict[sum])
if lowest_quantity is None or current_quantity < lowest_quantity:
lowest_quantity = current_quantity
a_weight = sum_dict[sum]
b_weight = combos[x]
if lowest_quantity is None:
return 'not possible'
left = ', '.join(str(n) for n in a_weight) if len(a_weight) else 'nothing'
right = ', '.join(str(n) for n in b_weight) if len(b_weight) else 'nothing'
return ('The fewest number of weights needed for equality is '
f'{lowest_quantity}, putting {left} on the left and {right} on the right.')
``````