Dig a border trench

Question

Background: Too many illegal immigrants from Blandia are crossing the border to Astan. The emperor of Astan has tasked you with digging a trench to keep them out, and Blandia must pay for the expenses. Since all typists have been furloughed until the trench is arranged, your code must be as short as possible.^_*

Task: Given a 2D map of the border between Astan and Blandia, make the Blands pay (with land) for a border trench.

For example: With Astanian cells marked A, Blandic cells marked B and trench cells marked + (the map frames are only for clarity):

┌──────────┐ ┌──────────┐
│AAAAAAAAAA│ │AAAAAAAAAA│
│ABAAAAAABA│ │A+AAAAAA+A│
│ABBBAABABA│ │A+++AA+A+A│
│ABBBAABABA│ │A+B+AA+A+A│
│ABBBBABABA│→│A+B++A+A+A│
│ABBBBABBBB│ │A+BB+A++++│
│ABBBBABBBB│ │A+BB+A+BBB│
│ABBBBBBBBB│ │A+BB+++BBB│
│BBBBBBBBBB│ │++BBBBBBBB│
└──────────┘ └──────────┘

Details: The map will have at least three rows and three columns. The top row will be entirely Astanian and the bottom row will be entirely Blandic.
 You may use any three values to represent Astanian territory, Blandic territory, and border trench, as long as input and output are consistent.

Automaton formulation: A Blandic cell with at least one Astanian cell in its Moore neighbourhood becomes a border trench cell.

Test cases

[
  "AAAAAAAAAA",
  "ABAAAAAABA",
  "ABBBAABABA",
  "ABBBAABABA",
  "ABBBBABABA",
  "ABBBBABBBB",
  "ABBBBABBBB",
  "ABBBBBBBBB",
  "BBBBBBBBBB"
]

becomes:

[
  "AAAAAAAAAA",
  "A+AAAAAA+A",
  "A+++AA+A+A",
  "A+B+AA+A+A",
  "A+B++A+A+A",
  "A+BB+A++++",
  "A+BB+A+BBB",
  "A+BB+++BBB",
  "++BBBBBBBB"
]

---

[
  "AAA",
  "AAA",
  "BBB"
]

becomes:

[
  "AAA",
  "AAA",
  "+++"
]

---

[
  "AAAAAAAAAA",
  "AAAABBBAAA",
  "AAAABBBAAA",
  "AAAABBBAAA",
  "AAAAAAAAAA",
  "BBBBBBABBB",
  "BBBBBBAABB",
  "BBBAAAAABB",
  "BBBBBBBBBB"
]

becomes:

[
  "AAAAAAAAAA",
  "AAAA+++AAA",
  "AAAA+B+AAA",
  "AAAA+++AAA",
  "AAAAAAAAAA",
  "++++++A+++",
  "BB++++AA+B",
  "BB+AAAAA+B",
  "BB+++++++B"
]

---

^{_{* DISCLAIMER: ANY RESEMBLANCE TO ACTUAL GEOPOLITICS IS PURELY COINCIDENTAL!}}

Answer 1

Wolfram Language (Mathematica), 15 bytes

2#-#~Erosion~1&

Try it online!

Or (39 bytes):

MorphologicalPerimeter[#,Padding->1]+#&

Try it online!

What else would we expect from Mathematica? Characters used are {Astan -> 0, Blandia -> 1, Trench -> 2}.

Answer 2

MATL, 11 8 bytes

Inspired by @flawr's Octave answer and @lirtosiast's Mathematica answer.

EG9&3ZI-

The input is a matrix with Astan represented by 0 and Blandia by 1. Trench is represented in the output by 2.

Try it online!

How it works

E       % Implicit input. Multiply by 2, element-wise
G       % Push input again
9       % Push 9
&3ZI    % Erode with neighbourhood of 9 elements (that is, 3×3) 
-       % Subtract, element-wise. Implicit display

Answer 3

JavaScript (ES7),  84  82 bytes

Saved 2 bytes thanks to @Shaggy

Takes input as a matrix of integers, with \$3\$ for Astan and \$0\$ for Blandia. Returns a matrix with the additional value \$1\$ for the trench.

a=>(g=x=>a.map(t=(r,Y)=>r.map((v,X)=>1/x?t|=(x-X)**2+(y-Y)**2<v:v||g(X,y=Y)|t)))()

Try it online!

Commented

a => (                      // a[] = input matrix
  g = x =>                  // g = function taking x (initially undefined)
    a.map(t =               //   initialize t to a non-numeric value
      (r, Y) =>             //   for each row r[] at position Y in a[]:
      r.map((v, X) =>       //     for each value v at position X in r[]:
        1 / x ?             //       if x is defined (this is a recursive call):
          t |=              //         set the flag t if:
            (x - X) ** 2 +  //           the squared Euclidean distance
            (y - Y) ** 2    //           between (x, y) and (X, Y)
            < v             //           is less than v (3 = Astan, 0 = Blandia)
        :                   //       else (this is the initial call to g):
          v ||              //         yield v unchanged if it's equal to 3 (Astan)
          g(X, y = Y)       //         otherwise, do a recursive call with (X, Y) = (x, y)
          | t               //         and yield the flag t (0 = no change, 1 = trench)
      )                     //     end of inner map()
    )                       //   end of outer map()
)()                         // initial call to g

Answer 4

K (ngn/k), 23 bytes

{x+x&2{++/'3'0,x,0}/~x}

Try it online!

uses 0 1 2 for "AB+"

{ } function with argument x

~ logical not

2{ }/ twice do

• 0,x,0 surround with 0-s (top and bottom of the matrix)

• 3' triples of consecutive rows

• +/' sum each

• + transpose

x& logical and of x with

x+ add x to

Answer 5

APL (Dyalog Unicode), 11 bytes^SBCS

⊢⌈{2∊⍵}⌺3 3

this is based on @dzaima's 12-byte solution in chat. credit to @Adám himself for thinking of using ∊ in the dfn, and to @H.PWiz for reminding us to use the same encoding for input and output

Try it online!

represents 'AB+' as 2 0 1 respectively

{ }⌺3 3 apply a function to each overlapping 3×3 region of the input, including regions extending 1 unit outside the matrix, padded with 0s

2∊⍵ is a 2 present in the argument? return a 0/1 boolean

⊢⌈ per-element max of that and the original matrix

Answer 6

PowerShell, 220 bytes

It's not as small as the other submissions, but I thought I'd add it for reference. [FORE!]

function m($i,$m){($i-1)..($i+1)|?{$_-in0..$m}}
$h=$a.count-1;$w=$a[0].length-1
foreach($i in 0..$h){-join$(foreach($j in 0..$w){if ($a[$i][$j]-eq'B'-and($a[(m $i $h)]|?{$_[(m $j $w)]-match'A'})){'+'}else{$a[$i][$j]}})} 

Try it online!

Answer 7

Octave, 37 31 26 bytes

This function performs a morphological erosion on the Astan (1-b) part of the "image" using conv2 imerode, and then uses some arithmetic to make all three areas different symbols. Thanks @LuisMendo for -5 bytes!

@(b)2*b-imerode(b,ones(3))

Try it online!

Answer 8

J, 28 bytes

>.3 3(2 e.,);._3(0|:@,|.)^:4

Try it online!

'AB+' -> 2 0 1

Inspired by ngn's APL solution. 12 bytes just to pad the matrix with zeroes...

Answer 9

Charcoal, 20 bytes

≔⪫θ⸿θＰθＦθ⎇∧№ＫＭA⁼Bι+ι

Try it online! Link is to verbose version of code. Explanation:

≔⪫θ⸿θ

Join the input array with carriage returns rather than the usual newlines. This is needed so that the characters can be printed individually.

Ｐθ

Print the input string without moving the cursor.

Ｆθ

Loop over each character of the input string.

⎇∧№ＫＭA⁼Bι

If the Moore neighbourhood contains an A, and the current character is a B...

+

... then overwrite the B with a +...

ι

... otherwise print the current character (or move to the next line if the current character is a carriage return).

Answer 10

JavaScript, 85 bytes

Threw this together late last night and forgot about it. Probably still room for some improvement somewhere.

Input and output is as an array of digit arrays, using 3 for Astan, 0 for Blandia & 1 for the trench.

a=>a.map((x,i)=>x.map((y,j)=>o.map(v=>o.map(h=>y|=1&(a[i+v]||x)[j+h]))|y),o=[-1,0,1])

Try it online (For convenience, maps from & back to the I/O format used in the challenge)

Answer 11

Javascript, 126 118 bytes

_=>_.map(x=>x.replace(/(?<=A)B|B(?=A)/g,0)).map((x,i,a)=>[...x].map((v,j)=>v>'A'&&(a[i-1][j]<v|(a[i+1]||x)[j]<v)?0:v))

Pass in one of the string arrays from the question, and you'll get an array of strings character arrays (thanks @Shaggy!) out using 0 for the trench. Can probably be golfed more (without switching over to numerical arrays), but I can't think of anything at the moment.

Answer 12

Retina 0.8.2, 92 80 bytes

(?<=¶(.)*)B(?=.*¶(?<-1>.)*(?(1)_)A|(?<=¶(?(1)_)(?<-1>.)*A.*¶.*))
a
iT`Ba`+`.?a.?

Try it online! Loosely based on my answer to Will I make it out in time? Explanation: Any Bs immediately above or below As are turned into as. This then reduces the problem to checking Bs to the left or right of As or as. The as themselves also need to get turned into +s of course, but fortunately the i flag to T only affects the regex match, not the actual transliteration, so the As remain unaffected.

Answer 13

C# (Visual C# Interactive Compiler), 187 bytes

a=>a.Select((b,i)=>b.Select((c,j)=>{int k=0;for(int x=Math.Max(0,i-1);x<Math.Min(i+2,a.Count);x++)for(int y=Math.Max(0,j-1);y<Math.Min(j+2,a[0].Count);)k+=a[x][y++];return k>1&c<1?9:c;}))

Instead of chaining Take()s, Skip()s, and Select()s, instead this uses double for loops to find neighbors. HUGE byte decrease, from 392 bytes to 187. Linq isn't always the shortest!

Try it online!

Answer 14

Java 8, 169 145 bytes

m->{for(int i=m.length,j,k;i-->0;)for(j=m[i].length;j-->0;)for(k=9;m[i][j]==1&k-->0;)try{m[i][j]=m[i+k/3-1][j+k%3-1]<1?2:1;}catch(Exception e){}}

-24 bytes thanks to @OlivierGrégoire.

Uses 0 instead of A and 1 instead of B, with the input being a 2D integer-matrix. Modifies the input-matrix instead of returning a new one to save bytes.

The cells are checked the same as in my answer for the All the single eights challenge.

Try it online.

Explanation:

m->{                            // Method with integer-matrix parameter and no return-type
  for(int i=m.length,j,k;i-->0;)//  Loop over the rows
    for(j=m[i].length;j-->0;)   //   Inner loop over the columns
      for(k=9;m[i][j]==1&       //    If the current cell contains a 1:
          k-->0;)               //     Inner loop `k` in the range (9, 0]:
        try{m[i][j]=            //      Set the current cell to:
             m[i+k/3-1]         //       If `k` is 0, 1, or 2: Look at the previous row
                                //       Else-if `k` is 6, 7, or 8: Look at the next row
                                //       Else (`k` is 3, 4, or 5): Look at the current row
              [j+k%3-1]         //       If `k` is 0, 3, or 6: Look at the previous column
                                //       Else-if `k` is 2, 5, or 8: Look at the next column
                                //       Else (`k` is 1, 4, or 7): Look at the current column
               <1?              //       And if this cell contains a 0:
                  2             //        Change the current cell from a 1 to a 2
                 :              //       Else:
                  1;            //        Leave it a 1
        }catch(Exception e){}}  //      Catch and ignore ArrayIndexOutOfBoundsExceptions
                                //      (try-catch saves bytes in comparison to if-checks)

Answer 15

Perl 5, 58 46 bytes

$m=($n=/$/m+"@+")-2;s/A(|.{$m,$n})\KB|B(?=(?1)A)/+/s&&redo

TIO

-12 bytes thanks to @Grimy

/.
/;s/A(|.{@{-}}.?.?)\KB|B(?=(?1)A)/+/s&&redo

TIO

• -p like -n but print also
• -00 paragraph mode
• to get the width-1 /.\n/ matches the last character of first line
• @{-} special array the position of start of match of previous matched groups, coerced as string (first element)
• s/../+/s&&redo replace match by + while matches
  • /s flag, so that . matches also newline character
• A(|.{@{-}}.?.?)\KB matches
  • AB or A followed by (width-1) to (width+1) characters folowed by B
  • \K to keep the left of B unchanged
• B(?=(?1)A),
  • (?1) dirverting recursive, to reference previous expression (|.{$m,$o})
  • (?=..) lookahead, to match without consuming input

Answer 16

05AB1E, 29 bytes

_2FIн¸.øVgN+FYN._3£})εøO}ø}*Ā+

Matrices aren't really 05AB1E's strong suit (nor are they my strong suit).. Can definitely be golfed some more, though.
Inspired by @ngn's K (ngn/k) answer, so also uses I/O of a 2D integer matrix with 012 for AB+ respectively.

Try it online. (The footer in the TIO is to pretty-print the output. Feel free to remove it to see the matrix output.)

Explanation:

_                # Inverse the values of the (implicit) input-matrix (0→1 and 1→0)
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #   → [[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0]]
 2F              # Loop `n` 2 times in the range [0, 2):
   Iн            #  Take the input-matrix, and only leave the first inner list of 0s
                 #   i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]] → [0,0,0,0]
     ¸           #  Wrap it into a list
                 #   i.e. [0,0,0,0] → [[0,0,0,0]]
      .ø         #  Surround the inverted input with the list of 0s
                 #   i.e. [[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0]] and [0,0,0,0]
                 #    → [[0,0,0,0],[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0]]
        V        #  Pop and store it in variable `Y`
   g             #  Take the length of the (implicit) input-matrix
                 #   i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]] → 4
    N+           #  Add `n` to it
                 #   i.e. 4 and n=0 → 4
                 #   i.e. 4 and n=1 → 5
      F          #  Inner loop `N` in the range [0, length+`n`):
       Y         #   Push matrix `Y`
        N._      #   Rotate it `N` times towards the left
                 #    i.e. [[0,0,0,0],[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0]] and N=2
                 #     → [[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,1]]
            3£   #   And only leave the first three inner lists
                 #    i.e. [[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,1]]
                 #     → [[1,0,1,1],[1,0,0,0],[0,0,0,0]]
              }  #  After the inner loop:
    )            #  Wrap everything on the stack into a list
                 #   → [[[0,0,0,0],[1,1,1,1],[1,0,1,1]],[[1,1,1,1],[1,0,1,1],[1,0,0,0]],[[1,0,1,1],[1,0,0,0],[0,0,0,0]],[[1,0,0,0],[0,0,0,0],[0,0,0,0]]]
     €ø          #  Zip/transpose (swapping rows/columns) each matrix in the list
                 #   → [[[0,1,1],[0,1,0],[0,1,1],[0,1,1]],[[1,1,1],[1,0,0],[1,1,0],[1,1,0]],[[1,1,0],[0,0,0],[1,0,0],[1,0,0]],[[1,0,0],[0,0,0],[0,0,0],[0,0,0]]]
       O         #  And take the sum of each inner list
                 #   → [[2,1,2,2],[3,1,2,2],[2,0,1,1],[1,0,0,0]]
        ø        #  Zip/transpose; swapping rows/columns the entire matrix again
                 #   i.e. [[2,1,2,2],[3,1,2,2],[2,0,1,1],[1,0,0,0]]
                 #    → [[2,3,2,1],[1,1,0,0],[2,2,1,0],[2,2,1,0]]
               } # After the outer loop:
                 #   i.e. [[3,5,5,4,2],[4,6,5,4,2],[2,3,2,2,1],[1,1,0,0,0]]
  *              # Multiple each value with the input-matrix at the same positions,
                 # which implicitly removes the trailing values
                 #  i.e. [[3,5,5,4,2],[4,6,5,4,2],[2,3,2,2,1],[1,1,0,0,0]]
                 #   and [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #    → [[0,0,0,0],[0,1,0,0],[0,2,1,0],[2,2,1,0]]
   Ā             # Truthify each value (0 remains 0; everything else becomes 1)
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,2,1,0],[2,2,1,0]]
                 #   → [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,0,0]]
    +            # Then add each value with the input-matrix at the same positions
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,0,0]]
                 #   and [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #    → [[0,0,0,0],[0,2,0,0],[0,2,2,2],[2,2,1,1]]
                 # (and output the result implicitly)

Answer 17

PowerShell, 86 80 bytes

$p="(.?.?.{$(($args|% i*f '
')-1)})?"
$args-replace"(?s)(?<=A$p)B|B(?=$p`A)",'+'

