1# Go to a requested generation.  The given generation can be:
2#
3#  * an absolute number like 1,000,000 (commas are optional)
4#  * a number relative to the current generation like +9 or -6
5#  * an expression like "17*(2^(3*143)+2^(2*3*27))"
6#  * an expression starting with + or -, indicating a relative move
7#  * any of the above preceded by "f" (fast). This wil set the base
8#    step to 2 and provide less visual feedback of progress
9#
10# If the target generation is less than the current generation then
11# we go back to the starting generation (normally 0) and advance to
12# the target.
13#
14# If the input is preceded by F "fast" or q "quick" then we use the
15# algorithm of goto-fast.py, which sets the base to 2 and jumps by
16# powers of 2.
17#
18# Authors:
19# Original goto.py by Andrew Trevorrow and Dave Greene, April 2006.
20#   Updated Sept-Oct 2006 -- XRLE support and reusable default value.
21#   Updated April 2010 -- much faster, thanks to PM 2Ring.
22# goto-expression.py by Robert Munafo, using regexp expression
23# evaluation like Hypercalc (mrob.com/pub/perl/hypercalc.html)
24#  20111103 First stand-alone version of "expr.py" written as an
25#           exercise to learn me some Python
26#  20111105 Add expr_2 using re.sub (a cleaner implementation)
27#  20120624 Remove whitespace before evaluating
28#  20130213 Move expr_2 code to "goto-expression.py" for Golly.
29#  20130214 Fix precedednce bugs, add expr_3
30#  20130215 Remove redundant g.getstep and g.setstep calls. Full handling
31#           of scientific notation and leading signs (like "300+-3")
32#
33# TODO:
34#   Allow decimal point in EE notation, so "6.02e23" would work (right
35#     now you have to do "602e21")
36#   Make - and / associate left-to-right, so 100-10+1 gives 91 instead of 89
37#   Remove use of deprecated string.find and string.replace functions
38#   Why is it much faster when you start from gen 0? For example, start
39#     with puffer-train.rle, use this script to goto 10^100 then goto 2*10^100
40#     it's much faster if you start from gen 0 and go directly to 2*10^100
41#   Given that gofast saves and restores the base, should we use it always?
42#     Note that patterns with a lot of period-P oscillators run more
43#     efficiently when the base is set to P or a factor of P, so this
44#     is not a simple decision.
45
46from glife import validint
47from time import time
48import golly as g
49import re
50
51# --------------------------------------------------------------------
52# Regexp-based expression evaluator. The main loop contains match
53# cases for each type of operation, and performs one operation per
54# loop until there are none left to match. We use re.sub and pass
55# functions for the repl parameter. See:
56#   http://docs.python.org/2/library/re.html#re.sub
57#   http://docs.python.org/2/library/re.html#re.MatchObject.group
58
59p_whitespace = re.compile('[ \t]+')
60p_paren = re.compile('\((\d+)\)')
61p_parexp = re.compile('\((\d+[*/+-^][^()]*\d)\)')
62p_exp = re.compile('(\d+)\^(\d+)')
63p_mul = re.compile('(\d+)([*/])(n?\d+)')
64p_add = re.compile('(\d+)([-+])(n?\d+)')
65
66p_ee = re.compile('([.0-9]+)e([+-]?\d+)')
67p_mantissa = re.compile('^n?\d*\.?\d+$')
68p_leadn = re.compile('^n')
69p_digits = re.compile('^[+-]?\d+$')
70p_dot = re.compile('\.')
71
72p_plusminus = re.compile('([-+])([-+])')
73
74# erf = expression replace function
75def erf_paren(match):
76  "Remove parentheses: (123) -> 123"
77  a = match.group(1)
78  return a
79
80# ee_approx - Python-like integer approximation of a number in scientific
81#             notation. The mantissa and exponent are given separately and
82#             may be either numeric or string. (the caller is expected to
83#             generate them separately, e.g. by using a regexp to match
84#             parts of a string). The exponent must be an integer or an
85#             equivalent string; more flexibility is available for the
86#             mantissa (see examples)
87# All of the following examples evaluate to True:
88#   ee_approx(2.0, 20) == 2*10**20
89#   ee_approx('2.', 20) == 2*10**20
90#   ee_approx('12000', -3) == 12
91#   ee_approx(12e+03, '-3') == 12
92# The following return 0 because of an error:
93#   ee_approx(2.3, 4.0)      # Exponent may not be a float
94#   ee_approx(6.02, '23.')   # Exponent may not contain '.'
95# The following evaluate to False because of roundoff error:
96#   ee_approx('.02', 22) == 2*10**20
97def ee_approx(m, e):
98  "Integer approximation of m*10^e given m and e"
99  m = str(m)
100  # Make sure mantissa matches its pattern
101  if p_dot.search(m):
102    m = m + '0'
103  else:
104    m = m + '.0'
105  if not p_mantissa.search(m):
106    return 0
107  m = float(m)
108  m = int(m * float(2**64) * (1.0+2.0**-52.0))
109  e = str(e)
110  if not p_digits.search(e):
111    return 0
112  e = int(e)
113  if e<0:
114    e = 10**(-e)
115    return m/(e*2**64)
116  else:
117    e = 10**e
118    return (m*e)/(2**64)
119
120def erf_ee(match):
121  "Scientific notation: 1.2e5 -> 120000"
122  a = match.group(1)
123  b = match.group(2)
124  return str(ee_approx(a,b))
125
126def erf_exp(match):
127  "Exponentiation: 2^24 -> 16777216"
128  a = int(match.group(1))
129  b = int(match.group(2))
130  return str(a**b)
131
132def erf_mul(match):
133  "Multiplication and (integer) division"
134  a = int(match.group(1))
135  # match.group(2) is operator
136  b = match.group(3)
137  # Check for leading 'n'
138  if p_leadn.search(b):
139    b = p_leadn.sub('-', b)
140  b = int(b)
141  if(match.group(2) == '*'):
142    return str(a*b)
143  else:
144    return str(a//b)
145
146def erf_add(match):
147  "Addition and subtraction"
148  a = int(match.group(1))
149  # match.group(2) is operator
150  b = match.group(3)
151  # Check for leading 'n'
152  if p_leadn.search(b):
153    b = p_leadn.sub('-', b)
154  b = int(b)
155  if(match.group(2) == '+'):
156    return str(a+b)
157  else:
158    return str(a-b)
159
160""" Evaluate an expression without parentheses, like 2+3*4^5 = 3074
161    The precedence is:
162      If we match something like "6.02e23", expand it
163      Else if we match something like "4^5", expand it
164      Else if we match something like "3*17", expand it
165      Else if we match something like "2+456", expand it
166      Else return
167    It loops in all cases but the last
168"""
169def expr_2(p):
170  going = 1
171  # print 'e2:', p
172  while going:
173    if p_ee.search(p):
174      p = p_ee.sub(erf_ee, p, count=1)
175      # print 'e2 ee, got:', p
176    elif p_exp.search(p):
177      p = p_exp.sub(erf_exp, p, count=1)
178      # print 'e2 exp, got:', p
179    elif p_mul.search(p):
180      p = p_mul.sub(erf_mul, p, count=1)
181      # print 'e2 mul, got:', p
182    elif p_add.search(p):
183      p = p_add.sub(erf_add, p, count=1)
184      # print 'e2 add, got:', p
185    else:
186      # print 'e2 done'
187      going = 0
188  # print 'e2 return:', p
189  return p
190
191def erf_e2(match):
192  "Parenthesized bare expression"
193  a = expr_2(match.group(1))
194  return str(a)
195
196def erf_plusminus(match):
197  "--, -+, +-, or ++"
198  if match.group(2) == '-':
199    return match.group(1)+'n'
200  return match.group(1)
201
202"""
203    Evaluate an expression possibly including parenthesized sub-expressions
204    and numbers in scientific notation,
205    like 17*4^((7^2-3)*6^2+2e6)+602e21
206    The precedence is:
207      If we match something like "6.02e23", expand it
208      Else if we match something like "(3+4*5)", expand it using expr_2
209      Else if we match something like "(23456)", remove the parens
210      Else expand the whole string using expr_2 and return
211    It loops in all cases but the last
212"""
213def expr_3(p):
214  p = p_whitespace.sub('', p)
215  if p_plusminus.search(p):
216    p = p_plusminus.sub(erf_plusminus, p)
217  going = 1
218  while going:
219    if p_ee.search(p):
220      p = p_ee.sub(erf_ee, p, count=1)
221    elif p_parexp.search(p):
222      p = p_parexp.sub(erf_e2, p, count=1)
223    elif p_paren.search(p):
224      p = p_paren.sub(erf_paren, p, count=1)
225    else:
226      p = expr_2(p)
227      going = 0
228  return p
229
230# --------------------------------------------------------------------
231
232"""
233    gt_setup computes how many generations to move forwards. If we need to
234    move backwards, it rewinds as far as possible, then returns the number
235    of generations we need to move forwards.
236"""
237def gt_setup(gen):
238   currgen = int(g.getgen())
239   # Remove leading '+' or '-' if any, and convert rest to int or long
240   if gen[0] == '+':
241      n = int(gen[1:])
242      newgen = currgen + n
243   elif gen[0] == '-':
244      n = int(gen[1:])
245      if currgen > n:
246         newgen = currgen - n
247      else:
248         newgen = 0
249   else:
250      newgen = int(gen)
251
252   if newgen < currgen:
253      # try to go back to starting gen (not necessarily 0) and
254      # then forwards to newgen; note that reset() also restores
255      # algorithm and/or rule, so too bad if user changed those
256      # after the starting info was saved;
257      # first save current location and scale
258      midx, midy = g.getpos()
259      mag = g.getmag()
260      g.reset()
261      # restore location and scale
262      g.setpos(midx, midy)
263      g.setmag(mag)
264      # current gen might be > 0 if user loaded a pattern file
265      # that set the gen count
266      currgen = int(g.getgen())
267      if newgen < currgen:
268         g.error("Can't go back any further; pattern was saved " +
269                 "at generation " + str(currgen) + ".")
270         return 0
271      return newgen - currgen
272   elif newgen > currgen:
273      return newgen - currgen
274   else:
275     return 0
276
277# --------------------------------------------------------------------
278
279def intbase(n, b):
280   # convert integer n >= 0 to a base b digit list (thanks to PM 2Ring)
281   digits = []
282   while n > 0:
283      digits += [n % b]
284      n //= b
285   return digits or [0]
286
287def goto(newgen, delay):
288   g.show("goto running, hit escape to abort...")
289   oldsecs = time()
290
291   # before stepping we advance by 1 generation, for two reasons:
292   # 1. if we're at the starting gen then the *current* step size
293   #    will be saved (and restored upon Reset/Undo) rather than a
294   #    possibly very large step size
295   # 2. it increases the chances the user will see updates and so
296   #    get some idea of how long the script will take to finish
297   #    (otherwise if the base is 10 and a gen like 1,000,000,000
298   #    is given then only a single step() of 10^9 would be done)
299   if delay <= 1.0:
300     g.run(1)
301     newgen -= 1
302
303   # use fast stepping (thanks to PM 2Ring)
304   for i, d in enumerate(intbase(newgen, g.getbase())):
305      if d > 0:
306         g.setstep(i)
307         for j in xrange(d):
308            if g.empty():
309               g.show("Pattern is empty.")
310               return
311            g.step()
312            newsecs = time()
313            if newsecs - oldsecs >= delay:  # time to do an update?
314               oldsecs = newsecs
315               g.update()
316   g.show("")
317
318# --------------------------------------------------------------------
319# This is the "fast goto" algorithm from goto-fast.py that uses
320# binary stepsizes and does not do that initial step by 1 generation.
321
322def intbits(n):
323   ''' Convert integer n to a bit list '''
324   bits = []
325   while n:
326      bits += [n & 1]
327      n >>= 1
328   return bits
329
330def gofast(newgen, delay):
331   ''' Fast goto '''
332   #Save current settings
333   oldbase = g.getbase()
334   # oldhash = g.setoption("hashing", True)
335
336   g.show('gofast running, hit escape to abort')
337   oldsecs = time()
338
339   #Advance by binary powers, to maximize advantage of hashing
340   g.setbase(2)
341   for i, b in enumerate(intbits(newgen)):
342      if b:
343         g.setstep(i)
344         g.step()
345         g.dokey(g.getkey())
346         newsecs = time()
347         if newsecs - oldsecs >= delay:  # do an update every sec
348            oldsecs = newsecs
349            g.update()
350         if   g.empty():
351            break
352
353   g.show('')
354
355   #Restore settings
356   # g.setoption("hashing", oldhash)
357   g.setbase(oldbase)
358
359# --------------------------------------------------------------------
360
361def savegen(filename, gen):
362   try:
363      f = open(filename, 'w')
364      f.write(gen)
365      f.close()
366   except:
367      g.warn("Unable to save given gen in file:\n" + filename)
368
369# --------------------------------------------------------------------
370
371# use same file name as in goto.lua
372GotoINIFileName = g.getdir("data") + "goto.ini"
373previousgen = ""
374try:
375   f = open(GotoINIFileName, 'r')
376   previousgen = f.readline()
377   f.close()
378   if not validint(previousgen):
379      previousgen = ""
380except:
381   # should only happen 1st time (GotoINIFileName doesn't exist)
382   pass
383
384gen = g.getstring("Enter the desired generation number as an\n" +
385                  "expression, prepend -/+ for relative\n" +
386                  "move back/forwards, prepend f to use faster\n"
387                  "powers-of-2 steps:",
388                  previousgen, "Go to generation")
389# Evaluate the expression. This leaves leading "f" and/or "+/-"
390# intact.
391gen = expr_3(gen)
392
393# Find out if they want to get there quickly
394# %%% TODO: Use re instead of string.find and string.replace (which are
395#           deprecated in later versions of Python)
396fastmode = 0
397if(gen.find("f") == 0):
398  gen = gen.replace("f","")
399  fastmode = 1
400
401if len(gen) == 0:
402   g.exit()
403elif gen == "+" or gen == "-":
404   # clear the default
405   savegen(GotoINIFileName, "")
406elif not validint(gen):
407   g.exit('Sorry, but "' + gen + '" is not a valid integer.')
408else:
409   # best to save given gen now in case user aborts script
410   savegen(GotoINIFileName, gen)
411   oldstep = g.getstep()
412   # %%% TODO: Use re instead of string.replace to remove the commas
413   newgen = gt_setup(gen.replace(",",""))
414   if newgen > 0:
415     if fastmode:
416       gofast(newgen, 10.0)
417     else:
418       goto(newgen, 1.0)
419   g.setstep(oldstep)
420