Daily Challenge #150 - Boggle Guess Validator

#challenge

Setup

Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. Your function should take two arguments (2D array and string) and return true or false as to whether the string found in the array follows Boggle rules.

Valid guesses are strings that can be formed by connecting adjacent letters in any direction without using any previously used letters.

Example

 { {'I','L','A','W'},
  {'B','N','G','E'},
  {'I','U','A','O'},
  {'A','S','R','L'} }

In this Boggle board, the words "BINGO", "ILNBIA", and "LINGO" would be valid guesses, while "BUNGIE", "BINS", and "SINUS" would not be. You do not have to test whether the string is a valid word or not, only if it is a valid guess.

Test

{ {'E','A','R','A'},
{'N','L','E','C'},
{'I','A','I','S'},
{'B','Y','O','R'} }

Good luck, have fun coding~!

This challenge comes from 747823 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 (1)

Brett Martin • Dec 31 '19

JavaScript - not pretty and will think about how to make more elegant 😊 . I can move to codepen or something if this is way to big of a blurb

const getAllIdx = (arr, val) => {
    let indexes = [], i = -1;
    while ((i = arr.indexOf(val, i+1)) != -1){
        indexes.push(i);
    }
    return indexes;
}

const intersect = (a, b) => {
    const setA = new Set(a);
    const setB = new Set(b);
    const intersection = new Set([...setA].filter(x => setB.has(x)));
    return Array.from(intersection);
}

const range = (start, stop, step) => {
    const result = [];
    for (let i = start; i <= stop; i += step) {
        result.push(i);
    }

    return result;
}

const canBuildWord = (height, [first, second, ...rest], used=[]) => {
    let res = [];
    if (second === undefined) return true;

    for(let i = 0; i < first.length; i++) {

        nextUsed = [...used, first[i]];
        let val = first[i];
        ajacentIdx = [val-height, val+height];
        const rightBound = range(height-1, (height-1) + (height * (height-1)), height);
        const leftBound = range(0, height * height - 1, height);

        if (!rightBound.includes(val)) {
            ajacentIdx.push(val+1, val-height+1, val+height+1);
        }
        if (!leftBound.includes(val)) {
            ajacentIdx.push(val-1, val-height-1, val+height-1);
        }

        ajacentIdx = ajacentIdx.filter(x => !nextUsed.includes(x));

        let intersection = intersect(ajacentIdx, second);
        if (intersection.length === 0) {
            res.push(false);
        } else {
            for(let j = 0; j < intersection.length; j++) {
                res.push(canBuildWord(height, [intersection, ...rest], [...nextUsed, intersection[j]]));
            }
        }

    }
    return res.some(x => x);
}

const checkWord = (board, guess) => {
    const chars = guess.split('');
    const flat = [].concat.apply([], board);

    const startingPoints =[];
    for (let i = 0; i < chars.length; i++) {
        startingPoints.push(getAllIdx(flat, chars[i]));
    }

    const missingLetter = startingPoints.filter(points => points.length === 0).length !== 0;
    if (missingLetter) return false;

    return canBuildWord(board.length, startingPoints);
}

DEV Community

Daily Challenge #150 - Boggle Guess Validator

Setup

Example

Test

Top comments (1)

Read next

isclose and equal in PyTorch

Observability(Metrics, Monitoring & Prometheus) -2

Introducing BPMN support in .NET Workflow Engine library

Why You Should Use AWS Lambda For Web Development