Skip to content

Instantly share code, notes, and snippets.

@iwillspeak
Created Jan 31, 2017
Embed
What would you like to do?
Steps
#![feature(inclusive_range_syntax)]
/// Steps At
///
/// Returns the number of combinations of steps which can be made
/// where the top step is a given size. This is used as the recursive
/// step.
///
/// # Arguments
///
/// * `top_step` - The size of the top step
/// * `remaining_bricks` - The number of leftover bricks that can be used.
fn steps_at(top_step: usize, remaining_bricks: usize) -> usize {
if remaining_bricks > ((2 * top_step) + 2) {
// If we have enough to potentially make two layers of bricks
((top_step + 1)...(remaining_bricks / 2))
.map(|i| { steps_at(i, remaining_bricks - i)})
.sum::<usize>() + 1
} else if remaining_bricks > top_step {
// Just enough for a single layer of bricks
1
} else {
// Not enough leftover bricks to make a layer
0
}
}
/// Steps
///
/// Computes the number of possible steps whic can be created with a
/// given number of bricks.
///
/// # Arguments
///
/// * `i` - The number of bricks available
fn steps(i: usize) -> usize {
(1...i/2)
.map(|j| { steps_at(j, i - j)})
.sum()
}
fn main() {
for i in 1..200 {
println!("{}: {}", i, steps(i));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment