Discussion on: Daily Challenge #300 - Username / Password Comparison

View post

Rust

#![feature(once_cell)]

use aho_corasick::AhoCorasick;
use regex::Regex;
use std::collections::HashSet;
use std::lazy::SyncLazy;

static REGEX: SyncLazy<Regex> = SyncLazy::new(|| Regex::new(r"^[!-z&&[^\-/=\\]]{2,100}$").unwrap());

fn validate(u: &str, p: &str) -> bool {
    if [u, p].iter().any(|x| !REGEX.is_match(x)) {
        return false;
    };
    let (needle, haystack) = if u.len() < p.len() { (u, p) } else { (p, u) };

    let len = needle.len() / 2;
    let patterns = (0..needle.len() - len)
        .into_iter()
        .map(|i| &needle[i..i + len])
        .collect::<HashSet<_>>();
    let corasick = AhoCorasick::new(patterns);
    !corasick.is_match(haystack)
}

fn main() {
    assert_eq!(validate("newyorkcity", "yankees101"), true);
    assert_eq!(validate("username", "usernamePW"), false);
    dbg!(validate("Paa2", "Paaaaaa222!!!"));
    dbg!(validate("wordpass", "password"));
    dbg!(validate("superman", "persuzod"));
}

Look at it go!

A silly one.
Regex with range subtraction (all characters '!' to 'z' are accepted, except - / = and \), also checks for length.
So that regex is compiled only once, we construct it lazily.

Then we pick the shorter of the two strings, get all the overlapping windows into it, and colleсt them into a HashSet for uniqueness.

Then we use an Aho-Corasick automaton with all of these substrings to match on them simultaneously in one pass.

However, if you think about it, the same thing can be written without dependencies/nightly features
This trades CPU for memory, for instance:

fn ok_char(c: char) -> bool {
    match c {
        '-' | '/' | '=' | '\\' => false,
        '!'..='z' => true,
        _ => false,
    }
}

fn validate(u: &str, p: &str) -> bool {
    if [u, p].iter().any(|x| x.chars().any(|c| !ok_char(c))) {
        return false;
    }
    let (needle, haystack) = if u.len() < p.len() { (u, p) } else { (p, u) };

    let len = needle.len() / 2;
    !(0..needle.len() - len)
        .into_iter()
        .map(|i| &needle[i..i + len])
        .any(|w| haystack.contains(w))
}

fn main() {
    assert_eq!(validate("newyorkcity", "yankees101"), true);
    assert_eq!(validate("username", "usernamePW"), false);
    dbg!(validate("Paa2", "Paaaaaa222!!!"));
    dbg!(validate("wordpass", "password"));
    dbg!(validate("superman", "persuzod"));
}