Skip to content

Instantly share code, notes, and snippets.

@BonfaceKilz
Last active February 22, 2021 06:44
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save BonfaceKilz/920ec5ae3632ed7c0d041a198afb509a to your computer and use it in GitHub Desktop.
000. Monchoka! Weekly Algos by your neighbourly scheme-r ;)

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

@jnduli
Copy link

jnduli commented Feb 16, 2021

def partition(n):
    l, r = 0, 1
    while l < len(n) and r < len(n):
        # loop until we find first odd number
        while l < len(n) and n[l] % 2 == 0:
            l += 1
            r += 1
        while r < len(n) and n[r] % 2 != 0:
            r += 1
        if r >= len(n) or l >= len(n):
            continue
        n[l], n[r] = n[r], n[l]

@rwanyoike
Copy link

rwanyoike commented Feb 16, 2021

Solution in Python:

def partition(n):
    if len(n) < 2:
        return n
    head = 0
    tail = len(n) - 1
    while True:
        # head even; tail odd
        if (n[head] % 2 == 0) and (n[tail] % 2 != 0):
            head += 1
            tail -= 1
        # head odd; tail even
        elif (n[head] % 2 != 0) and (n[tail] % 2 == 0):
            n[head], n[tail] = n[tail], n[head]
            head += 1
            tail -= 1
        # head odd; tail odd
        elif (n[head] % 2 != 0) and (n[tail] % 2 != 0):
            tail -= 1
        # head even; tain even
        elif (n[head] % 2 == 0) and (n[tail] % 2 == 0):
            head += 1
        if head >= tail:
            break
    return n

@kodesoul
Copy link

Soution in Rust:

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

    even.iter()
        .chain(odd.iter())
        .copied()
        .collect()
}

@dmatano
Copy link

dmatano commented Feb 16, 2021

Solution in Python:

def partition(n):
    if len(n) < 2:
        return n
    head = 0
    tail = len(n) - 1
    while True:
        # head even; tail odd
        if (n[head] % 2 == 0) and (n[tail] % 2 != 0):
            head += 1
            tail -= 1
        # head odd; tail even
        elif (n[head] % 2 != 0) and (n[tail] % 2 == 0):
            n[head], n[tail] = n[tail], n[head]
            head += 1
            tail -= 1
        # head odd; tail odd
        elif (n[head] % 2 != 0) and (n[tail] % 2 != 0):
            tail -= 1
        # head even; tain even
        elif (n[head] % 2 == 0) and (n[tail] % 2 == 0):
            head += 1
        if head >= tail:
            break
    return n

This is great. I would've solved it the same way :)

@BonfaceKilz
Copy link
Author

Here are my solutions:

def partition_array(my_arr):
    l, r = 0, len(my_arr) - 1
    is_even = lambda x: x % 2 == 0
    is_odd = lambda x: not(is_even(x))
    while True:
        if l >= r:
            break
        if is_odd(my_arr[l]) and is_odd(my_arr[r]):
            r -= 1
            continue
        if is_even(my_arr[l]) and is_even(my_arr[r]):
            l += 1
            continue
        if is_odd(my_arr[l]) and is_even(my_arr[r]):
            my_arr[l], my_arr[r] = my_arr[r], my_arr[l]
        r -= 1
        l += 1

    return my_arr

Though I prefer this since IMHO it's more succinct:

def partition_array_(my_arr):
    l, r = 0, len(my_arr) - 1
    is_even = lambda x: x % 2 == 0
    is_odd = lambda x: not(is_even(x))
    while True:
        if l >= r:
            break
        l_, r_ = l, r
        if is_odd(my_arr[r_]):
            r -= 1
        if is_even(my_arr[l_]):
            l += 1
        if is_odd(my_arr[l_]) and is_even(my_arr[r_]):
            my_arr[l_], my_arr[r_] = my_arr[r_], my_arr[l_]
    return my_arr

@BonfaceKilz
Copy link
Author

BonfaceKilz commented Feb 18, 2021 via email

@BonfaceKilz
Copy link
Author

BonfaceKilz commented Feb 18, 2021 via email

@kodesoul
Copy link

kodesoul commented Feb 19, 2021

@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.

@kodesoul
Copy link

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

@BonfaceKilz
Copy link
Author

BonfaceKilz commented Feb 22, 2021 via email

@BonfaceKilz
Copy link
Author

BonfaceKilz commented Feb 22, 2021 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment