More feedback wanted: Countdown solver

[ZPedro]

Previously; every single line of code has been touched since then, so the review can resume from scratch anyway.

I am still not satisfied with the performance (lots of overhead from RefCell in particular), so I'm beginning to think the way forward would be to write unsafe code for the linked list with the operations I need (which more or less amount to insertion and removal of a single node at a time at locations designated by bookmarks), and then compare that with an array-based version where these insertions and removals occur at an offset instead.

use std::cell::RefCell;
use std::fmt::{Display, Error, Formatter};
use std::rc::Rc;

struct PresentLink<T> {
    g: Rc<RefCell<Node<T>>>,
}

struct Link<T> {
    g: Option<PresentLink<T>>,
}

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> Link<T> {
    fn push(&mut self, elem: T) {
        let new_node = Rc::new(RefCell::new(Node {
            elem: elem,
            next: Link { g: None },
        }));

        self.push_node(PresentLink { g: new_node });
    }

    fn push_node(&mut self, node: PresentLink<T>) {
        node.g.borrow_mut().next = Link { g: self.g.take() };
        self.g = Some(node);
    }

    fn pop_node(&mut self) -> Link<T> {
        Link {
            g: self.g.take().map(|node| {
                self.g = node.g.borrow_mut().next.g.take();
                node
            }),
        }
    }
}

#[derive(PartialEq, Clone, Copy, Debug)]
enum Op {
    Additive,
    Multiplicative,
}

impl Op {
    fn neutral_value(&self) -> u32 {
        match self {
            Op::Additive => 0,
            Op::Multiplicative => 1,
        }
    }

    fn combine(&self, a: u32, b: u32) -> u32 {
        match self {
            Op::Additive => a + b,
            Op::Multiplicative => a * b,
        }
    }

    fn realize(&self, a: u32, b: u32) -> Option<u32> {
        match self {
            Op::Additive => {
                if a > b {
                    Some(a - b)
                } else {
                    None
                }
            }
            Op::Multiplicative => {
                if a % b == 0 {
                    Some(a / b)
                } else {
                    None
                }
            }
        }
    }
}

struct Expr {
    op: Op,
    operands: Link<Contribution>,
}

struct ReadyValue {
    value: u32,
    backing: Option<Expr>,
}

impl ReadyValue {
    fn new_primitive(val: u32) -> Self {
        ReadyValue {
            value: val,
            backing: None,
        }
    }

    fn new_composed(val: u32, backing: Expr) -> Self {
        ReadyValue {
            value: val,
            backing: Some(backing),
        }
    }
}

struct Contribution {
    reverse: bool,
    value: ReadyValue,
}

impl PresentLink<Contribution> {
    fn front_expr_push_node(&self, node: PresentLink<Contribution>) {
        self.g
            .borrow_mut()
            .elem
            .value
            .backing
            .as_mut()
            .expect("The contribution present must be composed")
            .operands
            .push_node(node);
    }

    fn front_expr_pop_node(&self) -> Link<Contribution> {
        self.g
            .borrow_mut()
            .elem
            .value
            .backing
            .as_mut()
            .expect("The contribution present must be composed")
            .operands
            .pop_node()
    }
}

struct ResolveContext {
    goal: u32,
    available: Link<Contribution>,
    free_list: Link<Contribution>,
}

#[derive(Clone, Copy)]
struct AvailabilityIndexing {
    count: usize,
    composed_count: usize,
    other_composed_count: usize,
}

fn resolve(goal: u32, primitives: &[u32]) {
    let mut l_context = ResolveContext {
        goal: goal,
        available: Link { g: None },
        free_list: Link { g: None },
    };

    let mut count = 0usize;

    for prim in primitives {
        l_context.available.push(Contribution {
            reverse: false,
            value: ReadyValue::new_primitive(*prim),
        });

        l_context.free_list.push(Contribution {
            reverse: false,
            value: ReadyValue::new_composed(
                0,
                Expr {
                    op: Op::Additive,
                    operands: Link { g: None },
                },
            ),
        });
        count += 1;
    }

    let available_amounts = AvailabilityIndexing {
        count: count,
        composed_count: 0,
        other_composed_count: 0,
    };

    for phase in 0..=1 {
        explore_addition_of_floor(
            &mut l_context,
            &available_amounts,
            if phase == 1 {
                Op::Multiplicative
            } else {
                Op::Additive
            },
        );
    }
}

