Solving the Mining algorithm from HackerRank

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 } :
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, // # of mines
K = line1; // # 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, Gold = line });
}

// 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[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);
}
}
• 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. – forsvarir Jul 31 '16 at 18:18