In my previous post I challenged you to solve The Power of Substitution. This problem presents us with a substitution cipher, and asks how many times we would have to iterate the encoding process in order to turn a given message into a given encryption.

## A non-solution

Several commenters mentioned that they tried some sort of straightforward brute force approach: just iterate the encoding process and count how many iterations are needed to reach the specified encryption. This certainly works for the provided sample inputs. However, I hinted that this approach likely wouldn’t fit within Kattis’s time limit for the other, secret, test cases.

How did I know this solution would exceed the time limit? It is *not* just an issue of using efficient data structures! Even if someone told me they coded this straightforward solution in C++, I would have the same reaction. The problem specifies that the answer should be at most —and, as we will see, it is not hard to come up with test cases where the answer is indeed that large—and the simple fact is that counting to and applying the encryption at each step (which requires iterating through a list of length 200) is definitely going to take more than 1 second. A useful rule of thumb that I learned from Competitive Programming 3 is operations per second. (Of course your processor can carry out much more than *instructions* per second, but in practice this rule of thumb seems to work remarkably well for predicting run times up to the right order of magnitude.)

## Cycle decomposition of permutations

The given encoding, of course, is a *permutation* (the problem specifies only that it will be *one-to-one*, but any one-to-one endofunction on a finite set must in fact be a permtuation). Let’s call it . If we start with an arbitrary and repeatedly apply —that is, —what happens? Of course, because of the pigeonhole principle, the sequence must eventually repeat. But actually, something stronger is true: because is a permutation, the first repeated value must be itself. For suppose that was the first repeated value in the sequence. But then since is one-to-one, it must be the case that as well, which means , and so on up to .

So in fact if we start at an arbitrary and iterate , we will find a cycle that includes (including the possibility of a trivial length-1 cycle if ). If there are other elements not included in ’s cycle, we can pick any one of them and repeat the process to find another cycle (which can’t possibly overlap at all with ’s cycle—do you see why?). In general, any permutation can be decomposed in this way into a collection of disjoint cycles.

## CRT to the rescue

This idea of cycle decomposition is the key to unlocking the problem. Think about what happens to a particular letter in the message, which we eventually want to become . This will happen after applying the permutation some small number of times , such that . (In general, of course, it would be quite possible that and are not in the same cycle at all, and so will never turn into no matter how many times we apply ; but the problem statement guarantees that this will not be the case.)

The problem, of course, is that all the other letters may not be encrypted properly after only encryption steps, in which case we need to keep going until all the cycles line up. Suppose and are in a cycle of length . That means applying the encryption times to will result in again (and not before). Thus, we will get after steps and then every steps thereafter (); in other words, the number of encryption steps must be equivalent to .

Every position in the message yields a similar modular equivalence, giving us a system of up to 200 simultaneous modular equivalences which we can solve using the generalized Chinese Remainder Theorem. Incidentally, this is why the solution can be so large—if we have cycles of sizes , then it could take up to iterations for them to all line up. In the special case that all the cycle sizes are relatively prime, this is just their product. So for example we could have cycles of sizes , which add up to exactly ; the product of these is the primorial .

## My solution

Here is my solution. We’re going to use an unboxed array to represent the permutation, and the implementation of GCRT from a previous post.

```
{-# LANGUAGE RecordWildCards #-}
import Control.Arrow
import Data.Array.Unboxed
import NumberTheory
import Scanner
```

Here’s `main`

, along with a data type to represent a single test case and a `Scanner`

for reading one in. I like using record syntax to help me remember which field is which, combined with the `RecordWildCards`

extension to unpack the data structure and get the field names as local variables.

```
main = interact $
runScanner (numberOf tc) >>> map (solve >>> show) >>> unlines
data TC = TC { message :: [Int], crypt :: [Int], subst :: [Int] }
deriving Show
tc = do
l <- int
TC <$> l `times` int <*> l `times` int <*> 100 `times` int
```

We’re going to represent a permutation as an unboxed array, which gives us nice constant-time lookup. I often use `Data.Array`

or `Data.Array.Unboxed`

to represent read-only information (which comes up a lot more than you might think!), giving all the benefits of fast array access with none of the complications of mutability.

`type Perm = UArray Int Int`

The *distance* between and is simply the number of times we have to apply to get from to . Of course this definition would hang if and are not part of the same cycle, but we know they will be. Given `dist`

, we can also find the length of a cycle containing as one more than the distance from to . (We can’t just ask for the distance from to itself since that would return .)

```
dist :: Perm -> Int -> Int -> Int
dist p i j = length $ takeWhile (/= j) (iterate (p!) i)
cycleLen :: Perm -> Int -> Int
cycleLen p i = succ $ dist p (p!i) i
```

Finally, we can put these pieces together: create an array for the permutation, zip together the message and desired encryption, generating a modular equivalence for each, and solve the resulting system using `gcrt`

.

```
solve :: TC -> Int
solve (TC{..}) = pick . gcrt $ zipWith modEqn message crypt
where
p :: UArray Int Int
p = listArray (1,100) subst
modEqn m c = (fromIntegral (dist p m c), fromIntegral (cycleLen p m))
pick (Just (z,k)) = fromIntegral (z `mod` k)
```

Incidentally, this code inspired me to create a `Util.hs`

in my `comprog-hs`

repository containing (for now) `fi`

as an alias for `fromIntegral`

, and `both`

to apply a function to both elements of a tuple (sadly `lens`

is not available in the Kattis environment). Then we can just write `modEqn m c = both fi (dist p m c, cycleLen p m)`

.

## Solving bigger instances

The above solution works because the alphabet is quite small (only ). However, it’s actually quite wasteful. For example, suppose that the given message consists of copies of the number ; then we will recompute the length of ’s cycle times. It’s easy to imagine a variant of this problem where both the message length and the alphabet size could be much larger. Then my solution above would be too slow. For example, suppose the permutation consists of one giant cycle of length , and the message also has length . We would traverse the entire cycle for every single character in the message, for a total of about operations—much too slow. This post has gotten long enough, but in another post I will show an alternative solution which I believe would work quickly enough even for such large inputs (assuming that the input was restricted such that the answer was still of a reasonable size!). The idea is to precompute the cycle decomposition of the permutation (in time proportional to the size of the alphabet), storing the information in such a way that for each pair of letters in the message and desired encryption, we can find the distance between them and the length of their cycle in constant time.

## Next up: geometry

Next, I’d like to spend a few posts on the topic of geometry. I find that geometry problems work particularly well in Haskell (I don’t think I’ve solved a single geometry problem in Java). Let’s kick things off with a problem on the easier side:

Have fun!

Really appreciate this write up. As usual, I’m amazed to see how clean a solution can be.

Full disclosure, they’re usually not this clean when I first solve them =)

Been waiting for this!

Also realized I did an unnecessary step in the last problem where I tried to reach to the first point inside the loop before applying the CRT logic.

Here is my solution to today’s problem – https://github.com/sureyeaah/Competitive/blob/master/kattis/vacuumba.hs

The main part was parsing (I used your scanner, I will start working on a CP utils module soon) and using printf to control the precision while printing the real numbers.

Here is the interesting part of my solution. I use complex numbers to do the vector additions.

Pingback: Competitive programming in Haskell: cycle decomposition with mutable arrays | blog :: Brent -> [String]