Xah Talk Show 2024-10-31 Ep595, Wolfram Language, Detect Nesting Function Periodicy, Advent of Code 2023, Day 14 Part 2, Take 4

https://youtu.be/kAK9L15YUUE

(* HHHH--------------------------------------------------- *)

(* simple example of a discrete periodic function *)
Clear[xmod5]
xmod5[x_] := Mod[ x, 5 ];

Table[{x, xmod5[x]}, {x, 0, 20}]
(* {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 0}, {6, 1}, {7, 2}, {8, 3}, {9, 4}, {10, 0}, {11, 1}, {12, 2}, {13, 3}, {14, 4}, {15, 0}, {16, 1}, {17, 2}, {18, 3}, {19, 4}, {20, 0}} *)

(* HHHH--------------------------------------------------- *)

(*
the periodic of function
is different from the period of nesting the function.
for example
xmod5[x_] := Mod[ x, 5 ]
has period 5.
but if you nest xmod5, then the period is 1.
 *)

(* HHHH--------------------------------------------------- *)

(*
what is period defined.
it means, the sequence of output repeats.
 *)

(* HHHH--------------------------------------------------- *)

(*
is it possible for a discrete function to have a
different nesting period for different init value.
yes.

not sure what's a simple example,
but lots in
dynamical systems
butterfly effect

*)

(* HHHH--------------------------------------------------- *)
(*
Hailstone function.
If the number is even, divide it by two.
If the number is odd, triple it and add one.

this is a example, where the nesting period does not depends on init value. it's always 3.

*)

Clear[hailstone];

hailstone[x_] := If[ EvenQ[ x ], x/2, x 3 + 1];

NestList[ hailstone, 27, 99 ]

(* HHHH--------------------------------------------------- *)

(*
given a list,
determine if the tail of the list repeats, aka cycle.
e.g. {5, 9, 3, 2, 9, 3, 2, 9}
write a function.

Algo:
check if last 2 elements is same. If so, cycle is 1.
Check if last 4 elements is a cycle, e.g. {a b a b} if so, cycle is 2.
Check if last 6 elements is a cycle, e.g. {a b c a b c}
if so, cycle is 3.
This is 2*n
and so on.
Until 2*n is greater than length of list
*)

Clear[xFindCyclicTail]

xFindCyclicTail::usage = "xFindCyclicTail[list]
Return a list of the tail cycle.
If none, return empty list."

xFindCyclicTail = Function[{xlist},
If[
MatchQ[ xlist, {head___, tail__ , tail__ } ]
, Replace[ xlist, {head___, tail__ , tail__ } -> {tail} ] , {}]
];

xFindCyclicTail[{9,3,2,3,2}]
(* {3, 2} *)

(* HHHH--------------------------------------------------- *)

(*

write a function to detect periodicy of nesting
a given discrete function.

algo:
compute the function starting at init value.
nest in, for n times.

for each time you compute the function,
save the value as a history list,
and, compare, if current value is in history list.

if the current output match a value in history,
then, when you compute the next value, you need to check
if it match the next value in history.
do this check again, until, an output is the init matched value in history list.

*)

Clear[xGetNestPeriod];

xGetNestPeriod::usage = "xGetNestPeriod[f , init , maxNest]
return the period of nesting a discrete function f.
init is the initial value.
maxNest is the maximum nesting.";

