Freedom Trail

A very tough problem.

So, let’s go for the freedom trail problem.

We consider a ring inscribed with evenly-spaced letters. It locks a door and we need to input the correct password which we fortunately know. To operate the ring we can do three different operations:

  • rotate the whole ring clockwise one letter
  • rotate the whole ring counterclockwise one letter
  • push the ‘activate’ button and type the letter at the top

We have as input the content of the ring as a ring str and the password to type as a key str. Since we are a bit lazy we want to figure out what is the minimal number of operations needed in order to type the whole password.

For example, if we consider the ring ‘abcdeb’ and the key ‘abe’ we could propose several solutions:

  the ring:
    a
   b b
   e c
    d
  • activate, clockwise, activate, clockwise, clockwise, clockwise, activate with a cost of 7 operations
  • activate, counterclockwise, activate, counterclockwise, activate with a cost of 5 operations

Here the optimal solution uses 5 operations.

Since the problem is rather hard to parallelize, we are going to consider special cases. Here are some example rings:

  • iwgvcbqilaqfsjkbxvrhhaxfguluimftuoehpusxwtxhhrdeuboyxdyfeljofpcssqkyztijlqffwdvymncktmzvgcocxfzwjuoa
  • okfhkyomyahqroeouvzczrwsmuilwizahvruqvvtjqzhqiknwlawfckqtntehirqarfzxyovnqspqvxsnxewhjcwchikgiinwulq
  • qhkavjaffqcwbozulzgjzlcndkwpthgpochgunyshsphuteispibhdqogarrpbdbmqnryrnwngkkdaorgfrxystoqriaysqewyys
  • fqkwayxvuaduhjdwzyqocytfvadsxrhtzywhftrricrcerdyvnulbxehdakdjlyqwkccjpaswogcrjrdiepoapswwugesjmitzzr

Can you figure out an efficient parallel algorithm ?

Sequential Solution

Ok, let’s see the sequential solution. We are going to use a dynamic programming where the input is the current position on the ring and the current position on the key. All computed results are stored in a hash table instead of a matrix since many configurations are never reached.

We obtain the following code:

use std::collections::HashMap;

fn find_rotate_steps(ring: &str, key: &str) -> i32 {
    let mut memo = HashMap::new();
    find_rotate_dp(ring.as_bytes(), key.as_bytes(), 0, 0, &mut memo)
}

fn find_rotate_dp(
    ring: &[u8],
    key: &[u8],
    current_ring_position: usize,
    current_key_position: usize,
    memo: &mut HashMap<(usize, usize), i32>,
) -> i32 {
    if current_key_position == key.len() {
        0
    } else {
        if let Some(cached) = memo.get(&(current_ring_position, current_key_position)) {
            return *cached;
        }
        let value = if ring[current_ring_position] == key[current_key_position] {
            1 + find_rotate_dp(
                ring,
                key,
                current_ring_position,
                current_key_position + 1,
                memo,
            )
        } else {
            // we can either go left or right
            let left_chars = ring[0..current_ring_position]
                .iter()
                .rev()
                .chain(ring[(current_ring_position + 1)..].iter().rev());
            let right_chars = ring[(current_ring_position + 1)..]
                .iter()
                .chain(ring[0..current_ring_position].iter());
            let target = key[current_key_position];
            let left_movements = left_chars.take_while(|&c| *c != target).count() + 1;
            let right_movements = right_chars.take_while(|&c| *c != target).count() + 1;
            let left_pos = (current_ring_position + ring.len() - left_movements) % ring.len();
            let right_pos = (current_ring_position + right_movements) % ring.len();
            assert!(ring[left_pos] == target);
            assert!(ring[right_pos] == target);
            let left_value = find_rotate_dp(ring, key, left_pos, current_key_position, memo)
                + left_movements as i32;
            let right_value = find_rotate_dp(ring, key, right_pos, current_key_position, memo)
                + right_movements as i32;
            left_value.min(right_value)
        };
        memo.insert((current_ring_position, current_key_position), value);
        value
    }
}
Parallel Solution

So, the thing that makes this problem difficult is having the same letter appearing several times on the ring. This creates the possibility for different movement choices.

As you know dynamic programming is about find the shortest path in a particular graph.

Usually it is possible to parallelize sequential algorithms with a dependencies analysis and realize that you can move through the graph with a parallel front.

However this is not feasible here. If for example we take a repetition of 2 for each letter in the ring the graph ends up as a very long chain of pairs of vertices.

So we need another strategy. What we do is realize that all unique letters are special points in the graph: you must go through them.

Let’s take again the ‘abcdeb’ ring. If we take a key ‘abeba’ we obtain the following graph:

              (1,1)-(1,2)             (5,3)-(5,4)
             /           \           /           \
(0,0) - (0,1)             (4,2)-(4,3)             (0,4)-(0,5)
             \           /           \           /
              (5,1)-(5,2)             (1,3)-(1,4)

As you can see having to go through ’e’(at position 4 in the ring) in the position 2 of the key means that any path from the start to the end must go through (4,2). It is therefore possible to split the key into two subkeys on the ’e’ and to process these two subkeys in parallel.

Here is the parallel code:

fn find_rotate_steps_par(ring: &str, key: &str) -> i32 {
    // let's figure out where each unique char is.
    // note that this part is parallelized just for fun
    let unique_chars = ring
        .as_bytes()
        .par_iter()
        .enumerate()
        .fold(HashMap::new, |mut h: HashMap<u8, (bool, usize)>, (i, c)| {
            match h.entry(*c) {
                std::collections::hash_map::Entry::Occupied(mut o) => {
                    o.get_mut().0 = false;
                }
                std::collections::hash_map::Entry::Vacant(v) => {
                    v.insert((true, i));
                }
            }
            h
        })
        .reduce(HashMap::new, |mut h1, h2| {
            h2.into_iter().for_each(|(c, (unique, pos))| {
                if let Some(existing_c) = h1.get_mut(&c) {
                    existing_c.0 = false;
                } else {
                    h1.insert(c, (unique, pos));
                }
            });
            h1
        })
        .into_iter()
        .filter_map(|(c, (unique, pos))| if unique { Some((c, pos)) } else { None })
        .collect::<HashMap<_, _>>();

    rayon::iter::split((0, key.as_bytes()), |(start_index, key_part)| {
        // look for a unique char around the midpoint
        // if we find one we split around it
        let midpoint = key_part.len() / 2;
        let unique_char_index = (midpoint..key_part.len() - 1)
            .interleave((1..midpoint).rev())
            .find(|&i| unique_chars.contains_key(&key_part[i]));
        if let Some(split_index) = unique_char_index {
            // we want the midpoint on the left side
            let (left_key, right_key) = key_part.split_at(split_index + 1);
            let midchar = *left_key.last().unwrap();
            let midchar_pos = unique_chars[&midchar];
            ((start_index, left_key), Some((midchar_pos, right_key)))
        } else {
            ((start_index, key_part), None)
        }
    })
    .map(|(ring_position, key)| {
        let mut memo = HashMap::new();
        find_rotate_dp(ring.as_bytes(), key, ring_position, 0, &mut memo)
    })
    .sum()
}

What is amazing is that it does work and even gives a nice speedup. Try it out for yourselves!