-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.py
211 lines (148 loc) · 6.08 KB
/
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import random
import itertools
from copy import deepcopy
from function import FunctionTerm, Function
from brute_force_solver import brute_force_grid_search
from sequence_generator import run
generated_sequences = run()
print('\nBegin testing generated sequences:=========')
for seq in generated_sequences:
print(f'Sequence is : {seq[:10]}')
found_f = brute_force_grid_search(seq, 3, -3, 8) #
if found_f:
print(found_f.startIndex())
print('Found f is', found_f)
print()
print('End testing generated sequences:=========')
class Sus:
# This is sus
def __call__(self):
print('sus'*random.randint(1,10))
# sus = Sus()
# sus()
# The set of operations that would be good for our first attempt:
# +, -, *, /, %
# Operands:
# location indices (relative & absolute), any integer
# enforce integer coefficients with bounded absolute values in linear combinations
# enforce a bound for exponents (i.e. <= 4)?
# Here are some sequences that can be generated by these operations
# In general, f[loc] = g(loc, f[loc-1], f[loc-2], ...) for some constrained function g (likely polynomial)
# In most cases, f[loc] = g(loc) or g(f[loc-1]) or g(loc, f[loc-1])
# Notation: 1-index for f: f[1] denotes the first term of the sequence
# Jaden's idea:
# Each FunctionTerm will be one of
# a, a * b, a + b, a - b, a % b, a / b, f[loc - a], f[a]
#
# Calling evaluate() on the constant term will directly return the term
# And in each FunctionTerm that is not constant, calling evaluate()
# will evaluate recursively
# e.g. calling a * b will return a.evaluate() * b.evaluate()
# i.e. Each FunctionTerm is a tree in itself, except the constant term,
# which is a leaf node
#
# The __str__() method also be recursive, but add brackets around child terms
# To check whether two FunctionTerms are strictly the same, just
# check if their string representation is equal
########### FunctionTerm class test ############
# tested correct
print('Begin FunctionTerm tests')
term1 = FunctionTerm('power_term', c=5, exponent1=3, index_diff1=1)
print(term1) # should print out 5*f[n-1]^3
print(term1.evaluate([1,2,4,8,16], 3)) # should return 5*f[3-1]^3
term2 = FunctionTerm('loc_term', c=3, exponent1=2)
print(term2) # should print out 3*n^2, where n is the 1-indexed index
print(term2.evaluate([1,2,4,8,16], 5)) # should return 3*5^2
term3 = FunctionTerm('interaction_term', c=2, exponent1=3, index_diff1=1, exponent2=2, index_diff2=2)
print(term3) # should print out 2*f[n-1]^3*f[n-2]^2
print(term3.evaluate([1,2,4,8,16], 3)) # should print out 2*f[3-1]^3*f[3-2]^2
print()
########### FunctionTerm class test ############
########### Function class test ############
print('Begin Function tests')
f = Function()
f.addTerm(term1)
f.addTerm(term2)
f.addTerm(term3)
f.addTerm(FunctionTerm('loc_term', c=5, exponent1=2))
f.addTerm(FunctionTerm(c=10))
print(f) # should print out 8*n^2+5*f[n-1]^3+2*f[n-1]^3*f[n-2]^2
print(f.evaluate([1,2,4,8,16], 3)) # should print out 8*3^2+5*f[3-1]^3+2*f[3-1]^3*f[3-2]^2 = 128
print(f.evaluate([1,2,4,8,16], 1)) # should be None
print(f.startIndex())
print()
########### Function class test ############
########### Function class test ############
seq = [1,3,6,15,33,78]
found_f = brute_force_grid_search(seq, 5, -5, 6) #
print(found_f.startIndex())
print('Found f is', found_f) # should return f[n] = 3f[n-2] + f[n-1]
#print(found_f.terms)
# # Extensive Testing
'''
from sequences import prototype_sequences
print('Begin testing prototype sequences:=========')
for seq in prototype_sequences:
print(f'Sqeuence is : {seq[:10]}')
found_f = brute_force_grid_search(seq, 3, -3, 8) #
if found_f:
print(found_f.startIndex())
print('Found f is', found_f)
print()
print('End testing prototype sequences:=========')
'''
class FunctionTree:
# Represents the end function that we construct.
# When doing a tree search, this is a node
def __init__(self):
pass
def flatten(self):
# Flattens the operations in the node and returns the expression
# in python code
pass
return expression
def search(self):
# searches the tree
pass
pass
# Tree Search
# First layer, select which terms are included in the function proposal? (i.e., choose a nonempty subset from {loc, f[loc-1], f[loc-2], ..., f[1]})
# Brute force DFS sus reference: https://leetcode.com/problems/24-game/solution # sus
# We can generate a string of code in Python and execute it directly with exec(string)
# https://stackoverflow.com/questions/701802/how-do-i-execute-a-string-containing-python-code-in-python
# TODO
# Switch statement for perodicity 3:
# Case x % 3 = 0: ((x%3 + 1) % 3)((x%3 + 2) %3) / 2
# Case x % 3 = 1: ((x%3) %3)((x%3 + 1) % 3) / 2
# Case x % 3 = 2: ((x%3) % 3)((x%3 + 2) %3) / 2
#
# f[x] = ((x%3 + 1) % 3)((x%3 + 2) %3) / 2 * (...) + ((x%3) %3)((x%3 + 1) % 3) / 2 * (...) + ((x%3) % 3)((x%3 + 2) %3) / 2 * (...)
# Example code
# 1, 2, 3, 4
# f[loc] <- loc
# 1, 4, 9, 16
# f[loc] <- loc ** 2
# 1, 8, 27, 64
# f[loc] = loc**3
# 1, 1, 2, 3, 5, 8
# f[loc] = f[loc - 1] + f[loc - 2]
# generalized version: f[loc] = c1*f[loc-1] + c2*f[loc-2]
# 0, 1, 3, 6, 10, 15, 21, 28 (A000217)
# f[loc] = binom(n+1, 2) = loc*(loc + 1) / 2, or equivalently, f[loc] = (loc-1) + f[loc-1], which avoids non-integer quadratic coefficient 1/2
# generalized version: f[loc] = c1 * loc**2 + c2 * loc + c3 ?
# repetitions, like 1, 2, 3, 4, 1, 2, 3, 4
# f[loc] <- loc % 4 + 1
# skip-recurrence relation, 2,1,4,3,6,9,8,27,10
# f[2n+1] = 2+f[2n-1], f[2n] = 3*f[2n-2]
# can probably model this with modulus as well 妙！
# f[loc] = loc % 2 * (...) + (1 - loc%2) * (...)
# But modulus by a higher number can be harder (e.g. here is the case for 3)
# You would need to use two of these three terms
# (loc % 3)(loc % 3 - 1)(loc % 3 - 2)
# to model switch for 3
# More sus repetitions, like 2,(*4) 8, (+2) 10,(/2) 5, (-1) 4, (*4) 16, (+2) 18, (/2) 9, (-1) 8
# number of elements in GL_N(F_2) where N=loc # super duper sus!!
# f[loc] = (2^loc - 2^0)(2^loc - 2^1)(2^loc - 2^2)(2^loc - 2^3) ...
# PROBLEM! We can't do recursions.
# Interaction terms (sum of products), like 1,1,2,3,5,11,26
# f[loc] = f[loc-1] + f[loc-2]*f[loc-3]