# Random point inside boundary

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|
---

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

# MATL, 191817 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


# 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]
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


# Charcoal, 8281 77 bytes

ＷＳ⊞υι≔⌈ＥυＬιθＰ⭆⪫υ¶⎇⁼ι ψι↖Ｂ⁺²θ⁺²Ｌυψ¤_↘ＴθＬυＦＬυＦθ«Ｊκι¤ »ＵＭＫＡ⎇⁼ι_ψι≔ΦＫＡ⁼ι θ§≔θ‽Ｌθ#


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:

ＷＳ⊞υι≔⌈ＥυＬιθ


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

Ｐ⭆⪫υ¶⎇⁼ι ψι


Output the art but with spaces replaced with background.

↖Ｂ⁺²θ⁺²Ｌυψ¤_↘ＴθＬυ


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

ＦＬυＦθ«Ｊκι¤ »


Replace any remaining background with spaces.

ＵＭＫＡ⎇⁼ι_ψι


Replace any remaining padding with background.

≔ΦＫＡ⁼ι θ§≔θ‽Ｌθ#


Randomly replace a space with a #.

# 05AB1E, 8178 77 bytes

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


Uses 2 as random character.

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:
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)


# 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

# 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.

# 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!

# 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[]
]                         //


# 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.

• that's a lot of golfing :P Feb 20, 2023 at 10:58