Daily Challenge #227 - Android Lock Screen

#challenge

You might already be familiar with many smartphones that allow you to use a geometric pattern as a security measure. To unlock the device, you need to connect a sequence of dots/points in a grid by swiping your finger without lifting it as you trace the pattern through the screen. The image below has an example pattern of 7 dots/points: [A, B, I, E, D, G, C].

Your job is to implement the function countPatternsFrom(firstPoint, length); where firstPoint is a single-character string corresponding to the point in the grid (i.e.: 'A') and length is an integer indicating the length of the pattern. The function must return the number of combinations starting from the given point, that have the given length.

Take into account that dots can only be connected with straight directed lines either:

horizontally (like A to B)
vertically (like D to G),
diagonally (like I and E, as well as B and I), or
passing over a point that has already been 'used' like (G and C passing over E).

Examples

countPatternsFrom('B', 1), 1
countPatternsFrom('C', 2), 5

Tests

countPatternsFrom('D', 3)
countPatternsFrom('E', 4)
countPatternsFrom('E', 8)

Good luck!

This challenge comes from rsalago on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

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

Top comments (2)

Mihail Malo • Apr 16 '20 • Edited

Rust bruteforce solution

#[derive(Copy, Clone)]
struct Set(u16);
fn xy(n: i8) -> (i8, i8) {
    ((n % 3) as i8, (n / 3) as i8)
}

impl Set {
    fn has(&self, n: i8) -> bool {
        (self.0 & (1 << n)) != 0
    }
    fn flip(&self, n: i8) -> Self {
        Self(self.0 ^ (1 << n))
    }
}
impl Default for Set {
    fn default() -> Self {
        Set(0b111111111)
    }
}
fn attempt(pos: i8, depth: u8, field: Set) -> u16 {
    if depth == 0 {
        return 1;
    }
    let field = field.flip(pos);
    let (mx, my) = xy(pos);
    (0..9)
        .filter(|&i| field.has(i))
        .filter_map(|i| {
            let (x, y) = xy(i);
            let dx = x - mx;
            let dy = y - my;
            if match (dx.abs(), dy.abs()) {
                (0, 1) | (1, 0) | (1, 1) | (1, 2) | (2, 1) => true,
                (0, 2) | (2, 0) | (2, 2) => {
                    if !field.has((pos + i) / 2) {
                        true
                    } else {
                        false
                    }
                }
                _ => unreachable!(),
            } {
                Some(attempt(i, depth - 1, field))
            } else {
                None
            }
        })
        .sum()
}

fn main() {
    for start in 0..9 {
        for len in 0..=9 {
            println!(
                "start at {}, len {}: {} possibilities",
                start,
                len,
                attempt(start, len, Default::default())
            );
        }
    }
}

Look at it go
But note that the "game board" is rotationally symmetric, so there are only three distinctive positions: corner, side, and center.

Mihail Malo • Apr 16 '20 • Edited

Rust, precomputed here

#[derive(Debug)]
enum BadInputError {
    ZeroLength,
    FirstPoint(char),
}
fn count_patterns_from(first_point: char, length: usize) -> Result<u16, BadInputError> {
    if length < 2 {
        return Err(BadInputError::ZeroLength);
    }
    Ok(match first_point {
        'A' | 'C' | 'G' | 'I' => [1, 5, 31, 154, 684, 2516, 7104, 13792, 13792],
        'B' | 'D' | 'F' | 'H' => [1, 7, 37, 188, 816, 2926, 8118, 15564, 15564],
        'E' => [1, 8, 48, 256, 1152, 4248, 12024, 23280, 23280],
        bad => return Err(BadInputError::FirstPoint(first_point)),
    }
    .get(length - 2)
    .cloned()
    .unwrap_or(0))
}

fn main() {
    for start in (b'A'..=b'I').map(char::from) {
        println!("starting at {}, there are", start);
        for length in 1..=10 {
            match count_patterns_from(start, length) {
                Ok(num) => println!("\t{} patterns of length {}", num, length),
                Err(err) => eprintln!("{:?}", err),
            }
        }
    }
}

Deviations from spec: function named in snake_case, takes a char and not a single-char string.
Deviations from test cases: errors on length 1, as phones don't accept that, you need at least two anchors.

DEV Community

Daily Challenge #227 - Android Lock Screen

Examples

Tests

Top comments (2)

Rust bruteforce solution

Rust, precomputed here

Read next

3. How to setup Jest in a Next 15 project (+ eslint for testing)

How Does Cloud Computing Help in Scaling Applications Efficiently?

Mastering Git Stash: A Handy Tool for Managing Uncommitted Changes

Docker Swarm vs Kubernetes - A Deep Technical Analysis