DEV Community

dev.to staff
dev.to staff

Posted on

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!

Top comments (5)

Collapse
 
aminnairi profile image
Amin • Edited

Haskell

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)

readIntegersFrom :: String -> [Int]
readIntegersFrom string =
    read string :: [Int]

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.

Collapse
 
craigmc08 profile image
Craig McIlwrath

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

Collapse
 
aminnairi profile image
Amin

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

Collapse
 
erezwanderman profile image
erezwanderman

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[0][0] + ", " + testCase[0][1] + "], [" + string.Join(", ", testCase[1]) + "]    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[0][0];
            int right = scaleArr[0][1];
            int[] weights = scaleArr[1];
            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;
                    solutions[i].Value.lWeights.Add(weights[i]);
                }
                else
                {
                    solutions[i] = BalanceRec(left, right + weights[i], weights.Where((source, index) => index != i).ToArray());
                    if (solutions[i] == null) continue;
                    solutions[i].Value.rWeights.Add(weights[i]);
                }
            }
            return solutions.Where(x => x != null).OrderBy(x => x.Value.lWeights.Count + x.Value.rWeights.Count).FirstOrDefault();
        }
    }
}

Try it: [repl.it/repls/MajesticBadDifference]

Collapse
 
edreeseg profile image
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[0]
    weights = scaleArr[1]
    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.')