<< problem 214 - Totient Chains | Investigating the primality of numbers of the ... - problem 216 >> |
Problem 215: Crack-free Walls
(see projecteuler.net/problem=215)
Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal x vertical dimensions) such that,
for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".
For example, the following 9x3 wall is not acceptable due to the running crack shown in red:
There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8.
Calculate W(32,10).
My Algorithm
My solution can be divided in 3 steps:
1. generateRows
: find every possible sequence of "long" and "short" bricks, store them in allRows
2. checkCompatibility
: compare each possible row to each other to figure out which rows can be placed next to each other without running cracks, store in compatible
3. count
: determine how many rows can be below the current row, based on information in compatible
My rows contain the positions of the edges of two bricks (the "cracks"). The first and last are omitted because they are always 0 and 32 and not considered to be a crack.
The first row of the 9x3 wall would be { 3, 5, 7 }
, the second { 2, 4, 7 }
and the bottom { 3, 6 }
.
Step 1 was implemented as a recursive function that adds a "long" and a "short" brick to a row until its width exceeds 32.
Step 2 compares all rows and contains a stripped-down version of std::intersection
to find values contained in two containers.
Step 3 requires a bit of memoization but is the most simple step: it calls itself with all compatible rows.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "9 3" | ./215
Output:
Note: the original problem's input 32 10
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 <vector>
// a single row of brick, store the distance of each crack from the left border
typedef std::vector<unsigned char> Row;
// all unique rows
std::vector<Row> allRows;
// for each row of allRows store the indices of potential neighboring rows
std::vector<std::vector<unsigned int>> compatible;
// generate all distinct row patterns and store them in allRows
void generateRows(Row row, unsigned char maxWidth)
{
// last element contains the width of current row
auto width = row.empty() ? 0 : row.back();
// just one brick left ?
if (width + 2 == maxWidth || width + 3 == maxWidth)
{
allRows.push_back(row);
return;
}
// gap is too small for a brick
if (width + 1 == maxWidth)
return;
// add a 2-brick
row.push_back(width + 2);
generateRows(row, maxWidth);
// add a 3-brick
row.back()++; // replace last 2-brick by a 3-brick
generateRows(row, maxWidth);
}
// find all rows that can be neighbors
void checkCompatibility()
{
compatible.resize(allRows.size());
for (size_t i = 0; i < allRows.size(); i++)
for (size_t j = i + 1; j < allRows.size(); j++)
{
// verify that both rows share no crack
bool valid = true;
// similar to implementation of std::intersection
// note: all rows are already sorted
auto current1 = allRows[i].begin();
auto current2 = allRows[j].begin();
while (current1 != allRows[i].end() && current2 != allRows[j].end())
{
if (*current1 < *current2)
current1++;
else
if (*current2 < *current1)
current2++;
else
{
valid = false;
break;
}
}
// yes, both rows are compatible to each other
if (valid)
{
compatible[i].push_back(j);
compatible[j].push_back(i);
}
}
}
// count crack-free walls
unsigned long long count(unsigned int rowId, unsigned int rowsLeft)
{
// last row ?
if (rowsLeft == 1)
return 1;
static std::vector<std::vector<unsigned long long>> cache(allRows.size());
const unsigned long long Invalid = 0;
// try to look up memoized result
if (cache[rowId].size() <= rowsLeft)
cache[rowId].resize(rowsLeft + 1, Invalid); // not known yet, allocate memory
else
if (cache[rowId][rowsLeft] != Invalid)
return cache[rowId][rowsLeft];
// process all compatible walls
unsigned long long result = 0;
for (auto x : compatible[rowId])
result += count(x, rowsLeft - 1);
cache[rowId][rowsLeft] = result;
return result;
}
int main()
{
unsigned int width = 32;// 9;
unsigned int height = 10;// 3;
std::cin >> width >> height;
// create all 3329 distinct rows
Row empty;
generateRows(empty, width);
// set up compatibility relationships
checkCompatibility();
// start with each known row and count generated walls
unsigned long long result = 0;
for (unsigned int i = 0; i < allRows.size(); i++)
result += count(i, height);
std::cout << result << std::endl;
return 0;
}
This solution contains 19 empty lines, 21 comments and 2 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.06 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 3 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
July 22, 2017 submitted solution
July 22, 2017 added comments
Difficulty
Project Euler ranks this problem at 50% (out of 100%).
Links
projecteuler.net/thread=215 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p215.py (written by Nayuki)
Python github.com/smacke/project-euler/blob/master/python/215.py (written by Stephen Macke)
C++ github.com/Meng-Gen/ProjectEuler/blob/master/215.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/215.cpp (written by Yuping Luo)
C github.com/LaurentMazare/ProjectEuler/blob/master/e215.c (written by Laurent Mazare)
Java github.com/HaochenLiu/My-Project-Euler/blob/master/215.java (written by Haochen Liu)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p215.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem215.java (written by Magnus Solheim Thrap)
Go github.com/frrad/project-euler/blob/master/golang/Problem215.go (written by Frederick Robinson)
Mathematica github.com/steve98654/ProjectEuler/blob/master/215.nb
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 | |
[new] | 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 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 |
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 214 - Totient Chains | Investigating the primality of numbers of the ... - problem 216 >> |