ACM: 110 - Meta-Loopless Sorts

這題要寫出一個程式generate另一段程式碼。練習遞迴。Runtime 0.084，Ranking進入前100，超開心。

CODE

#include <stdio.h>

#define MAX 8

void showarr(int n, int *array);
void showspace(int sp);
void copyarr(int n, int *to, int *frm);
void insertarr(int n, int position, int end, int k, int *array);
void showmeta(int n, int pos, int *array);

int main(){
  int i, j;
  int m, n, a[MAX];
  
  scanf("%d", &m);
  
  for(i=0; i<m; i++){
    scanf("%d", &n);
    
    for(j=0; j<n; j++)
      a[j] = j;
    
    if( i > 0 )
      printf("\n");
        
    printf("program sort(input,output);\n");
    printf("var\n");
    showarr(n, a);
    printf(" : integer;\n");
    printf("begin\n");
    printf("  readln(");
    showarr(n, a);
    printf(");\n");
    
    if( n == 1 )
      printf("  writeln(a)\n");
    else
      showmeta(n, 1, a);
    printf("end.\n");
  }/*i: m inputs*/
  
  exit(0);
}

void showarr(int n, int *arr){
  int i;
  
  printf("%c", 'a'+arr[0]);
  for(i=1; i<n; i++)
    printf(",%c", 'a'+arr[i]);
}

void showspace(int sp){
  int i;
  
  for(i=1; i<=sp; i++)
    printf("  ");
}

void copyarr(int n, int *to, int *frm){
  int i;
  
  for(i=0; i<n; i++)
    to[i] = frm[i];
}

void insertarr(int n, int p, int e, int k, int *arr){
  int i;
  
  if( p == e )
    arr[p] = k;
  else{
    for(i=e; i>p; i--)
      arr[i] = arr[i-1];
    arr[p] = k;
  }
}

void showmeta(int n, int p, int *arr){
  int i, cpy[MAX];
  
  if( p == (n-1) ){
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showspace(p+1);
      printf("writeln(");
      showarr(n, cpy);
      printf(")\n");
    }/*i*/
  }
  else{
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showmeta(n, p+1, cpy);
    }/*i*/
  }
}