Daily Challenge #99 - Balance the Scales

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

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

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