Created
March 26, 2021 17:03
-
-
Save batiste/e0deae3a7bd3c764ee44f7a1be8c531a to your computer and use it in GitHub Desktop.
Google Coding Competition, Pattern matching, Round 1A 2020
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b3034 | |
function readInput() { | |
const readline = require('readline') | |
const rl = readline.createInterface({ | |
input: process.stdin, | |
output: process.stdout, | |
terminal: false | |
}) | |
let problem = { | |
T: 0, | |
testCases: [] | |
} | |
let currentTestCase = null; | |
rl.on('line', function (line) { | |
if (problem.T === 0) { | |
// Get number of test cases from first line | |
problem.T = Number(line) | |
} else { | |
// Get number of matches | |
if (!currentTestCase) { | |
currentTestCase = { P: Number(line), patterns: [] } | |
problem.testCases.push(currentTestCase) | |
} else { | |
currentTestCase.patterns.push(line.replace(/\*+/g, '*')) | |
} | |
if(currentTestCase.patterns.length === currentTestCase.P) { | |
currentTestCase = null; | |
} | |
} | |
}) | |
.on('close', () => { | |
// Finished processing input, now solve question | |
solveProblem(problem) | |
process.exit() | |
}) | |
} | |
function extractStart(str) { | |
let p = str.indexOf('*'); | |
if (p > -1) { | |
return str.substr(0, p) | |
} | |
return str | |
} | |
function extractEnd(str) { | |
let p = str.lastIndexOf('*'); | |
if (p > -1) { | |
return str.substr(p+1) | |
} | |
return str | |
} | |
function extractMiddle(str) { | |
let s = str.indexOf('*'); | |
let e = str.lastIndexOf('*'); | |
if (s > -1 && e > -1 && e != s) { | |
return str.substr(s, e).replace(/\*/g, '') | |
} | |
return '' | |
} | |
function addToStart(word, str) { | |
if (!word.start) { | |
word.start = str | |
} else { | |
if (word.start.length >= str.length) { | |
if (!word.start.includes(str)) { | |
throw (word.start + ' does not include ' + str) | |
} | |
} else { | |
if (!str.includes(word.start)) { | |
throw (str + ' does not include ' + word.start) | |
} | |
word.start = str | |
} | |
} | |
} | |
function addToEnd(word, str) { | |
if (!word.end) { | |
word.end = str | |
} else { | |
if (word.end.length >= str.length) { | |
if (!word.end.includes(str)) { | |
throw (word.end + ' does not include ' + str) | |
} | |
} else { | |
if (!str.includes(word.end)) { | |
throw (str + ' does not include ' + word.end) | |
} | |
word.end = str | |
} | |
} | |
} | |
function handleTestCase(testcase) { | |
let word = {start: '', middle: '', end: ''} | |
for(let pattern of testcase.patterns) { | |
if (pattern[0] != '*') { | |
addToStart(word, extractStart(pattern)) | |
} | |
if (pattern[pattern.length-1] != '*') { | |
addToEnd(word, extractEnd(pattern)) | |
} | |
word.middle = word.middle + extractMiddle(pattern) | |
} | |
if (word.start === word.end && ! word.middle) { | |
return word.start | |
} | |
return word.start + word.middle + word.end | |
} | |
function solveProblem(problem) { | |
let caseNb = 1; | |
for(let testcase of problem.testCases) { | |
try { | |
console.log(`Case #${caseNb}: ${handleTestCase(testcase)}`) | |
} catch (e) { | |
console.log(`Case #${caseNb}: *`) | |
} | |
caseNb++; | |
} | |
} | |
readInput() | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment