Jack Sparrow Holiday Party

Just another little project that was developed as part of interview for software company. Keeping it as a reference to my code style.

Очередной небольшой проект, разработанный в качестве тестового задания.

Условие задачи, как оно было получено

Вариант покороче есть ниже.

Уилл Тернер решил устроить пир как в старые добрые времена и попросил своего друга, капитана Джека Воробья, организовать это мероприятие. Джек решил, что для того чтобы пирушка удалась, ему необходимо купить N галлонов ямайского рома Appleton. Ром можно добыть в ряде мест:

• В Порт-Ройале есть три лавки, в которых торгуют ромом. В лавке Мэллроя есть 50 бутылок (в бутылке один галлон) по цене 50 пиастров за штуку, в лавке Сяо Фэня есть 60 бутылок по цене 52 пиастра, и в винном погребе Черной Бороды есть 200 по цене 55 пиастров.

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

• Похожая ситуация с Гектором Барбоссой. У Гектора есть целых три сундука по сто бутылок, каждый из которых стоит 5050 пиастров, и он даже готов их продать. Но Гектор в данный момент уплыл на Странные берега, и ради продажи одного сундука возвращаться не станет. Но он готов вернуться, если купить у него хотя бы два сундука.

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

Лишних пиастров у Джека никогда не бывает, поэтому он хочет минимизировать свои расходы.

Напишите Java программу, которая реализует интерфейс JackSparrowHelper.

P.S. Программа должна быть понятно написана

P.P.S. Программа будет протестирована с использованием не только приложенного, но и другого csv файла, имеющего тот же формат.

Условие задачи, но короче

Вам нужно купить N галлонов вина.

Вино продается у ряда продавцов, у каждого свои условия:

• цена за галлон
• доступное к продаже количество галлонов
• минимальная партия
• размер инкремента партии закупки (кто-то продает по одной бутылке, а кто-то только вагонами)

Цель: потратив минимальное количество денег, приобрести необходимое число галлонов вина.

Проблемы постановки задачи

1. Не указано, можно ли покупать больше, чем требуется. Например, если продают только вагонами, а нам надо 1 галлон, то допустимо ли купить 1 вагон?
2. Не указано, можно ли покупать остаток галлонов у продавца, если этот остаток меньше инкремента. Т.е. тот случай, когда продаем по 10 галлонов, а в наличии только 2.
3. Если минимальная партия меньше инкремента, то это может привести к тому, что выгодно покупать не одним заказом, а несколькими - маленькими.
4. Задача смахивает на NP-полную. Если это действительно так, найти общее решение можно только перебором. См. Задача о покрытии множества
5. Если задача таки NP-полная, то нужен дополнительный критерий для поиска решения. Например, ищем 20 секунд, потом берем что нашли.
6. Интерфейсом не задано поведение при плохих данных и/или запросе.
7. Уровнень видимости полей для бинов из API package-private, возможно, это "опечатка", но менять некошерно.

Допущения

Что бы задачу можно было решить, не потратив на нее слишком много времени, были приняты следующие допущения:

• Разрешается покупать больше, чем необходимо. Для решения пункта 1) выше
• Общий размер доступного к продаже должен быть таким, что бы его можно было полностью выкупить одним заказом. 2)
• Минимальная пария всегда больше или равна инкременту. Адресуем 3) выше
• При невозможности выполнить запрос (недостаточно рома на рынке, неверный формат файла и т.п.) метод helpJackSparrow возвращает null. Это очень плохая практика, но API задан и менять его мы не можем. RuntimeException не рассматриваем. 6)
• В данные нам свыше бины добавлены стандартные геттеры/сеттеры.

Реализация

Предположительно, задача NP-полная. Значит, единственный вариант найти оптимальное решение - перебор. Это печально, но придется строить дерево решений.

У оптимального решения очевидный минус - дохрена ресурсов жрет, собака. Поэтому есть еще два варианта - Жадный алгоритм и Генетический алгоритм

• DI не предусмотрен, хоть и напрашивается