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

from queue import Queue
from queue import PriorityQueue
import math
import heapq

@lru_cache(maxsize = 20000000)
def heuristic2(pos,spd,target):
    #pos, spd = state
    dst = abs(target-pos)
    if dst < 20:
        count = dst/10
    else: 
        spd = abs(spd)
        count = 0
        lastDst = dst
        #count = min(0, int(math.log2(dst) - math.log2(spd)) - 3)
        while dst > 0:
            lastDst = dst
            dst-=spd
            spd*=2
            count+=1
        if dst < 0:
            count+=min(1+int(math.log2(abs(dst))), 2+int(math.log2(abs(lastDst))))
    return count

@lru_cache(maxsize = 20000000)
def heuristic(dst,spd):
    #pos, spd = state
    #dst = abs(target-pos)
    spd = abs(spd)
    count = 0
    lastDst = dst
    #count = min(0, int(math.log2(dst) - math.log2(spd)) - 3)
    while dst > 0:
        lastDst = dst
        dst-=spd
        spd*=2
        count+=1
    if dst < 0:
        count+=min(1+int(math.log2(abs(dst))), 2+int(math.log2(abs(lastDst))))
    return count

class Solution:
    def racecar(self, target: int) -> int:
        def determine_sign(spd):
            if spd > 0:
                return -1
            else:
                return 1
        '''def heuristic(state):
            pos, spd = state
            dst = abs(target-pos)
            if dst < 20:
                return dst/10
            spd = abs(spd)
            count = 0
            lastDst = dst
            #count = min(0, int(math.log2(dst) - math.log2(spd)) - 3)
            while dst > 0:
                lastDst = dst
                dst-=spd
                spd*=2
                count+=1
            if dst < 0:
                count+=min(1+int(math.log2(abs(dst))), 2+int(math.log2(abs(lastDst))))
            return count'''
        '''def heuristic(state):
            pos, speed = state
            distance = target-pos
            res = 0
            # When distance and speed direction is different, we need to make a R
            if (distance > 0 and speed < 0) or (distance < 0 and speed > 0):
                distance = abs(distance)
                speed = 1
                res += 1
            return res+math.log(distance/speed+1, 2)'''
        # q = PriorityQueue()
        # q.put( (0, (0,(0,1)) ) )
        q = []
        heapq.heappush(q, (0, (0,(0,1))) )
        seenPositions = set([(0,1)])

        #count = 0
        #while q.qsize() > 0:# and count < 100:
        while len(q) > 0:
            #priority, (ind, (pos, spd)) = q.get()
            priority, (ind, (pos, spd)) = heapq.heappop(q)
            # print(priority, (ind, (pos, spd)))
            #count+=1
            if pos == target:
                return ind
            # option A
            newState = (pos+spd, spd*2)
            if not newState in seenPositions:
                #q.put((ind+1+heuristic(newState), (ind+1, newState)))
                heapq.heappush(q, (ind+1+heuristic(abs(newState[0]-target), newState[1]), (ind+1, newState)))
                #heapq.heappush(q, (ind+1+heuristic(newState), (ind+1, newState)))
                #heapq.heappush(q, (ind+1+heuristic2(newState[0], newState[1], target), (ind+1, newState)))
                seenPositions.add(newState)
            
            # option B
            newState = (pos, determine_sign(spd))
            if not newState in seenPositions:
                #q.put((ind+1+heuristic(newState), (ind+1, newState)))
                heapq.heappush(q, (ind+1+heuristic(abs(newState[0]-target), newState[1]), (ind+1, newState)))
                #heapq.heappush(q, (ind+1+heuristic(newState), (ind+1, newState)))
                #heapq.heappush(q, (ind+1+heuristic2(newState[0], newState[1], target), (ind+1, newState)))
                seenPositions.add(newState)


59209