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

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 [e-mail] with your suggestions!

Comments

[Mihail Malo]

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]

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.