%tchukarumaRealTREE.m
%state is the vector with all possible game states
%temp is the character string that you need to paste into maple
%in order to run this program type something like
%[a,b]=tchukarumaRealTREE
% a will then contain all of the states and b the stuff to paste into maple
%I think the main command you need to change below is play 
function [state,terminal]=unplay_tree()
bins = input('Please enter the number of bins, excluding the ruma.');
stones = input('Please enter the max number of stones');
%alph=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
%alph=['a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a','a'];
alph=char(97*ones(10000,1)); %works for all a's

fid=fopen('output.mpl','w');
state=zeros(1,bins);
for x=1:bins
	state(1,x)=input('how many in this bin?');
end
terminal(1)=1;
binnum=1;
nummoves(1)=1;
gamelevel = 1;
veclevel=2;
chain(1)=0;
chaining=0;
fprintf(fid,'with(graphtheory):\nb:=Graph(undirected,{');
temp2='c:=Graph(undirected,{';
going=1;

while(going && veclevel<2000 && sum(state(veclevel))<=stones)
    if(chain(gamelevel)~=0)
        chaining=1;
        binnum=chain(gamelevel);
    end
    if(state(gamelevel,binnum)~=0 && terminal(gamelevel)~=0)    
        %[state(veclevel,:),terminal(veclevel),chain(veclevel)]=play(binnum,state(gamelevel,:),bins);
        [new_states,terminal(veclevel),chain(veclevel)]=completely_unplay(state(gamelevel,:));
        state=[state;new_states];
        
        nummoves(veclevel)=nummoves(gamelevel)+1;
        binvec(veclevel)=binnum;
        if(veclevel==2)
            	temp2=strcat(temp2,'[',alph(nummoves(gamelevel)),vec2str(state(gamelevel,:)),',',alph(nummoves(veclevel)),vec2str(state(veclevel,:)),']');
        else
            temp2=strcat(temp2,',[',alph(nummoves(gamelevel)),vec2str(state(gamelevel,:)),',',alph(nummoves(veclevel)),vec2str(state(veclevel,:)),']');
        end
       if(veclevel~=2)
           fprintf(fid,',');
       end
      	fprintf(fid,strcat(',{',num2str(gamelevel),',',num2str(veclevel),'}'));
        veclevel=veclevel+size(new_states);
    end
    if(chaining==1)
        gamelevel=gamelevel+1;
        chaining=0;
        binnum=1;
    else
        if(binnum==bins)
            binnum=1;
            gamelevel=gamelevel+1;
        else
            binnum=binnum+1;
        end
    end

    if(gamelevel+1>veclevel)
        going=0;
    end
    state
end

fprintf(fid,'});\n');
fprintf(fid,strcat(temp2,'});\nDrawGraph(b,style=tree);\n'));
fprintf(fid,'DrawGraph(c,style=circle);\n');


function str=vec2str(v)
    str='';
    for i=1:length(v)
        str=strcat(str,num2str(v(i)));
    end
end


    function [score,board] = advantage(board,choice)
        number_there=board(choice);
        board(choice)=0;
        pos=choice;
        for x=1:number_there
            pos=mod(pos,length(board))+1;
            if(pos==choice)
                pos=mod(pos,length(board))+1;
            end
            board(pos)=board(pos)+1;
        end
        % now, we must steal!
        score=0;
        while((board(pos)==2 || board(pos)==3) && ~same_side(board,choice,pos))
            score=score+board(pos);
            board(pos)=0;
            pos=pos-1;
            if(pos==0)
                pos=length(board);
            end
        end
    end

