Hello. After the requisite hair-pulling, I have successfully implemented my first non-trivial algorithm with Rust, and I thought I'd present it here for feedback. First the code, then a few points where I think it ought to be possible to do better.
use std::rc::Rc;
use std::cell::RefCell;
use std::cell::Ref;
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
trait Stack<T> {
fn push(&mut self, elem: T);
fn push_node(&mut self, node: Rc<RefCell<Node<T>>>);
fn pop_node(&mut self) -> Option<Rc<RefCell<Node<T>>>>;
}
impl<T> Stack<T> for Link<T> {
fn push(&mut self, elem: T) {
let new_node = Rc::new(RefCell::new(Node {
elem: elem,
next: None,
}));
self.push_node(new_node);
}
fn push_node(&mut self, node: Rc<RefCell<Node<T>>>) {
(*node).borrow_mut().next = self.take();
*self = Some(node);
}
fn pop_node(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
self.take().map(|node| {
*self = (*node).borrow_mut().next.take();
node
})
}
}
enum Op {
Empty,
Additive(Link<Contribution>),
Multiplicative(Link<Contribution>),
}
impl Op {
fn neutral_value(&self) -> u32 {
match self {
Op::Empty => panic!(),
Op::Additive(_) => 0,
Op::Multiplicative(_) => 1
}
}
fn combine(&self, a: u32, b: u32) -> u32 {
match self {
Op::Empty => panic!(),
Op::Additive(_) => a+b,
Op::Multiplicative(_) => a*b
}
}
fn realize(&self, a: u32, b: u32) -> Option<u32> {
match self {
Op::Empty => panic!(),
Op::Additive(_) => if a>b { Some(a-b) } else { None },
Op::Multiplicative(_) => if a%b == 0 { Some(a/b) } else { None }
}
}
}
struct ReadyValue {
value: u32,
op: Op,
}
impl ReadyValue {
fn new_primitive(val: u32) -> Self {
ReadyValue { value: val, op: Op::Empty }
}
fn new_composed(val: u32, is_multiplicative: bool) -> Self {
ReadyValue { value: val, op: if is_multiplicative { Op::Multiplicative(None) } else { Op::Additive(None) } }
}
}
struct Contribution {
reverse: bool,
value: ReadyValue,
}
struct ResolveContext {
goal: u32,
available: Link::<Contribution>,
free_list: Link::<Contribution>,
}
#[derive(Clone)]
#[derive(Copy)]
struct AvailabilityIndexing {
count: usize,
composed_count: usize,
other_composed_count: usize,
}
fn resolve(goal: u32, primitives: &Vec<u32>) {
let mut local_context = ResolveContext { goal: goal,
available: None,
free_list: None};
let mut count = 0usize;
for prim in primitives {
local_context.available.push(Contribution { reverse: false, value: ReadyValue::new_primitive(*prim) });
local_context.free_list.push(Contribution { reverse: false, value: ReadyValue::new_composed(0, false) });
count += 1;
}
let available = AvailabilityIndexing {count: count,
composed_count: 0,
other_composed_count: 0};
for phase in 0..=1 {
explore_addition_of_right_node(&mut local_context, &available, None, if phase == 1 { Op::Multiplicative(None) } else { Op::Additive(None) });
}
}
struct RightNodeContext<'a> {
inherited_recruitment_bookmark: &'a Rc<RefCell<Node<Contribution>>>,
}
fn explore_addition_of_right_node(resolve_context: &mut ResolveContext,
available: & AvailabilityIndexing,
called_recruitment_bookmark: Option<&Rc<RefCell<Node<Contribution>>>>,
operation: Op) {
let mut local_availability = *available;
let no_other_left = local_availability.other_composed_count == 0;
let neutral_value = operation.neutral_value();
let mut work_node = resolve_context.free_list.pop_node().unwrap();
let lifetime: Rc<RefCell<Node<Contribution>>>;
let mut op_case = |is_same| {
if is_same {
local_availability.composed_count += 1;
} else {
local_availability.other_composed_count = local_availability.composed_count;
local_availability.composed_count = 1;
}
};
let local_context = RightNodeContext { inherited_recruitment_bookmark:
if let Some(concrete) = called_recruitment_bookmark.as_ref() {
match resolve_context.available.as_ref().unwrap().borrow().elem.value.op {
Op::Empty => panic!(),
Op::Additive(_) => match operation {
Op::Empty => panic!(),
Op::Additive(_) => { op_case(true); concrete }
Op::Multiplicative(_) => if no_other_left {
op_case(false);
lifetime = Rc::clone(&work_node);
&lifetime
} else {
// TODO: figure out how to remove duplication
resolve_context.free_list.push_node(work_node);
return;
}
}
Op::Multiplicative(_) => match operation {
Op::Empty => panic!(),
Op::Additive(_) => if no_other_left {
op_case(false);
lifetime = Rc::clone(&work_node);
&lifetime
} else {
// TODO: figure out how to remove duplication
resolve_context.free_list.push_node(work_node);
return;
}
Op::Multiplicative(_) => { op_case(true); concrete }
}
}
} else if no_other_left {
op_case(false);
lifetime = Rc::clone(&work_node);
&lifetime
} else {
// TODO: figure out how to remove duplication
resolve_context.free_list.push_node(work_node);
return;
}
};
local_availability.count += 1;
if (local_availability.count - local_availability.composed_count) < 2 { // don't bother
// TODO: figure out how to remove duplication
resolve_context.free_list.push_node(work_node);
return;
}
(*work_node).borrow_mut().elem.value.op = operation;
resolve_context.available.push_node(work_node);
iterate_possible_left_nodes(resolve_context, &local_context,
&local_availability,
local_context.inherited_recruitment_bookmark,
0, 0, neutral_value, neutral_value);
work_node = resolve_context.available.pop_node().unwrap();
resolve_context.free_list.push_node(work_node);
}
fn iterate_possible_left_nodes(resolve_context: &mut ResolveContext,
right_node_context: &RightNodeContext,
available: &AvailabilityIndexing,
recruitment_loc: &Rc<RefCell<Node<Contribution>>>,
forward_count: usize, reverse_count: usize,
forward_total: u32, reverse_total: u32) {
let mut local_availability = *available;
let mut local_recruitment_loc = recruitment_loc;
let mut backing: Rc<RefCell<Node<Contribution>>>;
local_availability.count -= 1;
loop {
let mut to_discard = (*local_recruitment_loc).borrow_mut();
if let Some(mut candidate) = to_discard.next.pop_node() {
drop(to_discard);
local_availability.other_composed_count
= available.other_composed_count - match (*candidate).borrow().elem.value.op {
Op::Empty => 0,
Op::Additive(_) => 1,
Op::Multiplicative(_) => 1,
};
for phase in 0..=1 {
let reverse = phase != 0;
(*candidate).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 new_forward_total = if reverse { forward_total } else { resolve_context.available.as_ref().unwrap().borrow().elem.value.op.combine(forward_total, (*candidate).borrow().elem.value.value) };
let new_reverse_total = if reverse { resolve_context.available.as_ref().unwrap().borrow().elem.value.op.combine(reverse_total, (*candidate).borrow().elem.value.value) } else { reverse_total };
match &mut resolve_context.available.as_ref().unwrap().borrow_mut().elem.value.op {
Op::Empty => panic!(),
Op::Additive(link) => link.push_node(candidate),
Op::Multiplicative(link) => link.push_node(candidate),
};
iterate_possible_left_nodes(resolve_context, right_node_context,
&local_availability, local_recruitment_loc,
new_forward_count, new_reverse_count,
new_forward_total, new_reverse_total);
for _ in 0..1 {
if (new_forward_count == 0) || ((new_forward_count + new_reverse_count) < 2) {
break; }
let raw_res = resolve_context.available.as_ref().unwrap().borrow().elem.value.op.realize(
new_forward_total,
new_reverse_total);
if let Some(res) = raw_res {
resolve_context.available.as_ref().unwrap().borrow_mut().elem.value.value = res;
if local_availability.count == 1 {
if res == resolve_context.goal {
print_result(&resolve_context.available.as_ref().unwrap().borrow().elem.value);
}
} else {
for phase2 in 0..=1 {
explore_addition_of_right_node(resolve_context, &local_availability,
Some(right_node_context.inherited_recruitment_bookmark),
if phase2 == 1 { Op::Multiplicative(None) } else { Op::Additive(None) });
}
}
}
}
candidate = match &mut resolve_context.available.as_ref().unwrap().borrow_mut().elem.value.op {
Op::Empty => panic!(),
Op::Additive(link) => link.pop_node().unwrap(),
Op::Multiplicative(link) => link.pop_node().unwrap(),
};
}
let temp = Rc::clone(&candidate);
(*local_recruitment_loc).borrow_mut().next.push_node(candidate);
backing = temp;
local_recruitment_loc = &backing;
} else { break; }
}
}
fn print_result(value: &ReadyValue) {
println!("{}", string_recursive(value));
}
fn string_recursive(value: &ReadyValue) -> String {
let continuation = |link: Option<&Rc<RefCell<Node<Contribution>>>>, is_multiplicative| {
let mut res = String::new();
let mut iter = link;
let mut is_first = true;
let mut num_rev = 0usize;
let mut backing: Link<Contribution>;
res.push_str("(");
loop {
if let Some(concrete) = iter {
if (*concrete).borrow().elem.reverse {
num_rev += 1;
} else {
if !is_first {
res.push_str(if is_multiplicative { " *" } else { " +" });
}
is_first = false;
res.push_str(" ");
res.push_str(&string_recursive(&(*concrete).borrow().elem.value));
}
let step1 = (*concrete).borrow();
let step3 = step1.next.as_ref();
let step4 = step3.map(|inner| { Rc::clone(inner) });
drop(step3);
drop(step1);
backing = step4.as_ref().map(|inner| { Rc::clone(inner) });
iter = backing.as_ref();
} else { break; }
};
if num_rev > 0 {
res.push_str(if is_multiplicative { " /" } else { " -" });
if num_rev > 1 {
res.push_str(" (");
}
}
is_first = true;
iter = link;
loop {
if let Some(concrete) = iter {
if (*concrete).borrow().elem.reverse {
if !is_first {
res.push_str(if is_multiplicative { " *" } else { " +" });
}
is_first = false;
res.push_str(" ");
res.push_str(&string_recursive(&(*concrete).borrow().elem.value));
}
let step1 = (*concrete).borrow();
let step3 = step1.next.as_ref();
let step4 = step3.map(|inner| { Rc::clone(inner) });
drop(step3);
drop(step1);
backing = step4.as_ref().map(|inner| { Rc::clone(inner) });
iter = backing.as_ref();
} else { break; }
};
if num_rev > 1 {
res.push_str(" )");
}
res.push_str(" )");
res
};
match &value.op {
Op::Empty => value.value.to_string(),
Op::Additive(link) => continuation(link.as_ref(), false),
Op::Multiplicative(link) => continuation(link.as_ref(), true)
}
}
fn main() {
resolve(4471u32, &vec![75u32, 10u32, 2u32, 6u32, 7u32, 1u32, 1u32]);
}
In case it's unclear, this solves the Countdown numbers round (except here I put a 4-digit goal and 7 primitives, because computers are just too fast to be able to properly profile this in the 3-digit goal and 6 primitives case) while taking into account the operations being commutative and associative to limit redundancies in the output. The algorithm internally uses linked lists, with somewhat tangled ownership: this is why the indirection between cons cells relies on Rc<RefCell<>>
.
The weak points, in no particular order:
-
At line 41, I have an integrated
enum Op
rather than, say,Option<(bool, Link<Contribution>)>
because it's simpler at times, but it also results in some complexity where I'm sure there could be better ways. -
At line 145 you can see an attempt to repeat myself less often, but it's partial (I couldn't manage to factor the
recruitment_bookmark
itself into that), and even then is more awkward than I'd like (I'd prefer two closures depending on the case, rather than one with an additional Boolean parameter) -
At line 230 I had to shorten the lifetime of the
Ref
I get from theRefCell
, because otherwise I couldn't perform the switcheroo at the end of the loop, and even then that code is more complicated than I'd like. I'm looking for more elegant solutions -
At line 257 you can see one of the techniques I pulled off to be able to avoid repeating my cleanup code; unfortunately I couldn't apply it in other places, as then rustc complained of constant variables being assigned twice and other consequences of interpreting this as a loop. I'm sure I could use a custom type implementing drop instead, but it is worth it for bookkeeping of my local variables?
-
At line 265 you can see I had to split in two what could otherwise be a single-line condition, because for some reason if it is in a single "if" the compiler seems to assume the temporaries (the
Ref
from the explicitborrow()
, in particular) have to last the entirety of the if block, while the same compiler is able to perfectly accept that they don't need to if the same temporaries are computed as part of an earlier statement. -
At line 311, the loop has more lines managing the loop induction variables than it does performing actual work! Now, this case is more complicated than the earlier ones where we'd pop and push, because we browse in read-only fashion and so have to content with multiple ownership, but even then I didn't expect I'd have to
Rc::clone
twice per loop! But if I don't, the borrow checker won't let me overwritebacking
unless I've dropped everything else (apparently owing to the funky lifetime of Ref) at which point I can't updatebacking
any more. DoublingRc::clone
was an act of desperation, and I'm still surprised it worked; thankfully this isn't hot code, but what if it was?