# Turnpike Problem (F#)

### The Problem

This is a problem for which no polynomial time solution exists, although a pseudo-polynomial (polynomial in the degree of the maximum element) does exist. In this paper, the algorithm proposed for the sum-function with full information is simple enough. For the original problem with the difference funcition, the algorithm is simple as well:

Problem. Given a set $D_A=\{a_i-a_j\},\ 1\le i, j\le n$, reconstruct the original set $A=\{a_i\},\ 1 \le i \le n$. (Naturally, we can only consider positive deltas: $D_A=\{a_i-a_j\},\ 1\le i, the set is sorted in the descending order).

A simple algorithm exists. It performs in $O(2^n\cdot\log{n})$ time, but in practice its performance is closer to $O(n^2\cdot\log{n})$, as it "probably" won't hit the worst case.

We first reduce our set $D_A$ to only positive values and assume they are sorted in the descending order.
Then the pseudocode will run as follows:


solution = [0; Da]
max_element = Da
remove (Da, Da)
while (Da not empty) {
if solution =  return []
if distances(solution.Add(Da)) $\subseteq$ Da && not explored_this_path()
remove(Da, distances)
else if distances(solution.Add(max - Da)) $\subseteq$ Da && not explored_this_path()
remove(Da, distances)
else
backtrack(solution, Da)
}
return solution;


We start by adding 0 and the maximal element to the solution, and remove the latter from the Da. At every step, we have a new version of the solution and Da. We take $\max{D_{A_cur}}$ to be the possible next element of the set $A$. Then we compute pair-wise distances of the current sub-solution and see if they represent the subset of $D_{A_cur}$. If that fails – we then try $a_{max} - \max{D_{A_cur}}$ the same way. If that fails as well, we backtrack to the previous state of the solution and previous $D_{A_cur}$, and keep backtracking until we reach a state, where not all of alternatives have been tried.

Once current Da is empty – we have a solution. If we have reached the root state and all alternatives have been tried – there is no solution.

Essentially, we are building a binary tree, where each node contains the current solution, current Da, and an edge connecting it with one or both of the alternatives above. Hopefully, we do not need to keep building this tree for too long. Here is a nice illustration of this process.

Note, that at every step we favor the remaining maximal element of $D_{A_cur}$ as opposed to $a_{max} - \max{D_{A_cur}}$. Doing the latter would produce a symmetric solution.

### F# Implementation

The source for this implementation is here

At every step, we keep building the following tree:

type DecisionTree =
| Empty
| TreeNode of deltas : Dictionary<int, int> * solution : int list * visited: uint32 * maxElem : DecisionTree * maxDist : DecisionTree * prev : DecisionTree


Every node contains the current deltas, current state of the solution, the number of times we have visited this node (for optimization), two possible branches and a pointer to the parent node.

The function that implements the current algorithm:

let rec insert (deltas : Dictionary<int, int>) (res : int list) (node : DecisionTree) (prevNode : DecisionTree) maxSol =
let insPrev () =
let res, deltas, prevPrev = getPrev prevNode
insert deltas res prevNode prevPrev maxSol

match node with
| Empty -> TreeNode(deltas, res, 0u, Empty, Empty, prevNode)
| TreeNode(dct, rslt, visited, maxElem, maxDist, prev) when visited < 2u ->
let curVisited = visit node
let elem =
if visited = 0u then keySeqMax deltas else maxSol - keySeqMax deltas
let dists = stepOk elem res deltas
if dists.Length > 0 then
let newDeltas = removeDist deltas dists
insert newDeltas (elem::res) (if visited = 0u then maxElem else maxDist) curVisited maxSol
elif visited = 0u then
insert deltas res curVisited prev maxSol
else
insPrev()
| _ -> insPrev()


The insert function implements each step of the algorithm and returns a reference to the currently inserted node.
The driver is a loop, implemented, naturally as a tail-recursive function:

let rec buildSolution (deltas : Dictionary<int, int>) (res : int list) (node : DecisionTree) (prev : DecisionTree) =
if deltas.Count = 0 then res |> List.sort
else
let newNode = insert deltas res node prev maxSol
let prevNode = node
match newNode with
| Empty -> [] // no solution
| TreeNode(deltas, res, visited, maxElem, maxDist, prev) ->
if visited >=2u && prev = Empty then [] // came all the way back, no solution
else
buildSolution deltas res newNode prevNode


This algorithm is biased towards always selecting the maximum remaining element from the Da as the next element in the solution. So, for an input set [2; 2; 3; 3; 4; 5; 6; 7; 8; 10], this algorithm produces [0; 3; 6; 8; 10]. Symmetrically, [0; 2; 4; 7; 10] is also a solution.

This site uses Akismet to reduce spam. Learn how your comment data is processed.