fn explore_addition_of_floor(
    resolve_context: &mut ResolveContext,
    available_amounts: &AvailabilityIndexing,
    new_operation: Op,
) {
    if available_amounts.other_composed_count != 0 {
        return;
    }

    let mut l_available_amounts = *available_amounts;

    l_available_amounts.other_composed_count = l_available_amounts.composed_count;
    l_available_amounts.composed_count = 0;

    explore_addition_of_right_node_guts(
        resolve_context,
        &mut l_available_amounts,
        None,
        new_operation,
    );
}

// The following function will hopefully be inlined

fn explore_addition_of_sibling_right_node(
    resolve_context: &mut ResolveContext,
    available_amounts: &AvailabilityIndexing,
    caller_recruitment_bookmark: &PresentLink<Contribution>,
    new_operation: Op,
) {
    let mut l_available_amounts = *available_amounts;

    explore_addition_of_right_node_guts(
        resolve_context,
        &mut l_available_amounts,
        Some(caller_recruitment_bookmark),
        new_operation,
    );
}

struct RightNodeContext<'a> {
    resolve_context: &'a mut ResolveContext,
    op: Op,
    downstream_siblings_recruitment_bookmark: PresentLink<Contribution>,
}
// Siblings are the other right nodes on the same floor
// Downstream ones are those created while this one is active

fn explore_addition_of_right_node_guts(
    resolve_context: &mut ResolveContext,
    available_amounts: &mut AvailabilityIndexing,
    caller_recruitment_bookmark: Option<&PresentLink<Contribution>>,
    new_operation: Op,
) {
    if (available_amounts.count - available_amounts.composed_count) < 2 {
        // don't bother
        return;
    }

    available_amounts.count += 1;
    available_amounts.composed_count += 1;

    let neutral_value = new_operation.neutral_value();

    let temp = resolve_context
        .free_list
        .pop_node()
        .g
        .expect("The free list must be big enough to satisfy all intermediate operations");

    temp.g
        .borrow_mut()
        .elem
        .value
        .backing
        .as_mut()
        .expect("The free list must only contain composed contributions")
        .op = new_operation;

    let mut l_context = RightNodeContext {
        resolve_context: resolve_context,
        op: new_operation,
        downstream_siblings_recruitment_bookmark: PresentLink {
            g: Rc::clone(&caller_recruitment_bookmark.unwrap_or(&temp).g),
        },
    };

    l_context.resolve_context.available.push_node(temp);

    let silly_temp = PresentLink {
        g: Rc::clone(&l_context.downstream_siblings_recruitment_bookmark.g),
    };

    iterate_possible_left_nodes(
        &mut l_context,
        available_amounts,
        &silly_temp,
        0,
        0,
        neutral_value,
        neutral_value,
    );

    l_context.resolve_context.free_list.push_node(
        l_context.resolve_context.available.pop_node().g.expect(
            "iterate_possible_left_nodes must exit with the available list exactly as it found it",
        ),
    );
}

/*
The point of iterate_possible_left_nodes() is to enumerate all the possible ways
to recruit candidates into the current operation, out of the pool of possible
candidates; that pool has been determined by explore_addition_of_right_node().

Obviously, the number of possibilities to pick a non-strict subset out of N
elements is 2 to the Nth power: each candidate in the pool can either be
recruited (1) or not (0) by this composition. Some of these possibilities are
invalid, of course, but we will explore the solution space that way.

By counting the possibilities from 00...0 to 11...1, we would in fact enumerate
all the possible recruitments for this composition. For practical reasons, we
will go backwards, from 11...1 to 00...0.

What we will do in practice is evaluating the first candidate, first recruting
it, which means we start with:
- 1x...x
then adjust the recruitment location, and delegate to ourselves. That way,
assuming this function performs it job for N-1, it will perform the job from
11...1 to 10...0; in other words, half the job for N. Then, we remove that
candidate from the composition, and ihnibit it from any future recruitment for
this composition; then we start over the loop.
The result is that the next candidate will be evaluated and hired at first and
recursive delegation will occur, resulting in these possibilities being
explored:
- 01...x
That is, from 011...1 to 010...0.
At the next loop iteration, the possibilities explored will start with 001, etc.
up until we realize we excluded all candidates; at which point the only
combination left is 00...0, which we don't need to explore at all. Unless, of
course, there were only one or two candidates in the pool, in which case that
test triggers even earlier.

There is additional accounting to avoid a downstream sibling (a composition on
the same floor) recovering candidates in a way that results in a composition
that we ourselves explored earlier, but that is the basic principle.
*/

fn iterate_possible_left_nodes(
    right_node_context: &mut RightNodeContext,
    available_amounts: &AvailabilityIndexing,
    recruitment_loc: &PresentLink<Contribution>,
    forward_count: usize,
    reverse_count: usize,
    forward_total: u32,
    reverse_total: u32,
) {
    let mut l_available_amounts = *available_amounts;
    let mut l_recruitment_loc = recruitment_loc;
    let mut carryover: PresentLink<Contribution>;

    l_available_amounts.count -= 1;

    let empty_composition = (forward_count + reverse_count == 0);

    loop {
        let mut to_discard = l_recruitment_loc.g.borrow_mut();
        if let Some(mut candidate) = to_discard.next.pop_node().g {
            drop(to_discard);

            if empty_composition {
                right_node_context.downstream_siblings_recruitment_bookmark = PresentLink {
                    g: Rc::clone(&l_recruitment_loc.g),
                };
            }

            l_available_amounts.other_composed_count = available_amounts.other_composed_count
                - match candidate.g.borrow().elem.value.backing {
                    None => 0,    // primitive
                    Some(_) => 1, // composed
                };
            for phase in 0..=1 {
                let reverse = phase != 0;
                candidate.g.borrow_mut().elem.reverse = reverse;

                let new_forward_count = forward_count + if reverse { 0 } else { 1 };
                let new_reverse_count = reverse_count + if reverse { 1 } else { 0 };
                let combinator = |operand| {
                    right_node_context
                        .op
                        .combine(operand, candidate.g.borrow().elem.value.value)
                };
                let new_forward_total = if reverse {
                    forward_total
                } else {
                    combinator(forward_total)
                };
                let new_reverse_total = if reverse {
                    combinator(reverse_total)
                } else {
                    reverse_total
                };

                right_node_context
                    .resolve_context
                    .available
                    .g
                    .as_ref()
                    .expect("The expression currently being built must be present")
                    .front_expr_push_node(candidate);

                iterate_possible_left_nodes(
                    right_node_context,
                    &l_available_amounts,
                    l_recruitment_loc,
                    new_forward_count,
                    new_reverse_count,
                    new_forward_total,
                    new_reverse_total,
                );

                (|| -> Option<()> {
                    if (new_forward_count == 0) || ((new_forward_count + new_reverse_count) < 2) {
                        return None;
                    }

                    let res = right_node_context
                        .op
                        .realize(new_forward_total, new_reverse_total)?;

                    right_node_context
                        .resolve_context
                        .available
                        .g
                        .as_ref()
                        .expect("The expression currently being built must be present")
                        .g
                        .borrow_mut()
                        .elem
                        .value
                        .value = res;

                    if l_available_amounts.count == 1 {
                        if res == right_node_context.resolve_context.goal {
                            print_result(
                                &right_node_context
                                    .resolve_context
                                    .available
                                    .g
                                    .as_ref()
                                    .expect("The expression currently being built must be present")
                                    .g
                                    .borrow()
                                    .elem
                                    .value,
                            );
                        }
                    } else {
                        explore_addition_of_sibling_right_node(
                            *(&mut right_node_context.resolve_context),
                            &l_available_amounts,
                            &right_node_context.downstream_siblings_recruitment_bookmark,
                            right_node_context.op,
                        );

                        explore_addition_of_floor(
                            *(&mut right_node_context.resolve_context),
                            &l_available_amounts,
                            if (right_node_context.op == Op::Additive) {
                                Op::Multiplicative
                            } else {
                                Op::Additive
                            },
                        );
                    }
                    Some(())
                })();

                candidate = right_node_context
                    .resolve_context
                    .available
                    .g
                    .as_ref()
                    .expect("The expression currently being built must be present")
                    .front_expr_pop_node()
                    .g
                    .expect("The expression contribution list must not be empty");
            }

            let temp = PresentLink {
                g: Rc::clone(&candidate.g),
            };
            l_recruitment_loc.g.borrow_mut().next.push_node(candidate);

            if empty_composition && l_available_amounts.other_composed_count != 0 {
                return;
                /* if we'd keep going, we would skip an "other_composed" not just for this composition,
                but for all downstream siblings (see usage of empty_composition at beginning of loop).
                As a result, other_composed_count would never reach 0 and so we'd never be able to
                close the floor anyway. So it'd be pointless to keep going. */
            }

            carryover = temp;
            l_recruitment_loc = &carryover;
        } else {
            break;
        }
    }
}

fn print_result(value: &ReadyValue) {
    println!("{}", value);
}

struct StackIterator<T> {
    top: Link<T>,
}

impl<T> StackIterator<T> {
    fn new(stack: &Link<T>) -> Self {
        Self {
            top: Link {
                g: stack.g.as_ref().map(|z| PresentLink { g: Rc::clone(&z.g) }),
            },
        }
    }
}

