Привет ! Меня зовут Ксавье Жувено, и вот пятнадцатая часть длинной серии статей о Пришествии кода. Предыдущую часть можно найти здесь

В этом новом посте мы решим задачу от 15 декабря 2015 года под названием «Наука для голодных». Решение я предложу на C++, но рассуждения можно применить и к другим языкам.

Часть 1

Проблема

Полную версию этой проблемы можно найти непосредственно на сайте Пришествие кода, здесь я опишу лишь суть проблемы:

Сегодня мы должны создать идеальный рецепт печенья с молоком. Для этого нам нужно найти правильный баланс ингредиентов.

Наш рецепт должен содержать 100 чайных ложек ингредиентов, и для его создания мы знаем ингредиенты, которые будем использовать, и их свойства на чайную ложку: capacity, durability, flavor, texture и calories. Чтобы оценить, хорош рецепт или нет, мы можем рассчитать балл для рецепта, сложив каждое из свойств (отрицательные суммы становятся равными 0), а затем перемножив все, кроме калорий.

Например, если у нас есть следующие ингредиенты:

Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3

Лучший рецепт будет состоять из 44 чайных ложек ириски и 56 чайных ложек корицы, а оценка этого рецепта будет выглядеть так: total_capacity * total_durability * total_flavor * total_texture, и каждое общее свойство рассчитывается путем умножения свойства каждого ингредиента на количество чайных ложек этого ингредиента. Например, расчет total_capacity: total_capacity = -1 * 44 + 2 * 56 = 68

Чтобы получить наш идеальный рецепт, мы должны найти тот, у которого лучший результат.

Решение

Идеальный рецепт печенья, я проголодался, только подумав об этом! 🍪

Прежде всего, мы должны извлечь из входных данных важную информацию, все свойства ингредиентов.

constexpr auto numberOfProperties = 4;
using PropertyValue = int;
using Ingredient = std::array<PropertyValue, numberOfProperties>;
Ingredient extractIngredientFrom (const std::string& line)
{
  std::istringstream stream(line);
  std::string ingredientName, capacity, comma, durability, flavor, texture;
  PropertyValue capacityValue, durabilityValue, flavorValue, textureValue;
  stream >> ingredientName >> capacity >> capacityValue >> comma >> durability >> durabilityValue >> comma >> flavor >> flavorValue >> comma >> texture >> textureValue;
  return Ingredient{capacityValue, durabilityValue, flavorValue, textureValue};
}

Вся необходимая информация — это свойства ингредиентов. Нам даже не нужны калории — так называется ингредиент.

Более того, вы можете видеть, что в инструкции по сбору информации из stream мы несколько раз использовали переменную запятую. На самом деле мы могли бы использовать только одну переменную мусора для всех элементов, которые мы не хотели получать. Но я предпочитаю этого не делать, чтобы инструкция отражала структуру ввода и облегчала чтение.

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

std::vector<Proportions> createAllProportionPossibles(size_t numberOfIngredients, size_t teaspoonNumber)
{
  if (numberOfIngredients == 1)
  {
    return {Proportions{teaspoonNumber}};
  }
  std::vector<Proportions> proportions;
  for(auto i = size_t{1}; i < teaspoonNumber; ++i)
  {
    const auto proportionsOfLessIngredients =
      createAllProportionPossibles (numberOfIngredients - 1, teaspoonNumber - i);
    for(const auto& proportionsOfLessIngredient : proportionsOfLessIngredients)
    {
      Proportions p {i};
      p.insert(p.end(), proportionsOfLessIngredient.begin(), proportionsOfLessIngredient.end());
      proportions.push_back(p);
    }
  }
  return proportions;
}

Легко, правда?… Шучу, мы на самом деле объясним этот код 😉

Первое, что нужно знать, это то, что мы используем рекурсию. Почему ? Потому что, допустим, у вас есть два ингредиента на 3 чайные ложки. Возможные пропорции были бы списком пары чисел (1, 2) и (2, 1). Теперь возьмем три ингредиента на 4 чайные ложки, поэтому соотношение будет (1, 1, 2), (1, 2, 1) и (2, >1, 1). Как видите, выделенное жирным шрифтом число в первых тройках — это число из списка пропорций на два ингредиента, на 3 чайные ложки. А в последней паре два жирных числа — это единственная возможная пропорция для 2 ингредиентов и 2 чайных ложек, так как 2 других занимает первый ингредиент.

Давайте углубимся в код, так будет понятнее.

Итак, сначала у нас есть условие остановки рекурсии. Действительно, если у нас есть только один ингредиент, мы даем ему всю чайную ложку, которая у нас есть.

Теперь рекурсия. В этой части кода мы даем первому ингредиенту все больше и больше чайной ложки с первой петлей. Затем мы генерируем все пропорции, возможные без этого ингредиента и чайной ложки, предоставленной ему. Наконец, в последнем цикле мы создаем пропорции, добавляя количество чайных ложек первого ингредиента ко всей пропорции, полученной без него.

