Expression

http://golf.shinh.org/p.rb?Expression
遅いのは再帰のせいか配列か。３つめ10秒以上で登録失敗する
expression-0.3.rb

def ex a,b,l
 z=[]
 l.times{|i|
  if i==b;z+=[a[i]-a[i+1]]
  elsif i==b+1
  else
   z+=[a[i]]
  end
 }
 z
end

$y=[]
def exp a,l
 z=[]
 (l-1).times{|i|
  z=ex(a,i,l)
  if l==2
   $y += z
  else
   exp z,l-1
  end
 }
 $y
end

a=gets.split(" ")
a.map!{|i|i.to_i}
l=a.length
puts exp(a,l).sort.uniq

c++、さらに遅くなった。borland cで3分。まあもっと根本的な問題かな
expression-0.cpp

#include <list>
#include <string>
#include <iostream>
#include <functional>
using namespace std;

void pr( list<int> l)
{
	list<int>::iterator it = l.begin();
	int c=10000;
	while( it != l.end() ) 
	{
		bool f;
		f=(c==*it);
		c=*it;
		++it;
		if(f) continue;
		cout << c ;
		cout<<endl;
	}
}

int get(list<int> l,int num)
{
	list<int>::iterator it = l.begin();
	for(;num>0;num--) 
	{
		++it;
	}
	return *it;
}


list<int> z;
list<int> ex(list<int> a,int b)
{
	z.clear();
	int l=a.size();
	for(int i=0;i<l;i++){
		if(i==b){
			z.push_back(get(a,i)-get(a,i+1));
		}
		else if(i==b+1);
		else
			z.push_back(get(a,i));
	}
	return z;
}

list<int> y;
list<int> exp( list<int> a)
{
	int l=a.size();
	list<int> x;
	for(int i=0;i<l-1;i++){
		x=ex(a,i);
		if(l==2){
			y.push_back( get(x,0) );
		}
		else{
			exp(x);
		}
	}
	return y;
}

int main()
{

	list<int> intlist,cpl;
	int i;

	char buf[100],*p;
	int y=0;
	while(1)
	{
		if(fgets(buf,sizeof(buf),stdin) == 0)break;
		//cout<<buf;
		p=buf;
		while(*p!=0){
			sscanf(p,"%d",&y);
			intlist.push_back( y );
			while(*p!=' ' && *p!=0){
				p++;
			}
			if(*p!=0)p++;
		}
		break;
	}
	intlist=exp(intlist);
	intlist.sort(  );//greater<int>()
	pr(intlist);
	return 0;
}

改良
括弧をばらして、1-1-(1-(1-1)) => 1-1-1+1-1　など
すべて調べる。
cだと　(+1)(-1)(-1)(+1)(-1) とかか

# expression2-0.rb

def e a
 [eval a]
end
def g j,i,c
 a=("0"*c+j.to_s(2))[-c..-1]
 if(a[i..i]!=nil);a[i..i]=="0" ? "+":"-";else;"-";end
end

a=gets.split(" ")
c=a.length-2
b=a*"-"
x=[]
x+=e b
(2**c).times{|j|
 b=a[0]+"-"
 (c+1).times{|i|
  s=g j+1,i,c
  b+=a[i+1]+s
 }
 b+="0"
 x+=e b
}
puts x.sort.uniq