Solution to https://fivethirtyeight.com/features/how-good-are-you-at-guess-who/

main.rs

use num::Rational;
use std::{collections::HashMap, iter::once};

struct Calc(HashMap<(isize, isize), Rational>);

impl Calc {
    fn prob(&mut self, me: isize, you: isize) -> Rational {
        assert!(me > 0);
        assert!(you > 0);
        // If we already have computed the solution, use that.
        if let Some(&ans) = self.0.get(&(me, you)) {
            return ans;
        }
        // Get the largest of selecting groups vs randomly
        let ans = (1..=me / 2)
            .map(|n| {
                // Choosing a question, dividing into n and (me - n) people
                Rational::from(1)
                    - Rational::new(n, me) * self.prob(you, n)
                    - Rational::new(me - n, me) * self.prob(you, me - n)
            })
            .chain(once(Rational::new(1, me))) // Selecting a random person
            .max()
            .unwrap();
        // Store the answer so we don't have to compute it again
        self.0.insert((me, you), ans);
        ans
    }
}

fn main() {
    let mut c = Calc(HashMap::new());
    println!("Ans(4)={}", c.prob(4, 4));
    println!("Ans(8)={}", c.prob(8, 8));
    println!("Ans(16)={}", c.prob(16, 16));
    println!("Ans(32)={}", c.prob(32, 32));
    println!("Ans(64)={}", c.prob(64, 64));

    println!("Ans(3)={}", c.prob(3, 3));
    println!("Ans(6)={}", c.prob(6, 6));
    println!("Ans(12)={}", c.prob(12, 12));
    println!("Ans(24)={}", c.prob(24, 24));
    println!("Ans(48)={}", c.prob(48, 48));
}