| Bytes | Lang | Time | Link |
|---|---|---|---|
| 059 | Dyalog APL | 250804T224405Z | Aaron |
| 018 | Uiua | 250721T030636Z | nyxbird |
| 280 | Python3 | 250720T174220Z | Ajax1234 |
| 038 | Jelly | 190401T230139Z | Jonathan |
| 191 | TSQL query | 190328T155837Z | t-clause |
| 059 | Jelly | 190328T132056Z | Nick Ken |
| 113 | JavaScript ES7 | 190328T020921Z | Arnauld |
| 220 | Python 2 | 190327T220350Z | Chas Bro |
Dyalog APL, ⎕IO←0, 85 63 59 chars
{⊃⍺≥((⊃∘⍸c∊⊂)¨1↓⍺)⌷⌊.+⍣≡⍨∘.(≢×(⍵⌷⍨⊢)+101×1≠(+/|⍤-))⍨c←,⍳⍴⍵}
Expects the speed, start coords, and end coords as a triplet on the left and the terrain map (matrix) on the right with unreachables as 101.
Explanation:
{⊃⍺≥((⊃∘⍸c∊⊂)¨1↓⍺)⌷⌊.+⍣≡⍨∘.(≢×(⍵⌷⍨⊢)+101×1≠(+/|⍤-))⍨c←,⍳⍴⍵}
c←,⍳⍴⍵ Ravel the indices of its rank, store in c for later; i.e. a 2x3 matrix would give (0 0) (0 1) (0 2) (1 0) (1 1) (1 2)
∘.( )⍨ Apply to both sides of this outer product to make a matrix of distances between each node
101×1≠(+/|⍤-) Find the absolute difference of coords and ensure it's 1 or multiply by 101 (to mean unreachable)
(⍵⌷⍨⊢)+ Add that to the corresponding place from the original input
≢× Zero out the whole thing if the left and right argument match in this outer product
⌊.+ Apply a minimum-sum inner product
⍣≡ until the results converge
⍨ with the right arg duplicated for to the left for the first run
( )⌷ Select from that final distances matrix
1↓⍺ the second and third left arguments (start and end coords)
( )¨ mapped to the saved off coordinates list
⊃∘⍸c∊⊂ by finding the index of where this coordinate appears in the list of saved coordinates
⊃⍺≥ And finally check if my original speed is greater than the returned distance
Uiua, 18 bytes
≥◌path(⤚𝄐⬚∞⊡⧋+A₂)≍
Takes inputs as start end grid speed
Try it!
path( # find the cheapest path:
⧋+A₂ # by choosing neighbors
⤚𝄐⬚∞⊡ # and picking from the grid (oob->infinity)
)≍ # ending at the given point
≥◌ # is the speed ≥ the cost?
Python3, 280 bytes
E=enumerate
def f(b,s,e,m):
d={(x,y):int([0,v][v!='X'])for x,r in E(b)for y,v in E(r)}
q=[(*s,m,[s])]
for x,y,m,p in q:
if(x,y)==e:
if m>=0:return 1
continue
q+=[(*V,m-d[V],p+[V])for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]if d.get(V:=(x+X,y+Y))and V not in p and m-d[V]>=0]
Jelly, 38 bytes
ạƝṢ€Ḅ’¬Ạ
ŒṪ’ḟŒPŒ!€ẎW€j¥@€ÇƇḊ€‘œị⁸§Ṃ’<⁵
An extremely inefficient full program accepting the terrain (with unvisitables as 101) then the start and end co-ordinates then the speed.
Try it online! (not much point trying most of the test cases!)
How?
Creates a list of all permutations of each of the power-set of "all terrain locations except the start & end", surrounds each of these with the start & end, filters to those which make only orthogonal moves of distance one, drops the start from each, indexes back into the terrain, sums each, takes the minimum, subtracts one and tests that this is less than the speed.
TSQL query, 205 191 bytes
Input is a table variable @t
@x=start xpos, @y=start ypos @i=end xpos , @j=end ypos @ =speed
DECLARE @t table(x int,y int,v int)
INSERT @t
values
(0,0,1),(0,1,1),(0,2,2),(0,3,1),(0,4,null),
(1,0,1),(1,1,2),(1,2,2),(1,3,1),(1,4,1),
(2,0,2),(2,1,1),(2,2,1),(2,3,2),(2,4,1),
(3,0,null),(2,1,null),(2,2,null),(2,3,1),(2,4,2)
DECLARE @x INT=2,@y INT=3,@i INT=0,@j INT=1,@ INT=5;
WITH C as(SELECT @y f,@x r,@ s
UNION ALL
SELECT f+a,r+b,s-v FROM C
JOIN(values(1,0),(0,1),(-1,0),(0,-1))x(a,b)ON
s>0JOIN @t
ON f+a=x and r+b=y)SELECT
max(iif(S>=0and f=@j and r=@i,1,0))FROM c
Try it online ungolfed version
Jelly, 59 bytes
+2¦µ_2ịæ.ؽœị$Ʋ+5ịƲ$4¦01Ñḣ3Ḋ⁼/Ɗ?ḣ2=/ẸƊoF<0ẸƊƊ?
çⱮØ.,U$;N$¤Ẹ
Not terribly fast; tries all paths until the speed units are exhausted, even retracing its steps. However, this avoids the need to check whether spaces are visited. Input is provided as [nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major
Explanation
Helper link
+2¦ | add the right argument to the second item in the left argument (current location)
µ | start a new monadic chain with the modified left argument
4¦ | for the fourth item (speed)...
_ | subtract...
ịƲ$ | the item located at...
2ịæ.ؽœị$Ʋ | the dot product of the current position and (number of columns,
| right-padded with 1)
+5 | plus five
? | Now, if...
Ɗ | next three as a monad
ḣ2=/ẸƊ | either current row or current column are equal to nrows/ncolumns respectively
o | or
F<0ẸƊ | any value is negative
0 | return zero
? | else if...
ḣ3Ḋ⁼/Ɗ | the second and third items (current and end pos) are equal
1 | return 1
Ñ | else pass the current list back to the main link
Main link
ç | call the helper link with the current list...
Ɱ | and each of
Ø.,U$;N$¤ | [0,1],[1,0],[0,-1],[-1,0]
Ẹ | Check if any are true
JavaScript (ES7), 116 113 bytes
Takes input as (matrix)([endRow, endCol])(speed, startRow, startCol). Expects large values for unreachable squares. Returns \$0\$ or \$1\$.
m=>e=>o=g=(s,y,x)=>m.map((r,Y)=>r.map((v,X)=>r[s<v|(x-X)**2+(y-Y)**2-1||g(s-v,Y,X,r[X]=1/0),X]=v),o|=y+[,x]==e)|o
Commented
m => // m[] = matrix
e => // e[] = target coordinates
o = // o = success flag, initialized to a non-numeric value
g = ( // g = recursive depth-first search function taking:
s, // s = speed
y, x // y, x = starting coordinates
) => //
m.map((r, Y) => // for each row r[] at position Y in m[]:
r.map((v, X) => // for each value v at position X in r[]:
r[ // this statement ultimately updates r[X]:
s < v | // abort if s is less than v
(x - X) ** 2 + // or the quadrance between (x, y)
(y - Y) ** 2 - 1 // and (X, Y) is not equal to 1
|| g( // otherwise, do a recursive call to g:
s - v, // subtract v from s
Y, X, // pass (Y, X) as the new coordinates
r[X] = 1 / 0 // temporarily make this cell unreachable
), // end of recursive call
X // restore r[X] ...
] = v // ... to its original value
), // end of inner map()
o |= y + [, x] == e // set the flag o if (y + ',' + x) matches (e + '')
) | o // end of outer map(); return o
Python 2, 220 bytes
def f(m,a,w,h,r,c,R,C):
T=[w*[999]for _ in' '*h];T[r][c]=0;P=[(r,c)];j,k=1,0
for u,v in P:exec"U,V=u+j,v+k;j,k=-k,j\nif h>U>-1<V<w:q=T[U][V];T[U][V]=min(T[u][v]+m[U][V],q);P+=[(U,V)]*(q>T[U][V])\n"*4
return a>=T[R][C]
Takes an array m of integers, with 'X' as a larger-than-100 value;, a speed a, m having width w and height h; and returns whteher we can start at the zero-indexed row/column cell (r,c) and get to the final cell (R,C).
The algorithm is a modified flood-fill. Slightly ungolfed code:
def f(m,a,w,h,r,c,R,C):
T = [w*[999]for _ in ' '*h] # make an array same size as m, with all
# values 999, whose values will represent
# the cost of getting to each cell.
T[r][c] = 0 # set the starting location to a cost of 0
P = [(r,c)] # initialize a set of cells whose neighbors'
# cost might need to be be updated
j,k = 1,0 # and also j,k which will take on values:
# (1,0), (0,1), (-1,0), (0,1), used to
# probe orthogonal neighbors
for u,v in P: # scan the cells in P
for _ in '1234': # look at each of 4 orthogonal positions
U,V = u+j,v+k # U and V get the indexes of a neighbor
# of the current cell.
j,k = -k,j # this 'rotates' the j,k pairing.
if h>U>-1<V<w: # if the coordinates are in bounds...
q = T[U][V] # save the current 'cost' of getting to cell (U,V)
# see if we can reduce that cost, which is calculated
# by taking the cost of the currently scanned cell
# + the value from m for the neighbor cell.
T[U][V] = min(T[u][v]+m[U][V] ,q)
# if we can reduce the cost, add the neighbor
# to P because **it's** neighbors might,
# in turn, need updating.
P += [(U,V)]*(q>T[U][V])
return a>=T[R][C] # return if speed is enough for the cost.