Last active
August 20, 2022 11:30
-
-
Save Morriz/6d90cefe2fd3c6fd517e39fedf784f2b to your computer and use it in GitHub Desktop.
My solution to codility grocery store problem: https://app.codility.com/programmers/task/grocery_store/
This file contains hidden or 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
/** | |
* There is no food in your fridge and you are hungry. You want to go to a local store and buy some food. You have to hurry as some of the shops will close soon. | |
* | |
* There are N squares in your neighborhood and M direct roads connecting them. The squares are numbered from 0 to N − 1. You are living in square 0 and can reach it in 0 seconds. The stores are located in the squares, one in each of them. You are given a map of the neighborhood in the form of four zero-indexed arrays A, B, C and D. Each of the arrays A, B, C contains M integers, while D contains N integers. | |
* | |
* For each I (0 ≤ I < M), the walking distance between squares A[I] and B[I] is C[I] seconds (in either direction). | |
* There can be multiple roads connecting the same pair of squares, or a road with both ends entering the same square. | |
* It is possible that some roads go through tunnels or over bridges (that is, the graph of squares and roads doesn't have to be planar). | |
* It is not guaranteed that you are able to reach all the squares. | |
* For each J (0 ≤ J < N), the shop at square J will close in D[J] seconds (if D[J] = −1, then the store is already closed); | |
* it is possible to buy the food even if you reach the shop at the very last second, when it closes. | |
* | |
* Write a function: function solution(A, B, C, D); | |
* that, given arrays A, B, C and D, returns the minimum time (in seconds) needed to reach an open store. If it is impossible, it should return −1. | |
* | |
* Approach chosen: | |
* | |
* Traverse adjacent nodes by visiting closest one and repeating from there until all nodes are visited, | |
* while keeping a table of travel time towards each node. | |
*/ | |
const solution = (A, B, C, D) => { | |
if (!A.length) return D[0] < 0 ? D[0] : 0 | |
const remainingOpenTimes = D | |
const times = [0] | |
const skipBlocks = {} | |
const connect = (block = 0) => { | |
// find adjacent blocks | |
const connectedBlocks = A.reduce((ret, startBlock, i) => { | |
const nextBlock = B[i] | |
const travelTime = C[i] | |
if ((startBlock === block && !skipBlocks[nextBlock]) || (nextBlock === block && !skipBlocks[startBlock])) { | |
ret.push([startBlock, nextBlock, travelTime]) | |
} | |
return ret | |
}, []) | |
if (!connectedBlocks.length) { | |
skipBlocks[block] = true // it ends here | |
return | |
} | |
// and calc minimal time to each | |
connectedBlocks.forEach(([_startBlock, _nextBlock, travelTime]) => { | |
const startBlock = _startBlock === block ? _startBlock : _nextBlock | |
const nextBlock = _nextBlock === block ? _startBlock : _nextBlock | |
if (times[nextBlock]) { | |
times[nextBlock] = Math.min(times[nextBlock], travelTime + (times[startBlock] || 0)) | |
} else times[nextBlock] = travelTime + (times[startBlock] || 0) | |
skipBlocks[startBlock] = true | |
}) | |
// continue with the block with the lowest distance | |
const minBlock = times.reduce((ret, time, i) => { | |
if (skipBlocks[i]) return ret | |
if (ret === undefined) ret = [i, time] | |
else if (time < ret[1]) ret = [i, time] | |
return ret | |
}, undefined) | |
if (minBlock && !skipBlocks[minBlock[0]]) connect(minBlock[0]) | |
} | |
connect() | |
const possible = remainingOpenTimes.reduce((time, remainingOpenTime, block) => { | |
const open = times[block] <= remainingOpenTime | |
if (time === undefined) { | |
if (open) time = times[block] | |
} else if (open && times[block] < time) time = times[block] | |
return time | |
}, undefined) | |
if (possible !== undefined) return possible | |
return -1 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I was however unable to perceive why one of the tests failed, leaving this at a 90% success rate.