advent of code day 11

advent of code day 11

[Stephen Leake]

mildly interesting; variation on Conway's Game of Life.
-- 
-- Stephe

Re: advent of code day 11

[John Perry]

On Friday, December 11, 2020 at 11:08:00 AM UTC-6, Stephen Leake wrote:
> mildly interesting; variation on Conway's Game of Life. 

I recognized that, too. A solution should not be hard to parallelize, and I'd like to, but for now I have other tasks. (no pun intended, well, OK yes it was)

Here's a couple of questions for the Ada experts. For each round I used two charts, a source and a result. These are arrays, defined like so:

   type Status is ( Floor, Empty, Occupied );

   type Chart_Array is array( Positive range <> , Positive range <> ) of Status;

   Chart1, Chart2: Chart_Array; -- actually defined with appropriate dimensions

A procedure named `Iterate_Seating` applies the given rules to a Chart_Array; an `if` statement determines which iterates into the other.

I thought it would be clearer to use references to switch from one chart to the other, but I had trouble doing that last night. Now I can get it this way:

   Source: Chart_Array renames Chart1;
   Result: Chart_Array renames Chart2;

   while Changed loop

      Perform_Round( Source => Source , Result => Result , ... );
      declare Tmp: Chart_Array renames Source;
      begin
         Source := Result;
         Result := Tmp;
      end;

   end loop;

Does this technique swap references, or does it copy the arrays element-by-element? The run times are the same even if I compel a copy operation; I suppose it's because the arrays aren't large enough, and there aren't enough copies, to make a difference.

thanks
john perry

Re: advent of code day 11

[Jeffrey R. Carter]

On 12/11/20 7:24 PM, John Perry wrote:
> 
>     Source: Chart_Array renames Chart1;
>     Result: Chart_Array renames Chart2;
> 
>     while Changed loop
> 
>        Perform_Round( Source => Source , Result => Result , ... );
>        declare Tmp: Chart_Array renames Source;
>        begin
>           Source := Result;
>           Result := Tmp;

Renaming simply creates an additional way to name something. This should be the 
same as

    Chart1 := Chart2;
    Chart2 := Chart1;

-- 
Jeff Carter
"[I]f we should ever separate, my little plum,
I want to give you one little bit of fatherly advice. ... Never
give a sucker an even break."
Poppy
97

Re: advent of code day 11

[gautier...@hotmail.com]

> Perform_Round( Source => Source , Result => Result , ... ); 
> declare Tmp: Chart_Array renames Source; 
> begin 
> Source := Result; 
> Result := Tmp; 
> end; 

To complete Jeff's answer, what you are doing is not a swap: it's equivalent to 
Source := Result;
Result := Source;
Ooops.
The ":=" makes a complete copy of the arrays.
So you'd need above "Tmp : Chart_Array := Source" to have a correct swap with 3 copies.
Of course it feels a bit heavy to make all those copies. And you understandably want to avoid playing with pointers. So a solution is to define:
Map : array (0 .. 1) of Chart_Array;
...
current := 0;
loop
  next := 1 - current;
  Perform_Round( Source => Map (current), Result => Map (next) , ... ); 
  current := next;
end loop;

Re: advent of code day 11

[gautier...@hotmail.com]

Full example in 2 flavours:
https://github.com/zertovitch/hac/blob/master/exm/aoc/2020/aoc_2020_11_full_ada.adb (full Ada only)
https://github.com/zertovitch/hac/blob/master/exm/aoc/2020/aoc_2020_11.adb (HAC & full Ada)

Re: advent of code day 11

[Jeffrey R. Carter]

On 12/11/20 8:29 PM, gautier...@hotmail.com wrote:
> 
> So you'd need above "Tmp : Chart_Array := Source" to have a correct swap with 3 copies.
> Of course it feels a bit heavy to make all those copies. And you understandably want to avoid playing with pointers. So a solution is to define:
> Map : array (0 .. 1) of Chart_Array;
> ...
> current := 0;
> loop
>    next := 1 - current;
>    Perform_Round( Source => Map (current), Result => Map (next) , ... );
>    current := next;
> end loop;

I don't see a need for a swap, or to avoid copying. I did

Current : Floorplan := Read;
Future  : Floorplan := (others => (others => Floor) );
...
All_Rounds : loop
    for R in ... loop
       for S in ... loop
          if Current (R, S) /= Floor then -- It's a seat
             Future (R, S) :=
                Next_State (Current (R, S), Num_Occupied (Current, R, S) );
          end if; -- else Future (R, S) = Floor
       end loop;
    end loop;

    exit All_Rounds when Current = Future;

    Current := Future;
end loop All_Rounds;

which took 34 ms, well within the timing requirements for the problem.

-- 
Jeff Carter
"[I]f we should ever separate, my little plum,
I want to give you one little bit of fatherly advice. ... Never
give a sucker an even break."
Poppy
97

Re: advent of code day 11

[John Perry]

On Friday, December 11, 2020 at 4:40:51 PM UTC-6, Jeffrey R. Carter wrote:
> I don't see a need for a swap, or to avoid copying. I did 
> 
> Current : Floorplan := Read; 
> Future : Floorplan := (others => (others => Floor) ); 
> ... 
> 
> Current := Future; 
> end loop All_Rounds; 
> 
> which took 34 ms, well within the timing requirements for the problem.

I agree it's not needed in this case. I raised the question simply because I'd like to know how it could be done in cases where it might well be important to save the time. I've sometimes shaved significant percentages of running time off programs by doing nothing more than avoiding copying arrays.

Re: advent of code day 11

[John Perry]

On Friday, December 11, 2020 at 1:29:58 PM UTC-6, gautier...@hotmail.com wrote:
> The ":=" makes a complete copy of the arrays.

That's what I was afraid of. 

> Of course it feels a bit heavy to make all those copies. And you understandably want to avoid playing with pointers.

Exactly!

So a solution is to define: 
> Map : array (0 .. 1) of Chart_Array; 
> ... 
> current := 0; 
> loop 
> next := 1 - current; 
> Perform_Round( Source => Map (current), Result => Map (next) , ... ); 
> current := next; 
> end loop;

This is a nice alternative, thanks.

Re: advent of code day 11

[Maxim Reznik]

Perhaps you might be interested in using generics for this solution

https://github.com/reznikmm/ada-howto/blob/advent-2020/md/11/11.md

Re: advent of code day 11

[Stephen Leake]

John Perry <john.perry@usm.edu> writes:

> On Friday, December 11, 2020 at 11:08:00 AM UTC-6, Stephen Leake wrote:
>> mildly interesting; variation on Conway's Game of Life. 
>
> I thought it would be clearer to use references to switch from one
> chart to the other, but I had trouble doing that last night. Now I can
> get it this way:
>
>    Source: Chart_Array renames Chart1;
>    Result: Chart_Array renames Chart2;

A 'renames' declaration creates a _static_ name for the object that is
the result of the expression; the expression is evaluated once when the
'renames' declaration is evaluated. When the name is used, it is the
same as any other object name.

>    while Changed loop
>
>       Perform_Round( Source => Source , Result => Result , ... );
>       declare Tmp: Chart_Array renames Source;

'Tmp' is evaluated each time around the loop, but since the global
Source is static, it always has the same value of Chart1.

>       begin Source := Result;

This does not revaluate the expression for global Source; it uses the
global Source name to determine where to store a copy of Result.

-- 
-- Stephe