Kirjautuminen

Haku

Tehtävät

Kilpailu

Murra koodi!
Lue ja osallistu!
Seuraava vihje 29.1.
Voittajia 1 + yrittäjiä 1

Keskustelu: Koodit: JavaScript: Sanajahti / wordz ratkoja

AtskaFin [06.01.2022 21:34:29]

#

Porukat pelasivat tässä illalla sanajahti 2:ta, joten päätinpä pikaisesti koodata ohjelman, joka osaa etsiä sanoja sanajahdin tyyppisestä taulukosta. (joo netistä tällaisia solvereitä löytyy pilvin pimein, mutta teinpä nyt oman).

Ohjelma tarvii kylkeensä vielä sanat joita etsiä. Itse latasin kotimaisten kielten keskuksen nykysuomen sanalistan ja converttasin sen tekstitiedostoksi, jossa jokaisella rivillä on yksi sana.

const fs = require('fs');

// Game board
const board = [
  'srsp',
  'räet',
  'möth',
  'adlä'
];

// Load dictionary
const finnishDictionary = fs.readFileSync('finnishDictionary.txt', { encoding:'utf8' })
    .split('\n')
    .filter(word => word.length > 2); // include only words that are atleast 3 letters long

const findStringsThatCanBeFormedFromAnotherString = (stringArray, givenString) => {
  const charCounts = new Array(215).fill(0);
  for (let i = givenString.length - 1; i >= 0; i--) {
      charCounts[givenString[i].toUpperCase().charCodeAt(0)]++;
  }

  return stringArray.filter(str => {
    const strCharCounts = new Array(215).fill(0);
    for (let i = str.length - 1; i >= 0; i--) strCharCounts[str[i].toUpperCase().charCodeAt(0)]++;
    for (let i = 65; i < 91; i++) return charCounts[i] >= strCharCounts[i]; // A-Z
    return charCounts[196] >= strCharCounts[196] || charCounts[214] >= strCharCounts[214]; // Ä&Ö
  });
};

const wordzDFS = (boardData, words) => {
  const filteredWords = findStringsThatCanBeFormedFromAnotherString(words, boardData.join(''));
  const wordsFound = new Set();

  filteredWords.map(n => n.toUpperCase()).forEach(wordToFind => {
    const visitedSlots = new Array(4);
    for (let i = 0; i < 4; i++) {
      visitedSlots[i] = new Array(4).fill(0);
    }

    const wordBuilder = [];
    let isWordBuiltSuccesfully = false;

    const dfs = (y, x) => {
      if (
        y < 0 || y > 3 || x < 0 || x > 3 || // outside of board?
        visitedSlots[y][x] || isWordBuiltSuccesfully || // slot already visited or word already found?
        wordToFind[wordBuilder.length] !== boardData[y][x].toUpperCase() // is character in this slot correct?
      ) return;

      visitedSlots[y][x] = 1;
      wordBuilder.push(boardData[y][x].toUpperCase());

      if (wordBuilder.length === wordToFind.length) {
        if (wordBuilder.join('') === wordToFind) {
          wordsFound.add(wordToFind);
          isWordBuiltSuccesfully = true;
        }

        return;
      }

      for (let i = -1; i < 2; i++) {
        for (let j = -1; j < 2; j++) {
          if (i === 0 && j === 0) continue;
          dfs(y+i,x+j);
        }
      }

      wordBuilder.pop();
      visitedSlots[y][x] = 0;
    }

    for (let i = 0; i < 4; i++) {
      for (let j = 0; j < 4; j++) {
        // if slot has first character of word then start dfs
        if (boardData[i][j].toUpperCase() === wordToFind[0]) dfs(i,j);
      }
    }
  });

  return Array.from(wordsFound).sort((a, b) => b.length - a.length);
};

console.log(wordzDFS(board, finnishDictionary).join('\n'));

AtskaFin [12.01.2022 19:20:04]

#

Tekaisin vielä huvikseen tuon skriptin ympärille käyttöliittymän:
https://sanajahti-ratkaisin.herokuapp.com/

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta