StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhat is the optimal Jewish toenail cutting algorithm?
text
Body
copied!<p>I am working on the software for a machine that will automatically trim toenails, so that users can simply put their feet in it and run it instead of having to manually do it by biting them or using nail clippers.</p> <p>A sizeable percentage of our potential user base will likely be Jewish, and, evidently, there is a <a href="https://judaism.stackexchange.com/questions/1301/trimming-toenails-in-sequence">tradition about not trimming toenails</a> (<a href="https://judaism.stackexchange.com/questions/1118/rules-for-cutting-nails">or fingernails</a>) in sequential order </p> <p>There seems to be dissenting opinion on the precise application of this tradition, but we think that the following rules are sufficient to accomodate people whose religious practices prohibit cutting toenails in order:</p> <ul> <li>No two adjacent toenails should be cut consecutively</li> <li>The cutting sequence on the left foot should not match the sequence on the right foot</li> <li>The cutting sequence on two consecutive runs should not be the same. The sequences shouldn't be easily predictable, so hardcoding an alternating sequence does not work.</li> </ul> <p>This is how we have decided to number the toes:</p> <pre><code>5 4 3 2 1 1 2 3 4 5 Left foot Right foot </code></pre> <p>I have written code to solve the problem, but the algorithm used is sub-optimal: in fact, the worst case performance is <strong>O(∞)</strong>. The way it works is comparable to <a href="http://en.wikipedia.org/wiki/Bogosort" rel="nofollow noreferrer">bogosort</a>. Here is a pseudocode simplification of the actual code used:</p> <pre class="lang-default prettyprint-override"><code>function GenerateRandomSequence sequence = Array[5] foreach (item in sequence) item = RandomNumberBetween(1,5) return sequence function GetToenailCuttingOrder while (true) sequence = GenerateRandomSequence() if (!AllItemsAreUnique(sequence)) continue if (NoTwoAdjacentItemsHaveConsecutiveNumbers(sequence)) return sequence do leftFootSequence = GetToenailCuttingOrder() rightFootSequence = GetToenailCuttingOrder() until (leftFootSequence != rightFootSequence && leftFootSequence != leftFootSequenceFromLastRun && rightFootSequence != rightFootSequenceFromLastRun) </code></pre> <p>Basically, it generates random sequences and checks if they meet the criteria. If it doesn't meet the criteria, it starts over. It doesn't take a ridiculously long amount of time, but it is very unpredictable.</p> <p>I realize that the way I am currently doing it is pretty terrible, but I'm having trouble coming up with a better way. Can any of you suggest a more elegant and performant algorithm?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload