Advertisement
alefhidalgo

TaskDuration

Jun 20th, 2011
1,582
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.87 KB | None | 0 0
  1. import java.io.FileInputStream;
  2. import java.io.IOException;
  3. import java.nio.CharBuffer;
  4. import java.nio.MappedByteBuffer;
  5. import java.nio.channels.FileChannel;
  6. import java.nio.charset.Charset;
  7. import java.nio.charset.CharsetDecoder;
  8. import java.util.Scanner;
  9. import java.util.Set;
  10. import java.util.Stack;
  11. import java.util.TreeSet;
  12.  
  13. /**
  14.  * Tuenti Programming Contest
  15.  * Challenge 4: Task Duration
  16.  * @author alefhidalgo [at] gmail [dot] com
  17.  */
  18. public class TaskDuration {
  19.  
  20.   private int nTasks = 0;
  21.   private Node[] tasks;
  22.   private long totalCost = 0;
  23.  
  24.   /**
  25.    * Inner Class Node
  26.    *
  27.    * @author alefhidalgo@gmail.com
  28.    *
  29.    */
  30.   private class Node implements Comparable<Node> {
  31.     private int duration;
  32.     private Set<Node> dependencies;
  33.  
  34.     public Node(int duration) {
  35.       this.duration = duration;
  36.       dependencies = new TreeSet<Node>();
  37.     }
  38.  
  39.     public void addDependency(Node n) {
  40.       dependencies.add(n);
  41.     }
  42.  
  43.     public Set<Node> getDependencies() {
  44.       return dependencies;
  45.     }
  46.  
  47.     public int getDuration() {
  48.       return duration;
  49.     }
  50.  
  51.     @Override
  52.     public int compareTo(Node o) {
  53.       return -1;
  54.     }
  55.  
  56.   }
  57.  
  58.   /**
  59.    * Load file 'in' into a data structure
  60.    *
  61.    * @throws IOException
  62.    */
  63.   public void load() throws IOException {
  64.     FileChannel fc = new FileInputStream("in").getChannel();
  65.     MappedByteBuffer byteBuffer = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
  66.     Charset charset = Charset.forName("US-ASCII");
  67.     CharsetDecoder decoder = charset.newDecoder();
  68.     CharBuffer charBuffer = decoder.decode(byteBuffer);
  69.     Scanner sc = new Scanner(charBuffer);
  70.     String aux = null;
  71.     String spl[] = null;
  72.     Node n = null;
  73.     Node nDep = null;
  74.  
  75.     while (sc.hasNextLine()) {
  76.       String next = sc.nextLine();
  77.       if (next.startsWith("#Number of tasks")) {
  78.         nTasks = sc.nextInt();
  79.         tasks = new Node[nTasks];
  80.       }
  81.       if (next.startsWith("#Task duration")) {
  82.         for (int i = 0; i < nTasks; i++) {
  83.           aux = sc.nextLine();
  84.           spl = aux.split(",");
  85.           tasks[Integer.parseInt(spl[0])] = new Node(Integer.parseInt(spl[1]));
  86.         }
  87.       }
  88.       if (next.startsWith("#Task dependencies")) {
  89.         while (sc.hasNext()) {
  90.           aux = sc.next();
  91.           spl = aux.split(",");
  92.           n = tasks[Integer.parseInt(spl[0])];
  93.           for (int i = 1; i < spl.length; i++) {
  94.             nDep = tasks[Integer.parseInt(spl[i])];
  95.             n.addDependency(nDep);
  96.           }
  97.         }
  98.       }
  99.     }
  100.     fc.close();
  101.   }
  102.  
  103.   /**
  104.    * newTimeCost
  105.    *
  106.    * @param cost
  107.    */
  108.   public void newTimeCost(long cost) {
  109.     if (cost > totalCost) {
  110.       totalCost = cost;
  111.     }
  112.   }
  113.  
  114.   /**
  115.    * iterativeCalculation
  116.    *
  117.    * @param root
  118.    */
  119.   private void iterativeCalculation(Node root) {
  120.     Stack<Node> nodes = new Stack<Node>();
  121.     nodes.push(root);
  122.     Node currentNode;
  123.     long timeAcum = 0;
  124.     while (!nodes.isEmpty()) {
  125.       currentNode = nodes.pop();
  126.       timeAcum += currentNode.getDuration();
  127.       if (currentNode.getDependencies().size() == 0) {
  128.         newTimeCost(timeAcum);
  129.         timeAcum -= currentNode.getDuration();
  130.       }
  131.       for (Node n1 : currentNode.getDependencies()) {
  132.         nodes.push(n1);
  133.       }
  134.  
  135.     }
  136.   }
  137.  
  138.   /**
  139.    * calculateDuration
  140.    *
  141.    * @param taskId
  142.    */
  143.   public void calculateDuration(String taskId) {
  144.     Node n = tasks[Integer.parseInt(taskId)];
  145.     iterativeCalculation(n);
  146.     System.out.println(taskId + " " + totalCost);
  147.     totalCost = 0;
  148.   }
  149.  
  150.   public static void main(String[] s) throws IOException {
  151.     TaskDuration taskDuration = new TaskDuration();
  152.     taskDuration.load();
  153.     Scanner in = new Scanner(System.in);
  154.     in.useDelimiter(",");
  155.     while (in.hasNext()) {
  156.       taskDuration.calculateDuration(in.next());
  157.     }
  158.   }
  159. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement