3
\$\begingroup\$

I was working on this problem for a few hours last night and finally came up with a brute-force solution. The task is to report the minimum work necessary (sum of weight × distance) to relocate gold produced at n mines to k of those mines. The first line of input contains n and k; subsequent lines give the location and amount of gold of each mine.

My solution is passing all the unit tests that don't time out, so I'm fairly confident that is correct except that it needs to use fewer operations in order to be a successful submission.

Any ideas on how I can make this not timeout?

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

static class Extensions 
{
     // ripped from http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n   
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
      return k == 0 ? new[] { new T[0] } :
        elements.SelectMany((e, i) =>
          elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
    }
}

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

class Solution 
{
    static void Main(String[] args) 
    {
        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(Console.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for(int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(Console.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for checking whether a move combination ends up 
        // forming K groups
        Func<IEnumerable<Tuple<Mine,Mine>>, bool> FormsKGroups = combo =>  {
            var groups = mines.Select(mine => new List<Mine>() { mine })
                              .ToList();
            foreach(var move in combo)
            {
                int start = mines.IndexOf(move.Item1), 
                      end = mines.IndexOf(move.Item2);
                groups[end].Add(mines[start]);
                groups[start].Remove(mines[start]);
            }
            return groups.Count(g => g.Count > 0) == K;            
        };

        // Get all move combinations that form K groups
        var moveCombos = mines.SelectMany(m => mines, (m1, m2) => Tuple.Create(m1, m2))
                              .Where(tuple => !tuple.Item1.Equals(tuple.Item2)) // we have all 2^N ordered pairs of mines
                              .Combinations(N - K) // all combinations of length (N - K) of those pairs
                              .Where(x => true); // that form K groups

        // helper function for calculating the cost of a sequence of moves
        Func<IEnumerable<Tuple<Mine,Mine>>, int> MovesCost = (moves) => 
            moves.Aggregate(0, (sum, move) => 
                sum + Math.Abs(move.Item1.Distance - move.Item2.Distance) * move.Item1.Gold);

        // calculate min cost and print result
        int mincost = moveCombos.Min(MovesCost);
        Console.WriteLine(mincost);
    }
}
\$\endgroup\$
  • 7
    \$\begingroup\$ To get the most from your question, try to include the problem specification/requirements in the question itself. Not all reviewers have the desire/access to visit off sure resources. \$\endgroup\$ – forsvarir Jul 31 '16 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.