The Pants Problem

Given an array of integers and a pointer:

-----|-----
    v
[1 2 3 4 5]

There are four available moves:

1. Move the pointer two places to the left

-|---------
v
[1 2 3 4 5]

2. Move the pointer two places to the right

----------|-
          v
 [1 2 3 4 5]

3. Swap the current number to the left

---|-------
   v
[1 3 2 4 5]

4. Swap the current number to the right

-------|---
       v
[1 2 4 3 5]

Goal

Reverse the array (the pointer position is not relevant):

-------|---
       v
[5 4 3 2 1]

Object breakdown

There are several classes that model the problem. Here are explanations:

PantsState

A single state of the pants problem, consisting of:

• The ordered array
• The pointer position

The four operations outlined above are represented as methods, each returning a new PantsState that is the result of the transition. If the transition cannot be done, then None is returned.

PantsPath

An ordered list of PantsStates that represent a series of moves when solving the Pants Problem. The primary function is to generate child PantsPaths - each of which is a "next step" i.e. new PantsPaths with one additional PantsState at the end for each valid move from the most recent PantsState.

PantsSolver

This is a command class encapsulating the general algorithm for solving the Pants Problem. It consists of the following steps:

1. Initialize a "working set" of a single PantsPath with the initial PantsState - this working set is ranked by the "best" PantsPath
2. Pick the best PantsPath from the working set
3. If that PantsPath ends with the goal, return it as the solution
4. If not, generate the child PantsPaths from the best, and add them to the working set
5. Goto step 2

Heuristics

You may be wondering how to determine which PantsPath is the "best" - this is guided by Heuristics. See also: https://en.wikipedia.org/wiki/Heuristic_(computer_science)

The concept is pretty straightforward, given a PantsPath (and with a reference to the goal state), return an integer that scores how "good" it is (lower == better). The specific heuristic defines what that means, and there are two heuristics in place as samples:

1. BreadthFirst: Return the number of PantsStates in the PantsPath - this will favor evaluating the shortest paths first.

2. Distance: This sums the difference between the current state and the goal state. For example, the distance between [5 4 3 2 1] and [5 3 4 2 1] is 2: abs(5 - 5) + abs(4 - 3) + abs(3 - 4) + abs(2 - 2) + abs(1 - 1) = 0 + 1 + 1 + 0 + 0 = 2

Running

Make sure that Python 3 is installed, then run:

> python3 pants.py

This will run the problem with the default heuristic and problem size. Help is available my running:

python3 pants.py --help

You can specify a custom problem size and/or a different heuristic to use:

python3 pants.py --size=7 --heuristic=Distance

You can also run the unit tests:

> python3 -m unittest

Write your own heuristics to solve the pants problem!