Skillmon
> This is (an unofficial) part of the Summer of Code 2022 series, see https://topanswers.xyz/tex?q=2059 for more information

We want to build a small 2D pyramid. A pyramid has *n* stories with the first story having *n* stones, the second having *n*-1 stones, and so forth until the *n*th story, having 1 stone. The stones are numbered, starting from the bottom left like in the following 3-story pyramid (beware the glorious ASCII-art):


_______
|       |
|   6   |
___|_______|___
|       |       |
|   4   |   5   |
___|_______|_______|___
|       |       |       |
|   1   |   2   |   3   |
|_______|_______|_______|


Your task: Given a sequence of already placed stones in the form ,x,y,z, (so a comma separated list with a leading comma, might have more or less than 3 indices) with x, y, and z being different stone-numbers, and another stone-number (which is *not* in the sequence), decide if the stone has a dependent form.

A stone shall have a dependent form if either the two stones below it are already in the sequence (so for instance 4 is dependent if 1 and 2 are part of the sequence in our 3-story pyramid), or the stone above it and the other stone below the above stone are already part of the sequence (so for instance 3 is dependent if 5 and 2 are part of the sequence in our 3-story pyramid).

Your code should work for arbitrary pyramid heights (within TeX-limitations).

Bonus question: A stone shall also be considered dependent if the two stones below it are already dependent, or the stone above it and the other stone below the above stone are already dependent. For the bonus question you might also assume that the input sequence does not contain redundant information, so no later element of the sequence is dependent on earlier sequence items.

**EDIT:** Of course you also know the pyramid height if you need to as an argument (or inside a macro or however you want to get that information).

**EDIT 2:** There is a prize! The one with the most starred answer by Friday, 2022-10-07 00:00 UTC, can make a wish for a new animal to be added to ducksay. If two answers are tight for the most stars the early bird catches the worm.

![autumn_of_code-1.png](/image?hash=0dc0360180d438de3dbc49eff7b114d9da78787191beec02c75728a1f5e8309c)
Skillmon
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:

---------

# 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.

% 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@if@in{#2}\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)

Enter question or answer id or url (and optionally further answer ids/urls from the same question) from

Separate each id/url with a space. No need to list your own answers; they will be imported automatically.