/***************************************************************************

                          raetzel.c  - Guess the digits
                             -------------------
    begin                : Sam Okt 25 22:33:10 CEST 2003
    copyright            : (C) 2003 by Christof Grigutsch 
    email                : docx@wh-og.hs-niederrhein.de

    purppose             : calculates and display solutions for the specified
                           kind of riddle.
    modules              : none
    parameters           : none
    limitations          : the program will only works correct if all possible
                           digits of the given number base are used in the
                           riddle. If not, it will display the solutions
                           multiple times.

 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include <stdio.h>
#define n 6      // change this for a another output-range in "combine"
#define base 10


void swap( char code[], int a, int b )
{
        char tmp;
        tmp = code[a];
  code[a] = code[b];
  code[b] = tmp;
}


void bubble( char code[], int a )
{
        int i, j;
/*  Bubblesort algorithm  */
  for ( i = 0; i < ( base - a ); i++ )
        {
                for ( j = a; j < ( base - i - 1); j++ )
    {
                        if ( code[j] > code[j+1] )
          {
        swap( code, j, j+1 );
            }
        }
  }
}


int input( char string[9][n+1], char code[], char op[6+1], char zero[base] )
{
        int i, j, k;
  char tmp[ n+1 ];
/*  create base letter-code */
  for ( i = 0; i <= base; i++ )
  {
        code[i] = '\0';
  }
/*  create base list for zero-positions */
  for ( i = 0; i < base; i++ )
  {
        zero[i] = '\0';
  }


  printf( "\nGuess the digits\n\n");
  printf( "Please enter the following values:\n\n");
  printf( "Use the characters [a-zA-Z] for the symbols ordered\n");
  printf( "as in the assignment, and [+-*/] for the operators.\n\n");
  printf( "\n Please insert riddle in this structure:\n");
  printf( "\n   s1     op1     s2     =     s3" );
  printf( "\n\n   op4            op5          op6" );
  printf( "\n\n   s4     op2     s5     =     s6" );
  printf( "\n----------------------------------" );
  printf( "\n   s7     op3     s8     =     s9" );
        printf( "\n" );
/* read all 9 strings */
        for( i = 0; i < 9; i++ )
        {
          fflush( stdin );
        printf( "\n s%d: ", i+1 );
/*  store temporary the string  */
                scanf( "%s", tmp );
/*  put all first letters in a special array, that may not be touched by zero */
    k = 0;
    while ( ( zero[k] != tmp[0] ) && ( zero[k] != '\0') )
    {
        k++;
    }
/*  if not yet exists, add to list  */
    if ( zero[k] == '\0' )
    {
        zero[k] = tmp[0];
    }
    j = 0;
    while ( ( j < n ) && ( tmp[j] != '\0' ) )
    {
/*  copy string char by char to destination */
        string[i][j] = tmp[j];
      k = 0;
/*  check if letter already exists  */
      while ( ( code[k] != string[i][j] ) && ( code[k] != '\0') )
      {
        k++;
      }
/*  if not yet exists, add to code  */
      if ( code[k] == '\0' )
      {
        code[k] = string[i][j];
      }
      j++;
    }
    string[i][j] = '\0';
  }
/* read all 6 operators */
        for( i = 0; i < 6; i++ )
        {
          fflush( stdin );
    printf("\n op%d: ", i+1 );
    scanf("%s", &op[i] );
  }
/* count the differnt letters */
  while (code[k] != '\0' )
 {
        k++;
  }
  if ( k <= base )
  {
/*  sort the list with bubble-sort by ASCII numbers */
    bubble(code, 0 );
        return( k );
  }
  else
  {
        return( -1 );
  }
}


