/* =============================================================== */
/*   CORSO DI PROGRAMMAZIONE IN C (C89)                            */
/*   Claudio Fornaro                                               */
/*   Ver. 3 - 2021                                                 */
/*   12-Algoritmi_Soluzioni.txt                                    */
/* =============================================================== */

/* =============================================================== */
/*   1                                                             */
/* =============================================================== */

/* Selection sort semplificato ----------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#define N 30

int main()
{
   int v[N], tmp;
   int i,j;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   for (i=0; i<N-1; i++)
      for (j=i+1; j<N; j++)
         if (v[j] < v[i])                   /* crescente */
         {
            tmp = v[j];
            v[j] = v[i];
            v[i] = tmp;
         }

   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}


/* Selection sort ------------------------------------------------ */
#include <stdio.h>
#include <stdlib.h>
#define N 30

int main()
{
   int v[N], tmp;
   int i,j, jmin;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   for (i=0; i<N-1; i++)
   {
      jmin = i;
      for (j=i+1; j<N; j++)
         if (v[j] < v[jmin])                 /* crescente */
            jmin = j;
      tmp = v[jmin];
      v[jmin] = v[i];
      v[i] = tmp;
   }


   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}


/* Bubble sort --------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#define N 30

int main()
{
   int v[N], tmp;
   int i,j;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   for (i=0; i<N-1; i++)
      for (j=0; j<N-1; j++)
         if (v[j] > v[j+1])                 /* crescente */
         {
            tmp = v[j];
            v[j] = v[j+1];
            v[j+1] = tmp;
         }



   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}


/* Bubble sort ottimizzato SCAMBI -------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#define N 30

int main()
{
   int v[N], tmp;
   int i,j;
   enum {NO, SI} scambi;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   scambi = SI;
   for (i=N-1; i>0 && scambi; i--)
   {
      scambi = NO;
      for (j=0; j<i; j++)
         if (v[j] > v[j+1])                 /* crescente */
         {
            tmp = v[j];
            v[j] = v[j+1];
            v[j+1] = tmp;
            scambi = SI;
         }
   }

   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}


/* Bubble sort ottimizzato ULTIMO -------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#define N 30
int main()
{
   int v[N], tmp;
   int i, j, ultimo;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   for (i=N-1; i>0; i=ultimo)
   {
      ultimo = 0;
      for (j=0; j<i  ; j++)
         if (v[j] > v[j+1])                 /* crescente */
         {
            tmp = v[j];
            v[j] = v[j+1];
            v[j+1] = tmp;
            ultimo = j;
         }
   }

   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}



/* Insertion sort ------------------------------------------------ */
#include <stdio.h>
#include <stdlib.h>
#define N 30

int main()
{
   int v[N], key;
   int i,j;

   printf("Inserire %d valori interi:\n", N);
   for (i=0; i<N; i++)
      scanf("%d", &v[i]);

   for (j=1; j<N; j++)
   {
      key = v[j];
      for (i=j-1; i>=0 && v[i]>key; i--)    /* crescente */
         v[i+1] = v[i];
      v[i+1] = key;
   }

   printf("Valori riordinati:\n");
   for (i=0; i<N; i++)
      printf("%d ", v[i]);

   return EXIT_SUCCESS;
}



/* =============================================================== */
/*   2                                                             */
/* =============================================================== */


#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 15000L

int main ()
{

   long i, j, jmin, key;
   double valori1[N], valori2[N], valori3[N], valori4[N], valori5[N],
          tmp;
   clock_t t1, t2;
   enum {NO, SI} scambi;

   srand(time(NULL));

   /* L'ordinamentio sara' sempre su vettori con gli stessi valori */
   for (i=0; i<N; i++)
      valori5[i]=valori4[i]=valori3[i]=valori2[i]=valori1[i]=
                 (double)rand()*1.0;

   printf("Ordinamento su %ld valori double\n", N);

/* volendo usare il codice del precedente esercizio senza modificarlo
   si #define v in modo che di volta in volta corrisponda a valori1, 
   valori2, ecc.   #undef serve per eliminare la definizione prima
   di farne un'altra per lo stesso simbolo, unicamente per eliminare
   il warning del compilatore sulla ridefinizione del simbolo v */

#define v valori1
   /* selection sort semplificato */
   t1 = clock();  /* tempo iniziale */
   for (i=0; i<N-1; i++)
      for (j=i+1; j<N; j++)
         if (v[j] < v[i])                   /* crescente */
         {
            tmp = v[j];
            v[j] = v[i];
            v[i] = tmp;
         }
   t2 = clock();  /* tempo finale */
   printf("Selection sort semplificato: %ld clock\n", t2-t1);

#undef v
#define v valori2
   /* selection sort */
   t1 = clock();
   for (i=0; i<N-1; i++)
   {
      jmin = i;
      for (j=i+1; j<N; j++)
         if (v[j] < v[jmin])                 /* crescente */
            jmin = j;
      tmp = v[jmin];
      v[jmin] = v[i];
      v[i] = tmp;
   }
   t2 = clock();
   printf("Selection sort: %ld clock\n", t2-t1);

#undef v
#define v valori3
   /* bubble */
   t1 = clock();
   for (i=0; i<N-1; i++)
      for (j=0; j<N-1; j++)
         if (v[j] > v[j+1])                 /* crescente */
         {
            tmp = v[j];
            v[j] = v[j+1];
            v[j+1] = tmp;
         }
   t2 = clock();
   printf("Bubble sort normale: %ld clock\n", t2-t1);

#undef v
#define v valori4
   /* bubble ottimizzato */
   t1 = clock();
   scambi = SI;
   for (i=N-1; i>0 && scambi ;i--)
   {
      scambi = NO;
      for (j=0; j<i; j++)
         if (v[j] > v[j+1])                 /* crescente */
         {
            scambi = SI;
            tmp = v[j];
            v[j] = v[j+1];
            v[j+1] = tmp;
         }
   }
   t2 = clock();
   printf("Bubble sort ottimizzato: %ld clock\n", t2-t1);

#undef v
#define v valori5
   /* insertion */
   t1 = clock();
   for (j=1; j<N; j++)
   {
      key = v[j];
      for (i=j-1; i>=0 && v[i]>key; i--)    /* crescente */
         v[i+1] = v[i];
      v[i+1] = key;
   }
   t2 = clock();
   printf("Insertion sort: %ld clock\n", t2-t1);


return EXIT_SUCCESS;
}



