10
2
Challenge Taken with permission from my University Code Challenge Contest
The dependence we have on mobile phones makes us charge them every night up to the maximum level of the battery, so we do not run the risk of running out of power by the middle of the next day. There are even people who, when they see a free outlet during the day, put it to charge for what may happen.
I am one of them.
Over the years, I have refined my technique to not charge the battery to the maximum every night. With my perfectly known repetitive routines, I am clear on what times of the day I will be able to do those partial recharges (and how many units the level will increase) and what lowers the battery level between each charge. With these data, every night I calculate the minimum battery level I have to leave the house the next day with so that it never falls below my self-imposed threshold of two units.
What I have not yet managed to master is that same calculation when I leave the established routine and I have several alternatives to do things. It happens, for example, on the days when I'm en route to another city to which I can arrive in different ways.
In my first approach to the problem, I am assuming that I want to move around a "chessboard", from the upper-left corner to the lower-right corner. In each "cell" I can either charge the mobile a specific amount, or I cannot and its load level goes down.
Challenge
Given a FxC matrix of integers, output the minimal battery level amount I need to go from the top-left corner to the bottom-right without the load level ever falling below 2 units.
In the matrix, a positive number indicates how much I can charge my mobile phone before I have to resume following my path, while a negative number indicates that there are no outlets and that the mobile's battery drops its charge level by that amount. It is guaranteed that the quantities in the source and destination cells (top-left and bottom-right corner) are always 0 and that the rest of the values (absolute value) do not exceed 100.
Example
Given:
$$ \begin{bmatrix} &-1&1&-1 \\ -1&-1&-1&-1 \\ -1&1&-1&-1 \\ 1&1&-1&0 \end{bmatrix}$$
The path I need less battery is:
$$ \begin{bmatrix} &-1&1&-1 \\ \color{blue}{-1}&-1&-1&-1 \\ \color{blue}{-1}&1&-1&-1 \\ \color{blue}{1}&\color{blue}{1}&\color{blue}{-1}&0 \end{bmatrix}$$
And the minimal battery level amount I need is 4
Notes
- The Start is always going to be the top-left corner
- The End is always going to be the bottom-right corner
- You cannot go to a cell you've already passed. Example: Once in position (0,1), you cannot go to the initial point (0,0)
- Your battery level cannot (for any reason) go under 2
- You can assume there will always be a beginning and an end
- You can take the 1-dimensional arrays as multidimensional if you need to
[1,2,3] == [[1,2,3]]
- There can be multiple correct (minimal needed charge) paths
- Your goal is to only output the lowest initial battery level needed, not the route
- You can only go vertically and horizontally (not diagonally)
Test Cases
[0, 0] => 2
[0, 1, 0] => 2
[0, -1, 0] => 3
[0, 15, -20, 5, 0] => 7
[[0, -3],[-5, 0]] => 5
[[0, -5, -9, 5], [-3, 5, 2, -2], [2, -4, -4, 0]] => 5
[[0, -1, 1, -1], [-1, -1, -1, -1], [-1, 1, -1, -1], [1, 1, -1, 0]] => 4
I forgot the day of the challenge. Sandbox post
– Luis felipe De jesus Munoz – 2019-02-15T15:05:08.237To anybody remembering: The challenge "The Hungry Moose" never made it out of the sandbox, so this is no dupe.
– Black Owl Kai – 2019-02-15T15:20:56.437@BlackOwlKai I think both challenges are different – Luis felipe De jesus Munoz – 2019-02-15T15:43:47.003
1Will the optimal path ever require moving left or up? For example
[[0,1,-1],[-9,-9,1],[-9,1,-1],[-9,-1,-9],[-9,1,0]]
– Kamil Drakari – 2019-02-15T16:37:54.140@KamilDrakari Yes – Luis felipe De jesus Munoz – 2019-02-15T17:11:23.527
Are there any other squares equal to 0 besides start and end? None of the examples do, but there doesn't look to be a rule that excludes this. – dana – 2019-02-18T15:58:36.673
1@dana no, there are only 2
0s
placed one at the top-left corner and the other one at the bottom-right – Luis felipe De jesus Munoz – 2019-02-18T17:42:45.643