int permutation( char code[], char zero[base] )
{
        int i, j;
  i = 0;
/*  check if first letter in code list can be zero  */
  while ( ( zero[i] != '\0' ) && ( code[0] != zero[i] ) && ( code[0] != '\0' ) )
  {
        i++;
  }
        if ( ( zero[i] != '\0' ) && ( code[0] != '\0' ) )
  {
/*  current letter is not allowed to zero */
        i = 1;
/*  sort complete list with bubble-sort behind the first position */
            bubble( code, 1 );
    while ( ( code[i] <= code[0] ) && ( i < base ) )
    {
        i++;
    }
/*  if the first letter the largest, end the permutation  */
          if ( i < base )
    {
        swap( code, 0, i );
      return( 0 );
    }
    else
    {
/*  no more combinations  */
                        return( 1 );
    }
  }
  else
  {
                i = base - 2;
          while ( ( code[i] >= code[i+1] ) && ( i >= 0 ) )
                {
                i--;
                }
          if ( ( code[i] < code[i+1] ) && ( i >= 0 ) )
                {
/* number can only changed with a larger number */
                if ( code[i] < code[base-1] )
                  {
                                swap( code, i, base-1 );
            }
          else
                {
                                j = base - 2;
                while ( code[i] >= code[j] )
          {
                        j--;
                  }
                                swap( code, i, j );
                   }
/*  allign the rest of the numbers description  */
            if ( i+1 < base-1 )
                  {
                        bubble( code, i+1 );
                  }
                return( 0 );
                }
                else
          {
/*  no more combinations  */
                return( 1 );
                }
  }
}


int calculate( int nstring[9], char op, int a, int b, int c )
{
        int i;

  i = 0;
        switch( op )
  {
        case '+' :      if ( nstring[a] + nstring[b] != nstring[c] )
                                                { i = 1; }
                break;
        case '-' :      if ( nstring[a] - nstring[b] != nstring[c] )
                                                { i = 1; }
                break;
        case '*' :      if ( nstring[a] * nstring[b] != nstring[c] )
                                                { i = 1; }
                break;
        case '/' :      if ( nstring[b] != 0 )
                                                { if ( ( nstring[a] / nstring[b] != nstring[c] )
                        || ( nstring[a] % nstring[b] != 0 ) )
                                                        { i = 1; } }
                break;
    default:            i = 1;
  }
  return( i );
}


void combine( char string[9][n+1], char code[], char op[6+1] )
{
        int i, j, k;
  int nstring[ 9 ];
  int error_flag;
/*   for each of the 9 strings  */
        for ( i = 0; i < 9; i++ )
  {
    nstring[i] = 0;
    j = 0;
/*  so long as there are letters in the string  */
    while ( string[i][j] != '\0' )
    {
        k = 0;
/*  search actual letter in the code  */
       while ( code[k] != string[i][j] )
      {
        k++;
      }
/*  use Horner-Scheme */
      nstring[i] = ( nstring[i] * base ) + k;
        j++;
    }
  }
/*  now we have a number for each string

    if all calculations are right, error_flag should stay at zero*/
  error_flag = 0;
  error_flag += calculate( nstring, op[0], 0, 1, 2 );
  error_flag += calculate( nstring, op[1], 3, 4, 5 );
  error_flag += calculate( nstring, op[2], 6, 7, 8 );
  error_flag += calculate( nstring, op[3], 0, 3, 6 );
  error_flag += calculate( nstring, op[4], 1, 4, 7 );
  error_flag += calculate( nstring, op[5], 2, 5, 8 );

/* if there no error, got the match */
  if ( error_flag == 0 )
  {
    printf("\nThe solution:\n\n");
    printf("\n %6i  %c  %6i  =  %6i", nstring[0], op[0], nstring[1], nstring[2] );
    printf("\n\n %6c     %6c     %6c",       op[3],             op[4],      op[5] );
    printf("\n\n %6i  %c  %6i  =  %6i", nstring[3], op[1], nstring[4], nstring[5] );
    printf("\n-----------------------------" );
    printf("\n %6i  %c  %6i  =  %6i", nstring[6], op[2], nstring[7], nstring[8] );
  }
}


int main( void )
{
  int letters;
  char choice;
  char op[ 6+1 ];
  char string[ 9 ][ n+1 ];
  char code[ base+1 ];
  char zero[ base ];

  do
  {
/*  get all the needed input and work with it */
        letters = input( string, code, op, zero );

          if ( letters < 0 )
        {
                printf("\n you entered too many letters!" );
          }
        else
          {
                  do
                {
/*  try combination */
                    combine( string, code, op );
                        }
/*  get next code in while  */
                while ( permutation( code, zero ) != 1 );
          }
                printf("\n\n No more possibilities\n" );
          printf("\n The program has finished, exit with \'x\': ");
        fflush( stdin );
        scanf("%s", &choice );
  }
  while ( choice != 'x' );
  return( 1 );
}