home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 3 / AACD03.BIN / AACD / Programming / sofa / archive / SmallEiffel.lha / SmallEiffel / lib_show / pyramid.e < prev    next >
Text File  |  1999-06-05  |  7KB  |  244 lines
  1. --          This file is part of SmallEiffel The GNU Eiffel Compiler.
  2. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  3. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr
  4. --                       http://SmallEiffel.loria.fr
  5. -- SmallEiffel is  free  software;  you can  redistribute it and/or modify it
  6. -- under the terms of the GNU General Public License as published by the Free
  7. -- Software  Foundation;  either  version  2, or (at your option)  any  later
  8. -- version. SmallEiffel is distributed in the hope that it will be useful,but
  9. -- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. -- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License
  11. -- for  more  details.  You  should  have  received a copy of the GNU General
  12. -- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
  13. -- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14. -- Boston, MA 02111-1307, USA.
  15. --
  16. class PYRAMID
  17. --
  18. -- Solving the problem of the Pyramid for small pyramid only.
  19. --
  20. --| This program uses the back-tracking method.
  21. --| Its goal is to try to fill a pyramid by making a substraction
  22. --| between two succesive columns and to take its absolute value.
  23. --| The result is put on the next line.
  24. --| Example :
  25. --|  6 14 15 3 13
  26. --|   8 1 12 10
  27. --|    7 11 2
  28. --|     4  9
  29. --|       5
  30. --
  31. -- See also pyramid2, which run faster than this first solution.
  32.  
  33. inherit
  34.    ANY
  35.       redefine
  36.          out_in_tagged_out_memory
  37.       end;
  38.  
  39. creation make
  40.  
  41. feature
  42.  
  43.    size : INTEGER;
  44.  
  45.    make is
  46.       do
  47.          if argument_count = 0 then
  48.             std_output.put_string("Want to compute a small pyramid ?%N%
  49.                                   %Enter a small number (> 1) : ");
  50.             std_output.flush;
  51.             std_input.read_integer;
  52.             size := std_input.last_integer;
  53.          else
  54.             size := argument(1).to_integer;
  55.          end;
  56.          if size <= 1 then
  57.             std_output.put_string("You feel sick ?%N");
  58.          elseif size > biggest_one then
  59.             std_output.put_string("Value too big for this method.%N");
  60.          else
  61.             !!elem.make(1,max);
  62.             if fill_up(1) then
  63.                std_output.put_string("Full pyramid :%N");
  64.                print_on(std_output);
  65.             else
  66.                std_output.put_string("Unable to fill_up such one.%N");
  67.             end;
  68.          end;
  69.       end; -- make
  70.  
  71.    max : INTEGER is
  72.       do
  73.          Result := (size * (size + 1)) // 2;
  74.       end; -- max
  75.  
  76.    out_in_tagged_out_memory is
  77.       local
  78.          lig,col,nb : INTEGER;
  79.       do
  80.          from
  81.             lig := 1;
  82.             col := 1;
  83.             nb := 0;
  84.          until
  85.             nb = max
  86.          loop
  87.             if col = 1 then
  88.                tagged_out_memory.extend('%N');
  89.             end;
  90.             (elem.item(indice(lig,col))).append_in(tagged_out_memory);
  91.             tagged_out_memory.append(" ");
  92.             if col = size - lig + 1 then
  93.                col := 1 ;
  94.                lig := lig + 1 ;
  95.             else
  96.                col := col + 1;
  97.             end;
  98.             nb := nb + 1;
  99.          end;
  100.          tagged_out_memory.extend('%N');
  101.       end;
  102.  
  103.    belongs_to(nb : INTEGER): BOOLEAN is
  104.       require
  105.          nb_trop_petit: nb >= 1;
  106.          nb_trop_grand: nb <= max;
  107.       local
  108.          i : INTEGER;
  109.          trouve : BOOLEAN;
  110.       do
  111.          from
  112.             i := 1;
  113.             trouve := false;
  114.          until
  115.             ((i > max) or trouve)
  116.          loop
  117.             trouve := (nb = elem.item(i));
  118.             i := i + 1;
  119.          end;
  120.          Result := trouve;
  121.       end; -- belongs_to
  122.  
  123.    propagate (col, val_column_1: INTEGER): BOOLEAN is
  124.       require
  125.          val_column_1 >= 1;
  126.          val_column_1 <= max;
  127.          col >= 1;
  128.          col <= size;
  129.       local
  130.          stop : BOOLEAN;
  131.          lig : INTEGER;
  132.          val : INTEGER;
  133.       do
  134.          if belongs_to(val_column_1) then
  135.             Result := false ;
  136.          else
  137.             from
  138.                elem.put(val_column_1,indice(1,col));
  139.                lig := 1;
  140.                val := val_column_1;
  141.                stop := false;
  142.                Result := true;
  143.             until
  144.                stop
  145.             loop
  146.                lig := lig + 1;
  147.                if lig > col then
  148.                   stop := true;
  149.                else
  150.                   val := val - elem.item(indice(lig-1,col-lig+1));
  151.                   if val < 0 then -- valeur absolue !
  152.                      val := - val ;
  153.                   end;
  154.                   if belongs_to(val) then
  155.                      clear_column(col);
  156.                      stop := true;
  157.                      Result := false;
  158.                   else
  159.                      elem.put(val,indice(lig,col-lig+1));
  160.                   end;
  161.                end;
  162.             end;
  163.          end;
  164.       end; -- propagate
  165.  
  166.    fill_up (col : INTEGER) : BOOLEAN is
  167.       require
  168.          col >= 1;
  169.       local
  170.          stop : BOOLEAN;
  171.          nb : INTEGER;
  172.       do
  173.          if col > size then
  174.             Result := true;
  175.          else
  176.             from
  177.                stop := false;
  178.                nb := max;
  179.             until
  180.                stop
  181.             loop
  182.                if belongs_to(nb) then
  183.                   nb := nb - 1;
  184.                   stop := (nb = 0);
  185.                elseif propagate(col,nb) then
  186.                   if  fill_up(col + 1) then
  187.                      stop := true;
  188.                   else
  189.                      clear_column(col);
  190.                      nb := nb - 1;
  191.                      stop := (nb = 0);
  192.                   end;
  193.                else
  194.                   nb := nb - 1;
  195.                   stop := (nb = 0);
  196.                end;
  197.             end;
  198.             Result := (nb > 0);
  199.          end;
  200.       end; -- fill_up
  201.  
  202. feature {NONE}
  203.  
  204.    elem: ARRAY[INTEGER];
  205.  
  206.    case_vide : INTEGER is 0;
  207.  
  208.    biggest_one: INTEGER is 10;
  209.  
  210.    indice (lig,col : INTEGER): INTEGER is
  211.       require
  212.          lig_trop_petit: lig >= 1 ;
  213.          lig_trop_grand: lig <= size ;
  214.          col_trop_petit: col >= 1 ;
  215.          col_trop_grand: col <= size ;
  216.       local
  217.          l : INTEGER ;
  218.       do
  219.          l:= size - lig + 1;
  220.          Result := max - ((l * (l + 1)) // 2) + col;
  221.       ensure
  222.          Result >= 1 ;
  223.          Result <= max ;
  224.       end; -- indice
  225.  
  226.    clear_column (col : INTEGER) is
  227.       require
  228.          col >= 1;
  229.          col <= size;
  230.       local
  231.          lig : INTEGER;
  232.       do
  233.          from
  234.             lig := 1;
  235.          until
  236.             lig > col
  237.          loop
  238.             elem.put(case_vide,indice(lig,col-lig+1));
  239.             lig := lig + 1;
  240.          end;
  241.       end; -- clear_column
  242.  
  243. end --  PYRAMID
  244.