1
\$\begingroup\$

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.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ This is Code Review, and comments are an important part of the code. So don't remove them "for brevity" - we want to see the full code, even if that makes it long! Even if the comments are longer than the code you've shown, that's not a lot here on CR. Please edit to reinstate the full code (we can't review linked code, for a number of reasons). \$\endgroup\$ Commented Sep 4, 2023 at 14:31
  • \$\begingroup\$ PartialOrd + Ord -- sorry, you lost me there. How does partial add anything, given a total ordering? And similarly for equality. \$\endgroup\$
    – J_H
    Commented Sep 4, 2023 at 23:31
  • \$\begingroup\$ Just read this a second time for not finding rhythm nor rhyme on 1st take. A window sliding up an array is valid if any two numbers in it sum up to a target? What are the blocks about? \$\endgroup\$
    – greybeard
    Commented Sep 5, 2023 at 5:28
  • \$\begingroup\$ @J_H you are correct. This is a mistake i often do. Ord bound implies PartialOrd + Eq, + PartialEq. It might be a reflex from using derive macros. My implementation requires only Add and Hash. Even Eq is unnecessary though I'm not inclined to remove it, as it communicates the use.. \$\endgroup\$ Commented Sep 6, 2023 at 12:59
  • \$\begingroup\$ @greybeard I'm sorry for that. I've made some edits. Calling the validation sequence an array was misleading. I hope it is clearer now. A block is just an abstraction over something that can be added and compared to it self. As that is what is needed to validate it as the next building block of the mine. \$\endgroup\$ Commented Sep 6, 2023 at 13:16

2 Answers 2

1
\$\begingroup\$

Hmmm, interesting approach, consuming quadratic memory to save time.

In the copy-n-pasted Cargo.toml you probably intended "edition = 2023".


Informative comments

/// Block in a [Mine]. Has blanket implementation for numerical types.
pub trait Block: Eq + Add... + Sized {}

Thank you for the comment. It is the start of something helpful.

An URL citation of the original problem would have been helpful. Certainly the mention of "numerical" is a useful hint.

What I really wanted to know at this point is that a Block

  • is a positive integer,
  • which can exceed 2 ** 64 but will fit within a u128.

nit: Consider renaming to just WINDOW_SIZE or even WINDOW, with the comment spelling out its validation role.


messages that are diagnostic

        "Initialization blocks must have at least: {} blocks. Size of the blocks provided: {0}",

nit, grammar: Strike the first : colon.

The "blocks ... blocks" remark, about e.g. 100 initialization integers which must each have at least {100 bits?, 100 integers?}, threw me for a moment. Please prefer singular "The initialization block" "The initial blocks", to clarify.

EDIT

The collective noun "a block", such as "a block of numbers", is what I was getting hung up on. What we're shooting for is: Of a great many blocks, we can apply an "initial" adjective to the first few, the ones that shall be unconditionally accepted. If a block is not an initial block, then it must survive a windowed validation process. The diagnostic seems to be speaking of the length of some grouping, a grouping for which we've not yet introduced a Defined Term.

    /// Used for tracking how many blocks have been validated
    total_blocks: usize,

Go with active verb of "Tracks how many ..."


beef up the Block trait

pub struct Mine<..., B: Block + Hash + Copy> {
...
impl ... Mine<..., B>
where
    B: Block + Hash + Copy,
...

Is there a use case for an unhashable uncopyable Block?

I feel they should be part of the trait.


range limits

    /// No validation is performed on the initialization blocks.

I feel it is sensible to tell the compiler that every Block is positive, and has limited magnitude. It can help with proofs about whether overflow is possible, and so can affect generated bounds checks and benchmark timings.

nit, typo: "mine is extended, otherwise a an error"


algorithm

try_extend_one() is very clear, thank you. It took a bit of setup work to make that function a walk in the park.

Personally, I had in mind sequentially scanning and then making nested probes of a HashMap, in the hopes that reads are cheaper than writes. Also, a Block that succeeds can terminate early. And seeing sums that are too large also admits of early termination.

I am a little surprised you found that 100 (deterministic!) writes plus 100 deletes winds up being cheaper in practice.

I encourage you to publish benchmark results in your github repo that folks can read even if they've not run the code.


modulo results

Choose an arbitrary modulus M. When deciding if a + b might sum to c, we can ask whether a % M and b % M are compatible with (a + b) % M. With decimal notation and an M of ten, examining the units digits will be instructive.

If a program grouped the 100 candidates by, say, the three low-order bits (.5 × log2(WINDOW_SIZE)), that may let us ignore the seven eighths of candidates which couldn't possibly produce the proper sum. The speedup would only increase as window size increases.


This codebase achieves its design goals.

I would be willing to delegate or accept maintenance tasks on it.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the comment. 1) I didn't wanna cite the source of the challenge since it seems to still be open so it felt wrong. 1.1) I felt the Add trait bound combined with the definition of block validity does enough to communicate what a block is. But those two are separated. You have to look at the Mine to understand what a block is. 2) Initialization blocks should be renamed. Those are tough to understand constructions. 3) A two pointer impl uses Eq instead of Hash. Copy seems really strict. I believe this decision is hard to make in a toy task without knowing about intended usage \$\endgroup\$ Commented Sep 6, 2023 at 21:42
  • 1
    \$\begingroup\$ About performance. The idea was that window size is a constant compared to the number of possible validated values afterwards. That would justify sacrificing performance of new for marginal gains in try_extend_one(). I no longer feel this to be correct. Also my benchmarks were broken :D I will post the full explanation in form of an answer asap. \$\endgroup\$ Commented Sep 6, 2023 at 21:49
  • 1
    \$\begingroup\$ would be willing to delegate or accept maintenance tasks on it is an excellent measure of program code quality. \$\endgroup\$
    – greybeard
    Commented Sep 7, 2023 at 5:21
