11
\$\begingroup\$

I feel tired to do "find the pattern" exercise such as

1 2 3 4 (5)
1 2 4 8 (16)
1 2 3 5 8 (13)

Please write a program that finds the pattern for me.

Here, we define the pattern as a recurrence relation that fits the given input, with the smallest score. If there are multiple answers with the same smallest score, using any one is fine.

Let the \$k\$ first terms be initial terms (for the recurrence relation, etc.), and the \$i\$'th term be \$f(i)\$ (\$i>k,i\in\mathbb N\$).

  • A non-negative integer \$x\$ adds\$\lfloor\log_2\max(|x|,1)\rfloor+1\$ to the score
  • The current index \$i\$ adds \$1\$ to the score
  • +, -, *, / (round down or towards zero, as you decide) and mod (a mod b always equal to a-b*(a/b)) each add \$1\$ to the score
  • For each initial term \$x\$, add \$\lfloor\log_2\max(|x|,1)\rfloor+2\$ to the score
  • \$f(i-n)\$ (with \$n\le k\$) adds \$n\$ to the score. E.g. Using the latest value \$f(i-1)\$ add \$1\$ to the score, and there must be at least 1 initial term.
  • Changing the calculation order doesn't add anything to the score. It's fine if you write 1+i as 1 i +, +(i,1) or any format you like.

Samples:

input   -> [score]    expression
1 2 3 4     -> [1]    f(i) = i
1 2 4 8     -> [5]    f(1) = 1, f(i) = f(i-1)+f(i-1)
1 2 3 5 8   -> [9]    f(1) = 1, f(2) = 2, f(i) = f(i-1)+f(i-2)

Shortest program in each language wins. It's fine if your program only solve the problem theoretically.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Should 1, 2, 4, 8 be f(1) = 1, f(i) = f(i - 1) + f(i - 1)? And how current score 5 got? \$\endgroup\$
    – tsh
    Oct 29, 2018 at 10:13
  • 1
    \$\begingroup\$ f(1) = 1 is 2 points, f(2) = 2 is 3 points, f(i-1) is 1 point, + is 1 point, f(i-2) is 2 points. So f(1) = 1, f(2) = 2, f(i) = f(i-1) + f(i-2) is 9 points. Where am I wrong? \$\endgroup\$
    – tsh
    Oct 29, 2018 at 10:42
  • 1
    \$\begingroup\$ @tsh Fixed issues. Data generated by hand \$\endgroup\$
    – l4m2
    Oct 29, 2018 at 11:17
  • \$\begingroup\$ +1 how is the 1,2,4,8 scored at 5? I see an "initial term x" of 1 adding two, "the current index i" twice adding one each, "two non-negative integer x" both with value 1 each adding one, and a +adding one. This makes seven, but I could easily be misinterpreting something. \$\endgroup\$ Oct 29, 2018 at 11:27
  • 3
    \$\begingroup\$ Does this answer your question? What comes next? \$\endgroup\$
    – user85052
    Jan 27, 2020 at 12:20

2 Answers 2

4
\$\begingroup\$

Python, 554 bytes

