Написать программу, реализующую алгоритм склейки перелетов. Входные данные брать из файла input.json, результат должен помещаться в файл output.json.
На входе дано перечисление строк. Каждая строка состоит из опциональных строковых элементов. "a1" - элемент присутствует, null - элемент отсутствует.
[
[ "a1", "a2", "a3", "a4" ], <- первая строка
[ "b1", null, null, "b4" ],
[ null, "c2", "c3", null ], <- 3я строка
[ "d1", null, null, "d4" ],
[ null, "e2", "e3", null ], <- 5я строка
[ null, "f2", "f3", "f4" ],
[ "h1", null , null, null ], <- 7я строка
[ "g1", null , null, null ]
]
Необходимо получить все возможные сочетания строк так, чтобы их строковые элементы полностью дополняли друг друга.
Строки парсятся в структуру, в которой хранится битовая маска и все строки удовлетворяющие этой маске. Например, пример выше разбивается в структуру из таблицы ниже.
| Маска в десятичной системе | Маска | Номер строк удовлетворяющие значению маски |
|---|---|---|
| 6 | 0110 | 3,5 |
| 7 | 0111 | 6 |
| 8 | 1000 | 7,8 |
| 9 | 1001 | 2,4 |
| 15 | 1111 | 1 |
Таким образом в последующем, мы работаем не со строками, а с битовыми масками, что позволяет сравнивать не отдельные примеры, а множества строк , подходящих под маску.
Далее, находятся все комбинации масок используя две формулы:
- ((a|b)^a)^b - проверяет валидность склейки
- (a|b) - возвращает результат склейки
Например, при склеивании масок 6 и 8
- ((a|b)^a)^b = 0
- (a|b) = 1110
В результате получаем все комбинации склеек для масок.
[
[ 8 , 7 ],
[ 9 , 6 ],
[ 15 ]
]
Далее, рекурсивно сопостовляются все возможные варианты комбинаций строк.