# 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 <

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