Brain Fork - Optimization - Puzzle discussion

Bonjour,
j’ai un soucis avec le test 17 (=test 16 en validation). Je passe les tests mais pas la validation.
D’où ma question sur la libellé du test: “Alphabet complet x11 séparé par une lettre”.
Dans les tests j’ai supposé qu’on avait l’alphabet complet classé de A à Z suivi d’une lettre fixe quelconque, l’ensemble répété 11 fois.
Comme ça ne passait pas en validation, j’ai supposé que la lettre intercalaire pouvait varier. Mais ça ne passait pas non plus en validation.
Il me reste à supposer que l’alphabet est complet mais déclassé.
Avant de faire ce test, je voulais savoir si mon raisonnement tien la route. Merci.

Hello,
I have a problem with test 17 (=test 16 in validation). I pass the tests but not the validation.
Hence my question about the wording of the test: “Complete alphabet x11 separated by a letter”.
In the tests I assumed that we had the complete alphabet classified from A to Z followed by any fixed letter, the whole repeated 11 times.
Since it didn’t pass in validation, I assumed that the intervening letter could vary. But it didn’t pass in validation either.
I still have to assume that the alphabet is complete but downgraded.
Before doing this test, I wanted to know if my reasoning holds. Thank you.

Translated with www.DeepL.com/Translator (free version)

Hey.
I’m not sure to understand. Since your code is supposed to work for any test case conform to the statement, what’s the point to know exactly the content of this validator? Sounds like you’re trying to hard-code the solution…

1 Like

Bonjour,
Oui et non. Au début j’ai codé une solution globale qui fonctionnait mais avec un score très moyen.
Avoir avoir parcouru le forum et découvert les “boucles” je ne voyait pas comment les utiliser efficacement sans les affecter à des tests spécifiques. Les validateurs sont bien sûr différents des tests mais seulement dans les valeurs. Par exemple le test 19 (=18 en validation) est une “Séquence incrémentale séparée par des espaces”. Par programmation, il est possible de détecter ce cas et de basculer sur une portion de programme approriée. Est-ce du hard-coding?

Hello,
Yes and no. At the beginning I coded a global solution that worked but with a very average score.
Having browsed the forum and discovered the “loops” I could not see how to use them effectively without assigning them to specific tests. The validators are of course different from the tests but only in the values. For example test 19 (=18 in validation) is an “Incremental sequence separated by spaces”. By programming, it is possible to detect this case and switch to a learned portion of the program. Is this hard-coding?

Not really… Partial hard-coding perhaps? :sweat_smile:
I thought you were trying to hard-code the precise values. (What you totally can do if you want to, and if you find them… Though probably no one will help you to do it. :wink: )
I don’t know the exact content of the validator, but it is supposed to be equivalent to the test, so I’ll say your hypothesis is worth the try. Or perhaps just a reversed alphabet? Anyway: Test it. Theoretically nobody knows the validators of official puzzles, so you’ll better find the answer yourself than wait for it.
Good luck! :slight_smile:

1 Like

Okay, thanks for your answers.

I put again my question as I didn’t really get an answer.
All my test pass, my issue is with the score. How come the score of each test does not correspond to the length of the printed sequence but is sometimes longer?

I am using python. The 2 last lines of my code are:

debug(f'Total order size: {len(orders)}')
print(orders)

And for certain tests, for example test 24, I got :
[DEBUG] Total order size: 2295
Whereas the test score is 2805 (2805 steps)
All my test pass but with the longest tests, there is always a difference between the length of what I print and the number of steps being executed (which is always bigger).

how do you get this value for the score? Nb of characters on test 24 (score) is indeed 2295

First, I had issues to reply because the reply button is hidden at the bottom of the text box where we write. (tested on Edge, Chrome and FF).

See the recording: Game Replay - CodinGame
The number of steps displayed is 2805.

What matters is the size of the string containing your orders. If you use loops, some orders will be used several times so it’s normal if the number of steps displayed is higher.

For example for this testcase the length of my string is 1239 but the number of steps is 1685.

OK. I think I got it. I will try again with that in mind. I thought something was broken. Happy that it was not the case.

Hi. It’s me again. I’ve just came back to the brain fork. When I factorize the alphabet using the ‘+[.+]’ pattern instead of writing each letter 1 by 1, I get the exact same total score (8621 in my case), whereas I’m supposed to spare about 800 characters.

What am I missing?

The validator might differ from the testcase. For example if it’s called alphabet it probably has all letters but maybe it doesn’t start with A, or maybe the letters are doubled for example, or maybe it’s reversed or whatever.

