Proposal for a new exercise: Moving Day

Exercism Building Exercism
1

My last two ideas for new exercises didn’t gain much attention but I’ll try again, with a new idea.

Moving Day

Description

Your friend Sean is writing a program that manages a TODO list and is asking for your help.
Users should be able to move some selected items to a different location within the list.

Specifically:

  • The selected items are grouped together.
  • The relative order of the selected items does not change.
  • The relative order of the unselected items does not change.
  • All items above the target index in the original list are still above that index in the reordered list.
  • All items at or below the target index in the original list are still at or below that index in the reordered list.

For example:

In the list below on the left side the user has selected seven items.
They move them to the index that is currently occupied by “Mopping floors”.
The result is the list on the right side.

Before:                                After:
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓         ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃   Washing dishes           ┃         ┃   Washing dishes           ┃
┃   Unloading the dishwasher ┃         ┃   Unloading the dishwasher ┃
┃   Taking out the trash     ┃         ┃   Taking out the trash     ┃
┃ ☒ Vacuuming                ┃──┐      ┃   Doing laundry            ┃
┃ ☒ Sweeping floors          ┃──┤      ┃   Putting away laundry     ┃
┃   Doing laundry            ┃  │      ┃ ☒ Vacuuming                ┃
┃   Putting away laundry     ┃  │      ┃ ☒ Sweeping floors          ┃
┃ ☒ Mopping floors           ┃──┤  ╭──▸┃ ☒ Mopping floors           ┃
┃ ☒ Dusting surfaces         ┃──┤  │   ┃ ☒ Dusting surfaces         ┃
┃   Making the bed           ┃  │  │   ┃ ☒ Cleaning the bathroom    ┃
┃   Changing bed sheets      ┃  ├──╯   ┃ ☒ Wiping kitchen counters  ┃
┃ ☒ Cleaning the bathroom    ┃──┤      ┃ ☒ Cleaning out the fridge  ┃
┃   Cooking meals            ┃  │      ┃   Making the bed           ┃
┃ ☒ Wiping kitchen counters  ┃──┤      ┃   Changing bed sheets      ┃
┃   Grocery shopping         ┃  │      ┃   Cooking meals            ┃
┃ ☒ Cleaning out the fridge  ┃──┘      ┃   Grocery shopping         ┃
┃   Organizing clutter       ┃         ┃   Organizing clutter       ┃
┃   Watering plants          ┃         ┃   Watering plants          ┃
┃   Walking the dog          ┃         ┃   Walking the dog          ┃
┃   Taking out recycling     ┃         ┃   Taking out recycling     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛         ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
  • The selected items are now grouped together, from “Vacuuming” to “Cleaning out the fridge”.
  • The relative order of the selected items did not change, e.g. “Vacuuming” comes before “Sweeping floors”.
  • The relative order of the unselected items did not change, e.g. “Putting away laundry” comes before “Making the bed”.
  • All items above “Mopping floors” in the original list are still above “Mopping floors”.
  • All items at or below “Mopping floors” in the original list are still at or below “Mopping floors”.
4 Likes
2

Initial Stub and Tests (Python)

# file moving_day.py

def move_around(items: list[tuple[bool, str]], target_idx: int) -> None:
    """Move the selected items to the target index."""
    # Happy Coding!

# file moving_day_test.py

import unittest
from moving_day import move_around


