# Can you make your way through the Ulam spiral?

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.

• So do we just have to display whether we can make it, or de we also have to print the suggested path? Dec 13 '20 at 21:16
• @SunnyMoon the task doesn't require printing the path at any point. look at the tags - it's a decision problem. Dec 13 '20 at 21:17
• 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 Dec 13 '20 at 21:24
• @LuisMendo it's here just for validating that the answer is right - it's a soft bound Dec 13 '20 at 21:28
• 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 Dec 13 '20 at 22:44

# 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

• k is 2*max(|x|, |y|)
– att
Dec 14 '20 at 4:55
• @att I wouldn't have bet on it given that Math.max() is rather lengthy, but it does save a byte. :-) Thank you! Dec 14 '20 at 8:30
• +1: looks valid to me, nice answer! Dec 14 '20 at 13:58

# 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.