34
\$\begingroup\$

You are a medieval overlord tasked with designing a road network between three kingdoms placed on a \$9 \times 9\$ grid. A sample placement of kingdoms might look like this:

Non-commercial use of tileset by douteigami. Thanks!

The kingdoms make the following three demands:

  1. The road network must be connected: for any tile on the road network, you must be able to reach any other tile on the road network by just moving horizontally or vertically only along road tiles.
  2. The kingdoms must be connected: Every kingdom has at least one road tile immediately adjacent horizontally or vertically.
  3. The road network must be thin: No block of \$2\times2\$ squares can all be road tiles.

Both of the following road networks satisfy all three criteria:

    

The following setups fail to satisfy one of the three criteria:

Roads not connected    Kingdoms not connected    2x2 block of road

Challenge

Take input of a \$9\times9\$ grid with three kingdoms in any format. This may be a multiline string with spaces and characters, a list of single-line strings, a list of zeros and ones, a matrix, or any other reasonable format for your language.

As output, add a road network to the input (indicated in any suitable way) that satisfies the above three criteria. Note that:

  • The kingdoms will never be horizontally or vertically adjacent.
  • There is no requirement that your road network be minimal in any sense, just that it follows the three rules.
  • You may not place roads on top of kingdoms.
  • A \$2\times2\$ block where three tiles are road and a single tile is a kingdom is OK; the third restriction only concerns four road tiles.

Test Cases

The test cases use . for an empty space, k for a kingdom and # for a road, but you may take inputs in other formats/use any three distinct characters or integers as described in the previous section.

Input     -> Possible output

.........    .........
....k....    ....k....
.........    ....#....
.........    ....#....
.k....... -> .k####...
.........    .....#...
.....k...    .....k...
.........    .........
.........    .........

k.k......    k#k...... 
.........    .#.......
k........    k#.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.k.......    .k....... 
k........    k#.......
.k.......    .k.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.........    ......... 
.........    .........
k........    k#.......
.........    .#.......
k........ -> k#.......
.........    .#.......
k........    k#.......
.........    .........
.........    .........

........k    ...#####k 
....k....    ...#k....
.........    ...#.....
.........    ...#.....
......... -> ...#.....
.........    ####.....
.........    ...#.....
....k....    ...#k....
.........    ...#.....

.........    ......... 
.........    .........
.........    .........
.........    .........
......... -> .........
.........    .........
k........    k........
.k.......    #k.......
..k......    ##k......

Here's the inputs as a list of list of lists, should you prefer that:

[[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0]]]

Scoring

Shortest code in bytes wins.

\$\endgroup\$
16
  • 4
    \$\begingroup\$ Can't we just always output the grid road with the current criteria? \$\endgroup\$
    – LiefdeWen
    Sep 11 '20 at 8:34
  • 3
    \$\begingroup\$ @Sisyphys Can you provide a test case which will not be valid with the grid roads \$\endgroup\$
    – LiefdeWen
    Sep 11 '20 at 9:14
  • 7
    \$\begingroup\$ May the output consists of the roads without the kingdoms? \$\endgroup\$
    – Arnauld
    Sep 11 '20 at 13:18
  • 2
    \$\begingroup\$ @Arnauld I calculated incorrectly and was just double-checking, \$74326\$ is indeed correct - confirmed by OEIS. The number of discounted cases certainly seemed too big. \$\endgroup\$ Sep 11 '20 at 19:31
  • 4
    \$\begingroup\$ I really like this challenge and your last one! It's fun to try to think of good solutions that are golfable. I'm curious what people come up with. \$\endgroup\$
    – xnor
    Sep 12 '20 at 8:12
12
\$\begingroup\$

JavaScript (ES7),  166 153 149  137 bytes

Slower and even less subtle than my first answer, but also shorter. This simply looks for a path touching all kingdoms without generating any \$2\times 2\$ road blocks.

Takes input as a flat list of 81 entries, with \$0\$ for an empty cell and \$2\$ for a kingdom. Returns another list with \$0\$ for an empty cell, \$1\$ for a road and \$3\$ for a kingdom.

