Вот мой пример структуры данных:
r означает строку.
var data = {
r0: ["E9", "55", "1C"],
r1: ["1C", "E9", "E9"],
r2: ["BD", "1C", "55"]
}
Как мне найти все пути, где пути не могут быть одинаковыми, пути могут проходить только по горизонтали (и только начиная с строки 0), затем по вертикали, затем по горизонтали и т. д., во время пути он не может выбрать одно и то же значение . Однако пути могут «прыгать» по значениям, если в текущей строке/столбце обнаружено допустимое значение.
Строки и столбцы начинаются с индекса 0.
Примеры ожидаемых путей, выводимых из будущего алгоритма:
RowColumn(value),....
// these paths stop because there are no more valid vertical or horizontal values to pick.
00(E9), 10(1C), 11(E9), 01(55), 02(1C), 22(55), 12(E9)
02(1C), 22(55), 20(BD), 00(E9), 01(55), 21(1C), 11(E9), 10(1C), 12(E9)
🤔 А знаете ли вы, что...
JavaScript поддерживает асинхронное программирование с использованием промисов и асинхронных функций.
// Trying to replicate output 00(E9), 10(1C), 11(E9), 01(55), 02(1C), 12(E9), 22(55), 21(1C), 20(BD)
const algo = (values) => {
// Find the number of keys of the values/data object
const totalKeys = Object.keys(values).length
// Cycle through the keys with an assumption that the first key is always 'r0'
for (let row = 0; row < totalKeys; row++) {
// construct a key name
const keyName = "r" + row
// get the array associated with this key
const arr = values[keyName]
// loop through the array
for (let column = 0; column < arr.length; column++) {
// get the current value
const value = arr[column]
// do whatever you want to do with values, I am just printing them here
console.info("" + row + column + "(" + value + ")")
}
}
}
const data = { // usage of var is discouraged, use let or const instead
r0: ["E9", "55", "1C"],
r1: ["1C", "E9", "E9"],
r2: ["BD", "1C", "55"]
}
algo(data);Прочитав ваш вопрос, я понял, что правила были такими:
0_0Чтобы получить каждый путь, соответствующий этим правилам, вы можете использовать рекурсивную функцию (функция, которая вызывает сама себя).
В следующем примере он принимает 2 параметра:
При первом вызове мы даем ему путь, содержащий первую ячейку (['0_0']), и true, потому что мы должны двигаться горизонтально.
Тогда это будет:
function rowColumn(obj) {
// Convert the Object to a 2D Array
const data = Object.values(obj),
rows = data.length,
cols = data[0].length,
res = [];
function recursive(path, horizontal) {
// Get the row or column cells that haven't been visited yet
const nextCells = getNextCells(path, horizontal);
// If no neighbors were found, push the result and return
if (!nextCells.length) return res.push(path);
// Apply recursion for all possible neighbors
nextCells.forEach(cell => recursive(path.concat(cell), !horizontal));
}
function getNextCells(path, horizontal) {
const [x, y] = path[path.length - 1].split('_').map(v => +v);
let cells = [];
if (horizontal) cells = Array.from({length: cols}, (_, i) => `${i}_${y}`);
else cells = Array.from({length: rows}, (_, i) => `${x}_${i}`);
// Remove the cells that have already been visited
return cells.filter(p => !path.includes(p));
}
// Start the recursion
recursive(['0_0'], true);
// Format the result
return res.sort((a, b) => a.length - b.length)
.map(path => path.map(cell => {
const [x, y] = cell.split('_').map(v => +v);
return `${x}${y}(${data[y][x]})`;
}));
}
const data = {
r0: ["E9", "55", "1C"],
r1: ["1C", "E9", "E9"],
r2: ["BD", "1C", "55"],
};
const res = rowColumn(data);
console.info(
`There are ${res.length} paths possible:`,
res.map(path => path.join(' '))
);