1. Computing

Programming Challenge 69 - Black Box

Completed

By

Black Box Reflections

Parker Brothers have a game called Black Box which this is loosely based on but it's not the same rules.

This does have a box that's a 8 x 8 square with 8 openings on each of the four sides. In the box are 64 windowed compartments (so light can shine through all the way from top to bottom and left to right) and each compartment can take a two sided mirror angled at 45 degrees in either of two orientations / or \.

An automatic scanner shines a light through each of the 32 openings and records out of which opening the light emerges. If it passes straight through then a 0 is recorded for the entry and exit opening.

If however the light emerges from a different opening (other than directly opposite) it is given a value, 1 for the first beam, 2 for the second etc.

Note the following:
  • Light will always emerge from a different opening to the entry.
  • If light hits a mirror, it's deflected 90 degrees.
  • Light must always emerge. There's no configuration possible to trap it.
  • Openings and exits are the same if swapped. If it enters at a and exits at b then if it enters at b it will exit at a.
  • If the beam emerges from the opening opposite but has a non-zeo value then it's not a straight through path. It has bounced off a multiple of 4 mirrors.

Mirrors

For a \ mirror, a beam from the West will go South, a beam from the East will go North. For a / mirror a beam from the West will go North, a beam from the East will go South. What'd you'd expect!

An Example

There are two mirrors in the box below.

 01001000
0........0
0........0
0........0
0........0
2.\../...3
0........0
0........0
0........0
 02003000

Here there are three paths, 1, 2 and 3. Path 1 goes straight down South to the left mirror, bounces Rast towards the right mirror and then North and out the top. Path 2 from the West bounces off the left mirror and goes South and exits at the bottom and path 3 enters from the bottom and goes North, bounces off the right mirror and then goes East and exits out the right hand side.

The Contest

You are given ten mirror puzzles to solve. Each puzzle is a 32 character string with up to 15 paths allowed per puzzle. So the characters are 0-9,A-F.

The characters are ordered in four blocks of 8 chars running top, right, bottom,left, one per side and characters running left to right and top to bottom. So the grid above would be:

Top------Right----Bottom---Left
01001000 00003000 02003000 00002000

I've added spaces to make it easier to identify but the inputs below do not have spaces.

To solve all the puzzles your program has to read the ten inputs then identify where the mirrors are and their orientation / or \.

For each puzzle, output the 8 x 8 grid like above showing the mirrors and paths.

The above as input an would look like this:

01001000000030000200300000002000

The output for that should be:

 01001000
0........0
0........0
0........0
0........0
2.\../...3
0........0
0........0
0........0
 02003000

The Challenge Inputs

I've changed it to be 10 instead of the original five. Here's the input.

03000300002000000100020000100000
04104000005020000350200000103000
04302000010600500160500002030040
04000040010500500200001003030020
22000504340000601700060513000070
05210A000A2907630640079001380854
12B30A90A9B040870506087023401056
5610300A30067902A810200940057804
02077020030340400508805001016060
10066008708400034002300750510002

Winning Criteria

You get 2 points for each correctly placed mirror, -1 for each one wrong. Highest score wins.

Final Results

Thank you to Arun Prakash M, Mark Mammel, Michael Chock and Ron Spain for entering. There were two errors in the input file so I think its only fair to call this a draw. The order is alphabetically sorted on first name. below.

One of the flaws was a missed pair of digits, but the other was tricky. A mirror that could be removed and didn't affect the actual values.

The missed pair of digits was puzzle 6 with 05210AB00A290763064B079001380854. The optional mirror / was in puzzle 5 at position (sixth column,second column).

Here are the ten puzzles (corrected- thanks Arun) in csv format.

  1. Arun Prakash M(C#) Result=Draw (India,32)
  2. Mark Mammel(C++) Result=Draw, (USA,)
  3. Michael Chock(C++) Result=Draw
  4. Ron Spain(C) Result=Draw, (USA,34)

General Tips on Entering

This is a single page article with tips on things to do and not do when entering challenges. Please read it!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Contest 69 email address with the subject line Programming Contest 69.

It must compile with Open Watcom, Microsoft Visual C++ 2010/2012 Express Edition/Microsoft Visual Studio 2010/2012, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is May 5, 2013.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 69 - Black Box

©2014 About.com. All rights reserved.