f=(a,X)=>+(z=/.*1,1.{15}1,1|2/.exec(a))?a.some((v,x)=>(a[x]++,(d=(x-X)**2)-1|x/9^X/9&&d-81?0:v?1/X&&v==2?f(a,X):0:f(a,x))||!a[x]--)&&a:!z

Try it online!

How?

We use the regular expression /.*1,1.{15}1,1|2/ to detect either a \$2\times 2\$ block of roads or a remaining kingdom. We get null if nothing is matched, a string that is coerced to NaN by the unary + if a block is matched, or a string that is coerced to \$2\$ if a kingdom is matched.

Because the left and right boundaries are ignored, the condition on the road block is a little more restrictive than it really should, as it will also match something like that:

.........
........X
X.......X
X........
.........

However, we have plenty of room to find a path that will work even without including that kind of pattern.


JavaScript (ES7),  243 236  226 bytes

I'm not very happy with this method, as it heavily relies on a brute-force search. There must exist more elegant and more straightforwards ways of solving this. But it does work!

Expects a matrix with \$0\$ for an empty cell and \$3\$ for a kingdom. Returns another matrix with \$0\$ for an empty cell, \$2\$ for a kingdom and \$4\$ for a road.

f=(m,k)=>(M=m.map((r,y)=>r.map((v,x)=>x^k%8&&x^k%8+2+k/8%8&&y^(q=k/64&7)&&y^q+2+k/512?v:v?3:(X=x,Y=y,1))),g=(X,Y)=>M.map((r,y)=>r.map((v,x)=>(x-X)**2+(y-Y)**2-1?0:v-1?v-3?0:r[x]=2:g(x,y,r[x]=4))))(X,Y)|/1|3/.test(M)?f(m,-~k):M

Try it online!

How?

All puzzles can be solved1 by putting at most 2 horizontal roads and at most 2 vertical roads across the entire grid, either next to or 'over' the kingdoms.

1: this was empirically verified

Example:

example

Given \$k\ge 0\$, we compute:

$$x_0=k\bmod 8$$ $$x_1=x_0+2+(\lfloor k/8\rfloor \bmod 8)$$ $$y_0=\lfloor k/64\rfloor \bmod 8$$ $$y_1=y_0+2+\lfloor k/512\rfloor$$

We put vertical roads at \$x_0\$ and \$x_1\$ and horizontal roads at \$y_0\$ and \$y_1\$. If any value is greater than \$8\$, it's simply ignored.

Because \$x_1\ge x_0+2\$ and \$y_1\ge y_0+2\$, we will never end up we a \$2\times 2\$ block of roads.

Starting from a road cell, we flood-fill the grid to make sure that the two other criteria are fulfilled.

\$\endgroup\$
4
  • \$\begingroup\$ Do you still have the code that you used to verify your method? I'd like it to check a solution of mine \$\endgroup\$
    – user
    Sep 11 '20 at 17:35
  • 1
    \$\begingroup\$ @user I'm not sure it's really going to help you but it looks like that. \$\endgroup\$
    – Arnauld
    Sep 11 '20 at 17:43
  • \$\begingroup\$ Thanks. Good catch on my answer, by the way \$\endgroup\$
    – user
    Sep 11 '20 at 17:52
  • 1
    \$\begingroup\$ @user And here is the (ugly) code I used to check a grid. \$\endgroup\$
    – Arnauld
    Sep 11 '20 at 17:58
8
\$\begingroup\$

Perl 5, 251 317 298 258 bytes

sub f{eval'forP(0..80){forT(0,1){my@r;forK(@_){X=intP/9;Y=P%9;I=intK/9;J=K%9;push@r,X*9+Y andT&&Y-J?Y-=Y<=>J:X-I?X-=X<=>I:Y-J?Y-=Y<=>J:0 whileX.Y neI.J}D="."x81;substrD,$_,1,1for@_;substrD,$_,1,0for@r;3==D=~y/1/1/&&D!~/00.{7}00/&&returnD}}'=~s/[A-Z]/\$$&/gr}

Try it online!

Somewhat ungolfed:

