loading...

re: Daily Challenge #99 - Balance the Scales VIEW POST

FULL DISCUSSION
 

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]

code of conduct - report abuse