A problem with strings

A problem with strings


An Algorithm and C program that finds out for any string that is twisted and tangled, if it will form a Knot or not when its two ends are stretched. The problem originally appears here.

The input will consist of a diagram of one single continuous string described in a two-dimensional grid of characters such as shown above. The ‘−’ and ‘|’ characters represent a horizontal and vertical segment of the string, respectively. ‘+’ characters represent corners where the string turns at right angles on the table. ‘I’ or ‘H’ characters represent locations where parts of the strings cross:

The dot character, ‘.’, obviously,represents empty spaces of the table unoccupied by the string. Two horizontally adjacent non-empty spaces of the table are connected by the string iff neither of them are ‘|’ characters. Similarly, vertically adjacent non-empty spaces are connected by the string iff neither of them are ‘-’ characters. Inputs will be such that every ‘+’ character will represent a proper corner where the string turns at a unambiguously at a right angle: formally, every ‘+’ character will be connected to exactly one vertically adjacent and exactly one horizontally adjacent space. Moreover, to further simplify matters, you can assume that the only characters along the border of the given diagram, other than dots, will represent endpoints of the string. In short,the input will unambiguously specify a valid piece of string starting and ending at the border of the input diagram. Finally, assume that the string has negligible width and is made of a very smooth material, so that parts of the string can easily slide over each other with negligible friction.

I have written the solution to this problem in C programming language. It can be compiled on any linux platform. The input file is apws.in. Also included another input file named apws (2).in as an alternative input.

The apws.in file serves as an input file which the program will use. Make sure to put both – the source file and the apws.in file in the same directory.  Either Copy the code and input file below or download the package.

I have not written any defensive code to check for the correct format of the input file. So if you are experiencing any strange behavior from the program, please check the format of your input file. The program is not heavily tested.

Download Package
Download Package

 The Algorithm

  1. Find any one end of the string as a starting point to begin traversing the string.
  2. Initialize an empty stack.
  3. Traverse the string along its path. Check the stack when you reach the end of the string for the sub-string "UDU" or "DUD". If there is such pattern found then the string is likely to be knotted. Or else it will be straightened.
  4. Follow these rules to push or pop 'U' (Up) or 'D' (Down) into the stack as you traverse.
    1. If you cross an intersection from below push D.
    2. If you cross an intersection from above push U.
    3. If you cross an intersection and if the last character in the stack is same as the one you are supposed to push, ignore to push and pop the last character instead.
    4. If you cross an intersection and if the last character in the stack was from the same point as you are now, ignore to push and pop the last character instead.
/*
 * Author: Mufaddal Makati
   Official Post: http://www.rawbytes.com
 Copyright [2012] [Author: Mufaddal Makati]

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 *
 * Created on July, 2012.
 */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void parse_input(FILE *);
int process_string();
struct status
{
        int knot;
        char knotstats[50];
        int lipr[50];
 int lipc[50];
 int curr;
};
void process(char ,struct status *,int ,int ,int * );
void changedir(int ,int *,int *,int *);
int row,coloumn;
char **grid;

int main(int *argc,char *argv[])
{
 FILE *input;
 int answer=0;

 if((input=fopen("apws.in","r"))== NULL)
        {
                printf("Error opening configuration file.\n");
                exit(1);
        }

 parse_input(input);

 answer=process_string();

 if(answer==1)
 printf("\nKnotted\n");
 else
 printf("\nStraightiened\n");

 return 0;
}

void parse_input(FILE * input)
{
 int i=0,j=0;
 char line[50];

 while(fgets(line,50,input)!=NULL)
 {
 if(line[0]== ' ' || line[0]== '\n' || line[0]=='\t')
 continue;

 else if(sscanf(line,"%d %d",&row,&coloumn))
 {
 grid=(char **)calloc(row,sizeof(char *));
                        if(grid == NULL)
 {
 printf("Grid Memory allocation Failed.\n");
 exit(1);
 }
 for(j=0;j<row;j++)
                        {
 grid[j]=(char *)calloc(coloumn+1,sizeof(char));
                                if(grid[j]==NULL)
                                {
                                    printf("Grid Memory allocation Failed.\n");
                                    exit(0);
                                }
                        }
 continue;
 }
 else if(sscanf(line,"%s",grid[i]))
 {
 i++;
 continue;
 }
 else
 {
 printf("Input file not proper.\n");
 exit(0);
 }
 }
 for(i=0;i<row;i++)
 printf("%s\n",grid[i]);
}

