13
\$\begingroup\$

Given an ASCII art with simple closed paths using | and - (pipes and dashes), output a random point inside the boundary.

Eg. given:

----              ----
|  |-   ---  =>   |12|-   ---
|   |   | |       |345|   |6|
-----   ---       -----   ---
Any point 1-6 should have an equal probability of being printed.

Specs

  • Take a string, list of strings or a matrix containing |, -,
  • Output either the ASCII art with a space replaced by a constant character other than a pipe, dash or space or print the two-dimensional/one-dimensional index.
  • All adjacent pipe-dash pairs are connected
  • This is , so the shortest answer wins

Test cases

---
|1|
---

----
|12|-   ---
|345|   |6|
-----   ---

 ---
 |1|
--2--
|345|
-----

-------
|1---2|
|3|4|5|
|6---7|
-------

--- ---
|1| |2|
|3---4|
|56789|
---A---
  |B|
---C---
|DEFGH|
|I---J|
|K| |L|
--- ---


    ---
    |1|
    ---
---     ---
|2|     |3|         (4 simple closed paths)
---     ---
    ---
    |4|
    ---
\$\endgroup\$
8
  • 2
    \$\begingroup\$ What does it mean "output a point"? Output its coordinates? \$\endgroup\$
    – matteo_c
    Feb 18, 2023 at 14:54
  • \$\begingroup\$ What is the definition of connected? Eg, it looks as if the pipe characters could all be asterisks, and connected just means adjacent? \$\endgroup\$
    – Jonah
    Feb 18, 2023 at 15:09
  • \$\begingroup\$ @Jonah More of a plus than an asterisk, but yes, updated, thanks. \$\endgroup\$
    – math scat
    Feb 18, 2023 at 15:19
  • \$\begingroup\$ Suggested test case. (it has a space at all four sides, none of which are considered inside a boundary). \$\endgroup\$ Feb 18, 2023 at 20:00
  • 1
    \$\begingroup\$ What is expected output for this testcase? \$\endgroup\$
    – tsh
    Feb 19, 2023 at 3:11

9 Answers 9

5
\$\begingroup\$

MATL, 19 18 17 15 bytes

36yy>t0ZI-flZr(

2 bytes saved thanks to @LuisMendo

Input is provided as a 2D character array and the random point is replaced by $

Try it out at MATL Online

Explanation

      % Implicitly retrieve the 2D character array input
36    % Push the literal 36 (ASCII for $) to the stack
y     % Make a copy of the character array
y     % Copy the value 36
>     % Create a boolean 2D array where all values with ASCII > '$' (36) are TRUE
      % these are the elements == '|' or '-' that make up the boundary
t     % Duplicate this boolean 2D array
0ZI   % Perform the morphological fill operation to set the value of all elements
      % within the boundaries to TRUE also
-     % Subtract the boundary to leave TRUE values only for elements that are 
      % inside the boundary
f     % Find the index values of all remaining TRUE values
lZr   % Pick one at random
(     % And assign the '$' (36) to that element in the original input
      % Implicitly display the result
\$\endgroup\$
0
4
\$\begingroup\$

Vyxal, 32 bytes

2(ðvø.∩)∩ðÞIk□"λhn÷:k□ẊṠJ↔";Ẋ÷F℅

Try it Online!

Expects a rectangular matrix containing |, -, . Returns a 2D index.

How?

Surround the input with spaces from all sides.

2(     )  # repeat twice:
  ð       #   push a space
   vø.    #   vectorized surround
      ∩   #   transpose
        ∩ # transpose

Find the coordinates of all spaces that are in the outside component.

ðÞI                  # get the coordinates of all spaces
   k□                # push cardinal directions [[0,1],[1,0],[0,-1],[-1,0]]
     "               # pair
      λ           ;Ẋ # apply the following function until a fixed point:
                         Takes a pair [coordinates of all spaces,  coordinates spaces reached so far]  
       h             #   head
        n            #   argument
         ÷           #   push each to stack
          :          #   duplicate
           k□        #   push cardinal directions [[0,1],[1,0],[0,-1],[-1,0]]
             Ẋ       #   cartesian product
              Ṡ      #   vectorising sum
               J     #   join the top two item on the stack
                ↔    #   keep only those items of a that are in b
                 "   #   pair

Now we have the pair [coordinates of all spaces, coordinates of spaces reachable from one of the sides].

÷   # push each to stack
 F  # remove items from a that are in b
  ℅ # choose a random item
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 82 81 77 bytes

WS⊞υι≔⌈EυLιθP⭆⪫υ¶⎇⁼ι ψι↖B⁺²θ⁺²Lυψ¤_↘TθLυFLυFθ«Jκι¤ »UMKA⎇⁼ι_ψι≔ΦKA⁼ι θ§≔θ‽Lθ#

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and marks the random selection with a #. Explanation:

WS⊞υι≔⌈EυLιθ

Input the strings and calculate the width of the ASCII art.

P⭆⪫υ¶⎇⁼ι ψι

Output the art but with spaces replaced with background.

↖B⁺²θ⁺²Lυψ¤_↘TθLυ

Add extra background padding, fill it with _s, and then remove the extra padding.

FLυFθ«Jκι¤ »

Replace any remaining background with spaces.

UMKA⎇⁼ι_ψι

Replace any remaining padding with background.

≔ΦKA⁼ι θ§≔θ‽Lθ#

Randomly replace a space with a #.

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 81 78 77 bytes

.B€SðQ2Fø1δ.ø}©˜ƶ®gäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅsM]¤θ©δÜ€¦˜0K®Êðs.;ÐÏSāDΩQ·.;0ð:

