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

#define MAX_PROM_V_KLAUSULI 100
#include "problem.c"
#include "tabu.c"

struct moznost_s {
        unsigned short vaha;
        unsigned short index;
};

/** Porovnani */
#define JE_LEPSI(res1, res2)                            \
        (res1##_splneno > res2##_splneno ||             \
                ( res1##_splneno == res2##_splneno &&   \
                  res1##_vaha > res2##_vaha )           \
        )
#define NENI_HORSI(res1, res2)                          \
        (res1##_splneno > res2##_splneno ||             \
                ( res1##_splneno == res2##_splneno &&   \
                  res1##_vaha >= res2##_vaha )          \
        )

/** Vlastni heuristika */
reseni_t* tabu_search(const struct problem_s *problem, int max_kroku)
{
        reseni_t *aktualni_reseni, *nejlepsi_reseni;
        int i, j, restartuj,
            nejlepsi_reseni_vaha, nejlepsi_reseni_splneno, // Celkove nejlepsi nalezene reseni
            aktualni_reseni_vaha, aktualni_reseni_splneno, // aktualni zpracovavany stav
            nejlepsi_reseni_kroku_vaha, nejlepsi_reseni_kroku_splneno, nejlepsi_zmena_kroku; // nejlepsi reseni v kroku

        // Tabulist na promenne
        struct tabulist_s *tabu;
        tabu = tabulist_new((int)(3.425 + 0.10425*problem->promennych), problem->promennych);

        // Pro vyber z vice moznosti
        int moznosti_index = 0;
        struct moznost_s *moznosti = (struct moznost_s *)malloc(sizeof(struct moznost_s) * problem->promennych);

        // Dlouhodoba pamet
        int posledni_zmena[1000];
        int naposledy_splneno[1000];
        int pouzij_pamet = problem->promennych/2;
        int posledni_zlepseni;

        // Alokace pameti
        aktualni_reseni = problem_vektor_reseni( problem );
        nejlepsi_reseni = problem_vektor_reseni( problem );

        restartuj = 0.6*problem->promennych*problem->promennych;

        problem_nahodne_ohodnoceni( problem, aktualni_reseni, 0.5 );
        problem_kopiruj_reseni(problem, nejlepsi_reseni, aktualni_reseni);

        nejlepsi_reseni_vaha = problem_vaha( problem, nejlepsi_reseni );
        nejlepsi_reseni_splneno = problem_splneno_klausuli( problem, nejlepsi_reseni );

opakuj: for( i = 1; i <= problem->promennych; i++ )
                posledni_zmena[i] = max_kroku;
        for( i = 0; i <= problem->klausuli; i++ )
                naposledy_splneno[i] = max_kroku;

        posledni_zlepseni = max_kroku;

        while(max_kroku--){
                problem_splneno_aktualizuj_vyskyt( problem, aktualni_reseni, naposledy_splneno, max_kroku);

                /////////////////////////////////////////////////////////////////////////////////
                // Pokud se dlouho nezlepsilo, spln nejdele nesplnenou formuli //////////////////
                if( posledni_zlepseni - pouzij_pamet > max_kroku ){
                        int max_krok = 0, max_krok_idx = 0, max_klausule_idx = 0;
                        for( i = 0; i < problem->klausuli; i++ )
                                if( naposledy_splneno[i] > max_krok ){
                                        max_klausule_idx = i;
                                        max_krok = naposledy_splneno[i];
                                }
                        max_krok = 0; struct klausule_s *klausule; int prom;
                        klausule = problem->klausule[ max_klausule_idx ];
                        for( i = 0; i < klausule->promennych; i++ ){
                                prom = klausule->promenne[i] > 0 ? klausule->promenne[i] : -klausule->promenne[i];
                                if( naposledy_splneno[ prom ] > max_krok ){
                                        max_krok = naposledy_splneno[ prom ];
                                        max_krok_idx = prom;
                                }
                        }
                        aktualni_reseni[ max_krok_idx ] = !aktualni_reseni[ max_krok_idx ];
                        posledni_zmena[ max_krok_idx ] = max_kroku;
                        tabulist_vloz( tabu, max_krok_idx );
                        posledni_zlepseni = max_kroku;
                }

                ///////////////////////////////////////////////////////////////////////////////
                // Zkus zmenit vsechny promenne ///////////////////////////////////////////////
                nejlepsi_reseni_kroku_vaha = 0; nejlepsi_reseni_kroku_splneno = 0; nejlepsi_zmena_kroku = 0;
                for( i = 1; i <= problem->promennych; i++ ){
                        aktualni_reseni[i] = !aktualni_reseni[i];

                        aktualni_reseni_vaha = problem_vaha( problem, aktualni_reseni );
                        aktualni_reseni_splneno = problem_splneno_klausuli( problem, aktualni_reseni );

                        // Pokud je reseni nejlepsi nalezene - Aspiracni kriterium
                        // nebo neni na tabulistu
                        if( JE_LEPSI( aktualni_reseni, nejlepsi_reseni) || !tabulist_obsahuje( tabu, i )  ){
                                if( aktualni_reseni_splneno > nejlepsi_reseni_kroku_splneno ){
                                        // Vytvorit novy vyber moznosti
                                        moznosti[0].index = i;
                                        moznosti[0].vaha = aktualni_reseni_vaha;
                                        moznosti_index = 1;
                                        nejlepsi_reseni_kroku_splneno = aktualni_reseni_splneno;
                                } else if( aktualni_reseni_splneno == nejlepsi_reseni_kroku_splneno ){
                                        moznosti[moznosti_index].index = i;
                                        moznosti[moznosti_index].vaha = aktualni_reseni_vaha;
                                        moznosti_index += 1;
                                }
                        }
                        aktualni_reseni[i] = !aktualni_reseni[i];
                }

                ////////////////////////////////////////////////////////////////////////////////
                // Vybere se nejlepsi zmena a spocita sumu vah /////////////////////////////////
                int vaha_sum = 0, max_vaha = 0, nejlepsi_zmena_kroku = 0;
                for( i = 0; i < moznosti_index; i++ ){
                        vaha_sum += moznosti[i].vaha;
                        if( moznosti[i].vaha > max_vaha ){
                                max_vaha = moznosti[i].vaha;
                                nejlepsi_zmena_kroku = moznosti[i].index;
                        }              
                }

                nejlepsi_reseni_kroku_vaha = moznosti[ nejlepsi_zmena_kroku ].vaha;
                ////////////////////////////////////////////////////////////////////////////////
                // Kdyz se naslo lepsi reseni //////////////////////////////////////////////////
                if( JE_LEPSI( nejlepsi_reseni_kroku, nejlepsi_reseni ) ){
                                nejlepsi_reseni_vaha = nejlepsi_reseni_kroku_vaha;
                                nejlepsi_reseni_splneno = nejlepsi_reseni_kroku_splneno;

                                problem_kopiruj_reseni( problem, nejlepsi_reseni, aktualni_reseni );
                                nejlepsi_reseni[ nejlepsi_zmena_kroku ] = !nejlepsi_reseni[ nejlepsi_zmena_kroku ];
                                assert( problem_splneno_klausuli(problem, nejlepsi_reseni) == nejlepsi_reseni_kroku_splneno );
                                posledni_zlepseni = max_kroku;

                                if(nejlepsi_reseni_splneno == problem->klausuli && problem->prvni_reseni)
                                        goto konec;
                }

                //////////////////////////////////////////////////////////////////////////////
                // Pokud se uz hodne dlouho nenaslo zlepsujici reseni ////////////////////////
                if( posledni_zlepseni > max_kroku + restartuj ){
                        problem_nahodne_ohodnoceni( problem, aktualni_reseni, 0.5 );
                        tabulist_vyprazdni( tabu );
                        pouzij_pamet *= 2;
                        restartuj *= 2;
                        // Pokud nam naposledy chybela jen jedna klausule, tak ji pro zacatek "maximalne" splnime
                        if( nejlepsi_reseni_splneno == problem->klausuli - 1 )
                                for( i = 0; i < problem->klausuli; i++ )
                                        if( ! klausule_je_splnena( problem->klausule[i], nejlepsi_reseni ) ){
                                                for( j = 0; j < problem->klausule[i]->promennych; j++ )
                                                        if( problem->klausule[i]->promenne[j] < 0 ){
                                                                aktualni_reseni[ -problem->klausule[i]->promenne[j] ] = 0;
                                                                tabulist_vloz( tabu, -problem->klausule[i]->promenne[j] );
                                                        } else {
                                                                aktualni_reseni[ problem->klausule[i]->promenne[j] ] = 1;
                                                                tabulist_vloz( tabu, problem->klausule[i]->promenne[j] );
                                                        }
                                                break;
                                        }
                        goto opakuj;
                }

                /////////////////////////////////////////////////////////////////////////////
                // Nahodne s pravdepodobnosti umernou vaze vybereme nasledujici stav ////////
                float prah = (vaha_sum * (rand() / (RAND_MAX + 1.0)));
                vaha_sum = 0;
                for( i = 0; i < moznosti_index; i++ ){
                        vaha_sum += moznosti[i].vaha;
                        if( vaha_sum > prah ){
                                nejlepsi_zmena_kroku = moznosti[i].index;
                                break;
                        }              
                }

                /////////////////////////////////////////////////////////////////////////////
                // Prechod do dalsiho stavu /////////////////////////////////////////////////
                aktualni_reseni[nejlepsi_zmena_kroku] = !aktualni_reseni[nejlepsi_zmena_kroku];
                posledni_zmena[nejlepsi_zmena_kroku] = max_kroku;
                tabulist_vloz( tabu, nejlepsi_zmena_kroku );
        }


konec:  free(aktualni_reseni);
        free(moznosti);
        tabulist_znic( tabu );
        return nejlepsi_reseni;
}

/** Main - nacte vstup a zavola heuristiku */
int main(int argc, char *argv[])
{
        int znak, klausuli, literalu, max_kroku, i;
        char buf[30];
        reseni_t *reseni;
        
        struct problem_s *problem;
        signed short promenne_klausule[MAX_PROM_V_KLAUSULI];


        // Nacteni specifikace klausule a pripadnych vah
        while(1){
                znak = getchar();
                if( znak == ' ' ) continue;
                if( znak == 'p' ){
                        scanf("%s", buf);
                        if( strcmp(buf, "cnf") == 0 ){
                                scanf("%d%d", &literalu, &klausuli);
                                problem = problem_new(literalu, klausuli, 1);
                                break;
                        } else if( strcmp(buf, "wcnf") == 0 ) {
                                scanf("%d%d", &literalu, &klausuli);
                                problem = problem_new(literalu, klausuli, 0);
                                for( i = 1; i <= literalu; i++ ){
                                        if( scanf("%hd", &problem->vaha[i]) != 1 ||  problem->vaha[i] < 1){
                                                fprintf(stderr, "Spatny vstup - ocekavana vaha (prirozene cislo)\n");
                                                exit(EXIT_FAILURE);
                                        }
                                }
                                break;
                        }
                        fprintf(stderr, "Nepodporovany typ formule\n");
                        exit(EXIT_FAILURE);
                } else if ( znak == 'c' ){
                        while( (znak = getchar()) != '\n' )
                                if( znak == EOF ){
                                        fprintf(stderr, "Spatny vstup - neocekavany konec\n");
                                        exit(EXIT_FAILURE);
                                }
                } else {
                        fprintf(stderr, "Spatny vstup - neplatny znak\n");
                        exit(EXIT_FAILURE);
                }
        }
        // Nacteni klausuli
        while(klausuli--){
                int a;
                for( i = 0; i < MAX_PROM_V_KLAUSULI; i++ ){
                        scanf("%d", &a);
                        if( a == 0 ) break;
                        promenne_klausule[i] = a;
                }
                problem_pridej_klausuli(problem, i, promenne_klausule);
        }

        max_kroku = argc == 2 ? atol(argv[1]) : 4*problem->promennych*problem->promennych;
        
        reseni = tabu_search( problem, max_kroku );

        // Vypis reseni
        printf("Splneno: %d Vaha: %d Ohodnoceni: ", problem_splneno_klausuli( problem, reseni), problem_vaha( problem, reseni ));
        for( i = 1; i <= problem->promennych; i++ ) printf("%d", reseni[i] ? 1 : 0 );
        printf("\n");

        free( reseni );
        problem_znic( problem );

        return 0;
}