Codingame - La programmation hantée. Concours de fantômes dans la console fin Fevrier

[rOut]

Gold league me voilà !

Bon, je touche plus à rien jusqu'à la promo, il s'agirait quand même pas de retomber dans le classement.

Forcément avec un modèle de simulation complètement aux fraises, ça marchait pas très très bien

[rOut]

Ha ben lol, ils ont ouvert la Legend League, mais en fait c'est le boss de la Silver qui est devenu le boss de la Gold, avec un nouveau Boss intermédiaire entre Bronze et Silver... Du coup je me retrouve dans la Legend sans avoir rien touché

[Naity]

Quel homme

[Naity]

Mon programme marche pas

[rOut]

Qu'est ce qui ne marche pas dans ton programme ?

[Naity]

Qu'est ce qui ne marche pas dans ton programme ?

Ca fonctionne pas comme je veux

Il est senser tester tous les coups sur 4 tours et recupere la meilleure combinaison. Le hic c'est que le programme fait un peu ce qu'il veut et au final, je me chope a peu pres le meme score sans prevision, avec un, deux, ou 3 coups d'avance. En y regardant de plus pres, il fait parfois le coup optimal, et parfois qqchose d'autre. Et pour couronner le tout, a partir de 3 tours d'avance je me chope un ArrayOutOfRangeException sorti de nulle part que j'arrive pas a traquer.

