Coding Solution

Winamax Battle – solution CodinGame en Python3

Moyensimulationqueuescard gameMis à jour le
Réponse courte

Winamax Battle est une pure simulation du jeu de la bataille. On garde chaque paquet dans une file, on joue des tours jusqu'à ce qu'un paquet soit vide, et en cas d'égalité on lance une bataille où chaque joueur pose trois cartes face cachée et une quatrième face visible, en recommençant s'il y a encore égalité. Le gagnant ramasse d'abord les cartes jouées par le joueur 1, puis celles du joueur 2, et si un joueur manque de cartes pendant une bataille le résultat est PAT. Le coût est linéaire en nombre de tours.

L'énoncé

Deux joueurs commencent chacun avec un paquet issu d'un jeu standard de 52 cartes. À chaque tour, les deux révèlent leur carte du dessus ; la plus haute valeur remporte les deux cartes, qui vont sous le paquet du gagnant. Les valeurs vont de 2 jusqu'à l'As, les couleurs n'ont aucune importance. En cas d'égalité, une bataille démarre : chaque joueur pose trois cartes face cachée et une face visible, et ce sont ces nouvelles cartes visibles qui décident, avec éventuellement de nouvelles batailles.

Il faut afficher le gagnant (1 ou 2) et le nombre de tours joués, un tour comptant une seule fois batailles comprises. Si un joueur ne peut pas poser les cartes exigées par une bataille, on affiche PAT à la place.

La démarche, étape par étape

  1. Convertir les cartes en valeurs numériquesOn retire le dernier caractère (la couleur) et on convertit le reste : 2 à 10 en nombres, puis J, Q, K, A en 11, 12, 13, 14. Attention au « 10 », seul rang à deux caractères.
  2. Utiliser de vraies filesOn stocke les deux paquets dans une deque (ou un tampon circulaire). Prendre sur le dessus et ajouter en dessous sont alors en O(1), et le code se lit comme les règles.
  3. Jouer un tourOn retire une carte de chaque paquet vers deux piles. Tant que les dernières cartes des deux piles sont égales, on vérifie que chaque joueur a au moins 4 cartes ; sinon la partie se termine en PAT ; sinon on déplace 4 cartes de chaque paquet vers sa pile.
  4. Attribuer les cartes dans le bon ordreLe gagnant du tour ajoute pile1 (toutes les cartes du joueur 1, dans l'ordre) puis pile2 sous son propre paquet, quel que soit le gagnant. On incrémente le compteur de tours une fois par tour.
  5. S'arrêter quand un paquet est videAvant de commencer un tour, si un paquet est vide, on affiche le numéro de l'autre joueur suivi du nombre de tours.

Complexité

TempsO(R)
MémoireO(52)

R est le nombre de tours ; chaque tour déplace un nombre borné de cartes. Le code publié utilise list.pop(0) et des concaténations de listes, en O(taille du paquet), mais avec 52 cartes au plus c'est négligeable.

Code de la solution

Winamax Battle – Python3

Cette version s'appuie sur IndexError pour détecter un paquet vide, à la fois au début d'un tour (fin de partie) et pendant une bataille (PAT). Notez que la docstring de compare dit qu'elle renvoie 1 quand la carte 2 gagne ; le code renvoie en réalité -1 dans ce cas.

# Game configuration : the differents cards possible and their value
# We would only need to modify this dictionnary if the order of the 
# card changed, or if we wanted to play with a 32 card game for example
values = {'2D':2, '2H':2, '2C':2, '2S':2, 
          '3D':3, '3H':3, '3C':3, '3S':3,
          '4D':4, '4H':4, '4C':4, '4S':4, 
          '5D':5, '5H':5, '5C':5, '5S':5,
          '6D':6, '6H':6, '6C':6, '6S':6,
          '7D':7, '7H':7, '7C':7, '7S':7,
          '8D':8, '8H':8, '8C':8, '8S':8, 
          '9D':9, '9H':9, '9C':9, '9S':9,
          '10D':10, '10H':10, '10C':10, '10S':10, 
          'JD':11, 'JH':11, 'JC':11, 'JS':11,
          'QD':12, 'QH':12, 'QC':12, 'QS':12, 
          'KD':13, 'KH':13, 'KC':13, 'KS':13,
          'AD':14, 'AH':14, 'AC':14, 'AS':14}
    
def compare(c1, c2):
    ''' returns : 
    - 0 if card1 and card 2 have equal values
    - 1 if card1 wins over card2
    - 1 if card2 wins over card1'''
    global values

    if values[c1] < values[c2]:
        return -1
    elif values[c1] > values[c2]:
        return 1
    else:
        return 0


# Reads input to initialize decks
deck1, deck2 = [], []
for i in range(int(input())):
    deck1.append(input())
for i in range(int(input())):
    deck2.append(input())

nbRounds = 0

while True:
    # Each loop is one game round
    # pile1 and pile2 are the cards played this turn by player 1 and 2

    try:    
        pile1, pile2 = [deck1.pop(0)], [deck2.pop(0)]
    except IndexError:
        # this error means one of the two decks is empty
        winner = '1' if len(deck1) > 0 else '2'
        print(winner, nbRounds)
        break

    nbRounds+=1
    
    # In case of war(s)
    try:
        # While there is a war, each player plays 3 other cards
        while compare(pile1[-1], pile2[-1]) == 0:
            for i in range(4):
                pile1.append(deck1.pop(0))
                pile2.append(deck2.pop(0))
    except IndexError:
        # an index error means one of the two decks got empty
        # during a war, and both players are equally first
        print('PAT')
        break

    # Moves the 2 piles to the round winner's deck bottom
    if compare(pile1[-1], pile2[-1]) == -1:
        deck2 = deck2 + pile1 + pile2
    else:
        deck1 = deck1 + pile1 + pile2
            

Erreurs fréquentes

Pour aller plus loin

La plupart des bugs de Winamax Battle viennent de l'ordre des cartes, donc une astuce de débogage efficace consiste à afficher les deux paquets après chaque tour sur le premier test et à comparer avec une simulation à la main de trois ou quatre tours ; l'exemple de l'énoncé est assez court pour être vérifié. Autre détail bon à connaître : la partie peut en théorie boucler indéfiniment avec certains ordres de paquets, et les solutions robustes s'en protègent avec une limite de tours ou en stockant les états (paquet1, paquet2) déjà vus dans un ensemble. Les tests de CodinGame se terminent toujours, mais la détection de cycle est une bonne habitude pour les puzzles de simulation et ne coûte presque rien avec 52 cartes.

Questions fréquentes

Combien de cartes sont jouées lors d'une bataille dans Winamax Battle ?

Chaque joueur ajoute trois cartes face cachée et une face visible, donc quatre par joueur. Les cartes visibles sont comparées ; une nouvelle égalité relance une bataille avec la même règle.

Une bataille compte-t-elle comme un tour supplémentaire ?

Non. Toute la séquence, de la première confrontation à la résolution de la dernière bataille, compte pour un seul tour.

Quand la réponse est-elle PAT ?

Quand l'un des joueurs n'a pas assez de cartes pour terminer une bataille. La partie s'arrête immédiatement et les deux joueurs sont considérés à égalité.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome