Here's the solution. Note you have to use an intermediate variable a
, otherwise it's impossible. It uses: ((17 << 6) + 17) - 256 = 849 and that 17 = (1 << 4) + 1.
a = (X << 4) + X
return (a << 6) + a - (X << 8)
I found it by searching possible programs on a stack machine using the code at the end of the answer. The solution was given in the form of a stack program, which I manually translated into the expression above:
['push X', '<<4', 'push X', '+', 'dup 0', '<<6', '+', 'push X', '<<8', '-']
Here's the program... it takes a few minutes to run.
import heapq
def moves(adds, shifts, stack, just_shifted):
if len(stack) and shifts and not just_shifted:
for shv in xrange(1, 10):
yield (adds, shifts-1), '<<%d' % shv, stack[:-1] + [stack[-1] << shv]
if len(stack) <= adds:
for i in xrange(len(stack)):
if stack[i] != 1:
yield (adds, shifts), 'dup %d' % i, stack + [stack[i]]
if len(stack) > 1 and adds:
yield (adds-1, shifts), '+', stack[:-2] + [stack[-2] + stack[-1]]
yield (adds-1, shifts), '-', stack[:-2] + [stack[-2] - stack[-1]]
if len(stack) <= adds:
yield (adds, shifts), 'push X', stack + [1]
def find(target):
work = []
heapq.heappush(work, (0, [], 3, 3, []),)
while work:
it = heapq.heappop(work)
print it
if len(it[1]) == 1 and it[1][-1] == target:
return it[4]
just_shifted = len(it[4]) and ('<<' in it[4][-1])
for nsum, desc, nst in moves(it[2], it[3], it[1], just_shifted):
nit = (it[0]+1, nst, nsum[0], nsum[1], it[4] + [desc])
heapq.heappush(work, nit)
print find(849)