13
\$\begingroup\$

Goal

In this competition, you are given a random room with one candle inside. The goal is to write the shortest program (this is golf) that determines what parts of the room are illuminated by the candle, by replacing the dark spots with @'s. The program should take a room from STDIN, with the output printed to STDOUT.

Example Input/Room

+------+
|  C   |
|      +--+
|  \      |
+---------+

The candle is represented with a C, and the walls/mirrors are represented with |,-,/, or \. The walls themselves are mirrors. The corners of the room are represented with a +.

Rooms will never have diagonal walls, and light will never be able to escape out of the room.

Also, the first character on a line is always going to be part of the wall off the room. The absolute last character on each line is going to be the opposite wall of the room. No characters between these two are going to be outside of the room.

Light and Reflection

The candle emits eight (laser-like) beams of light in eight basic directions: N, S, E, W, NE, SE, SW, and NW. These rays of light bounce off of the mirrors as described below:

Old Direction of Travel | Mirror | New Direction
N S E W NE SE SW NW       /        E W N S -- -- -- --
N S E W NE SE SW NW       \        W E S N -- -- -- --
N S E W NE SE SW NW       |        - - - - NW SW NE SW
N S E W NE SE SW NW       -        - - - - SE NE SW NE

A - represents the light being absorbed. Light is always absorbed by C's or +'s. It is important to note that the lights reflects off of a mirror only when it is occupying the same space as the mirror. These rules are much easier to understand when you draw the reflection out on paper.

Example Output

As output, the program should print an image of the illuminated room, with dark spots written as an @, light spots left blank, and mirrors unaffected. For the above example, the output would be:

+------+
|  C   |
|@   @ +--+
| @\      |
+---------+

This means that, if you drew out the beams of light, they will never reach the spaces marked with @.

More examples

Input:
+-----+
|     |
|     |
|  C  |
|     |
|     |
+-----+
Output:
+-----+
| @ @ |
|@   @|
|  C  |
|@   @|
| @ @ |
+-----+

Input:
+-----+
|  \  |
|/ C \+-+
|       |
|  \ - ++
+------+
Output:
+-----+
|  \ @|
|/ C \+-+
|      @|
| @\ -@++
+------+
\$\endgroup\$
  • \$\begingroup\$ In your example, shouldn't the bottom-left corner be @ too? \$\endgroup\$ – Peter Taylor Oct 5 '11 at 5:51
  • 1
    \$\begingroup\$ @Peter Taylor: The SW beam hits that spot. \$\endgroup\$ – Briguy37 Oct 5 '11 at 13:11
  • 3
    \$\begingroup\$ Bears some similarities to the very well received Lasers challenge on Stack Overflow. Enough similarities to make the methods used therein interesting with enough differences to require some considerable thought about how they might be applied. \$\endgroup\$ – dmckee Oct 5 '11 at 20:41
  • \$\begingroup\$ Could use more validation cases. \$\endgroup\$ – dmckee Oct 6 '11 at 1:37
  • \$\begingroup\$ @dmckee I added two more examples. \$\endgroup\$ – PhiNotPi Oct 6 '11 at 3:12
2
\$\begingroup\$

Python, 292 chars

import sys
R=''
for x in sys.stdin:R+='%-97s\n'%x[:-1].replace(' ','@')
M={'/':'-98/d','\\':'98/d'}
for d in(-98,-1,1,98,99,97,-97,-99):
 if d>98:M={'|':'d^2','-':'-d^2'}
 p=R.find('C')
 while 1:
  p+=d
  if R[p]in' @':R=R[:p]+' '+R[p+1:]
  elif R[p]in M:d=eval(M[R[p]])
  else:break
print R,

Reads in the room, makes it rectangular, then walks out from the candle in all directions. M contains the active mirror characters and their effect (/\ for the cardinal directions, |- for the others)

Can handle rooms up to 97 characters wide.

\$\endgroup\$
2
\$\begingroup\$

c -- 504

Relies on K&R default function calling semantics. Very straight forward implementation except for the fiddle stuff with bouncing the rays.

