#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Primitive sequence analyzer
# written by Fish
# https://github.com/kyodaisuu/primseq
#
# When environmental variable SCRIPT_NAME is set, it runs as a CGI program.
# Otherwise it runs as a commandline program.
def main():
"""Show ordinal of a primitive sequence
Determine if it is commandline or CGI.
"""
import os
if os.getenv('SCRIPT_NAME') is None:
maincl()
else:
maincgi()
return
def maincl():
"""Show ordinal of a primitive sequence
Invoked from command line.
"""
# Test some values
assert primseq('') == 'Empty sequence'
assert primseq('00000') == '5'
assert primseq('012') == 'w^w'
assert primseq('01012') == 'w^w' # w+w^w is not canonical
assert primseq('012123') == 'w^(w^w)' # Another canonical test
assert primseq('000111') == 'w^3' # Another canonical test
assert primseq('123012') == 'w^w+w^w' # Another canonical test
assert primseq('0121212') == 'w^(w+w+w)'
assert primseq('01233451234') == 'w^(w^(w^(w^w))+w^(w^w))'
assert primseq('0123123') == 'w^(w^w+w^w)'
assert primseq('012333') == 'w^(w^(w^3))'
assert primseq('01221') == 'w^(w^2+1)'
assert primseq('0123122201221') == 'w^(w^w+w^3)+w^(w^2+1)'
# Change raw_input to input and it works for Python 3
seq = raw_input('Sequence = ')
seq = makelist(seq)
assert seq[0].isdigit()
seq = standard(seq)
assert seq[0] == 0
print(seq)
print(primseq(seq))
return
def maincgi():
"""Show ordinal of a primitive sequence
Running as a CGI program.
"""
import cgi
# Comment out for debugging
# import cgitb
# cgitb.enable()
# Write html
print(r'''Content-Type: text/html
Primitive sequence analyzer
'''
# Get form input
f = cgi.FieldStorage()
text = f.getfirst('text', '')
seq = makelist(text)
if len(seq) > 1 and seq[0].isdigit():
try:
seq = standard(seq)
except Exception:
print("
')
print('より詳しい説明')
print(footer)
return
def makelist(seq):
"""Make list from string
When comma or space is used, they are used as separators"""
seq = seq.strip()
if ',' in seq:
seq = seq.replace(',', ' ')
if ' ' in seq:
seq = seq.split()
seq = list(seq)
return seq
def primseq(seq):
"""Convert primitive sequence to ordinal"""
# Check input sequence
try:
if len(seq) == 0:
return 'Empty sequence'
except Exception:
return 'Invalid sequence'
for i in seq:
try:
if int(i) < 0:
return 'Number should be positive'
except Exception:
return 'Invalid number'
# Convert to standard sequence
seq = standard(seq)
right = len(seq)-1
for i in range(right+1)[::-1]:
if seq[i] != seq[right]:
ord = str(right-i)
break
if i == 0 and seq[0] == seq[right]:
return str(right-i+1)
ord = prim(seq[:i+1], seq[i+1], ord)
return ord
def prim(seq, num, ord):
if seq[len(seq)-1] < num:
if ord == '1':
ord = 'w'
else:
if '+' in ord or '^' in ord:
ord = 'w^('+ord+')'
else:
ord = 'w^'+ord
if len(seq) == 1:
return ord
ord = prim(seq[:len(seq)-1], seq[len(seq)-1], ord)
return ord
# A + B
for i in range(len(seq))[::-1]:
if seq[i] == num:
break
ord = primseq(seq[i:len(seq)]) + '+' + ord
if i == 0:
return ord
ord = prim(seq[:i], seq[i], ord)
return ord
def standard(seq):
"""Convert sequence to standard expression
Start from 0: [1,2,3] -> [0,1,2]
Increment with 1: [0,2,4] -> [0,1,2]"""
st = stand(seq)
while len(st) < len(seq):
seq = st
st = stand(seq)
return st
def stand(seq):
st = []
offset = int(seq[0])
nextoffset = offset
prev = 0
for i in range(len(seq)):
offset = nextoffset
n = int(seq[i])-offset
if n < 0:
n = 0
nextoffset = int(seq[i])
if n == prev:
if i == 0:
st.append(0)
else:
st.append(st[i-1])
if n > prev:
st.append(st[i-1] + 1)
if n < prev:
for j in range(i)[::-1]:
if n == int(seq[j])-offset:
st.append(st[j])
break
if n > int(seq[j])-offset:
st.append(st[j]+1)
break
prev = n
# Check canonical
# A + B = B when A < B
i = len(st)-1
while i > 1:
i -= 1
if st[i-1] == st[i]:
for j in range(i, len(st)):
if st[j] < st[i]:
break
if st[j] > st[i]:
if i == 1:
st = st[1:len(st)]
else:
st = st[:i-1] + st[i:len(st)]
break
if st[i-1] > st[i]:
for j in range(i)[::-1]:
if st[j] == st[i]:
left = st[j:i]
right = st[i:len(st)]
# normalize the left part
dummy = list(range(left[0]))
if dummy + left != list(standard(dummy + left)):
return st[:j] + list(standard(dummy + left))[left[0]:]+right
found = False
equal = True
for k in range(len(left)):
if len(right) < k+1:
continue
if left[k] < right[k]:
found = True
if left[k] > right[k]:
equal = False
break
if equal and found == False and len(left) < len(right) and right[len(left)] > right[0]:
found = True
if found:
if j == 0:
return tuple(right)
st = st[:j] + right
i = j
break
return tuple(st)
if __name__ == '__main__':
main()