<< problem 154 - Exploring Pascal's pyramid | Counting Digits - problem 156 >> |
Problem 155: Counting Capacitor Circuits
(see projecteuler.net/problem=155)
An electric circuit uses exclusively identical capacitors of the same value C.
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel
with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.
Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances.
For example, using up to n=3 capacitors of 60 \mu F each, we can obtain the following 7 distinct total capacitance values:
If we denote by D(n) the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors
and the simple procedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...
Find D(18).
Reminder : When connecting capacitors C_1, C_2 etc in parallel, the total capacitance is C_T = C_1 + C_2 + ...,
whereas when connecting them in series, the overall capacitance is given by: dfrac{1}{C_T} = dfrac{1}{C_1} = dfrac{1}{C_2} + ...
My Algorithm
Each large circuit can be subdivided into two smaller circuits that are either connected in parallel or in series.
There are sometimes multiple ways to subdivide a circuit - but all result in the same total capacitance.
The top-most example can be split into 2 plus 1 or 1 plus 2 capacitors. When connected in parallel, I always get 120 + 60 = 60 + 120 = 180.
Of course that's a very basic example because both combinations are based on parallel connections.
The idea is as follows:
- there is a single capacitor for D(1)
- to find all circuits for D(2) I have to combine all capacitors from D(a) and D(b) where a+b=2 in parallel and in series
- in general: to find all circuits for D(c) I have to combine all capacitors from D(a) and D(b) where a+b=c in parallel and in series
- if different combinations give the same total capacitance then it only has to be counted once ("each capacitance must be unique")
Fraction
to be able to handle connections in series(because of the heavy use of divisions in dfrac{1}{C_c} = dfrac{1}{C_a} = dfrac{1}{C_b}).
The numerator and/or denominator sometimes became pretty huge and after reading the problem statement multiple times
I realized that the actual rating of a single capacitor doesn't matter:
the example mentions 60 \mu F but that Farad value is just arbitrary. The number of networks of capacitors with 1 F will be the same since
I don't have to print the capacitances - only count how many different I can find.
With 60 \mu F I had tons of overflows, even with
long long
, but 1 F is perfectly fine with my Fraction
class even whenrelying on the slightly faster
unsigned short
(→ 20% performance boost).
Alternative Approaches
The series can be found in oeis.org/A153588 .
Modifications by HackerRank
My program is a little bit too slow for the last test case (probably misses the deadline just by a few milliseconds).
It's strange that even the Hackerrank author suggests pre-computing the result to match the 2 seconds time limit.
Note
The class Fraction
was added to my toolbox, too.
A significant part of my code takes care that all solutions/capacitances are unique.
The std::set
container offers that "for free": yes, you don't need to write any code - unlike I did - but std::set
is much slower, too.
The problem is solved roughly five times faster when #define FAST
is enabled (→ std::vector
instead of std::set
).
It's actually pretty nice how much code is identical for both containers: aside from push_back()
vs. insert()
there are no additional differences.
There is also a significant memory overhead of set::set
: it consumes about 200% more memory even though it only stores 50% of the values.
Even with all these optimizations: my solution is still in the top 10 of the "most expensive solutions".
And I have to admit: some parts of my code look ugly now - or better said: hardly comprehensible ...
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 3 | ./155
Output:
Note: the original problem's input 18
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. Or just jump to my GitHub repository.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
// use std::vector instead of std::set
#define FAST
// ---------- code from my toolbox ----------
// simple class to representation a fraction
// note: no checks for a zero denominator
// signs are not normalized
struct Fraction
{
// change to long long if you need to support larger values
typedef unsigned short T;
// numerator
T num;
// denominator
T den;
Fraction(T numerator, T denominator = 1)
: num(numerator), den(denominator)
{}
// add
Fraction operator+(const Fraction& other) const
{
// n1/d1 + n2/d2 = (n1*d2 + n2*d1) / d1*d2
return { T(num * other.den + other.num * den), T(den * other.den) };
}
// sort
bool operator< (const Fraction& other) const
{
// n1/d1 < n2/d2 => n1*d2 < n2*d2
return num * other.den < other.num * den;
}
// compare
bool operator==(const Fraction& other) const
{
// n1/d1 < n2/d2 => n1*d2 < n2*d2
return num * other.den == other.num * den;
}
// return Fraction with swapped numerator and denominator
Fraction inverse() const
{
return { den, num };
}
};
// ---------- problem-specific code ----------
int main()
{
unsigned int limit = 18;
std::cin >> limit;
// capacitance of a single element (1 F)
Fraction Capacitance = 1;
// store all circuits
#ifdef FAST
std::vector<std::vector<Fraction>> circuits;
#else
std::vector<std::set<Fraction>> circuits;
#endif
circuits.resize(limit + 1);
// only one basic circuit at level 1 (I use 1F instead of 60uF but the exact value is irrelevant)
circuits[1] = { Capacitance };
// find all circuits consisting of 2,3,4, ... 18 elements
for (unsigned int sizeC = 2; sizeC <= limit; sizeC++)
{
// split into "sub-circuits" A and B where size(A) <= size(B)
for (unsigned int sizeA = 1; sizeA <= sizeC / 2; sizeA++)
{
// remaining circuits
auto sizeB = sizeC - sizeA;
// create all combinations
for (auto circuitA : circuits[sizeA])
for (auto circuitB : circuits[sizeB])
{
// serial connection
// c = a + b
auto serial = circuitA + circuitB;
#ifdef FAST
circuits[sizeC].push_back(serial);
#else
circuits[sizeC].insert(serial);
#endif
// parallel connection
// 1/c = 1/a + 1/b
// invC = invA + invB where invC = 1/c and invA = 1/a and invB = 1/b
auto parallel = (circuitA.inverse() + circuitB.inverse()).inverse();
#ifdef FAST
circuits[sizeC].push_back(parallel);
#else
circuits[sizeC].insert(parallel);
#endif
}
}
#ifdef FAST
// remove duplicates
std::sort(circuits[sizeC].begin(), circuits[sizeC].end());
auto garbage = std::unique(circuits[sizeC].begin(), circuits[sizeC].end());
circuits[sizeC].erase(garbage, circuits[sizeC].end());
#endif
}
// merge all circuits
std::vector<Fraction> all;
#ifdef FAST
// little trick to keep memory usage low: move the largest vector's content instead of copying
all = std::move(circuits[limit]);
limit--;
#endif
// copy all capacitances
for (unsigned int i = 1; i <= limit; i++)
all.insert(all.end(), circuits[i].begin(), circuits[i].end());
// and remove duplicates
std::sort(all.begin(), all.end());
auto garbage = std::unique(all.begin(), all.end());
// count unique fractions
auto numUnique = std::distance(all.begin(), garbage);
std::cout << numUnique << std::endl;
return 0;
}
This solution contains 19 empty lines, 34 comments and 18 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 2.1 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 106 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
September 15, 2017 submitted solution
September 15, 2017 added comments
Hackerrank
see https://www.hackerrank.com/contests/projecteuler/challenges/euler155
My code solves 17 out of 18 test cases (score: 94.12%)
I failed 0 test cases due to wrong answers and 1 because of timeouts
Difficulty
Project Euler ranks this problem at 60% (out of 100%).
Hackerrank describes this problem as easy.
Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.
Links
projecteuler.net/thread=155 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/frrad/project-euler/blob/master/python/Problem155.py (written by Frederick Robinson)
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p155.py (written by Nayuki)
Python github.com/smacke/project-euler/blob/master/python/155.py (written by Stephen Macke)
C++ github.com/Meng-Gen/ProjectEuler/blob/master/155.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/155.cpp (written by Yuping Luo)
Java github.com/HaochenLiu/My-Project-Euler/blob/master/155.java (written by Haochen Liu)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p155.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem155.java (written by Magnus Solheim Thrap)
Mathematica github.com/steve98654/ProjectEuler/blob/master/155.nb
Perl github.com/shlomif/project-euler/blob/master/project-euler/155/euler-155.pl (written by Shlomi Fish)
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 |
I stopped working on Project Euler problems around the time they released 617.
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 | 632 | 633 | 634 | 635 | 636 | 637 | 638 | 639 | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 | 648 | 649 | 650 |
651 | 652 | 653 | 654 | 655 | 656 | 657 | 658 | 659 | 660 | 661 | 662 | 663 | 664 | 665 | 666 | 667 | 668 | 669 | 670 | 671 | 672 | 673 | 674 | 675 |
676 | 677 | 678 | 679 | 680 | 681 | 682 | 683 | 684 | 685 | 686 | 687 | 688 | 689 | 690 | 691 | 692 | 693 | 694 | 695 | 696 | 697 | 698 | 699 | 700 |
701 | 702 | 703 | 704 | 705 | 706 | 707 | 708 | 709 | 710 | 711 | 712 | 713 | 714 | 715 | 716 | 717 | 718 | 719 | 720 | 721 | 722 | 723 | 724 | 725 |
726 | 727 | 728 | 729 | 730 | 731 | 732 | 733 | 734 | 735 | 736 | 737 |
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 154 - Exploring Pascal's pyramid | Counting Digits - problem 156 >> |