[Prof. Templeton]

On a 10 x 10 grid table, a light beam enters from the middle of the top left cell at an angle of 45 degrees as indicated by the arrow. When the beam reaches a mirror it is reflected and its path ends when it reaches the edge of the table.

Place the mirrors on the table to create the maximum beam length. The mirrors may not touch each other, not even diagonally. The size and quantities of the mirrors you can use are shown below. A squares diagonal length will be 1 unit.

What is the longest beam you can make?

[EventHorizon]

As of now, I have 5 configurations that give a path length of 61.5.

I had to prune the search space rather significantly to make it so my code would finish in my lifetime... so the final answer I get may not be perfect. I'll try to think of better optimizations, but I only just came up with a somewhat acceptable pruning that wouldn't provably find the optimum.

And since I'm curious as to what it found, I'll make a picture of one of the 61.5s.

Looking at it, it's simple to increase it to 63.5 by swapping the 3 that gets hit once with the 1 at the top left. Also, there's got to be a way to better utilize that 4. I'll post again quick once I marginally improve it.

[EventHorizon]

67.5

[EventHorizon]

The last one was pretty enough that I was hoping it was at least made of the same pattern as the optimal one, but alas...

69.5

This was modified from a 66 length one the code found.

[EventHorizon]

This is the best one that a very restricted search found. I'm running a slightly more thorough search, but it will take a while, and I may need to start and stop it a few times.

So for now, here's a 76.

And here's the code that found it

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <memory.h>


using namespace std;


#define GRIDSIZE 10

int GRIDSIZESQ;

#define NUMPIECES 10


int thegrid[GRIDSIZE][GRIDSIZE]; //the pieces that are placed

int available[GRIDSIZE][GRIDSIZE]; //where a piece could be placed


int pieces[NUMPIECES]; //sizes of mirrors

int currentpos[NUMPIECES]; //for knowing how far the search is

int firstpos[NUMPIECES]; //for restarting the search later


int maxlength=0; //best solution found *2


int lightit(); //shine the laser

void toggle(int x, int y, int ori, int size); //put or remove piece

int check(int x, int y, int ori, int size); //can I put the piece there?

void add(int x, int y, int ori, int size, int num); //modifies available matrix

void printit(); //print solution and length

void recurse(int currentvalue, int first); //the search


//to lower CPU usage

#define SLEEPWAIT 400

#define SLEEPINT 1000

int counter = 0;


//to print current search state

int counter2 = 0;

#define RECORDINT 100000000


int main(int argc, char *argv[])

{

	GRIDSIZESQ = (GRIDSIZE*GRIDSIZE);

	pieces[0] = 4;

	pieces[1] = 3;

	pieces[2] = 3;

	pieces[3] = 2;

	pieces[4] = 2;

	pieces[5] = 2;

	pieces[6] = 1;

	pieces[7] = 1;

	pieces[8] = 1;

	pieces[9] = 1;

	for(int i = 0; i < GRIDSIZE; i++)

	{

		for(int j = 0; j < GRIDSIZE; j++)

		{

			thegrid[i][j] = 0;

			available[i][j] = 0;

		}

	}

	available[0][0] = 5;

	available[0][1] = 5;

	available[1][1] = 5;//having pieces in these positions makes it a short length...


	available[8][0] = 5;//decided to make it so you cannot have a piece in corners or next to corners

	available[9][0] = 5;

	available[9][1] = 5;

	available[0][8] = 5;

	available[0][9] = 5;

	available[1][9] = 5;

	available[9][8] = 5;

	available[9][9] = 5;

	available[8][9] = 5;

	available[1][0] = 5;



	//only allow single squares in the middle (hopefully the optimal solution is in this set).

	for(int i = 1; i < GRIDSIZE-1; i++)

	{

		for(int j = 1; j < GRIDSIZE-1; j++)

			available[i][j] = 1;

	}


	firstpos[0] = 0;//if you need to restart the search, enter info here

	firstpos[1] = 0;

	firstpos[2] = 0;

	firstpos[3] = 0;

	firstpos[4] = 0;

	firstpos[5] = 0;

	firstpos[6] = 0;

	firstpos[7] = 0;

	firstpos[8] = 0;

	firstpos[9] = 0;


	recurse(0,1);


	cout << "Done!" << endl;

}


void recurse(int current, int first)

