#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CACHE 5
enum
{
di = -1,
um = 0,
da = 1
};
enum
{
shsh = 0,
umum,
umda,
umdi,
daum,
dada,
dadi,
dium,
dida,
didi,
symmax
};
char *sym2[] = {
"shsh",
"umum",
"umda",
"umdi",
"daum",
"dada",
"dadi",
"dium",
"dida",
"didi",
};
char * sym1[] = {
"di",
"um",
"da",
};
#define abs(a) ((a)<0?-(a):a)
#define decode_sym1(a) ((a)==0?di:((a)==1?um:da))
#define encode_sym1(a) ((a)==-1?0:((a)==0?1:2))
void decodeSym2(int sym2, int * str)
{
switch(sym2)
{
case shsh:
break;
case umum:
str[0] = um;
str[1] = um;
break;
case umda:
str[0] = um;
str[1] = da;
break;
case umdi:
str[0] = um;
str[1] = di;
break;
case daum:
str[0] = da;
str[1] = um;
break;
case dada:
str[0] = da;
str[1] = da;
break;
case dadi:
str[0] = da;
str[1] = di;
break;
case dium:
str[0] = di;
str[1] = um;
break;
case dida:
str[0] = di;
str[1] = da;
break;
case didi:
str[0] = di;
str[1] = di;
break;
}
}
int isMinimized(int *str, int count, int n)
{
int i, sum = 0;
for(i = 0; i < count; i++)
{
sum += str[i];
if(sum == n)
return 1;
}
return 0;
}
int minimize(int *str, int count, int n)
{
int i, d, diff = 0, sum = 0;
for(i = 0; i < count; i++)
{
sum += str[i];
if(sum == n)
return 1;
if(abs(sum-n) <= 2)
{
diff = sum-n;
d = i;
}
}
for(i = 0; i <= d; i++)
{
switch(diff)
{
case -2:
if(str[i] == di)
{
str[i]=da;
return 1;
}
break;
case -1:
if(str[i] == di)
{
str[i]=um;
return 1;
}else
if(str[i] == um)
{
str[i]=da;
return 1;
}
break;
case 1:
if(str[i] == um)
{
str[i]=di;
return 1;
}else
if(str[i] == da)
{
str[i]=um;
return 1;
}
break;
case 2:
if(str[i] == da)
{
str[i]=di;
return 1;
}
break;
}
}
return 0;
}
int decodeState(int state, int * cache, int * cache_size)
{
int state3[MAX_CACHE+2] = {0};
int i = 0, q = -1;
*cache_size = 0;
for(i = 0; i < MAX_CACHE+2; i++)
{
state3[i] = state%3;
state /= 3;
if(state == 0) break;
}
if(i < 1) return -1;
if(state3[i] < 1) return -1;
q = (state3[i]-1)*3+state3[i-1];
i-=2;
for(;i >= 0; i--)
{
cache[(*cache_size)++] = decode_sym1(state3[i]);
}
return q;
}
int encodeState(int q, int * cache, int cache_size)
{
int p = 1;
int state = 0;
int i;
for(i = cache_size-1;i >=0; i--)
{
state += encode_sym1(cache[i])*p;
p*=3;
}
state += (q/3+1)*p*3+(q%3)*p;
return state;
}
#define map_zero_state(s) ((s)==3?0:(s))
int * shiftCache(int * cache, int cache_size)
{
memmove(cache, cache+1, (cache_size-1)*sizeof(int));
return cache;
}
void printCommand2(int q, int * cache, int cache_size, int sym, int move)
{
int state = encodeState(q, cache, cache_size);
printf("%03d %s %s\n", map_zero_state
(state
), sym2
[sym
], sym1
[encode_sym1
(move
)]);
}
void processVariants()
{
int state, sym, move;
int q, cache[10]={0}, cache_size;
for(state = 0; state <= 999; state++)
{
q = decodeState(state, cache, &cache_size);
if(q < 0)
continue;
if(q > 0 && cache_size == 0)
continue;
for(sym = 0; sym < symmax; sym++)
{
q = decodeState(state, cache, &cache_size);
if(sym == shsh && cache_size == 0)
continue;
if(sym == shsh)
{
move = cache[0];
printf("%03d %s ", map_zero_state
(state
), sym2
[sym
]);
printCommand2(0, shiftCache(cache, cache_size), cache_size-1, shsh, move);
continue;
}
if(q > 0)
{
move = cache[0];
printf("%03d %s ", map_zero_state
(state
), sym2
[sym
]);
printCommand2(q+move, shiftCache(cache, cache_size), cache_size-1, sym, move);
continue;
}
if(q == 0)
{
printf("%03d %s ", map_zero_state
(state
), sym2
[sym
]);
if(cache_size == MAX_CACHE)
{
minimize(cache, cache_size, 0);
move = cache[0];
printCommand2(move<0?0:move, shiftCache(cache, cache_size), cache_size-1, sym, move);
continue;
}
/*
if(cache_size > 0 && isMinimized(cache, cache_size, 0))
{
move = cache[0];
printCommand2(move<0?0:move, shiftCache(cache, cache_size), cache_size-1, sym, move);
continue;
}*/
-
decodeSym2(sym, cache+cache_size);
cache_size+=2;
minimize(cache, cache_size, 1);
move = cache[0];
printCommand2(0, shiftCache(cache, cache_size), cache_size-1, shsh, move);
continue;
-
}
}
}
}
int main()
{
processVariants();
return 0;
}