13
\$\begingroup\$

You will be given a point (x,y) relative to the center of the Ulam spiral (the center being the point which represents one), and length z. The task is to check whether there exists a path from (0,0) to (x,y) of length z, assuming prime numbers are obstacles and each turn in path has an angle of 90 degrees. Path may not overlap with itself. (x,y) may not be a prime.

Examples of valid paths:

XXXX
   XX
    X
    X
    XXXXXXXX
    XXXXXX
XXXXX
XXXXXXXXXXXXXX
             X
             X
             X
             XXXXXXX

Examples of invalid paths:

XXXXXXXXXXXX
            XXXXX
XXXXX   XXXXXX
     X X
      X
XXX
   X
  X
   XXXXXXXXXXX
       X
       X
XXXXXXX!XXX
       X  X
       XXXX

The path above overlaps in a place marked with !.

For the record, this is a fragment of a Ulam spiral with 1 (0,0) marked:

............#...#.......#...#
.#...#...........#.#.....#...
#.#.....#.#.....#.....#......
.........#...........#...#...
....#...#.......#.....#......
...#.........#...#.#...#.#.#.
......#.....#.........#.#...#
.#.....#...#.#...............
..............#.#.....#...#..
...#...#.#...#.......#...#.#.
..............#.#...#........
.....#...#.#.....#.#.#.....#.
#.#.#.#.#.#.#...#.......#....
.............#.#.#...........
........#...#.1##.#.#.#...#.#
.#.......#.#.#...............
..........#...#..............
...#.#...#.#...#...#.#...#...
..#...#...#.....#.....#.#...#
...........#...........#.....
......#.#.....#...#...#......
...#...#...........#.......#.
....#.....#...#.#............
.........#.#...#.....#...#...
#.#.#.........#.#.....#.....#
.#...#...........#.#.........
#.#.....#.....#...#.#........
.......#.........#.......#...
........#.#...#.#.........#..

I/O examples

Input: (5, -1), 7 - true
Suggested path:
1##.#.#.#...#.#
XXXXXX.........
#..............

Input: (3, 0), 6 - true
Suggested path:
.#.#.#...........
#.1##X#.#.#...#.#
.#XXXX...........

Input: (-2, -1), 18 - true
Suggested path:
...#...#.#...#.......#...#.#.
..............#.#...#........
.....#...#.#.....#.#.#.....#.
#.#.#.#.#.#.#...#.......#....
.............#.#.#...........
........#...#.1##.#.#.#...#.#
.#.......#.#X#XX............
..........#.XX#XX............
...#.#...#.#.XX#XX.#.#...#...
..#...#...#...XX#X....#.#...#
...........#...XXX.....#.....

Input: (2, 1), 6 - false
Input: (-5, 2), 20 - true
Input: (-1, 0), 5 - false

Additional considerations

abs(x) <= 20 and abs(y) <= 20 cases have to be resolved within the TIO time limit (soft bound; 60s) to verify validity of the answers. The answers have to (theoretically and ideally) work on any reasonable input.

\$\endgroup\$
9
  • \$\begingroup\$ So do we just have to display whether we can make it, or de we also have to print the suggested path? \$\endgroup\$
    – SunnyMoon
    Dec 13 '20 at 21:16
  • 1
    \$\begingroup\$ @SunnyMoon the task doesn't require printing the path at any point. look at the tags - it's a decision problem. \$\endgroup\$ Dec 13 '20 at 21:17
  • \$\begingroup\$ The time limit makes the challenge less interesting, in my opinion. It shifts the focus away from golfing, and more into finding an efficient algorithm \$\endgroup\$
    – Luis Mendo
    Dec 13 '20 at 21:24
  • \$\begingroup\$ @LuisMendo it's here just for validating that the answer is right - it's a soft bound \$\endgroup\$ Dec 13 '20 at 21:28
  • 4
    \$\begingroup\$ Having coordinates with abs up to 20 means the required path length could be up to 40. So dumb brute force involves around 3^39 possible paths, which will exceed 60 seconds. I'm not saying you should remove that limit, but do note that the main part of the challenge becomes finding an efficient algorithm, rather than golfing the code \$\endgroup\$
    – Luis Mendo
    Dec 13 '20 at 22:44
