/*	perf_misch.c -- Matthias Jauernig, 11.12.03					*/
/*	Programm simuliert das perfekte Mischen eines Kartenstapels			*/

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

int main(void){
	// n,k,i sind die einzulesenden Werte
	// p,q,r,s sind Lauf- und Hilfsvariablen
	// anz gibt die minimale Durchlaufszahl bis zur Stapelwiederherstellung an
	int n, k, i, p, q, r, s, anz;
	// a ist das Array, was gemischt wird, b ist stets das Ausgangsarray
	// c und d sind die beiden Teilstapel, in die a immer zerlegt wird
	int *a, *b, *c, *d;

	printf(	"--------------------------------\n"
		"| Perfektes Mischen von Karten |\n"
		"--------------------------------\n\n");

	//################################# Eingabe ######################################
	do{
		printf("Anzahl n der Karten (n gerade, n>0)?: ");
		scanf("%d", &n);
	}while((n<1 && printf("!! Anzahl muss größer 0 sein!\n\n"))
		|| (n%2!=0 && printf("!! Anzahl muss gerade sein!\n\n")));
	do{
		printf("Wieviel mal soll perfekt gemischt werden (>0)?: ");
		scanf("%d", &k);
	}while(k<1 && printf("!! Anzahl muss größer 0 sein!\n\n"));
	do{
		printf("Wert i der i-ten Karte (0<=i<%d)?: ", n);
		scanf("%d", &i);
	}while((i<0 && printf("!! imuss größer gleich 0 sein!\n\n"))
		|| (i>=n && printf("!! i muss kleiner als %d sein!\n\n", n)));

	//########################### Speicherreservierung ###############################
	a=(int *)malloc(n*sizeof(int));
	b=(int *)malloc(n*sizeof(int));
	c=(int *)malloc(n/2*sizeof(int));
	d=(int *)malloc(n/2*sizeof(int));

	//########################### Arrays initialisieren ##############################
	for(p=0; p<n; p++)
		a[p]=b[p]=p;

	printf(	"\n=> Nach 0 mal Mischen: Karte mit Wert %d"
		" ist an %d. Stelle im Stapel.\n", i, i);

	//########################## k-mal perfektes Mischen #############################
	// Schleife läuft solange, bis k-mal gemischt wurde und der Ausgangsstapel wieder-
	// hergestellt wurde, also s==1 (s ist Hilfsvariable, die dies anzeigt)
	for(p=1, s=0; p<=k || s!=1; p++){
		// teile zunächst in die beiden Hilfsstapel
		for(q=0; q<n; q++)
			if(q<n/2) c[q]=a[q];
			else d[q-n/2]=a[q];

		// reißverschlussartig wieder zusammen setzen
		for(q=0, r=0; q<n; q+=2, r++){
			a[q]=c[r];
			a[q+1]=d[r];
		}

		// wenn k-mal gemischt, dann Position der Karte mit Wert i ausgeben
		if(p==k){
			for(r=0, q=0; r<n && q!=1; r++)
			if(a[r]==i){
				printf(	"=> Nach %d mal Mischen: Karte mit Wert %d "
					" ist an %d. Stelle im Stapel.\n\n", k, i, r);
				q=1;
			}
		}

		// wenn Ausgangsstapel noch nicht wieder hergestellt, dann schauen, ob
		// dies in diesem Durchgang der Fall ist, ansonsten s=0 belassen
		if(s!=1){
			for(q=0, s=1; q<n && s==1; q++)
				if(a[q]!=b[q]) s=0;
			// Durchgangsanzahl in anz speichern
			if(s==1) anz=p;
		}
	}
	printf("==> Nach %d Durchläufen wurde der Ausgangsstapel wieder hergestellt!\n\n", anz);

	//################################# Aufräumen ####################################
	free(a); free(b); free(c); free(d);
	return 0;
}

/* 3 Testläufe
##########################################################################################
1.) wenn i=0, dann muss die Karte immer auf Platz 0 bleiben, egal wie groß n,k sind
##########################################################################################
--------------------------------
| Perfektes Mischen von Karten |
--------------------------------

Anzahl n der Karten (n gerade, n>0)?: 10000
Wieviel mal soll perfekt gemischt werden (>0)?: 10000
Wert i der i-ten Karte (0<=i<10000)?: 0

=> Nach 0 mal Mischen: Karte mit Wert 0 ist an 0. Stelle im Stapel.
=> Nach 10000 mal Mischen: Karte mit Wert 0  ist an 0. Stelle im Stapel.

==> Nach 300 Durchläufen wurde der Ausgangsstapel wieder hergestellt!

##########################################################################################
2.) wenn i=n-1, dann muss die Karte immer auf Platz n-1 bleiben, egal wie groß n,k sind
##########################################################################################
--------------------------------
| Perfektes Mischen von Karten |
--------------------------------

Anzahl n der Karten (n gerade, n>0)?: 1000
Wieviel mal soll perfekt gemischt werden (>0)?: 100000
Wert i der i-ten Karte (0<=i<1000)?: 999

=> Nach 0 mal Mischen: Karte mit Wert 999 ist an 999. Stelle im Stapel.
=> Nach 100000 mal Mischen: Karte mit Wert 999  ist an 999. Stelle im Stapel.

==> Nach 36 Durchläufen wurde der Ausgangsstapel wieder hergestellt!

##########################################################################################
3.) wenn i=4, n=10 und k=3, so muss i am Ende an 5. Stelle sein und nach 6 mal Mischen
der Ausgangsstapel wieder hergestellt werden (Rechnung per Hand)
##########################################################################################
--------------------------------
| Perfektes Mischen von Karten |
--------------------------------

Anzahl n der Karten (n gerade, n>0)?: 10
Wieviel mal soll perfekt gemischt werden (>0)?: 3
Wert i der i-ten Karte (0<=i<10)?: 4

=> Nach 0 mal Mischen: Karte mit Wert 4 ist an 4. Stelle im Stapel.
=> Nach 3 mal Mischen: Karte mit Wert 4  ist an 5. Stelle im Stapel.

==> Nach 6 Durchläufen wurde der Ausgangsstapel wieder hergestellt!			*/