Uses 2 as random character.

Try it online or verify all test cases.

Explanation:

Step 1: Pad the input with trailing spaces to make it a rectangle, and add an additional border of spaces. Then convert it to a matrix of 0s for | and -, and give each space an unique 1-based integer value.

.B           # Blockify the (implicit) multi-line input by adding trailing spaces,
             # and then split it on newlines
  €S         # Convert each line to a list of characters
    ðQ       # Check for each character whether it's a space (1 if space; 0 otherwise)
2Fø1δ.ø}     # Add a border of 1s:
2F     }     #  Loop 2 times:
  ø          #   Zip/transpose; swapping rows/columns
    δ        #   Map over each inner list/row:
   1 .ø      #    Surround it with a leading/trailing 1
©            # After the loop: store the matrix in variable `®` (without popping)
 ˜           # Flatten it to a single list
  ƶ          # Multiply each value by its 1-based index
   ®g        # Push the length (aka amount of rows) of matrix `®`
     ä       # Split the list of integers back into a matrix of that many rows

Try just this first step online.

Step 2: Flood-fill the positive values in the matrix to identify the islands of spaces:

Δ            # Loop until it no longer changes to flood-fill:
 2Fø0δ.ø}    #  Add a border of 0s around the matrix:
 2F     }    #   Loop 2 times:
   ø         #    Zip/transpose; swapping rows/columns
     δ       #    Map over each row:
    0 .ø     #     Add a leading/trailing 0
 2Fø€ü3}     #  Convert it into overlapping 3x3 blocks: 
 2F    }     #   Loop 2 times again:
   ø         #    Zip/transpose; swapping rows/columns
    €        #    Map over each inner list:
     ü3      #     Convert it to a list of overlapping triplets
 ®*          #  Multiply each 3x3 block by the value in matrix `®`
             #  (so the 0s remain 0s)
 εεÅsyøÅsM   #  Get the largest value from the horizontal/vertical cross of each 3x3
             #  block:
 εε          #   Nested map over each 3x3 block:
   Ås        #    Pop and push its middle row
     y       #    Push the 3x3 block again
      ø      #    Zip/transpose; swapping rows/columns
       Ås    #    Pop and push its middle rows as well (the middle column)
         M   #    Push the flattened maximum of the entire (scoped) stack,
             #    which is the flattened maximum of the cross of the current 3x3 block
]            # Close the nested maps and flood-fill loop

Try just the first two steps online.

Step 3: Remove the border and all right-padded trailing space-integers. Then replace that same value to 0s and every other value to 1s in the input-string.

¤            # Push the last row (without popping the matrix)
 θ           # Pop and push its last item
  ©          # Store this space-integer in variable `®` (without popping)
   δ         # Map over each row with this space-integer as argument:
    Ü        #  Remove all trailing space-integers from the row
     €       # Map over each row again:
      ¦      #  Remove its first character (the leading column of space-integers)
       ˜     # Then flatten the matrix to a list
        0K   # Remove all 0s (the "-" and "|")
          ®Ê # Check for each remaining spaces-value that it's NOT equal to `®`
             # (1 if it's a space inside a boundary; 0 if it's a space outside boundary)
ð            # Push a space character " "
 s           # Swap so this list of 0s/1s is at the top
  .;         # Replace all spaces in the (implicit) input one by one with these 0s/1s

Try just the first three steps online.

Step 4: Transform all 1s into 0s, except for a random one, which we'll make 2 instead.

Ð            # Triplicate the modified input-string
 Ï           # Pop two copies, and only keep all 1s
  S          # Convert this string of 1s to a list of 1s
   ā         # Push a list in the range [1,length] (without popping the list of 1s)
    D        # Duplicate it
     Ω       # Pop and push a random integer from this list
      Q      # Check which one in the list is equal to it
             # (so we have a list of 0s with one random 1)
       ·     # Double each, so the 1 becomes a 2 (0s remains 0)
        .;   # Then replace all 1s in the modified input one by one with these 0s/2s

Try just the first four steps online.

Step 5: Finally replace all 0s back to spaces. After which we output the result.

0ð:          # Replace every 0 back to a space
             # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js),181 180 178 bytes

f=x=>[...x+0,n=0].map(_=>{for(i in x)for(j in e=x[i])for(k of'0123')(x[+i+--k%2]||++n)[+j+--k%2]?r=n=>Math.random()*n|0:1/e[j]?e[j]=0:0})&&x[p=r(x.length)][q=r(n)]<'!'?[p,q]:f(x)

Try it online!