class MoveAroundTests(unittest.TestCase):

    def test_move_one_item_to_the_front(self) -> None:
        items = [
                 (False, "Solve problem"),
                 (False, "Run Tests"),
                 (True, "Read instructions"),
                 ]
        move_around(items, 0)
        self.assertEqual(items, [
                 (True, "Read instructions"),
                 (False, "Solve problem"),
                 (False, "Run Tests"),
                 ])

    def test_move_one_item_to_the_back(self) -> None:
        items = [
                 (True, "Profit"),
                 (False, "Collect underpants"),
                 (False, "???"),
                 ]
        move_around(items, 3)
        self.assertEqual(items, [
                 (False, "Collect underpants"),
                 (False, "???"),
                 (True, "Profit"),
                 ])

    def test_move_one_item_to_the_middle(self) -> None:
        items = [
                 (False, "Idea"),
                 (True, "Marketing"),
                 (False, "Research"),
                 (False, "Build"),
                 (False, "Publish"),
                 ]
        move_around(items, 2)
        self.assertEqual(items, [
                 (False, "Idea"),
                 (True, "Marketing"),
                 (False, "Research"),
                 (False, "Build"),
                 (False, "Publish"),
                 ])

    def test_move_multiple_items_to_the_front(self) -> None:
        items = [
                 (False, "My Brilliant Friend"),
                 (False, "The Corrections"),
                 (False, "2666"),
                 (True, "The Underground Railroad"),
                 (False, "Never Let Me Go"),
                 (True, "The Road"),
                 (False, "Lincoln in the Bardo"),
                 (True, "Bewilderment"),
                 (True, "Atonement"),
                 (False, "H Is for Hawk"),
                 ]
        move_around(items, 0)
        self.assertEqual(items, [
                 (True, "The Underground Railroad"),
                 (True, "The Road"),
                 (True, "Bewilderment"),
                 (True, "Atonement"),
                 (False, "My Brilliant Friend"),
                 (False, "The Corrections"),
                 (False, "2666"),
                 (False, "Never Let Me Go"),
                 (False, "Lincoln in the Bardo"),
                 (False, "H Is for Hawk"),
                 ])

    def test_move_multiple_items_to_the_back(self) -> None:
        items = [
                 (False, "Kid A"),
                 (False, "Stankonia"),
                 (False, "Is This It"),
                 (False, "The Idler Wheel"),
                 (True, "Elephant"),
                 (True, "Under Construction"),
                 (False, "Back to Black"),
                 (False, "Yankee Hotel Foxtrot"),
                 (True, "Kala"),
                 (True, "Vespertine"),
                 ]
        move_around(items, 10)
        self.assertEqual(items, [
                 (False, "Kid A"),
                 (False, "Stankonia"),
                 (False, "Is This It"),
                 (False, "The Idler Wheel"),
                 (False, "Back to Black"),
                 (False, "Yankee Hotel Foxtrot"),
                 (True, "Elephant"),
                 (True, "Under Construction"),
                 (True, "Kala"),
                 (True, "Vespertine"),
                 ])

    def test_move_multiple_items_to_the_middle(self) -> None:
        items = [
                 (False, "There Will Be Blood"),
                 (True, "Parasite"),
                 (True, "Spirited Away"),
                 (False, "Eternal Sunshine of the Spotless Mind"),
                 (True, "The Grand Budapest Hotel"),
                 (False, "Before Sunset"),
                 (True, "Lady Bird"),
                 (False, "28 Days Later"),
                 (False, "Memento"),
                 (True, "Lost in Translation"),
                 ]
        move_around(items, 3)
        self.assertEqual(items, [
                 (False, "There Will Be Blood"),
                 (True, "Parasite"),
                 (True, "Spirited Away"),
                 (True, "The Grand Budapest Hotel"),
                 (True, "Lady Bird"),
                 (True, "Lost in Translation"),
                 (False, "Eternal Sunshine of the Spotless Mind"),
                 (False, "Before Sunset"),
                 (False, "28 Days Later"),
                 (False, "Memento"),
                 ])
3

Example solutions

Straightforward with O(n) auxiliary memory

def move_around(items: list[tuple[bool, str]], target_idx: int) -> None:
    """Move the selected items to the target index."""
    num_unselected_before_target = sum(
            not selected for selected, _ in items[:target_idx])
    selected = [item for item in items if item[0]]
    not_selected = [item for item in items if not item[0]]
    items[:] = (
            not_selected[:num_unselected_before_target] +
            selected +
            not_selected[num_unselected_before_target:])

