================================
= Riconoscitori di grammatiche =
================================

boolean r1(int[] a) {
   if (a.length < 2 || a[0] != 5 || a[a.length-1] != 5) {
      return false;
   }
   int i = 1;
   for (; i < a.length && (a[i] == 1 || a[i] == 2 || a[i] == 3 || a[i] == 4); i++);
   return i == a.length - 1;
}


*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*


boolean r2(int[] a) {
   if (a.length % 2 != 0) {
      return false;
   }
   int i = 0;
   for (; i < a.length && a[i] == 1 && (a[i+1] == 2 || a[i+1] == 3); i+=2);
   return i == a.length;
}


*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*


boolean r2(int[] a) {
   if (a.length % 2 != 0) {
      return false;
   }
   int i = 0;
   for (; i < a.length && a[i] == 1 && (a[i+1] == 2 || a[i+1] == 3); i+=2);
   return i == a.length;
}


*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*~~*


boolean r3(int[] a) {
   if (a.length % 2 != 1 || a[a.length / 2] != 3) {
      return false;
   }
   int i = 0;
   int l = a.length / 2;
   for (; i < l && a[i] == 1 && a[a.length -1 - i] == 2; i++);
   return i == l;
}


================================
= Riconoscitore di ordinamento =
================================

boolean grows(int[] a) {
   int i = 0;
   for (; i < a.length - 1 && a[i] <= a[i+1]; i++);
   return a.length == 0 || i == a.length - 1;
}


====================
= Prodotto scalare =
====================

double dotProduct(double[] a, double[] b) {
   double res = 0;
   if (a.length == b.length) {
      for (int i = 0; i < a.length; i++) {
         res += a[i] * b[i];
      }
   }
   return res;
}


==================
= Normalizzatore =
==================

double normalise(int[] a) {
   if (a.length == 0) {
      return 0;
   }
   double res = 0;
   int min = a[0];
   int max = a[0];
   for (int i = 0; i < a.length; i++) {
      res += a[i];
      if (a[i] > max) {
         max = a[i];
      }
      if (a[i] < min) {
         min = a[i];
      }
   }
   res = res / a.length / (max - min);
   return max > min ? res : 1;
}


====================================
= Esercizi aggiuntivi: grammatiche =
====================================

/* {0[1]}0 */
boolean r(int[] a) {
   int i = 0;
   for (; i < a.length - 1 && a[i] == 0; i++) {
      if (a[i+1] == 1) {
         i++;
      }
   }
   return i == a.length - 1 && a[i] == 0;
}

/* {0[1]}0 */
boolean r(int[] a) {
   int i = 0;
   for (; i < a.length - 1 && a[i] == 0; i++) {
      if (a[i+1] == 1) {
         i++;
      }
   }
   return i == a.length - 1 && a[i] == 0;
}

/* {2}3 */
boolean r(int[] a) {
   int i = 0;
   for (; i < a.length - 1 && a[i] == 2; i++);
   return i == a.length - 1 && a[i] == 3;
}

/* {2}3{2} */
boolean r(int[] a) {
   if (a.length < 1) {
      return false;
   }
   int i = 0;
   for (; i < a.length - 1 && a[i] == 2; i++);
   if (a[i] != 3) {
      return false;
   }
   i++;
   for (; i < a.length && a[i] == 2; i++);
   return i == a.length;
}

/* 5{1{2|3}4}4 */
boolean r(int[] a) {
   if (a.length < 2 || a[0] != 5 || a[a.length - 1] != 5) {
      return false;
   }
   for (int i = 1; i < a.length - 1; i++) {
      if (a[i] != 1 ) {
         return false;
      }
      i++;
      for(; i < a.length - 2 && (a[i] == 2 || a[i] == 3); i++);
      if (a[i] != 4) {
         return false;
      }
   }
   return true;
}

/* 1^n 2^n */
1boolean r(int[] a) {
   if (a.length % 2 != 0) {
      return false;
   }
   int l = a.length / 2;
   int i = 0;
   for (; i < l && a[i] == 1 && a[a.length - 1 - i] == 2; i++);
   return i == l;
}

/* 1^n 3 2^2n */
boolean r(int[] a) {
   int l = a.length / 3;
   if (a.length % 3 != 1 || a[l] != 3) {
      return false;
   }
   int i = 0;
   for (; i < l && a[i] == 1 && a[l + 1 + i] == 2 && a[a.length - 1 - i] == 2; i++);
   return i == l;
}

/* 1^n 3 2^2n 4 5^n */
boolean r(int[] a) {
   int l = (a.length - 2) / 4;
   if (a.length % 4 != 2 || a[l] != 3 || a[3 * l + 1] != 4) {
      return false;
   }
   int i = 0;
   for (; i < l && a[i] == 1 && a[l + 1 + i] == 2 && a[2 * l + 1 + i] == 2 && a[3 * l + 2 + i] == 5; i++);
   return i == l;
}
	
/* 1^n 3 2^2n 4 [5^n] */
boolean r(int[] a) {
   boolean noFives = a[a.length - 1] != 5;
   int l = (a.length - 2) / (noFives ? 3 : 4);
   if (a.length % (noFives ? 3 : 4) != 2 || a[l] != 3 || a[3 * l + 1] != 4) {
      return false;
   }
   int i = 0;
   for (; i < l && a[i] == 1 && a[l + 1 + i] == 2 && a[2 * l + 1 + i] == 2 && (noFives || a[3 * l + 2 + i] == 5); i++);
   return i == l;
}

/* {1^n 2^n} */
boolean r(int[] a) {
   if (a.length % 2 != 0) {
      return false;
   }
   int i = 0;
   while (i < a.length) {
      int n = i;
      for (; i < a.length && a[i] == 1; i++);
      n = i * 2 - n;
      for (; i < a.length && i < n && a[i] == 2; i++);
      if (i != n) {
         return false;
      }
   }
   return i == a.length;
}


===================================================
= Esercizi aggiuntivi: funzioni su array e numeri =
===================================================

double avgFromTo(int[] a, int start, int end) {
   int sum = 0;
   if (start < 0) {
      start = 0;
   }
   if (end > a.length) {
      end = a.length;
   }
   for (int i = start; i<a.length && i < end; i++) {
      sum += a[i];
   }
   return (double) sum / (end - start);
}

int max(int[] a) {
   if (a.length == 0) {
      return 0;
   }
   int max = a[0];
   for (int i = 1; i < a.length; i++) {
      if (a[i] > max) {
         max = a[i];
      }
   }
   return max;
}

boolean ballot(boolean[] a) {
    int majority = a.length / 2 + 1;
    int t = 0;
    for (int i=0; i<a.length; i++) {
       if (a[i]) {
          t++;
       }
       if (t > a.length / 2) {
          return true;
       }
       if (i - t > a.length / 2) {
          return false;
       }
    }
    return false;
}

boolean isPrime(int n) {
   /*
    * Far more efficient solutions exist! ;)  
    */
   if (n < 2 || n % 2 == 0) {
      return false;
   }
   int i = 3;
   for (; i < n / 2 && n % i != 0; i+=2);
   return i == n/2 || i == n/2 - 1;
}


int nextPrime(int n) {
   /*
    * Far more efficient solutions exist! ;)  
    */
   if(n < 2) {
      return 2;
   }
   int i = n + (n % 2 == 0 ? 1 : 2);
   for (; !isPrime(i); i+=2);
   return i;
}