<< problem 244 - Sliders | Numbers for which Euler's totient function ... - problem 248 >> |
Problem 247: Squares under a hyperbola
(see projecteuler.net/problem=247)
Consider the region constrained by 1 <= x and 0 <= y <= 1/x.
Let S_1 be the largest square that can fit under the curve.
Let S_2 be the largest square that fits in the remaining area, and so on.
Let the index of Sn be the pair (left, below) indicating the number of squares to the left of S_n and the number of squares below S_n.
The diagram shows some such squares labelled by number.
S_2 has one square to its left and none below, so the index of S_2 is (1,0).
It can be seen that the index of S_32 is (1,1) as is the index of S_50.
50 is the largest n for which the index of S_n is (1,1).
What is the largest n for which the index of S_n is (3,3)?
My Algorithm
Each square has a lower-left corner (x_0,y_0) and an upper-right corner (x_1,y_1) such that:
(1) x_1 - x_0 = y_1 - y_0 = side (length of each side of that square)
The hyperbola y = 1/x must go through the upper-right corner:
(2) y_1 = dfrac{1}{x_1}
Substituting (2) in (1):
(3) x_1 - x_0 = dfrac{1}{x_1} - y_0
And solve for x_1:
(4) x_1 - dfrac{1}{x_1} = x_0 - y_0
(5) dfrac{x^2_1 - 1}{x_1} = x_0 - y_0
(6) x^2_1 - 1 = x_1 (x_0 - y_0)
(7) 0 = x^2_1 - x_1 (x_0 - y_0) - 1
(8) 0 = x^2_1 + x_1 (y_0 - x_0) - 1
That's a quadratic equation with parameters:
(9) p = y_0 - x_0, q = -1
(10) x = -frac{p}{2} \pm sqrt{(frac{p}{2})^2 - q}
Omitting the second solution:
(11) x_1 = -frac{y_0 - x_0}{2} + sqrt{(frac{y_0 - x_0}{2})^2 + 1}
(12) x_1 = frac{x_0 - y_0}{2} + frac{1}{2} sqrt{(x_0 - y_0)^2 + 4}
(13) x_1 = 0.5 * (x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4})
Therefore the length of a side in (1) becomes:
(14) side = x_1 - x_0
(15) side = 0.5 * (x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4}) - x_0
And a bit simplified:
(16) side = 0.5 * (-x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4})
(17) side = 0.5 * (sqrt{(x_0 - y_0)^2 + 4} - x_0 - y_0)
That formula can be found in Square::setSideLength
.
My program starts with a single square whose lower-left corner (x, y) is at (1, 0).
All squares are stored in an std::set
named todo
which is sorted descendingly by the square's size
(the overloaded Square::operator<
returns the "wrong" result on purpose because an std::set
is sorted ascendingly by default).
I always pick the largest (→ the first) square from todo
and replace it by its upper and right neighbor.
Each square's position (x, y) and index (left, below) are tracked.
In order to have a square at index (3, 3) I have to have a square at (2, 3) or (3, 2).
Generalized, only if some squares are in todo
where left <= 3 and below <= 3 and left + below < 3+3 then it's
still possible to generate a square at index (3, 3).
candidates
counts how many squares fulfil that condition. If candidates
becomes zero then no more squares can be at (3,3).
The most recent will be printed.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "1 1" | ./247
Output:
Note: the original problem's input 3 3
cannot be entered
because just copying results is a soft skill reserved for idiots.
(this interactive test is still under development, computations will be aborted after one second)
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <set>
#include <cmath>
// a square is described by its lower left corner (x,y) and its index along x and y axis
struct Square
{
Square(double x_, double y_, unsigned int left_, unsigned int below_)
: x(x_), y(y_), left(left_), below(below_)
{
setSideLength();
}
// lower-left corner
double x;
double y;
// number of squares on the left side
unsigned int left;
// number of squares below
unsigned int below;
// length of a side
double side;
// note: sort in reverse, therefore return true if it's the larger (!) value
bool operator<(const Square& other) const
{
return side > other.side;
}
private:
// find length of edges of the largest square whose lower-left corner is at x,y
void setSideLength()
{
// see my explanations above
side = 0.5 * (sqrt((x - y) * (x - y) + 4) - x - y);
}
};
int main()
{
unsigned int indexLeft = 3;
unsigned int indexBelow = 3;
std::cin >> indexLeft >> indexBelow;
// square's number
unsigned int result = 0;
// create first square with lower-left corner at (1,0) and no other squares on its left or bottom side
std::set<Square> todo = { Square(1, 0, 0, 0) };
unsigned int candidates = 1; // => the first square is left of and below all other squares
while (candidates > 0)
{
result++;
// pick first (= largest) square
auto current = *(todo.begin());
// and remove it
todo.erase(todo.begin());
// create a new square on top of the current square
Square top (current.x, current.y + current.side,
current.left, current.below + 1);
todo.insert(top);
// and a square on the right side
Square right(current.x + current.side, current.y,
current.left + 1, current.below);
todo.insert(right);
// count how many squares could be on the left or bottom side of a square with index (3, 3)
if (top .left <= indexLeft && top .below <= indexBelow)
candidates++;
if (right .left <= indexLeft && right .below <= indexBelow)
candidates++;
if (current.left <= indexLeft && current.below <= indexBelow)
candidates--;
}
// show ID of last square with index (3, 3)
std::cout << result << std::endl;
return 0;
}
This solution contains 12 empty lines, 16 comments and 3 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.19 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 25 MByte.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
August 14, 2017 submitted solution
August 14, 2017 added comments
Difficulty
Project Euler ranks this problem at 65% (out of 100%).
Links
projecteuler.net/thread=247 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/LaurentMazare/ProjectEuler/blob/master/e247.py (written by Laurent Mazare)
Python github.com/Meng-Gen/ProjectEuler/blob/master/247.py (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/247.cpp (written by Yuping Luo)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem247.java (written by Magnus Solheim Thrap)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
the flashing problem is the one I solved most recently |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |
76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |
126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |
151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |
176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |
201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 | 612 | 613 |
I scored 13526 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 244 - Sliders | Numbers for which Euler's totient function ... - problem 248 >> |