--          This file is part of SmallEiffel The GNU Eiffel Compiler.
--          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
--            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr
--                       http://SmallEiffel.loria.fr
-- SmallEiffel is  free  software;  you can  redistribute it and/or modify it
-- under the terms of the GNU General Public License as published by the Free
-- Software  Foundation;  either  version  2, or (at your option)  any  later
-- version. SmallEiffel is distributed in the hope that it will be useful,but
-- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
-- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License
-- for  more  details.  You  should  have  received a copy of the GNU General
-- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
-- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-- Boston, MA 02111-1307, USA.
--
class PYRAMID
--
-- Solving the problem of the Pyramid for small pyramid only.
--
--| This program uses the back-tracking method.
--| Its goal is to try to fill a pyramid by making a substraction
--| between two succesive columns and to take its absolute value.
--| The result is put on the next line.
--| Example :
--|  6 14 15 3 13
--|   8 1 12 10
--|    7 11 2
--|     4  9
--|       5
--
-- See also pyramid2, which run faster than this first solution.

inherit
   ANY
      redefine
         out_in_tagged_out_memory
      end;

creation make

feature

   size : INTEGER;

   make is
      do
         if argument_count = 0 then
            std_output.put_string("Want to compute a small pyramid ?%N%
                                  %Enter a small number (> 1) : ");
            std_output.flush;
            std_input.read_integer;
            size := std_input.last_integer;
         else
            size := argument(1).to_integer;
         end;
         if size <= 1 then
            std_output.put_string("You feel sick ?%N");
         elseif size > biggest_one then
            std_output.put_string("Value too big for this method.%N");
         else
            !!elem.make(1,max);
            if fill_up(1) then
               std_output.put_string("Full pyramid :%N");
               print_on(std_output);
            else
               std_output.put_string("Unable to fill_up such one.%N");
            end;
         end;
      end; -- make

   max : INTEGER is
      do
         Result := (size * (size + 1)) // 2;
      end; -- max

   out_in_tagged_out_memory is
      local
         lig,col,nb : INTEGER;
      do
         from
            lig := 1;
            col := 1;
            nb := 0;
         until
            nb = max
         loop
            if col = 1 then
               tagged_out_memory.extend('%N');
            end;
            (elem.item(indice(lig,col))).append_in(tagged_out_memory);
            tagged_out_memory.append(" ");
            if col = size - lig + 1 then
               col := 1 ;
               lig := lig + 1 ;
            else
               col := col + 1;
            end;
            nb := nb + 1;
         end;
         tagged_out_memory.extend('%N');
      end;

   belongs_to(nb : INTEGER): BOOLEAN is
      require
         nb_trop_petit: nb >= 1;
         nb_trop_grand: nb <= max;
      local
         i : INTEGER;
         trouve : BOOLEAN;
      do
         from
            i := 1;
            trouve := false;
         until
            ((i > max) or trouve)
         loop
            trouve := (nb = elem.item(i));
            i := i + 1;
         end;
         Result := trouve;
      end; -- belongs_to

   propagate (col, val_column_1: INTEGER): BOOLEAN is
      require
         val_column_1 >= 1;
         val_column_1 <= max;
         col >= 1;
         col <= size;
      local
         stop : BOOLEAN;
         lig : INTEGER;
         val : INTEGER;
      do
         if belongs_to(val_column_1) then
            Result := false ;
         else
            from
               elem.put(val_column_1,indice(1,col));
               lig := 1;
               val := val_column_1;
               stop := false;
               Result := true;
            until
               stop
            loop
               lig := lig + 1;
               if lig > col then
                  stop := true;
               else
                  val := val - elem.item(indice(lig-1,col-lig+1));
                  if val < 0 then -- valeur absolue !
                     val := - val ;
                  end;
                  if belongs_to(val) then
                     clear_column(col);
                     stop := true;
                     Result := false;
                  else
                     elem.put(val,indice(lig,col-lig+1));
                  end;
               end;
            end;
         end;
      end; -- propagate

   fill_up (col : INTEGER) : BOOLEAN is
      require
         col >= 1;
      local
         stop : BOOLEAN;
         nb : INTEGER;
      do
         if col > size then
            Result := true;
         else
            from
               stop := false;
               nb := max;
            until
               stop
            loop
               if belongs_to(nb) then
                  nb := nb - 1;
                  stop := (nb = 0);
               elseif propagate(col,nb) then
                  if  fill_up(col + 1) then
                     stop := true;
                  else
                     clear_column(col);
                     nb := nb - 1;
                     stop := (nb = 0);
                  end;
               else
                  nb := nb - 1;
                  stop := (nb = 0);
               end;
            end;
            Result := (nb > 0);
         end;
      end; -- fill_up

feature {NONE}

   elem: ARRAY[INTEGER];

   case_vide : INTEGER is 0;

   biggest_one: INTEGER is 10;

   indice (lig,col : INTEGER): INTEGER is
      require
         lig_trop_petit: lig >= 1 ;
         lig_trop_grand: lig <= size ;
         col_trop_petit: col >= 1 ;
         col_trop_grand: col <= size ;
      local
         l : INTEGER ;
      do
         l:= size - lig + 1;
         Result := max - ((l * (l + 1)) // 2) + col;
      ensure
         Result >= 1 ;
         Result <= max ;
      end; -- indice

   clear_column (col : INTEGER) is
      require
         col >= 1;
         col <= size;
      local
         lig : INTEGER;
      do
         from
            lig := 1;
         until
            lig > col
         loop
            elem.put(case_vide,indice(lig,col-lig+1));
            lig := lig + 1;
         end;
      end; -- clear_column

end --  PYRAMID