Since we rabbits were the real builders of the pyramids, we of course know the answer!
# Base Puzzle
The following solves the normal (not the bonus) puzzle. But see the next section [Bonus Puzzle] below. This simply builds a formatted list of stones which the current stone might depend on and then iterates through said list to look for a combination of which both stones appear in the list.
Since I was lazy I didn't implement the search whether a stone is in the list expandably, and hence this is not fully expandable (though it is for the most part, only the search function isn't -- and the assignment for the list, which I could drop if I implemented an expandable search function).
I hope the comments are enough to understand the code.
```
\documentclass{article}
\makeatletter
\def\cd@f@gobble@to@end#1\cd@q@end{}
\ExplSyntaxOn
% copy over the definition of `\prg_replicate:nn` but remove the leading
% `\exp:w` so that we can add it (`\romannumeral`) instead to get a single step
% of expansion.
\exp_args:NNno \exp_args:Nno \use:n { \cs_new:Npn \cd@f@replicate #1#2 }
{ \exp_after:wN \use_none:n \prg_replicate:nn {#1} {#2} }
\cs_new:Npn \solveAoC@pretty #1 { \clist_use:nnnn {#1} {~and~} {,~} {~and~} }
\ExplSyntaxOff
\def\cd@f@gobble@to@empty#1\@empty{}
\protected\def\cd@f@if@in#1#2%
{%
\begingroup\def\cd@f@if@in@aux##1,#1,##2\cd@f@if@in{\endgroup}%
\expandafter\cd@f@if@in@aux#2\cd@f@if@in\cd@f@if@in@aux
,#1,\cd@f@if@in\@secondoftwo
}
\def\cd@f@if@in@aux,#1,\cd@f@if@in\@secondoftwo#2#3{#2}
\def\cd@f@story@info#1;#2;%
{%
% input:
% #1: stone-number
% #2: number of stories
% returns (after \the):
% <story>;
% <first-block-of-story>;
% <last-block-of-story>;
\numexpr
\expanded{\unexpanded{%
\expandafter\cd@f@story@info@aux\the\numexpr#2+1\relax;(#2-1);1;#1;%
}\expandafter}\romannumeral
% -2 since we already have one iteration in front, and don't need one for
% the last story
\cd@f@replicate{#2-2}\cd@f@story@info@aux\cd@f@story@info@last
\cd@f@story@info@end
}
\def\cd@f@story@info@aux#1;#2;#3;#4;#5%
{%
\ifnum#4<#1 % we found the story
\expandafter\cd@f@story@info@found
\the\numexpr#1-1\expandafter;%
\the\numexpr#1-#2-1\relax;%
#3;%
\fi
\expandafter#5%
\the\numexpr#1+#2\expandafter;%
\the\numexpr#2-1\expandafter;%
\the\numexpr#3+1;%
#4;%
}
\def\cd@f@story@info@last#1;#2;#3;#4;\cd@f@story@info@end{#3\relax;#4;#4;}
\def\cd@f@story@info@found#1;#2;#3;\fi#4\cd@f@story@info@end{\fi#3\relax;#2;#1;}
\def\cd@f@neighbourpairs#1;#2;%
{%
% input:
% #1: stone-number
% #2: number of stories
% output after `\expanded`:
% list of neighbour pairs that would render this stone dependent in the
% following form: a1,b1;a2,b2;
\expandafter\cd@f@neighbourpairs@aux\the\cd@f@story@info#1;#2;#1;%
}
\def\cd@f@neighbourpairs@aux#1;#2;#3;#4;%
{%
% input:
% #1: story of new stone
% #2: left-most stone in that story
% #3: right-most stone in that story
% #4: stone-number
% output after `\expanded`:
% list of neighbour pairs that would render this stone dependent in the
% following form: a1,b1;a2,b2;
\ifnum#1>1 % not first story
% the two blocks below this block
\the\numexpr#4-#3+#2-2\relax,\the\numexpr#4-#3+#2-1;%
\fi
\ifnum#4>#2 % not left-most stone
% the block to the left, and left-above
\the\numexpr#4-1\relax,\the\numexpr#4+#3-#2\relax;%
\fi
\ifnum#4<#3 % not right-most stone
% the block to the right, and right-above
\the\numexpr#4+1\relax,\the\numexpr#4+#3-#2+1\relax;%
\fi
}
\protected\def\cd@f@neighbourcheck#1#2%
{%
% input:
% #1: stone-number
% #2: number of stories
\expandafter\cd@f@neighbourcheck@aux
\expanded{\cd@f@neighbourpairs#1;#2;}%
\cd@q@end,\cd@q@end;%
}
\protected\def\cd@f@neighbourcheck@aux#1,#2;%
{%
\cd@f@gobble@to@end#1\cd@f@neighbourcheck@done\cd@q@end
\cd@f@if@in{#1}\cd@v@stonelist
{\cd@f@if@in{#2}\cd@v@stonelist\cd@f@neighbourcheck@found{}}%
{}%
\cd@f@neighbourcheck@aux
}
\def\cd@f@neighbourcheck@done\cd@q@end#1\cd@f@neighbourcheck@aux#2#3{#3}
\def\cd@f@neighbourcheck@found#1\cd@q@end,\cd@q@end;#2#3{#2}
\let\cd@v@stonelist\@empty
\newcommand\checkdependent[1]
{%
% input:
% #1: list of stones
% #2: stone-number (curried)
% #3: number of stories (curried)
% output:
% first of two if dependent
% second of two if independent
% store input into variables
\def\cd@v@stonelist{#1}%
\cd@f@neighbourcheck
}
\newcommand\solveAoC[3]
{%
\noindent
For a #3-story pyramid, with the stones \solveAoC@pretty{#1} already
carved, the stone #2 has a\checkdependent{#1}{#2}{#3}{ }{n in}dependent
form!\par\bigskip
}
\makeatother
\begin{document}
\solveAoC{,1,2,}{4}{3}
\solveAoC{,4,5,}{6}{3}
\solveAoC{,1,5,9,}{6}{4}
\solveAoC{,1,5,8,}{6}{4}
\end{document}
```
This prints:
![soc15-pyramid_dependency-1.png](/image?hash=2fff21d6040e073b592bad12b9064155db77026b1f03f7e14051d387d6289c4f)
---------
# Bonus Puzzle
This solves the bonus puzzle. Our approach is a bit different than the one above. Instead of checking the possible neighbour pairs being in the list we first build a list of all dependent stones (which we append to our input list). For that we need to nest several loops, again I hope the comments are sufficient to understand the code :P
```
\documentclass{article}
\makeatletter
\def\cd@f@gobble@to@end#1\cd@q@end{}
\def\cd@f@gobble@to@eol#1\cd@q@eol{}
\ExplSyntaxOn
% copy over the definition of `\prg_replicate:nn` but remove the leading
% `\exp:w` so that we can add it (`\romannumeral`) instead to get a single step
% of expansion.
\exp_args:NNno \exp_args:Nno \use:n { \cs_new:Npn \cd@f@replicate #1#2 }
{ \exp_after:wN \use_none:n \prg_replicate:nn {#1} {#2} }
\cs_new:Npn \solveAoC@pretty #1 { \clist_use:nnnn {#1} {~and~} {,~} {~and~} }
\ExplSyntaxOff
\def\cd@f@gobble@to@empty#1\@empty{}
\protected\def\cd@f@if@in#1#2%
{%
\begingroup\def\cd@f@if@in@aux##1,#1,##2\cd@f@if@in{\endgroup}%
\expandafter\cd@f@if@in@aux#2\cd@f@if@in\cd@f@if@in@aux
,#1,\cd@f@if@in\@secondoftwo
}
\def\cd@f@if@in@aux,#1,\cd@f@if@in\@secondoftwo#2#3{#2}
\def\cd@f@story@info#1;#2;%
{%
% input:
% #1: stone-number
% #2: number of stories
% returns (after \the):
% <story>;
% <first-block-of-story>;
% <last-block-of-story>;
\numexpr
\expanded{\unexpanded{%
\expandafter\cd@f@story@info@aux\the\numexpr#2+1\relax;(#2-1);1;#1;%
}\expandafter}\romannumeral
% -2 since we already have one iteration in front, and don't need one for
% the last story
\cd@f@replicate{#2-2}\cd@f@story@info@aux\cd@f@story@info@last
\cd@f@story@info@end
}
\def\cd@f@story@info@aux#1;#2;#3;#4;#5%
{%
\ifnum#4<#1 % we found the story
\expandafter\cd@f@story@info@found
\the\numexpr#1-1\expandafter;%
\the\numexpr#1-#2-1\relax;%
#3;%
\fi
\expandafter#5%
\the\numexpr#1+#2\expandafter;%
\the\numexpr#2-1\expandafter;%
\the\numexpr#3+1;%
#4;%
}
\def\cd@f@story@info@last#1;#2;#3;#4;\cd@f@story@info@end{#3\relax;#4;#4;}
\def\cd@f@story@info@found#1;#2;#3;\fi#4\cd@f@story@info@end{\fi#3\relax;#2;#1;}
\def\cd@f@neighbourpairs#1;#2;%
{%
% input:
% #1: stone-number
% #2: number of stories
% output after `\expanded`:
% list of neighbour pairs that would render this stone dependent in the
% following form: a1,b1;a2,b2;
\expandafter\cd@f@neighbourpairs@aux\the\cd@f@story@info#1;#2;#1;%
}
\def\cd@f@neighbourpairs@aux#1;#2;#3;#4;%
{%
% input:
% #1: story of new stone
% #2: left-most stone in that story
% #3: right-most stone in that story
% #4: stone-number
% output after `\expanded`:
% list of neighbour pairs that would render this stone dependent in the
% following form: a1,b1;a2,b2;
\ifnum#1>1 % not first story
% the two blocks below this block
\the\numexpr#4-#3+#2-2\relax,\the\numexpr#4-#3+#2-1;%
\fi
\ifnum#4>#2 % not left-most stone
% the block to the left, and left-above
\the\numexpr#4-1\relax,\the\numexpr#4+#3-#2\relax;%
\fi
\ifnum#4<#3 % not right-most stone
% the block to the right, and right-above
\the\numexpr#4+1\relax,\the\numexpr#4+#3-#2+1\relax;%
\fi
}
% check if the stone is not already in the list, else add it to the list, and
% append it to the outer most loop of `\cd@f@complete@dependencies`.
\protected\def\cd@f@mayhaps@addto#1#2%
{\cd@f@if@in{#1}#2{}{\edef#2{#2#1,}\cd@f@mayhaps@addto@aux{#1}}}
\def\cd@f@mayhaps@addto@aux#1#2\cd@q@eol{#2#1,\cd@q@eol}
% input:
% #1: number of stories
% #2: one element of our stone-list
% output:
% Adds all dependent stones to the `\cd@v@dependentlist`.
\protected\def\cd@f@complete@dependencies#1,#2,%
{%
\cd@f@gobble@to@eol#2\cd@f@complete@dependencies@done\cd@q@eol
\expanded{\cd@f@complete@dependencies@aux\cd@f@neighbourpairs#2;#1;}%
\cd@q@end,\cd@q@end;%
\cd@f@complete@dependencies#1,%
}
% input:
% #1: neighbour-A of a neighbourpair
% #2: neighbour-B of a neighbourpair
% output:
% Mayhaps adds neighbour-A to the dependentlist if neighbour-B is already part
% of that list (in which case neighbour-A is dependent on neighbour-B and
% the current element of the stone-list), or vice versa.
\protected\def\cd@f@complete@dependencies@aux#1,#2;%
{%
\cd@f@gobble@to@end#2\cd@f@complete@dependencies@next\cd@q@end
\cd@f@if@in{#1}\cd@v@dependentlist
{\cd@f@mayhaps@addto{#2}\cd@v@dependentlist}
{%
\cd@f@if@in{#2}\cd@v@dependentlist
{\cd@f@mayhaps@addto{#1}\cd@v@dependentlist}{}%
}%
\cd@f@complete@dependencies@aux
}
% end the inner dependency-loop, next iteration of the outer loop
\def\cd@f@complete@dependencies@next#1\cd@f@complete@dependencies
{\cd@f@complete@dependencies}
% ends the outer dependency-loop
\def\cd@f@complete@dependencies@done#1\cd@f@complete@dependencies#2,{}
\let\cd@v@dependentlist\@empty
\newcommand\checkdependent[3]
{%
% input:
% #1: list of stones
% #2: stone-number
% #3: number of stories
% output:
% first of two if dependent
% second of two if independent
% store input into variables
\def\cd@v@dependentlist{#1}%
\cd@f@complete@dependencies#3#1\cd@q@eol,%
\cd@f@if@in{#2}\cd@v@dependentlist
}
\newcommand\solveAoC[3]
{%
\noindent
For a #3-story pyramid, with the stones \solveAoC@pretty{#1} already
carved, the stone #2 has a\checkdependent{#1}{#2}{#3}{ }{n in}dependent
form!\par\bigskip
}
\makeatother
\begin{document}
\solveAoC{,1,2,}{4}{3}
\solveAoC{,4,5,}{6}{3}
\solveAoC{,1,5,9,}{6}{4}
\solveAoC{,1,5,8,}{6}{4}
% new cases that would be independent with the base puzzle but become dependent
% with the bonus puzzle
\solveAoC{,1,5,3,}{8}{4}
\solveAoC{,1,2,3,}{8}{4}
\solveAoC{,1,4,6,}{3}{3}
\end{document}
```
Output:
![soc15-pyramid_dependency-1.png](/image?hash=f7b20012368d3ef34df284cabfafbd3440ffd9d7801e405be339ade82e25067a)