Algorithm


Problem Name: beecrowd | 3167

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/3167

Finding Words on Secondary Diagonal

 

By Elder Sobrinho, UFTM BR 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 input = readFileSync("/dev/stdin", "utf8").toLowerCase().split("\n")

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"
		return "NOT FOUND"
	}
}


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 }
			case "NOT FOUND": { output.push(`4 Palavra "${word}" inexistente`); 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 & Try With Live Editor

Input

x
+
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

x
+
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
Advertisements

Demonstration


Previous
#3166 Beecrowd Online Judge Solution 3166 Finding Words on Main Diagonal Solution in C, C++, Java, Js and Python
Next
#3170 Beecrowd Online Judge Solution 3170 Christmas Balls Solution in C, C++, Java, Js and Python