Skip to content

Instantly share code, notes, and snippets.

@DimitarNestorov
Last active February 24, 2019 17:24
Show Gist options
  • Save DimitarNestorov/a0d26b0a436a6582c3fb5cc25453ab67 to your computer and use it in GitHub Desktop.
Save DimitarNestorov/a0d26b0a436a6582c3fb5cc25453ab67 to your computer and use it in GitHub Desktop.
hash code pizza practice problem
const fs = require('fs')
const file = fs.readFileSync('./a_example.in', 'utf8')
// const file = fs.readFileSync('./b_small.in', 'utf8')
function cloneArray(arr) {
return arr.slice(0)
}
function cloneMatrix(arr) {
return arr.map(a => a.slice(0))
}
let pizza = file.split('\n')
const [ rows, columns, minIngridients, maxArea ] = pizza.shift().split(' ').map(item => parseInt(item, 10))
while (pizza.length > rows) {
pizza.pop()
}
pizza = pizza.map(line => line.split(''))
console.log(rows, columns, minIngridients, maxArea)
console.log(pizza)
// get all possible slices
const area = rows * columns
const slices = []
for (let i = 0; i < area; i++) {
const currentRow = i % rows
const currentColumn = i % columns
for (let j = 0, endRow = currentRow + j; ((j <= maxArea) && (endRow < rows)); j++, endRow++) {
for (let k = 0, endColumn = currentColumn + k; ((k <= maxArea) && (endColumn < columns)); k++, endColumn++) {
const area = (endRow - currentRow + 1) * (endColumn - currentColumn + 1)
if (area > maxArea) {
continue
}
let mushrooms = 0
let tomatoes = 0
for (let m = currentRow; m <= endRow; m++) {
for (let n = currentColumn; n <= endColumn; n++) {
if (pizza[m][n] === 'M') {
mushrooms++
} else if (pizza[m][n] === 'T') {
tomatoes++
}
}
}
if ((tomatoes < minIngridients) || (mushrooms < minIngridients)) {
continue
}
slices.push([currentRow, currentColumn, endRow, endColumn])
}
}
}
// console.log(slices)
// build maps with all possible combinations
const pizzas = []
function cutSliceFromPizza(slice, pizza) {
let [ currentRow, currentColumn, endRow, endColumn ] = slice
for (let i = currentRow; i <= endRow; i++) {
for (let j = currentColumn; j <= endColumn; j++) {
if (pizza[i][j]) {
pizza[i][j] = ''
} else {
return true
}
}
}
}
function matchWithOtherSlices(possibleSlices, index, pizza, pizzaSlices) {
const firstSlice = possibleSlices[index]
if (cutSliceFromPizza(firstSlice, pizza)) return
pizzaSlices.push(firstSlice)
pizzas.push({pizza, slices: pizzaSlices})
const otherSlices = cloneArray(possibleSlices)
otherSlices.splice(index, 1)
for (let i = 0; i < otherSlices.length; i++) {
matchWithOtherSlices(otherSlices, i, cloneMatrix(pizza), cloneArray(pizzaSlices))
}
}
for (let i = 0; i < slices.length; i++) {
matchWithOtherSlices(slices, i, cloneMatrix(pizza), [])
}
// console.log(pizzas)
// score every map
pizzas.forEach((data) => {
const { pizza } = data
data.score = pizza.reduce(
(score, row) => row.reduce(
(score, item) => score += Number(!Boolean(item)),
score
),
0
)
})
// print highest score map
const bestPizza = pizzas.reduce((pizza, bestPizza) =>
pizza.score > bestPizza.score ? pizza : bestPizza
, {score: 0})
console.log(bestPizza)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment