# 818. Race Car (Hard)

https://leetcode.com/problems/race-car/

Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: `position += speed, speed *= 2`.

When you get an instruction "R", your car does the following: if your speed is positive then `speed = -1` , otherwise `speed = 1`.  (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

```Example 1:
Input:
target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.
```
```Example 2:
Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.
```

Note:

• `1 <= target <= 10000`.

## Solutions

``````class Solution {
private class Node {
int position, speed, steps;

Node(int position, int speed, int steps) {
this.position = position;
this.speed = speed;
this.steps = steps;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) {
return false;
}

Node node = (Node) o;
return position == node.position && speed == node.speed;
}

@Override
public int hashCode() {
return Objects.hash(position, speed);
}
}

public int racecar(int target) {
if (target == 0) {
return 0;
}

Set<Node> done = new HashSet<>();
Queue<Node> queue = new ArrayDeque<>();

Node start = new Node(0, 1, 0);

done.add(start);
queue.offer(start);

while (!queue.isEmpty()) {
Node curr = queue.poll();

// Turn over to opposite direction, at current time point, remain same position
Node c2 = new Node(curr.position, curr.speed < 0 ? 1 : -1, curr.steps + 1);

if (!done.contains(c2)) {
queue.offer(c2);
done.add(c2);
}

// Position stays the same, no need to check if reach the target

// If current position exceeds 2x target, walking too far away, turn over
if (Math.abs(curr.position) >= Math.abs(target * 2)) {
continue;
}

// Proceed along the axis
Node c1 = new Node(curr.position + curr.speed, curr.speed * 2, curr.steps + 1);

// do not walk the walked steps
if (!done.contains(c1)) {
queue.offer(c1);
done.add(c1);
}

// reach the target
if (target == c1.position) {
return c1.steps;
}
}

return -1;
}
}
``````

## References

Copyright © iovi.com 2017 all right reserved，powered by GitbookLast Modification: 2019-12-03 11:01:18