add tag
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)
Top Answer
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}
```

![image.png](/image?hash=37b80dd64d9573cdce673296afc3a62d0fcbc67a22ad6f60caab73d873168a4d)

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