7
\$\begingroup\$

The obstacle course

You are currently stuck in some kind of course and you have to escape. However, if you do not choose the fastest way then the exit will close in front of you. Your challenge is to find the fastest route in an obstacle course.

Input

Your input consists of a list with lists in it, a 2D grid containing only positive integers. For example, it might look as follows:

eg. [[0,1,2],[0,3,5],[2,6,1]] which visually looks like:

0  1  2
0  3  5
2  6  1

Each number represents the time that is needed to pass the location. For example, (1,2) takes 6 seconds to pass. Your code can take for granted that no conversions of the input have to be made to make it a list that works with your language.

Computing

Your starting position will also be (1,1), which in the input above is 2. You have to include those seconds in your final answer. From your starting position your goal is to work to (xmax, ymax), which in the input above is (3,3). You have to find the fastest route to get there, so the sum of your numbers must be minimal.

Note for example understanding: the grid is from 1 and on-wards, (0,0) is not the starting position. (1,1) is bottom left and (3,3) is top right in this example.

Output

Your code must output the minimal time it takes to reach the top right corner from the bottom left corner. In the input above this is 2 + 0 + 0 + 1 + 2 = 5 seconds. Your code should output nothing else than a whole integer.

Additional specifications

  • Your may not move diagonally; only left, right, down, up
  • This is , shortest code in bytes wins
  • The grid wont always be square, but the start will always be connected to the end
  • minimum input is a 1x1 grid
  • grid will only contain positive integers

To sum up the given example:

Input: [[0,1,2],[0,3,5],[2,6,1]] // any format you like
Output: 5

How:
2 + 0 + 0 + 1 + 2 = 5
\$\endgroup\$
  • \$\begingroup\$ Will the 2D grid be square? \$\endgroup\$ – mınxomaτ Oct 26 '15 at 20:22
  • \$\begingroup\$ What's the minimum input size? 1x1? \$\endgroup\$ – mınxomaτ Oct 26 '15 at 20:25
  • \$\begingroup\$ If the bottom left corner is (1,1), wouldn't the top right corner be (3,3) in your example? \$\endgroup\$ – Dennis Oct 26 '15 at 20:26
  • \$\begingroup\$ Edited. I wrote the question from mobile so the grid was weird. \$\endgroup\$ – Thomas W Oct 26 '15 at 20:27
  • \$\begingroup\$ Are all times nonnnegative? \$\endgroup\$ – flawr Oct 26 '15 at 20:38
3
\$\begingroup\$

Matlab, 207 199 bytes

Given the matrix with all the times A, the idea is using a new B matrix that has every entry set to Inf except the initial entry. Then we generate a new matrix C where we apply following formula to each pair of coordinates (i,j)

 C(i,j) = min( B(i,j), B(i-1,j)+A(i,j), B(i+1,j)+A(i,j), B(i,j-1)+A(i,j), B(i,j+1)+A(i,j) );

This means: either B(i,j) already represents the minimum time to get to (i,j) or we can get to B(i,j) quicker via one of the neighbours.

Then we replace B with C and repeat this step enough times (until nothing changes anymore), and #rows + #columns is an upper bound for this.

After that, we just need to print the top right element (or in matrix-speak: bottom right) element.

This idea is basically stolen from the Floyd-Warshall algorithm.

Note that for doing this, I need also to consider some technical details, namely that I should not access elements outside the matrix, that is why I need the zero padding and shift of coordinates.

a=input('');
[r,c]=size(a);
A=padarray(a,[1,1]);
C=A+Inf;C(2,2)=A(2,2);
for i=1:r+c
    B=C;
    for i=2:r+1;
        for j=2:c+1;
            v=[-1,1];
            C(i,j)=min([B(i,j)-A(i,j),B(i+v,j)',B(i,j+v)]+A(i,j));
        end;
    end;
end;
disp(A(r+1,c+1))

Input: We need to reverse the order of the rows due to indexing, so the example given would be

[[2,6,1];[0,3,5];[0,1,2]]

or alternatively

[2,6,1;0,3,5;0,1,2]

So for this example we get following intermediate steps that will show the progression quite nicely (I removed the padding):

 2     Inf   Inf
 Inf   Inf   Inf
 Inf   Inf   Inf

 2     8     Inf
 2     Inf   Inf
 Inf   Inf   Inf

 2     8     9
 2     5     Inf
 2     Inf   Inf

 2     8     9
 2     5    10
 2     3    Inf

 2     8     9
 2     5    10
 2     3     5

PS: I love challenges like this one=)

\$\endgroup\$
  • \$\begingroup\$ Glad you liked it. Not glad to see that this is the only answer :( \$\endgroup\$ – Thomas W Oct 28 '15 at 20:25
  • \$\begingroup\$ Perhaps you might want to first post it in the sandbox or/and discuss it with some guys in the chat. I think the challenge was great, but perhaps people just stopped by once and saw that there were still some things to figure out. But sometimes challenges you put a lot of effort in still do not get answered a lot. I just recently had one of those here. \$\endgroup\$ – flawr Oct 28 '15 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.