main.rs

use std::char;

type Board = [[char; 3]; 3];

static BOARD: Board = [
    ['C', 'B', 'X'],
    ['A', 'A', 'A'],
    ['N', 'N', 'T']
];

type Coord = (usize, usize);

static WORDS: [&'static str; 2] = ["BANANA", "CAT"];

#[derive(Default, Debug, Clone)]
struct LetterCoord {
    coord: Coord,
    letter: char,
}

#[derive(Debug, Clone, Default)]
struct BoardWalk {
    path: Vec<Coord>,
    buffer: String,
}

fn main() {
    let words: Vec<BoardWalk> = find_words(&BOARD, &WORDS);

    for word in words {
        println!("Word: {} - Path: {:?}", word.buffer, word.path);
    }
}

fn find_words(board: &Board, words: &[&'static str]) -> Vec<BoardWalk> {
    let mut row_n = 0 as usize;
    let coords = board
        .iter()
        .flat_map(|row| {
            let mut col_n = 0 as usize;
            let res = row.iter().map(move |letter| {
                let letter = LetterCoord {
                    coord: (row_n, col_n),
                    letter: letter.clone(),
                };
                col_n += 1;

                letter
            });

            row_n += 1;

            res
        })
        .collect::<Vec<LetterCoord>>();

    coords
        .iter()
        .flat_map(|coord| find_words_rec(&coord, &coords, words, None))
        .collect()
}

fn find_words_rec(
    coord: &LetterCoord,
    coords: &Vec<LetterCoord>,
    words: &[&'static str],
    walked: Option<BoardWalk>,
) -> Vec<BoardWalk> {
    let mut walked = walked.unwrap_or_default();
    let mut result = vec![];
    walked.path.push(coord.coord);
    walked.buffer.push(coord.letter);

    if words.contains(&walked.buffer.as_str()) {
        result.push(walked.clone());
    }

    for word in coords
        .iter()
        .filter(|inner_coord| {
            let diffr = i32::abs(coord.coord.0 as i32 - inner_coord.coord.0 as i32);
            let diffc = i32::abs(coord.coord.1 as i32 - inner_coord.coord.1 as i32);
            diffr <= 1 && diffc <= 1
        })
        .filter(|coord| !walked.path.contains(&coord.coord))
        .flat_map(|coord| find_words_rec(&coord, &coords, &words, Some(walked.clone())))
        .collect::<Vec<BoardWalk>>()
    {
        result.push(word);
    }

    result
}