15
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is division guaranteed to be exact? \$\endgroup\$ – Peter Taylor Aug 18 '11 at 16:25
  • \$\begingroup\$ @Peter Yes. Every step will result in an integer. \$\endgroup\$ – Gareth Aug 18 '11 at 16:26
  • \$\begingroup\$ But if the step is "/3", is it guaranteed that the remainder will always be 0? \$\endgroup\$ – Peter Taylor Aug 18 '11 at 16:46
  • \$\begingroup\$ @Peter Yes, remainder will always be 0. \$\endgroup\$ – Gareth Aug 18 '11 at 20:53
  • 3
    \$\begingroup\$ oeis.org \$\endgroup\$ – Thomas Eding Aug 18 '11 at 21:34
12
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you very much for posting an explanation! I've been looking for dissected Golfscript programs so I can try to make more sense of them. \$\endgroup\$ – migimaru Aug 22 '11 at 23:29
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice idea for how to handle non-exact division. \$\endgroup\$ – Peter Taylor Aug 19 '11 at 5:40
  • \$\begingroup\$ It was an accidental side-effect. Searching for a solution was just my initial idea on how to solve this problem, as to me, it felt like a simpler task than computing the answer. \$\endgroup\$ – Thomas Eding Aug 19 '11 at 7:58
  • \$\begingroup\$ Is Control.Monad -> Monad possible? And how about interact$show.n.q read.words \$\endgroup\$ – FUZxxl Aug 20 '11 at 11:40
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice. Passes all my tests, but not Peter Taylor's particularly evil one: 0 0 1 2 3 6 7 14 \$\endgroup\$ – Gareth Aug 19 '11 at 9:29
  • \$\begingroup\$ 0 0 0 0 1 0 0 0 0 1 does not output 0. \$\endgroup\$ – Thomas Eding Aug 19 '11 at 20:51
  • \$\begingroup\$ @trinithis That input doesn't conform to the spec. The sequence of operations must repeat completely at least once. \$\endgroup\$ – Gareth Aug 19 '11 at 21:11
  • 1
    \$\begingroup\$ Oooh, here's a fun improvement: lambda x:x+b-a --> (b-a).__add__. Too bad it's only one character, I'm learning so much about python by doing these. \$\endgroup\$ – Clueless Aug 23 '11 at 9:17
  • 1
    \$\begingroup\$ Making l implicitly global saves a lot: pastie.org/2416407 \$\endgroup\$ – Clueless Aug 23 '11 at 11:54
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I've upvoted, though strictly speaking the input should be via stdin rather than command arguments. \$\endgroup\$ – Gareth Aug 21 '11 at 22:06
  • \$\begingroup\$ That actually lets me shorten the program by four characters :) \$\endgroup\$ – Clueless Aug 21 '11 at 22:29
  • \$\begingroup\$ Few chars, i=v=0 and while v==0: \$\endgroup\$ – Ante Aug 22 '11 at 8:57
  • \$\begingroup\$ @Ante thanks, I thought you couldn't do that in python because assignment isn't an expression, but it's a helpful tidbit for golfing. Literal tabs as the second level indentation also helps. \$\endgroup\$ – Clueless Aug 23 '11 at 8:11
  • \$\begingroup\$ I'm not a Pythoner, but you seem to be using booleans as integers in some expressions, and yet can't use integer v as a boolean in the while test. Is that right? If so, surely v<1 works as a guard. \$\endgroup\$ – Peter Taylor Aug 23 '11 at 8:28
2
\$\begingroup\$

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)}}
\$\endgroup\$
1
\$\begingroup\$

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)
}
\$\endgroup\$
  • \$\begingroup\$ How do I invoke it? echo "0 0 1 2 3 6 7 14" | scala Sequence keeps the screen black. \$\endgroup\$ – user unknown Aug 22 '11 at 17:32
  • \$\begingroup\$ @user unknown scala Sequence and then enter the sequence and press enter. \$\endgroup\$ – Gareth Aug 22 '11 at 21:23
  • \$\begingroup\$ Ah, you wrote in the questions comment, that you don't solve this specific one - it works with echo - pipe as above for the solvable questions. \$\endgroup\$ – user unknown Aug 22 '11 at 22:16
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Would it help to shrink it if you treated - as a special case of + and / as a special case of *? My way of passing Peter Taylor's (and similar) input was to chop off the first number in the sequence and try again. I haven't had time to look at how your program works yet to know if that would help with yours. \$\endgroup\$ – Gareth Aug 22 '11 at 17:25
  • \$\begingroup\$ I guess it would help, but only for that special case. A series which contains the null-multiplication later, like -1, 0, 0, 1, 2, 3, 6, 7, 14 will need a different healing. \$\endgroup\$ – user unknown Aug 22 '11 at 19:26

Your Answer

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

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