FANDOM


Постановка (kost)


Как насчет вот такой задачки: "Посчитай закономерность".
Есть последовательность из 1000-2000 чисел, в которой каждые 2-5 (число постоянное) чисел (числа целые, от 0 до 10000, а еще интереснее сделать любой длинны) идут по какому-то алгоритму, а потом по закономерности. Возможные операции - "+-*/" (деление целочисленное). Изначально ноль. Тоесть например если закономерность такая:
+5 *60 /4 +18 +19
то входной файл будет
5 300 75 93 112 117 7020 1755 ...

Задача - определить алгоритм. А потом будем расширять добавлением парочки новых операторов и т.п. и т.д.
Если никто не против - могу накатать полное условие по-быстрячку и поехали)


TODO: разобраться, как постить отформатированный код с подсветкой (raw non-escaped HTML or smth?)

ACHTUNG!!! Не редактировать в rich editor'е! Он портит листинги! Нажимать в правом верхнем углу кнопочку с чёрненькой консолькой и редактировать сорсы. Примеры кодов вставлять внутрь <pre></pre>

Smalltalk/Seaside, danio, link (no sources)k



Python, gromozeka, 25.07.2007, link , link2, link3, link4 , link5

def action(n1,n2):
   l=set([])
   if n1==0 and n2==0:l|=set(["*any"])    
   if n1<=n2:l|=set(['+'+str(n2-n1)])
   else:l|=set(['-'+str(n1-n2)])
   for (a,b,op) in [(n1,n2,"*"),(n2,n1,'/')]:
       if a!=0:
           arg=b/a
           if (op=="*" and arg*a==b) or (op=="/" and arg!=0):
               l|=set([op+str(arg)])
               if (op=="/" and b%a==0):
                   if b/a<0:s=-1
                   else:s=1
                   a,b=abs(a),abs(b)
                   for arg in xrange(b/(a+1)+1,b/a+1):
                       l|=set([op+str(arg*s)])              
   return l

def my_and(x,y):
    res,tmp=x&y,lambda x:set([e for e in list(x) if e[0] in '*/'])
    if '*any' in x: res|=tmp(y)
    if '*any' in y: res|=tmp(x)
    return res
        
def nth(l,n,start): return [l[i] for i in xrange(start,len(l),n)]
def intr(l): return reduce(lambda x,y:my_and(x,y),l)
def hypo(a,n): return [intr(nth(a,n,i)) for i in xrange(0,n)]
    
def find_alg(l):
    acts=[action(l[i-1],l[i]) for i in xrange(1,len(l))]
    for i in xrange(1,len(acts)):
        if my_and(acts[i],acts[0])!=set([]):
            t=hypo(acts,i)
            if not(set([]) in t):
                acts=t; break
    return ''.join([el[0] for el in map(list,acts)])

C++, D_K, 25.07.2007, link , link2, link3

class modif
{
    struct data{
        char c;
        int i;
        bool en_i;
        data():c(0),i(-1),en_i(false){}
        data(char c_, int i_, bool en_i_=true):c(c_),i(i_),en_i(en_i_){}
        int operator()(int i_)const{return c=='+'? i_+i : c=='-'? i_-i : c=='*'? i_*i : i_/i;}
        bool find(int x,int y)
        {
            if(en_i) return (*this)(x)==y;
            if( c=='+' || c== '-' || (c=='*' && (abs(x)>abs(y) || !x && x!=y)) || (c=='/' && (abs(y)>abs(x) || !y )) )
                return false;
            i= c=='/'? x/y : !x? 0: y/x;
            if(c=='/'&&(!i || i==1)) return false;
            return true;
        }
        friend ostream& operator<<(ostream &os, const data &d){os<<d.c<<d.i;return os;}
    } var[4];
    int active;
    int n;
public:
    modif():active(-1),n(0){}
    modif(int x, int y):active(0),n(1)
    {
        if(x==y){
            var[0]= x==0 ? data('*', -1, false) : data('*', 1);
            var[n++]= x==0 ? data('/', -1, false) : data('/', 1);
            return;
        }
        var[0] = abs(y)>abs(x) ? data('+',y-x) : data('-', x-y);
        if(abs(y)>abs(x) && x && y%x==0)
            var[n++] = data('*',y/x);
        if(abs(x)>abs(y) && y && x )
            var[n++] = (x%y==0)? data('/',x/y,false) : data('/',-1,false);
    }
    bool find(int x, int y)
    {
        for(active=0; active<n; ++active)
            if(var[active].find(x,y)) return true;
        return (active=0, false);
    }
    int operator()(int i)const{return var[active](i);}
    friend ostream& operator<<(ostream &os, const modif &m){os<<m.var[m.active]; return os;}
};
bool find_alg(istream &in, ostream &out)
{
    int i;
    in>>i;
    if(i) return false;
    vector<int> buf(1,i);
    int ni;
    while(!in.eof()){
        in>>ni;
        buf.push_back(ni);
    }
    unsigned buf_i=1, buf_sz=buf.size();
    vector<modif> alg;
    alg.push_back(modif(i,buf[1]));
    i=buf[buf_i++];
    while(buf_i < buf_sz){
        ni = buf[buf_i++];
        bool flg=alg[0].find(i,ni);
        if(flg){
            unsigned alg_sz=alg.size();
            for(int p=0; p<alg_sz && flg && buf_i-1+p<buf_sz; ++p)
                flg = alg[p].find(buf[buf_i-2+p],buf[buf_i-1+p]);
            if(flg){
                for(int ind=buf_i-2+alg_sz,p=0; ind<buf_sz-1 && flg; ++ind,++p)
                    flg = alg[(p==alg_sz? p=0 : p)](buf[ind])==buf[ind+1];
                if(flg){
                    out<<alg[0];
                    for(int p=1;p<alg_sz;++p)out<<" "<<alg[p];
                    return true;
                }
            }
        }
        if(!flg)
            alg.push_back(modif(i,ni));
        i=ni;
    }
    return false;
}


