Dans ce challenge, comme dans la partie Tri Sélectif, nous devons aussi trier un tableau de valeur généré aléatoirement mais de manière plus éfficace.

Regardons un peu le code qui tourne côté serveur :

import os

def usage():
	print('Actions possibles:')
	print('  - "comparer X Y": compare les valeurs du tableau aux cases X et Y, et retourne 1 si la valeur en X est inférieure ou égale à celle en Y, 0 sinon.')
	print('  - "echanger X Y": échange les valeurs du tableau aux cases X et Y, et affiche le taleau modifié.')
	print('  - "longueur:       retourne la longueur du tableau.')
	print('  - "verifier:      retourne le flag si le tableau est trié.')

def printArray(A):
	print(" ".join("*" for a in A))

def verifier(A):
	return all([ A[i] <= A[i + 1] for i in range(len(A) - 1) ])

if __name__ == "__main__":

	A = list(os.urandom(32))
	print("Votre but est de trier un tableau dont vous ne voyez pas les valeurs (chacune est remplacée par *) :")
	printArray(A)
	usage()
	B = A[:]

	try:
		nbCmp = 5 * 32 + 25
		while True:
			x = input(">>> ")

			if x.startswith("comparer"):
				if nbCmp > 0:
					x, y = list(map(int, x.split(" ")[1:]))
					print(int(A[x] <= A[y]))
					nbCmp -= 1
				else:
					print("Erreur : plus de comparaisons disponibles !")

			elif x.startswith("echanger"):
				x, y = list(map(int, x.split(" ")[1:]))
				A[x], A[y] = A[y], A[x]

			elif x.startswith("longueur"):
				print(len(A))

			elif x.startswith("verifier"):
				c = verifier(A)
				if c:
					flag = open("flag.txt").read().strip()
					print(f"Le flag est : {flag}")
				else:
					print("Erreur : le tableau n'est pas trié")
					print(f"Le tableau de départ était : {B}")
					print(f"Le tableau final est :       {A}")
				print("Bye bye!")
				break

			else:
				usage()
	except:
		print("Erreur : vérifier les commandes envoyées.")

Ce code est à peu près le même que le précédent sauf qu'on remarque ici une variable nommée nbCmp.

Cette variable est égale à 5 x 32 + 25 = 185.

if nbCmp > 0:
  x, y = list(map(int, x.split(" ")[1:]))
  print(int(A[x] <= A[y]))
  nbCmp -= 1
else:
  print("Erreur : plus de comparaisons disponibles !")

Dans ce bloc, nous voyons que la variable nbCmp est décrémentée à chaque déclenchement de la fonction comparer. Ce qui veut dire que nous ne pouvons avoir que 185 coups maximum.

Faisons donc un algorithme qui permet de reprendre le même script que dans le challenge précédent.

#!/usr/bin/env python3

# python3 -m pip install pwntools
from pwn import *

# Paramètres de connexion
HOST, PORT = "challenges.france-cybersecurity-challenge.fr", 2052

def comparer(x, y):
	io.sendlineafter(b">>> ", f"comparer {x} {y}".encode())
	return int(io.recvline().strip().decode())

def echanger(x, y):
	io.sendlineafter(b">>> ", f"echanger {x} {y}".encode())

def longueur():
	io.sendlineafter(b">>> ", b"longueur")
	return int(io.recvline().strip().decode())

def verifier():
	io.sendlineafter(b">>> ", b"verifier")
	r = io.recvline().strip().decode()
	if "flag" in r:
		print(r)
	else:
		print(io.recvline().strip().decode())
		print(io.recvline().strip().decode())

def trier(N):
	#############################
	#   ... Complétez ici ...   #
	# Ajoutez votre code Python #
	#############################
	def tri_rapide(gauche, droite):
		if gauche >= droite:
			return

		# Choix du pivot au hasard
		pivot = random.randint(gauche, droite)

		# Échange le pivot avec le dernier élément du tableau
		echanger(pivot, droite)
		pivot = droite

		# Partitionne le tableau autour du pivot
		i = gauche
		for j in range(gauche, droite):
			if comparer(j, pivot) <= 0:
				echanger(i, j)
				i += 1
		echanger(i, droite)

		# Trie les sous-tableaux gauche et droit
		tri_rapide(gauche, i - 1)
		tri_rapide(i + 1, droite)

	tri_rapide(0, N - 1)
	for i in range(N // 2):
		echanger(i, N - i - 1)

# Ouvre la connexion au serveur
io = remote(HOST, PORT)

# Récupère la longueur du tableau
N = longueur()

# Appel de la fonction de tri que vous devez écrire
trier(N)

# Verification
verifier()

# Fermeture de la connexion
io.close()

Nous avons redéfini la fonction trier pour faire un tri en moins de 185 coups.

def trier(N):
  def tri_rapide(gauche, droite):
    if gauche >= droite:
      return

      # Choix du pivot au hasard
      pivot = random.randint(gauche, droite)

      # Échange le pivot avec le dernier élément du tableau
      echanger(pivot, droite)
      pivot = droite

      # Partitionne le tableau autour du pivot
      i = gauche
      for j in range(gauche, droite):
        if comparer(j, pivot) <= 0:
          echanger(i, j)
          i += 1
          echanger(i, droite)

      # Trie les sous-tableaux gauche et droit
      tri_rapide(gauche, i - 1)
      tri_rapide(i + 1, droite)

  tri_rapide(0, N - 1)
  for i in range(N // 2):
    echanger(i, N - i - 1)

Nous utilisons ici l'algorithme de tri rapide (dont le principe est décrit dans le lien précédent)

Résultat :

 FCSC{6d275607ccfba86daddaa2df6115af5f5623f1f8f2dbb62606e543fc3244e33a}