/*
   The C code contained in this file was written by Melanie Hart
   and Robert Bosch in November and December, 1999.  The code is 
   an implemenation of a DP approach for finding optimal piano
   fingerings.  See the article "Finding Optimal Piano Fingerings"
   by Melanie Hart, Robert Bosch, and Elbert Tsai for a detailed
   description.

   Please send comments to bobb@cs.oberlin.edu.
 */

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

#define MAX_NUM_NOTES 100      /* Maximum number of notes in passage */
#define MAX_INTERVAL_SIZE 12 
#define BIG_NUM 999 

int d[2][2][6][6][MAX_INTERVAL_SIZE+1];

int m;                         /* Number of intervals */
int num_notes;

int pitch[MAX_NUM_NOTES+1];    /* pitch[n] = pitch of nth note             */
int color[MAX_NUM_NOTES+1];    /* color[n] = color of nth note             */
int direction[MAX_NUM_NOTES];  /* direction[n] = direction of nth interval */
int size[MAX_NUM_NOTES];       /* size[n] = size of $n$th interval         */

int fsx[MAX_NUM_NOTES+1][6][6];
int fs[MAX_NUM_NOTES+1][6];
int xstar[MAX_NUM_NOTES+1][6][5];
int num_opt[MAX_NUM_NOTES+1][6];
int finger[MAX_NUM_NOTES];
int optcost;
int num_basic_mvts;


/*
    The function "get_ratings" reads the difficulty ratings from the file
    "tables.dat".
 */

void get_ratings()
{
int i, j, basic_mvt;
int l_color, h_color, l_finger, h_finger, s;
int num_basic_mvts;

FILE *input;

for (l_color = 0; l_color <= 1; l_color++)
  for (h_color = 0; h_color <= 1; h_color++)
    for (l_finger = 1; l_finger <= 5; l_finger++)
       for (h_finger = 1; h_finger <= 5; h_finger++)
         for (s = 1; s <= MAX_INTERVAL_SIZE; s++)
           d[l_color][h_color][l_finger][h_finger][s] = BIG_NUM;

if ((input=fopen("tables.dat", "r")) == NULL)
  {
    printf("Couldn't open tables.dat!\n");
    exit();
  }

fscanf(input, "%d", &num_basic_mvts);

for (l_color = 0; l_color <= 1; l_color++)
  for (h_color = 0; h_color <= 1; h_color++)
    for (basic_mvt = 0; basic_mvt < num_basic_mvts; basic_mvt++)
      {
        fscanf(input, "%d", &l_finger);
        fscanf(input, "%d", &h_finger);
        for (s = 1; s <= MAX_INTERVAL_SIZE; s++) 
          fscanf(input, "%d", &d[l_color][h_color][l_finger][h_finger][s]);
      }

fclose(input);

}


/*
    The function "get_notes" reads the file "notes.dat", which describes
    the righthand passage of interest.
 */

void get_notes()
{
int n;

FILE *input;

if ((input = fopen("notes.dat", "r")) == NULL)
  {
    printf("Couldn't open notes.dat!\n");
    exit();
  }

fscanf(input, "%d", &num_notes);
m = num_notes - 1;

for (n = 0; n <= m; n++)
  fscanf(input, "%d", &pitch[n]);

fclose(input);

}


/*
    The following function computes the sizes and directions of the
    intervals that comprise the righthand passage of interest.
 */

void find_sizes_and_directions()
{
int n;

for (n = 1; n <= m; n++)
  if (pitch[n] > pitch[n-1])
    {
      direction[n] = 1;
      size[n] = pitch[n] - pitch[n-1]; 
    }
  else
    {
      direction[n] = 0;
      size[n] = pitch[n-1] - pitch[n]; 
    }

}


/*
    The following function computes the sizes and directions of the
    intervals that comprise the righthand passage of interest.
 */

void find_colors()
{
int n, pitch_mod;

for (n = 0; n <= m; n++)
  {
   if (pitch[n] >=0) 
     pitch_mod = pitch[n] % 12;
   else
     pitch_mod = (pitch[n] % 12) + 12;
    if ( 
         (pitch_mod == 0) || (pitch_mod == 2) 
      || (pitch_mod == 4) || (pitch_mod == 5) 
      || (pitch_mod == 7) || (pitch_mod == 9)
      || (pitch_mod == 11) 
       )
      color[n] = 0;
    else
      color[n] = 1;
  }
}
								 

main()
{
int  n, s, x;
optcost = BIG_NUM;

get_ratings();
get_notes();
find_sizes_and_directions();
find_colors();

for (n = 1; n <= m; n++)
  {
    printf("I%d = (%d,%d) is a direction %d interval of size %d.\n",
       n, pitch[n-1], pitch[n], direction[n], size[n]);
    printf("  Its lower and upper notes are colors %d and %d.\n",
       color[n-1], color[n]);
  }
printf("\n");

for (n = m; n >= 1; n--)
  for (s = 1; s <= 5; s++)
    fs[n][s] = BIG_NUM;

/* Stage m */

for (s = 1; s <= 5; s++)
  {
    if (s == 1)
      printf("Stage %d\n", m);
    printf(" %d: ", s);

    for (x = 1; x <= 5; x++)
      {
        if ( direction[m] == 1 )
          fsx[m][s][x] = d[color[m-1]][color[m]][s][x][size[m]];
        else
          fsx[m][s][x] = d[color[m]][color[m-1]][x][s][size[m]];
        printf("%4d", fsx[m][s][x]);
      }

    for (x = 1; x <= 5; x++)
      if (fsx[m][s][x] < fs[m][s])
        fs[m][s] = fsx[m][s][x];
    printf("%4d  ", fs[m][s]);

    num_opt[m][s] = 0;
    for (x = 1; x <= 5; x++)
      if (fsx[m][s][x] == fs[m][s])
        {
          xstar[m][s][num_opt[m][s]] = x;
          num_opt[m][s] = num_opt[m][s] + 1;
        }

    for (x = 0; x < num_opt[m][s]; x++)
      {
        printf("%d", xstar[m][s][x]);
        if (x < num_opt[m][s]-1)
          printf(",");
        else
          printf("\n");
      }
    if (s == 5)
      printf("\n");
  }

/* Stages m-1 through 1 */

for (n = m-1; n >= 1; n--)
  for (s = 1; s <= 5; s++)
    {
      if (s == 1)
        printf("Stage %d\n", n);
      printf(" %d: ", s);
      
      if (size[n] != 0)
      {
      for (x = 1; x <= 5; x++)
        if ( direction[n] == 1) 
          {
            fsx[n][s][x] = d[color[n-1]][color[n]][s][x][size[n]] + fs[n+1][x];
            printf("%4d+%d=%4d ", 
              d[color[n-1]][color[n]][s][x][size[n]], fs[n+1][x], fsx[n][s][x]);
          }
        else
          {
            fsx[n][s][x] = d[color[n]][color[n-1]][x][s][size[n]] + fs[n+1][x];
            printf("%4d+%d=%4d ", 
              d[color[n]][color[n-1]][x][s][size[n]], fs[n+1][x], fsx[n][s][x]);
          }
              
      for (x = 1; x <= 5; x++)
        if (fsx[n][s][x] < fs[n][s])
          fs[n][s] = fsx[n][s][x];
      printf("%4d  ", fs[n][s]);

      num_opt[n][s] = 0;
      for (x = 1; x <= 5; x++)
        if (fsx[n][s][x] == fs[n][s])
          {
            xstar[n][s][num_opt[n][s]] = x;
            num_opt[n][s] = num_opt[n][s] + 1;
          }

      for (x = 0; x < num_opt[n][s]; x++)
        {
          printf("%d", xstar[n][s][x]);
          if (x < num_opt[n][s]-1)
            printf(",");
          else
            printf("\n");
        }
      if (s == 5)
        printf("\n");
    }

      else
      {
        for (x = 1; x <= 5; x++)
        {
           fsx[n][s][x] = fsx[n+1][s][x];
           fs[n][s] = fs[n+1][s];
        }
	   xstar[n][s][0] = s;
      }
}

for (s = 1; s <= 5; s++)
  if (fs[1][s] < optcost)
    {
      optcost = fs[1][s];
      finger[0] = s;
    }

for (n = 1; n <= m; n++)
  finger[n] = xstar[n][finger[n-1]][0];

printf("The optimal cost is %d\n", optcost);
printf("This is an optimal fingering:\n");

for (n = 0; n <= m; n++)
  printf(" %d", finger[n]);
printf("\n");

}