Solution de dboissin pour Centaure sur Tore

use std::{io::{Read, Write}, net::TcpStream, time::Duration};
use regex::Regex;

use crate::{FarmError, Result};

const BUFFER_SIZE: usize = 8192;
const BEGIN_IMAGE: &str = "------------------------ BEGIN MAZE ------------------------";
const END_IMAGE: &str = "------------------------- END MAZE -------------------------";

pub struct FarmClient {
    stream: TcpStream,
    buffer: [u8; BUFFER_SIZE],
}

impl FarmClient {

    pub 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)
    }

    pub fn read_lines(&mut self) -> Result<String> {
        let mut lines = String::new();
        loop {
            let size = self.stream.read(&mut self.buffer)?;
            if size > 0 {
                let text = str::from_utf8(&self.buffer[..size])?;
                lines.push_str(&text);
            }
            if size < BUFFER_SIZE {
                println!("{}", lines);
                return Ok(lines);
            }
        }
    }

    pub fn read_flag(&mut self) -> Result<String> {
        let mut lines = String::new();
        loop {
            let text = self.read_lines()?;
            lines.push_str(&text);
            if text.contains("FCSC") {
                break;
            }
        }
        Ok(lines)
    }

    pub fn read_maze(&mut self) -> Result<(String, (usize, usize))> {
        let mut lines = String::new();
        loop {
            let text = self.read_lines()?.replace("\n", "");
            lines.push_str(&text);
            if text.ends_with(">>> ") {
                break;
            }
            if text.ends_with("Bye bye.") {
                return Err(Box::new(FarmError::ReadTCPStreamError));
            }
        }

        let (before, text) = lines
            .split_once(BEGIN_IMAGE)
            .ok_or(Box::new(FarmError::ImageReadError))?;
        let (img, _) = text
            .split_once(END_IMAGE)
            .ok_or(Box::new(FarmError::ImageReadError))?;
        let dimensions = Self::parse_tore_dimensions(before)
            .ok_or(Box::new(FarmError::ReadToreDimensionsError))?;
        Ok((img.to_string(), dimensions))
    }

    fn parse_tore_dimensions(text: &str) -> Option<(usize, usize)> {
        let size_regex = Regex::new(r"Generating a (\d+)x(\d+) tore").unwrap();
        size_regex.captures(&text).map(|dimensions|
            (dimensions[1].parse().unwrap_or(0), dimensions[2].parse().unwrap_or(0)))
    }

    pub fn send_message(&mut self, text: &str) -> Result<()> {
        writeln!(self.stream, "{text}")?;
        Ok(())
    }

}

use opencv::{core, imgcodecs, imgproc, prelude::*};
use base64::prelude::*;
use crate::Result;

fn load_base64_png(base64_img: &str) -> Result<Mat> {
    let decoded_bytes = BASE64_STANDARD.decode(base64_img.trim())?;
    let mat = Mat::from_slice(&decoded_bytes)?;
    let img = imgcodecs::imdecode(&mat, imgcodecs::IMREAD_COLOR)?;
    Ok(img)
}

fn binarize(img: &Mat, blur: Option<core::Size>) -> Result<Mat> {
    let mut gray = Mat::default();
    imgproc::cvt_color(&img, &mut gray, imgproc::COLOR_BGR2GRAY, 0)?;
    let blurred_or_not = if let Some(blur_size) = blur {
        let mut blurred = Mat::default();
        imgproc::gaussian_blur(&gray, &mut blurred, blur_size, 0.0, 0.0, core::BORDER_DEFAULT)?;
        blurred
    } else {
        gray
    };
    let mut binary = Mat::default();
    imgproc::threshold(&blurred_or_not, &mut binary, 0.0, 255.0, imgproc::THRESH_BINARY | imgproc::THRESH_OTSU)?;
    Ok(binary)
}

fn crop_grid(img: &Mat) -> Result<Mat> {
    let border = 63;
    let width = img.cols() - border * 2;
    let y = img.rows() - width - border;
    let rect = core::Rect::new(border, y, width, width);
    let cropped = Mat::roi(img, rect)?;
    Ok(cropped.try_clone()?)
}

fn prepare_grid(img: &Mat) -> Result<Mat> {
    let binary_img = binarize(&img, None)?;
    let grid_img = crop_grid(&binary_img)?;

    // Erode
    let kernel = imgproc::get_structuring_element(imgproc::MORPH_RECT, core::Size::new(3, 3), core::Point::new(-1, -1))?;
    let mut eroded = Mat::default();
    imgproc::erode(&grid_img, &mut eroded, &kernel, core::Point::new(-1, -1), 1, core::BORDER_CONSTANT, imgproc::morphology_default_border_value()?)?;

    Ok(eroded)
}

pub fn load_grid(base64_img: &str) -> Result<Mat> {
    let img = load_base64_png(&base64_img)?;
    prepare_grid(&img)
}

