#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>
using namespace std;
struct Bits{
Bits *next;
Bits *last;
bool onlyOneBit;//true = vain yksi bitti, false = yli yksi bitti
bool bit; // bit == true == 1, bit == false == 0
unsigned int index;
};
struct Index{
unsigned int value;
Index *next;
};
Bits *temp, *temp2, *temp3;
bool lastBits = false;
bool lastBit = false;
void printBits(Bits *a);
bool deleteBits(Bits *a);
void addIndex(unsigned int index);
void printIndex();
void freeIndex();
void freeMemory(Bits *a);
Index *index_a = (Index *)malloc(sizeof(Index *));
Index *index_ap = index_a; //index ap on listan loppu ja index_a on listan alku
//bool init_index = true;
int main(void){
char bit;
bool cur_bit;
bool last_bit;
bool onlyOneBit;
index_ap->next = NULL;
Bits *a = (Bits *)malloc(sizeof(Bits *));
a->bit = (fgetc(stdin) == '1'); //otetaan ensimmäinen bit, jotta sitä ei pidä joka kerta tarkistaa while-lauseen for-lauseessa, tms, jne..
//(buffer[i] == '1')
if (feof(stdin)) {
cout << endl << "QAQ"; //vain yksi bit syötetty = yhtä ei voida poistaa = häviö
return 0;
}
a->next = NULL;
a->last = NULL;
a->index = 0;
Bits *ap = a;
onlyOneBit = true;
unsigned int len = 256;
unsigned int length;
char buffer[len];
while(!lastBit) {
//cout << "asdf";
fgets(buffer, len, stdin);
length = strlen(buffer);
if (buffer[length - 1] == '\n') {
buffer[length - 1] = buffer[length - 2];
//length--; //'poistetaan' '\n'
//length--;
lastBits = true;
//nyt voidaan poistaa myös ne Bits:it, joiden ap->last ja ap->next on NULL
}
//muodostetaan ihan ensimmäiseksi lista, sitten tehdään niistä pointersToBits
for (int i = 0; i < length; i++){
if (buffer[i] == '1') cur_bit = 1;
else cur_bit = 0;
if (cur_bit != ap->bit || (lastBits && i == length - 1)) {
if (lastBits) {
if (i == length - 1) {
lastBit = true;
//printBits(a);
//cout << "ekomatti1 << " << buffer << " " << i << " ";
}
}
//eri bitti, vaihdetaan
if (ap->last != NULL) ap->index = (ap->last)->index + 1;
ap->onlyOneBit = onlyOneBit;
//ny on uusi alkio linkattu
//ap on nyt saatu uusi alkio
//tarkistetaan voidaanko poistaa jokin alkio
if (deleteBits(ap)) { //ap, tai temp voitiin poistaa
if (lastBit) {
//cout << "ap:" << (ap->last)->index << " " << (ap->last)->bit << " " << (ap->last)->onlyOneBit << endl;
/*while (*/deleteBits(ap);//);
}
//cout << endl;printBits(a);
} else if (lastBit) { //alkioita ei voitu poistaa, viimeiset alkiot ovat menossa -> peli on päättynyt, peliä ei voitu ratkaista
//cout << endl;printBits(a);
cout << endl << "QAQ";
//printIndex();
freeMemory(a);
freeIndex();
return 0;
}
ap->next = (Bits *)malloc(sizeof(Bits *));
(ap->next)->last = ap;
ap = ap->next;
ap->bit = cur_bit;
//ap->onlyOneBit = false;
ap->next = NULL;
onlyOneBit = true;
} else if (onlyOneBit){
onlyOneBit = false;
}
}
}
//printBits(a); //tulostaa bitit a:sta alkaen
printIndex(); //tulostaa indeksit
freeIndex();
freeMemory(a);
return 0;
}
bool deleteBits(Bits *ap){ //ottaa syötteenä ap:n, eikä temp:iä poistettavasta alkiosta, sillä silloin saatettaisiin joutua tekemään turhaa kaksinkertaista tarkistusta, ja jouduttaisiinki
if ((temp = ap->last) != NULL) {
if ((temp = temp->last) != NULL){ //taaksepäin on linkki = temp, eli poistettava alkio on olemassa <-> eteenpäin on linkki, sillä ap on olemassa
//if (lastBit) cout << "asdfasdf"; pitäisi pitää paikkansa
//cout << "asf";
//tarkastetaan ensin tilanne, jossa molemmat linkit ovat täysiä
//kaikissa näissä temp:n pitää !onlyOneBit, sillä yhden bitin jonoja ei voida poistaa
if (!temp->onlyOneBit){ //vasemmalle linkattava on yli yhden bitin, tarkistetaan onko sillä linkki toiseenkin suuntaan
if ((temp->last) != NULL) {
if ((temp->last)->last != NULL){ //linkki löytyi, temp-alkio voidaan poistaa
//yhdistetään(, ei linkata) temp:iä seuraava ja sitä edeltävä alkio toisiinsa
//temp2 on temp:n vasen, eli last-puoli ja temp3 on oikea, eli next-puoli
temp2 = temp->last; //osoitetaan temp:lla temp:n lastiin, jotta voidaan poistaa temp
temp2->onlyOneBit = false; //uusi koko on aina väh.2bit
//temp2->bit // ei muutu
temp3 = temp->next;
//ap:n indeksiksi tulee poisttavan, eli temp:n indeksi
ap->index = temp->index; //muita indeksejä ei pidä vaihtaa, temp2:n indeksi säilyy temp2:sen ja temp3:sen hybridillä
addIndex(temp->index); //lisätään index myös listaan
free(temp); //voidaan poistaa temp, sillä molempiin sen ympärillä oleviin alkioihin osoitetaan jo
//säilytetään ainoastaan temp2, sillä siinä on kaikki tarvittava info -> aina kun poistetaan yksi alkio, poistetaan käytännössä kaksi, paitsi kun poistetaaan viimeinen alkio, jos poistetaan
temp2->next = temp3->next; //nyt kaikki info on temp2:ssa, joten:
ap->last = temp2;
free(temp3);
return true; //alkio voitiin poistaa
}
} else {
if (lastBit) {
goto A;
}
}
} else goto A;
//return false; //turhaan, sillä lopussa on kuitenkin return false
} else goto A; //lastbit, 1 takana
} else { //ap:lla ei ole vasemmalle linkkiä, joten poistettavalla alkiolla(== ap) ei ole myöskään varmasti oikealle päin linkkiä
A: //jos linkkejä ei ole kumpaankaan suuntaan, ainoastaan ->last->last:n puuttuessa on tämä tilanne, sillä ->last->last:lla on aina ->next->next
//->tarkistetaan onko peli päättynyt = ei tule lisää merkkejä = lastBits == true
//cout << "ekomatti << ";
if (lastBit){ //jos peli on päättynyt
//cout << "ekomatti2 << ";
if (ap->last != NULL) {
ap = ap->last;
}
if (!ap->onlyOneBit) { //jos ap, poistettava alkio on yli yhden bitin bittainen, peli voidaan voittaa = alkio voidaan poistaa
temp = ap; //pointataan ap:n pointtaamaan alkioon, sillä ap pitää poistaa, mutta ap:n pitää toisaalta säilyä
addIndex(ap->index);
if ((ap = ap->last) != NULL) { //jos alkioita = alkio on vielä jäljellä
//(yläpuoli)siirretään ap yhden alkion takaisinpäin, sillä edellinen alkio = uusin alkio = listan pää poistetaan
if ((temp2 = temp->next/*==ap->next->next*/) != NULL){ //myös ap:n seuraava alkio on olemassa != mahdotonta, mutta harvinaista
//yhdistetään alkiot ap ja ap->next->next
//ap->onlyOneBit = false; //aivan turha laittaa falseksi, sillä tiedetään että se on aina false ja se poistetaan nyt jokatapauksessa
addIndex(ap->index); //lisätään ap:n indeksi, sillä se poistetaan nytten
//indeksi jää samaksi, mikä se nyt on
if (ap->last == NULL && temp2->next == NULL) {
//poistetaan temp, ja yhdistetään ap ja temp2
return true;
}
//free(temp->next); //poistetaan vanha alkio
//free(ap); //ja myös sen toinen osa, eli uusi hybridi, sillä peli on jokatapauksessa nyt päättynyt, joko häviöön tai voittoon
//cout << "last";
//kaikki ap, temp, temp->next on poistettu
//cout << "asdf";
}
} else return true;
//free(temp); //ap voi olla joko null tai ap->last, eli toivottavasti eka alkio, jos halutaan voittaa
} else { //muutoin peliä ei voida voittaa = alkiota ei voida poistaa = peli on päättynyt
return false;
}
}
} /*otherwise reutnr false*/
//tarkastetaan sitten tilanne, jossa molemmat linkit ovat tyhiä
//ja näiden else, eli tilanne, jossa toinen linkeistä on tyhjä saadaan 'else'.llä
//täällä poistetaan ne alkiot,
return false;
}
void freeMemory(Bits *a){
if (a==NULL) return;
Bits *ap = a;
Bits *ap2;
do{
ap2 = ap->next;
free(ap);
ap = ap2;
}while(ap2 != NULL) ;
}
void freeIndex(){
if (index_a==NULL) return;
Index *ap = index_a;
Index *ap2;
do{
ap2 = ap->next;
free(ap);
ap = ap2;
}while(ap2 != NULL) ;
}
void addIndex(unsigned int index){
static bool init_index = true;
if (!init_index) {
index_ap->next = (Index *)malloc(sizeof(Index *)); //luodaan uusi alkio
index_ap = index_ap->next; //siirrytään siihen
} else init_index = false;
index_ap->value = index; //muokataan sen arvo ja
index_ap->next = NULL; //alustetaan seuraava ap NULL == 0:ksi
}
void printBits(Bits *a){
if (a==NULL) return;
Bits *ap = a;
do{
cout << "bit: " << ap->onlyOneBit << " " << endl;
}while((ap = ap->next) != NULL) ;
}
void printIndex(){
if (index_a == NULL) return;
Index *ap = index_a;
do{
cout << ap->value << " ";
}while((ap = ap->next) != NULL) ;
}