7
\$\begingroup\$

JavaScript (ES6), 169 bytes

Saved 1 byte thanks to @att

Expects (z)(x,y). Returns false if there's a solution or true otherwise.

z=>F=(X,Y,i=z,k)=>--i?[-1,0,1,2].every(d=>(g=d=>n%--d?g(d):d==1)(n=(k=2*Math.max(x=X+d%2,-x,y=Y+~-d%2,-y))*k-~(-y<x?y-k-x:k+x-y))|F[k=[x,y]]||F(x,y,i,F[k]=1)|--F[k]):X|Y

This is fast enough for all existing test cases, but I guess it's likely to time out on some other ones.

Try it online!

Commented

NB: the spiral formula is similar to the one I used in my answer to Spiral neighbourhoods.

z =>                              // outer function taking z
F = (                             // main recursive function taking:
  X, Y,                           //   (X, Y) = current position
  i = z,                          //   i = move counter initialized to z
  k                               //   k = local variable whose initial value is ignored
) =>                              //
  --i ?                           // decrement i; if it's not equal to 0:
    [-1, 0, 1, 2].every(d =>      //   for each direction d:
      ( g = d => n % --d ? g(d)   //     g is a recursive primality test function
                         : d == 1 //     which is invoked ...
      )(                          //
        n =                       //     ... on the 1-indexed square ID n defined as:
          ( k = 2 * Math.max(     //       k² + (k + x - y) * s + 1
              x = X + d % 2, -x,  //       with:
              y = Y + ~-d % 2, -y //         x = X + dx
            )                     //         y = Y + dy
          ) * k -                 //         k = 2 * max(|x|,|y|) = 2 * max(x,-x,y,-y)
          ~(-y < x ? y - k - x    //         s = -1 if -y < x or 1 otherwise
                   : k + x - y)   //
      )                           //     abort if n is prime
      | F[k = [x, y]]             //     or (x, y) was already visited
      || F(x, y, i, F[k] = 1)     //     otherwise mark (x, y) as visited and do a
                                  //     recursive call with the new position
      | --F[k]                    //     clear the mark afterwards
    )                             //   end of every()
  :                               // else:
    X | Y                         //   falsy if and only if X = Y = 0
\$\endgroup\$
3
  • \$\begingroup\$ k is 2*max(|x|, |y|) \$\endgroup\$
    – att
    Dec 14 '20 at 4:55
  • \$\begingroup\$ @att I wouldn't have bet on it given that Math.max() is rather lengthy, but it does save a byte. :-) Thank you! \$\endgroup\$
    – Arnauld
    Dec 14 '20 at 8:30
  • \$\begingroup\$ +1: looks valid to me, nice answer! \$\endgroup\$ Dec 14 '20 at 13:58
2
\$\begingroup\$

Wolfram Language (Mathematica), 117 bytes

(a=0;Do[g@a=b;a-=I^⌈2√b⌉,{b,8#^2}];1!=##2&&!PrimeQ@g@#2&&If[#<2,0==#2,Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&@##)&

Try it online!

Input \$z\$ and a complex number \$x+iy\$.

1!=##2&&!PrimeQ@g@#2                            (* check if the current path is valid *)
&&If[#<2,0==#2                                  (* if the length is reached, check if the endpoint is the origin *)
    Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&        (*  otherwise, check if any child paths succeed *)

(a=0;Do[g@a=b;a-=I^⌈2√b⌉,{b,8#^2}]; % &@##)&    (* cache indices of a sufficiently large spiral first. *)

110 bytes

1!=##2&&!PrimeQ[b=1;0//.a_/;a!=#2:>a-I^⌈2√b++⌉;b]&&If[#<2,0==#2,Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&@##&

Try it online!

Same principle, but takes much longer without cached spiral indices.

\$\endgroup\$

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.