best-travel-puzzle code to try: node bestTravel.output.v2.js.
CONTENTS
0 FOREWORD
1 LIBRARY
1.1 CONSTANTS
1.2 UNIT FUNCTIONS
1.2.1 assert (for local testing)
1.2.2 allRoutesIndexesExtractor
1.2.3 headAndTailIndex
1.2.4 zipper
1.2.5 allRoutesHeadsAndTails
1.2.6 allRoutesBodyParts
1.2.7 comparator
1.2.8 allRoutesFromVariationsScope
1.2.9 numSplitter
1.2.10 isAscending
1.2.11 onlyAscendingFiltered
1.2.12 zeroPrefixAdder
1.2.13 strokeToCellsSeparator
1.2.14 allRoutesAddressess
1.2.15 nowhereToHide
1.2.16 allRoutes
1.2.17 allRoutesLengths
1.2.18 allRoutesLengthsIndexed
1.2.19 allDistances
1.2.20 allRoutesDetails
1.2.21 TargetRouteDetails
2 BUILDING
2.1 MODULE FUNCTIONS
2.1.1 optimalRouteFinder
0 FOREWORD
О структуре программы.
Код состоит из содержания, библиотеки, модульной функции
В библиотеке лежат константы и примитивные функции.
Каждая примитивная функция сопровождается тестом.
Объявления функций максимально возможно отделены от их вызова.
Внутри библиотеки функции видят друг друга, хоть и очень редко связаны.
Модульная функция пользуется функциями из библиотеки.
Вызовы в ней происходят по цепочке снизу верх.
Так как тест расположен снизу, так легче понять, какое значение требуется и
благодаря примерам-аннотациям понятно, как значение меняется проходя через
функции.
Сам модуль представляет собой комплекс из оболочки и объекта хранящего стек функций.
Оболочка принимает необходимые данные, вызывает последнюю функцию в стеке из объекта
и возвращает значение вызова.
Объект хранит пары из ключа, указывающего значение функции и самой функции с
нужными ей в данном контексте вводными. Начиная с нижней функции требующей результаты
вышележащей остальные вызываеются по цепочке, тем самым проводя данные ввода через серию
преобразований.
Условие задачи.
Джон и Мери хотят посетить несколько городов A, B, C... Мери на листке бумаги
перечисляет расстояния между этими городами. ls = [50, 55, 57, 58, 60]. Но проблема
в том, что Джону надоело водить машину и он сказал Мери, что поедет не больше t = 174 километров
и максимум они посетят 3 города. Какие расстояния, а следовательно, какие города они выберут,
чтобы сумма расстояний была максимально возможной? Например, у них есть списки из трех городов
с расстояниями между ними: [50,55,57],[50,55,58],[50,55,60],[50,57,58],[50,57,60],[50,58,60],
[55,57,58],[55,57,60],[55,58,60],[57,58,60]. Суммы расстояний между этими городами составляют:
162, 163, 165, 165, 167, 168, 170, 172, 173, 175. Так как Джон категорически против ехать больше
174 километров, то нужное нам расстояние составляет 173 километра, а значит правильный ответ
будет [55, 58, 60].
Функция chooseBestSum принимает три параметра: t - максимальная дистанция, k - число городов,
которое надо посетить и ls - массив дистанций между городами. Функция возвращает максимальное
расстояние, если такое существует, иначе null
1 Вход: ( 163, 3, [50, 55, 56, 57, 58] ),
Выход: 163 ([[50,55,58],163]).
2 Вход: ( 163, 3, [50] ),
Выход: null
3 Вход: ( 230, 3, [91, 74, 73, 85, 73, 81, 87] ),
Выход: 228 ([[74,73,81],228]).
Обоснование решения.
Так как я не нашел ни одного понятного решения похожей задачи по комбинаторике, собрал свое.
1. Для начала найдем все возможные сочетания путей между данным множеством городов.
У такого сочетания на каждой позиции может стоять только определённое множество значений,
Например, для множества городов = [c1,c2,c3,c4,c5] в сочетаниях по три, множество сочетаний
областей допустимых значений (ОДЗ) выглядит [[c1,c2,c3],[c2,c3,c4],[c3,c4,c5]].
Таким образом надеюсь понятно, какие города на каких местах могут стоять и на каких точно не могут.
2. Теперь для того, чтобы по очереди найти все сочетания, надо найти всё множество адресов,
по которым можно их достать. Общее число адресов равно длине сочетания в степени равной величине
ОДЗ каждой позиции. То есть в данном случае 3*(3*3).
3. Нужно как-то сделать счетчик адресов с тремя позициями, по количеству членов сочетания.
Пусть он выглядит как 000. Каждое число в позиции может принимать значени от 0 до значения
длины ОДЗ, то есть от 1 до 3 (то есть от 0 до 2х). Чтобы получить значения счетчиков (000,001,002,010,011..)
нужно перевести общее число адресов (27) в подходящую систему счисления, в данном случае с основанием 3.
4. Теперь фильтруем адреса с только возрастающими значениями членов, чтобы убрать повторяющиеся сочетания.
5. С полученным множеством адресов достаем все возможные сочетания путей.
6. Считаем длину каждого пути.
7. Собираем в один массив детали пути и его длину.
8. По заданному значению длины пути возвращаем оптимальное сочетание городов вместе с длиной пути.