Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

For practice, I am working through some google code jam problems. The code below is for the Milkshakes problem located here:

http://code.google.com/codejam/contest/dashboard?c=32016#s=p1

This solution solves for both the small and large data set. Please let me know how I can improve this code. Thank you.

import java.util.*;
import java.io.*;

public class MilkShake {

  private final int UNMALTED = 0;
  private final int NOCHOICE = 2;
  private boolean isPossible;
  private ArrayList<ArrayList<Integer>> customerPreferenceList = new ArrayList<ArrayList<Integer>>();
  private int[] finalBatchAr;
  private StringBuilder result = new StringBuilder();

  public static void main(String[] args) {
    new MilkShake().go();
  }

  public void go() {

  File inputFile = new File("/* File name */");
  BufferedReader br = null;

    try {

      br = new BufferedReader(new FileReader(inputFile));    
      int numTests = Integer.parseInt(br.readLine());

      //Loop through each test
      for(int testCounter = 0; testCounter < numTests; ++testCounter) {
        customerPreferenceList.clear();
        int numFlavors = Integer.parseInt(br.readLine());
        initializeFlavorAr(numFlavors);

        int numCustomers = Integer.parseInt(br.readLine());
        isPossible = true;

        //For each test, loop through each customer
        for(int customerCounter = 0; customerCounter < numCustomers; ++customerCounter) {
          String[] customerPrefs = br.readLine().split(" ");
          ArrayList<Integer> custRow = new ArrayList<Integer>();

          for(int j = 0; j < customerPrefs.length; ++j) {
            custRow.add(Integer.parseInt(customerPrefs[j]));
          }
          customerPreferenceList.add(custRow);
        }

        //Eliminate first element of each row. Number of elements each customer likes is not used.
        if(!customerPreferenceList.isEmpty()) {
          for(ArrayList<Integer> a : customerPreferenceList) {
            if(!a.isEmpty()) { a.remove(0); }
          }
        }

        boolean customerPreferenceListChanged = true;

        while(customerPreferenceList.size() > 0 && isPossible && customerPreferenceListChanged == true) {
          customerPreferenceListChanged = false;
          ArrayList<Integer> removeList = new ArrayList<Integer>();

          //Deal with rows with only one choice
          for(int oneChoiceCounter = 0; oneChoiceCounter < customerPreferenceList.size(); ++oneChoiceCounter) {
            if(customerPreferenceList.get(oneChoiceCounter).size() == 2) {
              int indexOfFlavorInQuestion = customerPreferenceList.get(oneChoiceCounter).get(0);
              if(finalBatchAr[indexOfFlavorInQuestion - 1] == NOCHOICE) {
                finalBatchAr[indexOfFlavorInQuestion - 1] = customerPreferenceList.get(oneChoiceCounter).get(1);
                removeList.add(oneChoiceCounter);
                customerPreferenceListChanged = true;
              }
              else if(finalBatchAr[indexOfFlavorInQuestion - 1] != customerPreferenceList.get(oneChoiceCounter).get(1)) {               
                isPossible = false;
                break;
              }
              else {
                //flavor already in map - remove from customerPreferenceList
                removeList.add(oneChoiceCounter);
                customerPreferenceListChanged = true;
              }
            }
          }

          if(!removeList.isEmpty()) {
            cleanUpCustomerPreferenceList(removeList);
            removeList.clear();
          }

          //Loop through all other cases, if any element already in finalBatchAr remove the row from customerPreferenceList
          for(int elementExistsCounter = 0; elementExistsCounter < customerPreferenceList.size(); ++elementExistsCounter) {
            for(int j = 0; j < customerPreferenceList.get(elementExistsCounter).size(); j += 2) {
              if(finalBatchAr[customerPreferenceList.get(elementExistsCounter).get(j) - 1] == customerPreferenceList.get(elementExistsCounter).get(j + 1)) {
                removeList.add(elementExistsCounter);
                customerPreferenceListChanged = true;
                break;
              }
            }
          }

          if(!removeList.isEmpty()) {
            cleanUpCustomerPreferenceList(removeList);
            removeList.clear();
          }

          //Loop through customerPreferenceList again, get rid of all elements that conflicts with finalBatchAr
          //If currentRow empty afterwards, set isPossible to false
          for(int conflictCounter = 0; conflictCounter < customerPreferenceList.size(); ++conflictCounter) {
            int currentRowSize = customerPreferenceList.get(conflictCounter).size();

            for(int j = 0; j < currentRowSize; j += 2) {
              if((finalBatchAr[customerPreferenceList.get(conflictCounter).get(j) - 1] != NOCHOICE) && (finalBatchAr[customerPreferenceList.get(conflictCounter).get(j) - 1] != customerPreferenceList.get(conflictCounter).get(j + 1))) {                
                customerPreferenceList.get(conflictCounter).remove(j);
                customerPreferenceList.get(conflictCounter).remove(j);
                j -= 2;
                currentRowSize -= 2;
                customerPreferenceListChanged = true;
              }
            }

            if(customerPreferenceList.get(conflictCounter).size() == 0) {
              isPossible = false;
              break;
            }

          }
        }

        finalizeFlavorAr(numFlavors);
        appendResult(testCounter + 1, numFlavors);
      }
    } catch(FileNotFoundException fe) {
        fe.printStackTrace();
    } catch(IOException ie) {
        ie.printStackTrace();
    } finally {
        try {
          if(br != null) {
             br.close();
          }
        } catch (IOException ex) {
            ex.printStackTrace();
        }  
    }
    writeResultToFile();
  }