0
\$\begingroup\$

I want to discuss the motivation behind the solution in the question and the process in which I found the solution posted through the question to be bad.

For brevity I will use the following notation:

  • B - short for block, type of the numerical values in the mine
  • I - validation sequence size, size of initial data.
  • N - number of iterations for valid blocks after initialization

Initially my implementation was driven by:

  • I is fixed
  • N >> I

My focus was to create a fast method for validating entries after initialization. Mine::try_extend one and Mine::new. Two implementations came to mind.

  1. Solve the two sum problem using two pointer technique over a sorted validation sequence - TwoPtrMine
  2. Solve the two sum problem by precomputing all possible sums and storing them in a HashSet - HashMine

Both solutions have O(I) running time for Mine::try_extend one. Running time for TwoPtrMine::new is O(Ilog2I) and O(I) memory. HashMine::new is O(I2) running time and memory.

This should have signaled the 1st solution is superior but I wanted to test how Mine::try_extend_one performed in both implementations[1]. Since use cases are unknown, maybe sacrificing initialization performance is worth for possible marginal gains in performance of validating new entries.

I've created both solutions and used criterion to test the performance. Expectedly TwoPtrMine::new performed better. But that was not what I was interested in testing. Testing Mine::try_extend_one was unexpectedly hard. I got results that didn't depend on $I$. This was a red flag, but it took me some time to realize I was only testing the error path.

A walk with my duck got me to realize I've misjudged the problem. The key idea I initially missed was that N is bounded[2]. To see why imagine the initialization set to be as small as possible[3]: [1;I]. Then the smallest valid value we can give to Mine::try_extend_one is 2, and crucially we can only do that I-1 times. Generally speaking every I entries the smallest valid entry value must be doubled[4]. By continuing this logic we can see N < I * B::Bits. In the case of B = u128 and I=100 that is merely 12 800 iterations.

This informed me that trying to test just the running time of Mine::try_extend_one is probably not a good idea. At least not using criterion.

Bellow is a two pointer solution for completeness - I haven't given it too much effort.

Mine trait:

/// 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.
///
/// [VALIDATION_WINDOW_SIZE]: Mine<VALIDATION_WINDOW_SIZE>s
pub trait Mine<const VALIDATION_WINDOW_SIZE: usize, B: Block> {
    /// Create a new mine with given `initialization_blocks`.
    /// No validation is performed on the initialization blocks.
    fn new(initialization_blocks: [B; VALIDATION_WINDOW_SIZE]) -> Self;
    /// Try to extend the [Mine] with all the items from the
    /// `blocks` iterator. The method is successful if all
    /// the blocks are successfully added, or the iterator is empty. Otherwise the
    /// error [MineError::InvalidBlock] of the first invalid block
    /// is returned. **IMPORTANT:** Blocks prior to the invalid block are still added
    /// to the mine.
    fn try_extend_one(&mut self, new_block: B) -> Result<(), MineError<VALIDATION_WINDOW_SIZE, B>>;

    /// Same as [Mine::new] except if the initialization blocks fail to convert
    /// to the desired array [MineError::InvalidInitializationBlocksSize]
    /// is returned.
    fn try_new(
        initialization_blocks: impl TryInto<[B; VALIDATION_WINDOW_SIZE]>,
    ) -> Result<Self, MineError<VALIDATION_WINDOW_SIZE, B>>
    where
        Self: Sized,
    {
        let initialization_blocks: [B; VALIDATION_WINDOW_SIZE] =
            initialization_blocks.try_into().map_err(|_| {
                MineError::<VALIDATION_WINDOW_SIZE, B>::InvalidInitializationSequenceLen
            })?;

        Ok(Self::new(initialization_blocks))
    }

    /// Try to extend the [Mine] with all the items from the
    /// `blocks` iterator. The method is successful if all
    /// the blocks are successfully added, or the iterator is empty. Otherwise the
    /// error [MineError::InvalidBlock] of the first invalid block
    /// is returned. **IMPORTANT:** Blocks prior to the invalid block are still added
    /// to the mine.
    fn try_extend(
        &mut self,
        blocks: impl IntoIterator<Item = B>,
    ) -> Result<(), MineError<VALIDATION_WINDOW_SIZE, B>> {
        for block in blocks {
            self.try_extend_one(block)?
        }
        Ok(())
    }

