# 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 v, s, d;
Node(int v, int s, int d){
this.v = v;
this.s = s;
this.d = d;
}

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

@Override
public int hashCode() {
return Objects.hash(v, s);
}
}

public int racecar(int target) {
if(target == 0) return 0;
Queue<Node> queue = new ArrayDeque<>();
Set<Node> done = new HashSet<>();
Node start = new Node(0, 1, 0);
queue.offer(start);
while(!queue.isEmpty()){
Node curr = queue.poll();
if(curr.v < (target * 2)){
Node c1 = new Node(curr.v + curr.s, curr.s * 2, curr.d + 1);
if(c1.v >= 0){
if(!done.contains(c1)){
queue.offer(c1);
if(target == c1.v){
return c1.d;
}
}
}
}
Node c2 = new Node(curr.v, curr.s < 0 ? 1 : -1, curr.d + 1);
if(!done.contains(c2)){