## Algorithm

Problem Name: beecrowd | 3167

# Finding Words on Secondary Diagonal

By Elder Sobrinho, UFTM Brazil

Timelimit: 3

In Algelandia, the favorite pastime is the Word Search puzzles. One of these has the following characteristics:

1. The words occur only in the direction of the secondary diagonal;
2. Words can occur with uppercase and/or lowercase;
3. If a given word exists, it occurs only once and at any position on the diagonal;
4. Words can exist in both normal and inverted form, that is, the diagonal reading could be top-down or bottom-up form.

In this context, the figure below demonstrates how the words “workshop”, “videogame” and “scanner” can occur in the game.

## Input

The first line contains three integers: 1) N that represents the number of words that we will check if there are in the game, limited by [1,100]; 2) M that represents the number of lines in the matrix, limited by [10,1000]; 3) P that represents the number of columns in the matrix, limited by [10,1000]. In addition, each N-words follows the limit: [6,100].

## Output

Depending on the existence of each N-word, inform:

• 1 Palavra "X" na diagonal secundaria
• 2 Palavra "X" acima da diagonal secundaria
• 3 Palavra "X" abaixo da diagonal secundaria
• 4 Palavra "X" inexistente

Where X is the searched word, moreover, X must be in lower case.

 Input Sample Output Sample 7 20 20 equivocado maturidade prescindir insight designer efemero feeling SkCaBhRgVjAsDsHeJcEk FuNmHdIkWiJsOaRmStPm RwOuHsGOLcHtWtRvBeAf MaHuQnRwJbIoAbJrXjXt IoUjIEVgDdJeAvEpTbAv IuAlmvBresDppdEmRnSh QreEUrTSRcOraQAuJgNl BEfpQaitBnEdUdLqMpWp FeXgMgWoAsIiAnIpIfAm AfGqnvBkCrVkNnKgXmKj XoNeIoKIuoRxSsUqOsFn NirsItntCcCiXfWsDnMq SmGlEdAAVgGvCiSeEpKb VeNlIMDjMhMgBmHgGrLw OmBrIoGateVcXgTbPfXo HaAjAfKiEdRuMgXgQwFv VtWrWsSuNvFwGlWrLuWi BeJbRqGuXkHrJsMnGlCc RwXbViXmUdMeIpQgKvOe GvTmJjWfRmJkVcVgVrCr 1 Palavra "equivocado" na diagonal secundaria 2 Palavra "maturidade" acima da diagonal secundaria 2 Palavra "prescindir" acima da diagonal secundaria 3 Palavra "insight" abaixo da diagonal secundaria 2 Palavra "designer" acima da diagonal secundaria 2 Palavra "efemero" acima da diagonal secundaria 2 Palavra "feeling" acima da diagonal secundaria

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const { readFileSync } = require("fs")

const reverse = (str) => Array.from(str).reverse().join("")

class Matrix {
/**
* @param {number} rows
* @param {number} cols
*/
static createModel(rows = 0, cols = 0) { return ({ dimensions: { cols, rows } }) }
/**
* Create a square matrix from a object model
* @template T
* @param {ReturnType} model
* @param {Array} values
* @param {T} defaultReplacementValue
*/
static createFromModel(model, values, defaultReplacementValue = null) {
return Array.from({ length: model.dimensions.rows }, (_, rowIndex) => {
return Array.from({ length: model.dimensions.cols }, (_, colIndex) => {
return values[(model.dimensions.cols * rowIndex) + colIndex] || defaultReplacementValue
})
})
}
}

