25
\$\begingroup\$

The Cartesian plane can be tiled with increasingly large squares like so:

enter image description here

This tiling can be generated by starting with a square of side length 1, placed at the origin 0, 0, and then repeatedly adding a square to the side of the resulting rectangle anticlockwise of the previous square, starting on the right. The first few iterations look like this:

enter image description here enter image description here enter image description here enter image description here enter image description here

Your challenge is to, given a coordinate (x, y) on the plane, return the side length of the square covering that coordinate. For example:

enter image description here

From the construction above, a square with side length 1 is placed at (0, 0), so (0, 0) should result in 1. However, the tile one square above and to the right at (1, 1) is covered by a square of side length 2, so (1, 1) should result in 2. Similarly, the coordinate 2 tiles to the left of the origin, (-2, 0), should result in 3, and (3, -2) should result in 8.

You may take x and y swapped and/or negated - equivalently, you may index into any rotation or reflection of the tiling. This is , shortest wins!

Testcases

These use the coordinate system from above, using x, y -> size.

0, 0 -> 1
1, 0 -> 1
1, 1 -> 2
-3, 1 -> 3
-3, -1 -> 5
3, -2 -> 8
6, 15 -> 13
-4, -5 -> 21
-4, -6 -> 34
145, 214 -> 610
Improve this question
\$\endgroup\$
0

8 Answers 8

Reset to default
13
\$\begingroup\$

JavaScript (Node.js), 51 bytes by Weird Glyphs

f=(x,y,u=1,r=2)=>(x|y)>-1&x<r&y<u?u:f(y,r+~x,r,r+u)

Try it online!

JavaScript (Node.js), 52 bytes

f=(x,y,u=0,r=1)=>x<0|x>r|y<0|y>u?f(y,r-x,r,u-~r):u+1

Try it online!

by shifting the rect

JavaScript (Node.js), 69 bytes

f=(x,y,l=0,u=0,r=1,d=0)=>x<l|x>r|y<d|y>u?f(y,-x,d,-l,u-~r-l,-r):u-d+1

Try it online!

If in the rect then output its height, otherwise rotate by 90 and extend to right

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ 51 bytes \$\endgroup\$ Commented Jan 30, 2025 at 11:35
4
\$\begingroup\$

JavaScript (ES6), 78 bytes

Expects (x,y) with y negated.

f=(x,y,a=d=0,b=1)=>x<0|x/b|y<0|y/b?f(x+(A=[-b,a,a+=b,0])[d++],y+A[d&=3],b,a):b

Try it online!

Method

Given:

  • the previous Fibonacci value \$a\$
  • the current Fibonacci value \$b\$
  • a direction \$d\$ initialized to \$0\$ and incremented modulo \$4\$ after each iteration

the displacement vector to get the top-left corner of the next Fibonacci tile is:

  • if \$d=0\$: \$(+b,-a)\$
  • if \$d=1\$: \$(-a,-a-b)\$
  • if \$d=2\$: \$(-a-b,0)\$
  • if \$d=3\$: \$(0,+b)\$

Instead of adding these vectors to the current position \$(X,Y)\$ and testing if we have \$X\le x<X+b\$ and \$Y\le y<Y+b\$, we subtract them from the target position \$(x,y)\$ until we have \$0\le x<b\$ and \$0\le y<b\$.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python, 53 bytes

f=lambda y,x,H=1,W=2:H*(H>y>-1<x<W)or f(x,~y+H,W,W+H)

Attempt This Online!

Pretty straightforward recursion.

Looks like @Arnauld and @l4m2 did pretty much the same several hours before me. So this should count as a port of theirs.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 55 bytes

Ｆ²⊞υＮ≔Ｅ⁴‹ι²θＷ⊙Ｅ⁴Σ✂θκＬθ⁴⎇‹λ²¬‹§υλꋧυλ±κ⊞θΣ…⮌Ｅθ⁺κ⁼³λ²Ｉ⌈θ

Try it online! Link is to verbose version of code. Explanation: Probably not the best algorithm, but at least the number of bytes is relevant.

Ｆ²⊞υＮ

Input the target coordinates.

≔Ｅ⁴‹ι²θ

Start with a rectangle whose right, top, left and bottom are 1, 1, 0, 0 respectively, however the rectangle's coordinates are actually given by the cyclic sums of the list values so that rather than actually modifying the coordinates in place the additional values are simply appended to the list, plus the left and bottom coordinates need to be negated.

Ｗ⊙Ｅ⁴Σ✂θκＬθ⁴⎇‹λ²¬‹§υλꋧυλ±κ

Repeat until the target coordinates lie inside the rectangle.

⊞θΣ…⮌Ｅθ⁺κ⁼³λ²

Push the next Fibonacci number to the rectangle.

Ｉ⌈θ