  private void initializeFlavorAr(int numFlavors) {
    finalBatchAr = null;
    finalBatchAr = new int[numFlavors];

    for(int i = 0; i < numFlavors; ++i) {
      finalBatchAr[i] = NOCHOICE;
    }

  }

  private void finalizeFlavorAr(int numFlavors) {
    for(int i = 0; i < numFlavors; ++i) {
      if(finalBatchAr[i] == NOCHOICE) {
        finalBatchAr[i] = UNMALTED;
      }
    }
  }

  private void appendResult(int testCase, int numFlavors) {

    result.append("Case #" + testCase + ": ");

    if(!isPossible) {
      result.append("IMPOSSIBLE");
    }
    else {
      for(int i = 0; i < finalBatchAr.length; ++i) {
        result.append(finalBatchAr[i] + " ");
      }
    }
    result.append("\n");
  }

  private void writeResultToFile() {  
    PrintWriter pr = null;

    try {
      pr = new PrintWriter(new File("/* File name */"));
      pr.print(result);        

    } catch(FileNotFoundException e) {
        e.printStackTrace();
    } finally {
        if(pr != null) {
          pr.close();
        }
    } 
  }

  private void cleanUpCustomerPreferenceList(ArrayList<Integer> removeList) {
    for(int i = 0; i < removeList.size(); ++i) {
      int removeIndex = removeList.get(i);
      customerPreferenceList.remove(removeIndex - i);
    }
  }
}
share|improve this question
add comment

2 Answers

Your go() method is waaaaaaaayyyyyyyyyyyyyy to long, break it up in digestible parts. Try to think in different abstraction levels, and don't mix them in one method (e.g. you deal with file input directly, but have a separate method for writing into a file). Follow the Single Responsibility Principle.

You should use extended for loops where possible, e.g.

for(int j = 0; j < customerPrefs.length; ++j) {
   custRow.add(Integer.parseInt(customerPrefs[j]));
}

-->

for(String customerPref : customerPrefs) {
   custRow.add(Integer.parseInt(customerPref));
}
share|improve this answer
    
thanks for the input. In your words, why do you think a smaller method is necessarily better than a larger one? How would you respond to the argument that given a solution that requires steps A, B, and C to complete it is easier to code them sequentially in one function rather than forcing whoever wants to understand the program to jump back and forth in the code between method definitions? Not saying I disagree with your response, I would just like to hear your opinion. –  sproule Aug 29 '11 at 17:43
1  
The answer is "level of abstraction". If your method needs to do A, B and C to perform a task, it must do it. However if you have to do A1, A2 and A3 in order to do A, you should have a separate method encapsulating these steps, which is called from the top-level method. In your method, you have more or less a comment for every logical step, which are top-level abstractions. Pack the code after every comment a separate method, and call it from go(). But all of this is just an application of the Single Responsibility Principle. –  Landei Aug 30 '11 at 7:08
2  
@fiddlesticks Have a read at this great article by Uncle Bob blog.objectmentor.com/articles/2009/09/11/… You don't have to extract it so much as in the article, but that gives you a good idea. And you don't have to worry about someone having to jump back and forth to understand the code. With more methods (with each method name suggesting the intent) a reader would be skipping the methods he doesn't care about. And that's a very good thing ! –  stratwine Sep 2 '11 at 18:39
    
You can't foreach through an array. –  Eva Jul 10 '12 at 13:42
    
@sproule When A,B,and C are longer than 15 lines of code put together (or more practically when the code starts to smell), it's easier to jump between different well-named methods than slog through one poorly-named one. –  Eva Jul 10 '12 at 13:50
show 1 more comment

Move try/catch/finally block body to separate method. Its main goal is an error processing, and body is a main functionality, so they have different responsibility.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.