/** @param {string[][]} matrix  */
function findsWordsRelativeToSecondaryDiagonalFromMatrix(matrix) {
const rows = matrix.length
const cols = matrix[0].length

const secondaryDiagonalCharSequence = Array.from({ length: Math.min(rows, cols) }, (_, i) => matrix[i][cols - i - 1]).join("")
const aboveSecondaryDiagonalCharSequencesList = new Array(cols - 1).fill("")
const belowSecondaryDiagonalCharSequencesList = new Array(rows - 1).fill("")

// ABOVE SECONDARY DIAGONAL CHARACTER SEQUENCE LIST
for (let u = 1; u  < = aboveSecondaryDiagonalCharSequencesList.length; u++)
for (let i = 0, j = cols - u - 1; i  <  rows && j >= 0; i++, j--)
aboveSecondaryDiagonalCharSequencesList[u - 1] += matrix[i][j] || "0"

// BELOW SECONDARY DIAGONAL CHARACTER SEQUENCE LIST
for (let u = 1; u  < = belowSecondaryDiagonalCharSequencesList.length; u++)
for (let i = u, j = cols - 1; i  <  rows && j >= 0; i++, j--)
belowSecondaryDiagonalCharSequencesList[u - 1] += matrix[i][j] || "0"

return (word = "") => {
word = word.toLowerCase()
const reversed = reverse(word)

if (secondaryDiagonalCharSequence.includes(word) || secondaryDiagonalCharSequence.includes(reversed)) return "SECONDARY DIAGONAL"
if (aboveSecondaryDiagonalCharSequencesList.some(seq => seq.includes(word) || seq.includes(reversed))) return "ABOVE SECONDARY DIAGONAL"
if (belowSecondaryDiagonalCharSequencesList.some(seq => seq.includes(word) || seq.includes(reversed))) return "BELOW SECONDARY DIAGONAL"
}
}

function main() {
const output = []

const [numQueries, rows, cols] = input.shift().split(" ", 3).map(value => Number.parseInt(value, 10))
const words = input.splice(0, numQueries)
const chars = input.splice(0).map(row => row.split("", cols)).flat(1)

const squareMatrixModel = Matrix.createModel(rows, cols)
const matrix = Matrix.createFromModel(squareMatrixModel, chars, "")
const queriableMatrixSequencesInstance = findsWordsRelativeToSecondaryDiagonalFromMatrix(matrix)

for (const word of words) {
const result = queriableMatrixSequencesInstance(word)

switch (result) {
case "SECONDARY DIAGONAL": { output.push(`1 Palavra "\${word}" na diagonal secundaria`); break }
case "ABOVE SECONDARY DIAGONAL": { output.push(`2 Palavra "\${word}" acima da diagonal secundaria`); break }
case "BELOW SECONDARY DIAGONAL": { output.push(`3 Palavra "\${word}" abaixo da diagonal secundaria`); break }
}
}

console.log(output.join("\n"))
}

main()

/**
Conforme a existência de cada palavra N, informe:

1 Palavra "X" na diagonal secundaria
2 Palavra "X" acima da diagonal secundaria
3 Palavra "X" abaixo da diagonal secundaria
4 Palavra "X" inexistente
*/
``````
Copy The Code &

Input

cmd
7 20 20 equivocado maturidade prescindir insight designer efemero feeling SkCaBhRgVjAsDsHeJcEk FuNmHdIkWiJsOaRmStPm RwOuHsGOLcHtWtRvBeAf MaHuQnRwJbIoAbJrXjXt IoUjIEVgDdJeAvEpTbAv IuAlmvBresDppdEmRnSh QreEUrTSRcOraQAuJgNl BEfpQaitBnEdUdLqMpWp FeXgMgWoAsIiAnIpIfAm AfGqnvBkCrVkNnKgXmKj XoNeIoKIuoRxSsUqOsFn NirsItntCcCiXfWsDnMq SmGlEdAAVgGvCiSeEpKb VeNlIMDjMhMgBmHgGrLw OmBrIoGateVcXgTbPfXo HaAjAfKiEdRuMgXgQwFv VtWrWsSuNvFwGlWrLuWi BeJbRqGuXkHrJsMnGlCc RwXbViXmUdMeIpQgKvOe GvTmJjWfRmJkVcVgVrCr

Output

cmd
1 Palavra "equivocado" na diagonal secundaria 2 Palavra "maturidade" acima da diagonal secundaria 2 Palavra "prescindir" acima da diagonal secundaria 3 Palavra "insight" abaixo da diagonal secundaria 2 Palavra "designer" acima da diagonal secundaria 2 Palavra "efemero" acima da diagonal secundaria 2 Palavra "feeling" acima da diagonal secundaria