16
\$\begingroup\$

This is a challenge inspired by Chebyshev Rotation. I suggest looking at answers there to get inspiration for this challenge.

Given a point on the plane there is a unique square (a rectangle with equal sides) that is centered on the origin and intersects that point (interactive demo):

enter image description here

Given a point p and a distance d, return the point obtained by moving distance d from p, counter-clockwise (and clockwise for negative d), along the perimeter of the square centered on the origin that intersects p. Your answer must be accurate to at least 4 decimal digits.

Testcases:

(0, 0), 100 -> (0, 0)
(1, 1), 81.42 -> (-0.4200, 1.0000)
(42.234, 234.12), 2303.34 -> (-234.1200, 80.0940)
(-23, -39.234), -234.3 -> (39.2340, -21.8960)

The following test cases are from the original challenge by Martin Ender, and all are with d = 1:

(0, 0)       -> (0, 0)
(1, 0)       -> (1, 1)
(1, 1)       -> (0, 1)
(0, 1)       -> (-1, 1)
(-1, 1)      -> (-1, 0)
(-1, 0)      -> (-1, -1)
(-1, -1)     -> (0, -1)
(0, -1)      -> (1, -1)
(1, -1)      -> (1, 0)
(95, -12)    -> (95, -11)
(127, 127)   -> (126, 127)
(-2, 101)    -> (-3, 101)
(-65, 65)    -> (-65, 64)
(-127, 42)   -> (-127, 41)
(-9, -9)     -> (-8, -9)
(126, -127)  -> (127, -127)
(105, -105)  -> (105, -104)
\$\endgroup\$
5
  • \$\begingroup\$ Couldn't almost all of these be only slightly changed from the other challenge? This seems like a needless addition. \$\endgroup\$
    – ATaco
    Oct 17, 2016 at 2:41
  • 1
    \$\begingroup\$ @ATaco No, it's quite a bit more complicated. \$\endgroup\$
    – orlp
    Oct 17, 2016 at 2:45
  • \$\begingroup\$ Should the distance be calculated along the perimeter starting at p? \$\endgroup\$ Oct 17, 2016 at 16:33
  • \$\begingroup\$ @GáborFekete What else? \$\endgroup\$
    – orlp
    Oct 17, 2016 at 16:34
  • \$\begingroup\$ Yeah I see, the test cases imply this but it isn't stated explicitly. I thought at first that it would start at the positive intersection at the x-axis. \$\endgroup\$ Oct 17, 2016 at 16:39

2 Answers 2

4
\$\begingroup\$

Python 2, 363 335 296 266 262 258 256 233 Bytes

Woo, 130 bytes lost! Thanks to Neil for saving 4 bytes, Nathan Merrill for saving 2 bytes, and xnor for saving a ridiculous 23 bytes!

The general idea is this: We can reduce the distance traveled by taking it's the modulus of it against the perimeter of the square. The perimeter is defined as 8 times the largest of the two coordinates, since the point must rest on it. Then, after modulus is taken we are guaranteed to have no overlap. It also guarantees we only ever have to move counter-clockwise, since modulus gives a positive result.

From there, I simply use what we know from the given x and y-coordinates to figure out where we are: top, bottom, left, right, or in a corner, and determine the direction, which can be one of 0, 1, 2, 3:

0 --> we are on the 'top', moving 'left'
1 --> we are on the 'left', moving 'down'
2 --> we are on the 'bottom', moving 'right'
3 --> we are on the 'right', moving 'up'

After this, it is as simple as looping while we still have distance to travel, and based on the direction we subtract or add to the appropriate coordinate, and tell the loop which direction we are going next.

p,d=input()
x,y=p
s=max(x,y,-x,-y)
d=d%(s*8or 1)
r=[(y<s)*[2,[3,x>-s][x<s]][y>-s],[2*(y<0),3*(y<=0)][x>0]][y*y==x*x]
while s>0<d:f=1-2*(r<2);m=abs(f*s-p[r%2]);j=d>m;p[r%2]=[p[r%2]+f*d,f*s][j];r=-~r%4;d=(d-m)*j
print"%.4f "*2%tuple(p)

