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



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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.