Skip to content

Instantly share code, notes, and snippets.

@Morriz
Last active August 20, 2022 11:30
Show Gist options
  • Save Morriz/6d90cefe2fd3c6fd517e39fedf784f2b to your computer and use it in GitHub Desktop.
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/
/**
* 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
}
@Morriz
Copy link
Author

Morriz commented Feb 13, 2019

I was however unable to perceive why one of the tests failed, leaving this at a 90% success rate.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment