14
\$\begingroup\$

Given a board, write the shortest program or function to display or return which characters are in sight of the player. A character is in sight if is possible to draw a line between it and the player, without crossing any characters that block vision.

Input:

  • @ represents the player's position. There will only be one of these in the input.
  • any character that matches the regex [#A-Z] blocks vision.
  • any character that matches [ a-z] allows vision.
  • there will be no invalid characters
  • you are guaranteed a rectangular input

Lines are defined as follows:

  • define vector to be a magnitude and a direction
  • a direction is one of N,NE,E,SE,S,SW,W,NW
  • a magnitude is how many chars along that direction to count
  • let the initial vector be called d1; the second vector be called d2
  • one of d1 or d2 must have a magnitude of 1; the other may have whatever magnitude
  • d1's direction must be adjacent to d2's direction (e.g: N and NE)

A line is defined to be all chars along the path marked by applying d1, then d2, d1, d2 ....

Sample line (given by the .s):
d1 = (magnitude: 4, direction: E)
d2 = (magnitude: 1, direction NE)

               .....
          .....
     .....
@.... 

Output:

  • each visible character in the right position, . substitutes for space.
  • Space for each non-visible character.

Sample input:

@         
    K     
 J        

    L   




         o

Corresponding output:

@.........
....K.....
.J.....   
..........
.. .L.....
..  . ....
... .. ...
...  .. ..
...   .  .
....  ..  

Sample Input:

 B###M#  by 
 #Q   # Zmpq
 # # aaa    
@  m #      
# ##P#      
# ####      
# ####      
#M ###      
######      

Corresponding Output:

.B  #M      
.# ..   Z pq
.#.#.aaa..  
@..m.#      
#.##P#      
 .#         
 .#         
 M.         
  #         

Sample input:

  w                 

     O  l   gg  rT  
   QQL      Ag  #b  
   qqqqq         XqQ
 x     V# f@aa      
   Y        aaa     
   uU  E  l TaKK    
  e  dd  FF d opi   
   e       d        

Corresponding output:

   ..........  .....
    ......... ..... 
     O..l...gg..rT  
...QQL......Ag..#b..
...qqqqq.........XqQ
        #.f@aa......
   Y........aaa.....
...uU..E..l.TaKK....
      d..FF.d.op    
     .... .d. ...   
\$\endgroup\$
  • 3
    \$\begingroup\$ OK... bats, all kind of funghi, molds and snakes and even wraiths block the line of view, but giant mimics, hill orcs, mastodons, all kinds of other creatures or even fire vortices don't? \$\endgroup\$ – John Dvorak Jan 27 '14 at 5:23
  • \$\begingroup\$ @JanDvorak I was lazy and chose capital letters for blocking. Sort of like TALL monsters vs short monsters; which would you be able to see over. So yes. \$\endgroup\$ – Justin Jan 27 '14 at 5:24
  • 1
    \$\begingroup\$ I don't know about quantum mechanics, but the bat and the gnome mummy might be an easy deal. The mimic might complicate things further, though. Also, those three ants might be fun, and the large group of assorted monsters on the north-east might already know about you. Yeah... it might be nasty. As for #3 - where's my teleporation scroll? Oops, that was destroy armor. \$\endgroup\$ – John Dvorak Jan 27 '14 at 5:31
  • 3
    \$\begingroup\$ Just a curious observation, but if I understand your definition of "line" right, it looks like there are some squares that won't be visible even without any obstacles. For example, if the player is at (0, 0), then the square at (5, 12) can't be reached by any line. It might've made more sense to, say, specify some canonical implementation of Bresenham's line algorithm for drawing a line between any two points, and define a square as obscured if the line between it and the player intersects an obstacle. \$\endgroup\$ – Ilmari Karonen Jan 28 '14 at 14:51
  • 1
    \$\begingroup\$ @IlmariKaronen You are absolutely correct. That is just how I like it. :-). \$\endgroup\$ – Justin Jan 28 '14 at 19:00
5
\$\begingroup\$

GolfScript, 171 characters

.n?):L)[n*.]*1/:I'@'?{\+[{1$+}*]..{I=26,{65+}%"#
"+\?)}??)<}+{[L~.).)1L)L.(-1L~]>2<`{[.[~\]]{1/~2$*+L*.-1%}%\;~}+L,%~}8,%%{|}*`{1$?)I@=.n=@|\.' '={;'.'}*' 'if}+I,,%''*n%n*

The input must be provided on STDIN.

The output for the examples given above is slightly different. I verified the responses by hand and think they are correct.

Example 1:

@.........
....K.....
.J.....   
..........
.. .L.....
..  . ....
... .. ...
...  .. ..
...   .  .
....  ..  

Example 2:

.B  #M      
.# ..   Z pq
.#.#.aaa..  
@..m.#      
#.##P#      
 .#         
 .#         
 M.         
  #         

Example 3:

   ..........  .....
    ......... ..... 
     O..l...gg..rT  
...QQL......Ag..#b..
...qqqqq.........XqQ
        #.f@aa......
   Y........aaa.....
...uU..E..l.TaKK....
      d..FF.d.op    
     .... .d. ...   
\$\endgroup\$
  • \$\begingroup\$ This doesn't seem to work for single line inputs (which are valid rectangles...) \$\endgroup\$ – Justin Jan 30 '14 at 4:58
  • \$\begingroup\$ @Quincunx The code assumes that you finalise your input with a newline. Alternatively prepend n+ to the code. \$\endgroup\$ – Howard Jan 30 '14 at 5:32
4
\$\begingroup\$

Ruby - 510 chars

Quite a mammoth; but it is my first ever attempt at a golf.

m=$<.read;w,s,o,p=m.index(?\n)+1,m.size,m.dup.gsub(/[^@\n]/,' '),m.index(?@);d=[-w,1-w,1,w+1,w,w-1,-1,-1-w];0.upto(7){|i|x=d[i];[i-1,i+1].each{|j|y=d[j%8];[1,nil].each{|l|t=0;catch(:a){loop{c,f,r=p,1,nil;catch(:b){loop{(l||r)&&(1.upto(t){|u|c+=x;n=!(0...s).include?(c)||m[c]==?\n;n&&throw(f ?:a: :b);o[c]=m[c]==" "??.: m[c];a=m[c]=~/[#A-Z]/;a&&throw(f ?:a: :b)};f=nil);r=1;c+=y;n=!(0...s).include?(c)||m[c]==?\n;n&&throw(f ?:a: :b);o[c]=m[c]==" "??.: m[c];a=m[c]=~/[#A-Z]/;a&&throw(f ?:a: :b)}};t+=1}}}}};$><<o

Input is by file specified as argument; I assume the input file to consist of a rectangular block of characters (so, trailing spaces included), and to have a trailing newline.

This version makes extensive use of catch-throw to exit deep loops; I can possibly improve matters with bounds-checked loops instead.

Unobfuscated code:

# Read the map in
map = $<.read

# Determine its width and size
width = map.index("\n")+1
size = map.size

# Create a blank copy of the map to fill in with visible stuff
output = map.dup.gsub /[^@\n]/,' '

# Locate the player
player = map.index('@')

dirs = [
  -width,   # N
  1-width,  # NE
  1,        # E
  width+1,  # SE
  width,    # S
  width-1,  # SW
  -1,       # W
  -1-width  # NW
]

0.upto(7) do |i1|
  d1 = dirs[i1]
  [i1-1, i1+1].each do |i2|
    d2 = dirs[i2%8]

    # Stepping by 0,1,2... in d1, work along the line.
    # Write the cell value into the duplicate map, then break if it's
    # a "solid" character.
    #
    # Extensive use of catch-throw lets us exit deep loops.

    # For convenience of notation, instead of having either d1 or d2
    # be magnitude 1, and always doing d1,d2,d1... - I have d2 always
    # being magnitude 1, and doing either d1,d2,d1 or d2,d1,d2...

    # Loop twice - first with d1,d2,d1... second with d2,d1,d2...
    [true,false].each do |long_first|
      step = 0

      catch(:all_done) do
        # This loop increments step each iteration, being the magnitude of d1
        loop do
          cell = player
          first = true  # True until we've done the first d1
          later = false # True once we've done the first d2

          catch(:done) do
            # This loop repeatedly applies d1 and d2
            loop do
              if long_first || later  # Don't apply d1 first if starting with d2
                1.upto(step) do |dd1|
                  cell += d1 # Move one cell in d1
                  invalid = !(0...size).include?(cell) || map[cell]=="\n" # Out of range
                  throw :all_done if first && invalid # No point trying a longer step if the
                                                      # first application of d1 is out of range
                  throw :done if invalid # No point continuing with this step length

                  output[cell]=map[cell] == " " ? '.' : map[cell] # Transfer visble character
                  wall = map[cell]=~/[#A-Z]/  # Hit a wall?
                  throw :all_done if first && wall # Drop out as before
                  throw :done if wall
                end
                first = false
              end
              later=true

              # Now repeat above for the single d2 step
              cell += d2
              invalid = !(0...size).include?(cell) || map[cell]=="\n"
              throw :all_done if first && invalid
              throw :done if invalid
              output[cell]=map[cell] == " " ? '.' : map[cell]
              wall = map[cell]=~/[#A-Z]/
              throw :all_done if first && wall
              throw :done if wall
            end
          end
          step += 1
        end
      end
    end
  end
end

puts output

Edit

Ilmari Karonen notes in the question comments that the given vision algorithm doesn't see all squares, even when there's no obstacle. Here's a demonstration of that, out to (40,40) away from the player.

@.......................................
........................................
........................................
........................................
........................................
............ ...........................
..............  ........................
............ ...   ..... ...............
.............. ...    .....  ...........
...............  ...     .....   .......
.................  ...      .....    ...
..................   ...       .....
..... . ............   ...        .....
.....................    ...         ...
...... . ..............    ...
...... .. ..............     ...
....... . ................     ...
....... .. ............. ..      ...
.......  .  .................      ...
........ .. ............... ..       ...
........  .  ............... ...       .
........  ..  ................ ..
.........  .  ................. ...
.........  ..  .................  ..
....... .   .   . ................ ...
..........  ..  ...................  ..
..........   .   ...................  ..
........ .   ..   . ..................
........ ..   .   .. ..................
...........   ..   .....................
......... .    .    . ..................
......... ..   ..   .. .................
......... ..    .    .. ................
.......... .    ..    . ................
.......... ..    .    .. ...............
.......... ..    ..    .. ..............
..........  .     .     .  .............
........... ..    ..    .. .............
........... ..     .     .. ............
...........  .     ..     .  ...........
\$\endgroup\$
  • \$\begingroup\$ Hmm. This fails test 3. Needs debugging. \$\endgroup\$ – Chowlett Jan 27 '14 at 17:30
  • \$\begingroup\$ are you sure? I could have made a mistake... \$\endgroup\$ – Justin Jan 27 '14 at 20:17
  • \$\begingroup\$ Pretty sure - I can see the V behind the wall! I think I'm not detecting the newline after the previous line. \$\endgroup\$ – Chowlett Jan 27 '14 at 21:39
  • \$\begingroup\$ Definitely should not be seeing that... \$\endgroup\$ – Justin Jan 27 '14 at 21:44
  • \$\begingroup\$ Ah, it was a problem with my input; I had an extra space after XqQ. That said, your given answer for 3 doesn't match the testcase at all - it at least has an extra line at the top, and only one space between the O and l. \$\endgroup\$ – Chowlett Jan 28 '14 at 9:04

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.