{

	if (first) currentpos[current] = firstpos[current]-1;

	else currentpos[current] = -1;

	for(int ori = (first?(firstpos[current]/GRIDSIZESQ):0); ori < 2; ori++)

	{

		for(int x = (first?(firstpos[current]/GRIDSIZE)%GRIDSIZE:0); x < GRIDSIZE; x++)

		{

			for(int y = (first?(firstpos[current]%GRIDSIZE):0); y < GRIDSIZE; y++)

			{

				//optimization -- removes identical configurations by forcing

				//				identical pieces to be ordered by position

				currentpos[current]++;

				if ((current > 0) && (pieces[current] == pieces[current-1]))

					if (currentpos[current]%GRIDSIZESQ <= currentpos[current-1]%GRIDSIZESQ) continue;


				if (check(x,y,ori,pieces[current]))//can I put a piece there?

				{

					toggle(x,y,ori,pieces[current]);

					add(x,y,ori,pieces[current],5);

					if (current < NUMPIECES-1)

					{//add next piece

						recurse(current+1,first);

						first = 0;

					}

					else

					{//check configuration

						int currentvalue=0;

						if (maxlength <= (currentvalue=lightit()))

						{

							maxlength = currentvalue;

							printit();

						}

					}

					toggle(x,y,ori,pieces[current]);

					add(x,y,ori,pieces[current],-5);

				}

			}

		}

		if (pieces[current]==1) break; //orientation doesn't matter for singles

	}

}


int lightit()

{

	if (++counter == SLEEPINT){counter=0;usleep(SLEEPWAIT);}

	if (++counter2 == RECORDINT)

	{

		counter2=0;

		for(int i = 0; i < NUMPIECES; i++)

		{

			cout << currentpos[i] << " ";

		}

		cout << endl;

	}


	int x = 0, y = 1, dx = 1, dy = 1;

	int length = 0;

	if (thegrid[0][0]) return 0;

	do

	{

		if (length%2) //at a vertical line

			{if (thegrid[x/2][(y+dy)/2]) dy=-dy;}

		else //at a horizontal line

			{if (thegrid[(x+dx)/2][y/2]) dx=-dx;}

		x+=dx; y+=dy;

		length++;

	} while ((x%(GRIDSIZE*2)) && (y%(GRIDSIZE*2)));

	return length;

}


void toggle(int x, int y, int ori, int size)

{

	int value = 1-thegrid[x][y];

	if (!ori)

		for(int i = 0; i < size; i++) thegrid[x+i][y] = value;

	else

		for(int i = 0; i < size; i++) thegrid[x][y+i] = value;

}


int check(int x, int y, int ori, int size)

{

	if (!ori)

	{

		if (x+size-1 >= GRIDSIZE) return 0;

		if ((available[x][y] > ((size==1)?1:0)) || (available[x+size-1][y] > ((size==1)?1:0))) return 0;

	}

	else

	{

		if (y+size-1 >= GRIDSIZE) return 0;

		if ((available[x][y] > ((size==1)?1:0)) || (available[x][y+size-1] > ((size==1)?1:0))) return 0;

	}

	return 1;

}


void add(int x, int y, int ori, int size, int num)

{

	int minx = (x-1 < 0) ? 0 : x-1;

	int maxx = (!ori ? x+size : x+1);

	maxx = (maxx >= GRIDSIZE) ? GRIDSIZE-1 : maxx;

	int miny = (y-1 < 0) ? 0 : y-1;

	int maxy = (ori ? y+size : y+1);

	maxy = (maxy >= GRIDSIZE) ? GRIDSIZE-1 : maxy;

	for(int i = minx; i <= maxx; i++)

		for(int j = miny; j <= maxy; j++)

			available[i][j] += num;

}


void printit()

{

	for(int j = 0; j < GRIDSIZE; j++)

	{

		for(int i = 0; i < GRIDSIZE; i++)

		{

			if (thegrid[i][j]) cout << "X";

			else cout << " ";

		}

		cout << endl;

	}

	cout << maxlength << endl << endl;

}

Edit reason: Bug in resume code

Edited December 8, 2011 by EventHorizon

[Prof. Templeton]

This is the best one that a very restricted search found. I'm running a slightly more thorough search, but it will take a while, and I may need to start and stop it a few times.

So for now, here's a 76.

And here's the code that found it

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <memory.h>


using namespace std;


#define GRIDSIZE 10

