<< problem 156 - Counting Digits | Digital root sums of factorisations - problem 159 >> |
Problem 158: Exploring strings for which only one character comes lexicographically after its neighbour to the left
(see projecteuler.net/problem=158)
Taking three different letters from the 26 letters of the alphabet, character strings of length three can be formed.
Examples are 'abc', 'hat' and 'zyx'.
When we study these three examples we see that for 'abc' two characters come lexicographically after its neighbour to the left.
For 'hat' there is exactly one character that comes lexicographically after its neighbour to the left.
For 'zyx' there are zero characters that come lexicographically after its neighbour to the left.
In all there are 10400 strings of length 3 for which exactly one character comes lexicographically after its neighbour to the left.
We now consider strings of n <= 26 different characters from the alphabet.
For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically after its neighbour to the left.
What is the maximum value of p(n)?
My Algorithm
Each valid string s
consists of two sub-strings: s = left + right
left
and right
must be strictly monotonically descending (each letter/character is smaller than its left neighbor)
and there is a "break" between left
and right
such that the last character of left
is bigger than the first character of right
.
My function count(n, alphabet)
returns the number of words with n
characters out of an alphabet of size alphabet
(which is 26) that match all conditions.
It considers the simplified case where only the first characters are chosen. That mean that for n=3
only "a"
, "b"
and "c"
are taken from the alphabet.
The "break" can be at any position from 2
to n-1
and therefore a simple loop analyzes each possible break:
- there are \binom{n}{i} ways to build
left
using onlyi
out of the firstn
characters (seechoose(n, k)
, taken from problem 116) - any of the first
n
characters which are not part ofleft
must be part ofright
- if the highest
i
characters are all part ofleft
then there is no break betweenleft
andright
→ we must not count that combination
result
by the number of ways to choose n
characters from the whole alphabet
.
Alternative Approaches
I tried a Dynamic Programming approach, too, but had a bug somewhere. The next day I came up with the must simpler version you see below.
Note
The for
-loop can be transformed to a closed formula → speeding up the program.
But the program already finishes all calculations in less than 0.01 seconds, therefore I don't bother with finding the correct formula.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "26 3" | ./158
Output:
Note: the original problem's input 26 26
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++ and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
// number of ways to choose n elements from k available
// code taken from problem 116
unsigned long long choose(unsigned long long n, unsigned long long k)
{
// n! / (n-k)!k!
unsigned long long result = 1;
// reduce overflow by dividing as soon as possible to keep numbers small
for (unsigned long long invK = 1; invK <= k; invK++)
{
result *= n;
result /= invK;
n--;
}
return result;
}
// count number words with n characters
unsigned long long count(unsigned int n, unsigned int alphabet)
{
// invalid parameters: must not use each letter of the alphabet more than once
if (n > alphabet)
return 0;
// count how many word with n characters use the characters 1..n
unsigned long long result = 0;
// there are n places where the "break" between s1 and s2 can occur
// count all possible characters chosen for s1 and s2
for (unsigned int i = 1; i < n; i++)
result += choose(n, i) - 1; // minus 1 because there is always one combination with no break between s1 and s2
// general case: use characters 1..Alphabet instead of 1..n
return result * choose(alphabet, n);
}
int main()
{
// bonus feature: user-defined alphabet size and maximum word length
unsigned int alphabet = 26;
unsigned int size = 3;
std::cin >> alphabet >> size;
// all "words" with 2..size characters
unsigned long long best = 0;
for (unsigned int i = 2; i <= size; i++)
{
unsigned long long current = count(i, alphabet);
// more than before ?
if (best < current)
best = current;
}
std::cout << best << std::endl;
return 0;
}
This solution contains 7 empty lines, 13 comments and 1 preprocessor command.
Benchmark
The correct solution to the original Project Euler problem was found in less than 0.01 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
(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
June 13, 2017 submitted solution
June 13, 2017 added comments
Difficulty
Project Euler ranks this problem at 55% (out of 100%).
Links
projecteuler.net/thread=158 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/Meng-Gen/ProjectEuler/blob/master/158.py (written by Meng-Gen Tsai)
Python github.com/smacke/project-euler/blob/master/python/158.py (written by Stephen Macke)
C++ github.com/roosephu/project-euler/blob/master/158.cpp (written by Yuping Luo)
C++ github.com/smacke/project-euler/blob/master/cpp/158.cpp (written by Stephen Macke)
Java github.com/HaochenLiu/My-Project-Euler/blob/master/158.java (written by Haochen Liu)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem158.java (written by Magnus Solheim Thrap)
Go github.com/frrad/project-euler/blob/master/golang/Problem158.go (written by Frederick Robinson)
Perl github.com/shlomif/project-euler/blob/master/project-euler/158/euler-158-v1.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 |
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 |
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 156 - Counting Digits | Digital root sums of factorisations - problem 159 >> |