000. Monchoka! Weekly Algos by your neighbourly scheme-r ;)

00 Binary Partitions.md

Prelude

Hi folks! Much thanks for last weeks submissions!

Here is a (very) interesting blogpost about how FOSDEM 2021 was setup: https://www.matrix.org/blog/posts. Perhaps something we should try out as a community as time goes by?

That withstanding, this week I've been thinking about backups. How do you back up your systems? At work, if you can talk about it, what's your backup strategy?

Last Week's Challenge

Issue 0: https://is.gd/b99nd2

Mailing List discussion: https://groups.google.com/g/nairobi-gnu/c/H6qSbSQ7rTk

If you get the bandwidth, hack at the problems at the submission links above-- It's a nice way to get comments on your code \m/\m/.

This Week's Challenge

Write a procedure that partions a list into even and odd numbers. Order doesn't really matter.

Constraint: Try doing this without creating a new array.

Examples:
Input: n = [1, 2, 3, 4, 5, 6, 7]
Output: [2, 4, 6, 1, 3, 5, 7]

Input: n = []
Output: []

Input: n = [1, 2]
Output: [2, 1]

Post your solutions as comments to this gist

@BonfaceKilz There's a method called partition_in_place in rust nighly.

fn partition(vec: Vec<i32>) -> Vec<i32> {
    let mut vec = vec;
    vec.iter_mut()
        .partition_in_place(|&n| n%2 == 0)
}

The problem is that it isn't stable.

I could reduce one heap allocation by taking ownership of the even and odd vectors.

fn partition(vec: Vec<i32>) -> Vec<i32> {
    let (even,odd): (Vec<i32>,Vec<i32>) = vec.iter().partition(|&n| n%2==0);

    even.into_iter()
        .chain(odd.into_iter())
        .collect()
}

I could create a functional approach that doesn't make a heap allocation but it would require
more lines of code. I'll post the solution today.

This works without making extra heap allocations.

#[derive(PartialEq,PartialOrd,Eq,Ord)]
enum Parity {
    Even(i32),
    Odd(i32),
}

impl Parity {
    fn wrap(n: i32) -> Self {
        if n%2 == 0 { Self::Even(n) }
        else { Self::Odd(n) }
    }
    fn unwrap(self) -> i32 {
        match self {
            Self::Even(n) => n,
            Self::Odd(n) => n,
        }
    }
}

fn partition(vec: Vec<i32>) -> Vec<i32> {
    let mut vec: Vec<Parity> = vec.into_iter()
        .map(Parity::wrap)
        .collect();

    vec.sort();
    vec.into_iter()
        .map(|n| n.unwrap() )
        .collect()
}

princebett <notifications@github.com> writes:

@BonfaceKilz There's a method called `partition_in_place` in rust nighly. ```{rust} fn partition(vec: Vec<i32>) -> Vec<i32> { let mut vec = vec; vec.iter_mut() .partition_in_place(|&n| n%2 == 0) } ``` The problem is that it isn't stable.

This looks neat!

I could reduce one heap allocation by draining the even and odd vectors. ```{rust} pub fn binary_partition(vec: Vec<i32>) -> Vec<i32> { let (mut even,mut odd): (Vec<i32>,Vec<i32>) = vec.iter().partition(|&n| n%2==0); even.drain(..) .chain(odd.drain(..)) .collect() } ``` I could create a functional approach that doesn't make a heap allocation but it would require more lines of code. I'll post the solution today.

More lines of code does not necessarily imply a code smell.

…

-- Bonface M. K. D4F09EB110177E03C28E2FE1F5BBAE1E0392253F Humble GNU Emacs User / Bearer of scheme-y parens Curator: <https://upbookclub.com> / Twitter: @BonfaceKilz

princebett <notifications@github.com> writes:

This works without making extra heap allocations. ```{rust} #[derive(PartialEq,PartialOrd,Eq,Ord)] enum Parity { Even(i32), Odd(i32), } impl Parity { fn wrap(n: i32) -> Self { if n%2 == 0 { Self::Even(n) } else { Self::Odd(n) } } fn unwrap(self) -> i32 { match self { Self::Even(n) => n, Self::Odd(n) => n, } } } fn partition(vec: Vec<i32>) -> Vec<i32> { let mut vec: Vec<Parity> = vec.into_iter() .map(Parity::wrap) .collect(); vec.sort(); vec.into_iter() .map(|n| n.unwrap() ) .collect() } ```

+1 for this although I don't entirely understand what's going on ;). I'll dig deeper into that later \o/

…

-- Bonface M. K. D4F09EB110177E03C28E2FE1F5BBAE1E0392253F Humble GNU Emacs User / Bearer of scheme-y parens Curator: <https://upbookclub.com> / Twitter: @BonfaceKilz