18
2
(inspired by Helka's response to my random pairing of "chess" and "Fibonacci" tags in chat)
Fibonacci
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.
The Queens
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%
.
The Challenge
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, n
and x
:
- The
n
represents how large the tiling is. The example tiling above, with the21
square on the left, is a board of sizen = 8
sincef(8) = 21
(when zero-indexed). - The
x
represents 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 n=8
and 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 n
and x=1
or x=2
, the coverage is going to approach (but never reach) 0%
(for example, with n=8
and 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.
Rules
- 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.
Examples
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
My profile picture is semi-relevant – Stephen – 2017-07-24T15:09:13.347
"When Fibonacci met the Queens"? Or "Fibonacci meets the Queens"? – Jonathan Allan – 2017-07-24T15:40:09.527
2"To escape closure, a fibonacci challenge has to be as good as the previous 2 fibonacci challenges put together." Seems good enough. – programmer5000 – 2017-07-24T15:42:40.463
@JonathanAllan The title is correct as-is. It's present indicative tense as in "this is what happens when X happens." Compare "When Henry meets Sally for lunch, they always eat hamburgers." – AdmBorkBork – 2017-07-24T15:51:39.667
Ah, you mean "When Fibonacci meets the Queens..."! – Jonathan Allan – 2017-07-24T15:54:08.240
@JonathanAllan Yes, but SE won't let me have trailing ellipses in the title. – AdmBorkBork – 2017-07-24T16:00:49.697
@AdmBorkBork I get
309/714
forn=8, x=4
. I've double checked it a couple of times, and believe I'm right based on my understanding of the rules. Can you double check if your number is right, or let me know if I misunderstood something? – Brian J – 2017-07-24T17:18:39.477Note to self: name drop Helka, next time I write a challenge... – caird coinheringaahing – 2017-07-24T17:21:14.757
@BrianJ Yep. A typo on my notes when I was going through the calculation manually resulted in the mistake spreading.
309
is correct, and I've updated the question. Thanks! – AdmBorkBork – 2017-07-24T17:52:24.640@AdmBorkBork Also,
n=8,x=1
I get88/714
– Brian J – 2017-07-24T17:57:11.727@BrianJ Thanks - that was a mistaken holdover from the sandbox; initially, I had defined coverage to not include the starting position but later changed that and apparently never updated the
87
to an88
. Thanks. – AdmBorkBork – 2017-07-24T18:02:08.357