= Reverse Folding =

<<TableOfContents>>

== Problem Description ==

This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate {{{length(N)}}}) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), -90 (left turn) and +90 (right turn). 
We refer to each placement of the string as a folding. A folding is represented by a predicate {{{fold(I,X,Y)}}} where I in {1,...,N} is the I-th element of the string, and {{{(X,Y)}}} are its coordinates in the plane. You can assume X and Y in {0,...,2N}.

A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N. A move at time t is represented by {{{pivot(t,i,clock)}}} or {{{pivot(t,i,anticlock)}}}. Exactly one move occurs at a time t.
Different elements must occupy different positions at any of the discrete time points considered: that is, each intermediate layout of the string must not have overlapping points in the 2D plane.

The goal is to find (if it exists) a sequence of T moves (T is defined by the predicate time(T)) such that lead the initial straight line fold 

{{{fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).}}}

into the fold assigned as input.

Ideas on modeling with variants of ASP can be found in: <<BR>>
A. Dovier, A. Formisano, E. Pontelli. <<BR>>
Perspectives on Logic-based Approaches for Reasoning About Actions and Change. <<BR>>
To appear in LNCS 6565, Essay in honour of Michael Gelfond <<BR>>
(paper draft available on line)


== Predicates ==

 * '''Input''': {{{fold/3, length/1, time/1}}}

 * '''Output''': {{{pivot/3}}}

== Input format ==

The target fold is encoded by means of the following facts:
 * a fact {{{length(n)}}}, where {{{n}}} is a positive integer;
 * {{{n}}} facts of the form {{{fold(i,x_i,y_i)}}}, where {{{i = 1,...,n}}} and {{{(x_i,y_i)}}} is a point in a 2D Cartesian plane.

A fact of the form {{{time(t)}}} is used for specifying the number of moves in the output sequence.

== Output format ==

A sequence of {{{t}}} moves leading the initial straight line fold into the fold assigned as input.
Such a sequence should be encoded by means of predicate {{{pivot/3}}}, where the first argument
is a time step, the second argument is the ID of a point of the fold, and the last argument is
either {{{clock}}} or {{{anticlock}}}.

== Example(s) ==

Assume the input is:
{{{
fold(1,9,9). 
fold(2,9,10). 
fold(3,9,11). 
fold(4,10,11). 
fold(5,11,11). 
fold(6,11,10). 
fold(7,11,9). 
fold(8,10,9). 
fold(9,10,10). 

length(9). 
time(4). 
}}}
This means that the the final form of the protein is
{{{
   _ _
  |   | 
  | |_|
}}}

Starting from the straight line fold, it is possible to reach
that folding with the application of the following pivot
moves (which is the expected output from the system):
{{{
pivot(1,3,clock). 
pivot(2,5,clock). 
pivot(3,8,clock). 
pivot(4,7,clock). 
}}}
Effects of pivot moves
{{{
 | 
 | 
 | 
 | 
 | 
 |    _ _ _ _ _ _    _ _     _ _     _ _ 
 |   |              |   |   |   |   |   | 
 |   |              |   |   |   |   | |_| 
                        |      _| 
                        | 
}}}

== Notes and Updates ==

Different elements must occupy different positions only at discrete time points. 
The case in which elements overlap during rotation from one time point to another is not to be considered.

== Problem peculiarities ==

'''Type''': Search/NP
'''Competition''': M&S only

== Author(s) ==
 * Author:  Agostino Dovier 	
   * Affiliation: University of Udine, Italy
 * Author: Andrea Formisano 	
   * Affiliation: University of Perugia, Italy
 * Author: Enrico Pontelli	
   * Affiliation: New Mexico State University, USA