Je me suis resigne. Je vais faire un trucs simple dans un langage obscure (genre F#) pour chopper lachievement Top10/langage. Je vais faire autrechose de ma fin de journee (je suis dessus depuis 10h ce matin) vu que je ne pourrais pas vraiment y retoucher demain ou c weekend.

- - - Mise à jour - - -

Par ailleurs, si quelqu'un veut bien me filer le pseudocode pour passer silver avec just un if, je dis pas non

[Naity]

Derniere ligne droite. Ca donne quoi chez vous?

[Rao]

Rien du tout, pas eu le temps de m'y mettre cette fois.
Par contre j'ai codé un bot random au début, et quand il ont ajouté la dernière ligue j'ai reçu un mail me disant que mon bot passait en Silver .
J'ai rien compris mais c'est rigolo

[rOut]

C'est la misère un peu, même si relativement parlant je m'en sors bien. Je suis coincé vers la 50e place en légende, et ça descend petit à petit quoi que je fasse... Vendredi j'étais arrivé vers la 30e place, et samedi matin me voilà 60e. Samedi je suis content j'ai trouvé une meilleure heuristique et j'ai regagné 30 places, mais ce matin rebelotte, 50e. Le niveau monte régulièrement mais moi je ne sais pas quoi faire pour endiguer ça, pas moyen de trouver une heuristique qui déchire, et les bidouillages de constantes ça n'a pas beaucoup d'effet.

[Naity]

Arf rOut. C'est deja super impressionnant

Moi j'ai laisse tomber faute de temps. J'ai pose le code du bot en F# histoire de faire un top 10 dans un langage obscure. Pous ce matin j'ai decouvert que je suis passe silver. J'ai tweake un peu mon programme et je me retrouve top 3 Pourvu que ca tienne

[rOut]

En fait je crois que je préférais le challenge CSB, c'était certes plus difficile avec un peu de maths, mais plus fun. Là j'ai quand même l'impression que c'est du vilain brute force avec une seule stratégie optimale.

[Naity]

Là j'ai quand même l'impression que c'est du vilain brute force

Noooooooooooon, ca ne se reflete pas-du-tout dans le classement:


Pour les concours moins axes sur l'algorithmie, un temps type SF 2442 (3 jours) serait ptet plus adapte.

[Rao]

J'ai pas suivi le chat irc cette fois mais je parierais qu'on va retrouver les mêmes stratégies de la part des mêmes gusses en tête.
Et sinon GG rOut heureusement que tu es là pour compenser

[Tamno]

Moi je suis un peu triste

[rOut]

Moi je suis un peu triste
http://tof.canardpc.com/view/cd42a79...75559a5dcc.jpg

Arf, allez courage. Un tout petit peu plus de simus et c'est gagné.

Protip: au premier tour t'as quasiment 1s de timeout, ça laisse le temps de faire bien plus de simulations pour prendre un bon départ.

[rOut]

Bon ben petit panic submit au dernier moment, avec une super feature qui déchire. Vu la tournure que ça prend je regrette un peu. Mais bon on va dire que mon jugement était biaisé par tous les gens qui submittaient en meme temps et je savais pas trop à quoi m'en tenir !

[Naity]

Bon ben petit panic submit au dernier moment, avec une super feature qui déchire. Vu la tournure que ça prend je regrette un peu. Mais bon on va dire que mon jugement était biaisé par tous les gens qui submittaient en meme temps et je savais pas trop à quoi m'en tenir !

C'etait quoi la feature? Je fini mon episode du Doctor et je met a jour le premier post avec le clasement des canards. Si vous pouviez poster la ligue dans laquelle vous avez fini, ce serait chouette.

Pour la posterite, mon usine a gaz C# qui m'a coute mon temps libre de dev et qui scorait moins que le "print(ColorA

[rOut]

C'était de privilégier les colonnes au milieu de la grille plutôt que celles au bord. Je sais pas trop ce qui m'a pris

Enfin bon, je vais surement finir dans les 60e de la ligue legende.

[Naity]

Enfin bon, je vais surement finir dans les 60e de la ligue legende.

Ca reste un super resultat

En attendant que ca compute le resultat final, je poste pour la posterite mon usine a gaz en C# qui m'a coute le temps libre reserve pour l'event et qui scorait moins que que le bete "print (ColorA);"

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Player
{
    static void Main(string[] args)
    {
        //initialisation
        Game myGame = new Game();
        
        // game loop
        while (true)
        {
            for (int i = 0; i < 8; i++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                int colorA = int.Parse(inputs[0]); // color of the first block
                int colorB = int.Parse(inputs[1]); // color of the attached block
                myGame.AddBlock(colorA, colorB, i);
            }
            for (int i = 0; i < 12; i++)
            {
                string row = Console.ReadLine();
                myGame.UpdateRow(row, i);
            }
            for (int i = 0; i < 12; i++)
            {
                string row = Console.ReadLine(); // One line of the map ('.' = empty, '0' = skull block, '1' to '5' = colored block)
            }
            Console.WriteLine(myGame.GetBestColumn().ToString());
            
            // Write an action using Console.WriteLine()
            // To debug: Console.Error.WriteLine("Debug messages...");
            // "x": the column in which to drop your blocks
        }
    }
}

public class Game
{    
    //private datas
    private const int forecast = 8; //nomber of blocks known in advance
    private const int columns = 6;
    private const int rows = 12+2;//to avoid out of range in case of a block on top of the 12th one
    private const int minBlocks = 6; //minimum of block destroyed to consider a move advantageous
    private Tile[,] grid;
    private Tile[,] tempGrid;
    private Tile[,] secondTempGrid;
    private Tile[,] thirdTempGrid;
    private Block[] nextBlocks;
    private Result[] results = new Result[columns];
    
    //methods
    public Game()
    {
        grid = new Tile[columns, rows];
        InitializeGrid();
        tempGrid = new Tile[columns, rows];
        secondTempGrid = new Tile[columns, rows];
        thirdTempGrid = new Tile[columns, rows];
        nextBlocks= new Block[forecast]; 
    }
    
    private void InitializeGrid()
    {
        for (int r = 0; r < rows; r++)
        {
            for (int c = 0; c < columns; c++)
            {
                grid[c,r] = new Tile (r, c, '.');
            }
        }
    }
    
    public void UpdateRow(string row, int rowIndex)
    {
        int columnIndex = 0;
        foreach (char element in row)
        {
            grid[columnIndex,rowIndex+2].Type = element;
            columnIndex++;
        }
   } 
   
    public void AddBlock(int ca, int cb, int id)
    {
       nextBlocks[id] = new Block(ca, cb, id);
   }
   
    public int GetBestColumn()
    {
       for (int i = 0; i < columns; i++)
       {
           results[i] = CalculateColumnResult(i);
       }
       Array.Sort(results);
       Console.Error.WriteLine(results[columns-1]);
       return results[columns-1].Column; //return biggest result
   }
   
    private Result CalculateColumnResult(int col)
    {
       int height = 0;
       Result colResult = new Result(col);
       CloneGrid(grid, tempGrid);
       List<Tile> toExplore = new List<Tile>();
       Result[] secondResult = new Result[columns];
       Result[] thirdResult = new Result[columns];
       //calculate the height
       while(tempGrid[col, rows-height-1].Type != '.')
       {
           height++;
       }
       
       //add the blocks to the temp grid
       tempGrid[col, rows-height-1].Type = nextBlocks[0].ColorA;
       toExplore.Add(tempGrid[col, rows-height-1]);
       tempGrid[col, rows-height-2].Type = nextBlocks[0].ColorB;
       toExplore.Add(tempGrid[col, rows-height-2]);
       //Console.Error.WriteLine("grid with balls:");
       //Console.Error.WriteLine(DisplayGrid(tempGrid));
       //first search
       colResult.AddResult(GetResult(toExplore, tempGrid, height));
       toExplore.Clear();
       toExplore.TrimExcess();
       //second search
       
       for (int c = 0; c < columns; c++)
       {
           height = 0;
           CloneGrid(tempGrid, secondTempGrid);
            while(secondTempGrid[c, rows-height-1].Type != '.')
            {
                height++;
            }
            if (height<11)
            {
                secondTempGrid[c, rows-height-1].Type = nextBlocks[1].ColorA;
                toExplore.Add(secondTempGrid[c, rows-height-1]);
                secondTempGrid[c, rows-height-2].Type = nextBlocks[1].ColorB;
                toExplore.Add(secondTempGrid[c, rows-height-2]);
                secondResult[c] = GetResult(toExplore, secondTempGrid, 0);
                toExplore.Clear();
                toExplore.TrimExcess();
                
                //third search
                for (int c2 = 0; c2 < columns; c2++)
                {
                    height = 0;
                    CloneGrid(secondTempGrid, thirdTempGrid);
                    while(thirdTempGrid[c2, rows-height-1].Type != '.')
                    {
                        height++;
                    }
                    if(height<11)
                    {
                        thirdTempGrid[c2, rows-height-1].Type = nextBlocks[1].ColorA;
                        toExplore.Add(thirdTempGrid[c2, rows-height-1]);
                        //Console.Error.WriteLine("c2 = {0}, height = {1}, r-h-2 = {2}", c2, height, rows-height-2);
                        try
                        {
                            thirdTempGrid[c2, rows-height-2].Type = nextBlocks[1].ColorB;
                        }
                        catch (IndexOutOfRangeException e)
                        {
                            Console.Error.WriteLine("c2 = {0}, height = {1}, r-h-2 = {2}", c2, height, rows-height-2);
                            throw;
                        }
                        toExplore.Add(thirdTempGrid[c2, rows-height-2]);
                        thirdResult[c2] = GetResult(toExplore, thirdTempGrid, 0);
                        toExplore.Clear();
                        toExplore.TrimExcess();
                    }
               }
               Array.Sort(thirdResult);
               secondResult[c].AddResult(thirdResult[columns-1]);
            }
       }
       Array.Sort(secondResult);
       //Console.Error.WriteLine(colResult);
       //Console.Error.WriteLine(secondResult[columns-1]);
       colResult.AddResult(secondResult[columns-1]);
       //Console.Error.WriteLine(colResult);
       
       return colResult;
    }
    
    private Result GetResult(List<Tile> toExplore, Tile[,] gr, int height)
    {
        int skulls = 0;
        int blocks = 0;
        int groups = 0;
        int voisin = 0;
        int colors = 0;
        List<Tile> toRemove = new List<Tile>();
        List<Tile> skullsList = new List<Tile>();
        List<Tile> explored = new List<Tile>();
        while (toExplore.Count > 0)
        {
           //Console.Error.WriteLine("beginning: {0}", toExplore.Count);
           foreach (Tile t in toExplore)
           {
               if(t.Type!= '.' && !explored.Contains(t))
               {
                   explored.AddRange(ExploreFromTile(t, gr, skullsList));
                   voisin = explored.Count;
                   //Console.Error.WriteLine("Tile {0} has {1} neighbours surrounded with {2} skulls.", t, explored.Count, skullsList.Count);
                   if (voisin >= 4)
                   {
                       toRemove.AddRange(explored);
                       blocks += voisin;
                       foreach (Tile skull in skullsList)
                       {
                           if (!toRemove.Contains(skull))
                           {
                               toRemove.Add(skull);
                               skulls++;                               
                           }
                       }
                       groups++;
                   }
                   colors += voisin;
               }
           }
           if(toRemove.Count>0)
           {               
                UpdateGrid(gr, toRemove);
                //Console.Error.WriteLine("Actualised grid is:");
                //Console.Error.WriteLine(DisplayGrid(gr));
           }
           toExplore.Clear();
           toExplore.TrimExcess();
           toExplore.AddRange(toRemove);
           toRemove.Clear();
           toRemove.TrimExcess();
           explored.Clear();
           explored.TrimExcess();
           //Console.Error.WriteLine("end: {0}", toExplore.Count);
       }
       return new Result(-1, skulls, blocks, height, groups, colors);
    }
    
    private List<Tile> ExploreFromTile(Tile t, Tile[,] gr, List<Tile> skullsList)
    {
        List<Tile> neighbors = new List<Tile>();
        List<Tile> toExplore = new List<Tile>();
        List<Tile> explored = new List<Tile>();
        toExplore.Add(t);
        while (toExplore.Count > 0)
        {
            List<Tile> temp = new List<Tile>();
            foreach (Tile tile in toExplore)
            {
                if (tile.Type != '.' & tile.Type != '0')
                {
                    neighbors.Add(tile);
                    if (tile.Row-1 >= 0)
                    {
                        Tile tp = gr[tile.Column, tile.Row-1];
                        if (tp.Type == tile.Type && !explored.Contains(tp) && !temp.Contains(tp))
                        {
                            temp.Add(tp);
                        }
                        else if (tp.Type == '0' && !skullsList.Contains(tp))
                        {
                            skullsList.Add(tp);
                        }
                    }
                    if (tile.Row+1 < rows)
                    {
                        Tile tp = gr[tile.Column, tile.Row+1];
                        if (tp.Type == tile.Type && !explored.Contains(tp) && !temp.Contains(tp))
                        {
                            temp.Add(tp);
                        }
                        else if (tp.Type == '0' && !skullsList.Contains(tp))
                        {
                            skullsList.Add(tp);
                        }
                    }
                    if (tile.Column-1 >= 0)
                    {
                        Tile tp = gr[tile.Column-1, tile.Row];
                        if (tp.Type == tile.Type && !explored.Contains(tp) && !temp.Contains(tp))
                        {
                            temp.Add(tp);
                        }
                        else if (tp.Type == '0' && !skullsList.Contains(tp))
                        {
                            skullsList.Add(tp);
                        }
                    }
                    if (tile.Column+1 < columns)
                    {
                        Tile tp = gr[tile.Column+1, tile.Row];
                        if (tp.Type == tile.Type && !explored.Contains(tp) && !temp.Contains(tp))
                        {
                            temp.Add(tp);
                        }
                        else if (tp.Type == '0' && !skullsList.Contains(tp))
                        {
                            skullsList.Add(tp);
                        }
                    }
                }
                explored.Add(tile);
            }
            toExplore = temp;
        }
        return neighbors;
    }
    
    private void CloneGrid(Tile[,] from, Tile[,] to)
    {
       for (int r = 0; r < rows; r++)
       {
           for (int c = 0; c < columns; c++)
           {
               to[c,r] = (Tile) from[c,r].Clone();
           }
       }
   }
    
    private void UpdateGrid(Tile[,] gr, List<Tile>tR)
    {
        tR.Sort();
        foreach(Tile t in tR)
        {
            for(int i = t.Row; i>0; i--)
            {
                gr[t.Column, i].Type = gr[t.Column, i-1].Type;
            }
            gr[t.Column, 0].Type='.';
        }
    }
    
    private string DisplayGrid(Tile[,] gr)
    {
       string result = "";
       for (int r = 0; r < rows; r++)
       {
           for (int c = 0; c < columns; c++)
           {
               result += gr[c,r].Type.ToString();
           }
           result += "\n";
       }
       return result;
   }
   
    public override string ToString()
    {
        return DisplayGrid(grid);
    }
}

public class Tile : ICloneable, IComparable<Tile>
{
    //private datas
    private int row;
    private int column;
    private char type;
    
    //public accessors
    public int Row { get{ return row;}}
    public int Column { get{ return column;}}
    public char Type { get{ return type;} set{type = value;}}
    
    //methods
    public Tile(int r, int c, char t)
    {
        row = r;
        column = c;
        type = t;
    }
    
    public object Clone()
    {
	    return new Tile(this.row, this.column, this.type);
    }
    
    public int CompareTo(Tile that) //compare tiles, the lowest being the "biggest" for grid update purpose
    {
        if (this.Row > that.Row)
        {
            return 1;
        }
        else if (this.Row < that.Row)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
    
    public override string ToString()
    {
        return "r" + row.ToString() + "c" + column.ToString() + "t" + type.ToString();
    }

}

public class Result : IComparable<Result>
{
    //private datas
    private const int minBlocks = 0; //6; //minimum of block destroyed to consider a move advantageous
    private const int minGroups = 0; //2; //minimum of groups destroyed to consider a move advantageous
    private const int maxColor = 0; //3; //minimum of block destroyed to consider a move advantageous
    private int column = -1; //column at which the block was placed
    private int skulls = -1; //number of skulls destroyed
    private int blocks = -1; //number of blocks destroyed
    private int height = -1; //height at which the block will be placed
    private int groups = -1; //number of groups of blocks destroyed
    private int voisin = -1; //number of adjacent blocks
    
    //public accesors
    public int Column { get{ return column;}}
    public int Skulls { get{ return skulls;}}
    public int Blocks { get{ return blocks;}}
    public int Height { get{ return height;}}
    public int Groups { get{ return groups;}}
    public int Voisin { get{ return voisin;}}
    
    //methods
    public Result(int col, int sk, int blck, int high, int grp, int vois)
    {
        column = col;
        skulls = sk;
        blocks = blck;
        height = high;
        groups = grp;
        voisin = vois;
    }
    
    public Result(int col)
    {
        column = col;
        skulls = 0;
        blocks = 0;
        height = 0;
        groups = 0;
        voisin = 0;
    }
    
    public void AddResult(Result res)
    {
        skulls += res.Skulls;
        blocks += res.Blocks;
        height += res.Height;
        groups += res.Groups;
        voisin += res.Voisin;
    }
    
    public int CompareTo(Result that)
    {
        
        if (this.Groups > that.Groups)
        {
            return 1;
        }
        else if (this.Groups < that.Groups)
        {
            return -1;
        }
        
        //first comparaison priority: the ammount of blocks removed 
        if (this.Blocks > that.Blocks)
        {
            return 1;
        }
        else if (this.Blocks < that.Blocks)
        {
            return -1;
        }
        
        //second comparaison priority: the ammount of skulls among blocks removed
        if (this.Skulls > that.Skulls) 
        {
            return 1;
        }
        else if (this.Skulls < that.Skulls)
        {
            return -1;
        }
        
        if (this.Voisin > that.Voisin)
        {
            return 1;
        }
        else if (this.Voisin < that.Voisin)
        {
            return -1;
        }
        
        //third comparaison priority: the height at which the block is placed (the lower the better)
        if (this.Height < that.Height)
        {
            return 1;
        }
        else if (this.Height > that.Height)
        {
            return -1;
        }
        
        //if all equals, pick the leftmost solution
        if(this.Column < that.Column)
        {
            return 1;
        }
        else if (this.Column > that.Column)
        {
            return -1;
        }
        else 
        {
            return 0; //then the two Results are the same
        }
    }
    
    public override string ToString()
    {
        return "Column: " + column.ToString() + " Groups: " + groups.ToString() + " Blocks: " + blocks.ToString() + " Skulls: " + skulls.ToString() + " Voisin: " + voisin.ToString() + " Height: " + height.ToString();
    }
}

public class Block
{
    //private datas
    private char colorA = 'a';
    private char colorB = 'a';
    private int index = -1;
    
    //public accessors
    public char ColorA { get{ return colorA;}}
    public char ColorB { get{ return colorB;}}
    public int Index { get{ return index;}}
    
    //methods
    public Block(int ca, int cb, int id)
    {
        colorA=Convert.ToChar(ca+48);
        colorB=Convert.ToChar(cb+48);
        index=id;
    }
    
    public override string ToString()
    {
        return colorA.ToString() + colorB.ToString() + index.ToString();
    }
}

- - - Mise à jour - - -

By The Way, c'est quel membre du forum SLep sur CiG?

[Rao]

C'est moi!

[Naity]

C'est moi!

En plus t'es sur la 1ere page. Toute mes confuses

[rOut]

Bon ben voilà le classement final est terminé. Je m'en sors pas si mal finalement

https://www.codingame.com/leaderboar...c059714fa905f8

Par contre je suis un peu blasé après avoir lu sur le chat que certains arrivaient à faire entre 1M et 400k simulations par tour, j'ai clairement pas optimisé assez mon code.

[Naity]

Le classement final semble s'etre stabilise sur le site. Je vais faire mon Diwidyant mais vous avez tous ete merveilleux

Rout et Tamno avec leur niveau (presque) legende prouvent qu'ils en ont dans l'clavier.
Ceci, nous autre, pauvres mortels n'avont pas a rougir. Perso, ce fut fun, meme si je peste encore contre mon super programme qui devait tout deboiter mais ne cassa pas 3 pattes a un canard (boiteux )

Je vais metter a jour l'OP pour que nos exploits restent graves dans la roche.

• Smash The Code (30.04.2016 - 08.05.2016). Classement:

1# rOut (Legend League 27.41 points, programmé en C++, 56/2493 au classement général)
2# Tamno (Gold League 26.63 points, programmé en C#, 311/2493 au classement général)
3# Naity (Silver League 22.90 points, programmé en F#, 1329/2493 au classement général)
4# Monsieur Odd (SilverLeague 32.76 points, programmé en Javascript, 1364/2493 au classement général)
5# Rao (SLep) (Silver League 18.94 points, programmé en Python3, 1677/2493 au classement général)
6# Foudge (Bronze League 22.79 points, programmé en C#, 2105/2493 au classement général)
7# Karedas (Bronze League 17.89 points, programmé en PHP, 2275/2493 au classement général)

[rOut]

pb4608 arrivé premier montre sa fonction d'eval pour ceux que ça intéresse: http://pastebin.com/70N0RbBc

Attention ça pique les yeux.

- - - Mise à jour - - -

Pour info, et pour vous donner de l'espoir à tous, le mec n'est même pas programmeur dans la vie, il a découvert le C++ sur CodinGame et a appris à coder en posant des questions sur le chat pendant les challenges... ca calme.

[Naity]

Prochain concours:

• 25.06.2016 - 03.07.2016: Codebusters

- - - Mise à jour - - -

Attention ça pique les yeux.

Vite, du collyre

- - - Mise à jour - - -

Pour info, et pour vous donner de l'espoir à tous, le mec n'est même pas programmeur dans la vie, il a découvert le C++ sur CodinGame et a appris à coder en posant des questions sur le chat pendant les challenges... ca calme.

Comme moi, le talent en plus
(je suis sur qu'il me bat pas sous paint )

- - - Mise à jour - - -

Par contre je suis un peu blasé après avoir lu sur le chat que certains arrivaient à faire entre 1M et 400k simulations par tour, j'ai clairement pas optimisé assez mon code.

Tu pourra te faire du bien en te faisant du mal une fois qu'ils l'auront rendu dispo hors concours

[Naity]

Bon ben y'a eu un bug dans les achievements. ^^

[rOut]

Jayjay, même si tu risques de le perdre

[Naity]

Jayjay, même si tu risques de le perdre

C'est fait

Top 3 quand meme (place no 2 au final)

[rOut]

HOLALA CSB IS BACK

https://www.codingame.com/games/multi

Avec un mini tuto pour apprendre à faire une AI et un système de league.

[Naity]

Chouette, par contre je peux pas rétuliser mon code un à un