Clawsort

There are $n$ numbers and a robot with a claw.
Give the robot a sequence of “<” and “>” commands.
Sort the input array!
Operation >
Operation <
Subtask 2: Sort 3 numbers

Courtesey of s_gamer

Idea: Choose a random direction 

  Robot robot(a);
  while (!robot.is_sorted()) {
    if (robot.pos == 0)
      robot.go('>');
    else if (robot.pos == n-1)
      robot.go('<');
    else
      robot.go("<>"[random(rng)]);
  }
  return robot.cmd;
Idea: Hardcode all cases 

  map, string> operations = {
    {{0,1,2}, "."},
    {{0,2,1}, ">><<>."},
    {{1,0,2}, "><>."},
    {{1,2,0}, ">><<><><."},
    {{2,0,1}, "><>><>."},
    {{2,1,0}, ">><><<>."},
  };
  cout << "Case #" << testcase << ": "
       << operations[a] << '\n';

General Case: $n$ numbers

We have seen two approaches in the submissions:

  1. Try out some random operations and continue with the most promising looking option.
  2. Actually come up with a sorting algorithm.

Idea: Insertion sort

  1. Navigate to the element with value 0
  2. Drag it to position 0.
  3. Move to position 1 and pretend we only need to sort from 1, repeat

Dragging stuff with fish

This solution gives you 82 points. 

  for (int i=0; i<n && !robot.is_sorted(); ++i) {
    int to = robot.index(i);
    robot.go(repeat(">", to - i));
    robot.go(repeat("<><", (to - i)-1));
    robot.go("<>");
  }

How to optimize this?

Note that a fish drags two elements. More carry capacity, more speed!

$\Rightarrow 93~\text{points}$

How to optimize this?

Moving 2 elements by 1 with 3 operations feels optimal

But we waste time walking right, as we don’t carry anything!

We could put elements $n-2$ and $n-1$ directly at the right place.

Step 1: locate the first occurrence of 8 or 9
Step 2: grab the 9 with fish
Step 3: move the 9 onto the 8 and continue right
Step 4: move both at the right place
Step 5: continue looking for 0 and 1 and put them at the right place
Step 5: do the same again for the rest 

    // Step 1: locate the first occurrence of 8 or 9
    int a = robot.index(r-2), b = robot.index(r-1);
    robot.go(repeat(">", min(a, b) - robot.pos));
    while (robot.pos < r-1)
    if (robot.a[robot.pos+1] == r-1 ||
        robot.a[robot.pos+1] == r-2)
        robot.go("><>"); // Step 2: drag them both with fish
      else
        robot.go(">");   // Step 3: move the 9 onto the 8
    // Step 4: move both at the right place
    robot.go("<");
    if (robot.a[r-1] == r-2)
      robot.go("<>><");
    robot.go("<");
This solution gives 97 points.

Need to optimize a few special cases to get full score.

Brute-Force approach

  1. Try all possibilities
  2. If we can estimate how good a solution is, we can discard unpromising ones
  3. Trade-off quality vs speed

Courtesey of Erik Klein

The principled approach

  1. What local observations can I make?
  2. What global strategy should I go with?
  3. Are there any redundancies in my approach?
Yaël’s solution