xGetNestPeriod[f_ , init_ , maxNest_] :=
Module[ {xtestF, xresult},
xtestF = Function[ xresult = xFindCyclicTail @ {##}; If[ xresult === {} , True , False] ];
NestWhile[ f , init, xtestF, All, maxNest ];
Length @ xresult
];

xGetNestPeriod[xmod5, 99, 1000]
(* 1 *)

xGetNestPeriod[ hailstone, 27, 1000]
(* 3 *)

(* HHHH--------------------------------------------------- *)

Clear[xFindCyclicTail]

xFindCyclicTail::usage = "xFindCyclicTail[list]
Return a list of the tail cycle.
If none, return empty list.";

xFindCyclicTail = Function[{xlist},
If[
MatchQ[ xlist, {head___, tail__ , tail__ } ] ,
Replace[ xlist, {head___, tail__ , tail__ } -> {tail} ] ,
 {}]
];

Clear[xGetNestPeriod];

xGetNestPeriod::usage = "xGetNestPeriod[f , init , maxNest]
return the period of nesting a discrete function f.
init is the initial value.
maxNest is the maximum nesting.";

xGetNestPeriod[f_ , init_ , maxNest_] :=
Module[ {xtestF, xresult},
xtestF = Function[ xresult = xFindCyclicTail @ {##};
Print[ xresult ];
(* If[ xresult === {} , True , False] ]; *)
NestWhile[ f , init, xtestF, All, maxNest ];
Length @ xresult
];

(* HHHH--------------------------------------------------- *)

xinput =
"O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....";

xinput =
"#...#...O....OO.#O.O........#.OO.#.O..O.O.#.#..O#..O...#.#......#..O.....O.###O..OO.#.....O.O.......
O.#..#..O.O...O..#OO#...#.#.OO....O.#.....O.#OOO.#O.#O#O.......O......O.OO.#.#.........O..#.....#...
....O..O..O#...#O#......O...##O#.O.....#O..##..O...#O..O.O..#.O..O..#.....OO....O.O.O...O......#.O.O
##O....O....#.OOO...O.#....O#.O#OO....O....O#...O..O#O.#..O.OO...O..O..#.#O..OO.O...O..#.#OO#.......
.O.O#OO..#...#..........O#.O..##.O..OO.O...#........O##.OOOO..#.#....O..O#O.#O.##..OO..O...#..O##...
OO...O##.....#...O.#O.....#.OOO.#.##...##...##.O.....##....O..O..#..#..OO...#..........OO..#.O#...O.
.OO#..#.O.O##...O....O...O....#.O.O..#.OO........O..O..O..###..O...O#..#..#......OO.O..#O....O##.#..
#O.O..O#...O..O.O.O...#.....O..O......O....OO.OO..O#.O#..#.O......#..O...#.O.##.#....O.OO.#...O...O#
.#.O.....O...O...O...O.#.........OO.....#................O....O..#..........##.O#.OO..O###..#.......
#O...#O..O#.......O...#..O...OO..#...O........#....O#..OO...O.O..#.OOO.....O..O.#...O.OO#.OO#.OO.O#.
......#.O...O...O.O...#...#O.O#....#.O..###..O....#.#.O.OO#....O#.....O...#.O......##......#O..#OO..
#OO.##...#..O....#...#...OO...........OO.O.OOOO...#...#O..#...#O#.O.O......O....O..#.O..O...#O#.O.O.
#...O.OO...#.#.OO...O#O....OO....#O....O.O#..#....O...##..O..O.#..#..#...........O...OO#.#..O.....O#
..#..O.O#.....O....O#..#........OO#.#...#O.O....O#....O#...O..#....OO#.O.#........#O....O.O...##O.#O
....#O.....O#...O.......O.......OO..#.....#...O##.O.......#O#....O...O..O.O.......#.....#..#.O.O.O..
.....O.....O.O.O#O.O##.....OOO#...#O.O#O.....#.O#..........O#O.....O.OOO..##.#O....O.O.....#.O.O#O.#
O#O....O.#.......O.O.OO.#..#...#O#..O...O.......O.#........#O#....O....O.#...#.O.#O...O.#.........O.
........O.O...O.#O....#..O....#O.....OO#..O.O..####..#...O..O...OOO.#OO..#....#...OO..O.....#O..O..#
O#...##...#..#O#..#O#..O#....OO..O#O#.....OOOOOO#.#.O.O..O.OO.O........O...#.#......OO#...#..#.#...#
..OO.O..OO.OO....#........#O.#...#O....#...O.OO...O#..O......O.###....#O......#.....####...#..#.#OO.
..O.O..O#....#.O.#.#.#.O#..O.......OO.........##.O.....#OOO..O#..#OO#.....O...OO.O.O...#...OO#.O.#..
O...#........###..##..O#.#O.O..O.#OO.OO...#....#O.O#O..OO...##....O......OO..#...#.......#...#......
..O..#.O#...OO#O.O#....#.....O#..O..O#..O.O..O.#O.O.#O.#OO..#........#.#O..#O....O..#...#OO#...#.O.O
..#O..O.....#....O.O...O.#O.#.O#.O......#........OO...O....#.O........O#.OO#..........O.O..OOOOO#.#.
O..##.##...........O##.#...#.O.#.OO..O.O...OO#.#..#...O..O....#..#..#...O###......O#.#O#..O.#....O.#
#.O.O.O.###.##......#.OO...OO.O..OOO.O.OOO.....##..O#...O......O.#O..#...#...OO..O#......O....##.O.#
#...#.O.O....O..#...#........##O#O#O..##O.#......O...OO#O...OOOO#O..OO##..#......O.#O.#.O#.OO...O..#
#..#........#O.#O.#...O...O....#OO...O....#...O..#......#..O..O...##........O..#.O..#.#OO..OO.O##.O.
..#...#...OO.#.O#O.O.##..#..##..O#...O#....#..O....OO.OOO..O#.#....O.......OO.#.O#.....O.#O.O.#.....
.......O...O..O...#.O..OO...O.....O.O#..#OO#.O...O..O#O..O..#.OO.......O..O....OOOO..O.#.O#O#..O.##.
.####...O.....#...#......#.O...........O......O.#O.....O.#......#.#...O...#......#..O#.....O.O..O..#
O....O...#OO##.O.O...O....O..O......O.O..O..O..O#O..O.O#O.#O.#..OO.....#.O.#O#..##.#.O.O...OO....#..
....#.O..O..#...#....O............O.O.#O.#.O...O....O.#.OO....O..O##...O##......O....O...OO........#
.#O...O..O.O.#O.......O###OO.O.O.O.....##O..OO...#.O..#OO..#...#...#.O.O###.....#O#..##.#O.....O....
..#.###.#..##......#..#.#OO..O......O..#OOO.#O...#....OO.##O...O..#.#O....#OO....O.#.......#....O...
#OO...#......#..#........#.OO.##....#...OOOO..O#O..O.#..#O........#O.OO#..........OO..OO....O..#O.#.
..##.##.O....#.##O..#...###..O##.#.#......O#O..###..##......O...#.....##.#...........O.O.O....O.#...
...O.#..#......#.OO..#..O##...O..O...OO##...OO.O#....O.O.#.O.....O..#..O..#...O..#O.....O.O..O.O#.##
O......###OOO#.#.....OO...O.....O.##.....OO..........OO#O#.O.#.#O....O..#O.#..........##O...#O....O.
..#...#...OO.OO#.....OO...O.O.O.##.##O##..O.#.O#..O.O.....OOOO....#....O.O.#..##OO.O#..#O.O.#...O...
.#.OO.##....O..O...O..#.##.O#OO..#.....OO.........O.OOO.#..O....O....OOO.#.OO..O..#...O#OO.OO##.#.O.
.#.OO.O#.O.O.....#O..O.O..O......O.#O...O..O...##.O#..#.O.....O...O....OO.OOO..OO.O...OO..#.#..OOO#.
.#..O.#.O..#.OOO....#O#O#............##.#.O...O....O.OO..#.O....O#O#.O.#...#....#..OO.O.O#.#.....O.O
O....O.O#....O..#.......O..#O.##.#...O..O.......O#.#.....#..#..O......O..O.....#............##OO....
O#.O...O.##O..OO..O.O.O.#O.O..##..O#.#..#O..O#O...#...OO..#.O.O....OO..O..#..O.......O.O#....O..#.O#
#.O..##......#..O#O..........##O#.#O..O#.#..#.O..##O.O.#.OO....O#..........O..#.##..#..O.#...#O.OO..
.O..#....OO...O.......#...#...O.##...O..O.O.........OO#O.OO.O..O...O.##.....##.....##O..#......O....
#..O.O..OO....O.O#.#O#........O..OO#.OO#O.O..O..#......O#...##.......#..##..O.#..#.O.O...#....#.O...
#..O.#...OO#.OO#.O.OO.O##.#....OO....#........#.O.O....O.#..O#..#....#.O#..O#..O.....OO..OOOO.....O.
.O..OO#.O#OO..#O..O.#......O..O..O.#O.#..#.#.O..O.O..O.....##.OO..#O.#............O#...#......O.OO.#
O......##OO....O...O......#...O..O.#...OO#O..O.OOO..O.....O...#.##..OOO.##...O.O....O#O....##...#...
..OO..#.O.O..#O.O...O...#...O.O#.##O....##...###O..O...O.O##..........###...O...O..#...#.#.....O....
#..OO....O..#O..OO...OO.............O.O..OOO.O.#.....O#O....#O.....#.O..O....O..O....O..O....O.#....
OO.O##..O...#O........#O...#OOOO.O..O....O...O..O..O#.O.O..##.##..O.#O...O#...#..O...O...OO.......O.
#..O#..O...O.#......#OO.OO.O.#...O...O#...#...O..##O#....#......#.....#..#O...#.O.O..............O#.
##..OO#..........#.O..OOOOO..#...#....#.#..O#O...O....#.O.#O#OO.#......#...O........O...O#....#....O
.....O...O#....O..O..OO.O..#...O.#..#..#...O#..#O....O.#.....#O....O...##....#..#......###.O.....O#.
#...O#..O..O#..OO....#.#...#O#..#.....#..#..................OO....O......OO.........O###O#....OO.O..
O#...O.O.O..##.....##....#....#......#...O.#...O..##...O..O...##..#....#..O..O#...##..O.O..OOO..#...
..#.......#.O..O..#O....#...#.....OOO#...O#...O#.#.#O.....O#O.#.O.#.O......O.#..O.O..O#......O.O..O#
...O.#.#..O.#..###..#...#.....O..O.....OO#..O..#.O..#....OOO...........#.......#..OO..OO#.#O....#O..
.O.O...#....#.#O..#..OO#..#....OO....#O..O#.#..#..O.#..O.#O#..OO........#O.#...OO....OO......#.#O...
OO.O.O#..#.#.#.O.OOO...#....O..O##...O.OO#.#.....O.....#.....O....#.........O...O..........OOO.O.OOO
......O...O...###....##.O.O..OOO..O.O......O.#.......#..O..........O#..#..#O.#.##.....###.#O#O#O..#.
O..#..#O.OO.......#.OO...#OO..OO.O#O.....#.#.O..OOO.OO.##O.O#...#.O......#..#O#O...O#..........O.O#.
OO#...O..#..O.#..O........O.....O.....O........O..#....###..O..O..#...O...#.#.##.......O..#.O#O#O...
.......O..O...O...O.OO#.O.#..OO............O.O.O.#..OO#....##O.....O#.....O##O.....O.#...###O.....#.
.....O....OO..O..#O.....O#..O..O.#.#O#.#O#....O.#O..O#.O#.OO......#.O#..O.O...O...#...#..O....#...#O
#...#....#..O..#.O..#.##O..#O..#..OOO.#..##.....OO.O.....OOO.#..O.#.##O#..O.#..#.#.#....#O#...##....
.OO.O..###....#O....O..#.O.#.......#....O###..O.#......O#....#........O...#O..#..#.........O......##
O#......O#.....#.O....#..#.O.#O.......OO#...#..#.#O.#.O.##......#.#.#..O#O.#...O......O..OOO..OO.###
#O.#.O...O.....O....#OO##...OO..#...OO.#O.OOO.O..#O....O............#....#....#...........O.OOO#.OO.
.O.O.#OO#O.O.OO#..O..#....O.#..O...O....O.#OO#O...##.......O...O.....#.O...#...O.##O...OOO.O........
.O#..O.......#..##..OO#.....O.#.OO#...#O.O..O......O..OO.#...#.#............O#O.OO.......O#........#
.OO#..O##...........O.OO.....#.##....O#.#.#O..O...O..#..#..O.......#......#.#...........###O##......
...#...#.....O........OO..#.#...O.#.....#.OO.....#.O.#OO......#OO..#.....#..O##..O..#...O.O.......O#
O...O...#O..#O#O.......#..#O....#OO....#.#O.....O....O##.#...O.......#.....#........#O.O...O...O....
..#.....OO.#.OO....O#O....O#O...O.O...#O.##....##O...#..##O#.OO#O..OOO.#.#......O.OO.O..O.O.OO.#O.#.
.......O.....##...O#.#O.#....O.....O........#...#.OO...#...OO........#OO#...#..OO..O...#....O#.#OO.O
..#..O.OO....O...#.......OO.O.##...#...O...#.O#.OO#....O...O..O###.O.###O..#....##.O.##....O..##...#
.......OOO.....OO..#..O..#O.OOO#O.....O.O#.....O....###..O#..OO..O....###O.OO...#..#.O....#.O.O..#OO
.#...#.........#.###..#...#.#...#O.#..O#O#OOOO#.#.O.....O.#....#..O......#OO....O..O.O.#.O......O..O
O.O....O....O..O......O...#.....O##....OOO.....#.OO.#..O....O..O.O#.O#.OO......#....#......OO......O
..#O.#O.....O...#O...##.O#..O...#..##.O.O.O....#.....#.O#O.....#............O....#.#...#....###...#.
.O..O...OO.....#...........##...O#.O##O........OO..O.###O.#..#..#.O..O.......O....#O.#.........#...#
..##.O....O...O.O.O#O...#O..#..#.#.O...#O.O.O.....#....#...........O...O....O....OO#O.#.O....#..O..O
.#O#....O.....O#O..O##O#..O..O.O.....O........#.#......O#..O..OO.OO#.....OO........O......O#...O.#..
....#.....O..#......O...##.O.O.#..#.....O.O..#.O#.#O...##....O.......#O..O.....#..#.....#.....#.....
.OO....OOO.OO....O...#.......O......#O.#O..O.O#O..............O.#......#.#.......#....#.O....#.#O.#.
OO...OO.#.O#OO#........##.O.....#..#O.#....O..O..O.O#..........O..O.O....#..O.......O....O....O.OO.O
O.#O.......O#.#...#........O...O.O....O#OO....O.O.O...#.#.O#...#O#O.....##..O#O...#O....O....O#OOO.#
.OO#..#..O..........##.O.#OO#..O.O.#...#....O..O#.O..#.#.....O.O..#..OO..##O#...O.O.O#........O.....
.O............#.O...#...#....###.O#.#.#....O.....OO...#O.#.O..O##...#O.#O..OO#..#.O#.#.....O#.......
#..O#..#.OOO#O...O.O..O..#OOO....#...........O##...OOO##O....O.O...O..O#O.........O.OO.....O....O...
.#....#OO..##O..#O##O.#O....#......O.OO..........##.OO#O...#.....O.O.....O#..OO.#........O..O.O..O..
....O.##...#.O.........O.OO....#....##O..#O.......#..O.##O#..#O..#.....O.O#O....#...O..O.OO.........
..###.O.....##.....OO.O..OO.O..#...O.....#....O.O...............O.##.#.O#O#.#...O..#.OOOOO....#.#.#.
O...O....O.#.#.O#.O#..#......O#.....OO.##....OO.....O.......O....O.O.....#...O..OO#..OO..O....#OOO.#
#.#.#.O..#.O...#....#..O....O......O..#..O.OO#O......O.......O.O.........O...O.......OO.##.......#.#
O#..........O...#O.###....#O..O.#......O....#.O.O...O...O.....O#..#.O#..O.#.O..OOO#.O...#..O.#O.....";

(* turn into matrix *)
xmatrix = Map[ Characters , StringSplit[ xinput ]];

xrowcount = Length[ xmatrix ];

moveNorth = Function[{xx},
Transpose @ ReplaceRepeated[ Transpose @ xx,
{head___,Pattern[dots, Longest[ ".".. ] ],Pattern[balls, Longest[ "O".. ] ],tail___} -> {head,balls, dots, tail}
] ];

moveWest =
Function[{xx},
ReplaceRepeated[ xx,
{head___,
Pattern[dots, Longest[ ".".. ] ],
Pattern[balls, Longest[ "O".. ] ],
tail___} ->
{head,balls, dots, tail}
] ];

moveSouth =
Function[{xx}, Transpose @ ReplaceRepeated[ Transpose @ xx,
{head___, Pattern[balls, Longest[ "O".. ] ], Pattern[dots, Longest[ ".".. ] ], tail___} -> {head,dots,balls,tail}
] ];

moveEast =
Function[{xx}, ReplaceRepeated[ xx,
{head___, Pattern[balls, Longest[ "O".. ] ], Pattern[dots, Longest[ ".".. ] ], tail___} -> {head,dots,balls,tail}
] ];

(* do one cycle of moving balls *)

f1cycle = Function[{yy}, yy // moveNorth // moveWest // moveSouth // moveEast];

(* xallmoved = Nest[ f1cycle, xmatrix,100 ] *)

xperiod = xGetNestPeriod[f1cycle, xmatrix, 10^4];

xallmoved = Nest[ f1cycle, xmatrix, Mod[ 10^9 , xperiod ] ];

Total @ MapIndexed[ Function[{xval, xindex},
 Count[ xval, "O" ] * (xrowcount - xindex[[1]] +1) ],
xallmoved ]

(* answer *)

Advent of Code 2023, Index

Xah Talk Show 2024-10-31 Ep595, Wolfram Language, Detect Nesting Function Periodicy, Advent of Code 2023, Day 14 Part 2, Take 4

Xah Talk Show, Advent of Code 2023, Day 14, Wolfram Language