22
\$\begingroup\$

The Challenge

Given a rectangular grid of characters

A B C D E
F G H I J
K L M N O
P Q R S T

and a grid with the same dimensions of dots and spaces

. .     .
  .   . .
  .   .  
  . . .  

Output the string which is generated by following the dots through the grid starting in the upper left corner. This example would yield ABGLQRSNIJE

Notes

  • You may take the input grids as 2D-arrays or the closest alternative in your language instead of a multiline string.
  • You may use the NULL value of your language instead of spaces. But you have to use dots to mark the path.
  • You don't need to separate dots on the same line with spaces. I just added them for readability.
  • The smallest possible grid has the size 1x1.
  • The start and end dot will have only one neighbour. The dots between them will always have exact two vertical or horizontal neighbours. This guarantees that the path is unambiguously.
  • The path will not go diagonal.
  • The characters in the grid will be either all upper- or lowercase characters in the range [a-z] whatever is most convenient for you.
  • The path will always start in the upper left corner.

Rules

Test cases

Grid #1

A B C A B C W
D E F G H U Q
X L U S D Q Z
A S U K W X I
W U K O A I M
A I A I O U P
. .          
  . . .      
      .      
. . . .      
.            
.            
=> ABEFGSKUSAWA
. . . . . . .
            .
. . .       .
.   . .     .
.           .
. . . . . . .
=> ABCABCWQZIMPUOIAIAWAXLUUK

Grid #2

Note the triple spaces in the second lines of the first and second examples.

A B
C D
.  
   
=> A
. .
   
=> AB
.  
. .
=> ACD

Grid #3

A
.
=> A

Happy Coding!

\$\endgroup\$
8
  • \$\begingroup\$ Are you sure the second test case for Grid #1 is correct? I think the output should be ABCABCUQXIUOIAIAWAXLUUK. \$\endgroup\$
    – vaultah
    Mar 5, 2016 at 20:45
  • \$\begingroup\$ @vaultah Thaks for the hint, corrected it. Had the dots in the grid one column to far on the left. \$\endgroup\$
    – Denker
    Mar 5, 2016 at 20:54
  • \$\begingroup\$ Do we need to accept input with every other character a space, as here, or can it be just letters and newlines (and no extra spaces in the dot matrix)? \$\endgroup\$
    – msh210
    Mar 6, 2016 at 6:36
  • \$\begingroup\$ @msh210 As said in the challenge, you may use some kind of NULL value instead of spaces, given of course you take the input as a 2D array. \$\endgroup\$
    – Denker
    Mar 6, 2016 at 14:53
  • \$\begingroup\$ I meant, with nothing at all, not even a null byte. \$\endgroup\$
    – msh210
    Mar 6, 2016 at 15:25

3 Answers 3

4
\$\begingroup\$

APL, 63 bytes

{⍺[(⊂1 1){×≢⍵:⍺,(V/⍵)∇⍵/⍨~V←(+=⌊/)+/¨2*⍨⍺-⍵⋄⍺}1↓(,⍵='.')/,⍳⍴⍵]}

This is a function that takes two character matrices (they must be matrices), the character grid as its left argument and the dots grid as its right argument. The matrix of dots may be smaller than the matrix of characters.

