Программированию Яндекс раствора (молочные коктейли)


На практике, я работаю через некоторые проблемы с Google Джем код. Код ниже-это для коктейлей проблему, которая находится здесь.

Проблема

Вы владеете молочный магазин. Есть N различных ароматов, которые вы можете готовить, и каждый аромат можно приготовить "солод" или "несоложеных". Так, вы можете сделать \$2л\$ различные виды коктейлей.

Каждый из ваших клиентов имеет набор типов коктейль, что им нравится, и они будут довольны, если у вас есть по крайней мере один из этих типов подготовлены. Одним из видов клиент любит будет "солод" вкус.

Вы хотите сделать \ФП\$ партий молочные коктейли, так что:

Есть ровно одна партия для каждого вкуса молочного коктейля, а это либо соложеного или несоложеного. Для каждого клиента, вы делаете по крайней мере один типа коктейль, что им нравится. Минимально возможное количество партий это солод. Найти можно ли удовлетворить все ваши клиенты учитывая эти ограничения, и если это так, что коктейль следует сделать. Если это возможно, чтобы удовлетворить все ваши клиенты, будут единственный ответ, который минимизирует количество солодового партий.

Вход

  • Первая строка содержит целое число \$С\$, количество тестов в входной файл.

Для каждого тестового случая будет:

  • Одну строку, содержащую целое число \ФП\$, количество ингредиенты.
  • Одну строку, содержащую целое число \$м\$, количество клиентов.
  • \$М\$ строк, по одной для каждого клиента, каждый из которых содержит:
    • Целое число \$Т >= 1\$, количество молочного коктейля типы клиент любит, затем
    • \$Пар Т\$ целых чисел X и y, по одному для каждой тип заказчику нравится, где \Х $\$ - это молочный коктейль вкус между 1 и \Н $\$ включительно, и $\Г\$ либо 0, чтобы указать, соложеный, или 1 к указанному соложеного. Обратите внимание, что:
      • Ни одна пара будет происходить более чем один раз для одного клиента.
      • Каждый клиент будет иметь по крайней мере один аромат, который им нравится (\$Т >= 1\$).
      • Каждому клиенту понравится одно солодовый вкус. (В большинстве одна пара для каждого клиента \$г = 1\$).

Все эти числа разделяются одним пробелом.

Выход

  • C строк, по одной для каждого тестового случая в порядке их следования во входных данных файл, каждая из которых содержит строку "дело № X:", где X-число тестовый случай, начиная с 1, затем:
    • Строку "Impossible", если клиентов не может быть удовлетворен; или
    • N разделенных пробелами целых чисел, по одному на каждый вкус от 1 до n, которые равны 0 если соответствующий вкус должен быть подготовлен несоложеных, и 1, если он должен быть солод. Пределы

Небольшой набор данных

\$С = 100\$
\$1 <= Н <= 10\$
\$1 <= М <= 100\$

Большой набор данных

\$С = 5\$
\$1 <= Н <= 2000\$
\$1 <= М <= 2000\$

Сумма всех \$Т\$ значения для клиентов в тестовом случае не будет превышать 3000.

Это решение решает для обеих маленьких и больших наборов данных. Пожалуйста, дайте мне знать, как я могу улучшить этот код.

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);
    }
  }
}


2515
3
задан 29 августа 2011 в 12:08 Источник Поделиться
Комментарии
2 ответа

Ваш идти() метод waaaaaaaayyyyyyyyyyyyyy к длинным, разбейте его на удобоваримые части. Попробуйте мыслить на разных уровнях абстракции, и не смешивать их в одном методе (например, вы имеете дело с входного файла напрямую, но иметь отдельный метод для записи в файл). Выполните один принцип ответственности.

Вы должны использовать расширенные петли там, где это возможно, например,

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

-->

for(String customerPref : customerPrefs) {
custRow.add(Integer.parseInt(customerPref));
}

3
ответ дан 29 августа 2011 в 07:08 Источник Поделиться

Перейти попробовать/поймать/наконец тело блока в отдельный метод. Ее основной целью является обработка ошибок, а тело-это основной функциональности, поэтому они имеют разную ответственность.

1
ответ дан 2 сентября 2011 в 10:09 Источник Поделиться