Case of the missing crystal eggs. Use rough pseudo code to solve? Edit
CHALLENGE: Case of the missing crystal eggs
The scientists noticed a set of crystal eggs had been stolen when they reported to work early Tuesday morning. Reliable witnesses say the eggs were definitely there on Monday morning. The thieves must have come in sometime between Monday morning and Tuesday morning.
The camera system had been disconnected, but the laboratory had a backup system: a webcam took a picture of the crystals every 5 minutes and stored it securely. Every hour 12 pictures were taken, so in the 24-hour period, 12 * 24 = 288 pictures were taken.
Write rough pseudocode to find out the time of the crime as quickly as possible
Answers
A naive approach would be to just iterate through all the pictures and see when the eggs are gone... what would be a quicker way? Is there any way we can avoid checking some of the pictures?
28 September 2016
This is an example of a search algorithm.How you can search through a list depends upon whether the list is sorted or not. The only way to search through a completely random list is to do so one by one, starting at the beginning and ending at the found position.The list of pictures is actually ordered because the pictures start as a series with the eggs in place and ends with a series with the eggs gone. This means you can use a binary search.First, let us assume we have a function to examine the pictures and determine whether the eggs are in place. Let’s call it FUNCTeggs(index) and assume that it returns a value of TRUE if the eggs are present and FALSE if they are not. In practice this would be a complicated bit of software and might take some time to run, so we need to call it as few times as possible.We will need some other variables as well:upperbound – the upper number in the binary searchlowerbound – the lower number in the binary searchpicnum – the number of the picture we are looking atpic1, pic2 – the results of the search for two consecutive pictures.We are looking for two different results for two consecutive pictures, one with eggs, the next, without eggs. This is found using “pic1 XOR (exclusive OR) pic2” which is only TRUE if the two pictures are different.If unsuccessful we need to decide if we need to go forward along the list or to backtrack. (this is why we need the list ordered) This is decided by “pic1 AND pic2”, if both are TRUE we need to go forwards down the list, otherwise we need to go backwards towards the start. This is done by changing the upper or lower boundary.The “picnum>=287” terminates the loop in the event of a null search. You might want to confirm this condition.upperbound ←288lowerbound ← 1BEGIN LOOPpicnum ← INT((upperbound+lowerbound)/2)pic1 ← FUNCTeggs(picnum)pic2 ← FUNCTeggs(picnum+1)IF pic1 XOR pic2 THEN exit loopIF picnum >= 287 THEN exit loopIF pic1 AND pic2 THEN lowerbound ← picnum ELSE upperbound ← picnumCONTINUE LOOPA simple search, if the FUNCTeggs() function takes 5 minutes, might take up to 24 hours to fullfil (288 calls). With this binary search the FUNCTeggs() will be called a maximum of 18 times which would mean a maximum of an hour and a half. This routine will call FUNCTeggs() multiple times for the same picture during a search so a method of producing a trail of results is needed to avoid this.On a successful exit “picnum” contains the number of the last picture that contains the eggs.
28 September 2016
Add an answer
Similar questions