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 вагон?
- Не указано, можно ли покупать остаток галлонов у продавца, если этот остаток меньше инкремента. Т.е. тот случай, когда продаем по 10 галлонов, а в наличии только 2.
- Если минимальная партия меньше инкремента, то это может привести к тому, что выгодно покупать не одним заказом, а несколькими - маленькими.
- Задача смахивает на NP-полную. Если это действительно так, найти общее решение можно только перебором. См. Задача о покрытии множества
- Если задача таки NP-полная, то нужен дополнительный критерий для поиска решения. Например, ищем 20 секунд, потом берем что нашли.
- Интерфейсом не задано поведение при плохих данных и/или запросе.
- Уровнень видимости полей для бинов из API package-private, возможно, это "опечатка", но менять некошерно.
Что бы задачу можно было решить, не потратив на нее слишком много времени, были приняты следующие допущения:
- Разрешается покупать больше, чем необходимо. Для решения пункта 1) выше
- Общий размер доступного к продаже должен быть таким, что бы его можно было полностью выкупить одним заказом. 2)
- Минимальная пария всегда больше или равна инкременту. Адресуем 3) выше
- При невозможности выполнить запрос (недостаточно рома на рынке, неверный формат файла и т.п.) метод helpJackSparrow возвращает null. Это очень плохая практика, но API задан и менять его мы не можем. RuntimeException не рассматриваем. 6)
- В данные нам свыше бины добавлены стандартные геттеры/сеттеры.
Предположительно, задача NP-полная. Значит, единственный вариант найти оптимальное решение - перебор. Это печально, но придется строить дерево решений.
У оптимального решения очевидный минус - дохрена ресурсов жрет, собака. Поэтому есть еще два варианта - Жадный алгоритм и Генетический алгоритм
- DI не предусмотрен, хоть и напрашивается