Python, Vladimir the Red Sunny, 25.07.2007, link

import functools

def evaluate_candidate(candidate, sequence, n):
    match = True
    for i in range(0, len(sequence)-1, n):
        if candidate(sequence[i]) != sequence[i+1]:
            match = False
            break
    return match

def search(i_numbers, n):
    numbers = i_numbers[:]
    final_candidates = []
    for i in range(n):
        candidates = []
        
        def fn(a, b):
            return lambda x: x + a - b
        
        candidates.append( fn(numbers[i+1], numbers[i]) )
        candidates[-1].description = " + " + `numbers[i+1] - numbers[i]`
        if numbers[i] != 0:
            if numbers[i+1]%numbers[i] == 0:
                
                def fn(a, b):
                    return lambda x: x* (a / b)
                
                candidates.append( fn(numbers[i+1], numbers[i]) )
                candidates[-1].description = " * " + `numbers[i+1] / numbers[i]`
            
            if (numbers[i+1] != 0) and (numbers[i]%numbers[i+1] == 0):
                
                def fn(a, b):
                    return lambda x: x / (a / b)
                
                candidates.append( fn(numbers[i], numbers[i+1]) )
                candidates[-1].description = " / " + `numbers[i] / numbers[i+1]`
        
        eval_func = functools.partial(evaluate_candidate, sequence = numbers[i:], n = n)
        tmp_candidates = filter(eval_func, candidates)
        
        if len(tmp_candidates) < 1:
            print "Error: no matches"
            return None
        
        if len(tmp_candidates) > 1:
            print "Error: more than one match"
            return None
        final_candidates.extend(tmp_candidates)
        
    return final_candidates

#+5*60/4+18+19
n = 5
control_seq = [0, 5, 300, 75, 93, 112, 117, 7020, 1755]

ops = search(control_seq, n)
if ops:
    s = "".join([f.description for f in ops])
    print s
else:
    print "Nothing found."



Visual Prolog 7.x, Винитарх, 26.07.2007, link , link2, link3 , link4

open core,console,string,list,std
domains
pair = p(integer,integer).
pair_list = pair*.
pair_list_list = pair_list*.

class predicates
ку: (integer_list) -> string procedure.
тесты: (pair_list_list) -> string nondeterm.
тест: (pair_list,string,integer) nondeterm (i,i,i).
oper: (pair,string,integer)  nondeterm (i,o,o).
check: (pair,string,integer)  determ (i,i,i).
выборки: (integer_list,integer,core::positive) -> pair_list_list procedure.
выборка: (integer_list,integer,integer,core::positive) -> pair_list procedure.

clauses
ку(L)=A:-To= list::length(L)-2,A=тесты(выборки(L,To,fromto(1,To+1))),!.
ку(_)="Ку".

тесты([V|L])= concat(O,toString(A),тесты(L)):- oper(getMember_nd(V),O,A), тест(V,O,A).
тесты([])="".

тест([P|V],O,A):-check(P,O,A),!,тест(V,O,A).
тест([],_,_).

oper(p(X,Y),O,A):- X<=Y, A=Y-X, O="+"; X>Y, A=X-Y, O="-"; X<>0, A=Y quot X, Y rem X=0, O="*";
   Y<>0, Arg=X quot Y, (Arg>=0, A=downTo(Arg,2); Arg<=0, A=fromTo(Arg,-2)), X quot A = Y, O="/".
check(p(X,Y),O,A):- O="+", X+A=Y; O="-", X-A=Y; O="*", X*A=Y; O="/", X quot A=Y.

выборки(L,To,Step)= [X||From=fromto(0,Step-1),X=выборка(L,From,To,Step)].
выборка(L,From,To,Step)= [p(X,Y)||I= fromtoInStep(From,To,Step), X=nth(I,L), Y=nth(I+1,L)].

Python, Кошмар, 27.07.2007, link , link2 (это не другая задача?)




Lisp, DeefFinder, 27.07.2007, link (вроде, программа не обрабатывает много чего, стоит включать? - VtRS)




C++, IL_Agent, 29.07.2007, link




C, D_K, 01.08.2007, link




Haskell, Vladimir the Red Sunny, 08.08.2007, link, link2, link3 (no source)




Python (без лямбд), gromozeka, 12.08.2007, link




K, zevun, 29.08.2007, link, link2



(вроде, всё, позже никто не решал?)