#!/usr/local/bin/perl5 --  # -*-Perl-*-
# topo.pl	-- Eisaku Ohfuchi
#
# Applied Topology -Simplification of the planar model
#  

## Example of Inputs:
##  Input: abcdbcdaefEfgGhhijjkllImmKnn  (Test for 1-4)
##  Classfication: 3
##  Result: bbccddlljjnnooaaffhh
##
##  Input: dFccfbaBAD (Test input for 5)
##  Classfication: 3
##  Result: eeaabb
##
##  Input: eccFbaBAfE (Test input for 5)
##  Classfication: 3
##  Result: ddaabb
##  
##  Input: aAbB
##  Classfication: 1
##  Result: bB
##
##  Input: abcBAC
##  Classfication: 2
##  Result: acAC


print "INPUT: ";
$string = <STDIN>;
chop $string;
$string_length = length $string;
$midout = $string;
@abc = ('a'..'x');


###
###  Create the mid-code($midout)
###

foreach $word (@abc){
    if(($midout =~ /([a-xA-XYZ]*)$word([a-xA-XYZ]*)\u${word}([a-xA-XYZ]*)/) ||
	($midout =~ /([a-xA-XYZ]*)\u${word}([a-xA-XYZ]*)$word([a-xA-XYZ]*)/)){

        $midout = "$1Y$word$2Y$word$3";
        $abc_check{$word} = 1;

    }elsif (($midout =~ /([a-xA-XYZ]*)$word([a-xA-XYZ]*)$word([a-xA-XYZ]*)/) ||
       ($midout =~ /([a-xA-XYZ]*)\u${word}([a-xA-XYZ]*)\u${word}([a-xA-XYZ]*)/)){

       $midout = "$1Z$word$2Z$word$3";
       $abc_check{$word} = 1;

    }
}


###
### Sytax Check 
###
print "   midout(Syntax): $midout\n";
if($midout =~ /^([YZ][a-xA-X])+$/){
    print "Syntax OK.\n";
}else{
    print "Syntax Error. Please check your input.\n";
    print "midout: $midout\n";
    exit(0);
}
 
TOP:
###
### 1. Shorcut 
###

for($j=($string_length /2);$j>=2;$j--){
    for($i=0;$i<=($string_length /2);$i++){   
	if($midout =~ /^\w{$i}(([Z][a-x]){$j})\w*$/){
	    if($midout =~ /^\w*($1)\w*$1\w*$/g){
               @tmplist=split(/[Z]/,$1);
               &get_alt_word;
               foreach (@tmplist){$abc_check{$_} = 0;}
               $midout =~ s/$1/Z$alt_word/g;
             }
         }
     }
}
print "1.Shortcut -Completed\n";
print "   midout(1.Shortcut): $midout\n";

###
### 2. Toridal Pair
###

foreach (@abc){
    if(($midout =~ /^(\w+)Y{1}$_{1}Y{1}$_{1}(\w*)$/g)||
    ($midout =~ /^(\w*)Y{1}$_{1}Y{1}$_{1}(\w+)$/g)||
    ($midout =~ /^Y{1}$_{1}(\w+)Y{1}$_{1}$/g)
    ){
	$midout = "$1$2";
    }
}
print "2.Toridal Pair -Completed\n";
print "   midout(2.Toridal Pair): $midout\n";


###
### 3. Collecting twisted pairs
###

foreach (@abc){
    if($midout =~ /^(\w*)(Z{1}$_{1})(\w+)Z{1}$_{1}(\w*)$/g){
	$tmp = $3;
	foreach $word (@abc){		 
	    $tmp =~ s/Z$word/$word/g;
            $tmp =~ s/Y$word/\u${word}/g;
        }
        $tmp=reverse($tmp);
	foreach $word (@abc){
	    $tmp =~ s/$word/Z$word/g;
            $tmp =~ s/\u${word}/Y$word/g;
        }
        $midout = "$1$tmp$2$2$4";
    }
}
print "3.Collecting twisted pairs -Completed\n";
print "   midout(3.Collecting Z): $midout\n";

###
### 4. Collecting toroidal pairs
###

for($i=0;$i<=($string_length-4);$i++){   
    for($j=0;$j<=($string_length-3-$i);$j++){
	if($midout =~ /^\w{$i}Y([a-x])\w{$j}Y([a-x])\w*Y[a-x]\w*Y[a-x]\w*$/){
	    if($midout =~ /^(\w{$i})Y($1)(\w{$j})Y($2)(\w*)Y($1)(\w*)Y($2)(\w*)$/){
		$midout = "$7Y$4Y$2Y$4Y$2$5$3$9$1";
	    }
         }
    }
}
print "4.Collecting toroidal pairs -Completed\n";
print "   midout(4.Collecting Y): $midout\n";