И тогда у нас есть это, мы можем генерировать все пропорции независимо от количества чайных ложек и ингредиентов.

Все, что нам осталось сделать, это найти, какая пропорция является лучшей.

constexpr auto teaspoonsNumber = 100;
const auto allProportionsPossible = createAllProportionPossibles (ingredients.size(), teaspoonsNumber);
const auto winningProportion = std::max_element(
  std::begin(allProportionsPossible),
  std::end(allProportionsPossible),
  [&ingredients](const auto& firstProportion, const auto& secondProportion)
  {
    return calculateTotalScore(ingredients, firstProportion) < calculateTotalScore(ingredients, secondProportion);
  });
const auto bestTotalScore = calculateTotalScore(ingredients, *winningProportion);

Как видите, после создания всех возможных пропорций мы используем алгоритм std::max_element, чтобы найти наилучшую. Мы также используем метод calculateTotalScore, который вычисляет оценку одной пропорции. Итак, давайте посмотрим на его тело.

int calculateTotalScore(std::vector<Ingredient> ingredients, Proportions proportion)
{
  auto score{1};
  for(auto propertyIndex = size_t{0}; propertyIndex < numberOfProperties; ++propertyIndex)
  {
    auto propertyScore{0};
    for(auto indexIngredient = size_t{0}; indexIngredient < ingredients.size(); ++indexIngredient)
    {
      const auto& ingredient = ingredients[indexIngredient]; propertyScore += ingredient[propertyIndex] * proportion[indexIngredient];
    }
    if(propertyScore < 0)
    {
      score = 0;
      break;
    }
    score *= propertyScore;
  }
  return score;
}

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

И вуаля, с этим последним фрагментом кода мы можем найти лучший рецепт печенья 🥇

Часть 2

Проблема

Отлично, теперь наш рецепт популярен, и мы хотим сделать лучший рецепт печенья 500 калорий.

Решение

Логика решения этой части такая же, как и в первой части. Сначала мы собираем информацию, затем генерируем все возможные пропорции и, наконец, находим выигрышную пропорцию ингредиента. Генерация пропорций остается такой же, как и в первой части. Но сбор информации, теперь мы собираем количество калорий, которое раньше было бесполезным. Чтобы это выглядело так:

constexpr auto numberOfProperties = 5;
using PropertyValue = int;
using Ingredient = std::array<PropertyValue, numberOfProperties>;
Ingredient extractIngredientFrom (const std::string& line)
{
  std::istringstream stream(line);
  std::string ingredientName, capacity, comma, durability, flavor, texture, calories;
  PropertyValue capacityValue, durabilityValue, flavorValue, textureValue, caloriesValue;
  stream >> ingredientName >> capacity >> capacityValue >> comma >> durability >> durabilityValue >> comma >> flavor >> flavorValue >> comma >> texture >> textureValue >> comma >> calories >> caloriesValue;
  return Ingredient{capacityValue, durabilityValue, flavorValue, textureValue, caloriesValue};
}

И, наконец, самая важная часть — это подсчет очков рецепта.

int calculateTotalScore(std::vector<Ingredient> ingredients, Proportions proportion)
{
  auto score{1};
  for(auto propertyIndex = size_t{0}; propertyIndex < numberOfProperties; ++propertyIndex)
  {
    auto propertyScore{0};
    for(auto indexIngredient = size_t{0}; indexIngredient < ingredients.size(); ++indexIngredient)
    {
      const auto& ingredient = ingredients[indexIngredient];
      propertyScore += ingredient[propertyIndex] * proportion[indexIngredient];
    }
    if(propertyIndex == numberOfProperties - 1)
    {
      return (propertyScore != 500) ? 0 : score;
    }
    if(propertyScore < 0)
    {
      return 0;
    }
    score *= propertyScore;
  }
  return score;
}

Большая часть расчета остается прежней. Мы по-прежнему вычисляем оценку каждого свойства, но если это последнее свойство, также известное как калорийность, мы проверяем, равна ли его оценка 500. Если это не так, мы устанавливаем оценку 0, в противном случае мы интегрируем ее в итоговую оценку.

И так, у нас есть решение второй части этой проблемы 😃

Вывод

Вы можете заметить, что решения, написанные в этом посте, включают не все исходники для создания работающих программ, а только интересную часть исходников для решения этой проблемы. Если вы хотите увидеть программы от начала до конца, вы можете зайти на мою учетную запись GitHub, изучить полное решение, добавить комментарии или задать вопросы, если хотите, на платформе, на которой вы читаете эту статью, она также поможет мне. улучшить качество моих статей.

Вот список элементов, которые мы использовали, я не могу убедить вас взглянуть на их определения:

Спасибо, что читаете, надеюсь, вам понравилось 😃

И до следующей части, получайте удовольствие, учась и развиваясь.

Первоначально опубликовано на http://10xlearner.com 4 ноября 2019 г.