A friend asked for help reaching the next level of a puzzle game. The test which stalled her involves machine placement in a sausage factory.
… each sausage was branded with a letter for quality control purposes, thus: ypbtkizfgxptclcoirdsuhjwulqkoszrabfc
The string was then drawn through seven machines which rearranged the sausages in flavour enhancing ways.
Machine A: The Reversifier
Reverses the order of the sausages, so they get tastier as you go along.
Machine G: Secondhalffirstifier
move the second half of the string to the beginning, as the earlier sausages are too spicy to eat early in the morning.
He attached these machines in a certain sequence, though one of them was out for repair so only six were used. He then fed a string of sausages through and was surprised to discover the string that came out at the other end said lickyourlips. What order were the machines in?
It’s nicely phrased, but what’s really wanted is the sequence of simple transformations that takes input “ypbtkizfgxptclcoirdsuhjwulqkoszrabfc” and produces output “lickyourlips”.
It’s no doubt possible to work backwards and figure out a solution using no more than logic, pencil and paper. For example, only two of the machines change the length of the string, and — looking at the before and after lengths — these must both be used. It’s rather easier to write a short program to find a solution.
First we must simulate the seven sausage machines, A-G, which perform the following sequence operations.
- reverse the order of a sequence
- remove every other element of a sequence
- remove every third element of a sequence
- pairwise reverse elements of a sequence
- move even numbered elements to the front of a sequence
- move the last element of a sequence to the front
- swap the front and back half of a sequence
None of these is difficult, especially in a high-level language which builds in support for sequence operations. What I found noteworthy is that a solution can be found without any loops or if statements. What’s more, every operation can handled using nothing more than slice operations.
Here’s my solution. The machines consist of slice operations, helped by a couple of conditional expressions and recursive calls. The solution can then be brute-forced: there are only 5040 ways of permuting 6 out of 7 machines.
reduce to apply a chain of functions to a string of sausages — an explicit loop might be clearer, but I want a loop-free solution. For this same reason I use recursion in the pairwise swapper and the element dropper. Generally in Python, recursion is a poor choice. In this case I know I’m starting with a string of just 36 elements which cannot get any longer; there’s no risk of exceeding the system recursion limit.
The sequence reversal
s[::-1] is idiomatic but alarming to the uninitiated. Slices have
[start:stop:stride] fields, any of which may be defaulted. Usually
stop default to the start and end of the sequence, but in this case the negative stride reverses them.
To rotate the last element of a sequence to the front, prefer:
return s[-1:] + s[:-1]
return [s[-1]] + s[:-1]
because the latter raises an
IndexError for an empty sequence.
Slicing is a formidable tool for sequence manipulation, especially when combined with the option of using negative indices to count back from the end. Slices allow you to reverse, rotate and partition sequences, to pairwise swap elements, and to drop every nth element.
The miniature recipes presented here don’t even use slice assignment, which gives me an excuse to reproduce this elegant prime sieve function, which does.