 # TwoSum problem, popping head/tail from slices

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?

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

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() {
} 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() {
} 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
}``````

`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()
}
``````

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`).

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

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

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

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

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

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

1 Like