8
\$\begingroup\$

Inspired by Is this Flow Free puzzle trivial? by @Bubbler. Lengthy chunks of this challenge are borrowed from there. This may be one step of a solution for the linked challenge, depending on chosen strategy.

Challenge

Given an array of digits 1-9 and a padding character of your choice, output the border of the shape made by the digits (in any direction, with any starting point).

Example

Here, the padding character is 0.

Input   Border  Output (one of possible)
00111   00###   111334442222211133
13333   ###3#   
13243   #32##   
13240   #32#0   
23240   #3##0   
22200   ###00   

Rules

The input can be taken as a single string/array or a list of lines. You may also take the dimensions of the array as input.

The input shape will be guaranteed to be at least 2 cells thick (so no overlapping borders) and will be interconnected (so one continuous border).

You may assume only the digits 1-9 are used and choose the padding character to be either 0 or any consistent non-digit one. You may omit the trailing padding in the input and assume the array will have minimal dimensions to fit the shape (so no column or row full of 0 will be provided).

Output the string/list in any convenient manner.

This is , the shortest code per language wins!

Test cases

Here, the padding character is 0. Outputs here start at the leftmost cell of first row, but rotations and reflections of that vector are fine.

00111
13333
13243
13240
23240
22200
Output: 111334442222211133

11111
13331
12221
Output: 111111122211

00110
33333
32222
Output: 113322223333

00330
03240
13243
23243
22043
Output: 334433344232221332

0000777
0006666
0025550
0555300
8888000
9990000
Output: 7776655358899988552566

123456
789876
540032
120000
345678
987654
Output: 123456623789842456784567893157
\$\endgroup\$
2
  • \$\begingroup\$ May I assume no extra padded 0's are given? For example, not 00000 11111 13331 12221 nor 011111 013331 012221. \$\endgroup\$
    – tsh
    Oct 12 '21 at 5:15
  • 1
    \$\begingroup\$ @tsh "the array will have minimal dimensions to fit the shape (so no column or row full of 0 will be provided)" \$\endgroup\$
    – pajonk
    Oct 12 '21 at 7:07
5
\$\begingroup\$

JavaScript (ES6),  116  101 bytes

Expects a list of strings, using any non-digit character for padding. Returns a string.

a=>(g=X=>+(d&=3,v=(a[y=Y+--d%2]||0)[x=X+~-d%2])?x-q|y?v+g(x,Y=y):v:g(X,d+=2))(q=a[d=Y=0].search`\\d`)

Try it online!

How?

This algorithm starts at the leftmost non-empty cell on the first row of the grid and goes counterclockwise from there, leading to the outputs provided in the test cases in reverse order.

The recursive function \$g\$ takes a position \$(X,Y)\$ and a direction \$d\$. (NB: \$Y\$ and \$d\$ are global variables. Only \$X\$ is passed explicitly.)

We first look for the smallest \$q\ge0\$ such that the cell at \$(q,0)\$ is not empty and do an initial call to \$g\$ with \$(X,Y)=(q,0)\$ and \$d=0\$.

Within the function \$g\$:

  1. We force \$d\$ into \$[0,1,2,3]\$ by isolating the two least significant bits, and we decrement it afterwards.
  2. We advance by one square to a new position \$(x,y)\$, according to the updated value of \$d\$:
    • \$-1\$ = north
    • \$0\$ = west
    • \$1\$ = south
    • \$2\$ = east
  3. If we've just reached \$(q,0)\$, the border is complete. We append the last value and stop.
  4. Otherwise, we do a recursive call:
    • If the cell at our new position is non-empty, we append the value of the cell to the final result and process the recursive call g(x,Y=y). Because \$d\$ was decremented at step 1, it means that we do a 90° turn to the right.
    • Otherwise, we process the recursive call g(X,d+=2), which means that we rollback to the previous position and do a 90° turn to the left.
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 82 53 51 bytes

WS⟦ι⟧J⌕⭆θ¬Σι0⁰≔⁰θW¬⁼0KK«⊞υKK≦⊕θW›0§KV⁻¹θ≦⊖θ✳⊗θ0»⎚↑υ

Try it online! Link is to verbose version of code. Uses space as the padding character. Edit: Saved 29 31 bytes by realising that the border end could be detected without deleting the interior. Explanation:

WS⟦ι⟧

Print the input to the canvas.

J⌕⭆θ¬Σι0⁰

Find the first digit in the first row.

≔⁰θ

Start moving horizontally.

W¬⁼0KK«

Repeat until the border has been traversed.

⊞υKK

Append the next border cell to the result.

≦⊕θ

Try rotating left.

W›0§KV⁻¹θ≦⊖θ

Rotate right if necessary until a digit is found.

✳⊗θ0

Move in that direction, erasing the current border.

»⎚↑υ

Output the final result.

\$\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.