impl<T> Iterator for StackIterator<T> {
    type Item = PresentLink<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let temp = self.top.g.take()?;
        self.top.g = temp
            .g
            .borrow()
            .next
            .g
            .as_ref()
            .map(|z| PresentLink { g: Rc::clone(&z.g) });
        Some(temp)
    }
}

impl Display for Op {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        write!(
            f,
            "{}",
            match (self, f.sign_minus()) {
                (Op::Additive, false) => "+",
                (Op::Additive, true) => "-",
                (Op::Multiplicative, false) => "*",
                (Op::Multiplicative, true) => "/",
            }
        )
    }
}

impl Display for ReadyValue {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        match &self.backing {
            None => {
                write!(f, "{}", self.value)?;
            }
            Some(Expr { op, operands }) => {
                let mut is_first = true;
                let mut num_rev = 0usize;

                write!(f, "(")?;

                let prepare_child = |in_f: &mut Formatter<'_>, in_is_first: &mut bool| {
                    if !*in_is_first {
                        write!(in_f, " {}", op)?;
                    }
                    *in_is_first = false;
                    write!(in_f, " ")
                };

                for concrete in StackIterator::new(operands) {
                    if concrete.g.borrow().elem.reverse {
                        num_rev += 1;
                    } else {
                        prepare_child(f, &mut is_first)?;
                        write!(f, "{}", &concrete.g.borrow().elem.value)?;
                    }
                }

                if num_rev > 0 {
                    write!(f, " {:-}", op)?;
                    if num_rev > 1 {
                        write!(f, " (")?;
                    }
                }

                is_first = true;

                for concrete in StackIterator::new(operands) {
                    if concrete.g.borrow().elem.reverse {
                        prepare_child(f, &mut is_first)?;
                        write!(f, "{}", &concrete.g.borrow().elem.value)?;
                    }
                }

                if num_rev > 1 {
                    write!(f, " )")?;
                }
                write!(f, " )")?;
            }
        };

        Ok(())
    }
}

fn main() {
    // 0 solution:
    resolve(10000000, &[50, 25, 5, 2, 10, 4, 8]);
    // 0 solution:
    resolve(23917, &[50, 25, 5, 2, 10, 4, 8]);
    // Find some solutions:
    resolve(1800, &[1, 1, 2, 2, 5, 4, 10]);
    // Find 2 solutions:
    resolve(5432, &[2, 4, 8, 3, 9, 6, 1]);
    // Find 1 solution:
    resolve(10301, &[75, 25, 5, 3, 3, 9, 1]);
    // Find 4 solutions:
    resolve(4321, &[2, 4, 8, 3, 9, 6, 1]);
    // Find many solutions:
    resolve(4471, &[75, 10, 2, 6, 7, 1, 1]);
}

[alice]

Do you have a description of the problem you're trying to solve? I tried googling "Countdown numbers round" but didn't find anything.

[2e71828]

It's one of the segments in a popular British game show. The particular game in question can be described something like this:

Determine a sequence of arithmetic operations on a set of given input integers that produces a result as close as possible¹ to the given target integer.

¹ In the context of a competition, closer than your competitor's answer.

[ZPedro]

Oh, and I forgot to attach this as tribute to my fellow rustaceans:

[jonh]

Countdown (game show) | Numbers round

[ZPedro]

So, since this code here appears more satisfying I thought I'd do a little post-mortem of the first review topic.

I think the most significant improvements came from stopping the attempts to do a bunch of treatments as a single step; that attitude was best exemplified by the former Op type (the one that had an Empty case and dependent data). I thought it would make for fewer statements, as when I need to determine whether a value is composed I often soon need to know what its operation is; but when I distanced myself from that initial attitude, I was able to simplify the code in significant ways. In fact, these simplifications compounded: when I relented and added explore_addition_of_floor() instead of having explore_addition_of_right_node() handle both cases (i.e. whether the right node in question opens a new floor or not), it turned out to unlock additional simplification in code that had previously been set up to be less complex in the first place.

Even in cases where this resulted in a concern being split between two functions, the resulting solution (e.g. the caller_recruitment_bookmark parameter of explore_addition_of_right_node_guts() being an Option) turned out to be less onerous (here, by using caller_recruitment_bookmark.unwrap_or(&temp)) than trying to handle it all as a single "transaction".

Another set of improvements came from reading Chapter 18 and beyond, but also Rust Design Patterns. In fact, I think some of these patterns, including the suggestions of methods of the standard library objects such as ::take or ::replace, ought to be part of the base book (with proper flagging of course). If only because the compiler will suggest them and/or because there is no safe alternative.

(I also figured out how to properly debug code on my Mac, but this will be the subject of a different topic)