# Daily Challenge #99 - Balance the Scales

Daily Challenge (273 Part Series)

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!

Daily Challenge (273 Part Series)

### Discussion 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] balance = readIntegersFrom$ head strings

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 :)

Thanks for taking some time to help me on my journey.

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();
}
}
}


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.')  