    /// Try and create and extend a Mine from a single iterator.
    /// First [VALIDATION_WINDOW_SIZE] elements of `blocks` are used to create the mine.
    /// The remainder of elements are used to try_extend the mine.
    ///
    /// # Errors
    /// - If the `blocks` iterator length is less than [VALIDATION_WINDOW_SIZE] then
    /// [MineError::InvalidInitializationSequenceLen] is returned.
    /// - If any remaining element can't be validated [MineError::InvalidBlock] is returned.
    ///
    /// [VALIDATION_WINDOW_SIZE]: Mine<VALIDATION_WINDOW_SIZE>
    fn try_create_and_extend(
        blocks: impl IntoIterator<Item = B>,
    ) -> Result<(), MineError<VALIDATION_WINDOW_SIZE, B>>
    where
        Self: Sized,
    {
        let (initialization_blocks, remaining_blocks) =
            take_with_remainder(blocks.into_iter(), VALIDATION_WINDOW_SIZE);

        let initialization_blocks = initialization_blocks
            .try_into()
            .map_err(|_| MineError::InvalidInitializationSequenceLen)?;

        let mut mine = Self::new(initialization_blocks);

        mine.try_extend(remaining_blocks)
    }
}

Two pointer implementation:

use crate::mine::{Block, Mine, MineError};
use std::{collections::VecDeque, ops::Add};

/// Concrete implementation of [Mine]
#[derive(Clone, Debug)]
pub struct TwoPtrMine<const VALIDATION_WINDOW_SIZE: usize, B: Block + Copy + Ord> {
    // TODO: could try RingBuffer
    /// 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).
    // TODO: try using an array
    /// Used for quick validation of new blocks.
    ordered_validation_blocks: Vec<B>,
    /// Tracks how many blocks have been validated
    total_blocks: usize,
}

impl<const VALIDATION_WINDOW_SIZE: usize, B> Mine<VALIDATION_WINDOW_SIZE, B>
    for TwoPtrMine<VALIDATION_WINDOW_SIZE, B>
where
    B: Block + Copy + Ord,
    for<'a> &'a B: Add<&'a B, Output = B>,
    for<'a> B: Add<&'a B, Output = B>,
{
    fn new(mut initialization_blocks: [B; VALIDATION_WINDOW_SIZE]) -> Self {
        let validation_blocks = initialization_blocks;
        initialization_blocks.sort_unstable();

        Self {
            validation_blocks: VecDeque::from(validation_blocks),
            ordered_validation_blocks: Vec::from(initialization_blocks),
            total_blocks: validation_blocks.len(),
        }
    }

    fn try_extend_one(
        &mut self,
        new_block: B,
    ) -> Result<(), crate::mine::MineError<VALIDATION_WINDOW_SIZE, B>> {
        // CHECK NEW BLOCK VALIDITY

        let mut min_to_max = self.ordered_validation_blocks.iter().enumerate();
        let mut max_to_min = self.ordered_validation_blocks.iter().enumerate().rev();

        let mut min_item = min_to_max.next();
        let mut max_item = max_to_min.next();

        while let (Some((i, min)), Some((j, max))) = (min_item, max_item) {
            // all possible (min, max) pairs exhausted
            if i == j {
                return Err(crate::mine::MineError::InvalidBlock(
                    new_block,
                    self.total_blocks + 1,
                ));
            }
            match (min + max).cmp(&new_block) {
                // min element can't be a part of the solution pair
                std::cmp::Ordering::Less => min_item = min_to_max.next(),
                // found solution pair
                std::cmp::Ordering::Equal => break,
                // max element can't be a part of the solution pair
                std::cmp::Ordering::Greater => max_item = max_to_min.next(),
            }

            // TODO: we can search for the old block in this loop as an optimization attempt
        }

        // NEW BLOCK IS VALID
        // now we can safely remove/insert items to validation blocks

        let old_block = self
            .validation_blocks
            .pop_front()
            .expect("validation_blocks have a minimum size VALIDATION_WINDOW_SIZE");
        self.validation_blocks.push_back(new_block);

        // TODO:
        // - try mapping validation blocks to ordered validation blocks when you perform sort
        // - try linear search, for small enough windows / block sizes it may be faster
        let old_block_idx = self
            .ordered_validation_blocks
            .binary_search(&old_block)
            .unwrap_or_else(|i| i);
        self.ordered_validation_blocks.remove(old_block_idx);

        let new_block_idx = self
            .ordered_validation_blocks
            .binary_search(&new_block)
            .unwrap_or_else(|i| i);
        self.ordered_validation_blocks
            .insert(new_block_idx, new_block);

        self.total_blocks += 1;

        Ok(())
    }
}

I've done performance testing on try_create_and_extend. TwoPointerMine outperforms HashMine significantly.

1 : This was probably a futile attempt. I reads and writes to a hash map should be expensive.

2 : N is not bounded by B::SIZE/2 but something far less

3: having [0,0, 1, ..] would be trivial as we could just keep entering zeroes

4: this is not precise but the bound remains true. I+1th value must be doubled

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.