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.
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 5 hours ago
Peter KageyPeter Kagey
773517
$endgroup$
add a comment |
$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.
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 5 hours ago
Peter KageyPeter Kagey
773517
$endgroup$
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
5 hours ago
$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
5 hours ago
$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
5 hours ago
add a comment |
$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.
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 5 hours ago
Peter KageyPeter Kagey
773517
$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.
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 5 hours ago
Peter KageyPeter Kagey
773517
asked 5 hours ago
Peter KageyPeter Kagey
773517
asked 5 hours ago
Peter KageyPeter Kagey
773517
asked 5 hours ago
Peter KageyPeter Kagey
773517
asked 5 hours ago
Peter KageyPeter Kagey
773517
773517
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
5 hours ago
$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
5 hours ago
$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
5 hours ago
add a comment |
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
5 hours ago
$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
5 hours ago
$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
5 hours ago
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
5 hours ago
$begingroup$
This was inspired by this Math Stack Exchange question.
$endgroup$
– Peter Kagey
5 hours ago
$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
5 hours ago
$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
5 hours ago
$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
5 hours ago
$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
5 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
JavaScript (ES6), 163 bytes
Prints all possible solutions as matrices containing 1-indexed values that describe the partition. (Or prints nothing if there's no solution.)
a=>(m=a.map(_=>[...a]),g=(n,[X,Y]=a[n++],j=0)=>a[j]?m.map((r,y)=>r.map((v,x)=>++v|(X-x)**2+(Y-y)**2-!!j?0:r[g(r[x]=n,[x,y],j+1),x]=v)):a[n]?g(n):console.log(m))(0)
Try it online!
answered 4 hours ago
ArnauldArnauld
73.9k690310
$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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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 (ES6), 163 bytes
Prints all possible solutions as matrices containing 1-indexed values that describe the partition. (Or prints nothing if there's no solution.)
a=>(m=a.map(_=>[...a]),g=(n,[X,Y]=a[n++],j=0)=>a[j]?m.map((r,y)=>r.map((v,x)=>++v|(X-x)**2+(Y-y)**2-!!j?0:r[g(r[x]=n,[x,y],j+1),x]=v)):a[n]?g(n):console.log(m))(0)
Try it online!
answered 4 hours ago
ArnauldArnauld
73.9k690310
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 163 bytes
Prints all possible solutions as matrices containing 1-indexed values that describe the partition. (Or prints nothing if there's no solution.)
a=>(m=a.map(_=>[...a]),g=(n,[X,Y]=a[n++],j=0)=>a[j]?m.map((r,y)=>r.map((v,x)=>++v|(X-x)**2+(Y-y)**2-!!j?0:r[g(r[x]=n,[x,y],j+1),x]=v)):a[n]?g(n):console.log(m))(0)
Try it online!
answered 4 hours ago
ArnauldArnauld
73.9k690310
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 163 bytes
Prints all possible solutions as matrices containing 1-indexed values that describe the partition. (Or prints nothing if there's no solution.)
a=>(m=a.map(_=>[...a]),g=(n,[X,Y]=a[n++],j=0)=>a[j]?m.map((r,y)=>r.map((v,x)=>++v|(X-x)**2+(Y-y)**2-!!j?0:r[g(r[x]=n,[x,y],j+1),x]=v)):a[n]?g(n):console.log(m))(0)
Try it online!
answered 4 hours ago
ArnauldArnauld
73.9k690310
$endgroup$
JavaScript (ES6), 163 bytes
Prints all possible solutions as matrices containing 1-indexed values that describe the partition. (Or prints nothing if there's no solution.)
a=>(m=a.map(_=>[...a]),g=(n,[X,Y]=a[n++],j=0)=>a[j]?m.map((r,y)=>r.map((v,x)=>++v|(X-x)**2+(Y-y)**2-!!j?0:r[g(r[x]=n,[x,y],j+1),x]=v)):a[n]?g(n):console.log(m))(0)
Try it online!
answered 4 hours ago
ArnauldArnauld
73.9k690310
answered 4 hours ago
ArnauldArnauld
73.9k690310
answered 4 hours ago
ArnauldArnauld
73.9k690310
answered 4 hours ago
ArnauldArnauld
73.9k690310
73.9k690310
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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
5 hours ago
$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
5 hours ago
$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
5 hours ago