Last active
March 26, 2020 02:06
-
-
Save gie3d/9f0b47e197074d2965794d8242ecfb1c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const fs = require('fs'); | |
| fs.readFile('input', 'utf8', (err, contents) => { | |
| console.log(contents); | |
| const data = parseData(contents); | |
| // console.log(data); | |
| const result = findBestRoutePoint(data); | |
| console.log(result); | |
| }); | |
| const findBestRoutePoint = data => { | |
| let memo = {}; | |
| let result = 0; | |
| for (let row = 0; row < data.m; row++) { | |
| let rowPoint = routePoint(row, 0, data, memo); | |
| if (rowPoint > result) { | |
| result = rowPoint; | |
| } | |
| } | |
| return result; | |
| }; | |
| const routePoint = (row, column, data, memo) => { | |
| const memoKey = `${row}-${column}`; | |
| if (memo[memoKey] !== undefined) { | |
| // console.log('utilize memo: ', memoKey); | |
| return memo[memoKey]; | |
| } | |
| if (isOutOfBound(row, column, data)) { | |
| return 0; | |
| } else if (column === data.n - 1) { | |
| return data.field[row][column]; | |
| } else { | |
| const upRight = routePoint(row - 1, column + 1, data, memo); | |
| const right = routePoint(row, column + 1, data, memo); | |
| const downRight = routePoint(row + 1, column + 1, data, memo); | |
| const maxRoute = Math.max(upRight, right, downRight); | |
| const result = data.field[row][column] + maxRoute; | |
| memo[memoKey] = result; | |
| return result; | |
| } | |
| }; | |
| const isOutOfBound = (row, column, data) => { | |
| const isOutOfColumn = column >= data.n; | |
| const isOutOfRow = row < 0 || row >= data.m; | |
| return isOutOfColumn || isOutOfRow; | |
| }; | |
| const parseData = contents => { | |
| let result = {}; | |
| try { | |
| const splitContents = contents.split(/\r?\n/); | |
| result.m = parseInt(splitContents[0].split(' ')[0]); | |
| result.n = parseInt(splitContents[0].split(' ')[1]); | |
| result.field = []; | |
| for (let i = 1; i < splitContents.length; i++) { | |
| result.field.push(splitContents[i].split(' ').map(x => parseInt(x))); | |
| } | |
| } catch (e) { | |
| console.log('error: ', e); | |
| } | |
| return result; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment