This shows a little use case for Const generics, in C++ (run-time about 0.32 seconds):
#include <stdio.h>
const int N_BOWLS = 40;
const int N_ORANGES = 9;
typedef int Used[N_BOWLS];
typedef int Oranges[N_ORANGES];
template <int turn>
int solve(int x, Used used, Oranges oranges) {
int count = 0;
for (; x < N_BOWLS - (N_ORANGES - turn - 1); x++) {
if (!used[x]) {
used[x]++;
for (int y = 0; y < turn; y++) {
const int tmp_index = x + x - oranges[y];
if (tmp_index >= 0 && tmp_index < N_BOWLS)
used[tmp_index]++;
}
oranges[turn] = x;
count += solve<turn + 1>(x + 1, used, oranges);
for (int y = 0; y < turn; y++) {
const int tmp_index = x + x - oranges[y];
if (tmp_index >= 0 && tmp_index < N_BOWLS)
used[tmp_index]--;
}
used[x]--;
}
}
return count;
}
template <>
inline int solve<N_ORANGES>(int, Used, Oranges) {
return 1;
}
int main() {
Used used = {0};
Oranges oranges = {0};
printf("%d\n", solve<0>(0, used, oranges) == 7555794);
}
Similar code in Rust without const generics (run-time about 0.52 seconds):
// rustc -C opt-level=3 -C target-cpu=native
const N_BOWLS: usize = 40;
const N_ORANGES: usize = 9;
type Used = [usize; N_BOWLS];
type Oranges = [usize; N_ORANGES];
fn solve(turn: usize, mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if turn == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - turn - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. turn {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[turn] = x;
count += solve(turn + 1, x + 1, used, oranges);
for y in 0 .. turn {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn main() {
//let mut used: Used = Default::default();
let mut used: Used = [0; 40];
let mut oranges: Oranges = Default::default();
println!("{}", solve(0, 0, &mut used, &mut oranges) == 7_555_794);
}
You can regain the same performance in Rust unrolling the template manually (run-time about 0.33 seconds):
// rustc -C opt-level=3 -C target-cpu=native
const N_BOWLS: usize = 40;
const N_ORANGES: usize = 9;
type Used = [usize; N_BOWLS];
type Oranges = [usize; N_ORANGES];
fn solve0(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 0 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 0 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 0 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[0] = x;
count += solve1(x + 1, used, oranges);
for y in 0 .. 0 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve1(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 1 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 1 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 1 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[1] = x;
count += solve2(x + 1, used, oranges);
for y in 0 .. 1 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve2(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 2 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 2 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 2 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[2] = x;
count += solve3(x + 1, used, oranges);
for y in 0 .. 2 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve3(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 3 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 3 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 3 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[3] = x;
count += solve4(x + 1, used, oranges);
for y in 0 .. 3 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve4(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 4 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 4 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 4 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[4] = x;
count += solve5(x + 1, used, oranges);
for y in 0 .. 4 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve5(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 5 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 5 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 5 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[5] = x;
count += solve6(x + 1, used, oranges);
for y in 0 .. 5 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve6(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 6 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 6 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 6 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[6] = x;
count += solve7(x + 1, used, oranges);
for y in 0 .. 6 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve7(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 7 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 7 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 7 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[7] = x;
count += solve8(x + 1, used, oranges);
for y in 0 .. 7 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve8(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
if 8 == N_ORANGES {
1
} else {
let mut count = 0;
while x < N_BOWLS - (N_ORANGES - 8 - 1) {
if used[x] == 0 {
used[x] += 1;
for y in 0 .. 8 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] += 1;
}
}
oranges[8] = x;
count += solve9(x + 1, used, oranges);
for y in 0 .. 8 {
let tmp_index = x + x - oranges[y];
if tmp_index < N_BOWLS {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
count
}
}
fn solve9(_: usize, _: &mut Used, _: &mut Oranges) -> usize {
1
}
fn main() {
//let mut used: Used = Default::default();
let mut used: Used = [0; 40];
let mut oranges: Oranges = Default::default();
println!("{}", solve0(0, &mut used, &mut oranges) == 7_555_794);
}
And the same code with D language templates and “static if” (with the LDC compiler the run-time is about 0.33 seconds):
enum uint BOWLS = 40;
enum uint ORANGES = 9;
alias Used = uint[BOWLS];
alias Oranges = uint[ORANGES];
uint solve(uint turn)(uint x, ref Used used, ref Oranges oranges) {
static if (turn == ORANGES) {
return 1;
} else {
uint count = 0;
while (x < BOWLS - (ORANGES - turn - 1)) {
if (used[x] == 0) {
used[x] += 1;
foreach (immutable uint y; 0 .. turn) {
immutable tmp_index = x + x - oranges[y];
if (tmp_index >= 0 && tmp_index < BOWLS) {
used[tmp_index] += 1;
}
}
oranges[turn] = x;
count += solve!(turn + 1)(x + 1, used, oranges);
foreach (immutable uint y; 0 .. turn) {
immutable tmp_index = x + x - oranges[y];
if (tmp_index >= 0 && tmp_index < BOWLS) {
used[tmp_index] -= 1;
}
}
used[x] -= 1;
}
x += 1;
}
return count;
}
}
void main() {
import std.stdio;
Used used = 0;
Oranges oranges = 0;
writeln(solve!0(0, used, oranges) == 7_555_794);
}
Is the current minimal Rust proposal including a “static if”?