? Please help me with solving this array problem (Min Steps in Infinite Grid) (Page 1) ● SmileBASIC Source Forums

Sign In

Register
*Usernames are case-sensitive
Forgot my password

Please help me with solving this array problem (Min Steps in Infinite Grid)

  • #1 ✎ 2 millie You 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 ✎ 168 Nathaniel Spring 2017 Contest Winner I won the SmileBASIC Source Spring 2017 Contest! Programming Contest Staff Pick "Your program is one of our favorites!" - Staff Achievements Final(?) Contest Winner I won the (possibly) final SmileBASIC Source Contest! October 2018 Programming Contest 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_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
  • #3 ✎ 2 millie
    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 ✎ 1580 12Me21 Head Admin Video Games I like to play video games! Hobbies First Year My account is over 1 year old Website Expert Programmer Programming no longer gives me any trouble. Come to me for help, if you like! Programming Strength I 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