What comes next?

Question

Given a space-separated list of integers, your task is to find the next integer in the sequence. Each integer in the sequence is the result of applying a single mathematical operation(+,-,* or /) to the previous integer, and each sequence is made up of a variable number of such operations (but no more than 10). No sequence will be longer than half the length of the sequence of integers, so you'll have each sequence of operations appear at least twice for confirmation.
Input will be via stdin (or prompt for JavaScript solutions).

Here are some explanatory examples.

Input:

1 3 5 7 9 11

Output:

13

Fairly easy, this one. All values are previous value +2.

Input:

1 3 2 4 3 5 4 6 5 7 6

Ouput:

8

Two steps in this sequence, +2 then -1.

Input:

2 6 7 3 9 10 6 18 19 15 45 46

Output:

42

Three steps - *3, +1, -4.

Test cases

Here are few more test cases:

Input:

1024 512 256 128 64 32 16

Output:

8

Input:

1 3 9 8 24 72 71 213 639

Output:

638

Input:

1 2 3 4 5 2 3 4 5 6 3 4 5 6 7

Output:

4

Input:

1 2 4 1 3 9 5 8 32 27 28 56 53 55 165 161 164 656 651 652 1304

Output:

1301

I have an ungolfed Scala solution (42 lines) that I will post in a couple of days.

This is code-golf - shortest answer wins.

Answer 1

Golfscript, 203 138 chars

~]0{).2$.);[\(;]zip\/zip{.{~-}%.&({-}+\{;{.0={.~\%{.~%{;0}{~/{/}+}if}{~\/{*}+}if}{~!{;}*}if}%.&(\{;;0}/}{\;}if}%.{!}%1?)!{0}*}do\@)\,@%@=~

This uses far more ifs than a standard Golfscript program, and its operation is pretty cryptic, so here's a commented (but not ungolfed other than by the addition of whitespace and comments) version:

~]0
# Loop over guesses L for the length of the sequence
{
    # [x0 ... xN] L-1
    ).
    # [x0 ... xN] L L
    2$.);[\(;]zip
    # [x0 ... xN] L L [[x0 x1][x1 x2]...[x{N-1} xN]]
    \/zip
    # [x0 ... xN] L [[[x0 x1][xL x{L+1}]...][[x1 x2][x{L+1} x{L+2}]...]...]
    {
        # [x0 ... xN] L [[xi x{i+1}][x{i+L} x{i+L+1}]...]
        # Is there an operation which takes the first element of each pair to the second?
        # Copy the pairs, work out each difference, and remove duplicates
        .{~-}%.&
        # Turn the first difference into an operation
        ({-}+\
        # If there was more than one unique difference, look for a multiplication
        {
            ;
            # [x0 ... xN] L [[xi x{i+1}][x{i+L} x{i+L+1}]...]
            # Do something similar, but working out multiplicative factors
            # Note that if we have [0 0] it could be multiplication by anything, so we remove it.
            # However, they can't all be [0 0] or we'd have only one unique difference
            {
                # [0     0   ] =>
                # [0     _   ] => 0     # a "false" value, because it can't possibly be multiplication
                # [a     a.b'] => {b'*}
                # [a'.b  b   ] => {a'/}
                # [_     _   ] => 0     # ditto
                # This is the obvious place to look for further improvements
                .0={.~\%{.~%{;0}{~/{/}+}if}{~\/{*}+}if}{~!{;}*}if
            }%.&
            # If we have one unique multiplication, even if it's false, keep it.
            # Otherwise discard them and replace them with false.
            (\{;;0}/
        }
        # There was only one unique difference. Discard the pairs
        {\;}if
        # operation - one of 0, {d+}, {m*}, {M/}
    }%
    # [x0 ... xN] L [op0 ... op{L-1}]
    # Is any of the operations false, indicating that we couldn't find a suitable operation?
    .{!}%1?
    # [x0 ... xN] L [op0 ... op{L-1}] idxFalse
    # If idxFalse is -1 then all the ops are ok, and we put a false to exit the loop
    # Otherwise one op failed, so we leave the array of ops, which is non-false, to be popped by the do.
    )!{0}*
}do
# [x0 ... xN] L [op0 ... op{L-1}]
\@)\,@%@=~
# op{(len(Xs)-1)%L} (Xs[-1])