1 Like

I am starting again from scratch. Thanks for the explanations.

Thanks all for your helps. I am progressing fast right now. Currently 6525 points…

This is the most annoying puzzle…
which is kind of experience.

Hello,
I did the puzzle as asked in my mission board, however the mission isn’t checked…
Is it a bug as the name and rules of the game changed? (The aim is less than 4000 chars, not 6500)

The leaderboard shows your current performance is 13,779 chars.
https://www.codingame.com/multiplayer/optimization/brain-fork/leaderboard?column=keyword&value=narguilo

Thanks, I didn’t know where to look :o:

Still not sure where it comes from, but I should find out now!

2 Likes

Bonjour à tous,

Je me heurte à un gros mur je suis à cours d’idée pour réduire mon score !!!

J’ai jouer avec les boucles, les Patterns , les recherche de runes contenant la mêmes lettre … et la ben je n’ai plus d’idée et du coup je me retrouve un peu bloqué …

Quelqu’un pourrait-il me guidé vers la voie de la liberté s’il vous plait?

Alain

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

 * Auto-generated code below aims at helping you parse

 * the standard input according to the problem statement.

 **/

int char_to_int(char c)

{

    int value = -1;

    if( c == ' ')

    {

        return value;

    }

    for(char cc = 'A' ; cc <= 'Z' ; cc++)

    {

        value++;

        if( cc == c)

        {

            return value;

        }

    }

    value = -1;

    return value;

}

class Rune

{

    public :

    Rune()

    {

        //On démarre l'alphabet à zéro, donc -1 = espace

        Number = -1 ;

    }

    int Get_Number()

    {

        return Number;

    }

    void Set_Number(int n)

    {

        if( n > 25)

        {

            this->Number = -1;

        }

        else if ( n < -1)

        {

            this->Number = 25;

        }

        else

        {

            this->Number = n;

        }

       

    }

    private :