lambda s:next((s[:i],x)for n in N()for i in R(A(s))if(b:=sum(map(lambda k:A(bin(abs(k)))-1,s[:i])))<n for x in X(n-b,i)if all(E(s,x,j)==s[j]for j in R(i,A(s))))
E=lambda s,x,i:x if int==type(x)else i+1if"i"==x else s[i-x[1]]if"@"==x[0]else.5if(r:=E(s,x[2],i))==0else[(l:=E(s,x[1],i))+r,l-r,l*r,l//r,l%r]["+-*/%".index(x[0])]
A=len
R=range
def X(k,i):
 for x in["i",0]*(k==1)+[["@",k]]*(k<=i)+[[op,l,r]for a in R(1,k-1)for r in X(k-a-1,i)for l in X(a,i)for op in"+-*/%"if k>2]:yield x
 for n in R(2**(k-1),2**k):yield n
def N(k=0):
 while 1>0:k+=1;yield k

Attempt This Online!

running the test-cases takes approximately 30 seconds

The running time is at exponential in the score, so the program may take extremely long to finish if the sequence has a score of more than 10

Output format:

  1. array of initial values
  2. expression for remaining values
  • i: index, integers -> constants
  • ["@",k] -> f(i-k) (for k any integer)
  • [op,l,r] -> l op r (l,r expressions; op operation)

Uses % for mod (I can change it if it is a problem)

for example: ([1, 1], ['+', ['@', 1], ['@', 2]]) -> f(1)=f(2)=1, f(i)=f(i-1)+f(i-2)

Explanation

Go through all expressions in order of score

expressions(k,i) (golfed: X) generates all expressions with score k and i initial elements

check and evaluate (golfed: in-lined/E) evaluate the expression to check if it generates the sequence

The main function goes through all expressions ordered by score and returns the first expression that computes the sequence.

ungolfed version:

def evaluate(seq,expr,i):
 if type(expr)==int:
  return expr
 if expr=="i":
  return i+1
 if expr[0]=="@":
  return seq[i-expr[1]]
 if expr[0]=="+":
  return evaluate(seq,expr[1],i)+evaluate(seq,expr[2],i)
 if expr[0]=="-":
  return evaluate(seq,expr[1],i)-evaluate(seq,expr[2],i)
 if expr[0]=="*":
  return evaluate(seq,expr[1],i)*evaluate(seq,expr[2],i)
 if expr[0]=="/":
  return evaluate(seq,expr[1],i)//evaluate(seq,expr[2],i)
 if expr[0]=="%":
  return evaluate(seq,expr[1],i)%evaluate(seq,expr[2],i)

def check(seq,n_initTerms,expr): ## check if expr is an expression for this sequence
 try:
  for i in range(n_initTerms,len(seq)):
   if not evaluate(seq,expr,i)==seq[i]:
    return False
  return True
 except:
  return False

def expressions(k,i):
 if k==1:
  yield "i"
 if k<=i:
  yield ["@",k]
 if k>2:
  for a in range(1,k-1):
   for op in "+-*/%":
    for l in expressions(a,i):
     for r in expressions(k-a-1,i):
      yield [op,l,r]
 for n in range(2**(k-1),2**k):
  yield n
 if k==1:
  yield 0

def find(seq):
 n=1;
 while True:
  for i in range(len(seq)-1):
   base_score=sum(map(lambda k:len(bin(abs(k)))-2,seq[:i]))
   if base_score<n:
    for expr in expressions(n-base_score,i):
     if check(seq,i,expr):
      return (seq[:i],expr)
  n+=1

Python, 613 bytes

lambda s:min((sum(map(L,s[:i]))+S(s,x),k,s[:i],x)for k in range(2**sum(map(L,s)))if all(E(s,x:=B(k//A(s),i:=k%A(s)),j)==s[j]for j in range(k%A(s),A(s))))[2:]
I=int
A=len
L=lambda k:A(bin(abs(k)))-1
S=lambda s,x:L(x)-1if I==type(x)else 1if"i"==x else x[1]if"@"==x[0]else S(s,x[1])+S(s,x[2])+1
E=lambda s,x,i:x if I==type(x)else i+1if"i"==x else s[i-x[1]]if"@"==x[0]else.5if(r:=E(s,x[2],i))==0else[(l:=E(s,x[1],i))+r,l-r,l*r,l//r,l%r]["+-*/%".index(x[0])]
B=lambda k,i:[q:=(k-i)//3,"i"if k==0else["@",k]if k<=i else[q,-q][r]if(r:=(k-1)%3)<2else["+-*/%"[q%5],B(I((r:=bin(q//5))[2::2],2),i),B(I("0"+r[3::2],2),i)]][1]

Attempt This Online!

ungolfed version

\$\endgroup\$
4
  • \$\begingroup\$ Could you explain what this output would mean? ([1, 2], ['%', 40, ['*', 'i', 'i']]) \$\endgroup\$
    – Simd
    Aug 30, 2023 at 9:18
  • \$\begingroup\$ @Simd f(1)=1,f(2)=2,f(i)=(i*i)%40 \$\endgroup\$
    – bsoelch
    Aug 30, 2023 at 9:19
  • \$\begingroup\$ I am probably being stupid but that is supposed to make 1,2,4,8,15 but doesn’t seem to. 3*3%40=9 doesn’t it? \$\endgroup\$
    – Simd
    Aug 30, 2023 at 9:29
  • 2
    \$\begingroup\$ @Simd I made a typo, I meant 40%(i*i) \$\endgroup\$
    – bsoelch
    Aug 30, 2023 at 9:31
1
\$\begingroup\$

Python3, 1488 bytes:

A rather long approach, but designed to be fast, especially on more common recursive sequences. Explanation of notation coming soon.

from math import*
E=enumerate
def V(s,e):
 e,W=e
 if[0,0]==e[:2]:return all(i==e[-1]for i in s)
 if[0]==e[:1]:return all(a==e[1]*i+e[2]for i,a in E(s,1))
 return all(sum(N*s[i-(W-I)-1]for N,(I,_)in e[0])+i*e[1]+e[2]==a for i,a in E(s,1)if i>max(W-j for _,(j,_)in e[0]))
def C(s,c=[]):
 if[]==s and c:yield c;return
 if s:yield from[*C(s[1:],c+[s[0]]),*C(s[1:],c)]
I=lambda V,i:{(0,V),(V//i,V%i)}
def W(x,y):
 t=[[x,1,0],[y,0,1]]
 while t[-1][0]:q=t[-2][0]//t[-1][0];r=t[-2][0]%t[-1][0];t+=[[r,t[-2][1]-q*t[-1][1],t[-2][2]-q*t[-1][2]]]
 return t[-2]
def D(a,b,x,y,g):
 q=[(0,1,x,y),(0,-1,x,y)]
 while q:
  m,d,X,Y=q.pop(0);m+=d
  if all([X,Y]):yield(X,Y)
  J,K=x+m*(b/g),y-m*(a/g)
  if abs(X)+abs(Y)>abs(J)+abs(K)or 0==all([X,Y]):q+=[(m,d,J,K)]
def f(s):
 for O in range(1,len(s)):
  for J in sorted(C([*E(s)][:O][::-1]),key=len):
   if len(J)==1:
    yield([0,s[O]//(O+1),s[O]%(O+1)],O)
    for u in I(s[O]%J[0][1],O+1):
     j=s[O]//J[0][1]
     yield([[(1,J[0])for _ in range(j)],*u],O);yield([[(j,J[0])],*u],O)
   else:
    q=[(J[0][1],[(1,J[0])],J[1:],s[O])]
    while q:
     x,R,S,v=q.pop(0)
     if[]==S:
      for u in I(v,O+1):yield([R,*u],O)
      continue
     y=S[0][1]
     for i in range(v-1):
      if 0==(v-i)%gcd(x,y):
       g,a,b=W(X:=max(x,y),Y:=min(x,y))
       G=(v-i)//g;A,B=[b,a][x>y]*G,[a,b][x>y]*G;
       A,B=min(D(X,Y,A,B,g),key=lambda x:sum(map(abs,x)))
       q+=[(v-i,[(A*z,l)for z,l in R]+[(B,S[0])],S[1:],i)]
def F(s):
 for i in f(s):
  if V(s,i):return i

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.