/* =============================================================== */
/*   3                                                             */
/* =============================================================== */


/* Selection sort semplificato -----------------------------------
   Identico all'ordinamento crescente salvo il simbolo di > nel 
   confronto:
         if (v[j] > v[i])                   /* decrescente */
*/

/* Selection sort ------------------------------------------------
   Identico all'ordinamento crescente salvo il simbolo di > nel 
   confronto:
         if (v[j] > v[jmin])                /* decrescente */
*/

/* Bubble sort (tutti) -------------------------------------------
   Identico all'ordinamento crescente salvo il simbolo di > nel 
   confronto:
         if (v[j] < v[j+1])                 /* decrescente */
*/


/* Insertion sort ------------------------------------------------
   Identico all'ordinamento crescente salvo il simbolo di > nel 
   confronto:
      for (i=j-1; i>=0 && v[i]<key; i--)    /* decrescente */
*/



/* =============================================================== */
/*   4                                                             */
/* =============================================================== */


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define LETTEREALFABETO 26 /* numero di lettere dell'alfabeto */
#define MAXFRASE 128

int main()
{
    int lettere[LETTEREALFABETO] = {0}; /* contatori delle lettere */
    int i;
    char frase[MAXFRASE];
    enum {FUORI, DENTRO} stato;

    printf("Inserire la frase da analizzare: ");
    gets(frase);

    stato = FUORI;
    for (i=0; frase[i]!='\0'; i++)
    {
        switch (stato)
        {
        case FUORI:
            /* 1. se stato FUORI ed è carattere alfabetico:
                  entra DENTRO (cambia lo stato in DENTRO) e incrementa 
                  il contatore di quel carattere */
            if (isalpha(frase[i]))
            {
                stato = DENTRO;
                lettere[toupper(frase[i]) - 'A']++;
            }
            /* 4. se stato FUORI e non è un carattere alfabetico:
               resta FUORI (non cambia lo stato) e non fa nulla */
            break;
        case DENTRO:
            /* 3. se stato DENTRO e non è un carattere alfabetico:
                  va FUORI dalla parola (cambia lo stato in FUORI) 
                  e non serve che faccia alcunche' */
            if (!isalpha(frase[i]))
            {
                stato = FUORI;
            }
            /* 2. se stato DENTRO ed è carattere alfabetico:
                  resta DENTRO (non cambia stato) e non fa nulla */
            break;
        }
    }

    for (i=0; i < LETTEREALFABETO; i++)
        printf("Parole che iniziano con %c: %d\n", 
                                                i+'A', lettere[i]);

    return EXIT_SUCCESS;
}



/* =============================================================== */
/*   5                                                             */
/* =============================================================== */


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXFILE 128
#define LETTEREALFABETO 26 /* lettere dell'alfabeto */

int main()
{
   char file[MAXFILE];
   FILE *fp;
   int lettere[LETTEREALFABETO] = {0}; /* contatori delle lettere */
   int c;
   int i;
   enum {FUORI, DENTRO} dove;
 
   printf("Input file: ");
   gets(file);
   if ( (fp = fopen(file, "r")) == NULL )
   {
      fprintf(stderr, "Impossibile aprire il file: %s\n", file);
      return EXIT_FAILURE;
   }
   
   dove = FUORI;
   while ((c=fgetc(fp)) != EOF)
   {
      if (dove==FUORI && isalpha(c))
      {
         lettere[toupper(c) - 'A']++;
         dove = DENTRO;
      }
      else if (dove == DENTRO && !isalpha(c))
         dove = FUORI;
   }
 
   for (i=0; i < LETTEREALFABETO; i++)
      printf("Parole che iniziano con %c: %d\n", i+'A', lettere[i]);

   fclose(fp);

   return EXIT_SUCCESS;
}

