Reverse Folding

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:
A. Dovier, A. Formisano, E. Pontelli.
Perspectives on Logic-based Approaches for Reasoning About Actions and Change.
To appear in LNCS 6565, Essay in honour of Michael Gelfond
(paper draft available on line)

Predicates

• Input: fold/3, length/1, time/1

• Output: pivot/3

Input format

Output format

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