Explanation:

  • (,⍵='.')/,⍳⍴⍵: get the positions of the dots, in row-column order
  • 1↓: drop the first one (it is known to be at 1 1)
  • (⊂1 1){...}: starting from 1 1, run the following function, which follows the path (its left argument is its current position, its right argument are unvisited positions). It works by selecting the nearest unvisited dot each time. (If the assumptions from the question hold, this is correct.)
    • ×≢⍵:: if there are still unvisited positions:
      • +/¨2*⍨⍺-⍵: find the Manhattan distance between each position and the current position
      • V←(+=⌊/): for each position, see if its distance is equal to the smallest distance, and store this in V.
      • ⍵/⍨~: select all positions for which this is not the case, these are the fields to visit next
      • (V/⍵): find the position for which it is the case, this will be the next field
      • : run the function again with these new arguments
      • ⍺,: the result is the current position, followed by the result of doing this for the rest of the list
    • ⋄⍺: otherwise, just return the current position and stop (it's the last one)
  • ⍺[...]: for each position, select the corresponding element in the character grid.

Test cases:

      f←{⍺[(⊂1 1){×≢⍵:⍺,(V/⍵)∇⍵/⍨~V←(+=⌊/)+/¨2*⍨⍺-⍵⋄⍺}1↓(,⍵='.')/,⍳⍴⍵]}
      ⍝ example
      g0  ← 4 5⍴'ABCDEFGHIJKLMNOPQRST'
      d0  ← 4 5⍴'..  . . .. . .  ... '
      ⍝ test case 1
      g1  ← 6 7⍴'ABCACBWDEFGHUQXLUSDQZASUKWXIWUKOAIMAIAIOUP'
      d1a ← 6 7⍴'..      ...      .   ....   .      .      '
      d1b ← 6 7⍴'.......      ....   .. ..  ..     ........'
      ⍝ test case 2
      g2  ← 2 2⍴'ABCD'
      d2a ← 1 1⍴'.'
      d2b ← 1 2⍴'..'
      d2c ← 2 2⍴'. ..'
      ⍝ test case 3
      g3  ← 1 1⍴'A'
      d3  ← 1 1⍴'.'

      g0 f d0
ABGLQRSNIJE
      (⊂g1) f¨ d1a d1b
┌────────────┬─────────────────────────┐
│ABEFGSKUSAWA│ABCACBWQZIMPUOIAIAWAXLUUK│
└────────────┴─────────────────────────┘
      (⊂g2) f¨ d2a d2b d2c
┌─┬──┬───┐
│A│AB│ACD│
└─┴──┴───┘
      g3 f d3
A
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 122 bytes

c=>g=>c[l=~c.search`
`,i=p=0]+[...g].map(_=>i|!p?c[i=(d=n=>g[i-n-p?i-n:c]>" "&&(p=i)-n)(1)||d(-1)||d(l)||d(-l)]:"").join``

Explanation

Takes the grids as multiline strings.

Feels like a decent attempt but I ran out of time while golfing so it could probably be improved.

var solution =

c=>g=>
  c[                            // add the starting letter to the output
    l=~c.search`
`,                              // l = line length
    i=p=0                       // i = current index, p = previous index
  ]+
  [...g].map(_=>                // loop
    i|!p?                       // if we have not finished yet
      c[i=                      // find the next index and return it's letter
        (d=n=>                  // d = function to check for a dot at offset n
          g[
            i-n-p?i-n           // if i - n != p, get the character at index i - n
            :c                  // else get index "c" (will return undefined, not a dot)
          ]>" "                 // if the character is a dot
          &&(p=i)-n             // set p to i and return i - n
        )
        (1)||d(-1)||d(l)||d(-l) // search for the next adjacent dot
      ]
    :""                         // if we have finished, return no letter
  )
  .join``                       // output all the returned letters
<textarea id="Characters" rows="6" cols="30">ABCABCW
DEFGHUQ
XLUSDQZ
ASUKWXI
WUKOAIM
AIAIOUP</textarea>
<textarea id="Grid" rows="6" cols="30">.......
      .
...   .
. ..  .
.     .
.......</textarea><br />
<button onclick="result.textContent=solution(Characters.value)(Grid.value)">Go</button>
<pre id="result"></pre>

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 43 bytes

{⍺[11 9∘○¨{⍵∪⍺∩∊⍵+⊂0j1*⍳4}⍣≡∘⊃⍨0j1⊥¨⍸⍵=⊃⍵]}

Try it online!

\$\endgroup\$

Your Answer

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

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