While quite long, it certainly works. Here's some example I/O:

[0, 0], 100 --> 0.0000 0.0000
[1, 1], 81.42 --> -0.4200 1.0000
[42.234, 234.12], 2303.34 --> -234.1200 80.0940
[-23, -39.234], -234.3 --> 39.2340 -21.8960

Try it online or run test cases.

\$\endgroup\$
4
  • \$\begingroup\$ Does s=max(x,y,-x,-y) work? \$\endgroup\$
    – Neil
    Oct 18, 2016 at 8:56
  • \$\begingroup\$ @Neil It does, thanks a bunch! \$\endgroup\$
    – Kade
    Oct 18, 2016 at 13:06
  • \$\begingroup\$ (s>0)*(d>0) is s>0<d. The output can be "%.4f "*2%tuple(p). if s:d=d%(8*s) can be d%(s*8or 1). (r+1) can be ~-r. 1*(x>-s) can just be (x>-s). abs(y)==abs(x) can be y*y==x*x \$\endgroup\$
    – xnor
    Oct 18, 2016 at 16:15
  • \$\begingroup\$ @xnor Wow, thanks! Only thins I changed are that (x>-s) didn't need the parenthesis, and ~-r decrements, so I used -~r. \$\endgroup\$
    – Kade
    Oct 18, 2016 at 16:51
3
\$\begingroup\$

JavaScript (ES6), 147 bytes

f=(x,y,d,s=Math.max(x,y,-x,-y),c=(d/8%s+s)%s*8,v=0,w=x+y>0?1:-1,b=(v?x:y)*w+c-s)=>c?b>0?f(v?s*w:x,v?y:s*w,d,s,b,!v,v?w:-w):[x+c*w*v,y+c*w*!v]:[x,y]

Explanation: Works by trying to add the direction vector while keeping within the bounds of the square. Any overshoot is recursively passed back with the direction rotated anticlockwise by 90°. The direction is actually encoded using a vertical flag v and a unit w so that the vectors (1, 0), (0, 1), (-1, 0) and (0, -1) are encoded with v of 0, 1, 0, 1 and w of 1, 1, -1, -1 respectively. The direction vector may not initially point in a suitable direction but it never points backwards so it will eventually rotate into a usable direction.

f=(x,y,d,                   Input parameters
 s=Math.max(x,y,-x,-y),     Calculate half the side of the square
 c=(d/8%s+s)%s*8,           Reduce the distance modulo the perimeter
 v=0,                       Initial vertical flag
 w=x+y>0?1:-1,              Initial direction
 b=(v?x:y)*w+c-s)=>         Will we overshoot the corner?
  c?b>0?f(v?s*w:x,v?y:s*w,  Advance to the next corner
          d,s,b,!v,v?w:-w): Rotate the direction
        [x+c*w*v,y+c*w*!v]: Advance the remaining amout
    [x,y]                   Nothing to do, zero input
\$\endgroup\$
2
  • \$\begingroup\$ This could be because my browser (Opera 40.0.2308.81), but it looks like it has a bit of rounding error for f(42.234, 234.12, 2303.34) -> [-234.12, 80.09399999999988] meaning it doesn't have 4 digit precision. Maybe adding some output formatting would fix this? Nice answer though! :) \$\endgroup\$
    – Kade
    Oct 19, 2016 at 18:32
  • \$\begingroup\$ @Shebang Technically output formatting would require rounding, and therefore introduce a potential rounding error. The numbers generated are the closest possible within the limits of floating-point arithmetic, which should not be expected to give exact results for arbitrary decimal representations. Stick to binary fractions if you want exact answers. \$\endgroup\$
    – Neil
    Oct 19, 2016 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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