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

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

(this programming puzzle is taken from https://projecteuler.net/problem=4, licensed under CC BY-NC-SA 4.0)

![SoC.png](/image?hash=f0ccd4b6a87af5e26bbe3981cb622c0237f7f02b8124f6c8a748c6177dee4a5f)
frougon
\* This line is not a spoiler. \*

The following code does the job with two little optimizations:

- the \sociv_is_palindrome:nTF conditional stops as soon as two different digits have been found in “complementary positions” (like first and last, second and penultimate, etc.);

- we skip all cases where one of the factors is a multiple of ten (by hypothesis, all numbers considered in the exercise are written without any leading zero, therefore no number greater than zero can be a palindrome and a multiple of ten).


\documentclass{article}
\ExplSyntaxOn

\int_new:N \l__sociv_ispal_current_index_int
\int_new:N \l__sociv_ispal_last_index_int
\bool_new:N \l__sociv_ispal_game_over_bool

\prg_generate_conditional_variant:Nnn \tl_if_eq:nn { xx } { F }

% #1: integer denotation for the number to test
\prg_new_protected_conditional:Npnn \sociv_is_palindrome:n #1 { T, F, TF }
{
\int_set:Nn \l__sociv_ispal_current_index_int { 1 }
\int_set:Nn \l__sociv_ispal_last_index_int
{ \int_div_truncate:nn { \tl_count:n {#1} } { 2 } }
\bool_set_false:N \l__sociv_ispal_game_over_bool

\bool_until_do:nn
{
\bool_lazy_or_p:nn
{
\int_compare_p:nNn { \l__sociv_ispal_current_index_int } >
{ \l__sociv_ispal_last_index_int }
}
{ \l__sociv_ispal_game_over_bool }
}
{
\tl_if_eq:xxF
{ \tl_item:nn {#1} { \l__sociv_ispal_current_index_int } }
{ \tl_item:nn {#1} { -\l__sociv_ispal_current_index_int } }
{ \bool_set_true:N \l__sociv_ispal_game_over_bool }

\int_incr:N \l__sociv_ispal_current_index_int
}

\bool_if:NTF \l__sociv_ispal_game_over_bool
{ \prg_return_false: }
{ \prg_return_true: }
}

\prg_generate_conditional_variant:Nnn \sociv_is_palindrome:n { V } { T, F, TF }

\int_new:N \l__sociv_flpp_start_of_range_int
\int_new:N \l__sociv_flpp_end_of_range_int
\int_new:N \l__sociv_flpp_product_int % tested product in the inner loop
% These vars will hold data corresponding to the greatest product found so far
\tl_new:N \l__sociv_flpp_greatest_product_so_far_tl
\tl_new:N \l__sociv_flpp_first_factor_tl
\tl_new:N \l__sociv_flpp_second_factor_tl

% #1: tl var where the first factor will be stored
% #2: tl var where the second factor will be stored
% #3: tl var where the greatest product will be stored
% #4: number of digits in each factor to test (leading zeros excluded)
\cs_new_protected:Npn \sociv_find_largest_palindrome_product:NNNn #1#2#3#4
{
\tl_set:Nn \l__sociv_flpp_greatest_product_so_far_tl { 0 }
\tl_set:Nn \l__sociv_flpp_first_factor_tl { 0 }
\tl_set:Nn \l__sociv_flpp_second_factor_tl { 0 }

\int_set:Nn \l_tmpa_int {#4} % evaluate this ⟨integer expression⟩ once
% \prg_replicate:nn is used to efficiently compute powers of ten
\int_set:Nn \l__sociv_flpp_start_of_range_int
{ 1 \prg_replicate:nn { \l_tmpa_int - 1 } { 0 } }
\int_set:Nn \l__sociv_flpp_end_of_range_int
{ 1 \prg_replicate:nn { \l_tmpa_int } { 0 } - 1 }

\int_step_inline:nnn { \l__sociv_flpp_start_of_range_int }
{ \l__sociv_flpp_end_of_range_int }
{
\int_compare:nNnF { \int_mod:nn {##1} { 10 } } = { 0 }
{
\int_step_inline:nnn { \l__sociv_flpp_start_of_range_int } {##1}
{
\int_compare:nNnF { \int_mod:nn {####1} { 10 } } = { 0 }
{
\int_set:Nn \l__sociv_flpp_product_int { ##1 * ####1 }

\sociv_is_palindrome:VT \l__sociv_flpp_product_int
{
\int_compare:nNnT
{ \l__sociv_flpp_product_int } >
{ \l__sociv_flpp_greatest_product_so_far_tl }
{
\tl_set:Nn \l__sociv_flpp_first_factor_tl {##1}
\tl_set:Nn \l__sociv_flpp_second_factor_tl {####1}
\tl_set:NV \l__sociv_flpp_greatest_product_so_far_tl
\l__sociv_flpp_product_int
}
}
}
}
}
}

\tl_set_eq:NN #1 \l__sociv_flpp_second_factor_tl
\tl_set_eq:NN #2 \l__sociv_flpp_first_factor_tl
\tl_set_eq:NN #3 \l__sociv_flpp_greatest_product_so_far_tl
}

\cs_new_eq:NN \findLargestPalindromeProduct
\sociv_find_largest_palindrome_product:NNNn
\cs_new_eq:NN \clistMapInline \clist_map_inline:nn
\ExplSyntaxOff

\begin{document}

\clistMapInline{1, 2, 3}{%
\findLargestPalindromeProduct{\firstFactor}{\secondFactor}{\maxProduct}{#1}%
$\firstFactor \times \secondFactor = \maxProduct$\par
}

\end{document}


# A better optimization (samcarter's idea)

In this section, I steal samcarter's excellent [idea](https://topanswers.xyz/tex?q=2082#a2321) of comparing a tl var to its reverse in order to test whether it is a palindrome. This makes the \sociv_is_palindrome:nTF conditional *much* easier to write and significantly faster. I've tested two implementations; the second one is slightly faster (\tl_reverse_items:n appears to be optimized for speed).

## First implementation

The conditional is not expandable because \tl_if_eq:nnTF isn't itself expandable (contrary to \tl_if_eq:NNTF); hence the protected.


\prg_generate_conditional_variant:Nnn \tl_if_eq:nn { e } { TF }

\prg_new_protected_conditional:Npnn \sociv_is_palindrome:n #1 { T, F, TF }
{
\tl_if_eq:enTF { \tl_reverse:n {#1} } {#1}
{ \prg_return_true: }
{ \prg_return_false: }
}


## Second implementation

This one isn't expandable either. First because \tl_if_eq:NnTF isn't expandable, and second because I use non-expandable operations in order to prepare \l__sociv_is_palindrome_tmp_tl as a copy of the first argument with each item wrapped inside braces (I do this because \tl_reverse_items:n wraps items of its result within braces if they weren't already braced).


\tl_new:N \l__sociv_is_palindrome_tmp_tl
\prg_generate_conditional_variant:Nnn \tl_if_eq:Nn { Nx } { TF }

\prg_new_protected_conditional:Npnn \sociv_is_palindrome:n #1 { T, F, TF }
{
\tl_clear:N \l__sociv_is_palindrome_tmp_tl
\tl_map_inline:nn {#1}
{ \tl_put_right:Nn \l__sociv_is_palindrome_tmp_tl { {##1} } }

\tl_if_eq:NxTF \l__sociv_is_palindrome_tmp_tl { \tl_reverse_items:n {#1} }
{ \prg_return_true: }
{ \prg_return_false: }
}


## Full code with the second implementation


\documentclass{article}
\ExplSyntaxOn

\int_new:N \l__sociv_ispal_current_index_int
\int_new:N \l__sociv_ispal_last_index_int
\bool_new:N \l__sociv_ispal_game_over_bool

\tl_new:N \l__sociv_is_palindrome_tmp_tl
\prg_generate_conditional_variant:Nnn \tl_if_eq:Nn { Nx } { TF }

% #1: integer denotation for the number to test
\prg_new_protected_conditional:Npnn \sociv_is_palindrome:n #1 { T, F, TF }
{
\tl_clear:N \l__sociv_is_palindrome_tmp_tl
\tl_map_inline:nn {#1}
{ \tl_put_right:Nn \l__sociv_is_palindrome_tmp_tl { {##1} } }

\tl_if_eq:NxTF \l__sociv_is_palindrome_tmp_tl { \tl_reverse_items:n {#1} }
{ \prg_return_true: }
{ \prg_return_false: }
}

\prg_generate_conditional_variant:Nnn \sociv_is_palindrome:n { V } { T, F, TF }

\int_new:N \l__sociv_flpp_start_of_range_int
\int_new:N \l__sociv_flpp_end_of_range_int
\int_new:N \l__sociv_flpp_product_int % tested product in the inner loop
% These vars will hold data corresponding to the greatest product found so far
\tl_new:N \l__sociv_flpp_greatest_product_so_far_tl
\tl_new:N \l__sociv_flpp_first_factor_tl
\tl_new:N \l__sociv_flpp_second_factor_tl

% #1: tl var where the first factor will be stored
% #2: tl var where the second factor will be stored
% #3: tl var where the greatest product will be stored
% #4: number of digits in each factor to test (leading zeros excluded)
\cs_new_protected:Npn \sociv_find_largest_palindrome_product:NNNn #1#2#3#4
{
\tl_set:Nn \l__sociv_flpp_greatest_product_so_far_tl { 0 }
\tl_set:Nn \l__sociv_flpp_first_factor_tl { 0 }
\tl_set:Nn \l__sociv_flpp_second_factor_tl { 0 }

\int_set:Nn \l_tmpa_int {#4} % evaluate this ⟨integer expression⟩ once
% \prg_replicate:nn is used to efficiently compute powers of ten
\int_set:Nn \l__sociv_flpp_start_of_range_int
{ 1 \prg_replicate:nn { \l_tmpa_int - 1 } { 0 } }
\int_set:Nn \l__sociv_flpp_end_of_range_int
{ 1 \prg_replicate:nn { \l_tmpa_int } { 0 } - 1 }

\int_step_inline:nnn { \l__sociv_flpp_start_of_range_int }
{ \l__sociv_flpp_end_of_range_int }
{
\int_compare:nNnF { \int_mod:nn {##1} { 10 } } = { 0 }
{
\int_step_inline:nnn { \l__sociv_flpp_start_of_range_int } {##1}
{
\int_compare:nNnF { \int_mod:nn {####1} { 10 } } = { 0 }
{
\int_set:Nn \l__sociv_flpp_product_int { ##1 * ####1 }

\sociv_is_palindrome:VT \l__sociv_flpp_product_int
{
\int_compare:nNnT
{ \l__sociv_flpp_product_int } >
{ \l__sociv_flpp_greatest_product_so_far_tl }
{
\tl_set:Nn \l__sociv_flpp_first_factor_tl {##1}
\tl_set:Nn \l__sociv_flpp_second_factor_tl {####1}
\tl_set:NV \l__sociv_flpp_greatest_product_so_far_tl
\l__sociv_flpp_product_int
}
}
}
}
}
}

\tl_set_eq:NN #1 \l__sociv_flpp_second_factor_tl
\tl_set_eq:NN #2 \l__sociv_flpp_first_factor_tl
\tl_set_eq:NN #3 \l__sociv_flpp_greatest_product_so_far_tl
}

\cs_new_eq:NN \findLargestPalindromeProduct
\sociv_find_largest_palindrome_product:NNNn
\cs_new_eq:NN \clistMapInline \clist_map_inline:nn
\ExplSyntaxOff

\begin{document}

\clistMapInline{1, 2, 3}{%
\findLargestPalindromeProduct{\firstFactor}{\secondFactor}{\maxProduct}{#1}%
$\firstFactor \times \secondFactor = \maxProduct$\par
}

\end{document}


Same output as above.
samcarter
*no spoiler here*

Not very efficient, but I learnt about \tl_reverse:V:


\documentclass{article}

\begin{document}

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is $9009 = 91 \times 99$.

Find the largest palindrome made from the product of two 3-digit numbers.
\ExplSyntaxOn

\int_new:N \l_sam_a_int
\int_new:N \l_sam_b_int
\int_new:N \l_sam_prod_int
\int_new:N \l_sam_pali_int
\tl_new:N \l_sam_prod_tl
\tl_new:N \l_sam_rev_tl

% loop over a
\int_step_inline:nnn {100} {999}
{

\int_set:Nn \l_sam_a_int { #1 }

% loop over b
\int_step_inline:nnn {100} {\l_sam_a_int}
{

\int_set:Nn \l_sam_b_int { ##1 }

% calculating product
\int_set:Nn \l_sam_prod_int { \l_sam_a_int * \l_sam_b_int }

% make a token list from the product
\tl_set:NV \l_sam_prod_tl \l_sam_prod_int

% reverse the token list
\tl_set:Nx \l_sam_rev_tl { \tl_reverse:V \l_sam_prod_tl }

% compare origional and reverse token list
\tl_if_eq:NNT \l_sam_prod_tl \l_sam_rev_tl
{
% check if palindrom is the largest
\int_compare:nNnT { \l_sam_pali_int } < { \l_sam_prod_int }
{
\int_set_eq:NN \l_sam_pali_int \l_sam_prod_int
}
}
}
}

\par
\int_use:N \l_sam_pali_int

\ExplSyntaxOff

\end{document}


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.