sub f {
  for$p(0..80){              #loop through all possible starting points p,
                             #... the crossroads in the 9x9 board
                             #... from which each road to each kingdom starts
   for$t(0,1){               #for each starting point, try two strategies
                             #...of movement: vertical first or horizontal first
    my @r;                   #init list of road tiles to empty
    for(@_){                 #loop through all the three kingdoms from input
      $x=int$p/9; $y=$p%9;   #x,y = start roads at current starting point p
      $X=int$_/9; $Y=$_%9;   #X,Y = current kingdom

      push @r, $x*9+$y       #register road tile while x,y not yet reached X,Y
      and                          # move x,y towards X,Y
      $t && $y-$Y ? $y-=$y<=>$Y :
            $x-$X ? $x-=$x<=>$X :
            $y-$Y ? $y-=$y<=>$Y :0 # move horizontally or vertically first
                                   # ...depending on current strategy t=0 or 1
        while $x.$y ne $X.$Y   # continue towards current kingdom unless there
    }
    $d='.'x81;                 # init current board string of 81 dots
    substr $d,$_,1,1 for @_;   # put 1's at kingdoms
    substr $d,$_,1,0 for @r;   # put 0's at road tiles
    3==$d=~s/1/1/g             # if board has 3 kingdoms (none overrun by road)
      && $d!~/00.{7}00/        # and current board has no 2x2 road tiles
      && return $d             # then the board is valid and is returned
                               # otherwise try the next of the 81 starting points
  }
 }
}

Can run like this:

@test=( [[1,4], [4,1], [6,5]],
        [[0,0], [0,2], [2,0]],
        [[0,1], [1,0], [2,1]],
        [[2,0], [4,0], [6,0]],
        [[0,8], [1,4], [7,4]],
        [[6,0], [7,1], [8,2]] );
