DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #227 - Android Lock Screen

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].

lockscreen

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)

Collapse
 
qm3ster profile image
Mihail Malo • 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.

Collapse
 
qm3ster profile image
Mihail Malo • 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.