fn bresenham_line(start: &core::Point, end: &core::Point) -> Vec<core::Point> {
    let mut points = Vec::new();
    let mut x0 = start.x;
    let mut y0 = start.y;
    let x1 = end.x;
    let y1 = end.y;

    let dx = (x1 - x0).abs();
    let dy = -(y1 - y0).abs();
    let sx = if x0 < x1 { 1 } else { -1 };
    let sy = if y0 < y1 { 1 } else { -1 };
    let mut err = dx + dy;

    while x0 != x1 || y0 != y1 {
        points.push(core::Point::new(x0, y0));
        let e2 = 2 * err;
        if e2 >= dy {
            err += dy;
            x0 += sx;
        }
        if e2 <= dx {
            err += dx;
            y0 += sy;
        }
    }
    points
}

pub fn line_has_intersection(img: &Mat, start_line: &core::Point, end_line: &core::Point) -> bool {
    let line = bresenham_line(start_line, end_line);
    for point in &line {
        if *img.at_2d::<u8>(point.y, point.x).unwrap_or(&0) == 0 {
            return true;
        }
    }
    false
}

use rand::seq::SliceRandom;

pub type Edge = (usize, usize, u8);

struct UnionFind {
    partitions: Vec<usize>,
    size: usize
}

impl UnionFind {

    fn new(size: usize) -> Self {
        let mut partitions = vec![0; size];
        for i in 0..size {
            partitions[i] = i;
        }
        Self { partitions, size }
    }

    fn union(&mut self, idx1: usize, idx2: usize) {
        self.partitions[idx2] = idx1;
        self.size -= 1;
    }

    fn find(&mut self, idx: usize) -> usize {
        let tmp_idx = self.partitions[idx];
        if  tmp_idx == idx {
            return idx;
        }
        let res_idx = self.find(tmp_idx);
        // compress path
        self.partitions[idx] = res_idx;

        res_idx
    }

}

#[derive(Clone)]
pub struct Graph<T> {
    nodes: Vec<T>,
    edges: Vec<Edge>,
}

impl <T> Graph<T> {

    pub fn new(nodes: Vec<T>, edges_opt: Option<Vec<Edge>>) -> Self {
        Self { nodes, edges: edges_opt.unwrap_or(vec![]) }
    }

    pub fn add_edges(&mut self, edges: &[Edge]) {
        self.edges.extend_from_slice(edges);
    }

    pub fn nodes(&self) -> &[T] {
        &self.nodes
    }

    pub fn node(&self, idx: usize) -> &T {
        &self.nodes[idx]
    }

    pub fn edges(&self) -> &[Edge] {
        &self.edges
    }

    pub fn karger_min_cut(&self, expected_min_cut: Option<usize>) -> Option<Vec<Edge>> {
        let mut res = None;
        let mut min_cut_size = usize::MAX;
        let nodes_count = self.nodes.len() as u32;
        let retry_number = nodes_count * nodes_count / 2;
        for _ in 0..retry_number {
            if let Some(min_cut) = self.karger_min_cut_union_find() && min_cut.len() < min_cut_size {
                min_cut_size = min_cut.len();
                res = Some(min_cut);
            }
            if let Some(expected_min_cut_size) = expected_min_cut && expected_min_cut_size == min_cut_size {
                break;
            }
        }
        res
    }

    fn karger_min_cut_union_find(&self) -> Option<Vec<Edge>> {
        let mut edges = self.edges.clone();
        edges.shuffle(&mut rand::rng());

        let mut clusters = UnionFind::new(self.nodes.len());
        while clusters.size > 2 && let Some(edge) = edges.pop() {
            let src = clusters.find(edge.0);
            let dest = clusters.find(edge.1);
            if src != dest {
                clusters.union(src, dest);
            }
        }

        if clusters.size != 2 {
            return  None;
        }
        let mut min_cut = vec![];
        for edge in self.edges() {
            if clusters.find(edge.0) != clusters.find(edge.1) {
                min_cut.push(*edge);
            }
        }
        Some(min_cut)
    }

}

use opencv::{core::Point, prelude::*};
use crate::{Result, graph::Graph, preprocessing::{self, line_has_intersection}};

#[derive(Clone)]
struct FarmPlot {
    x: usize,
    y: usize,
    center: Point,
}

impl FarmPlot {

    fn new(x: usize, y: usize, center: Point) -> Self {
        Self { x, y, center }
    }

}

pub struct Farm {
    img: Mat,
    offset_x: i32,
    offset_y: i32,
    start_x: i32,
    start_y: i32,
    rows: usize,
    colums: usize,
    graph: Graph<FarmPlot>,
}

impl Farm {

    pub fn new(base64_img: &str, rows: usize, colums: usize) -> Result<Self> {
        let img = preprocessing::load_grid(base64_img)?;
        let offset_x = img.cols() / colums as i32;
        let offset_y = img.rows() / rows as i32;
        let start_x = offset_x / 2;
        let start_y = offset_y / 2;

        let mut plots = Vec::with_capacity(rows*colums);
        for y in 0..rows {
            for x in 0..colums {
                let plot_center = Point::new(start_x + offset_x * x as i32, start_y + offset_y * y as i32);
                plots.push(FarmPlot::new(x, y, plot_center));
            }
        }

        Ok(Self { img, offset_x, offset_y, start_x, start_y, rows, colums,
            graph: Graph::new(plots, None)})
    }