My original submission was the following at 88 chars:

~]:x;2.{;).(2base(;{[{--}{@*\.!+/}]=}%[x.(;2$]zip\,<{~++}%x,.@[*x\]zip<{~~}%)\x(;=!}do\;

However, this tries to calculate the operations from the first occurrence of each, so if the operation is multiplication or division and the argument the first time round is 0 it breaks.

Answer 2

Haskell, 276 261 259 257 243 characters

Here is my inefficient solution. It works on unbounded (and bounded) integers. This solution happens to work correctly with non-exact division (eg: 5 / 2 = 2).

import Control.Monad
main=interact$show.n.q read.words
f=flip
q=map
_%0=0
x%y=div x y
s b=[1..]>>=q cycle.(f replicateM$[(+),(*),(%)]>>=f q[-b..b].f)
m l x s=[y!!l|y<-[scanl(f($))(x!!0)s],x==take l y]
n x=(s(maximum$q abs x)>>=m(length x)x)!!0

How it works: I create every possible sequence of (possible) operations. Then I test against the input sequence of numbers to see if the generated sequence will create the input. If it does, return the next number in the sequence. The code will always return an answer that is derived from a shortest sequence of operations. This happens because the list of operation sequences is generated in that order. It's arbitrary (but consistent) on deciding between ties. For example the code returns 6 or 8 for the sequence 2 4.

Ungolfed:

import Control.Monad

main :: IO ()
main = print . next . map read . words =<< getLine

opSequences :: Integral a => a -> [[a -> a]]
opSequences bound = [1 ..] >>= map cycle . (`replicateM` (ops >>= (`map` args) . flip))
  where
    ops = [(+), (*), \x y -> if y == 0 then 0 else div x y]
    args = [-bound .. bound]

match :: (MonadPlus m, Integral a) => [a] -> [a -> a] -> m a
match ns opSeq = guard (ns == take len ms) >> return (ms !! len)
  where
    n0 = ns !! 0
    len = length ns
    ms = scanl (flip ($)) n0 opSeq

next :: Integral a => [a] -> a
next ns = (opSequences bound >>= match ns) !! 0
  where
    bound = maximum $ map abs ns

Answer 3

Python, 333 366 ... 315 303 278 269 261 246 chars

n=map(float,raw_input().split())
y=len(n)-1
l=1
def O(f):
 p,q=n[f:y:l],n[f+1::l]
 for a,b in zip(p,q):
    for x in((b-a).__add__,(b/(a or 1)).__mul__):
     if map(x,p)==q:return x
while 1:
 if all(map(O,range(l))):print int(O(y%l)(n[y]));break
 l+=1

Creates operation with first pair of numbers and check it on other pairs. Stores all operations, and if all of them succeed then applies appropriate operation on list last element.

Edited: passes evil test:-) Now search for operation on all positions.

Answer 4

Python, 309 305 295 279 chars

Handles all of the original test cases, as well as Peter Taylor's gnarly 0 0 1 2 3 6 7 14 one:

l=map(int,raw_input().split())
i=v=0
while v<1:
 v=i=i+1
 for j in range(i):
    p=zip(l[j::i],l[j+1::i])
    d,r=set(q[1]-q[0]for q in p),set(q[1]*1./(q[0]or 1)for q in p if any(q))
    m,n=len(d)<2,len(r)<2
    v*=m+n
    if(len(l)-1)%i==j:s=l[-1]+d.pop()if m else int(l[-1]*r.pop())
print s

Ungolfed, with debugging output (very helpful in verifying correctness):

nums = map(int,raw_input().split())
result = None

for i in range(1,len(nums)/2+1):
    print "-- %s --" % i
    valid = 1
    for j in range(i):
        pairs = zip(nums[j::i], nums[j+1::i])
        print pairs

        diffs = [pair[1] - pair[0] for pair in pairs]
        # this is the tough bit: (3, 6) -> 2, (0, 5) -> 5, (5, 0) -> 0, (0, 0) ignored
        ratios = [float(pair[1])/(pair[0] or 1) for pair in pairs if pair[0] != 0 or pair[1] != 0]

        if len(set(diffs))==1:
            print "  can be diff", diffs[0]
            if (len(nums) - 1) % i == j:
                result = nums[-1] + diffs.pop()
        elif len(set(ratios))==1:
            print "  can be ratio", ratios[0]
            if (len(nums) - 1) % i == j:
                result = int(nums[-1]*ratios.pop())
        else:
            print "** invalid period **"
            valid=0
    if valid and result is not None:
        break

print result

Usage:

echo 0 0 1 2 3 6 7 14 | python whatcomesnext.py

Answer 5

Ruby 1.9 (437) (521) (447) (477)

Works for all test cases, including the "evil" one. I'll golf it more later.

EDIT: I realized there's another case that I wasn't handling properly - when the continuation needs to use the "mystery" operation. The sequence 2 0 0 -2 -4 -6 was initially returning 0 instead of -12. I've now fixed that.

EDIT: Fixed a couple more edge cases and cut down the code to 447.

EDIT: Ugh. Had to add some code to handle other "evil" sequences such as 0 0 0 6 18 6 12

def v(c,q);t=*q[0];q.size.times{|i|f=c[z=i%k=c.size]
f=c[z]=(g=q[z+k])==0??_:((h=q[z+k+1])%g==0?"*(#{h/g})":"/(#{g/h})")if f==?_
t<<=f==?_?(a=q[i];b=q[i+1].nil?? 0:q[i+1];(a==0&&b==0)||(a!=0&&(b%a==0||a%b==0))?b:0):eval(t.last.to_s+f)}
*r,s=t
(p s;exit)if q==r
end
s=gets.split.map &:to_i
n=[[]]
((s.size-1)/2).times{|i|a,b=s[i,2]
j=["+(#{b-a})"]
j<<=?_ if a==0&&b==0
j<<="*#{b/a}"if a!=0&&b%a==0
j<<="/#{a/b}"if a*b!=0&&a%b==0
n=n.product(j).map(&:flatten)
n.map{|m|v(m*1,s)}}

Answer 6

Scala

This is the solution I came up with:

object Z extends App{var i=readLine.split(" ").map(_.toInt)
var s=i.size
var(o,v,f)=(new Array[Int](s),new Array[Double](s),1)
def d(p:Int,j:Array[Int]):Unit={if(p<=s/2){def t(){var a=new Array[Int](s+1)
a(0)=i(0)
for(l<-0 to s-1){o(l%(p+1))match{case 0=>a(l+1)=a(l)+v(l%(p+1)).toInt
case _=>a(l+1)=(a(l).toDouble*v(l%(p+1))).toInt}}
if(a.init.deep==i.deep&&f>0){f^=f
println(a.last)}}
o(p)=0 
v(p)=j(1)-j(0)
t
d(p+1,j.tail)
o(p)=1
v(p)=j(1).toDouble/j(0).toDouble
t
d(p+1,j.tail)}}
d(0,i)
i=i.tail
d(0,i)}

Ungolfed:

object Sequence extends App
{
    var input=readLine.split(" ").map(_.toInt)
    var s=input.size
    var (ops,vals,flag)=(new Array[Int](s),new Array[Double](s),1)
    def doSeq(place:Int,ints:Array[Int]):Unit=
    {
        if(place<=s/2) 
        {
            def trysolution()
            {
                var a=new Array[Int](s+1)
                a(0)=input(0)
                for(loop<-0 to s-1)
                {
                    ops(loop%(place+1))match
                    {
                        case 0=>a(loop+1)=a(loop)+vals(loop%(place+1)).toInt
                        case _=>a(loop+1)=(a(loop).toDouble*vals(loop%(place+1))).toInt
                    }
                }
                if(a.init.deep==input.deep&&flag>0)
                {
                    flag^=flag
                    println(a.last)
                }
            }
            ops(place)=0
            vals(place)=ints(1)-ints(0)
            trysolution
            doSeq(place+1,ints.tail)
            ops(place)=1
            vals(place)=ints(1).toDouble/ints(0).toDouble
            trysolution
            doSeq(place+1,ints.tail)
        }
    }
    doSeq(0,input)
    input=input.tail
    doSeq(0,input)
}

Answer 7

Scala 936

type O=Option[(Char,Int)]
type Q=(O,O)
type L=List[Q]
val N=None
def t(a:Int,b:Int):Q=if(a>b)(Some('-',a-b),(if(b!=0&&b*(a/b)==a)Some('/',a/b)else N))else
(Some('+',b-a),(if(a!=0&&a*(b/a)==b)Some('*',b/a)else N))
def w(a:Q,b:Q)=if(a._1==b._1&&a._2==b._2)a else
if(a._1==b._1)(a._1,N)else
if(a._2==b._2)(N,a._2)else(N,N)
def n(l:L):Q=l match{case Nil=>(N,N)
case x::Nil=>x
case x::y::Nil=>w(x,y)
case x::y::xs=>n(w(x,y)::xs)} 
def z(l:L,w:Int)=for(d<-1 to w)yield
n(l.drop(d-1).sliding(1,w).flatten.toList)
def h(s:L):Boolean=s.isEmpty||(s(0)!=(N,N))&& h(s.tail)
def j(s:L,i:Int=1):Int=if(h(z(s,i).toList))i else j(s,i+1)
def k(b:Int,o:Char,p:Int)=o match{case'+'=>b+p
case'-'=>b-p
case'*'=>b*p
case _=>b/p}
val e=getLine 
val i=e.split(" ").map(_.toInt).toList
val s=i.sliding(2,1).toList.map(l=>t(l(0),l(1)))
val H=n(s.drop(s.size%j(s)).sliding(1,j(s)).flatten.toList)
val c=H._1.getOrElse(H._2.get)
println (k(i(i.size-1),c._1,c._2))

ungolfed:

type O = Option[(Char, Int)]

def stepalize (a: Int, b: Int): (O, O) = (a > b) match {
   case true => (Some('-', a-b), (if (b!=0 && b * (a/b) == a) Some ('/', a/b) else None)) 
   case false=> (Some('+', b-a), (if (a!=0 && a * (b/a) == b) Some ('*', b/a) else None)) }

def same (a: (O, O), b: (O, O)) = {
  if (a._1 == b._1 && a._2 == b._2) a else
  if (a._1 == b._1) (a._1, None) else 
  if (a._2 == b._2) (None, a._2) else 
  (None, None)}

def intersection (lc: List[(O, O)]): (O, O) = lc match {
  case Nil => (None, None)
  case x :: Nil => x
  case x :: y :: Nil => same (x, y)
  case x :: y :: xs  => intersection (same (x, y) :: xs)} 

def seriallen (lc: List[(O, O)], w: Int= 1) =
  for (d <- 1 to w) yield 
    intersection (lc.drop (d-1).sliding (1, w).flatten.toList)

def hit (s: List[(O, O)]) : Boolean = s match {
  case Nil => true 
  case x :: xs => (x != (None, None)) && hit (xs)}

def idxHit (s: List[(O, O)], idx: Int = 1) : Int =
  if (hit (seriallen (s, idx).toList)) idx else 
    idxHit (s, idx+1)

def calc (base: Int, op: Char, param: Int) = op match {
  case '+' => base + param
  case '-' => base - param
  case '*' => base * param
  case _   => base / param}

def getOp (e: String) = {
  val i = e.split (" ").map (_.toInt).toList
  val s = i.sliding (2, 1).toList.map (l => stepalize (l(0), l(1)))
  val w = idxHit (s)
  val hit = intersection (s.drop (s.size % w).sliding (1, w).flatten.toList)
  val ci = hit._1.getOrElse (hit._2.get)
  val base = i(i.size - 1)
  println ("i: " + i + " w: " + w + " ci:" + ci + " " + calc (base, ci._1, ci._2))
}

val a="1 3 5 7 9 11"
val b="1 3 2 4 3 5 4 6 5 7 6"
val c="2 6 7 3 9 10 6 18 19 15 45 46"
val d="1024 512 256 128 64 32 16"
val e="1 3 9 8 24 72 71 213 639"
val f="1 2 3 4 5 2 3 4 5 6 3 4 5 6 7"
val g="1 2 4 1 3 9 5 8 32 27 28 56 53 55 165 161 164 656 651 652 1304"
val h="0 0 1 2 3 6 7 14"
val i="0 0 0 0 1 0 0 0 0 1 0"

List (a, b, c, d, e, f, g, h, i).map (getOp)

Fails miserably on Peter Taylor's h, but I don't see the possibility to heal the program in a reasonable amount of time.