Data centers

DataCenters

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

// Oh no! Disaster has struck some of ACME's redundant data centers. The administrators have managed to restore backups, but some data sets are still missing from some data centers. Fortunately, every data set can be found at least once in one or more of the data centers. However, before ACME can resume normal operations, it needs to ensure that each data center has a copy of every data set.
// 
// Your goal is to help ACME resume normal operations by writing a program to synchronize data sets between data centers using as few copies as possible.
// 
//  
// 
// Input:
// 
// The first line of input will contain an integer between 0 and 999999 inclusive, representing the number of data centers.
// 
// Following that will be one line of input for each data center. Each line will contain an integer from 0 to 299 representing the number of data sets at that data center, followed by a space and space-separated list of data set ids currently present at that data center. Data set ids are each an integer between 1 and 999999, inclusive. Each line will be at most 999 characters long.
// 
// Data set ids are not necessarily consecutive. The list of data sets will not be in any particular order.
// 
// 
// Output:
// 
// The program must output an optimal data set copy strategy to ensure that every data center has a copy of every data set. Output one line for every copy instruction.
// 
// A copy instruction is of the form <data-set-id> <from> <to>, where <data-set-id> is the data set id, <from> is the index of the data center the data set will be copied from (1 = the first data center), and <to> is the index of the data center to copy the data set to.
// 
// When there are no more copy instructions, the program must output the word "done" on a line by itself.
// 
// There is often more than one correct output with minimal number of operations for a given input, and any output that satisfies the requirements is valid.
// 
// Constraints:
// 
// The code you submit must take input from stdin and produce output to stdout as specified above. No other output is permitted. You can assume the input will be valid.
// 
//  
// 
// Example 1:
// ----------
// Input:
// 
// 4
// 3 1 3 4
// 3 1 2 3
// 2 1 3
// 3 1 4 2

namespace DataCenters
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Enter input in specified format");
            
            string firstLine = Console.ReadLine();
            
            int numberOfDataCenters = Int32.Parse(firstLine);
            
            var dataSetIdsToDCMap = new Dictionary<int, HashSet<int>>();
            
            var dcToDataSetIdsMap = new Dictionary<int, List<int>>();
            
            for(int i = 0; i < numberOfDataCenters; i++) {
                string nextLine = Console.ReadLine();
                var inputs = nextLine.Split(' ');
                
                var dataCenterId = i + 1;
                
                var dataSetIds = new List<int>();
                
                for(int j = 1; j < inputs.Length; j++) {
                    var dataSetId = Int32.Parse(inputs[j]);
                                        
                    if (dataSetIdsToDCMap.ContainsKey(dataSetId)) {
                        dataSetIdsToDCMap[dataSetId].Add(dataCenterId);
                    } else {
                        var dataCenters = new HashSet<int>();
                        dataCenters.Add(dataCenterId);
                        
                        dataSetIdsToDCMap.Add(dataSetId, dataCenters);
                    } 
                    
                    dataSetIds.Add(dataSetId);   
                }
                
                dcToDataSetIdsMap.Add(dataCenterId, dataSetIds);
            }
            
            Console.WriteLine("Copy instructions are");
            generateInstructions(numberOfDataCenters, dcToDataSetIdsMap, dataSetIdsToDCMap);
            
            Console.WriteLine("Done");
        }
        
        static void generateInstructions(int numOfDataCenters,
            Dictionary<int, List<int>> dcToDataSetIdsMap,
            Dictionary<int, HashSet<int>> dataSetIdsToDCMap) {
        
            foreach(var dataSetId in dataSetIdsToDCMap.Keys) {
                var dataCentersForDataSet = dataSetIdsToDCMap[dataSetId];
                                
                if (dataCentersForDataSet.Count < numOfDataCenters) {
                    
                    int sourceDataCenter = dataCentersForDataSet.ToList().First();
                    
                    foreach(var dataCenter in dcToDataSetIdsMap.Keys) {
                        if (!dataCentersForDataSet.Contains(dataCenter)) {
                            var destinationDataCenter = dataCenter;
                            
                            dcToDataSetIdsMap[dataCenter].Add(dataSetId);
                            
                            dataSetIdsToDCMap[dataSetId].Add(dataCenter);
                            
                            Console.WriteLine("{0} {1} {2}", dataSetId, sourceDataCenter, destinationDataCenter);
                        }
                    }
                }
            }      
    	}
    }
}