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.
class Solution:

    def racecar(self, tgt: int) -> int:
        
        '''
            shortest path -> bfs
        
            starting from [0, 1], how to reach tgt = 5?
            
                [0, 1] -> [1, 2], [0, -1]
                
                    [1, 2] -> [3, 4], [1, -1]
                    [0, -1] ->[-1, -2], [0, 1] ... visited
                    
                    
                        [3, 4] -> [3, -1], [7, 8]
                        [1,-1] -> [0, -2], [1, 1]
                        [-1,-2]-> [-3,-4] ... too far, [-1,1]
                        
                        
                            [3, -1] -> [2, -2], [3, 1]
                            [7,  8] ... too far
                            [0, -2] -> [-2, -4] ... too far, [0, 1] ... visited
                            [1,  1] -> [2, 2], [1, -1] ...visited
                            [-1 ,1] -> [0, 2], [-1, -1] ... too far
                            
                            
                                [2, -2] -> [0, -4], [2, 1]
                                [3,  1] -> [4,  2], [3, -1] ... visited
                                [2,  2] -> [4,  4], [2, -1]
                                [0,  2] -> [2,  4], [0, -1] ... visited
                                
                                    [0, -4] -> [-4, -8] ... too far, [0, 1] ... visited
                                    [2,  1] -> [3,   2], [2, -1]
                                    [4,  2] -> [6,   4], [4, -1]
                                    [4,  4] -> [8,   8], [4, -1] ... in queue
                                    [2, -1] -> [1,  -2], [2,  1] ... visited
                                    [2,  4] -> [6,   8], [2, -1] ... visited
                                    
                                
                                        [3, 2] -> [5 , 4]  -->> arrived
                                        
                                        -> 7 steps                                    
        '''
        
        '''
            1. try greedy -> can't pass tgt = 5
            
            2. list out all the step until reach the tgt -> time: O(2 ^ (num of operations) )
            
            3. speed up -> dont visit same nodes, dont go to \"too far\" nodes                        
        '''    
        
        visited = dict()        
        q = collections.deque()        
        
        q.append([0, 1])        
        visited[0] = set()
        visited[0].add(1)
        
        step = 0
        while len(q) > 0:
            
            curSize = len(q)           
            
            for i in range(0, curSize):                
                
                pop = q.pop()
                pos, spd = pop[0], pop[1]
                
                if pos == tgt:
                    return step
                                                                                
                nextSteps = [ [pos + spd, spd * 2], [pos, - 1 * spd // abs(spd)] ]
                for nextStep in nextSteps:            
                    
                    nPos, nSpd = nextStep[0], nextStep[1]
                    
                    # check is too far node:
                    if abs(nPos - tgt) <= tgt:                        
                        # check visited
                        if nPos not in visited or nSpd not in visited[nPos]:
                            q.appendleft(nextStep)
                            if nPos not in visited:
                                visited[nPos] = set()
                            
                            visited[nPos].add(nSpd)
                            
            step += 1
            
            
        return -1
            
                    
                    
                    
                
            

class Solution:

    def racecar(self, tgt: int) -> int:
        
        '''
            shortest path -> bfs
        
            starting from [0, 1], how to reach tgt = 5?
            
                [0, 1] -> [1, 2], [0, -1]
                
                    [1, 2] -> [3, 4], [1, -1]
                    [0, -1] ->[-1, -2], [0, 1] ... visited
                    
                    
                        [3, 4] -> [3, -1], [7, 8]
                        [1,-1] -> [0, -2], [1, 1]
                        [-1,-2]-> [-3,-4] ... too far, [-1,1]
                        
                        
                            [3, -1] -> [2, -2], [3, 1]
                            [7,  8] ... too far
                            [0, -2] -> [-2, -4] ... too far, [0, 1] ... visited
                            [1,  1] -> [2, 2], [1, -1] ...visited
                            [-1 ,1] -> [0, 2], [-1, -1] ... too far
                            
                            
                                [2, -2] -> [0, -4], [2, 1]
                                [3,  1] -> [4,  2], [3, -1] ... visited
                                [2,  2] -> [4,  4], [2, -1]
                                [0,  2] -> [2,  4], [0, -1] ... visited
                                
                                    [0, -4] -> [-4, -8] ... too far, [0, 1] ... visited
                                    [2,  1] -> [3,   2], [2, -1]
                                    [4,  2] -> [6,   4], [4, -1]
                                    [4,  4] -> [8,   8], [4, -1] ... in queue
                                    [2, -1] -> [1,  -2], [2,  1] ... visited
                                    [2,  4] -> [6,   8], [2, -1] ... visited
                                    
                                
                                        [3, 2] -> [5 , 4]  -->> arrived
                                        
                                        -> 7 steps                                    
        '''
        
        '''
            1. try greedy -> can't pass tgt = 5
            
            2. list out all the step until reach the tgt -> time: O(2 ^ (num of operations) )
            
            3. speed up -> dont visit same nodes, dont go to \"too far\" nodes                        
        '''    
        
        visited = dict()        
        q = collections.deque()        
        
        q.append([0, 1])        
        visited[0] = set()
        visited[0].add(1)
        
        step = 0
        while len(q) > 0:
            
            curSize = len(q)           
            
            for i in range(0, curSize):                
                
                pop = q.pop()
                pos, spd = pop[0], pop[1]
                
                if pos == tgt:
                    return step
                                                                                
                nextSteps = [ [pos + spd, spd * 2], [pos, - 1 * spd // abs(spd)] ]
                for nextStep in nextSteps:            
                    
                    nPos, nSpd = nextStep[0], nextStep[1]
                    
                    # check is too far node:
                    if abs(nPos - tgt) <= tgt:                        
                        # check visited
                        if nPos not in visited or nSpd not in visited[nPos]:
                            q.appendleft(nextStep)
                            if nPos not in visited:
                                visited[nPos] = set()
                            
                            visited[nPos].add(nSpd)
                            
            step += 1
            
            
        return -1
            
                    
                    
                    
                
            
