RAID-5 Use Your Witz

The 4 waypoints with the clues have gone missing. However, now you can look at the description for Waypoints B, C & D for the code numbers you would have found at the waypoints!

6/8/2007: Congrats to Claudey for being the first to find the cache with the revised clues!

06-06-2007 Note! All 4 of the clues are updated and replaced and ready to go!
The new calculated coordinates should (hopefully!) put you closer to the cache than the old clues (it had been about 50 feet away - you should be within 20 feet away if I did it correctly!)
Changed hide date from original: 12/14/2005 to 6/6/2007.

I wanted to make a puzzle cache that people could find even if they had trouble finding one of the waypoints. And it turns out, there is a method for storing computer data that does just that: RAID-5(Wikipedia).

RAID stands for Redundant Array of Independent Disks, also known as Redundant Array of Inexpensive Disks. To solve the puzzle for this cache, you will learn how RAID-5 works.

Here is my version of how RAID-5 works - little did you know that this cache had educational value!

Let's say there is a lot of data to store, and there are 4 drives to store the data on:

There are a couple of disadvantages with this system. The first is that if one drive goes down, 1/4th of the data is lost. Another disadvantage is that a file usually is only on one drive, so all the data has to come from one disk, and the other 3 are idle.

Some of the other RAID specifications deal with the speed and others deal with storing the data redundantly. For example, RAID-0 says to stripe the data across the disks:

This means reading a file is faster, because a chunk is read from each disk, allowing the file to be read or written more quickly. But if 1 disk is lost, any files that have a block on failed disk are lost.

RAID-1 says to mirror the data - so 2 copies of the data are stored, with one drive being a complete copy of the other:

In a four disk system, that cuts the storage in half, and there is not normally a speed advantage of being able to read from multiple disks at once. But it is the simplest way to implement redundancy, or 'Hot Backup' for disks (I might even make a RAID-1 cache at some point). If one disk fails, the other disk in the mirror continues to provide the data with no impact to the system. In systems where a disk can be replaced without powering down the system, the system can copy all the data back to a new drive on the fly.

RAID-5 is a compromise to give the most storage, and the best speed, with redundancy. And versions of this are used in all sorts of server applications.

The data is striped across the disks for performance. For example, reading file ABC, the data comes from disk A, B and C. When the data for ABC is written, a recovery block (shown as CRC in this case), is written to disk D. This recovery block is used to recreate the data if a disk fails.

Let us say for example, that disk C fails:

The system will immediately recognize that the disk has failed, and will emulate the missing disk by calculating the missing blocks:

So reading file ABC - block A is read from Disk A, block B is read from disk B, and block C is calculated by reading CRC1 from disk D, and using the data from blocks A, B & CRC1 to calculate the data from block C.
There is a performance impact when running this way - but the calculation is pretty fast. In the case of reading DEF, there is no performance impact for this set of data, as it just ignores the missing CRC2.

RAID-5 can be implemented with any number of disks, not just the 4 I've shown graphically. But the more disks you have, the more vulnerable the system is to having a second disk fail before the first is replaced. There are methods to deal with that such as hot-spares (empty drives that the system can automatically mount up if one disk fails) and variations of multiple CRC volumes. But I'm only talking about the most straightforward version of RAID-5.

The method used to calculate the CRC in the first case, and to recover missing blocks when a disk fails, is called XOR - or Exclusive-OR. This is very easy for computers to calculate:

If there is 0 and 0 or 1 and 1 coming in, there is 0 coming out. If the bits mismatch, 1 and 0 or 0 and 1, there is a 1 coming out of XOR.

Applying this to bytes of data, it allows the creation of a recovery-block - also it can recover any one missing block.
In the example above, A xor B xor C = CRC1.
A xor B xor CRC1 gives the value for C.
A xor CRC1 xor C gives the value for B.
CRC1 xor B xor C gives the value for A.
And this works in any order: C xor CRC1 xor A still gives the value for B

For this puzzle cache, I have simplified the calculations. Instead of having to work with the encoding of characters in a block, with 8 or 16 bits per character, I have encoded this cache with 4 bits (using only decimal numbers). And to make it even easier, I am giving you a lookup table for the 16-by-16 possible XOR values:

View or right-click to download
You can look up in either order - you can start with the first number on the top or on the left. Then use the second number with the opposite. Meet at the grid-point, and you get the XOR value for those 2 numbers.

