<< problem 113 - Non-bouncy numbers | Counting block combinations II - problem 115 >> |

# Problem 114: Counting block combinations I

(see projecteuler.net/problem=114)

A row measuring seven units in length has red blocks with a minimum length of three units placed on it,

such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes.

For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).

# Algorithm

This is a nice Dynamic Programming problem:

- if there are less than three cells available then all must be black (1 solution)

- else: the next cell can be black (return `count[space - 1]`

)

- or: the next cells can be red, try all possible lengths and add `count[space - block]`

The algorithm examines most row lengths multiple times but memoizing the results in `solutions`

keeps the running time well below 0.01 seconds.

## Modifications by HackerRank

My approach needs a bit of memory. Hackerrank has inputs up to 10^18 which clearly exceed the RAM size of a desktop PC.

[TODO] find closed formula

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

The code contains `#ifdef`

s to switch between the original problem and the Hackerrank version.

Enable `#ifdef ORIGINAL`

to produce the result for the original problem (default setting for most problems).

#include <iostream>
#include <vector>
#define ORIGINAL
// memoized solutions

const long long Unknown = -1;
std::vector<long long> solutions;
// print result modulo some number

#ifndef ORIGINAL
const unsigned long long Modulo = 1000000007;
#endif
// find result for row with a certain length

unsigned long long count(unsigned long long space, unsigned int minBlockLength)
{
// finished ?
if (space == 0)
return 1;
// already know the answer ?
if (solutions[space] != Unknown)
return solutions[space];
// one option is to leave the next cell black
auto result = count(space - 1, minBlockLength);
// insert red blocks at the current position with all possible spaces
for (auto block = minBlockLength; block <= space; block++)
{
// how much is left after inserting ?
auto next = space - block;
// must be followed by a black cell
if (next > 0)
next--;
// count all combinations
result += count(next, minBlockLength);
}
// Hackerrank only
#ifndef ORIGINAL
result %= Modulo;
#endif
// memoize result
solutions[space] = result;
return result;
}
int main()
{
// minimum length of each red block
unsigned int minBlockLength = 3;
// size of the whole row
unsigned long long totalLength = 50;
std::cin >> totalLength >> minBlockLength;
// cached results
solutions.resize(totalLength + 1, Unknown);
// let's go !
std::cout << count(totalLength, minBlockLength) << std::endl;
return 0;
}

This solution contains 13 empty lines, 16 comments and 7 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "7 3" | ./114`

Output:

*Note:* the original problem's input `50 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)*

# Benchmark

The correct solution to the original Project Euler problem was found in **less than 0.01** seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++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

May 13, 2017 submitted solution

May 13, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler114

My code solved **3** out of **20** test cases (score: **12.5%**)

I failed **0** test cases due to wrong answers and **17** because of timeouts

# Difficulty

Project Euler ranks this problem at **35%** (out of 100%).

Hackerrank describes this problem as **medium**.

*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 never an option.

# Links

projecteuler.net/thread=114 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-114-fill-row-with-blocks/ (written by Kristian Edlund)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p114.java (written by Nayuki)

Scala: github.com/samskivert/euler-scala/blob/master/Euler114.scala (written by Michael Bayne)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are already solved and there wasn't a Hackerrank version of it (at the time I solved it) or I didn't care about it because it differed too much.

*Please click on a problem's number to open my solution to that problem:*

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 |

<< problem 113 - Non-bouncy numbers | Counting block combinations II - problem 115 >> |