The countdown problem was presented in a paper by Graham Hutton with a simple
and elegant solution in Haskell. See the paper here.
In this post I'll implement the same solution in Rust and see how it looks compared to
the original Haskell solution.
What is the problem
From the paper:
Countdown is a popular quiz programme on British television that includes a
numbers game that we shall refer to as the countdown problem. The essence of
the problem is as follows: given a sequence of source numbers and a single target
number, attempt to construct an arithmetic expression using each of the source
numbers at most once, and such that the result of evaluating the expression is the
target number. The given numbers are restricted to being non-zero naturals, as are
the intermediate results during evaluation of the expression.
For eg. Given the numbers [1, 3, 7, 10, 25, 50] and target 765, one solution would
be (1 + 50) âˆ— (25 âˆ’ 10).
Implementation
In the paper, an initial solution is presented which is then optimized. In this post
we will directly implement the final solution.
First we need a way to represent the supported operations. A sum type is ideal for this
and in Rust we can use enum for it:
Haskell
Rust
1
2
3
4
5
dataOp=Add|Sub|Mul|Div
1
2
3
4
5
6
7
#[derive(Copy, Clone)]enumOp{Add,Sub,Mul,Div}
The definitions looks very similar in both languages, though syntax is different. In Rust we also need to derive traits which
allows us to freely copy values of the type in the later program.
Next, we need to define an expression - which is either a number, or two sub-expressions
combined with an operator.
First I added a type alias for Int to keep the code similar to Haskell. We start to see differences - in Rust we cannot define nested
references directly. We could use smart pointer like Box or
Rc.
In our case we go with Rc since there will be shared sub expressions and reference counted object
performs better in that case.
Next, the paper defines some utility functions: to check if an expr is valid and also to apply
an expression and get its result:
Apart from syntax, no major change. We can do pattern matching in Rust similar to
Haskell. However, we always need to think about lifetime of variables - here I chose to
work with reference of Op instead of Op directly. It will be clear why that is better
as we look at other functions that calls this.
Now we get into the core logic of implementation. We need a way to split a list at all possible
points. For eg. [1, 2, 3] to ([1], [2, 3]) and ([1, 2], [3]).
The main difference in the Rust version is the absense of list comprehensions - that
syntactic sugar is not available, but it possible to achieve something similar using macros.
For eg, using the cute crate, we can rewrite the split function as follows:
While this is concise, I'll stick with what we can do with standard Rust in this post.
Next we need a function that returns the list of all permutations of all subsequences of a list.
In the paper it is called subbags and uses predefined functions that returns permutations etc.
We use the permutations function in the itertools crate in Rust for simplicity:
Haskell
Rust
1
2
3
4
5
subbags::[a]->[[a]]subbagsxs=[zs|ys<-subsxs,zs<-permsys]-- subs and perms defined elsewhere
With all the utility functions in place, we are ready to implement the logic for the countdown problem.
The idea is to consider all valid expressions and sub results and combine them to see if we can get the
intended result.
That's it. This is the complete implementation. You can checkout the complete runnable code
here.
Sidenote - adding parallelism
Since our code is written in a functional way it is trivial to make parts of it parallel.
By using the rayon crate and just making two minor changes:
sub_bags(ns).iter() –> sub_bags(ns).par_iter()
Rc –> Arc
this reduces the execution time from ~370ms to ~70ms for the above example.
Summary
Rust is a fairly expressive language and using the functional style is
quite natural. Ownership and lifetimes do get in the way sometimes,
but it is a price worth paying considering the runtime benefits.
Also the compiler error messages are really helpful and guides you to
the right solution.