/
findMaxPath.js
99 lines (93 loc) · 2.78 KB
/
findMaxPath.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
export function findMaxPath(board) {
let globalMaxPath = Number.NEGATIVE_INFINITY
for (let row = 0; row < board.length; row += 1) {
for (let column = 0; column < board[0].length; column += 1) {
const validPaths = findAllValidPaths(row, column, board)
validPaths.sort()
const largestValidPath = validPaths[validPaths.length - 1]
if (largestValidPath > globalMaxPath)
globalMaxPath = largestValidPath
}
}
return globalMaxPath
}
function findAllValidPaths(row, column, board) {
function findValidPaths(
rowPosition,
columnPosition,
board,
pathTracker = [],
previousMove = 'NONE'
) {
pathTracker.push(board[rowPosition][columnPosition])
if (isValidPath(pathTracker)) {
// use lexical scoping to reach outside and add path to validPaths
return validPaths.push(Number(pathTracker.join('')))
}
// look left
if (columnPosition - 1 >= 0 && isValidMove(previousMove, 'LEFT')) {
findValidPaths(
rowPosition,
columnPosition - 1,
board,
[...pathTracker],
'LEFT'
)
}
// look right
if (
columnPosition + 1 < board[0].length &&
isValidMove(previousMove, 'RIGHT')
) {
findValidPaths(
rowPosition,
columnPosition + 1,
board,
[...pathTracker],
'RIGHT'
)
}
// look up
if (rowPosition - 1 >= 0 && isValidMove(previousMove, 'UP')) {
findValidPaths(
rowPosition - 1,
columnPosition,
board,
[...pathTracker],
'UP'
)
}
// look down
if (
rowPosition + 1 < board.length &&
isValidMove(previousMove, 'DOWN')
) {
findValidPaths(
rowPosition + 1,
columnPosition,
board,
[...pathTracker],
'DOWN'
)
}
}
const validPaths = []
findValidPaths(row, column, board)
return validPaths
}
function isValidPath(path) {
if (path && path.length === 4) return true
return false
}
const oppositeMoves = {
LEFT: 'RIGHT',
RIGHT: 'LEFT',
UP: 'DOWN',
DOWN: 'UP',
}
/**
* Determines if a move is valid based on the previous move; this works because we are limited to only four integers and as a result _cannot_ repeat unless we go back as diagonal values are not available.
*/
function isValidMove(previousMove, proposedMove) {
return oppositeMoves[previousMove] !== proposedMove
}