Caching self-referential function results in Rust

Question

I am trying to teach myself Rust with Project Euler Problems, specifically https://projecteuler.net/problem=76.

I came up with a solution to the problem of:

fn main() {
    println!("{}", solution(100, 99));
}

fn solution(sum_to: i32, max_size: i32) -> i32 {
    if sum_to == 0 || max_size == 1 {
        1
    } else if sum_to < 0 {
        0
    } else {
        (1..=max_size)
            .map(|i| solution(sum_to - i, min(i, sum_to - i)))
            .sum()
    }
}

I know this works, but it takes forever to run because it winds up computing result for the same input multiple times.

I tried building a caching solution to this, but I run into problems with the borrow checker.

Code:

use std::cmp::min;
use std::collections::HashMap;

fn main() {
    println!("{}", solution_head(100))
}

fn solution_head(sum_to: i32) -> i32 {
    let mut cache = HashMap::new();
    (1..sum_to)
        .map(|i| solution(&mut cache, sum_to - i, min(i, sum_to - i)))
        .sum()
}

fn solution(
    cache: &mut HashMap<i32, HashMap<i32, i32>>,
    sum_to: i32,
    max_size: i32,
) -> i32 {
    if sum_to == 0 {
        1
    } else if sum_to < 0 {
        0
    } else {
        let cache_entry = cache.entry(sum_to);
        let map = cache_entry.or_insert(HashMap::new());
        let map_entry = map.entry(max_size);
        *map_entry.or_insert_with(|| {
            (1..=max_size)
                .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
                .sum()
        })
    }
}

Error:

error[E0500]: closure requires unique access to `*cache` but it is already borrowed
  --> src/bin/problem_76.rs:27:35
   |
24 |         let cache_entry = cache.entry(sum_to);
   |                           ------------------- borrow occurs here
...
27 |         *map_entry.or_insert_with(|| {
   |                    -------------- ^^ closure construction occurs here
   |                    |
   |                    first borrow later used by call
28 |             (1..=max_size)
29 |                 .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
   |                                   ----- second borrow occurs due to use of `*cache` in closure

I am not at all certain of how to accomplish this, as the ultimate problem that the borrow checker has with this code is that I am both:

using a reference to the cache in the function to check if I have already computed the result
sending a reference to the cache to recursive call of the function so that I can check if I have already computed the downstream result

What is the proper, idiomatic way of accomplishing this in Rust?

Have you tried a "global" map? https://stackoverflow.com/questions/34832583/global-mutable-hashmap-in-a-library — kelsny, Nov 05 '22 at 07:40

score 3 · Accepted Answer · answered Nov 05 '22 at 08:01

The problem is that cache_entry points to a value inside cache which means you cannot modify cache while the entry is in scope. I would restructure the code to use .get() and .insert(). I would also simplify cache to be HashMap<(i32, i32), i32>.

The following code works fast for me:

use std::collections::HashMap;

fn main() {
    let mut cache = HashMap::new();
    println!("{}", solution(&mut cache, 100, 99));
}

fn solution(cache: &mut HashMap<(i32, i32), i32>, sum_to: i32, max_size: i32) -> i32 {
    if sum_to == 0 || max_size == 1 {
        1
    } else if sum_to < 0 {
        0
    } else if let Some(x) = cache.get(&(sum_to, max_size)) {
        *x
    } else {
        let x = (1..=max_size)
            .map(|i| solution(cache, sum_to - i, std::cmp::min(i, sum_to - i)))
            .sum();
        cache.insert((sum_to, max_size), x);
        x
    }
}

Playground

Caching self-referential function results in Rust

1 Answers1