Didn't expect it runs in time

\$\endgroup\$
3
\$\begingroup\$

Retina, 114 bytes

^
_¶
$
¶_
P`.+
.+
_$&_
+`_ | _|(?<=(.)*)( |_)(.*¶(?<-1>.)*(?(1)$)(?!\2))[ _]
_$3_
@` 
#
^_+¶_|_+¶_+$|_+(¶)_
$1
_
 

Try it online! Marks the random selection with a #. Explanation:

^
_¶
$
¶_
P`.+
.+
_$&_

Pad the input and surround it with _s on all sides.

+`_ | _|(?<=(.)*)( |_)(.*¶(?<-1>.)*(?(1)$)(?!\2))[ _]
_$3_

Flood fill the _s so that only interior spaces remain.

@` 
#

Randomly replace one with the output marker.

^_+¶_|_+¶_+$|_+(¶)_
$1
_
 

Remove the padding and replace any remaining _s with spaces.

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

Python3, 770 bytes:

import random as U
E=enumerate
def T(b,x,y):
 D={}
 for i in b:D[i[x]]=D.get(i[x],[])+[i[y]]
 return D
def B(b):
 P=[(x,y)for x,r in E(b)for y,k in E(r)if' '!=k];p=[*P]
 while p:
  q=[(r:=p.pop(0),[r])]
  while q:
   F=0
   (x,y),r=q.pop(0)
   for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
    j,k=x+X,y+Y
    V=(j,k)
    if 0<=j<len(b)and 0<=k<len(b[0])and(len(r)<2 or V!=r[-2]):
     if(j==x and'-'==b[j][k])or(k==y and'|'==b[j][k])or b[x][y]!=b[j][k]:
      if V in r:yield r;p=[*({*p}-{*r})];F=1;break
      elif V in P:q+=[(V,[*r,V])]
   if F:break
def f(b):
 K=[]
 for i in B(b):
  Q,W=T(i,0,1),T(i,1,0)
  K+=[(x,y)for x,r in E(b)for y,k in E(r)if' '==k and x in Q and min(Q[x])<=y<=max(Q[x])and y in W and min(W[y])<=x<=max(W[y])]
 x,y=U.choice(K)
 b[x][y]='*'
 return b

Try it online!

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

JavaScript (ES11), 168 bytes

Expects a matrix of characters and returns the coordinates [x,y] of a cell.

m=>(o=[])[m.map((r,y)=>r.map((C,x)=>(g=(x,y,r=m[y],c=r?.[x])=>1/c?[-1,0,1,2].every(d=>g(x+d%2,y+~-d%2),r[x]=g)|(r[x]=c):!!c/C)(x,y)?n=o.push([x,y]):0))|Math.random()*n]

Attempt This Online!
(with some post-processing to insert an asterisk at the chosen position)

How?

For each space in the input matrix, we process a recursive flood-fill to test whether we can 'escape' through a boundary. We keep track of each starting point for which this is not the case and return one of them.

Commented

m =>                      // m[] = input matrix
(o = [])[                 // start with o[] set to an empty array
  m.map((r, y) =>         // for each row r[] at index y in m[]:
    r.map((C, x) =>       //   for each character C at index x in r[]:
      ( g = (             //     g is a recursive function taking:
          x, y,           //       (x, y) = current position
          r = m[y],       //       r[] = current row
          c = r?.[x]      //       c = character at this position
        ) =>              //
        1 / c ?           //     if c is a space:
          [-1, 0, 1, 2]   //       array of directions
          .every(d =>     //       for each direction d:
            g(            //         do a recursive call:
              x + d % 2,  //           add dx to x
              y + ~-d % 2 //           add dy to y
            ),            //         end of recursive call
            r[x] = g      //         start by invalidating the current cell
          ) |             //       end of every()
          (r[x] = c)      //       restore the current cell
        :                 //     else:
          !!c / C         //       return a truthy value (1/0 = +∞) if and
                          //       only if c is defined and C is a space 
      )(x, y) ?           //     initial call to g; if truthy:
        n =               //       update n to the length of o[] ...
          o.push([x, y])  //       ... once [x, y] has been added to o[]
      :                   //     else:
        0                 //       do nothing
    )                     //   end of inner map()
  )                       // end of outer map()
  | Math.random() * n     // pick a random item from o[]
]                         //
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 238 bytes

e=enumerate
a,*r={i+1j*j:c<'!'for i,r in e(open(0))for j,c in e(r)},
while q:=[i for i in a if a[i]][:1]:
 g,*v=1,
 while q:
  c,*q=q;a[c]=0;v+=[c]
  for i in-1,1,-1j,1j:q+=[c+i]*a.get(c+i,0);g&=c+i in a
 r+=v*g
print({*map(str,r)}.pop())

Try it online!

Flood-fills from every space position and stores the ones that do not go out of bounds. Then it relies on hash randomization for strings to pop a random coordinate from the final set.

\$\endgroup\$
1
  • \$\begingroup\$ that's a lot of golfing :P \$\endgroup\$
    – math scat
    Feb 20, 2023 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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