/* Nota
   Quando i casi sono pochi, non sempre lo switch è la soluzione più chiara.
*/



/* =============================================================== */
/*   6                                                             */
/* =============================================================== */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NRIGHE 256
#define NCOLONNE 256

int main()
{
    char immagine[NRIGHE][NCOLONNE]= {0}; /* Notare che è una matrice
       di caratteri e non un vettore di stringhe (la stringa ha il \0
       al fondo), dato che le righe non sono gestite come stringhe
       non serve richiedere un byte in piu' per il \0, quindi non NCOLONNE+1 */

    char riga[NCOLONNE+2];  /* questa e' la riga letta dal file, qui
       ci sara' eventualmente \n al fondo e \0 viene aggiunto dalla
       fgets, quindi NCOLONNE+2 */

    /* le seguenti definizioni sono unsigned per evitare warning di 
       conversione, anche se sicuramente non ci sarebbero problemi 
       considerando i valori stessi */
    unsigned int r, c, conta0, conta1;
    unsigned int nrighe, ncolonne; /* effettivo numero di righe e 
                                                      di colonne */
    enum {ZERO, UNO} stato;
    char filename[FILENAME_MAX];
    FILE *fpIN, *fpOUT;

    printf("Input file: ");
    gets(filename);
    if ( (fpIN = fopen(filename, "r")) == NULL )
    {
        fprintf(stderr, "Impossibile aprire file: %s\n", filename);
        return EXIT_FAILURE;
    }

    printf("Output file: ");
    gets(filename);
    if ( (fpOUT = fopen(filename, "w")) == NULL )
    {
        fprintf(stderr, "Impossibile aprire file: %s\n", filename);
        return EXIT_FAILURE;
    }

    /* legge la matrice di caratteri */
    for (r=0; r<NRIGHE && fgets(riga, NCOLONNE+2, fpIN) != NULL; r++)
        /* dato che fgets legge un carattere in meno di quanto 
           passato e deve leggere fino a NCOLONNE caratteri + \n, 
           bisogna indicare NCOLONNE+2 cosi' legge NCOLONNE+1 car. */
    {
        ncolonne = (unsigned int)strlen(riga);
        if (riga[ncolonne-1] == '\n')  /* toglie l'eventuale \n */
        {
            riga[ncolonne-1] = '\0';
            ncolonne--;
        }

        strncpy(immagine[r], riga, ncolonne); /* copia esattamente 
           ncolonne caratteri e non l'eventuale \0 finale, strncpy 
           non aggiunge esplicitamente \0  */
    }
    nrighe = r; /* numero effettivo di righe (<= NUMRIGHE) */

    /* compressione per righe */
    conta0=conta1=0;
    for (r=0; r<nrighe; r++)
    {
        if (immagine[r][0] == '0') /* stato iniziale della riga */
        {
            stato=ZERO;
            conta0=1;
        }
        else
        {
            stato=UNO;
            conta1=1;
        }
        for (c=1; c<ncolonne; c++)
        {
            if (stato==ZERO)
                if (immagine[r][c]=='0')
                    conta0++;
                else
                {
                    fprintf(fpOUT, "0%d ", conta0);
                    stato=UNO;
                    conta1=1;
                }
            else /* if (stato==UNO) */
                if (immagine[r][c]=='1')
                    conta1++;
                else
                {
                    fprintf(fpOUT, "1%d ", conta1);
                    stato=ZERO;
                    conta0=1;
                }
        }
        /* vedi Nota */
        if (stato==ZERO)
            fprintf(fpOUT, "0%d\n", conta0);
        else
            fprintf(fpOUT, "1%d\n", conta1);
    }

    /* compressione per colonne */
    conta0=conta1=0;
    for (c=0; c<ncolonne; c++)
    {
        if (immagine[0][c] == '0') /* stato iniziale */
        {
            stato=ZERO;
            conta0=1;
        }
        else
        {
            stato=UNO;
            conta1=1;
        }
        for (r=1; r<nrighe; r++)
        {
            if (stato==ZERO)
                if (immagine[r][c]=='0')
                    conta0++;
                else
                {
                    fprintf(fpOUT, "0%d ", conta0);
                    stato=UNO;
                    conta1=1;
                }
            else /* if (stato==UNO) */
                if (immagine[r][c]=='1')
                    conta1++;
                else
                {
                    fprintf(fpOUT, "1%d ", conta1);
                    stato=ZERO;
                    conta0=1;
                }
        }

        /* vedi Nota */
        if (stato==ZERO)
            fprintf(fpOUT, "0%d\n", conta0);
        else
            fprintf(fpOUT, "1%d\n", conta1);
    }

    fclose(fpIN);
    fclose(fpOUT);

    return EXIT_SUCCESS;
}

/* Nota
   L'output avviene solo durante le transizioni da uno stato
   all'altro quindi bisogna esplicitamente mandare in output anche
   l'ultima sequenza che non essendo seguita da una transizione non
   viene altrimenti emessa
*/