    int Number;

};

 class Player

 {

     public :

     Player()

     {

         code.clear();

         Position = 0;

         Tape_count = 0;

         Init_rune();

         //On laisse la première rune en espace pour faciliter le texte

         Avance();

     }

     void Avance()

     {

         code += '>';

         Position++;

         if( Position >= 29)

         {

             Position = 0;

         }

     }

     void Recule()

     {

         code += '<';

         Position--;

         if( Position < 0)

         {

             Position = 29;

         }

     }

     void Tape_la_rune()

     {

         code += '.';

         Tape_count++;

     }

     void Augmente_la_rune()

     {

         code += '+';

         rune[Position].Set_Number(rune[Position].Get_Number() + 1);

     }

     void Diminue_la_rune()

     {

         code += '-';

         rune[Position].Set_Number(rune[Position].Get_Number() - 1);

     }

     void Init_rune()

     {

         for(int i = 0; i < 30 ; i++)

         {

             rune.push_back(Rune());

         }

     }

     void Set_the_letter(int c)

     {

         int Wanted_letter = c;

         

            if(rune[Get_Position()].Get_Number() > Wanted_letter)

            {

                       

                if( Wanted_letter < 10 && rune[Get_Position()].Get_Number() > 18)

                {

                    while(rune[Get_Position()].Get_Number() != Wanted_letter)

                    {

                        Augmente_la_rune();

                    }

                }

                else

                {

                    while(rune[Get_Position()].Get_Number() != Wanted_letter)

                    {

                        Diminue_la_rune();

                    }

                }

            }

            else

            {

                if( Wanted_letter > 18 && rune[Get_Position()].Get_Number() < 10)

                {

                    while(rune[Get_Position()].Get_Number() != Wanted_letter)

                    {

                        Diminue_la_rune();

                    }

                }

                else

                {

                    while(rune[Get_Position()].Get_Number() != Wanted_letter)

                    {

                        Augmente_la_rune();

                    }

                }

            }

     }

    void Loop_thru_Pattern(string Pattern,string str)

    {

        //On mets en place toute les lettres du pattern

        for(int i = 0 ; i < Pattern.size() ; i++)

        {

           

            int actual_letter = char_to_int(Pattern.at(i));

            Avance();

           

            //Rune qui contient la lettre

            Set_the_letter(actual_letter);

        }

        //On compte combien de fois le patten se repete

        int size  = (str.size()  / Pattern.size() ) ;

               

        cerr << "Nombre de tour neccessaire : " << size/25 << " et il reste : " << (size%25) << endl;

        int loop_number = (size/25);

        //On compte combien il nous reste

        int reste;

        if(loop_number == 0)

        {

            loop_number++;

            reste = 0;

        }

        else

        {

            reste = (size%25);

        }

        int needed_size = ((size - reste)) ;

        while(loop_number != 0)

        {

            cerr << "Loop turn : " << loop_number << endl;

           

            int next_letter  = (needed_size / loop_number) - 1;

                       

            cerr << next_letter << endl;

                   

            Avance();

            //rune que l'on doit remettre à zéro

                   

            Set_the_letter(next_letter);

            add_to_code('[');

            for(int i = 0 ; i < Pattern.size() ; i++)

            {

                Recule();

            }

            for(int i = 0 ; i < Pattern.size() ; i++)

            {

                Tape_la_rune();

                Avance();

            }

                   

            Diminue_la_rune();

            add_to_code(']');

            //Nous sommes à un espace donc on remet la rune à -1

            rune[Get_Position()].Set_Number(-1);    

            loop_number--;

            needed_size -= (25*loop_number);

            if(reste != 0)

            {

                for(int i = 0 ; i < Pattern.size()  ; i++)

                {

                    Recule();

                }

            }

                                               
           

        }

               

        cerr << "Reste = " << reste << endl;

               

        for(int i = 0 ; i < reste   ; i++)

        {

            if(Pattern.size() != 1)

            {

                for(int i = 0 ; i < Pattern.size() ; i++)

                {

                    Tape_la_rune();

                    Avance();

                }

            }

            else

            {

                Tape_la_rune();

            }

           

        }

           

    }

    string search(string str)

    {

        string pattern = "";

       

        if( !str.empty())

        {

            //On recherche un pattern

           

            for(int i = 0 ; i <= str.size() ; i++)

            {

                cerr << str.at(i) << endl;

                string Pat = str.substr(0,i+1);

                string text = str.substr(Pat.size(),str.size());

                if(Pattern_search(Pat,text))

                {

                    return Pat;

                }

            }

           
           

        }

        return pattern;

    }

    bool Pattern_search(string Pattern,string text)

    {

   

        for(int i = 0 ; i < text.size() ;i++)

        {

            for(int j = 0 ; j < Pattern.size() ; j++)

            {

               

                if(i+j < text.size() && Pattern.at(j) != text.at(i+j) )

                {

                    return false;

                }

            }

           

            if( i + (Pattern.size() - 1) <= text.size())

            {

                i += Pattern.size() - 1;

            }

            else

            {

                return false;

            }

           

        }

        cerr << Pattern << endl;

        return true;

    }

    //Recherche du chemin le plus rapide

    void Search_letter(string str)

    {

        string Pattern = search(str);

        if( !Pattern.empty() && Pattern != str)

        {

            cerr << "Nous avons un pattern : " << Pattern << endl;

            Loop_thru_Pattern(Pattern,str);

            return;

        }

        search(str);

       

        for(int i = 0 ; i < str.size() ; i++)

        {

            if( Position == 0)

            {

                Avance();

            }

            int search = char_to_int(str.at(i));

           

            bool exist = false;

            //On recherche dans nos runes si nous avons déja cette lettre

            for(int i = 0 ; i < rune.size() ; i++)

            {

                if(rune[i].Get_Number() == search)

                {

                    Aller_a_la_rune(i);

                    Tape_la_rune();

                    exist = true;

                    break;

                }

            }

            cerr << "La lettre " << str.at(i) << " n'as pas encore été utilisée" << endl;

           

            //Si aucune rune ne contient notre lettre on cherche le moyen le plus court pour y acceder

            if(!exist)

            {

                Set_the_letter(search);

                               

                Tape_la_rune();

                if(i + 1 < str.size() && char_to_int(str.at(i + 1)) != search && search != -1)

                {

                    Avance();

                }

               

            }

        }

    }

    void Aller_a_la_rune(int n)

    {

       

        if( n < Position)

        {

            while( n != Position)

            {

                Recule();

            }

           

        }

        else if( n > Position)

        {

            while( n != Position)

            {

                Avance();

            }

        }

    }

           

    void Play(string str)

    {

       

        Search_letter(str);

       

    }

     string Get_code()

     {

         return code;

     }

     

     void add_to_code(char c)

     {

         code += c;

     }

     int Get_tape_count()

     {

         return Tape_count;

     }

     int Get_Position()

     {

         return Position;

     }

     

     private :

     string code ;

     int Position;

     int Tape_count;

     vector<Rune> rune;

 };

int main()

{

    string magic_phrase;

    getline(cin, magic_phrase);

    Player tim = Player();

    tim.Play(magic_phrase);

   

    cout << tim.Get_code() << endl;

}