1

First off I should state that I'm not a mathematician, I'm a programmer (Python, Javascript). But I thought this was more of a mathematical question than a programming one, so I'm asking it here.

I want to write a program that accepts a simple "secret knock" input, in the form of a defined sequence of mouse clicks/key presses with pauses between them. Imagine the rhythm of "shave and a haircut, two bits" from Who Framed Roger Rabbit. If I accept that the speed of the "knock" input might vary, I imagine that to figure out the "correctness" of the knock, I need to make a relative comparison of the gaps between the clicks/keypresses.

If I record a knock as a sequence of integers representing the current time (in ms) for every click/keypress, what would be a suitable mathematical way to compare the similarity of two such sequences, e.g. my recorded "correct" answer vs another input attempting to reproduce the knock? I'm guessing some sort of normalising would be required so that, for example, a knock that's half the speed but the correct rhythm would still pass.

Any advice appreciated! Many thanks for reading, and if I can clarify any of the above, please let me know.

BigglesZX
  • 113

1 Answers1

1

If the knocker were accurate enough to make the numbers of milliseconds exactly in the correct ratio, then you could just divide through by the greatest common divisor of all the gap durations; this would result in a sequence of small integers representing the relative lengths of the gaps. For example, the four gaps in "shave and a haircut" have relative durations 2:1:1:2 (or 3:2:1:3 or 4:3:1:4, depending on the rhythm you prefer for the "and a" beat).

In practice, you probably won't have that level of accuracy. I suggest that you divide through by the shortest gap length, resulting in perhaps complicated fractions that accurately record the relative gap durations; then do a continued fraction expansion on each resulting fraction (which is essentially doing the same Euclidean algorithm you'd use to calculate the greatest common divisor) and take one of the early convergents. If all the gap durations are an integer multiple of the shortest gap duration, this is just rounding the fractions off to the nearest integer, which already works for many secret knocks (including "shave and a haircut"); but the continued fraction approach allows for a little more flexibility. Of course you'd have to figure out how much error tolerance to allow, etc.

Greg Martin
  • 78,820
  • Thanks for your answer, Greg! That sounds like the right track. Would you mind walking me through the calculations in a little more detail? In my implementation, I've got as far as recording the gaps and doing the initial division by the smallest to produce a normalised list. I understand Euclid's algorithm but haven't quite got my head around continued fractions yet! Thanks. – BigglesZX Apr 02 '14 at 22:07
  • I figured out how to get the Euclidian Distance between the two sets and that seems to be working for now! I'll accept your answer. Thanks again. – BigglesZX Apr 03 '14 at 12:46