2
\$\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\$
  • 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 '18 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 '18 at 10:42
  • 1
    \$\begingroup\$ @tsh Fixed issues. Data generated by hand \$\endgroup\$ – l4m2 Oct 29 '18 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\$ – Jonathan Allan Oct 29 '18 at 11:27
  • 1
    \$\begingroup\$ Does this answer your question? What comes next? \$\endgroup\$ – user85052 Jan 27 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.