Algorithms for unlocking device

[rooftopsparrow]

This issue is a continuation of the discussion we had in class about proposed algorithms for solving the 4 bit lock 2 bit peek device problem.

Keep in mind the requirement that the program must halt ( meaning the unlock() method returns false if unable to to unlock ).

[rooftopsparrow]

My proposed algorithm was pretty basic. We want to figure out if we want to unlock by setting all bits to false, or all bits to true, then keep spinning until we set all the bits (max tries tbd).

1. Spin the lock
2. If unlocked: return true
3. If "goal" isn't set: peek the first two bits
   1. if both bits are both true, set "goal" to true.
   2. if bits are different, set "goal" arbitrarily.
   3. if bits are both false, set "goal" to false.
4. Set bits to goal. ( possible to skip this if both bits already are set to "goal" )
5. Rotate peek bits two over and repeat.

[rooftopsparrow]

Possible modification to number 3 of my algorithm would be to spin the lock ( up to a certain number of times ) until there are a majority of bits.

The "worst case" for the spins end up would be:

[ T F T F ]
[ F T F T ]
[ T F F F ]
[ F T T T ]

[hdemarco4]

Yeah, the best I could come up with is to brute force it, "peek" and "poke" for every "spin". I'm not sure about where to halt it. I think the worst cases would still be the same. We might need to randomize which ones we "peek" and "poke" at some point.

[Mojac]

I was thinking maybe we could have a threshold to determine when to peek different indexes. For example: Arbitrary numbers are used in this example. All division is floored (chop off all decimals)

1. We create, spin, peek first two [? ? - -], and poke [T F F F] to [T T F F]. Set threshold to 100 (byte data type, maybe?).
2. Spin, peek the same two indexes (first two for first iteration [? ? - -]).
   If we peeked [T T - -] we divide threshold by 2.
   If we peeked [T F - -] or [F T - -] we divide threshold by 1.5. Then poke all to true.
   If we peeked [F F - -] we set threshold to 100. Then poke all to true.
3. If threshold (100 or lower number from above) is less than 15 (arbitrarily chosen threshold). Then make threshold = 100 and change peek indexes (maybe shift right, so first change of peek indexes will result in [- ? ? -]).
4. If all indexes aren't true. Then repeat steps 2 through 4.

With this, we could make sure it haults by putting a cap on how many times step 3 resets the threshold to 100. The numbers above are just for example, we might want to play around with efficiency to determine good values for: thresholdBase (100), thresholdLimit (15), resetThreshCap (30?), divide by 2, divide by 1.5.

[hdemarco4]

Unfortunatly, I think that you can't poke just one value. You have to poke everything that you saw in the peek. So for your 1. if you peek [? ? - -], and find [T F - -]: if you poke that you get [F T - -].

[rooftopsparrow]

I don't think thats true @hdemarco4. The javadoc spec says you can supply the any boolean values in the pattern to poke.

[arcturas1]

@hdemarco4 You must poke exactly as many bits as exist in the peek, but you need not actually change the observed values from what they were. For example, if you Peek [??--] and get [TF--], you can just poke [TT--], which leaves the pattern's T in tact, which changing it's F.

[arcturas1]

My original approach looks at the problem as follows:
Let us blindly assign a goal of setting all bits to T. Since we can't track bits, trying to minimize work by building the machinery to set goals dynamically doesn't make much sense to me, and trying to figure out what your goal "should be" would take up more spins than just imposing a goal from the start (at least for the given 2-bit/4-disclosure device).

Now, assuming that the device is not already unlocked, then there are 14 possible bit patterns it could start from, all of which contain at most 3 F's. Then, following the first Spin-Peek-Poke cycle, we are guaranteed to have at least 2 of the bits set to T. Assuming the rotations are true random, then if we peek any two bits (might as well always be the first 2), the odds of any remaining F bits showing up within our peek window is 2/4, or 1/2. If n = the number of spins we perform, then the probability of any remaining F not showing up after n spins is 1/2^n. So, if we perform, say, 10,000 spin-peek-poke cycles, then the odds of the F not having shown up within our window is infinitesimally small. At this point I would say just perform one more spin-peek-poke, this time at the last 2 bits, which would only not succeed in unlocking the device with probability of approximately 1/2^(n+1), but 10,001 tries in machine time is pretty low, so we can repeat this a few times to make the odds even better.

Oh, and the spin-peek-poke loop stops as soon as spin returns true.

Combining this approach with the threshold approach makes the point at which we switch our peek window a bit less arbitrary, so I'm down with that, but it does so at the cost of building additional machinery that may be unnecessary.

I do like the threshold approach, though, and if we want to see if it's necessary to introduce or improves our performance over an approach that needs less code to implement, then I would suggest a very high threshold that decreases somewhat slowly to take advantage of the stochastic properties of the problem

[rooftopsparrow]

I'd vote going simple and improve with thresholding to speed up success.

Another thing to note @arcturas1 is that we cannot assume "true random" as Dr. Paul said there was no way to know if it is in fact random or if it is an "arbitrary rotating algorithm". I think its safe to assume "random" for the short run, but not a long term solution, where the thresholding makes a lot of sense to me.

[tgolnoft]

Boy I hope 10000 tries gets it haha.

As to the randomness of the rotating algorithm, what if rather than starting at the first two indexes and shifting based on the threshold what if the algorithm picked random indexes each time? It'd be a simpler implementation and should achieve the same thing. We could then gate the number of iterations at some number almost certain to find the solution to ensure it halts.