commit 183c9a8099e32fea5d3d92c4d3e09f4df54795e5
parent c5100a462403259664507e7a912c884585fbb68a
Author: n0tr1v <n0tr1v@protonmail.com>
Date: Thu, 30 Mar 2023 18:05:04 -0700
new algorithm to find path
Diffstat:
3 files changed, 26 insertions(+), 122 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
@@ -108,6 +108,7 @@ name = "bhcli"
version = "0.1.0"
dependencies = [
"base64",
+ "bresenham",
"chrono",
"clap 4.1.14",
"clipboard",
@@ -190,6 +191,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "0d8c1fef690941d3e7788d328517591fecc684c084084702d6ff1641e993699a"
[[package]]
+name = "bresenham"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bfc1116225f66d2ea341a26503f83a6b1205070a6f7199ce1f1550ead91f6fd7"
+
+[[package]]
name = "bumpalo"
version = "3.12.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
@@ -7,6 +7,7 @@ edition = "2018"
[dependencies]
base64 = "0.21.0"
+bresenham = "0.1.1"
chrono = "0.4.19"
clap = { version = "4.1.14", features = ["derive", "env"] }
clipboard = "0.5.0"
diff --git a/src/lechatphp/mod.rs b/src/lechatphp/mod.rs
@@ -2,6 +2,7 @@ use std::collections::{HashMap, HashSet};
use std::fmt::{Display, Formatter};
use std::hash::Hash;
use base64::{engine::general_purpose, Engine as _};
+use bresenham::Bresenham;
use image::{ColorType, DynamicImage, GenericImageView, Rgba};
use lazy_static::lazy_static;
@@ -100,8 +101,8 @@ pub fn solve_b64(b64_str: &str) -> Option<String> {
if img.width() > 60 {
return match solve_difficulty3(&img) {
Ok(answer) => Some(answer),
- Err(_e) => {
- // println!("{:?}", e);
+ Err(e) => {
+ println!("{:?}", e);
None
},
};
@@ -166,10 +167,6 @@ impl Letter {
let offset = self.offset();
Point::new(offset.x + LETTER_WIDTH/2, offset.y + LETTER_HEIGHT/2 - 1)
}
-
- fn angle(&self, other: &Self) -> f64 {
- get_angle(&self.center(), &other.center())
- }
}
#[derive(Debug)]
@@ -203,32 +200,27 @@ fn solve_difficulty3(img: &DynamicImage) -> Result<String, CaptchaErr> {
.ok_or(CaptchaErr("could not find starting letter".to_owned()))?;
let mut answer = String::new();
- let mut visited = HashSet::<Letter>::new();
+ let mut remaining: HashSet<Letter> = letters_map.values().cloned().collect();
let mut letter = starting;
+ remaining.remove(&letter);
answer.push(letter.character);
- visited.insert(letter.clone());
- for i in 0..NB_CHARS-1 {
- let top_left = Point::new(letter.offset.x-5, letter.offset.y-3);
- let mut rect = Rect{p1: top_left, width: LETTER_WIDTH+5+6, height: LETTER_HEIGHT+3+2};
- let mut retry = 0;
- 'retry_loop: loop {
- retry += 1;
- let square = img.crop_imm(rect.p1.x, rect.p1.y, rect.width, rect.height);
- let red_px_pts = get_contour_red_pixels(&rect.p1, &square);
- let nb_lines = if i == 0 { 1 } else { 2 };
- if red_px_pts.len() != nb_lines {
- if retry < 10 {
- rect.enlarge();
- continue 'retry_loop;
+ for _ in 0..NB_CHARS-1 {
+ let mut hm = HashMap::<Letter, u32>::new();
+ for l in remaining.iter() {
+ let mut red = 0;
+ let p1 = letter.center();
+ let p2 = l.center();
+ for (x, y) in Bresenham::new((p1.x as isize, p1.y as isize), (p2.x as isize, p2.y as isize)) {
+ if img.get_pixel(x as u32, y as u32) == *RED_COLOR {
+ red += 1;
}
- return Err(CaptchaErr(format!("letter #{} {:?} invalid nb lines detected ({})", i+1, letter, red_px_pts.len())));
}
- letter = get_next_node(&red_px_pts, &letter, &letters_map, &visited, i, nb_lines)
- .ok_or(CaptchaErr(format!("letter #{} {:?} all neighbors already visited", i+1, letter)))?;
- break 'retry_loop;
+ hm.insert(l.clone(), red);
}
+ let (max, _) = hm.iter().max_by(|a, b| a.1.cmp(b.1)).unwrap();
+ letter = max.clone();
+ remaining.remove(&letter);
answer.push(letter.character);
- visited.insert(letter.clone());
}
Ok(answer)
}
@@ -298,74 +290,6 @@ fn get_starting_letter(img: &DynamicImage, letters_map: &HashMap<char, Letter>)
starting
}
-fn get_next_node(red_px_pts: &Vec<Point>, letter: &Letter, letters_map: &HashMap<char, Letter>, visited: &HashSet<Letter>, i: u32, nb_lines: usize) -> Option<Letter> {
- if i == NB_CHARS-2 {
- for (_, l) in letters_map.iter() {
- if !visited.contains(&l) {
- return Some(l.clone());
- }
- }
- return None;
- }
- for idx in 0..nb_lines {
- let fst_red_pt = red_px_pts.get(idx).unwrap();
- let angle = get_angle(fst_red_pt, &letter.center());
- let neighbor = get_letter_in_direction(&letter, angle, &letters_map).unwrap();
- if !visited.contains(&neighbor) {
- return Some(neighbor);
- }
- }
- None
-}
-
-fn get_letter_in_direction(letter: &Letter, angle: f64, letters_map: &HashMap<char, Letter>) -> Option<Letter> {
- let mut min_angle = f64::MAX;
- let mut out: Option<Letter> = None;
- // Visit every other letters
- for (_, other_letter) in letters_map.iter() {
- if other_letter == letter {
- continue;
- }
- // Find the angle between the two letters
- let t = other_letter.angle(letter);
- let angle_diff = (angle - t).abs();
- if angle_diff < min_angle {
- // Keep track of the letter with the smaller angle difference
- min_angle = angle_diff;
- out = Some(other_letter.clone());
- }
- }
- out
-}
-
-// Find the angle in radians between two points
-// Ensure the angle is always positive [0, 2*PI]
-fn get_angle(p1: &Point, p2: &Point) -> f64 {
- let delta_y = p1.y as f64 - p2.y as f64;
- let delta_x = p1.x as f64 - p2.x as f64;
- let mut angle = delta_y.atan2(delta_x);
- if angle < 0.0 {
- angle += 2.0 * std::f64::consts::PI;
- }
- angle
-}
-
-#[derive(Debug)]
-struct Rect {
- p1: Point,
- width: u32,
- height: u32,
-}
-
-impl Rect {
- fn enlarge(&mut self) {
- self.p1.x = self.p1.x.checked_sub(1).unwrap_or(0);
- self.p1.y = self.p1.y.checked_sub(1).unwrap_or(0);
- self.width += 2;
- self.height += 2;
- }
-}
-
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Point {
x: u32,
@@ -376,34 +300,6 @@ impl Point {
fn new(x: u32, y: u32) -> Self {
Self{x, y}
}
-
- fn add(&self, other: Self) -> Self {
- Self{x: self.x + other.x, y: self.y + other.y}
- }
-}
-
-fn get_contour_red_pixels(top_left_pt: &Point, img: &DynamicImage) -> Vec<Point> {
- let (img_width, img_height) = img.dimensions();
- let mut out = vec![];
- let mut add_px = |x, y| {
- if let Some(px_color) = get_pixel_in_bound(img, x, y) {
- if px_color == *RED_COLOR {
- out.push(top_left_pt.add(Point::new(x, y)));
- }
- }
- };
- // process points on x axis, top/bottom lines
- for x in 0..img_width {
- add_px(x, 0);
- add_px(x, img_height-1);
- }
- // Process points on y axis, left/right columns, excluding the first line and last line
- // We exclude first/last lines to avoid processing the corners twice
- for y in 1..img_height-1 {
- add_px(0, y);
- add_px(img_width-1, y);
- }
- out
}
fn get_pixel_in_bound(img: &DynamicImage, x: u32, y: u32) -> Option<Rgba<u8>> {
