The task is a simple coding challenge I took part in. It is a spin on the two sum problem.
In the two sum problem you are given an validation sequence A and a test input I. I is valid if it's the sum of any two elements in the A. You can solve this in O(Nlog(N)) by first sorting A first, then using the two pointer technique.
The challenge is worded as follows: "The first 100 numbers of the mine are always secure, but after that, the next number is only safe if it is the sum of 2 numbers in the previous 100".
My solution allows for Mine segments to be generic. I call them Blocks.
It also generic over the validation window size - 100 in the thext of the challenge.
Full solution can be found on my github.
/// Block in a [Mine]. Has blanket implementation for numerical types.
pub trait Block: Eq + Add<Output = Self> + Sized {}
impl<T> Block for T where T: Eq + Add<Output = Self> + Sized {}
#[derive(Debug, Error, PartialEq, Eq)]
pub enum MineError<const VALIDATION_WINDOW_SIZE: usize, B: Block> {
#[error(
"Initialization blocks must have at least: {} blocks. Size of the blocks provided: {0}",
VALIDATION_WINDOW_SIZE
)]
InvalidInitializationBlocksSize,
#[error(
"Validation for block number {1} failed. Invalid block value: {0}.
A block is valid iff it is the sum of any two blocks in the previous: {}.",
VALIDATION_WINDOW_SIZE
)]
InvalidBlock(B, usize),
}
/// Responsible for mining new [Blocks](Block).
/// A new block is valid [iff](https://en.wikipedia.org/wiki/If_and_only_if) it's the
/// sum of any two blocks in the previous [VALIDATION_WINDOW_SIZE] blocks.
///
/// # Performance
/// - The size of [Mine] scales with O(VALIDATION_WINDOW_SIZE<sup>2</sup>).
///
/// [VALIDATION_WINDOW_SIZE]: Mine<VALIDATION_WINDOW_SIZE>
#[derive(Clone, Debug)]
pub struct Mine<const VALIDATION_WINDOW_SIZE: usize, B: Block + Hash + Copy> {
/// Holds [VALIDATION_WINDOW_SIZE] blocks used for validation.
validation_blocks: VecDeque<B>,
/// Holds all the possible two element sums from the [validation_blocks](Self::validation_blocks).
/// Used for quick validation of new blocks.
block_pair_sums: HashMultiSet<B>,
/// Used for tracking how many blocks have been validated
total_blocks: usize,
}
impl<const VALIDATION_WINDOW_SIZE: usize, B> Mine<VALIDATION_WINDOW_SIZE, B>
where
B: Block + Hash + Copy,
for<'a> &'a B: Add<&'a B, Output = B>,
for<'a> B: Add<&'a B, Output = B>,
{
/// Create a new mine with given `initialization_blocks`.
/// No validation is performed on the initialization blocks.
///
/// # Performance
/// This is a potentially costly operation with the running time of O(VALIDATION_WINDOW_SIZE<sup>2</sup>).
pub fn new(initialization_blocks: [B; VALIDATION_WINDOW_SIZE]) -> Self {
// Allocating half the max size. Worst case scenario with no overlapping sums
// requires only 1 more allocation.
let capacity = VALIDATION_WINDOW_SIZE.pow(2) / 2;
let mut sums = HashMultiSet::with_capacity(capacity);
for (i, first) in initialization_blocks[0..VALIDATION_WINDOW_SIZE - 1]
.iter()
.enumerate()
{
for second in initialization_blocks.iter().skip(i + 1) {
sums.insert(first + second);
}
}
Self {
validation_blocks: VecDeque::from(initialization_blocks),
block_pair_sums: sums,
total_blocks: VALIDATION_WINDOW_SIZE,
}
}
/// Try to extend the [Mine] by a single [Block] `new_block`.
/// If the validation is successful the mine is extended, otherwise
/// a an error [MineError::InvalidBlock] is returned. Details on validation
/// can be seen in [Mine] documentation.
///
/// If you want to try and add many blocks see [Mine::try_extend].
pub fn try_extend_one(
&mut self,
new_block: B,
) -> Result<(), MineError<VALIDATION_WINDOW_SIZE, B>> {
if !self.block_pair_sums.contains(&new_block) {
Err(MineError::InvalidBlock(new_block, self.total_blocks + 1))
} else {
// New block value is already validated. It is now correct
// to remove any previous entry and sum entry.
let old_block = self
.validation_blocks
.pop_front()
.expect("Mine always has VALIDATION_WINDOW_SIZE blocks");
for block in self.validation_blocks.iter() {
// remove all sums where the first block was a summand
self.block_pair_sums.remove(&(old_block + block));
// add new sums where the new block is a summand
self.block_pair_sums.insert(new_block + block);
}
self.validation_blocks.push_back(new_block);
self.total_blocks += 1;
Ok(())
}
}
}
Window size in the given test data was 100. So the O(N2) size of the hash set didn't seem like a problem. I've tried the two pointer approach for validation. But removing / inserting elements to an ordered set seemed to be performing worse than this solution.
I didn't want to put the Hash bound on Block as that seems a part of the implementation of mine. The bounds I used for reference addition on the other hand, bother me but I still prefer them to dereferencing in the code.
Problem with perf tests
I find it hard to performance try_extend_one using criterion. The crux of the problem for me is that the size of the elements in the validation sequence has to be increasing (Assuming no more than one 0 in the initial sequence). Since criterion needs a lot of iterations to give good results, this led to overflow. Maybe I could play with criterion setup to reduce the number of iterations but I assume this would sacrifice precision. Other option I have is to clone the entire Mine on every iteration then I guess I'm not really measuring try_extend_one. Any advice?
I'm mostly interested in building a performant solution to this problem. Any other comments are also welcome.
PartialOrd + Ord-- sorry, you lost me there. How does partial add anything, given a total ordering? And similarly for equality. \$\endgroup\$Ordbound impliesPartialOrd + Eq, + PartialEq. It might be a reflex from using derive macros. My implementation requires onlyAddandHash. EvenEqis unnecessary though I'm not inclined to remove it, as it communicates the use.. \$\endgroup\$