3
\$\begingroup\$

A queue in the game Roller Coaster Tycoon

You will be given a matrix. It contains a ride exit (with a direction), some path, as well as some obstacles. Your goal is to build the longest possible queue line in that space, which connects the ride exit to any path.

Inputs

A grid containing:

  • A ride exit with direction, as U, D, L, or R, depending if the exit is facing up, down, left or right.
  • Some obstacles, as X
  • Some path, as #

Outputs

A number which is equal to the remaining empty squares which were unable to be filled.

Example

[ "###########", "XXXX #", " D #", " #", " #", "XX ##", "XXXXXXXXX#X" ] 
[ "###########", "XXXX┏┓┗━━┓#", "!D┏━┛┃┏━━┛#", "┏┛┗┓┏┛┗━━┓#", "┗━┓┃┃┏┓!┏┛#", "XX┗┛┗┛┗━┛##", "XXXXXXXXX#X" ]

Result: 2 empty squares (marked by !)

Rules

  • All test cases will have a valid route between the ride exit and a path. However, this may be of zero length (i.e.: the exit is directly facing a path, in which case there is zero queue).
  • Code golf scoring

Test Cases

Format: number of empty squares map 0 [ "R #", ] 0 [ "R#", ] 0 [ " L # ", " ", " ", " ", " ", " X ", " " ] 27 [ " L # ", " XXXXXXXXX ", " X X ", " X X ", " X X ", " XXXXXXXXX ", " " ] 27 [ " L # ", " ######### ", " # # ", " # # ", " # # ", " ######### ", " " ] 25 [ "R #", " XXXXXXXXX", " XXXXXXXX ", " XXXXXXXX ", " XXXXXXXX ", " XXXXXXXX ", " ", ] 34 [ "# X #", " X ", " X ", " X ", " X ", " X ", "U X " ] 2 [ "###########", "XXXX #", " D #", " #", " #", "XX ##", "XXXXXXXXX#X" ]

Related

Improve this question
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Do we need to handle cases where there is path in the middle of the board, or the exit is not at the edge of the board? This would only be possible if the path was reached by a bridge or tunnel (which is rare in real life) or if the exit was via a bridge or tunnel (which is relatively common.) \$\endgroup\$ Commented Jun 6 at 17:33
  • \$\begingroup\$ @LevelRiverSt there is no constraint on the position of the path or the exit. Other than that there will be a valid route between them. \$\endgroup\$ Commented Jun 7 at 0:00
  • \$\begingroup\$ Also related \$\endgroup\$ Commented Jun 8 at 23:03
  • \$\begingroup\$ Do we need to handle cases where an entrance leads directly into a wall or path? \$\endgroup\$ Commented Jun 8 at 23:04
  • 1
    \$\begingroup\$ @ValueInk I think this is fully covered by the rules section. \$\endgroup\$ Commented Jun 9 at 3:19

2 Answers 2

Reset to default
3
\$\begingroup\$

JavaScript (ES6), 171 bytes

Expects a matrix of characters.

f=(m,X,Y=o=f,e=1,n=0)=>m.map((r,y)=>r.map((c,x)=>!~(j="RULD #".search(c))|(n+=j==4,X+1?j>4|(h=x-X)*h+(v=y-Y)*v^1:j<5)?0:j<4?e=j^(v&2)-~h:r[f(m,r[x]=x,y),x]=c))|e|n>o?o:o=n

Try it online! (only the fastest test cases)

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 84 bytes

ＷＳ⊞υι⊞υ⭆θX≔⟦⪫υX⟧υＦυ«≔⌈⁻ιXη≔⁺⌕ιη§⟦¹±¹⊕Ｌθ±⊕Ｌθ⟧⌕RLDηζ≡§ιζ#Ｊ№ι ⁰ ＦRLDU⊞υ⭆ι⎇⁼ληX⎇⁼μζκλ»Ｉⅈ

Try it online! Link is to verbose version of code. Takes input as a rectangular array of newline-terminated strings. (The quotes aren't actually necessary, I was just too lazy to remove them.) Explanation: Calculates all queues and outputs the least number of empty squares of those queues that reach a path, so too slow for many of the test cases.

ＷＳ⊞υι

Input the grid.

⊞υ⭆θX

Append a row of obstacles, to deal with cyclic indexing.

≔⟦⪫υX⟧υＦυ«

Join the rows together with more obstacles and start a breadth first search for queues.

≔⌈⁻ιXη

Find the current direction of this queue. (A different obstacle character, such as *, would save me two bytes.)

≔⁺⌕ιη§⟦¹±¹⊕Ｌθ±⊕Ｌθ⟧⌕RLDηζ

Find the next step of this queue.

≡§ιζ#Ｊ№ι ⁰

If this queue has reached a path, record the number of spaces left.

 ＦRLDU⊞υ⭆ι⎇⁼ληX⎇⁼μζκλ

If this queue has not reached an obstacle, try all possible next steps.

»Ｉⅈ

Output the minimum number of spaces left. (Because this is a breadth-first search, this is always the last count recorded.)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.