int GRIDSIZESQ;

#define NUMPIECES 10


int thegrid[GRIDSIZE][GRIDSIZE]; //the pieces that are placed

int available[GRIDSIZE][GRIDSIZE]; //where a piece could be placed


int pieces[NUMPIECES]; //sizes of mirrors

int currentpos[NUMPIECES]; //for knowing how far the search is

int firstpos[NUMPIECES]; //for restarting the search later


int maxlength=0; //best solution found *2


int lightit(); //shine the laser

void toggle(int x, int y, int ori, int size); //put or remove piece

int check(int x, int y, int ori, int size); //can I put the piece there?

void add(int x, int y, int ori, int size, int num); //modifies available matrix

void printit(); //print solution and length

void recurse(int currentvalue, int first); //the search


//to lower CPU usage

#define SLEEPWAIT 400

#define SLEEPINT 1000

int counter = 0;


//to print current search state

int counter2 = 0;

#define RECORDINT 100000000


int main(int argc, char *argv[])

{

	GRIDSIZESQ = (GRIDSIZE*GRIDSIZE);

	pieces[0] = 4;

	pieces[1] = 3;

	pieces[2] = 3;

	pieces[3] = 2;

	pieces[4] = 2;

	pieces[5] = 2;

	pieces[6] = 1;

	pieces[7] = 1;

	pieces[8] = 1;

	pieces[9] = 1;

	for(int i = 0; i < GRIDSIZE; i++)

	{

		for(int j = 0; j < GRIDSIZE; j++)

		{

			thegrid[i][j] = 0;

			available[i][j] = 0;

		}

	}

	available[0][0] = 5;

	available[0][1] = 5;

	available[1][1] = 5;//having pieces in these positions makes it a short length...


	available[8][0] = 5;//decided to make it so you cannot have a piece in corners or next to corners

	available[9][0] = 5;

	available[9][1] = 5;

	available[0][8] = 5;

	available[0][9] = 5;

	available[1][9] = 5;

	available[9][8] = 5;

	available[9][9] = 5;

	available[8][9] = 5;

	available[1][0] = 5;



	//only allow single squares in the middle (hopefully the optimal solution is in this set).

	for(int i = 1; i < GRIDSIZE-1; i++)

	{

		for(int j = 1; j < GRIDSIZE-1; j++)

			available[i][j] = 1;

	}


	firstpos[0] = 0;//if you need to restart the search, enter info here

	firstpos[1] = 0;

	firstpos[2] = 0;

	firstpos[3] = 0;

	firstpos[4] = 0;

	firstpos[5] = 0;

	firstpos[6] = 0;

	firstpos[7] = 0;

	firstpos[8] = 0;

	firstpos[9] = 0;


	recurse(0,1);


	cout << "Done!" << endl;

}


void recurse(int current, int first)

{

	if (first) currentpos[current] = firstpos[current]-1;

	else currentpos[current] = -1;

	for(int ori = (first?(firstpos[current]/GRIDSIZESQ):0); ori < 2; ori++)

	{

		for(int x = (first?(firstpos[current]/GRIDSIZE):0); x < GRIDSIZE; x++)

		{

			for(int y = (first?(firstpos[current]%GRIDSIZE):0); y < GRIDSIZE; y++)

			{

				//optimization -- removes identical configurations by forcing

				//				identical pieces to be ordered by position

				currentpos[current]++;

				if ((current > 0) && (pieces[current] == pieces[current-1]))

					if (currentpos[current]%GRIDSIZESQ <= currentpos[current-1]%GRIDSIZESQ) continue;


				if (check(x,y,ori,pieces[current]))//can I put a piece there?

				{

					toggle(x,y,ori,pieces[current]);

					add(x,y,ori,pieces[current],5);

					if (current < NUMPIECES-1)

					{//add next piece

						recurse(current+1,first);

						first = 0;

					}

					else

					{//check configuration

						int currentvalue=0;

						if (maxlength <= (currentvalue=lightit()))

						{

							maxlength = currentvalue;

							printit();

						}

					}

					toggle(x,y,ori,pieces[current]);

					add(x,y,ori,pieces[current],-5);

				}

			}

		}

		if (pieces[current]==1) break; //orientation doesn't matter for singles

	}

}


int lightit()

