<p>Your car starts at position <code>0</code> and speed <code>+1</code> on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions <code>&#39;A&#39;</code> (accelerate) and <code>&#39;R&#39;</code> (reverse):</p>

<ul>
	<li>When you get an instruction <code>&#39;A&#39;</code>, your car does the following:

	<ul>
		<li><code>position += speed</code></li>
		<li><code>speed *= 2</code></li>
	</ul>
	</li>
	<li>When you get an instruction <code>&#39;R&#39;</code>, your car does the following:
	<ul>
		<li>If your speed is positive then <code>speed = -1</code></li>
		<li>otherwise <code>speed = 1</code></li>
	</ul>
	Your position stays the same.</li>
</ul>

<p>For example, after commands <code>&quot;AAR&quot;</code>, your car goes to positions <code>0 --&gt; 1 --&gt; 3 --&gt; 3</code>, and your speed goes to <code>1 --&gt; 2 --&gt; 4 --&gt; -1</code>.</p>

<p>Given a target position <code>target</code>, return <em>the length of the shortest sequence of instructions to get there</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> target = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> target = 6
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AAARA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3 --&gt; 7 --&gt; 7 --&gt; 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    // car starts at 0 w/ speed +1
    // infinite number line

    // negative position possible
    // 'A' accelerate, 'R' reverse

    // 'A' -> car does: position += speed
    // speed *= 2

    // 'R' -> if speed is positive, speed = -1
    // otherwise, speed = 1

    // Example: "AAR"
    // position: 0 -> 1 -> 3 -> 3, speed: 1 -> 2 -> 4 -> -1

    // given target, return length of shortest sequence of instr to get there
    
    // Observations :
    // More "A" in a row are optimal for far distances
    // Must take into account skipping over position

    // reverse as soon as possible to optimize 'A' in row
    
    // Possibly dp? similar to fibonacci/1D dp problems
    
    // only two options: reverse and accelerate, can represent as tree
    // can overshoot first, then undershoot by slowly approaching it

    // dp not relevant, not repeating calculations, just exploring different paths
    // dfs/bfs?

    // brute force? Recurse and try to find answer, either reverse if in wrong dir
    // or accelerate if not

    // we will use bfs to find SHORTEST SEQUENCE
    int racecar(int target) {

        // we will store, pos, speed, moves
        queue<vector<int>> q;
        q.push({0, 1, 0});
        set<vector<int>> visited;

        // Modification when path is needed
        map<vector<int>, string> mp; 
        mp[{0, 1, 0}] = "";

        while(!q.empty()){
            vector<int> front = q.front();
            q.pop();

            int position = front[0];
            int speed = front[1];
            int moves = front[2];
            
            string str = mp[{position, speed}];

            if (position == target){
                cout << str << endl;
                return moves;
            }
            
            if (visited.count({position, speed}) || abs(position) > target * 2) continue;

            visited.insert({position, speed});

            // always try go forward
            q.push({position+speed, speed*2, moves+1});
            mp[{position+speed, speed*2}] = str + 'A';

            // should reverse in these cases:
            // 1. We will overshoot/have overshot (reverse once)
            // 2. We are moving in wrong direction (moving reverse after reversing once, or
            // after continuosly reversing after overshooting)
            

            if ((position + speed > target && speed > 0) || (position + speed < target && speed < 0)){
                int newSpeed;
                if (speed < 0){
                    newSpeed = 1;
                }else{
                    newSpeed = -1;
                }
                q.push({position, newSpeed, moves + 1});
                mp[{position, newSpeed}] = str + 'R';
            }

        }

        return 0;
    }
};
19611