###
### 5. Toroidal and twisted pairs -> twisted pairs
###

for($i=0;$i<=($string_length-6);$i++){   
    for($j=0;$j<=($string_length-4);$j++){
    if($midout =~ /^\w{$i}Z{1}([a-x])Z{1}[a-x]\w{$j}Y{1}([a-x])Y{1}([a-x])Y{1}[a-x]Y{1}[a-x]\w*$/){
	if($midout =~ /^(\w{$i})Z{1}($1)Z{1}$1(\w{$j})Y{1}($2)Y{1}($3)Y{1}($2)Y{1}$3(\w*)$/){
	    &get_alt_word;
	    $abc_check{$2} = 0; $abc_check{$4} = 0; $abc_check{$5} = 0;
            $ttmp1 = $alt_word;
	    &get_alt_word;
            $ttmp2 = $alt_word;
	    &get_alt_word;
            $ttmp3 = $alt_word;
	    $midout = "$1$3"."Z"."$ttmp1"."Z"."$ttmp1"."Z"."$ttmp2"."Z"."$ttmp2"."Z"."$ttmp3"."Z"."$ttmp3$7";
        }
}}
}
for($i=0;$i<=($string_length-6);$i++){   
    for($j=0;$j<=($string_length-4);$j++){
    if($midout =~ /^\w{$i}Y{1}([a-x])Y{1}([a-x])Y{1}[a-x]Y{1}[a-x]\w{$j}Z{1}([a-x])Z{1}[a-x]\w*$/){
	if($midout =~ /^(\w{$i})Y{1}($1)Y{1}($2)Y{1}($1)Y{1}$2(\w{$j})Z{1}($3)Z{1}$3(\w*)$/){
	    &get_alt_word;
	    $abc_check{$2} = 0; $abc_check{$3} = 0; $abc_check{$6} = 0;
            $ttmp1 = $alt_word;
	    &get_alt_word;
            $ttmp2 = $alt_word;
	    &get_alt_word;
            $ttmp3 = $alt_word;
	    $midout = "$1"."Z"."$ttmp1"."Z"."$ttmp1"."Z"."$ttmp2"."Z"."$ttmp2"."Z"."$ttmp3"."Z"."$ttmp3$5$7";
        }
}}
}
print "5.Toroidal and twisted -> twisted  -Completed\n";
print "   midout(5. Z&Y -> Z): $midout\n";


###
### Check as if $midout is a final result
###
$mid_string_length = length $midout;
$class = -1;
if($midout =~ /^Y[a-x]Y[a-x]$/){
    $class = 1;    ## class 1 (aA)
}elsif($midout =~ /^$/){
    $class = 0;    ## empty
}elsif($midout =~ /^((Z[a-x])+(Y[a-x])+)*$/){
    goto TOP;
}


## class 3 (aabbccdd ...)

if($class== -1){
    $class = 3;
    for($i=0;$i<=($mid_string_length-4);$i +=4){
	if($midout =~ /^\w{$i}Z([a-x])Z([a-x])\w*/){
	    if(!(($midout =~ /^\w{$i}Z($1)Z($1)\w*/)&& ($class == 3))){
		$class = -1; last;
	    }
         }else{$class = -1; last;}
    }
}

## class 2 (abABcdCD...)

if($class == -1){
    $class = 2;
    for($i=0;$i<$mid_string_length/8; $i++){
	$t = $i * 8;
	if($midout =~ /^\w{$t}Y([a-x])Y([a-x])Y([a-x])Y([a-x])\w*/){
	    if(!($midout =~ /^\w{$t}Y($1)Y($2)Y($1)Y($2)\w*/) && ($class == 2)){
		$class = -1; last;
	    }
        }else{$class = -1; last;}
    }
}


### $midout is not completed.

if($class == -1){
    goto TOP;
}



###
### Output the result
###

$result = $midout;
foreach (@abc){
    $result =~ s/Z$_(\w*)Z$_/$_$1$_/g;
    $result =~ s/Y$_(\w*)Y$_/$_$1\u${_}/g;
}
print "Final Result: $result\n";
print "Classfication: $class\n";

###
### Sub: Decide the altanative word
###

sub get_alt_word{
    foreach $tmp (@abc){
	if($abc_check{$tmp} == 0){
	    $alt_word = $tmp;
	    $abc_check{$tmp} = 1;
	    return;
	}
    }
    print "Error: altanative words not found because of too many.\n";
    exit(0);
}