int process_string()
{
 int startr=-1,startc=-1,endr=-1,endc=-1;
 int i,j,rowt=0,colt=0,direction=0;
 char cur;
 struct status curstat;

 curstat.knot=0;
 curstat.curr=1;
 for(i=0;i<50;i++)
 {
 curstat.lipr[i]=-1;
 curstat.lipc[i]=-1;
 curstat.knotstats[i]='\0';
 }
        curstat.knotstats[0]='X';
 for(i=0;i<row;i++)
 {
 if(grid[i][0]=='-' && startr==-1)
 {
 startr=i;
 startc=0;
 }
 else if(grid[i][0]=='-' && startr!=-1)
 {
 endr=i;
 endc=0;
 }
 }
 for(i=0;i<coloumn;i++)
 {
 if(grid[0][i]=='|' && startc==-1)
 {
 startc=i;
 startr=0;
 }
 else if(grid[0][i]=='|' && startc!=-1)
 {
 endc=i;
 endr=0;
 }
 }
 for(i=0;i<row;i++)
        {
                if(grid[i][coloumn-1]=='-' && startr==-1)
         {
                 startr=i;
 startc=coloumn-1;
 }
                else if(grid[i][coloumn-1]=='-' && startr!=-1)
                {
         endr=i;
 endc=coloumn-1;
 }
        }
        for(i=0;i<coloumn;i++)
        {
                if(grid[row-1][i]=='|' && startc==-1)
 {
                        startc=i;
 startr=row-1;
 }
                else if(grid[row-1][i]=='|' && startc!=-1)
 {
                        endc=i;
 endr=row-1;
 }
        }
 rowt=startr;
 colt=startc;
 while(rowt!=endr && colt!=endc)
 {
 switch (direction)
 {
 case 0:
 for(;(cur=grid[rowt][colt])!='+'|| (colt==endc && rowt==endr);colt++)
 process(cur,&curstat,rowt,colt,&direction);
 break;

 case 1:
 for(;(cur=grid[rowt][colt])!='+' || (colt==endc && rowt==endr);rowt++)
 process(cur,&curstat,rowt,colt,&direction);
 break;

 case 2:
 for(;(cur=grid[rowt][colt])!='+' || (colt==endc && rowt==endr);colt--)
 process(cur,&curstat,rowt,colt,&direction);
 break;

 case 3:
 for(;(cur=grid[rowt][colt])!='+'|| (colt==endc && rowt==endr);rowt--)
 process(cur,&curstat,rowt,colt,&direction);
 break;
 }
 if(rowt==endr && colt==endc)
 break;

 if(direction==0 || direction==2)
 changedir(0,&direction,&rowt,&colt);
 else
 changedir(1,&direction,&rowt,&colt);
 }
 if(strstr(curstat.knotstats,"DUD")==NULL || strstr(curstat.knotstats,"UDU")==NULL)
 curstat.knot=0;
 else
 curstat.knot=1;

 return curstat.knot;
}
void process(char cur,struct status *curstat,int rowt,int colt,int *direction)
{
 char temp='\0';
 switch(cur)
 {
 case '.':
 printf("Impossible outcome.\n");
 exit(0);

 case '-':
 case '|':
 return;

 case 'H':
 if(*direction==0 || *direction==2)
 temp='U';
 else
 temp='D';
 break;

 case 'I':
 if(*direction==0 || *direction==2)
 temp='D';
 else
 temp='U';
 break;
 }
 if((curstat->lipr[curstat->curr-1]==rowt && curstat->lipc[curstat->curr-1]==colt) || curstat->knotstats[curstat->curr-1]==temp)
 {
 curstat->lipr[curstat->curr-1]=-1;
 curstat->lipc[curstat->curr-1]=-1;
 curstat->knotstats[curstat->curr-1]='\0';
 curstat->curr--;
 }
 else
 {
 curstat->lipr[curstat->curr]=rowt;
 curstat->lipc[curstat->curr]=colt;
 curstat->knotstats[curstat->curr]=temp;
 curstat->curr++;
 }
}
void changedir(int d,int *direction,int *rowt,int *colt)
{
 if(!d)
 {
 if(grid[(*rowt)+1][*colt]=='|')
                {
 *direction=1;
                        (*rowt)++;
                }
 else
                {
 *direction=3;
                        (*rowt)--;
                }
 }
 else
 {
 if(grid[*rowt][(*colt)+1]=='-')
                {
 *direction=0;
                        (*colt)++;
                }
 else
                {
 *direction=2;
                        (*colt)--;
                }
 }
}
apws.in ( Input File)
9 15
...............
...+------+....
...|......|....
...|...+--H----
...|...|..|....
---I---H--+....
...|...|.......
...+---+.......
...............