Finding Pairs for Letters

Question

You should write a program or function which given a string as input outputs or returns a string or list of the lowercase letters in the order they find their uppercase pair.

The input is a string consisting of the characters [a-zA-Z] space and newline representing a torus (rectangular grid with wrap around for rows and columns) with some of the letters a-z and for every lowercase letter exactly one of its uppercase equal.

Every lowercase letter has a field of view equal to ord(letter)-97 grid steps i.e. a=0, b=1, ... , z=25 where 0 means you can only see your own cell. Steps (and field of view) are possible in all 8 directions. At every step:

• if a lowercase letter sees its uppercase pair (e.g. C for c) it will go straight to it
• if a lowercase letter doesn't see its uppercase pair it will move to the bottom right neighbor cell wrapping around if necessary.

There can be multiple letters at the same position. They don't block each other.

You should output or return the lowercase letters in the same order they reach their uppercase pair. If multiple letters reach their pair at the same step they should be outputted in alphabetical order. If a letter newer reaches its pair it shouldn't be outputted at all.

Input

• A string received in any reasonable way.
• Contains only letters [a-zA-Z] (at most one from each character; at least one pair of letters), spaces and newlines.
• Input will form a proper rectangle, i.e. there will be the same number of characters between every newline.
• Trailing newline is optional.

Output

• A list of lowercase letters in the order they reach their pair.
• Output can be in any reasonable data-structure (string, list, array etc.) and can be outputted or returned.
• Trailing newline is optional.

Examples

Input is all the rows between Input: and Visualization:. In visualization * marks all cells visited by letters. Other valid visualizations are possible as when a letter sees its pair often multiple shortest paths are possible. Space only lines are empty below. Check correct inputs here.

Input:

D     
  d Aa


Visualization:
  *   
D* *  
  d Aa
*     
 *    
Output: da
Step numbers: 2 5

Input:

W      B
    A   
  b     

      a 
  w     

Visualization:
**     *
W *    B
   *A   
  b *   
   * *  
    * a 
  w  * *
**    * 
Output: wb
Step numbers: 3 6

Input:


     A  


      a 

Visualization:
*  *****
**  ****
***  A**
****   *
*****   
 *****a 
  ******
Output: a
Step numbers: 39

Input:


   i      
  f     d 


    DI  F 
Visualization:


   i      
  f *   d 
   * *   *
*   **    
 ***DI**F 
Output: idf
Step numbers: 4 6 6

Input:



  g                 a                             


        G               W                         




                    j                             
             w                                    



                                         A      J 



Visualization:
       *         *         * *       *         *  
        *         *         * *       *         * 
         *         *         * *       *         *
* g       *         a         * *       *         
 * *       *         *         * *       *        
  * *       *         *         * *       *       
   * ***G    *     *****W        * *       *      
    *         *   *     *         * *       *     
     *         * *       *         * *       *    
      *         *         *         * *       *   
       *       * *         *         * *       *  
        *     *   * j       *         * *       * 
         *   w     * *       *         * *       *
*         *         * *       *         * *       
 *         *         * *       *         * *      
  *         *         * *       *         * *     
   *         *         * *       *       A * ***J 
    *         *         * *       *         *     
     *         *         * *       *         *    
      *         *         * *       *         *   
Output: gwj
Step numbers: 6 11 28

This is code-golf so the shortest entry wins.

Answer 1

Ruby 319 313 310 304 287 283

F=->s{l=s.split ?\n
b=[]
t={}
[*0...m=l.size].product([*0...n=l[0].size]).map{|y,x|c=l[y][x]
c!=' '&&c>?Z?b<<[c,y,x]:t[c.downcase]=[y,x]}
b.map{|q|c,y,x=q
u,i=t[c]
(m*n).times{|w|e=([u-(y+w)%m,i-(x+w)%n].map &:abs).max
e>c.ord-97||q<<w+e}
q[3]&&[q[3],q[0]]}.compact.sort.map{|a,b|b}}

This is a function that takes as input a string (without trailing newline) and returns an array of the lowercase letters in the correct order.

Here's a version you can run online with tests: http://ideone.com/5jiwLq

I've made a lot of modifications to the code. The history of modifications is available here.

Here's the indented and annotated version to make it easier to see what's going on (also available online):

F=->s{
  l=s.split ?\n
  m=l.size
  n=l[0].size

  # Make an array with lowercase letters and their coords (`b`)
  # Make a hash that for each target (uppercase letter) holds
  # its coordinates
  b=[]
  t={}
  [*0...m].product([*0...n]).map{|y,x| 
    c=l[y][x]
    c!=' '&&(c>?Z?b<<[c,y,x]:t[c.downcase]=[y,x])
  }

  # `l` is a function that, given an array of the form
  # [lowercase_letter, y-coord, x-coord] will append to that array
  # the number of steps required for the letter to reach its
  # uppercase correspondent
  l=->q{
    c,y,x=q
    u,i=t[c]
    d=c.ord-97
    (m*n).times{|w|
      e=([u-y,i-x].map &:abs).max
      e<=d&&q<<w+e
      y=(y+1)%m
      x=(x+1)%n
    }
  }

  # apply function `l` to each of the lowercase letters...
  b.map &l

  # ...then sort accordingly and return the array
  b.map{|x|[x[3],x[0]]}.select{|a,b|a}.sort.map{|a,b|b}
}