(inspired by Helka's response to my random pairing of "chess" and "Fibonacci" tags in chat)
The Fibonacci numbers are one of the more well-known sequences in mathematics, where each number is composed by adding the two previous numbers together. Below is a definition of the zero-indexed sequence:
f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)
This results in the sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, ... (OEIS link). In this challenge, we'll be focusing on only the strictly-positive values (so
1, 1, 2, 3, ...), and you can choose zero-indexing or one-indexing, but please state which in your submission.
The Fibonacci numbers can be used for a tiling of the plane, by using squares that are successive
f(n) in size, and aligning their edges together. The tiling is done in a counter-clockwise fashion, by placing squares in the pattern "right-up-left-down" from the current square. An example of this partial tiling for
f(8)=21, with the starting square highlighted in blue, is as follows:
You can see the
f(1)=1 as the starting square (highlighted in blue), the
f(2)=1 square placed to the right of it, the
f(3)=2 square placed up from there, the
f(4)=3 square placed left and so on. The next square would be
f(9)=21+13=34 and would be placed to the bottom. This is the partial tiling method we'll be using in this challenge.
In the game of chess, the most powerful piece is the queen because it can move any number of spaces horizontally, vertically, or diagonally. In the below board diagram, the squares with a black circle show where the queen can move:
We'll define the term coverage as
The percentage of squares that the queen can move to versus the total number of squares, given the queen's particular position on an empty board, and including the queen's own starting position.
For the example moves above, the queen's coverage is
28/64 = 43.75%. If the queen was in the upper-right
h8 square, the coverage would be
22/64 = 34.375%. If the queen was in
e7, the coverage would be
24/64 = 37.5%.
We're going to use the Fibonacci tiling demonstrated above as our chess board for this challenge. You'll be given two positive integers as input,
nrepresents how large the tiling is. The example tiling above, with the
21square on the left, is a board of size
n = 8since
f(8) = 21(when zero-indexed).
xrepresents which of the Fibonacci squares is used for the queen(s) placement, for calculating the coverage. The queens are placed one-at-a-time on each square in that particular Fibonacci square tile, and the total coverage is the summation of the individual (unique) coverage.
For example, here is an image of
n = 8 (the same tiling as above) and
x = 4 (corresponding to the
f(4) = 3 square, shaded blue). By placing a queen one-at-a-time into each of those nine blue squares, the queens can (combined) cover every square that's shaded orange. The total coverage in this example is therefore
309/714 = 43.28%.
Quite obviously, any time that
n = x, the coverage is going to be
100% (for example, with
x=8, you can see that every square on the entire board is going to be covered at least once). Conversely, with a suitably large
x=2, the coverage is going to approach (but never reach)
0% (for example, with
x=1, the coverage is a paltry
88/714 = 12.32%).
Given two such input numbers, you must output the coverage percentage, accurate to two decimal places. Please specify how your code handles rounding.
- The input and output can be given in any convenient format, but must be accurate to two decimal places. Please specify how your code handles rounding.
- Assume no other pieces are on the board or otherwise interfere with the moves.
- Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
- If possible, please include a link to an online testing environment so other people can try out your code!
- Standard loopholes are forbidden.
- This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
n = 8, x = 4 43.28 n = 8, x = 8 100 or 100.00 n = 8, x = 1 12.32 n = 4, x = 1 66.67 n = 4, x = 2 60 or 60.00 n = 5, x = 3 75 or 75.00 n = 5, x = 1 47.5 or 47.50