Output the highest used Fibonacci number.

46 44 bytes for a version that rotates the input point rather than the rectangle:

Ｆ²⊞υＮ≔Ｅ²ιθＷ⊙υ÷κ⌈θ«≔⟦⊖⁻⌈θ⊟υ⁻⊟υ⌈θ⟧υ⊞θΣ…⮌θ²»Ｉ⌈θ

Try it online! Link is to verbose version of code. Takes x and -y as inputs. Explanation:

Ｆ²⊞υＮ

Input the target coordinates.

≔Ｅ²ιθ

Start with the first two terms of the Fibonacci sequence.

Ｗ⊙υ÷κ⌈θ«

Repeat until the point lies in the current square.

≔⟦⊖⁻⌈θ⊟υ⁻⊟υ⌈θ⟧υ

Rotate the entire diagram so that the next square arrives at the origin. Note that there's an extra left offset to allow for the fact that the coverage depends on the rotation of the diagram, so for example after two rotations the 2 square actually ends up covering -1, -1 to 1, 1 so that points originally between 0, 1 and 1, 2 end up between 1, 1 and 0, 0, allowing the loop test to work correctly.

⊞θΣ…⮌θ²

Get the size of the next square.

»Ｉ⌈θ

Output the size of the found square.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 22 bytes

ḢṚÄß’_¥;⁹.ịʋɗḶi"Ạɗ?
Jç

A monadic Link that accepts a pair of integers and yields the tile value at that location (the tiling from the example has been rotated a quarter turn anti-clockwise).

Try it online! Or see it produce a tiling (rotated to match the question's examples).

How?

Note: I think ß is not being counted as a chainlink when grouping (i.e. I would have thought the ʋɗ should be ʋʋ).

ḢṚÄß’_¥;⁹.ịʋɗḶi"Ạɗ? - Recursive Helper Link: [T, NextT]; [X, Y]
                  ? - if...
                 ɗ  - ...condition: last three links as a dyad - f([T, NextT], [-Y, X]):
             Ḷ      -      lowered range -> TileRange = [[0..T-1], [0..NextT-1]]
               "    -      zip with:
              i     -      index of {CoordinatePart} in {TileRange} or 0 if not found
                Ạ   -      all truthy?
Ḣ                   - ...then: Head {[T, NextT]} -> T
            ɗ       - ...else: last three(four?!) links as a dyad - f([T, NextT], [X, Y]):
 Ṛ                  -      reverse {[T, NextT]} -> [NextT, T]
  Ä                 -      cumulative sums {that} -> [NextT, NextT + T]
           ʋ        -      last four links as a dyad - f([T, NextT], [X, Y]):
      ¥             -        last two links as a dyad - f([T, NextT], [X, Y]):
    ’               -          decrement {[T, NextT]} -> [T - 1, NextT - 1]
     _              -          subtract {[X, Y]} -> [T - 1 - X, NextT - 1 - Y]
       ;⁹           -        {that} concatenate {[X, Y]} -> -> [T - 1 - X, NextT - 1 - Y, X, Y]
         .          -        literal = 0.5
          ị         -        {0.5} index into {that} -> [Y, T - 1 - X]
   ß                -      call this link again - f([NextT, NextT + T], [Y, T - 1 - X])

Jç - Main Link: [-Y, X]:
J  - indices -> [1, 2]
 ç - call halper Link as a dyad - f([1, 2], [-Y, X])
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 100 bytes

def f(x,y):
 a=c=0;b=1;s=[1]*4
 while(-s[2]<x<s[0]>-s[3]<y<s[1])^1:a,b=b,a+b;s[c%4]+=b;c+=1
 print b

Try it online!

Alternative:

Python 3.8 (pre-release), 100 bytes

def f(x,y):
 a=c=0;s=[b:=1]*4
 while(-s[2]<x<s[0]>-s[3]<y<s[1])^1:a,b=b,a+b;s[c%4]+=b;c+=1
 return b

Try it online!

If returning a generator is allowed:

Python 3.8 (pre-release), 99 bytes

def f(x,y):
 a=c=0;s=[b:=1]*4
 while(-s[2]<x<s[0]>-s[3]<y<s[1])^1:a,b=b,a+b;s[c%4]+=b;c+=1
 yield b

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 167 bytes

m=(`mod`4)
t(d:_:z)|n<-1+z!!(m$d+1)+z!!(m$d+3)=m(d+1):n:[x+last(0:[n|i==d])|(i,x)<-zip[0..]z]
f(x,y)=until(\[_,_,a,b,c,d]->and[-c<=x,x<=a,-d<=y,y<=b])t[0,1,0,0,0,0]!!1

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 54 51 bytes

f=->x,y,u=1,r=2{x<r&&y<u&&x|y>-1?u:f[y,r+~x,r,r+u]}

Try it online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.