[Ludique] Énigme : Google Code Jam

Version imprimable

09/06/2011, 15h08
Golgotha

[Ludique] Énigme : Google Code Jam

Oyez Oyez !

Aujourd’hui pour vos yeux ébahis, je vous propose une petite épreuve qui va réveiller vos neurones, tiré du Google Code Jam (Round 3 2010).

Tous les langages sont acceptés (même MATLAB si ça vous tente :aie:), le principe c'est de s'amuser tout en apprenant, si vous avez des remarques, des idées n'hésitez pas à poster aussi, on est entre nous... :ccool:

Problème : Prolifération de Hot Dog

Le problème est donc le suivant :

(Ceux qui trouvent l'histoire pourrie, vous pouvez poster vos réclamations chez Google :mrgreen:)
Un certain nombre de vendeurs de hot-dogs ont commencé à vendre des hot-dogs dans les angles (intersections) le long d'une très longue rue est-ouest. Le problème c'est que plusieurs vendeurs pourraient vendre sur le même angle, ils occuperaient alors le même marché. Tout n'est pas perdu cependant ! Les vendeurs de hot-dogs ont un plan.

Si jamais il y a deux ou plusieurs vendeurs aux même angle, alors exactement deux des vendeurs peuvent effectuer un déménagement, ce qui signifie:

Un vendeur se déplace d'un coin plus à l'est le long de la rue. L'autre vendeur se déplace d'un angle plus à l'ouest le long de la rue. Rappelez-vous que la rue est très longue, il n'y a donc aucun danger de manquer d'angle. Compte tenu des positions de départ de tous les vendeurs de hot-dogs, vous devriez trouver le nombre minimum de coups dont ils ont besoin pour que les vendeurs soient tous séparés (ce qui signifie qu'ils sont tous sur différents coins).

Par exemple, supposons que la rue commence avec le nombre suivant de vendeurs de hot-dog à chaque coin, classés par ordre d'ouest en est:

Citation:

... 0 0 2 1 2 0 0 ...

Ensuite, les vendeurs peuvent être séparés en trois coups, comme indiqué ci-dessous:

Citation:

... 0 0 2 1 2 0 0 ...
.........|
.........+--- Mouvement ici

... 0 1 0 2 2 0 0 ...
............|
............+--- Mouvement ici

... 0 1 1 0 3 0 0 ...
...............|
...............+--- Mouvement ici

... 0 1 1 1 1 1 0 ...

Si vous voulez, vous pouvez donner le temps que votre programme aura mis pour trouver les réponses ;)

Voici les jeux d’essais, un simple et un plus complexe.

Chaque coin de rue est marqué par un nombre entier, positif ou négatif. Pour chaque i, i +1 coin se réfère à l'autre coin à l'est du coin i. Nous allons utiliser ce système d'étiquetage pour décrire les coins dans le fichier d'entrée.

La première ligne du fichier d'entrée contient le nombre de cas, T cas de test. Chaque cas commence par le nombre C d'angles qui ont au moins un vendeur de hot-dog dans la configuration de départ. Les C lignes suivantes contiennent chacun une paire de nombres entiers séparés par des espaces P, V, indiquant qu'il existe V vendeurs à l'angle P.

C-small-practice
C-large-practice

J'attends vos réponses :ccool:
10/06/2011, 00h39
pseudocode

<spoil>Chip Firing Game de degré 1</spoil>

;)

Edit : Remarque : ça pourrait être vu comme un spoil. Donc ne pas lire la suite pour ceux qui préfèrent ne pas échanger d'idées sur le sujet...

bon, comme il n'y a personne et histoire de ne pas laisser s'enterrer ce joli sujet... je me lance !

Approche simpliste, dans la mesure où il me faudrait une version vulgarisée de l'indice de pseudocode pour tout comprendre sans y passer une semaine... :aie:

J'ai supposé deux trucs (sans en avoir la preuve) :
1/
- Si [A] est une rue avec A vendeurs à une position donnée
- Alors R([A]) = A/2 '1' à gauche de A, A/2 '1' à droite de A et A%2 à la place de A

2/
- Si une rue contient [... A .... B ....]
- Alors la rue "réduite" R([... A .... B ....]) = R( R([...A..]) + R([...B...]) )

Est-ce correct ?

De là, côté algo... rien de très futé (sinon peut être l'utilisation d'une table de hash plutôt que d'un vecteur pour représenter la rue ?).

Côté résultats :
- ça "passe" pour le petit jeu d'essai
- ça boucle assez souvent pour le grand (je ne les ai pas tous faits) : c'est à dire qu'il y a probablement des cycles...

Voici le code (itératif) en C# s'appuyant sur les règles 1 et 2 :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
        public Dictionary<int, int> Solve( out int nIterations )
        {
            // Initialisation depuis les positions d'origine
            Dictionary<int, int> positions = new Dictionary<int, int>( _street.InitialPositions );
 
            // Les conflits sont toutes les positions correspondant à au moins 2 vendeurs
            Dictionary<int, bool> conflicts = new Dictionary<int, bool>();
            foreach ( KeyValuePair<int, int> pair in positions )
                if ( pair.Value > 1 )
                    conflicts[pair.Key] = true;
 
            nIterations = 0;
 
            // Tant qu'il y a des conflits
            while ( conflicts.Count > 0 )
            {
                Dictionary<int, bool> nextConflicts = new Dictionary<int, bool>();
 
                // Pour chaque conflit
                foreach ( int position in conflicts.Keys )
                {
                    int value = positions[position];
 
                    // On résoud le conflit de cette position
                    nextConflicts.Remove( position );
 
                    // A cette position il reste 0 si la valeur est paire, 1 sinon
                    if ( value % 2 == 0 )
                        positions.Remove( position );
                    else
                        positions[position] = 1;
 
                    // On 'développe' des 1 sur la valeur / 2 à gauche et à droite de la position 
                    for ( int i = 0 ; i < value / 2 ; i++ )
                    {
                        Update( positions, nextConflicts, position - i - 1 );
                        Update( positions, nextConflicts, position + i + 1 );
                    }
                }
 
                conflicts = nextConflicts;
 
                nIterations++;
            }
 
            return positions;
        }
 
        void Update( Dictionary<int, int> positions, Dictionary<int, bool> nextConflicts, int position )
        {
            int value;
            if ( positions.TryGetValue( position, out value ) )
            {
                value++;
                positions[position] = value;
 
                if ( value > 1 )
                    nextConflicts[position] = true;
            }
            else
            {
                positions.Add( position, 1 );
            }
        }