# Solving the Number Placement Problem using Python

By John Lekberg on March 25, 2020.

This week's post is about solving the "Number Placement Problem". You will learn:

# Problem statement

You are given a set of distinct numbers:

``````1, 4, 2, 9
``````

And you are given empty boxes with comparisons between them:

``````[ ] > [ ] < [ ] > [ ]
``````

Your goal is to place all the numbers into the boxes in a way that satisfies all the comparisons. E.g.

``````[9] > [1] < [4] > [2]
``````

is a valid solution because all of the comparisons are true:

• 9 > 1 is true.
• 1 < 4 is true.
• 4 > 2 is true.

And

``````[9] > [4] < [2] > [1]
``````

is an invalid solution because not all of the comparisons are true:

• 9 > 4 is true.
• 4 < 2 is not true.
• 2 > 1 is true.

# How I represent the data in the problem

I represent the set of numbers using a set object:

``````{ 1, 4, 2, 9 }
``````

I represent a comparison using an Enum object:

``````import enum

Comparison = enum.Enum("Comparison", ["Less", "Greater"])
``````

I represent the empty boxes with comparisons between them as a list of `Comparison` objects:

``````[Comparison.Greater, Comparison.Less, Comparison.Greater]
``````

# Creating a brute force solution

A brute force solution will attempt every way to place the numbers into the empty boxes.

Each attempt needs to be validated, so here is a function that generates all the constraints that the attempt must satisfy:

``````def constraints(placement, comparisons):
"""Generate all constraints for a potential solution.

placement -- a sequence of numbers. E.g. [1, 4, 2, 9].
comparisons -- a sequence of Comparison objects. E.g.
[Comparison.Greater, Comparison.Less, Comparison.Greater].
"""
for a, b, comp in zip(placement, placement[1:], comparisons):
if comp is Comparison.Less:
yield a < b
elif comp is Comparison.Greater:
yield a > b

list(constraints(
[9, 4, 2, 1],
[Comparison.Greater, Comparison.Less, Comparison.Greater]
))
``````
``````[True, False, True]
``````

And here is a function that checks if all comparisons are satisfied by a placement:

``````def valid_solution(placement, comparisons):
"""Check if a placement of numbers is valid."""
return all(constraints(placement, comparisons))

valid_solution(
[9, 1, 4, 2],
[Comparison.Greater, Comparison.Less, Comparison.Greater]
)
``````
``````True
``````
``````valid_solution(
[9, 4, 2, 1],
[Comparison.Greater, Comparison.Less, Comparison.Greater]
)
``````
``````False
``````

Here's a function that attempts every placement of numbers to find a valid solution:

``````import itertools

def number_placement_bf(numbers, comparisons):
"""Use brute force to solve the Number Placement Problem.

numbers -- a set of numbers. E.g. {1, 4, 2, 9}.
comparisons -- a list of comparisons. E.g.
[Comparison.Greater, Comparison.Less, Comparison.Greater].
"""
all_placements = itertools.permutations(numbers)
for placement in all_placements:
if valid_solution(placement, comparisons):
return placement

number_placement_bf(
{1, 4, 2, 9},
[Comparison.Greater, Comparison.Less, Comparison.Greater]
)
``````
``````(2, 1, 9, 4)
``````

What is the time complexity of the solution? For a set of n numbers,

• There are n! placements.
• Validating each placement requires n-1 operations (one for each constraint).

As a result, the time complexity of the brute force algorithm is:

O(n! n)

This means that, if using the brute force algorithm on a set of 4 numbers took 1 second, then using the brute force algorithm on a set of 10 numbers would take over 4 days!

# Using a greedy algorithm to create a faster solution

I will use a greedy algorithm to generate a faster solution than using the brute force algorithm.

Here's the algorithm. Given the set of numbers N and the list of comparisons C,

• Iterate over each comparison in C:
• If the comparison is "<", then take the least number from N.
• If the comparison is ">", then take the greatest number from N.
• Place the chosen number into the next empty box.
• Place the remaining number from N into the last empty box.

Here's why this algorithm works:

• In each iteration, a number is chosen to be placed into the next empty box.

• If the comparison is "<", the least number in N, min(N), is chosen. Thus, the partial comparison looks like

[min(N)] < [x]

Where x is a number that has not been chosen yet.

It doesn't matter that x is not yet chosen, because the least number in N is less than every other number in N. As a result, any choice of x from the remaining numbers in N works.

• If the comparison is ">", the greatest number in N, max(N), is chosen. Thus, the partial comparison looks like

[max(N)] > [x]

Where x is a number that has not been chosen yet.

It doesn't matter that x is not yet chosen, because the greatest number in N is greater than every other number in N. As a result, any choice of x from the remaining numbers in N works.

• In the first iteration, there are no restrictions in choosing the least or greatest remaining number in N, because there are no previous partial comparisons to satisfy.

• In the remaining iterations, using the above strategy never introduces restrictions in choosing the least or greatest remaining number in N, so each iteration can safely continue using the strategy.

• As a result, every comparison is satistfied after the iteration is complete.

Here's a function that implements this greedy algorithm:

``````import collections

def number_placement_greedy(numbers, comparisons):
"""Use a greedy strategy to solve the Number Placement Problem.

numbers -- a set of numbers. E.g. { 1, 4, 2, 9 }.
comparisons -- a list of comparisons. E.g.
[Comparison.Greater, Comparison.Less, Comparison.Greater].
"""
numbers = collections.deque(sorted(numbers))

for comp in comparisons:
if comp is Comparison.Less:
least = numbers.popleft()
yield least
elif comp is Comparison.Greater:
greatest = numbers.pop()
yield greatest

last = numbers.pop()
yield last

list(number_placement_greedy(
{1, 4, 2, 9},
[Comparison.Greater, Comparison.Less, Comparison.Greater]
))
``````
``````[9, 1, 4, 2]
``````

I sort the list using the built-in function sorted. This allows me to easily remove the least and greatest remaining numbers.

• The least remaining number is always the first number in `numbers`.
• The greatest remaining number is always the last number in `numbers`.

I use a collections.deque object because removing an item from the beginning of a list object is an O(n) operation. (See the Python Wiki's "Time Complexity" page for a time complexity comparison of list objects and collections.deque objects.)

What is the time complexity of the greedy algorithm?

• `sorted` uses timsort, which runs in O(n logn) time.
• There are O(n) comparisons (n-1 comparisons) to iterate over.
• Each iteration pops a number off of either end of the collections.deque object, which takes O(1) time per iteration.

As a result, the time complexity of the greedy algorithm is

O(n logn)

This means that, if using the greedy algorithm on a set of 4 numbers took 1 second, then using the greedy algorithm on a set of 10 numbers would take about 4 seconds. Compare this with the brute force algorithm, which would take over 4 days.

# In conclusion...

In this post, you learned how to use a greedy algorithm to quickly solve the "Number Placement Problem". Greedy algorithms only work on problems where you don't need to backtrack on decisions. But, when you can use a greedy algorithm, it is often one of the fastest ways to solve the problem.

My challenge to you:

How would you solve this problem if the numbers weren't distinct? For example, given this set of numbers:

``````1, 1, 2, 2, 3
``````

And this layout of empty boxes with comparisons:

``````[ ] < [ ] < [ ] > [ ] < [ ]
``````

A valid solution is

``````[1] < [2] < [3] > [1] < [2]
``````

But the greedy algorithm would generate this invalid solution:

``````[1] < [1] < [3] > [2] < [2]
``````

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!