Try it online!

The map is a string with newlines. This script replaces B to + with regexp (?<=A(.?.?.{$MapWidth-1})?)B|B(?=(.?.?.{$MapWidth-1})?A).

Less golfed Test script:

$f = {
$l=($args|% indexOf "`n")-1
$p="(.?.?.{$l})?"
$args-replace"(?s)(?<=A$p)B|B(?=$p`A)",'+'
}

@(
,(@"
AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB
"@,@"
AAAAAAAAAA
A+AAAAAA+A
A+++AA+A+A
A+B+AA+A+A
A+B++A+A+A
A+BB+A++++
A+BB+A+BBB
A+BB+++BBB
++BBBBBBBB
"@)
,(@"
AAA
AAA
BBB
"@,@"
AAA
AAA
+++
"@)
,(@"
AAAAAAAAAA
AAAABBBAAA
AAAABBBAAA
AAAABBBAAA
AAAAAAAAAA
BBBBBBABBB
BBBBBBAABB
BBBAAAAABB
BBBBBBBBBB
"@,@"
AAAAAAAAAA
AAAA+++AAA
AAAA+B+AAA
AAAA+++AAA
AAAAAAAAAA
++++++A+++
BB++++AA+B
BB+AAAAA+B
BB+++++++B
"@)
) | % {
    $map,$expected = $_
    $result = &$f $map
    $result-eq$expected
    #$result # uncomment this line to display results
}

Output:

True
True
True

Answer 18

Ruby, 102 bytes

->a{a+=?.*s=a.size
(s*9).times{|i|a[j=i/9]>?A&&a[j-1+i%3+~a.index($/)*(i/3%3-1)]==?A&&a[j]=?+}
a[0,s]}

Try it online!

input/output as a newline separated string

Answer 19

Python 2, 123 119 bytes

lambda m:[[[c,'+'][c=='B'and'A'in`[x[j-(j>0):j+2]for x in m[i-(i>0):i+2]]`]for j,c in e(l)]for i,l in e(m)];e=enumerate

Try it online!

I/O is a list of lists

Answer 20

TSQL, 252 bytes

Splitting the string is very costly, if the string was split and already in a table the byte count would be 127 characters. Script included in the bottom and completely different. Sorry for taking up this much space.

Golfed:

WITH C as(SELECT x,x/z r,x%z c,substring(@,x+1,1)v
FROM spt_values CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
WHERE'P'=type)SELECT @=stuff(@,x+1,1,'+')FROM c WHERE
exists(SELECT*FROM c d WHERE abs(r-c.r)<2and
abs(c-c.c)<2and'AB'=v+c.v)PRINT @

Ungolfed:

DECLARE @ varchar(max)=
'AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB';

WITH C as
(
  SELECT x,x/z r,x%z c,substring(@,x+1,1)v
  FROM spt_values
  CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
  WHERE'P'=type
)
SELECT
  @=stuff(@,x+1,1,'+')
FROM c
WHERE exists(SELECT*FROM c d 
         WHERE abs(r-c.r)<2 
           and abs(c-c.c)<2 and'AB'=v+c.v)
PRINT @

Try it out

TSQL, 127 bytes(Using table variable as input)

Execute this script in management studio - use "query"-"result to text" to make it readable

--populate table variable
USE master
DECLARE @v varchar(max)=
'AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB'

DECLARE @ table(x int, r int, c int, v char)

INSERT @
SELECT x+1,x/z,x%z,substring(@v,x+1,1)
FROM spt_values
CROSS APPLY(SELECT number x,charindex(char(10),@v)z)z
WHERE'P'=type and len(@v)>number

-- query(127 characters)

SELECT string_agg(v,'')FROM(SELECT
iif(exists(SELECT*FROM @
WHERE abs(r-c.r)<2and abs(c-c.c)<2and'AB'=v+c.v),'+',v)v
FROM @ c)z

Try it out - warning output is selected and not readable. Would be readable with print, but that is not possible using this method