In the example above, let us assign: A=3, B=6, C=9. Start with A xor B: 3 xor 6 = 5; then take the 5 and xor it with C: 5 xor 9 = 12. The CRC1 is 12.
Solving for each missing value:
Find C: A xor B xor CRC1 = C: 3 xor 6 = 5; 5 xor 12 = 10; C = 9!
Find B: A xor CRC1 xor C = B: 3 xor 12 = 15; 15 xor 9 = 6; B = 6!
Find A: CRC1 xor B xor C: 12 xor 6 = 10; 10 xor 9 = 3; A = 3!

To find the final cache, you will have to calculate the missing values from the failed disk (missing waypoint-clue). I am not going to remove one of the waypoints-clues; I am going to let you decide which waypoint to skip.
You might be tempted to find all 4 waypoints so you don't have to calculate the missing clue. But that is breaking the rules of this puzzle. To that end, I have done 2 things to motivate you to solve the puzzle the correct way. First, the 4 waypoint-clues are spread really far apart - it would take you as long or longer to go to the fourth clue as to do the calculations. Second, I am suggesting that you to do an additional calculation to prove you did the XOR calculations and the proof will tell me which waypoint-clue you skipped.

To make the calculations easier, I have created a set of worksheets to help you calculate the location of the final cache.

Printable Worksheets on a page
Or view/print each of the four worksheets separately:
Collected and Calculated Worksheet
Missing Blocks Worksheet
Final Coordinates Worksheet
Proof Worksheet

I have also created instructions/examples to use the worksheets: Example

In summary, you will want to:
Take a printout of the worksheet page, and a version of the XOR 16x16 look-up matrix with you.
Pick out which 3 waypoint-clues you are going to find.
Write in the values from the 3 waypoint-clues onto the worksheet.
Calculate the missing values, the cache coordinates, and the proof.
Visit the cache, sign the log.
Log your visit to the cache on the geocaching.com site.
Optionally, send us an email (through geocaching.com) with the proof value and the waypoint-clue you skipped (A, B, C or D). And any direct comments.

Please do not post any hint values in your online logs - even encrypted

There are 2 First-To-Find gifts in the cache for the first 2 people/teams to find the cache. Please take only one - first FTF get to chose. The items are of the same base value, although one has the potential to be worth a whole lot more ;-)

Final cache solution is within the bounds of the 4 listed Coordinates - if you calculate outside this area, try again! :)

All the points are designed to be accessed via a 'secret' path (see also GCQP3X)

Update 6/6/2006 - I finally got the other 3 update clue markers replaced last night. The puzzle is ready to go again. I have decided to change the listed coordinates for this puzzle to a nearby parking place. This means any travelbugs will get more accurate milage.
I have reduced the difficult/terrain to 2.5/3.0 because this puzzle is not that hard. Some people were intimidated by all the pages of math. I have moved the sample math to a seperate web page. Note: most people who have done this puzzle report that it is pretty straightforward and really is worth doing the math than going after the 4th coordinate.
Also I will add solver web page as well.

Update 3/27/2006 - included 50'NW info, updated encrypted hint, added a little more description to end, and dropped difficulty from 3.5 to 3.0 - it comes up as a 4.0/4.0, but it isn't that hard - also FTF prizes are gone, but there are still plenty of good trade items!

You can check your answers for this puzzle on Geochecker.com.

Additional Waypoints

PARMPE - Point-A
N 38° 55.866 W 104° 50.235
GCRMPE - Waypoint-A - find 3 of 4 of these waypoints - maps.google:http://maps.google.com/maps?f=q&hl=en&q=N+38%C2%B0+55.866+W+104%C2%B0+50.235&t=h
PBRMPE - Point-B
N 38° 54.936 W 104° 45.075
GCRMPE - Code B - B: 3-0-1-4-9
PCRMPE - Point-C
N 38° 56.787 W 104° 43.729
GCRMPE - Code C - C: 8-1-3-6-3
PDRMPE - Point-D
N 38° 58.587 W 104° 46.314
GCRMPE - Code D - D: 5-6-0-6-1
PKRMPE - Parking for RAID-5 GCRMPE
N 38° 57.162 W 104° 47.059
New puzzle coordinates and parking for final