for(@test){
    my @kingdom = map $$_[0]*9+$$_[1], @$_;
    print display( f(@kingdom) );
}
sub display{join('',map join(' ',split//)."\n",pop=~y/10/k#/r=~/.{9}/g).('-'x17)."\n"}

First lines of output: (see 'Try it online' link above for more)

# . . . . . . . .
# # # # k . . . .
# . . . . . . . .
# . . . . . . . .
# k . . . . . . .
# . . . . . . . .
# # # # # k . . .
. . . . . . . . .
. . . . . . . . .
\$\endgroup\$
7
\$\begingroup\$

Brachylog, 97 93 bytes

This actually is fast – brute force in Brachylog! You can't believe how surprised I was when I kept upping the board size. However, this assumes that a road doesn't need to fork. If anyone finds a counterexample – be warned, the other version will not run in time on TIO! :-)

Takes castles as 2, and returns roads as 1.

∧ċ{Ċℕᵐ≤ᵛ⁹}ᵐ{s₂{;.\-ᵐȧᵐ+1∧}ᵈ}ᵇP{,1↻₁}ᵐX&{iiʰgᵗc}ᶠT{ṗʰb}ˢ{,.≠&↰₃ᵐ∈ᵛ}P∧T,X≜bᵍtᵐhᵐḍ₉.¬{s₂\s₂c=₁}∧

Try it online! or Try all testcases!

How the original version works

Many bytes got lost for getting the output into a matrix form, as I didn't find a neat way to go from list of coordinates to its matrix representation. The rough story is:

ċ{l₂ℕᵐ≤ᵛ⁹}ᵐ

We are looking for a path: a list of coordinates, each 0 ≤ X ≤ 9.

s₂ᵇ{\-ᵐȧᵐ+}ᵛ¹hᵐ

And every pair of consecutive coordinates has a distance of 1.

P{,1↻₁}ᵐX

We'll store the path as P, and a version with a 1 before every coordinate as X.

&{iiʰgᵗc}ᶠT

Transform the matrix to a list of [Type, Y, X] and store it as T.

{ṗʰb}ˢ

However, we are only interested in cities for now, so the Type must be prime (that's why they are marked with 2).

C,P≠

The city and path coordinates must all be different to each other.

∧C{;.↰₂1∧}ᵐ∈ᵛP≜

Every city coordinate, shifted by a distance of 1, must be in the path.

∧T,Xbᵍtᵐhᵐḍ₉

To the tiles T append X (the path with Type = 1 prepended), group the tiles by their coordinates and take the last one – so roads will overwrite empty tiles. Reduce the list to the Type and split it into a 9x9 matrix.

.¬{s₂\\s₂c=₁}∧

This is already the output, but make sure there is no 2x2 submatrix of roads.

\$\endgroup\$
6
\$\begingroup\$

R, 248 257 251 264 250 245 bytes

Edit: +9 bytes to fix corner-case (literally; see #1 below), then some golfing, then +13 bytes to fix another corner-case (#2, below), then some more golfing...

function(g,s=setdiff,S=0:8%/%3-1,`^`=`%in%`){k=which(g>0,T);v=k[,1];w=k[,2]
g[r<-max(s(v+S,v)%%9),]=g[,c<-max(s(w+S,w)%%9)]=1
for(i in 1:3){x=v[i];y=w[i]
if(!(x^(r+S)|y^(c+S)))`if`(F|x^v[-i],g[x:r,y--y^w[-i]**(y<2)]<-1,g[x,y:c]<-F<-1)}
g[k]=2;g}

Try it online!

This is a 'constructive' rather than 'brute-force' solution: we build a single set of roads in such a way that the conditions will be satisfied, rather than trying-out various possibilities and checking whether-or-not we've violated one or more of the conditions.

Input is a matrix with non-zero elements representing the three kingdoms. Output is a matrix with roads represented by 1, and the kingdoms by 2.

How?

First we construct 'main' roads in the form of a '+' from north-to-south and from east-to-west across empty elements of the grid, and touching at least one of the 3 kingdoms (take care: corner-case 2 was when all kingdoms are in edge rows/columns, so we need to make sure that our 'adjacent' roads are still in the grid).
Now there at most 2 kingdoms left that still need to be connected.
For each kingdom that isn't already connected to the 'main' roads, we construct an 'access road' from the kingdom to one of the 'main' roads.
We need to be careful that the 'access road' won't be split by one of the kingdoms: therefore, we check whether the unconnected kingdom is on the same row as another kingdom, and, if it isn't, we construct an east-west access road. If the unconnected kingdom shares its row with another kingdom, we check if it also shares its column: if not, we build a north-south access road. If it does (and it also shared a row), then we can be sure that the adjacent columns are empty, so we build a north-south access road in a column adjacent to the kingdom (corner case 1: for this, we need to check if the kingdom is in column 1: if it is, we build the access road in column 2, otherwise in column y-1).

Here are the roads (orange) built for each of the 6 test cases (kingdoms indicated in whiteish):

enter image description here

Commented code:

function(g,                     # g=input grid with kingdoms
 s=setdiff,                     # s=alias to 'setdiff()' function
 S=0:8%/%3-1,                   # S=defines adjacent indices 
 `^`=`%in%`){                   # ^=alias to '%in%' function
 k=which(g>0,T)                 # k=get indices of the kingdoms
 v=k[,1];w=k[,2]                # v=x-coordinates, w=y-coordinates of kingdoms
 r<-max(s(v+S,v)%%9)            # r=empty row next-to a kingdom
                                # (elements of v±1 that are different to v, avoiding zero and >8)
 c<-max(s(w+S,w)%%9)            # c=first empty column next-to a kingdom
 g[r,]=g[,c]=1                  # build the 'main' roads
 for(i in 1:3){                 # loop through each of the 3 kingdoms:
  x=v[i];y=w[i]                 #  (x,y=x- and y-coordinates of current kingdom)
  if(!(xin%(r+S)|y%in%(c+S)))   #  if x or y are not adjacent to r or s 
                                #  (so this kingdom isn't connected to the 'main' roads)
   `if`(F|x%in%v[-i],           #  if x is shared with the row of another kingdom, or
                                #  'F' indicates that we've already built an east-west 'access road':
    g[x:r,y                     #   build an north-south 'access road' from x to r
    -                           #   (either on the same row, y, or on an adjacent row
    (-(y%in%w[-i]))**(y<2)<-1,  #   if y is shared with the col of another kingdom);
    g[x,y:c]<-F<-1)             #  otherwise build an east-west 'access road' from y to c
  }
 g[k]=2;                        # mark the kingdoms on the grid
 g                              # and return the grid
}
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 196 bytes

≔E⁹SθF⁹F⌕A§θιk⊞υ⟦ικ⟧FυF⁴F⁴«θJ§ι¹§ι⁰M✳⊗λ≔⁰ζW⁼KK.«✳⊗κ#≦⊕ζ»≔ωηF⁻υ⟦ι⟧F⁴F⁴«J§μ¹§μ⁰M✳⊗ξ≔KD⁹✳⊗νδM⌕δ#✳⊗ν¿∧№δ#¬№…δ⌕δ#¦k¿⁼⌕υμ¬⌕υι≔⟦μⅈⅉν⌕δ#ξ⟧η¿∧η⊖ΣE⟦ⅈⅉ⟧↔⁻π§η⊕ρ≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε»⎚»θFε«J⊟§ι⁰⊟§ι⁰M✳⊗⊟ι✳⊗⊟ι×#⊟ι

Try it online! Link is to verbose version of code. Works by drawing a line from a square adjacent to one kingdom to the edge of the grid, then drawing lines from squares adjacent to each of the other kingdoms to intersect the first line, except not allowing the two lines to be exactly one row apart. Explanation:

≔E⁹Sθ

Input the grid.

F⁹F⌕A§θιk⊞υ⟦ικ⟧

Locate all of the kingdoms.

FυF⁴F⁴«

Loop through each direction from each square adjacent to each kingdom.

θ

Print the grid.

J§ι¹§ι⁰M✳⊗λ

Jump to the selected kingdom and move to the selected adjacent square.

≔⁰ζ

Count the number of empty squares.

W⁼KK.«

Repeat while the current square is empty...

✳⊗κ#

... mark it with a #...

≦⊕ζ

... and increment the count.

»≔ωη

Start with no line for the second kingdom.

F⁻υ⟦ι⟧

Loop through the remaining kingdoms.

F⁴F⁴«

Loop through each direction from each square adjacent to this kingdom.

J§μ¹§μ⁰M✳⊗ξ

Jump to this kingdom and move to the selected adjacent square.

≔KD⁹✳⊗νδ

Grab the line in the selected direction.

M⌕δ#✳⊗ν

Move to where the line would intersect if it was valid.

¿∧№δ#¬№…δ⌕δ#¦k

Does this line cross the first kingdom's line? If so:

¿⁼⌕υμ¬⌕υι

If this is the second kingdom's line...

≔⟦μⅈⅉν⌕δ#ξ⟧η

... then save this as its line.

¿∧η⊖ΣE⟦ⅈⅉ⟧↔⁻π§η⊕ρ

Otherwise if the second kingdom's line does not intersect exactly one square away...

≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε

... then save this as a solution.

»⎚

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

»θ

Print the grid.

Fε«

Loop over the kingdoms in the last solution found.

J⊟§ι⁰⊟§ι⁰M✳⊗⊟ι

Jump to the position of the kingdom and move to the found adjacent square.

✳⊗⊟ι×#⊟ι

Print the found line.

Note that this code tries all combinations of kingdoms and directions. It's probably unnecessary to try them all, for instance I think it's likely that you can always draw a line up from one of three sides of the bottommost kingdom and connecting the other two kingdoms to that line. If this is true then the code can be simplified, currently saving 10 24 bytes: Try it online! Link is to verbose version of code. Explanation:

≔E⁹SθF⁹F⌕A§θιk⊞υ⟦ικ⟧

Input the grid and locate all of the kingdoms.

≔⊟υτ

Get the bottommost kingdom.

F³«

Check the squares to its right, above and left.

θJ§τ¹§τ⁰M✳⊗ι

Print the grid and jump to the selected adjacent square.

≔⁰ζW⁼KK.«↑#≦⊕ζ»

Draw a line up as far as possible.

≔ωη

Start with no line for the second kingdom.

FυF⁴F⁴«

Loop over the other two kingdoms, considering all lines for all four adjacent squares. (I could just do left and right lines but it turns out that all lines is golfier.)

J§κ¹§κ⁰M✳⊗μ

Jump to this kingdom's adjacent square.

≔KD⁹✳⊗λδ

Grab the line in the selected direction.

¿∧№δ#¬№…δ⌕δ#¦k

Does this line cross the first kingdom's line? If so:

¿⌕υκ«

If this is the third kingdom's line, then...

¿∧η⊖↔⁻ⅉ§η¹

... if the second kingdom's line isn't exactly one row away, then...

≔⟦⟦τ¹ζι⟧η⟦κλ⌕δ#μ⟧⟧ε

... save this as a solution.

»≔⟦κⅉλ⌕δ#μ⟧η

Otherwise for the second kingdom save this as its line.

»⎚

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

»θFε«J⊟§ι⁰⊟§ι⁰M✳⊗⊟ι✳⊗⊟ι×#⊟ι

Print the solution.

\$\endgroup\$
12
  • \$\begingroup\$ I believe the short version doesn't work in this case. (had to de-verbosify to fit the link into a comment.) :-) \$\endgroup\$
    – xash
    Sep 12 '20 at 11:46
  • \$\begingroup\$ @xash Ugh, that might be a symptom of a flaw in the code of the main version too, but it's hidden there because it tries other variations which mitigate the issue. \$\endgroup\$
    – Neil
    Sep 12 '20 at 13:06
  • \$\begingroup\$ @xash Actually there's a simpler pattern that thwarts my short version, just put two kingdoms in the top and bottom left corners and the third one column to the right in the middle. \$\endgroup\$
    – Neil
    Sep 12 '20 at 13:13
  • \$\begingroup\$ @xash Not only have I fixed both those flaws but I managed to golf the solution down at the same time! \$\endgroup\$
    – Neil
    Sep 12 '20 at 16:21
  • \$\begingroup\$ @Neil - a link is too long to fit into a comment, but the pattern toprow=....x... nextrow=.....x.. thirdrow=....x... seems to fail for your '17-bytes-saved' version. \$\endgroup\$ Sep 12 '20 at 16:37
3
\$\begingroup\$

Perl 5 -00ap, 114, 109 bytes

$_|=substr'iiiiiiiii
iaiaiaiai
'x5,10*!(grep/k/,@F[1,7]),90;1while s/(?<!i.{9})(?<!ii)i(?!iii|.{9}i.{9}i)/a/s

6 bytes saved thanks to @DomHastings, but 1 lost to fix a case.

Try it online!

Another perl answer, with a different approach, I've also upvoted the other perl answer.

I had to fix several times because of some cases (in addition to those of the question) for which it didn't work.

Solution

The idea is to start from the grid of roads which almost works and fix for the different cases. If there's a kingdom in the square region of os rows: 1 or 7 (after golfing), the grid is aligned on (0,0), otherwise on (0,1)

.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #
.........      # # # # #      #########
.........  ?   #########  :   # # # # #
.........      # # # # #      #########
.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #

Then the remaining roads can be fixed by removing squares when all the squares in the four directions, empirically (haven't a proof yet), at a distance of 3 (right), 2 (left, bottom) or 1 (up), are not a road (or are out of the map).

  ?
??#???
  ?
  ?

Justification

Looking for a counter-example. Starting from a grid of roads and putting kingdoms so that road a kingdom could be disconnected.

Because of the symmetries only the first corner is shown. For grid 1, the only case which causes a problem:

k.k###
. # # 
k#####
# # # 

and as there is no kingdom in the region described in solution it can't occur.

For grid 2, one example but other configurations exist:

k # #
..k###
k # #
######

One of the 2 kingdoms that cut the roads must be in the region described in solution, so this can't occur.

\$\endgroup\$
5
  • \$\begingroup\$ Nice answer! You can save a few bytes with a longer literal instead of the string repetition though: Try it online! \$\endgroup\$ Sep 14 '20 at 21:05
  • \$\begingroup\$ I haven't looked at your code, just the justification: you haven't mentioned the case where the top left hand corner is: ..k/.k#/k## (assuming . means "a bad road"). This has a disconnected road. You know kingdoms can be diagonally adjacent? \$\endgroup\$ Sep 17 '20 at 11:32
  • \$\begingroup\$ @SteveBennett, "Justification" is about disconnected kingdmons but in your case they are not disconnected. Your point is about removing the remaining roads and i wrote in "Solution" that i haven't a proof for all cases, but found empirically it works, can be checked here. I understand this may not be clear enough. \$\endgroup\$ Sep 17 '20 at 11:49
  • \$\begingroup\$ @SteveBennett, What i mean about 4 direction is that for each direction we check that all the corresponding number of squares are roads, and if for no direction the condition is met the road is removed. And this process is repeated until no more roads are removed. \$\endgroup\$ Sep 17 '20 at 11:56
  • \$\begingroup\$ Ah yep, that makes sense. \$\endgroup\$ Sep 17 '20 at 23:31
2
\$\begingroup\$

J, 139 127 bytes

Starting from [0,1] or [0,2] forming two grids

#XX#… and .X.#…
#.#.…     ####…
####…     .#.#…
#.#.…     ####…

at least one of the 3 attempts will succeed (based on a hacked together J script.) For some byte saving, this tries some more grids:

+u({.@\:#@~.@,"3)0|:(d|.!.0]*1+i.@$)*"2/u=:(}:"2}:"{d|.10$#:1023 682)(2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)(9 9$!.1]1 2 2)*1=+)"2]

Try it online!

How it roughly works

There should still be some bytes golfable. But for now:

(}:"2}:"{d|.10$#:1023 682)

The grid – first as a 10x10 matrix so we can easily shift via the 4 directions, we'll define later. Drawback: we have to cut it down to 9x9. Now, for every grid:

(9 9$!.1]1 2 2)*1=+

Whenever a castle is on a road, set the tile to empty. Also, give the roads at [0,1] and [0,2] value 2 (if they exist). From there we'll find the biggest connected road network now:

 2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)

Until the map does not change: shift it around and give each road a new road number: the maximum of the current number and the ones of the connected roads (but keep 0 as 0). Finally, keep the roads marked with 2 – those are connected to the starting nodes

(d|.!.0]*1+i.@$)*"2/

Now to check that all castles are connected: Take the original input, and shift it into the 4 directions. Give each castle a unique number.

 +u({.@\:#@~.@,"3)0|:

Sort the grids by the number of connected castle (the unique numbers after the shifted castle numbers are multiplied with the 1's of the road network.) Take the best one, add the castles back in – et voilà, a kingdom for you!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 67 bytes

F⁹F⌕ASk⊞υ⟦ικ⟧B⁹ψF⁹F⁹«Jκι¿¬№﹪⟦ικ⟧²﹪ΠEυΠ⊕λ² »Fυ«J⊟ι⊟ιk»F³F³«J⁺³κ⁺³ι¤#

Try it online! Link is to verbose version of code. Outputs using spaces for empty tiles, but anything except k serves as empty on input. This is an entirely different approach to my previous answer, so I thought it deserved a separate answer. It relies on the observation that the grid with 16 holes solves all problems except those with three kingdoms near the corners. The one thing those problems have in common is that all three kingdoms lie on even rows and columns. In such cases the grid is offset diagonally resulting in a grid with 25 holes. Explanation:

F⁹F⌕ASk⊞υ⟦ικ⟧

Read in the grid and save the coordinates of the kingdoms.

B⁹ψ

Prepare an empty area for the grid.

F⁹F⁹

Loop through each square on the grid.

«Jκι

Jump to that position.

¿¬№﹪⟦ικ⟧²﹪ΠEυΠ⊕λ² »

If both the row and column have the same parity as the bitwise OR of all of the coordinates, then place an explicit space at that position, preventing it from being flood filled. Since I don't have a good way of taking the bitwise OR of a list, I use De Morgan's laws to check whether neither row nor column contain have the parity of the bitwise AND of the complement of the list, noting that for the purposes of parity, product is equivalent to bitwise AND and increment is equivalent to complement.

Fυ«J⊟ι⊟ιk»

Place the kingdoms on the grid.

F³F³«J⁺³κ⁺³ι¤#

Try to flood fill starting at each of the nine centre squares. This guarantees that the result is a single connected road. It's not possible for only three kingdoms to disconnect the centre of the grid, so this is always safe.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.