DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #300 - Username / Password Comparison

#challenge

You are writing a password validator for a website. You want to discourage users from using their username as part of their password, or vice-versa, because it is insecure. Since its unreasonable to not allow them to have any letters in common, you come up with this rule:

For any password and username pair, the length of the longest common substring should be less than half the length of the shortest of the two.

In other words, you won't allow users to have half their password repeated in their username, or half their username repeated in their password.

Write a function validate(username, password) which returns true if your rule is followed, false otherwise.

Assume both the username and the password may contain uppercase letters, lowercase letters, numbers, spaces, and the following special/punctation characters: !@#$%^&*()_+{}:"<>?[];',. The username and password will each be less than 100 characters.

Examples

validate("newyorkcity", "yankees101"), TRUE
validate("username", "usernamePW"), FALSE

Tests

validate("Paa2", "Paaaaaa222!!!")
validate("wordpass", "password")
validate("superman", "persuzod")

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (3)

Collapse
 
peter279k profile image
peter279k •

Here is the simple solution with Python and difflib module:

import difflib


def validate(username, password):
    if len(username) == 0 and len(password) == 0:
        return False
    if len(username) == 0 or len(password) == 0:
        return False
    limit = min([len(password), len(username)]) / 2

    matches = difflib.SequenceMatcher(None, username, password).get_matching_blocks()
    size = 0
    for match in matches:
        if match.size >= limit:
            size += match.size

    if size == 0:
        return True
    return False
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mbaas2 profile image
Michael Baas •

Here's a solution in Dyalog APL:

∇ z←validate(a b);l;m;s;subs
 →(z←0∊l←≢¨a b)↑0                               ⍝ l=lengths, exit if there's 0 among them
 m←⌊/l                                          ⍝ lowest length
 s←(l⍳m)⊃a b                                    ⍝ get the shortest string
 m←⌊m÷2                                         ⍝ divide by 2
 subs←m{(↓⍺,[1.5]⍳(≢⍵)-⍺){⍺[1]↑⍺[2]↓⍵}¨⊂⍵}¨a b ⍝ look for matches of substrings of a in b (and vice versa)  ⍝ get substrings (of length m)
 z←~1∊∊subs{⍺⍷¨⊂⍵}¨b a                          ⍝ return 0 if we found any matches
∇
Enter fullscreen mode Exit fullscreen mode

Running it:

      validate'newyorkcity' 'yankees101'
1
      validate'username' 'usernamePW'
0
      validate'Paa2' 'Paaaaaa222!!!'
0
      validate'wordpass' 'password'
0
      validate'superman' 'persuzod'
1
      validate'abc' 'defghijklmnopab'  ⍝ added this testcase
0
Enter fullscreen mode Exit fullscreen mode

But don't take my word for it - Try It Online!

Collapse
 
qm3ster profile image
Mihail Malo • • Edited

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"));
}
Enter fullscreen mode Exit fullscreen mode

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"));
}
Enter fullscreen mode Exit fullscreen mode

Look at it go!

Read next

rijultp profile image

Enhancing User Experience with React-Joyride: How I made User onboarding seamless

Rijul Rajesh -

tiioluwani profile image

Navigating Search Solutions: A Comprehensive Comparison Guide to Meilisearch, Algolia, and ElasticSearch

Tiioluwani -

codewander profile image

WIP Notes working though Render hosting Flask + Vite + React + Wouter

Kanishka -

alwalxed profile image

Context Dump: Simplifying AI File Preparation

Awa -