TwoSum problem, popping head/tail from slices

#1

From Reddit I’ve seen this common hiring problem:

It has various solutions, the last one is (in Rust):

fn sums_to_target<T>(arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
    arr.sort_unstable();
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left < right {
        let sum = arr[left] + arr[right];
        if sum == k {
            return true;
        } else if sum < k {
            left += 1;
        } else {
            right -= 1;
        }
    }

    false
}

In D language you probably want to write that solution in a way more similar to this (it lacks some template constraints, please bear with me):

bool sums_to_target2(T)(T[] arr, in T k) {
    arr.sort();

    while (!arr.empty) {
        const sum = arr.front + arr.back;
        if (sum == k) {
            return true;
        } else if (sum < k) {
            arr.popFront;
        } else {
            arr.popBack;
        }
    }

    return false;
}

A similar solution in Rust:

#![feature(nll)]

fn sums_to_target2<T>(mut arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
    use std::cmp::Ordering::*;

    arr.sort_unstable();

    while let (Some(&x), Some(&y)) = (arr.first(), arr.last()) {
        match (x + y).cmp(&k) {
            Less => { arr = &mut arr[1 ..]; },
            Equal => return true,
            Greater => { arr = &mut arr[.. arr.len() - 1]; },
        }
    }

    false
}

Is it a good idea to put in the Rust std lib two functions that implement those pop_first and pop_last?

#2

I’m not exactly sure what you’re looking for, but “remove the first/last element of a slice” as known as split_first/split_last in Rust.

Or, since Rust iterators are more like what (IIRC) D calls a range, maybe you just want .next() and .next_back() on an iterator?

1 Like
#3

So far I’ve failed to find a reasonable solutions using split_first/split_last, but I’ll try again. I have found a solution using .next() and .next_back() but it’s not elegant (it’s painful code):

fn sums_to_target5<T>(arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
    use std::cmp::Ordering::*;

    arr.sort_unstable();
    let mut items = arr.iter();

    let mut x = if let Some(&head) = items.next() {
        head
    } else {
        return false;
    };

    let mut y = if let Some(&tail) = items.next_back() {
        tail
    } else {
        return false;
    };

    loop {
        match (x + y).cmp(&k) {
            Less => {
                if let Some(&head) = items.next() {
                    x = head;
                } else {
                    return false;
                }
            },
            Equal => return true,
            Greater => {
                if let Some(&tail) = items.next_back() {
                    y = tail;
                } else {
                    return false;
                }
            },
        }
    }
}

I’ll try to improve it.

With a peek_back a nice enough solution could be:

fn sums_to_target6<T>(arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
    use std::cmp::Ordering::*;

    arr.sort_unstable();
    let mut items = arr.iter().double_ended_peekable();

    while let (Some(&&x), Some(&&y)) = (items.peek(), items.peek_back()) {
        match (x + y).cmp(&k) {
            Less => { items.next(); },
            Equal => return true,
            Greater => { items.next_back(); },
        }
    }

    false
}
#4

split_first/split_last can be relatively nice when using catch to handle the empty array case (mainly missing destructuring assignment for updating left/right nicely)

fn sums_to_target<T>(arr: &mut [T], k: T) -> bool
where
    T: PartialEq + Ord,
    for<'a> &'a T: Add<Output = T> + PartialEq + Ord,
{
    arr.sort_unstable();

    do catch {
        let (mut left, arr) = arr.split_first()?;
        let (mut right, mut arr) = arr.split_last()?;

        loop {
            match (left + right).cmp(&k) {
                Ordering::Equal => break Some(()),
                Ordering::Less => {
                    let (l, a) = arr.split_first()?;
                    left = l;
                    arr = a;
                }
                Ordering::Greater => {
                    let (r, a) = arr.split_last()?;
                    right = r;
                    arr = a;
                }
            }
        }
    }.is_some()
}

(playground)

EDIT: Also, just realised that if catch is ever fixed to the semantics specified in the RFC this would be simplified by replacing break Some(()) with just break (although that might add some sort of type inference issue since nothing would be constraining the catch block to return an Option).

#5

The same technique actually works even better when applied to next/next_back


fn sums_to_target2<T>(arr: &mut [T], k: T) -> bool
where
    T: PartialEq + Ord,
    for<'a> &'a T: Add<Output = T>,
{
    arr.sort_unstable();
    do catch {
        let mut items = arr.iter();
        let mut x = items.next()?;
        let mut y = items.next_back()?;
        loop {
            match (x + y).cmp(&k) {
                Ordering::Equal => break Some(()),
                Ordering::Less => {
                    x = items.next()?;
                }
                Ordering::Greater => {
                    y = items.next_back()?;
                }
            }
        }
    }.is_some()
}
1 Like
#6

And on stable you can use a “slightly” uglier closure:

fn sums_to_target2<T>(arr: &mut [T], k: T) -> bool
where
    T: PartialEq + Ord,
    for<'a> &'a T: Add<Output = T>,
{
    arr.sort_unstable();
    (|| {
        let mut items = arr.iter();
        let mut x = items.next()?;
        let mut y = items.next_back()?;
        loop {
            match (x + y).cmp(&k) {
                Ordering::Equal   => return Some(()),
                Ordering::Less    => x = items.next()?,
                Ordering::Greater => y = items.next_back()?,
            }
        }
    })().is_some()
}
1 Like
#7

This is the nicest solution I’ve found so far:

#![feature(nll, match_default_bindings, advanced_slice_patterns)]

use std::ops::Add;

fn sums_to_target<T>(mut arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
    use std::cmp::Ordering::*;

    arr.sort_unstable();

    while let [ref x, .., ref y] = arr {
        match (*x + *y).cmp(&k) {
            Less => arr = &mut arr[1 ..],
            Equal => return true,
            Greater => arr = &mut arr[.. arr.len() - 1],
        }
    }

    false
}

fn main() {
    let mut data = [1, 2, 10, 3, 4];
    println!("{}", sums_to_target(&mut data, 2));
    println!("{}", sums_to_target(&mut data, 10));
    println!("{}", sums_to_target(&mut data, 5));
    println!("{}", sums_to_target(&mut data, 14));
}

But I’ve seen that LLVM is not able to remove the bound tests from those arr[1 …] and [… arr.len() - 1], despite arr must have a first and last item to be inside the while.

But is it really necessary for T to be Copy? If T is a BigInteger I’d like to not have to copy/clone it just to sum two of them.

1 Like
#8

It’s not, see the generic bounds I used above. You need to require Add on the reference.

1 Like