ROSECODE 560
Grid painting
The original interaction is no longer available. Any surviving program is preserved as source code.
Let there be a grid with M rows and N columns. The cells are numbered starting from 0 (topmost left) to MxN-1 (bottommost right) and some cells are painted to yellow randomly using the following code:
uint8 grid[NROWS*NCOLS] = {0};
void FillGrid(const int NROWS, const int NCOLS, const int NCELLS)
{
int NCellsPainted = (NCELLS+1)>>1;
uint painted = 0;
uint32 seed = 10001;
while (painted < NCellsPainted)
{
seed = seed * 10001 + 1001;
uint rowcol = seed % NCELLS;
if (grid[rowcol] == 0)
{
grid[rowcol] = 1; // [row,col] painted
++painted;
}
}
}
Consider as an example a 6x7 grid filled with 20 painted cells by generating random numbers in the range [0, 40):
let createMatrix = (m, n) => {
let [row, column] = [[], []],
rowColumn = m * n
for (let i = 0; i < rowColumn; i++) {
column.push(i)
if ((i+1) % n === 0) {
row.push(column)
column = []
}
}
return row
}
let setColorForEachElement = (matrix, nums) => {
let row = matrix.map(row => {
let column = row.map((column, key) => {
return { number: column, color: nums.indexOf(column) != -1?'yellow':'white' }
})
return column
})
return row
}
let generateNumbers = (m, n, s) =>
{
let grid = Array(m*n).fill(0);
let nums = [];
let NCells = s;
let NCellsPainted = (s+1)>>1;
let painted = 0;
let seed = 10001;
while (painted < NCellsPainted)
{
seed = seed * 10001 + 1001;
seed %= 4294967296;
let rowcol = seed % NCells;
if (grid[rowcol] == 0)
{
grid[rowcol] = 1;
nums.push(rowcol);
++painted;
}
}
return nums;
}
const matrix = createMatrix(6, 7)
const colorApi = setColorForEachElement(matrix, generateNumbers(6,7,40))
let table ='<font face="Courier New"><table>'
colorApi.forEach(row => {
table+= '<tr>'
row.forEach(column => table += `<td style='background: ${column.color};'>${column.number}<td>` )
table+='</tr>'
})
table+= '</table></font>'
let outputDiv = document.getElementById("ExampleGrid");
outputDiv.innerHTML = table;
Notice that some cells are painted contiguously (on the same row the cells to the right or to the left of a painted cell or on the same column upper/lower cells are also painted). Let's find such randomly painted blocks with more than 1 cell and treat them as some sets. As for the example we would have the following two sets:
S1 = {0, 1, 2, 3, 4, 5, 7, 8, 11, 15}
S2 = {17, 23, 24, 25, 28, 29, 30}
S1 has 10 elements that sum to 56 and S2 has 7 elements that sum to 176.
How many such sets would we have if we have a 9991x1001 grid filled with 5000000 painted cells by generating random integers in the range [0, 10000000)?
What would be the set number of the set with the maximal number of elements?
What would be the set number of the set with the maximal sum of elements?
Note that the sets are sorted by their smallest elements and numbered accordingly.
Answer format: a,b,c,d,e,f,g where
a is the number of sets
b is the set number of the set with the maximal number of elements
c is the number of elements of the set Sb
d is the sum of elements of the set Sb
e is the set number of the set with the maximal sum of elements
f is the number of elements of the set Se
g is the sum of elements of the set Se
Example: 2,1,10,56,2,7,176 for the 6x7 grid above.
[My timing: <10s]