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;
    }
}

Incorrect Solutions

References