    fn get_node_idx(&self, x: usize, y: usize) -> usize {
        x + self.colums * y
    }

    fn get_neighbor_node_idx(&self, x: usize, y: usize, relative_position: &(i32, i32)) -> (usize, bool) {
        let n_x = match relative_position.0 {
            -1 if x < 1 => (self.colums - 1, true),
            1 if x == self.colums - 1 => (0, true),
            _ => ((relative_position.0 + x as i32) as usize, false),
        };
        let n_y = match relative_position.1 {
            -1 if y < 1 => (self.rows - 1, true),
            1 if y == self.rows - 1 => (0, true),
            _ => ((relative_position.1 + y as i32) as usize, false),
        };
        (self.get_node_idx(n_x.0, n_y.0), n_x.1 || n_y.1)
    }

    fn generate_border_point(&self, plot: &FarmPlot, relative_position: &(i32, i32)) -> Option<Point> {
        match relative_position {
            (1, -1) => Some(Point::new(self.start_x * 2 + self.offset_x * plot.x as i32, self.offset_y * plot.y as i32)),
            (1, 0) => Some(Point::new(self.start_x * 2 + self.offset_x * plot.x as i32, self.start_y + self.offset_y * plot.y as i32)),
            (0, 1) => Some(Point::new(self.start_x + self.offset_x * plot.x as i32, self.start_y * 2 + self.offset_y * plot.y as i32)),
            (1, 1) => Some(Point::new(self.start_x * 2 + self.offset_x * plot.x as i32, self.start_y * 2 + self.offset_y * plot.y as i32)),
            _ => None
        }
    }

    pub fn init_graph(&mut self) {
        let adjacency_positions = vec![
                   (1, -1),
                    (1, 0),
            (0, 1), (1, 1)
        ];

        let mut edges = vec![];
        for plot in self.graph.nodes() {
            for position in &adjacency_positions {
                let (other_node_idx, border) = self.get_neighbor_node_idx(plot.x, plot.y, position);
                let other_plot = self.graph.node(other_node_idx);

                let destination_point = if border {
                    self.generate_border_point(plot, position).unwrap()
                } else {
                    other_plot.center
                };

                if !line_has_intersection(&self.img, &plot.center, &destination_point) {
                    let node_idx = self.get_node_idx(plot.x, plot.y);
                    edges.push((node_idx, other_node_idx, 1));
                }
            }
        }

        self.graph.add_edges(&edges);
    }

    pub fn disconnect_plots_min_cut(&self) -> Option<Vec<((usize, usize), (usize, usize))>> {
        if let Some(res) = self.graph.karger_min_cut(Some(3)) && res.len() == 3 {
            return Some(res.iter()
                .map(|idx|
                    ((self.graph.node(idx.0).x, self.graph.node(idx.0).y),
                    (self.graph.node(idx.1).x, self.graph.node(idx.1).y)))
                .collect());
        }
        None
    }

}

use std::{error::Error, time::Instant};

use crate::{client::FarmClient, farm::Farm};

pub(crate) mod client;
pub(crate) mod preprocessing;
pub(crate) mod graph;
pub(crate) mod farm;

pub type Result<T> = std::result::Result<T, Box<dyn Error + Send + Sync>>;

#[derive(Debug, strum_macros::Display)]
enum FarmError {
    ImageReadError,
    ReadTCPStreamError,
    ReadToreDimensionsError,
    DisconnectPlotsError,
}

impl Error for FarmError {}

pub fn resolve_mazes(host: &str, port: u16) -> Result<()> {
    let mut client = FarmClient::new(host, port)?;
    client.send_message("")?;
    for _ in 0..100 {
        let start = Instant::now();
        let (base64_img, (rows, columns)) = client.read_maze()?;
        let mut farm = Farm::new(&base64_img, rows, columns).unwrap();
        farm.init_graph();
        if let Some(removed_edges) = farm.disconnect_plots_min_cut() {
            client.send_message(&format!("{:?}", removed_edges))?;
            let duration = start.elapsed();
            println!("Solution {}x{} : {:?} found in {:?}", rows, columns, removed_edges, duration)
        } else {
            return Err(Box::new(FarmError::DisconnectPlotsError));
        }
    }
    client.read_flag()?;
    Ok(())
}

use centaure_parks::resolve_mazes;

fn main() {
    resolve_mazes("localhost", 4000).unwrap();
}

[package]
name = "centaure-parks"
version = "0.1.0"
edition = "2024"

[dependencies]
base64 = "0.22.1"
opencv = "0.98.1"
rand = "0.9.2"
regex = "1.12.2"
strum_macros = "0.27.2"