{

	if (++counter == SLEEPINT){counter=0;usleep(SLEEPWAIT);}

	if (++counter2 == RECORDINT)

	{

		counter2=0;

		for(int i = 0; i < NUMPIECES; i++)

		{

			cout << currentpos[i] << " ";

		}

		cout << endl;

	}


	int x = 0, y = 1, dx = 1, dy = 1;

	int length = 0;

	if (thegrid[0][0]) return 0;

	do

	{

		if (length%2) //at a vertical line

			{if (thegrid[x/2][(y+dy)/2]) dy=-dy;}

		else //at a horizontal line

			{if (thegrid[(x+dx)/2][y/2]) dx=-dx;}

		x+=dx; y+=dy;

		length++;

	} while ((x%(GRIDSIZE*2)) && (y%(GRIDSIZE*2)));

	return length;

}


void toggle(int x, int y, int ori, int size)

{

	int value = 1-thegrid[x][y];

	if (!ori)

		for(int i = 0; i < size; i++) thegrid[x+i][y] = value;

	else

		for(int i = 0; i < size; i++) thegrid[x][y+i] = value;

}


int check(int x, int y, int ori, int size)

{

	if (!ori)

	{

		if (x+size-1 >= GRIDSIZE) return 0;

		if ((available[x][y] > ((size==1)?1:0)) || (available[x+size-1][y] > ((size==1)?1:0))) return 0;

	}

	else

	{

		if (y+size-1 >= GRIDSIZE) return 0;

		if ((available[x][y] > ((size==1)?1:0)) || (available[x][y+size-1] > ((size==1)?1:0))) return 0;

	}

	return 1;

}


void add(int x, int y, int ori, int size, int num)

{

	int minx = (x-1 < 0) ? 0 : x-1;

	int maxx = (!ori ? x+size : x+1);

	maxx = (maxx >= GRIDSIZE) ? GRIDSIZE-1 : maxx;

	int miny = (y-1 < 0) ? 0 : y-1;

	int maxy = (ori ? y+size : y+1);

	maxy = (maxy >= GRIDSIZE) ? GRIDSIZE-1 : maxy;

	for(int i = minx; i <= maxx; i++)

		for(int j = miny; j <= maxy; j++)

			available[i][j] += num;

}


void printit()

{

	for(int j = 0; j < GRIDSIZE; j++)

	{

		for(int i = 0; i < GRIDSIZE; i++)

		{

			if (thegrid[i][j]) cout << "X";

			else cout << " ";

		}

		cout << endl;

	}

	cout << maxlength << endl << endl;

}

Well so far

Your answer of 76 and the lay-out matches my solution exactly. I am curious to see if your code can find a better one. Impressive work btw

[EventHorizon]

The first test restricted the center 8x8 squares to only be available for the single block mirrors, and that found the 76 length solution.

I tried restricting the center 6x6 squares to only be available to single block mirrors. I then tried restricting the center 8x8 like the first, but allowed a single double to be in the middle too. Neither of these two tests found a better solution.

None of the tests allowed pieces in or right next to corners.

I'd say that odds are it's the best configuration, and that it's the only one that allows that path length.

So, out of curiosity, here's a few questions:

1) Where did you find this puzzle? / How did you come up with it?

2) Why the pieces 4-1 3-2 2-3 1-4? (assuming you came up with it, since they are somewhat arbitrary)

3) How did you find the solution?

[bonanova]

Since the light path can't be re-entrant, that is, loop back on itself,

and then leave the grid, there must be a theoretical upper limit to

the path length - the total length of all possible diagonals.

Wondering what percent of the theoretical maximum the best

solution is ...

[Prof. Templeton]

The first test restricted the center 8x8 squares to only be available for the single block mirrors, and that found the 76 length solution.

I tried restricting the center 6x6 squares to only be available to single block mirrors. I then tried restricting the center 8x8 like the first, but allowed a single double to be in the middle too. Neither of these two tests found a better solution.

None of the tests allowed pieces in or right next to corners.

I'd say that odds are it's the best configuration, and that it's the only one that allows that path length.

So, out of curiosity, here's a few questions:

1) Where did you find this puzzle? / How did you come up with it?

2) Why the pieces 4-1 3-2 2-3 1-4? (assuming you came up with it, since they are somewhat arbitrary)

3) How did you find the solution?

Here's a link

http://diogen.h1.ru/english/puzzle05-4.html

No.12 on the bottom

[CaptainEd]

Since the light path can't be re-entrant, that is, loop back on itself,

and then leave the grid, there must be a theoretical upper limit to

the path length - the total length of all possible diagonals.

Wondering what percent of the theoretical maximum the best

solution is ...

Interesting thought, Bonanova, Since a non-edge square can be traversed a maximum of 2 units (all four diagonal legs), and the entry and exit to the grid take one unit each, an upper bound to the maximum must be 2 * 64 + 2 = 130.

Probably the bound can be tightened by limiting it by the number of reflective faces that can be on the outside...

[CaptainEd]

Here's a tighter bound.

First, imagine a solution with no interior pieces, as they use up valuable travel space.

Look at a ray that comes from one edge piece, reflects off another, and hits a third, such as the ray from A6 to F1 to J5. Its total length is 8, because the endpoints are on A and J.

If an edge piece is completely occupied, its rays total 8 (except for a ray that enters or exits the diagram).

If we totalled all the possible rays, we would count each one twice.

There are only 20 mirror cells available to us. If they were somehow all placed on the edge, and each one was struck by a ray from another, and one ray enters and one ray exits, the rays could have a maximum length of only 2 + 8 * 20 / 2 = 82.

So 76 represents a pretty efficient score.

[EventHorizon]

Here's a tighter bound.

First, imagine a solution with no interior pieces, as they use up valuable travel space.

Look at a ray that comes from one edge piece, reflects off another, and hits a third, such as the ray from A6 to F1 to J5. Its total length is 8, because the endpoints are on A and J.

If an edge piece is completely occupied, its rays total 8 (except for a ray that enters or exits the diagram).

If we totalled all the possible rays, we would count each one twice.

There are only 20 mirror cells available to us. If they were somehow all placed on the edge, and each one was struck by a ray from another, and one ray enters and one ray exits, the rays could have a maximum length of only 2 + 8 * 20 / 2 = 82.

So 76 represents a pretty efficient score.

You need to add in some. This is because of the initial ray.

For instance, if you had only 2 mirror blocks, it could look like this...

This is the maximal one for two blocks without blocks touching each other. If we then add in 8 for each additional 2 blocks we'd get

15.5+ 8*18/2 = 87.5

With just blocks on the edges you'd get closed loops (each of the same length of 16) each using 4 blocks. A single interior block can combine 4 such loops (a block on the diagonal however makes 2 closed loops of 3 formerly closed loops).

So you'd need at least 2 interior pieces to use all the other edge blocks.

Subtracting out the pieces of the closed loops contained in the interior blocks would give 78 in the image if I counted right.

If you simply subtract the contribution of 2 blocks from the earlier number, that would give 79.5.

Perhaps you could just find a minimal number of blocks to move inward one block (and over one space) to connect the loops. Each one would decrease the total length by 2, for the distance of going down one more and coming back up. You'd need at least 5 of these such blocks to connect the 5 different closed loops and subtracting this 10 units of length would leave 77.5.

However, I don't think any of these observations has proven a lower theoretical max. Maybe someone can sure up a proof.

I thought about this earlier, and couldn't bring myself to accept that I had even proven the 87.5 figure. Something seems like it needs to be examined more completely. Like disproving that blocks getting reused (multiple edges used) in the center could provide more distance. That's not saying I don't believe it could be correct, just that I don't think it's a solid proof yet.

"If we totalled all the possible rays, we would count each one twice."

Hmm, that seems useful. I'm going to think about this a bit more in relation to interior pieces and such.

Another possibly useful observation is that every time the beam hits a mirror, only 1 of the cardinal direction components of it's velocity vector is flipped. The other is still continuing towards the edge.

[CaptainEd]

I see, EventHorizon, you've shown me that the entry and exit rays are NOT counted twice, so we get to include them completely, rather than divided by two. So an entry and exit ray passes through an extra cell, adding one to the total, and they also don't get double counted, adding 8 to the total. So my estimated upper bound should have been 18 * 4 + 9 * 2 = 90.

I'm not disputing that 87.5 is a more accurate bound. After all, my approximation imposed no further constraints about non-touching mirrors.

As to the discussion about interior blocks, my intuition (as you said, NOT a proof) is that, aside from the possibility of connecting edges that couldn't have been connected, an interior block REMOVES up to 2 units from a path.

So, I would say that a solution involving 17 edge cells and 3 interior cells could have a pathlength no greater than 84.