Mixing
Partition a square grid into parts of equal area
$begingroup$
This challenge is based on the following puzzle: You are given an n by n grid with n cells marked. Your job is to the partition the grid into n parts where each part consists of exactly n cells, each containing exactly one marked cell.
Example
Here is a puzzle on the left and its (unique) solution on the right:
Challenge
You will be given a set of n zero-indexed coordinates in any reasonable format.
[(0,0), (0,3), (1,0), (1,1), (2,2)]
And your job is to write a program that returns any valid parition (again, in any reasonable format).
[
[(0,0), (0,1), (0,2), (1,2), (1,3)],
[(0,3), (0,4), (1,4), (2,4), (3,4)],
[(1,0), (2,0), (3,0), (4,0), (4,1)],
[(1,1), (2,1), (3,1), (3,2), (4,2)],
[(2,2), (2,3), (3,3), (4,3), (4,4)]
]
If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.
Input/Output Examples
[(0,0)] => [[(0,0)]]
[(0,0), (1,1)] => [
[(0,0), (1,0)],
[(0,1), (1,1)]
]
[(0,0), (0,1), (1,0)] => (no solution)
[(0,0), (0,1), (0,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (1,1), (2,1)],
[(0,2), (1,2), (2,2)],
]
[(0,0), (0,2), (1,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (0,2), (1,1)],
[(1,2), (2,1), (2,2)],
]
Scoring
This is code-golf, so shortest code wins.
code-golf combinatorics grid set-partitions
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
$endgroup$
|
show 4 more comments
$begingroup$
This challenge is based on the following puzzle: You are given an n by n grid with n cells marked. Your job is to the partition the grid into n parts where each part consists of exactly n cells, each containing exactly one marked cell.
Example
Here is a puzzle on the left and its (unique) solution on the right:
Challenge
You will be given a set of n zero-indexed coordinates in any reasonable format.
[(0,0), (0,3), (1,0), (1,1), (2,2)]
And your job is to write a program that returns any valid parition (again, in any reasonable format).
[
[(0,0), (0,1), (0,2), (1,2), (1,3)],
[(0,3), (0,4), (1,4), (2,4), (3,4)],
[(1,0), (2,0), (3,0), (4,0), (4,1)],
[(1,1), (2,1), (3,1), (3,2), (4,2)],
[(2,2), (2,3), (3,3), (4,3), (4,4)]
]
If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.
Input/Output Examples
[(0,0)] => [[(0,0)]]
[(0,0), (1,1)] => [
[(0,0), (1,0)],
[(0,1), (1,1)]
]
[(0,0), (0,1), (1,0)] => (no solution)
[(0,0), (0,1), (0,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (1,1), (2,1)],
[(0,2), (1,2), (2,2)],
]
[(0,0), (0,2), (1,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (0,2), (1,1)],
[(1,2), (2,1), (2,2)],
]
Scoring
This is code-golf, so shortest code wins.
code-golf combinatorics grid set-partitions
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
$endgroup$
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50
|
show 4 more comments
$begingroup$
This challenge is based on the following puzzle: You are given an n by n grid with n cells marked. Your job is to the partition the grid into n parts where each part consists of exactly n cells, each containing exactly one marked cell.
Example
Here is a puzzle on the left and its (unique) solution on the right:
Challenge
You will be given a set of n zero-indexed coordinates in any reasonable format.
[(0,0), (0,3), (1,0), (1,1), (2,2)]
And your job is to write a program that returns any valid parition (again, in any reasonable format).
[
[(0,0), (0,1), (0,2), (1,2), (1,3)],
[(0,3), (0,4), (1,4), (2,4), (3,4)],
[(1,0), (2,0), (3,0), (4,0), (4,1)],
[(1,1), (2,1), (3,1), (3,2), (4,2)],
[(2,2), (2,3), (3,3), (4,3), (4,4)]
]
If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.
Input/Output Examples
[(0,0)] => [[(0,0)]]
[(0,0), (1,1)] => [
[(0,0), (1,0)],
[(0,1), (1,1)]
]
[(0,0), (0,1), (1,0)] => (no solution)
[(0,0), (0,1), (0,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (1,1), (2,1)],
[(0,2), (1,2), (2,2)],
]
[(0,0), (0,2), (1,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (0,2), (1,1)],
[(1,2), (2,1), (2,2)],
]
Scoring
This is code-golf, so shortest code wins.
code-golf combinatorics grid set-partitions
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
$endgroup$
This challenge is based on the following puzzle: You are given an n by n grid with n cells marked. Your job is to the partition the grid into n parts where each part consists of exactly n cells, each containing exactly one marked cell.
Example
Here is a puzzle on the left and its (unique) solution on the right:
Challenge
You will be given a set of n zero-indexed coordinates in any reasonable format.
[(0,0), (0,3), (1,0), (1,1), (2,2)]
And your job is to write a program that returns any valid parition (again, in any reasonable format).
[
[(0,0), (0,1), (0,2), (1,2), (1,3)],
[(0,3), (0,4), (1,4), (2,4), (3,4)],
[(1,0), (2,0), (3,0), (4,0), (4,1)],
[(1,1), (2,1), (3,1), (3,2), (4,2)],
[(2,2), (2,3), (3,3), (4,3), (4,4)]
]
If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.
Input/Output Examples
[(0,0)] => [[(0,0)]]
[(0,0), (1,1)] => [
[(0,0), (1,0)],
[(0,1), (1,1)]
]
[(0,0), (0,1), (1,0)] => (no solution)
[(0,0), (0,1), (0,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (1,1), (2,1)],
[(0,2), (1,2), (2,2)],
]
[(0,0), (0,2), (1,2)] => [
[(0,0), (1,0), (2,0)],
[(0,1), (0,2), (1,1)],
[(1,2), (2,1), (2,2)],
]
Scoring
This is code-golf, so shortest code wins.
code-golf combinatorics grid set-partitions
code-golf combinatorics grid set-partitions
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
edited Jan 24 at 19:12
Peter Kagey
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
asked Jan 24 at 1:01
Peter KageyPeter Kagey
953519
953519
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50
|
show 4 more comments
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or $false$ if there's no solution.
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
Try it online!
How?
We first build a square matrix $m$ of size $Ntimes N$, where $N$ is the length of the input:
m = a.map(_ => [...a])
Each row of $m$ consists of a copy of the input, i.e. an array of $N$ coordinate pairs. The important point here is that all cells of $m$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator ++.
The recursive function $g$ takes a pointer $n$ into the input, the coordinates $(X,Y)$ of the previous cell, a counter $j$ that holds the number of filled cells in the current area, and a flag $i$ that is set when the marked cell is found in the area:
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
We test $a[n]$ to know if all areas have been processed and we test $a[j]$ to know if enough cells have been filled in the current area.
The main part of $g$ looks for the next cell of $m$ to fill by iterating on all of them:
m.some((r, y) => // for each row r at position y in m:
r.some((v, x) => // for each cell of value v at position x in r:
++v | // if this cell is already filled (i.e. v is numeric)
(X - x) ** 2 + // or the squared Euclidean distance between
(Y - y) ** 2 - // (X, Y) and (x, y)
1 ? // is not equal to 1:
0 // this is an invalid target square: do nothing
: // else:
g( // do a recursive call to g:
r[x] = n, // pass n unchanged and fill the cell with n
x, y, // pass the coordinates of the current cell
j + 1, // increment j
i | // update i:
x + [,y] == a[n] // set it if (x, y) = a[n]
) ? // if the result of the call is truthy:
1 // return 1
: // else:
r[x] = v // reset the cell to NaN
) // end of inner map()
) // end of outer map()
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179074%2fpartition-a-square-grid-into-parts-of-equal-area%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or $false$ if there's no solution.
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
Try it online!
How?
We first build a square matrix $m$ of size $Ntimes N$, where $N$ is the length of the input:
m = a.map(_ => [...a])
Each row of $m$ consists of a copy of the input, i.e. an array of $N$ coordinate pairs. The important point here is that all cells of $m$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator ++.
The recursive function $g$ takes a pointer $n$ into the input, the coordinates $(X,Y)$ of the previous cell, a counter $j$ that holds the number of filled cells in the current area, and a flag $i$ that is set when the marked cell is found in the area:
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
We test $a[n]$ to know if all areas have been processed and we test $a[j]$ to know if enough cells have been filled in the current area.
The main part of $g$ looks for the next cell of $m$ to fill by iterating on all of them:
m.some((r, y) => // for each row r at position y in m:
r.some((v, x) => // for each cell of value v at position x in r:
++v | // if this cell is already filled (i.e. v is numeric)
(X - x) ** 2 + // or the squared Euclidean distance between
(Y - y) ** 2 - // (X, Y) and (x, y)
1 ? // is not equal to 1:
0 // this is an invalid target square: do nothing
: // else:
g( // do a recursive call to g:
r[x] = n, // pass n unchanged and fill the cell with n
x, y, // pass the coordinates of the current cell
j + 1, // increment j
i | // update i:
x + [,y] == a[n] // set it if (x, y) = a[n]
) ? // if the result of the call is truthy:
1 // return 1
: // else:
r[x] = v // reset the cell to NaN
) // end of inner map()
) // end of outer map()
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
$endgroup$
add a comment |
$begingroup$
JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or $false$ if there's no solution.
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
Try it online!
How?
We first build a square matrix $m$ of size $Ntimes N$, where $N$ is the length of the input:
m = a.map(_ => [...a])
Each row of $m$ consists of a copy of the input, i.e. an array of $N$ coordinate pairs. The important point here is that all cells of $m$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator ++.
The recursive function $g$ takes a pointer $n$ into the input, the coordinates $(X,Y)$ of the previous cell, a counter $j$ that holds the number of filled cells in the current area, and a flag $i$ that is set when the marked cell is found in the area:
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
We test $a[n]$ to know if all areas have been processed and we test $a[j]$ to know if enough cells have been filled in the current area.
The main part of $g$ looks for the next cell of $m$ to fill by iterating on all of them:
m.some((r, y) => // for each row r at position y in m:
r.some((v, x) => // for each cell of value v at position x in r:
++v | // if this cell is already filled (i.e. v is numeric)
(X - x) ** 2 + // or the squared Euclidean distance between
(Y - y) ** 2 - // (X, Y) and (x, y)
1 ? // is not equal to 1:
0 // this is an invalid target square: do nothing
: // else:
g( // do a recursive call to g:
r[x] = n, // pass n unchanged and fill the cell with n
x, y, // pass the coordinates of the current cell
j + 1, // increment j
i | // update i:
x + [,y] == a[n] // set it if (x, y) = a[n]
) ? // if the result of the call is truthy:
1 // return 1
: // else:
r[x] = v // reset the cell to NaN
) // end of inner map()
) // end of outer map()
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
$endgroup$
add a comment |
$begingroup$
JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or $false$ if there's no solution.
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
Try it online!
How?
We first build a square matrix $m$ of size $Ntimes N$, where $N$ is the length of the input:
m = a.map(_ => [...a])
Each row of $m$ consists of a copy of the input, i.e. an array of $N$ coordinate pairs. The important point here is that all cells of $m$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator ++.
The recursive function $g$ takes a pointer $n$ into the input, the coordinates $(X,Y)$ of the previous cell, a counter $j$ that holds the number of filled cells in the current area, and a flag $i$ that is set when the marked cell is found in the area:
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
We test $a[n]$ to know if all areas have been processed and we test $a[j]$ to know if enough cells have been filled in the current area.
The main part of $g$ looks for the next cell of $m$ to fill by iterating on all of them:
m.some((r, y) => // for each row r at position y in m:
r.some((v, x) => // for each cell of value v at position x in r:
++v | // if this cell is already filled (i.e. v is numeric)
(X - x) ** 2 + // or the squared Euclidean distance between
(Y - y) ** 2 - // (X, Y) and (x, y)
1 ? // is not equal to 1:
0 // this is an invalid target square: do nothing
: // else:
g( // do a recursive call to g:
r[x] = n, // pass n unchanged and fill the cell with n
x, y, // pass the coordinates of the current cell
j + 1, // increment j
i | // update i:
x + [,y] == a[n] // set it if (x, y) = a[n]
) ? // if the result of the call is truthy:
1 // return 1
: // else:
r[x] = v // reset the cell to NaN
) // end of inner map()
) // end of outer map()
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
$endgroup$
JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or $false$ if there's no solution.
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
Try it online!
How?
We first build a square matrix $m$ of size $Ntimes N$, where $N$ is the length of the input:
m = a.map(_ => [...a])
Each row of $m$ consists of a copy of the input, i.e. an array of $N$ coordinate pairs. The important point here is that all cells of $m$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator ++.
The recursive function $g$ takes a pointer $n$ into the input, the coordinates $(X,Y)$ of the previous cell, a counter $j$ that holds the number of filled cells in the current area, and a flag $i$ that is set when the marked cell is found in the area:
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
We test $a[n]$ to know if all areas have been processed and we test $a[j]$ to know if enough cells have been filled in the current area.
The main part of $g$ looks for the next cell of $m$ to fill by iterating on all of them:
m.some((r, y) => // for each row r at position y in m:
r.some((v, x) => // for each cell of value v at position x in r:
++v | // if this cell is already filled (i.e. v is numeric)
(X - x) ** 2 + // or the squared Euclidean distance between
(Y - y) ** 2 - // (X, Y) and (x, y)
1 ? // is not equal to 1:
0 // this is an invalid target square: do nothing
: // else:
g( // do a recursive call to g:
r[x] = n, // pass n unchanged and fill the cell with n
x, y, // pass the coordinates of the current cell
j + 1, // increment j
i | // update i:
x + [,y] == a[n] // set it if (x, y) = a[n]
) ? // if the result of the call is truthy:
1 // return 1
: // else:
r[x] = v // reset the cell to NaN
) // end of inner map()
) // end of outer map()
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
edited Jan 25 at 0:48
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
answered Jan 24 at 2:26
ArnauldArnauld
78.7k795327
78.7k795327
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179074%2fpartition-a-square-grid-into-parts-of-equal-area%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
Jan 24 at 1:07
$begingroup$
@Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint.
$endgroup$
– Peter Kagey
Jan 24 at 1:10
$begingroup$
Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance.
$endgroup$
– Arnauld
Jan 24 at 1:16
$begingroup$
Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4?
$endgroup$
– Olivier Grégoire
Jan 24 at 7:30
$begingroup$
May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted.
$endgroup$
– Arnauld
Jan 24 at 13:50