Alternative solution with O(n) auxiliary memory

def move_around(items: list[tuple[bool, str]], target_idx: int) -> None:
    """Move the selected items to the target index."""
    part1, part2 = items[:target_idx], items[target_idx:]
    # note: in Python .sort() uses a stable sorting algorithm
    part1.sort(key=lambda t: t[0])
    part2.sort(key=lambda t: not t[0])
    items[:target_idx], items[target_idx:] = part1, part2

More complicated, without auxiliary memory

def reverse(items, begin: int, end: int) -> None:
    a, b = begin, end - 1
    while a < b:
        items[a], items[b] = items[b], items[a]
        a += 1
        b -= 1


def rotate(items, begin: int, mid: int, end: int) -> int:
    if begin != mid != end:
        reverse(items, begin, mid)
        reverse(items, mid, end)
        reverse(items, begin, end)
    return begin + end - mid


def stable_partition(items, begin: int, end: int, predicate) -> int:
    if end - begin == 0:
        return begin
    if end - begin == 1:
        return end if predicate(items[begin]) else begin
    if end - begin == 2:
        p1, p2 = predicate(items[begin]), predicate(items[begin + 1])
        if not p1 and p2:
            items[begin], items[begin + 1] = items[begin + 1], items[begin]
        return begin + p1 + p2
    mid = (begin + end) // 2
    x1 = stable_partition(items, begin, mid, predicate)
    x2 = stable_partition(items, mid, end, predicate)
    return rotate(items, x1, mid, x2)


def move_around(items: list[tuple[bool, str]], target_idx: int) -> None:
    """Move the selected items to the target index."""
    # without auxiliary memory
    stable_partition(items, 0, target_idx, lambda t: not t[0])
    stable_partition(items, target_idx, len(items), lambda t: t[0])
4

Discussion

The idea for this exercise comes from an old conference talk C++ Seasoning by Sean Parent which is pretty famous amongst C++ programmers for its proposed rule “No raw loops” and the quote “That’s a rotate”. In one part of the talk the speaker presents some long and complex code that he had to review at Google. He shows how hard it is to understand and reason about the original code and how it can be simplified by using algorithms from the standard library.

He actually presents *two* related problems: One where the user selects a contiguous sublist of items and moves it (“That’s a rotate”), the other allows the user to select multiple disjoint items and move them.
I chose the second one because IMHO it’s more versatile and the implementation is a tiny bit harder.

This exercise can be solved in multiple ways:

  1. By creating three lists, one of the unselected items before the insertion point, one for the selected items, one for the unselected items after the insertion point. Then it’s just a matter of concatenating the three lists.
  2. By some variation of (1) that need fewer lists and potentially needs to move fewer items around.
  3. By (stable) partitioning the two parts of the original list, the first part from the beginning to the insertion point, the second part from the insertion point to the end. That’s what Sean Parent presents in his talk.

I think this will be an interesting exercise because it’s a problem that one might encountered in practice, not just some toy problem or puzzle, it’s something that apparently made some C++ programmers at Google struggle, but it’s not so difficult that only veteran competitive programmers will be able to solve it.

For my showcase above I did just implement six tests, what I think would be typical use cases. I did not test edge cases: If the list of items is empty, if all or none items are selected, if the selected items are contiguous and end up in their original places.

1 Like
5

Feedback

Please, please provide some feedback, even if it’s just some short reaction. The last two times I presented an idea for a new exercise only very few people commented, the idea got no traction and got nowhere.

6

This sounds interesting to me!

1 Like
7

Yeah, I like it. If the exercise gets approved, I’ll take the initiative and add it to my tracks once the Arturo track overhaul is done in a couple of weeks.

1 Like
8

Cool idea!

1 Like
9

Any updates here? I think this could be PRed.

1 Like
10

Loved this exercise!