https://stackoverflow.com/questions/21653696
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianThat sounded like an interesting problem. The commment from @Xavier Holt could be pretty important: "A beam can never be reflected indefinitely". Every data structure that aims at tracking the visited fields (that is, checking whether a certain field was visited twice) could - in the worst case - significantly slow down the whole thing.
A graph-based approach, as suggested by mcdowella, could be feasible here. But since the rules of how the beam moves through the grid of mirrors are quite simple (and, as mentioned above, cycle detection etc. are not necessary), one can boil this down do walking through a 2D array. The current state is then represented by the current position (x,y), and the current direction (dy,dy), which is updated according to each mirror type that is encountered.
I just implemented this (in Java). The computeResults method computes a list of 5-element int[] arrays, where
- result[0] = Entering x-coordiante
- result[1] = Entering y-coordiante
- result[2] = Entering x-direction
- result[3] = Entering y-direction
- result[4] = Number of steps until the mirror field is left
The "core logic" is in the simulate method.
Some parts (especially the part that renders the field and the solution path into a frame) are rather quick & very dirty, but maybe someone finds it interesting anyhow. In any case, it computes the solution of a 2000x2000 grid in a few seconds on a very old PC.
import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class MirrorTracer
{
public static void main(String[] args)
{
//basicTest();
largerTest();
}
private static void basicTest()
{
String input =
"SBB" +
"BBB" +
"SBS";
int sizeX = 3;
int sizeY = 3;
int array[][] = createArray(input, sizeX, sizeY);
// int n = simulate(array, 2, 0, 0, 1);
// System.out.println(n);
List<int[]> results = computeResults(array, sizeX, sizeY);
printResults(array, sizeX, sizeY, results);
}
private static void largerTest()
{
int sizeX = 60;
int sizeY = 60;
int array[][] = createRandomArray(sizeX, sizeY, new Random(0));
List<int[]> results = computeResults(array, sizeX, sizeY);
printResults(array, sizeX, sizeY, results);
showResult(array, sizeX, sizeY, findBestResult(results));
}
private static List<int[]> computeResults(int array[][], int sizeX, int sizeY)
{
List<int[]> results = new ArrayList<int[]>();
for (int x=1; x<sizeX+1; x++)
{
results.add(compute(array, x, 0, 0, 1));
//results.add(compute(array, x, sizeY+1, 0, -1));
}
for (int y=1; y<sizeY+1; y++)
{
results.add(compute(array, 0, y, 1, 0));
//results.add(compute(array, sizeX+1, y, -1, 0));
}
return results;
}
private static int[] compute(int array[][], int x, int y, int dx, int dy)
{
int nx = x + dx;
int ny = y + dy;
int n = simulate(array, x, y, dx, dy);
return new int[]{ nx-1, ny-1, dx, dy, n };
}
private static int simulate(int array[][], int x, int y, int dx, int dy)
{
int steps = 0;
while (true)
{
int nx = x + dx;
int ny = y + dy;
if (isOnBorder(array, nx, ny))
{
break;
}
//System.out.println("Move from "+x+" "+y+" in "+dx+" "+dy+" to "+nx+" "+ny);
int ndx = dy;
int ndy = dx;
if (array[nx][ny] == '/')
{
ndx = -dy;
ndy = -dx;
}
x = nx;
y = ny;
dx = ndx;
dy = ndy;
steps++;
}
return steps;
}
private static boolean isOnBorder(int array[][], int x, int y)
{
return
x == 0 || x == array.length - 1 ||
y == 0 || y == array[x].length - 1;
}
private static int[][] createArray(String input, int sizeX, int sizeY)
{
int array[][] = new int[sizeX+2][sizeY+2];
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
char c = input.charAt((x-1) + (y-1) * sizeX);
array[x][y] = c == 'S' ? '/' : '\\';
}
}
return array;
}
private static int[][] createRandomArray(
int sizeX, int sizeY, Random random)
{
int array[][] = new int[sizeX+2][sizeY+2];
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
boolean b = random.nextBoolean();
array[x][y] = b ? '/' : '\\';
}
}
return array;
}
private static void printResults(
int array[][], int sizeX, int sizeY, List<int[]> results)
{
print(array, sizeX, sizeY);
for (int result[] : results)
{
printResult(result);
}
int bestResult[] = findBestResult(results);
System.out.println("Longest sequence:");
printResult(bestResult);
}
private static void print(int array[][], int sizeX, int sizeY)
{
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
System.out.print((char)array[x][y]);
}
System.out.println();
}
}
private static int[] findBestResult(List<int[]> results)
{
int maxLength = -1;
int maxLengthResult[] = null;
for (int result[] : results)
{
if (result[4] > maxLength)
{
maxLength = result[4];
maxLengthResult = result;
}
}
return maxLengthResult;
}
private static void printResult(int result[])
{
int x = result[0];
int y = result[1];
int dx = result[2];
int dy = result[3];
int n = result[4];
System.out.println("Entering at "+x+" "+y+" in direction "+dx+" "+dy+" does "+n+" steps");
}
private static void showResult(
final int array[][], final int sizeX, final int sizeY,
final int bestResult[])
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI(array, sizeX, sizeY, bestResult);
}
});
}
private static void createAndShowGUI(
final int array[][], final int sizeX, final int sizeY,
final int bestResult[])
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
JPanel resultPanel = new JPanel()
{
protected void paintComponent(Graphics g)
{
super.paintComponent(g);
int cellSizeX = getWidth() / (sizeX+2);
int cellSizeY = getHeight() / (sizeY+2);
g.setColor(Color.BLACK);
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
int x0 = x * cellSizeX;
int y0 = y * cellSizeY;
int x1 = x0 + cellSizeX;
int y1 = y0 + cellSizeY;
if (array[x][y] == '/')
{
g.drawLine(x0+2, y1-2, x1-2, y0+2);
}
else
{
g.drawLine(x0+2, y0+2, x1-2, y1-2);
}
}
}
g.setColor(Color.RED);
int dx = bestResult[2];
int dy = bestResult[3];
int x = bestResult[0]-dx+1;
int y = bestResult[1]-dy+1;
paintSimulation(g, array, x, y, dx, dy, cellSizeX, cellSizeY);
}
private int paintSimulation(
Graphics g, int array[][], int x, int y,
int dx, int dy, int cellSizeX, int cellSizeY)
{
int steps = 0;
while (true)
{
int nx = x + dx;
int ny = y + dy;
int x0 = x * cellSizeX + cellSizeX / 2;
int y0 = y * cellSizeY + cellSizeY / 2;
int x1 = nx * cellSizeX + cellSizeX / 2;
int y1 = ny * cellSizeY + cellSizeY / 2;
g.drawLine(x0, y0, x1, y1);
if (isOnBorder(array, nx, ny))
{
break;
}
int ndx = dy;
int ndy = dx;
if (array[nx][ny] == '/')
{
ndx = -dy;
ndy = -dx;
}
x = nx;
y = ny;
dx = ndx;
dy = ndy;
steps++;
}
return steps;
}
};
f.getContentPane().add(resultPanel);
f.setSize(800,800);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