% calculates the payoff matrix
% for a given board
    function pom(board)
        n=length(board)/2;
        fprintf('[\n');
        for b=1:n
             [p,board2]=advantage(board,b);
           for k=1:n
               q=advantage(board2,k+n);
              fprintf('(%i,%i) ',p,q); 
           end
           fprintf('\n');
        end
        fprintf(']\n');
    end

    function skip=find_skip(state)
        % finding the number we are skipping
        skip=1;
        while(state(skip)~=0 && skip<3)
            skip=skip+1;
        end
    end
    function [fin_state,choice] = unplay_wrapping(state,start_pos,wraps)
        pos=start_pos;
        collection=0;
        % finding the lowest value that isn't the skip bin
        skip=find_skip(state);
        while(state(pos)>0 || wraps>0)
            if(pos==skip && wraps>0)
                wraps=wraps-1;
                if(pos>1)
                    pos=pos-1;
                else
                    pos=length(state);
                end
            elseif(pos~=skip)
                state(pos)=state(pos)-1;
                collection=collection+1;
                if(pos>1)
                    pos=pos-1;
                else
                    pos=length(state);
                end
            end
        end
        state(pos)=collection;
        fin_state=state;
        choice=pos;
    end


    function [fin_states,choices] = unplay(state,start_pos)
        fin_states=zeros(1,length(state));
        choices=zeros(1,1);
        skip=find_skip(state);
        % start 'lowest' on a non-zero
        lowest=1;
        while(state(lowest)==0)
            lowest=lowest+1;
        end
        %set 'lowest' to the index of the min
        for q=1:length(state)
            if(state(q)~=0 && state(q) < state(lowest) && q~=skip)
                lowest=q;
            end
        end
        for wraps=0:state(lowest)
            [fin_states(wraps+1,:),choices(wraps+1,1)] = unplay_wrapping(state,start_pos,wraps);
        end
    end

% tells if a position is on 'my' side
    function is_it = my_side(state,x)
        is_it=same_side(state,1,x);
    end

% are these two positions on the same side?
    function is_it =same_side(state,x,y)
        is_it=false;
        n=length(state)/2;
        if(x>n && y>n)
            is_it=true;
        end
        if(x<=n && y<=n)
            is_it=true;
        end
    end

    function [good_answers,good_choices]=filter_results(answers,choices,state)
        x=1;
        [the_length,the_width]=size(answers);
        while(x<=the_length)
            the_min = min(answers(x,:));
            the_right_min = min(answers(x,floor(the_width/2)+1:the_width));
            test_board=answers(x,:);
            [s,test_result]=advantage(test_board,choices(x,:));
            if(the_min<0 || the_right_min>0 || choices(x)>the_width/2 || isequal(test_result,state)==false)
                answers(x,:)=[];
                choices(x,:)=[];
                x=x-1;
                [the_length,the_width]=size(answers);
            end
            x=x+1;
        end
        good_answers=answers;
        good_choices=choices;
    end

    function amount=zero_length(state,x)
        k=0;
        while(x-k>length(state)/2 && state(x-k)==0)
            k=k+1;
        end
        amount=k;
    end

    function the_array=to_bin_array(x,width)
        bin=dec2bin(x);
        [bin_length,bin_width]=size(bin);
        the_array=zeros(1,width);
        for idx=1:bin_width
            the_array(idx)=bin(bin_width-idx+1)-48;
        end
    end

function [answers,choices,t,c]=completely_unplay(state)
c=0;
t=1;

answers=zeros(1,length(state));
choices=zeros(1,1);
original_state=state;
for j=length(state):-1:1
    if(state(j)==0 && same_side(state,1,j)==false)
        num_zeros=zero_length(state,j);
        % for every combination of 2's and 3's in this 
        % strand of zeros that is num_zeros long
        for b=0:2^(num_zeros)-1
            my_array=to_bin_array(b,num_zeros);
            my_array=my_array+ones(size(my_array))*2;
            state(j-num_zeros+1:j)=my_array(1,1:num_zeros);
            [new_answers,new_choices]=unplay(state,j);
            answers=[answers;new_answers];
            choices=[choices;new_choices];
            state=original_state;
        end
    elseif(state(j)~=0)
        [new_answers,new_choices]=unplay(state,j);
        answers=[answers;new_answers];
        choices=[choices;new_choices];
        state=original_state;
    end
end

answers(1,:)=[];
choices(1,:)=[];
[answers,choices]=filter_results(answers,choices,state);
end


end