Что будет дальше?

Учитывая разделенный пробелами список целых чисел, ваша задача состоит в том, чтобы найти следующее целое число в последовательности. Каждое целое число в последовательности является результатом применения единой математической операции ( +, -, *или /) к предыдущему целому, и каждая последовательность состоит из переменного числа таких операций (но не более 10). Ни одна последовательность не будет длиннее половины длины последовательности целых чисел, поэтому каждая последовательность операций должна появляться как минимум дважды для подтверждения.
Ввод будет через стандартный ввод (или promptдля решений JavaScript).

Вот несколько пояснительных примеров.

Входные данные:

1 3 5 7 9 11

Выход:

13

Довольно легко, этот. Все значения являются предыдущими +2.

Входные данные:

1 3 2 4 3 5 4 6 5 7 6

Ouput:

8

Два шага в этой последовательности, а +2затем -1.

Входные данные:

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

Выход:

42

Три шага - *3, +1, -4.

Контрольные примеры

Вот еще несколько тестов:

Входные данные:

1024 512 256 128 64 32 16

Выход:

8

Входные данные:

1 3 9 8 24 72 71 213 639

Выход:

638

Входные данные:

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

Выход:

4

Входные данные:

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

Выход:

1301

У меня есть решение Scala (42 строки), которое я опубликую через пару дней.

Это код-гольф - самый короткий ответ выигрывает.

Golfscript, 203 138 символов

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

Это использует гораздо больше, ifчем стандартная программа Golfscript, и ее работа довольно загадочна, так что здесь есть закомментированная (но не зацикленная, кроме добавления пробела и комментариев) версия:

~]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])

Мое оригинальное представление было следующим в 88 символов:

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

Тем не менее, он пытается вычислить операции из первого вхождения каждого из них, поэтому, если операция является умножением или делением, а аргумент в первый раз равен 0, он прерывается.

Haskell, 276 261 259 257 243 символов

Вот мое неэффективное решение. Он работает с неограниченными (и ограниченными) целыми числами. Такое решение работает правильно с неточным делением (например:) 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

Как это работает: я создаю все возможные последовательности (возможных) операций. Затем я проверяю последовательность входных чисел, чтобы увидеть, будет ли сгенерированная последовательность создавать входные данные. Если это так, верните следующий номер в последовательности. Код всегда возвращает ответ, полученный из кратчайшей последовательности операций. Это происходит потому, что список последовательностей операций создается в этом порядке. Это произвольный (но последовательный) выбор между связями. Например, код возвращается 6или 8для последовательности 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

Python, 333 366 ... 315 303 278 269 261 246 символов

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

Создает операцию с первой парой чисел и проверяет ее на других парах. Сохраняет все операции, и если все они выполняются успешно, применяет соответствующую операцию к последнему элементу списка.

Отредактировано: проходит злой тест :-) Теперь ищите работу по всем позициям.

Питон, 309 305 295 279 символов

Обрабатывает все оригинальные тестовые случаи, а также грубый тест Питера Тейлора 0 0 1 2 3 6 7 14:

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, с выводом отладки (очень полезно при проверке правильности):

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

Использование:

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

Рубин 1,9 (437) (521) (447) (477)

Работает для всех тестовых случаев, включая «злой». Я буду играть в гольф позже.

РЕДАКТИРОВАТЬ: я понял, что есть еще один случай, который я не обрабатывал должным образом - когда продолжение должно использовать операцию «тайна». Последовательность 2 0 0 -2 -4 -6изначально возвращала 0 вместо -12. Я сейчас исправил это.

РЕДАКТИРОВАТЬ: Исправлено еще несколько крайних случаев и сократить код до 447.

РЕДАКТИРОВАТЬ: тьфу. Пришлось добавить некоторый код для обработки других «злых» последовательностей, таких как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)}}

Scala

Это решение, которое я придумал:

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)
}

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)

С треском проваливается на Питера Тейлора h, но я не вижу возможности вылечить программу за разумное время.