13
\$\begingroup\$

UPDATED SCORING: As this challenge is more difficult than I anticipated, I have adjusted the scoring. A program that can solve a single mirror input is a valid answer. More sophisticated programs get a bonus to their score.

There have been several puzzles on PPCG to find a laser path in a box of mirrors. In this puzzle, you need to create a box of mirrors to match a number of laser destinations.

You are given a box and a specifications where lasers are to enter and exit. Your program needs to place exactly N double-sided mirrors in the box to meet the specification. The mirrors must be angled at 45 degrees but can be forward sloping or back sloping.

Input

Your program should accept a box grid via STDIN, command line argument, or file in the following format examples:

+--G--+     +abcde+
G     |     f/////d
|    /|     a//   c
+-----+     f     |
            +-b-e-+

The letter pairs ([a-zA-Z] may be used) indicate the input/output of up to 52 lasers. Inside the box will be N / mirrors. The box dimensions will be 3 <= W,H <= 200. The box is made of +|- characters. There may be any number of mirrors in the box including zero.

Output

The output should match the input, except the / characters may be moved and/or changed into \ characters. Your program should send a correct mirror box string to STDOUT or a file, trailing new line optional. If no placement of mirrors can meet the input specification, output Impossible\n. Examples of possible solutions:

+--G--+     +abcde+
G  /  |     f \ \ d
|     |     a/ \  c
+-----+     f / //|
            +-b-e-+

Testing example

Input:

+abcdefghijklmnopqrstuvwxyA-+
|///////////////            |
|///////////////            |
|                           |
+-Abcdefghijklmnopqrstuvwxya+

Example output:

+abcdefghijklmnopqrstuvwxyA-+
|\                         \|
|/                        / |
|\\\\\\\\\\\\\\\\\\\\\\\\\\ |
+-Abcdefghijklmnopqrstuvwxya+

Scoring (UPDATED)

This is code-golf with bonuses. You should nominate with your answer how many mirrors your program can solve (N). Your score is the length of your program in bytes divided by N. This allows people to enter with a simple program, but rewards more ambition programmers with a bonus.

Standard loopholes disallowed.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ This sounds like a hard problem, regardless of golfing. \$\endgroup\$
    – orlp
    Apr 2, 2015 at 9:36
  • 2
    \$\begingroup\$ Hint: brute force is not an option; it will take you 3 universe ages at 10k options per second for the larger example. \$\endgroup\$
    – Sanchises
    Apr 2, 2015 at 14:01
  • \$\begingroup\$ @sanchises I think it will take a great deal longer, as any mirror can be flipped, so I think you need a * 2^30 component in there as well \$\endgroup\$ Apr 3, 2015 at 9:02
  • \$\begingroup\$ Extra hint: You will need to exploit properties of the puzzle to prune your search space. You might also using combinations of partial solutions or hillclimbing from partial solutions that are close to a complete solution. It is now valid to answer with simpler solutions, so programs that solve one or two mirror puzzles are welcome too. \$\endgroup\$ Apr 3, 2015 at 9:33

2 Answers 2

2
\$\begingroup\$

C# - 897 862 bytes

Found a serious bug with it putting mirrors in places that they can't be. Now it works, hopefully! Also did some light golfing, couldn't leave the while loop in there... shameful.

Complete program, takes input from STDIN, outputs to STDOUT.

This was a lot of fun, it copes fine with the 7 by 5 problem (and when you remove one of the mirrors, making it impossible), took about 1 hour to solve the 30 by 5.

using Q=System.Console;class P{static int w,L;static string S(char[]M,int t,int r,int i,int d,int[]B){var s="";if(r<0)return s;M=(char[])M.Clone();B=(int[])B.Clone();B[i]=1;for(i+=d;M[t]<48|t==i;i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1))if(++t>=L){for(i=0;++i<L&r>0;)if(B[i]<1&M[i]<33){M[i]='.';r--;}return r<1?new string(M):s;}int c=M[i];if(c>32)s=c>47|c<46?s=c==M[t]?S(M,t,r,t,0,B):s:S(M,t,r,i,c<47?w/d:-w/d,B);else if((s=S(M,t,r,i,d,B))==""&B[i]<1){M[i]='.';s=S(M,t,r-1,i,w/d,B);if(s==""){M[i]='/';s=S(M,t,r-1,i,-w/d,B);}}return s;}static void Main(){string a,A="",R=A;for(;(a=Q.ReadLine())!=null;A+=a)L+=(w=a.Length);var G=A.ToCharArray();int r=0,i=L;for(;i>0;G[i]=G[i]=='|'?',':G[i])if(G[--i]==47|G[i]==92){r++;G[i]=' ';}a=S(G,0,r,1,w,new int[L]);if(a=="")R="Impossible\n";else for(;i<L;i+=w)R+=a.Substring(i,w)+"\n";Q.Write(R.Replace(".","\\").Replace(",","|"));}}

7 by 5 Example:

+abcde+
f/////d
a//   c
f     |
+-b-e-+

+abcde+
f   \ d
a/  //c
f/ \ /|
+-b-e-+

Impossible version:

+abcde+
f ////d
a//   c
f     |
+-b-e-+

Impossible

Something different (the program doesn't look at the original mirror layout):

+a----+
|//// |
|/////|
|/////|
+----a+

+a----+
| /\\\|
|\\\\\|
|\\/\\|
+----a+

30 by 5 solution:

+abcdefghijklmnopqrstuvwxyA-+
| \\\\\\\\\\\\\\\\\\\\\\\\ \|
| /                       //|
|\                         \|
+-Abcdefghijklmnopqrstuvwxya+

It looks at each laser source in turn, and builds a valid route for it (if it can), and then moves onto the next. It's a pretty simple depth-first search, which has to know which laser source (target) it's looking at, how many mirrors it remain for it to place, the current cell it's "at", the direction it's moving in, and each cell it's visited already (so that it doesn't put a mirror somewhere it's already been). The last 3 are used for assembling the path for the current target, and at reset when the target changes. Once it's got all the lasers linked up, it goes ahead and fills in any gaps it doesn't need left empty (another reason it needs to know everywhere it's visited).

When it's building routes, it favours going "forward" over inserting a mirror, and when it does, it favours a "\" mirror - this is best seen in the "something different" example above, where it skips the first cell below the top-most 'a', then continually fills out a "\" if it can find a solution with one, otherwise a "/" (naturally, if skipping the first cell resulted in it being unable to find a solution, then it would back-track and try putting a mirror there instead).

using Q=System.Console;

class P
{
    static int w,L;

    // M is cur grid
    // t is target edge thing (0->L)
    // r is mirrors remaining
    // i is pos
    // d is dir
    static string S(char[]M,int t,int r,int i,int d,int[]B)
    {
        var s="";

        if(r<0) // no mirrors left
            return s;

        // clone everything
        M=(char[])M.Clone();
        B=(int[])B.Clone();

        B[i]=1; // can't write to this

        for(i+=d; // move i
            M[t]<48|t==i; // only if target is something sensible (increment if i==t)
            i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1)) // reflect, should be fine for w=3
            if(++t>=L) // run off the end
            {
                for(i=0;++i<L&r>0;) // don't need I any more (count through everything)
                    if(B[i]<1&M[i]<33) // not been here & it's open space
                    {
                        M[i]='.'; // doesn't matter
                        r--;
                    }
                return r<1?new string(M):s; // none remaining ? victory : defeat
            }

        int c=M[i];
        if(c>32) // not boring
            s=c>47|c<46? // hit edge
                s=c==M[t]? // hit the correct thing
                    S(M,t,r,t,0,B): // i+0=t, tells it to increment t
                    s
            :S(M,t,r,i,c<47?w/d:-w/d,B); // mirror
        else // boring
            if((s=S(M,t,r,i,d,B))==""&B[i]<1) // fwd
            {
                M[i]='.'; // use . instead of \
                s=S(M,t,r-1,i,w/d,B); // \
                if(s=="")
                {
                    M[i]='/';
                    s=S(M,t,r-1,i,-w/d,B); // /
                }
            }

        return s;
    }

    static void Main()
    {
        string a,A="",R=A; // R is free
        for(;(a=Q.ReadLine())!=null;A+=a) // read input
            L+=(w=a.Length); // note width, accumulate length

        var G=A.ToCharArray();

        int r=0,i=L; // count mirrors (I refuse to make these static)
        for(;i>0; // end on i=0
            G[i]=G[i]=='|'?',':G[i]) // replace | with ,
            if(G[--i]==47|G[i]==92) // remove and count mirrors
            {
                r++;
                G[i]=' '; // storing G[i] doesn't seem to save anything
            }

        // search
        a=S(G,0,r,1,w,new int[L]);

        if(a=="") // defeat
            R="Impossible\n";
        else // victory
            for(;i<L;i+=w) // for each line
                R+=a.Substring(i,w)+"\n";

        Q.Write(R.Replace(".","\\").Replace(",","|")); // swap back | and \
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Nice solution. According to the new scoring system you score at least 917/7 = 131. \$\endgroup\$ Apr 3, 2015 at 16:33
2
\$\begingroup\$

Python, 671 654 bytes

Not a solution, but an attempt, read below.

import random as R
def V(F):
 for S,_x,_y in (F[0],0,1),(F[-1],0,-1),([L[0] for L in F],1,0),([L[-1] for L in F],-1,0):
  for i,C in enumerate(S):
   if not C in '+-|':
    x=_x;y=_y
    if not x: X=i;Y=y
    elif not y: Y=i;X=x
    while F[Y][X] != C:
     if F[Y][X]=='\\':x,y=y,x
     if F[Y][X]=='/':a=x+y;x,y=x-a,y-a
     X+=x;Y+=y
     try:
      if F[Y][X] in '+-|':return False
     except:
      return False
 return True
F=open(input()).read().split('\n')
while 1:
 _=[F[0]]+['\n'.join([L[0]+''.join([R.choice(' \\/')for i in range(len(F[0])-2)])+L[-1] for L in F[1:-1]])]+[F[-1]]
 if V(_):
  for l in _: print l
  break

I did not golf this to the max, since I'm not satisfied with the solution. V validates a given solution by walking the field F for each character C it finds on the sideline. Solutions are generated at random. It's ugly, it works for entry1, but takes a Lot of time for the other entries. Since it randomly tries solutions, I don't consider this to be an actual solution for the given problem; but it might help others.

Run: echo "entry1.txt" | python script.py

\$\endgroup\$
1
  • 1
    \$\begingroup\$ With the new scoring system, this is a valid solution but does not score a divisor bonus (unless it can solve problems with 2 or more mirrors). I think you could optimise this by pruning out invalid configurations earlier (eg: each column or row with a letter on the edge must have at least one mirror - unless matching letters are opposite each other). \$\endgroup\$ Apr 3, 2015 at 16:39

Your Answer

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

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