20
3
This challenge is inspired by this app. The test cases are borrowed from that app.
This is a fastest-code challenge, where the objective is to solve the largest test cases in the least amount of time. There are provided some smaller test cases, so that people might test their algorithms faster.
You'll be given a square input grid, of dimensions n-by-n where 9 <= n <= 12. This grid will be divided into n areas, where the cells of each area has a unique identifiers (I'll use lower case letters from a-l in the the text here, but you may choose whatever you like, for instance integers 1-12).
The input may look like this (optional input format):
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
Or, easier to visualize:
Challenge:
You are to place 2*n trees in this park, according to the following rules:
- There shall be exactly 2 trees per column, and 2 trees per row
- All areas shall have exactly 2 trees.
- No trees can be adjacent to another tree, vertically, horizontally or diagonally
The solution to the layout above is:
Note: There is only one solution to each puzzle
Additional rules:
- The input and output formats are optional
- The output might for instance be a list of indices, a grid with 1/0 indicating if there's a tree in that position, or a modified version of the input where the trees are indicated
- The execution time must be deterministic
- The program must finish withing 1 minute at @isaacg's computer
- Specs: 4 CPUs, i5-4300U CPU @ 1.9 GHz, 7.5G of RAM.
- In case your program can't solve the two largest test case in one minute each then the time for the second largest (n=11) will be your score. You'll lose against a solution that solves the largest case.
Test cases:
I might edit this list if submissions seems to be customized to fit these test cases.
12-by-12:
--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk
11-by-11:
--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii
10-by-10
--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd
9-by-9
--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
"The input and output formats are optional, but should be the same" What does that mean? Can't I output a list of lists containing 1s and 0s for trees and non trees without caring about outputting the areas? – Fatalize – 2017-06-23T13:32:22.067
@Fatalize, edited. I think outputting a list of indices or a grid with 1/0 as you suggest is a good idea. – Stewie Griffin – 2017-06-23T13:35:36.500
1Information (if I calculate correctly): There are 3647375398569086976 configurations to put 24 trees in a 12*12 grid satisfy only (1):
There shall be exactly 2 trees per column, and 2 trees per row
, so a brute-force is probably impossible. – user202729 – 2017-06-23T14:13:37.703"shouldn't be a big problem": I personally think that it is. My current implementation solves the first test case in ~150ms and the 3rd one in 5s but fails to solve the last one (which is 'only' 11x11) in any reasonable amount of time. It would probably require some much more aggressive forward pruning -- and therefore a significant amount of additional code -- to complete within 1 minute. – Arnauld – 2017-06-23T16:25:22.863
1@Arnauld, I changed the maximum to 11 since that's the largest test case. You may post your solution (as a valid, competing submission), but it will not win if someone posts a solution that solves all test cases, regardless of code length. Fair? – Stewie Griffin – 2017-06-23T16:57:09.303
Stewie, we need bigger test cases. We have multiple answers in the smaller numbers of milliseconds. – isaacg – 2017-06-26T06:26:40.030
@isaacg, I'm not sure I'm able to make larger test cases that are guaranteed to have only one unique solution while not being trivial :/ I'll see what I can come up with... Suggestions are appreciated. – Stewie Griffin – 2017-06-26T08:25:03.563
Stewie, you might be able to make use of the solvers that have been made to check for uniqueness. Ask the people who made them if they can be adapted that way. Knowing whether something was unique would probably help composition. – isaacg – 2017-06-26T08:32:19.153
Do you think 20x20 is a good fit? (Still not sure if I can make one, but I'll try :) ) – Stewie Griffin – 2017-06-26T08:47:09.170