Rappel de l’épreuve
Le but de cette épreuve est d’intéragir en TCP avec un service pour trier un tableau dont on ne connait pas les valeurs. De plus, le nombre de comparaisons entre deux valeurs du tableau est limité.
Résolution
Le code pour résoudre cette épreuve a été écrit en Rust.
Client pour intéragir avec le service
Vu que le code a été écrit en Rust et pas en Python le fichier client.py fourni dans l’énoncé n’a pas été utilisé. À la place un client pour effectuer les différentes opérations a été ré-écrit :
use std::{error::Error, io::{Read, Write}, net::TcpStream, time::Duration};
type Result<T> = std::result::Result<T, Box<dyn Error + Send + Sync>>;
const BUFFER_SIZE: usize = 8192;
struct SortClient {
stream: TcpStream,
buffer: [u8; BUFFER_SIZE],
}
impl SortClient {
fn new(host: &str, port: u16) -> Result<Self> {
let stream = TcpStream::connect(format!("{host}:{port}"))?;
stream.set_read_timeout(Some(Duration::from_secs(5)))?;
let mut client = Self { stream, buffer: [0u8; BUFFER_SIZE] };
println!("{}", client.read_lines()?);
Ok(client)
}
fn read_lines(&mut self) -> Result<String> {
let mut lines = String::new();
loop {
if let Ok(size) = self.stream.read(&mut self.buffer) {
if size > 0 {
let text = str::from_utf8(&self.buffer[..size])?;
lines.push_str(&text.replace(">>> ", ""));
}
if size < BUFFER_SIZE && !lines.trim().is_empty() {
return Ok(lines);
}
}
}
}
fn read_number(&mut self) -> Result<usize> {
let lines = self.read_lines()?.replace("\n", "");
Ok(lines.parse::<usize>().map_err(| e | { println!("{lines}"); e })?)
}
fn size(&mut self) -> Result<usize> {
writeln!(self.stream, "longueur")?;
self.read_number()
}
fn swap(&mut self, x: usize, y: usize) -> Result<()> {
writeln!(self.stream, "echanger {} {}", x, y)?;
Ok(())
}
fn compare(&mut self, x: usize, y: usize) -> Result<bool> {
writeln!(self.stream, "comparer {} {}", x, y)?;
Ok(self.read_number()? == 1)
}
fn verify(&mut self) -> Result<String> {
writeln!(self.stream, "verifier")?;
self.read_lines()
}
}
En complément, la fonction main ci-dessous permet d’instancier le client et de lancer les fonctions de tri :
fn main() -> Result<()>{
let mut sort_client = SortClient::new("localhost", 4000)?;
let array_length = sort_client.size()?;
// bubble_sort(&mut sort_client, 0, array_length - 1)?;
quick_sort(&mut sort_client, 0, array_length - 1)?;
println!("{}", sort_client.verify()?);
Ok(())
}
Première tentative de résolution
En première intention, j’ai essayé de lancer le programme avec le tri à bulles que j’avais écrit pour l’épreuve Tri Sélectif :
fn bubble_sort(sort_client: &mut SortClient, first: usize, last: usize) -> Result<()> {
let mut compare_change = true;
while compare_change {
compare_change = false;
for i in first..last {
if !sort_client.compare(i, i+1)? {
sort_client.swap(i, i+1)?;
compare_change = true;
}
}
}
Ok(())
}
Mais, comme je m’y attendais, ça n’a pas été suffisant. Et, j’ai eu l’erreur Erreur : plus de comparaisons disponibles !.
Deuxième tentative de résolution
Vu que le tri à bulles demandait trop de comparaisons, j’ai opté pour un tri rapide en utilisant un pivot aléatoire :
fn quick_sort(sort_client: &mut SortClient, first: usize, last: usize) -> Result<()> {
let mut pivot = get_pivot(first, last);
pivot = partition(sort_client, first, last, pivot)?;
if pivot > 0 && pivot - 1 > first {
quick_sort(sort_client, first, pivot - 1)?;
}
if pivot + 1 < last {
quick_sort(sort_client, pivot + 1, last)?;
}
Ok(())
}
fn get_pivot(first: usize, last: usize) -> usize {
rand::random_range(first..last)
}
fn partition(sort_client: &mut SortClient, first: usize, last: usize, pivot: usize) -> Result<usize> {
sort_client.swap(pivot, last)?;
let mut j = first;
for i in first..last {
if sort_client.compare(i, last)? {
sort_client.swap(i, j)?;
j += 1;
}
}
sort_client.swap(j, last)?;
Ok(j)
}
Et là, le résultat est concluant :
Le flag est : FCSC{6d275607ccfba86daddaa2df6115af5f5623f1f8f2dbb62606e543fc3244e33a}
Bye bye!