Please help me with solving this array problem (Min Steps in Infinite Grid)
#1✎ 2millieYou are in an infinite 2D grid where you can move in any of the 8 directions :
(x,y) to
(x+1, y),
(x - 1, y),
(x, y+1),
(x, y-1),
(x-1, y-1),
(x+1,y+1),
(x-1,y+1),
(x+1,y-1)
You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.
Example :
Input : [(0, 0), (1, 1), (1, 2)]
Output : 2
It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).
Link - https://www.interviewbit.com/problems/min-steps-in-infinite-grid/
Posted
#2✎ 168NathanielSpring 2017 Contest WinnerI won the SmileBASIC Source Spring 2017 Contest!Programming ContestStaff Pick"Your program is one of our favorites!" - StaffAchievementsFinal(?) Contest WinnerI won the (possibly) final SmileBASIC Source Contest! October 2018Programming ContestHere's a simple solution:
ACLS
'SETUP
RESTORE @POINTS
READ NUMBER
DIM POINTS_XY[NUMBER*2]
FOR I=0 TO NUMBER*2-1
READ POINTS_XY[I]
NEXT
'OUTPUT
?MIN_STEPS(POINTS_XY)
'FUNCTION
DEF MIN_STEPS(ARRAY_XY)
VAR I,STEPS,LENGTH=LEN(ARRAY_XY)/2-1
FOR I=0 TO LENGTH-1
VAR DIST_X=ABS(ARRAY_XY[I*2 ]-ARRAY_XY[I*2+2])
VAR DIST_Y=ABS(ARRAY_XY[I*2+1]-ARRAY_XY[I*2+3])
INC STEPS,MAX(DIST_X,DIST_Y)
NEXT
RETURN STEPS
END
'INPUT
@POINTS
DATA 3 'NUMBER OF POINTS
DATA 0,0
DATA 1,1
DATA 1,2
Posted
Edited
by Nathaniel
Here's a simple solution:
ACLS
'SETUP
RESTORE @POINTS
READ NUMBER
DIM POINTS_XY[NUMBER*2]
FOR I=0 TO NUMBER*2-1
READ POINTS_XY[I]
NEXT
'OUTPUT
?MIN_STEPS(POINTS_XY)
'FUNCTION
DEF MIN_STEPS(ARRAY_XY)
VAR I,STEPS,LENGTH=LEN(ARRAY_XY)/2-1
FOR I=0 TO LENGTH-1
VAR DIST_X=ABS(ARRAY_XY[I*2 ]-ARRAY_XY[I*2+2])
VAR DIST_X=ABS(ARRAY_XY[I*2+1]-ARRAY_XY[I*2+3])
INC STEPS,MAX(DIST_X,DIST_Y)
NEXT
RETURN STEPS
END
'INPUT
@POINTS
DATA 3 'NUMBER OF POINTS
DATA 0,0
DATA 1,1
DATA 1,2
Thank you :)
Posted
#4✎ 158712Me21Head AdminSecond YearMy account is over 2 years oldWebsiteSyntax HighlighterReceived for creating the code syntax highlighter on SBSNight PersonI like the quiet night and sleep late.Express YourselfI believe this should work:
DIM TEST[3,2]
COPY TEST,@POINTS
?STEPS(TEST)
@POINTS
DATA 0,0
DATA 1,1
DATA 1,2
DEF STEPS(POINTS[])
VAR SUM=0
VAR I
FOR I=1 TO LEN(POINTS)/2-1
INC SUM,MAX(ABS(POINTS[I,0]-POINTS[I-1,0]),ABS(POINTS[I,1]-POINTS[I-1,1]))
NEXT
RETURN SUM
END
EDIT: I didn't look at Nathaniel's answer until after I posted this, and it turns out he did basically the same thing.
Posted
Edited
by 12Me21