#define N M[x+y*97]
#define Y abs(y)
#define O M[c]==
#define E else break;
int j[]={-98,-97,-96,-1,1,96,97,98},c,x,y,p,s,M[9409];main(){for(;
(c=getchar())!=-1;){if(c==10)x=0,++y;else{if(c==67)p=x+y*97;if(c==32)
c=64;N=c;++x;}}for(x=0;x<8;++x){y=j[x];c=p;do{c+=y;if(O'@')M[c]=32;s=y/Y;
if(O 92)if(y%2){y=s*(98-Y);}E if(O'/')if(y%2){y=s*-(98-Y);}E if(O'|')
if(~y%2){y=s*(97+(97-Y));}E if(O'-')if(~y%2){y=s*-(97+(97-Y));}E}while
(!(O'+')&&!(O'C'));}for(y=0;x=0,N!=0;++y){for(;N!=0;++x)putchar(N);
putchar(10);}}

Ungolfed

//#include <stdio.h>
int j[]={ -98, -97, -96, /* Increments to move around the array */
           -1,       1,
           96,  97,  98},
  c, x, y, p, s, /* take advantage of static initialization to zero */
  M[9409]; /* treat as 97*97 */

main(){
  /* read the map */
  while((c=getchar())!=-1/*Assume the deffinition of EOF*/){
    /* putchar(c);  */
    if (c=='\n')
      x=0,++y;
    else {
      if (c=='C') p=x+y*97; /* set start position */
      if (c==' ') c='@'; /* The room starts dark */
      M[x+y*97]=c; ++x;
    }
  }
  /* printf("Start position is %d (%d, %d)\n",p,p%97,p/97); */
  /* Now loop through all the direction clearing '@' cells as we
   * encounter them 
   */
  for(x=0;x<8;++x){
    y=j[x];c=p; /* y the increment, c the position */
    /* printf("\tposition %d (%d, %d) '%c'\n",c,c%97,c/97,M[c]); */
    /* printf("\tdirection = %d (%d, %d)\n",y,-(abs(y)-97),(y+98)/97-1); */
    do {
      c+=y;
      /* printf("\t\tposition %d (%d, %d) '%c'\n",c,c%97,c/97,M[c]); */
      /* We ought to do bounds checking here, but we rely on  *
       * the guarantee that the room will be bounded instead. */
      if(M[c]=='@') M[c]=' ';
      /* The reflections are handles
       *   + Stop or not stop based on the even/oddness of the increment
       *   + New direction is a little fiddly, look for yourself
       */
      s=y/abs(y); /* sign of y (need for some reflections) */
      if (M[c]=='\\') if (y%2){ y=s* (98-abs(y));     }else break; 
      if (M[c]=='/')  if (y%2){ y=s*-(98-abs(y));     }else break; 
      if (M[c]=='|')  if (~y%2){y=s* (97+(97-abs(y)));}else break; 
      if (M[c]=='-')  if (~y%2){y=s*-(97+(97-abs(y)));}else break;  
      /* printf("\t\t\tdirection = %d (%d, %d)\n",y,97-abs(y),(y+98)/97-1); */
    } while (!(M[c]=='+')&&!(M[c]=='C'));
    /* printf("\t...hit a %c. Done\n",M[c]); */
  }
  /* print the result */
  for(y=0;x=0,M[x+y*97]!=0;++y){
    for(;M[x+y*97]!=0;++x)
      putchar(M[x+y*97]);
    putchar('\n');
  }
}

Validation

$ gcc -g -o candle candle_golfed.c
$ for f in candle_room*; do (./candle < $f) ; done
+------+
|  C   |
|@   @ +--+
| @\      |
+---------+
+------+
|  C   |
|@   @ +--+
|  /@ @ @ |
+---------+
+------+
| @/   |
|@   @ +--+
|  C      |
+---------+
+------+
|  \@ @|
|@   @ +--+
|  C      |
+---------+
+-----+
| @ @ |
|@   @|
|  C  |
|@   @|
| @ @ |
+-----+
\$\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.