Xmas 2021 Puzzle(1)

[Mispeld]

Sweet.
You inspired me to get my three-addend solution for 85709 down to around 0.05-0.06s, and only 15 active lines.

Thanks. Regarding the reported times, these are some details affecting the benchmarks:

1. The palindromes were supplied to the algorithm in a sorted vector. The time to create and sort them is not included.
2. Valid solutions are stored in pre-allocated memory. The time to write or display the solutions is not included.
3. The benchmarks were run on a PC with a Core-i3 with base 3.6 GHz clock.
4. Execution was within an Excel process, which limited utilization to one core of the four cores.

Since the aspect of increasing the number of addends is an extension of the well-studied "subset sum" problem, O(b^n) time using O(1) memory is the best known efficiency. There are Dynamic Programming approaches with O time using O memory that answer the question "how many groups of n palindromes adding up to the target value"? I have not yet come across any that actually list the unique groups with that efficiency.

 

[drbitboy]

[Updates: fixed many typos]

My time is for everything: build palindromes; find triplets; write output. Building palindromes and writing output is very fast, so I expect finding the triplets dominates, but I would have to run some tests like @Mispeld did to confirm those assumptions. A brute force approach takes O(957^3) i.e. nearly a billion passes through the innermost loop.

Here is the Python logic for finding three addends:

### Find triplets of PDNs that add up to target sum
L = len(pdns)
for L0 in range(L):
  for L1 in range(L0,L):
    sm01 = pdns[:L0] + pdns[L1]
    rem = sm - sm01
    if rem < pdns[L1]: break
    if rem in pdnset: print('{0},{1},{2}'.format(pdns[L0],pdns[L1],rem))

• the Palindromic Decimal Numbers (PDNs), sorted in increasing order, are in Python list [pdns]
  • and also duplicated in Python set [pdnset].]
• The first (outer) loop selects one PDN, pdns[L0], at a time from the entire list, from 0 through less than or equal to the target sum
• The second (inner) loop selects a second PDN, pdns[L1], one at a time from pdns[L0] through the end of the list.
  • This ensures the triplet solutions found are sequences that do not decrease.
• The sum of pdns[L0] and pdns[L1] is sm01
• The difference from sm01 to sm (target sum) is rem(ainder)
• If rem is less than pdns[1], then we can break out of the second loop
  • Again, this ensures any triplet solution's sequence does not decrease
• If rem is in [pdnset], which can be determined very quickly via binary search (O(logN)) because [pdnset] is a set, not a list, then the third number is also a PDN. So the performance is O(N^(n-1) logN) i.e. O(N^2 logN) for three addends (n=3).

 

[Peter Nachtwey]

I am late to the game. I just got my python running again.


It seems to me there is a lot of combinations if the palindromes can be mixed and matched. For instance, all ones until the number is reached.
The the length of the palindromes must all be the same length then that greatly limits the combinations.



Did anybody try a recursive approach? It should be possible to mix and math different length palindromes. Using the sum of 1 digit palindromes The brute force method works there should be a more elegant way that doesn't needlessly try numbers that won't work. For instance, can one save time by making sure the tries start out at the first unspecified digit and work down instead of trying 0 to 9. Trying numbers from 0 to 9 works if the code does a break after the remainder is less than or equal to 0.

 

[Mispeld]

Did anybody try a recursive approach?

The Excel workbook referenced in post #8 uses a recursively called function named PalSum.

One problem with that workbook is that it writes solutions to a worksheet as it find them. This really slows it down when there are large numbers of valid solutions as addends are increased. The number of unique solutions increases similarly with processing time for the test cases referenced in post #13. From an efficiency standpoint, that leads me to believe the "list the valid solutions" is not the same as "count the valid solutions" for a specified target value and number of addends (i.e., listing is still O(b^n), where n = addends, regardless of memory use).

 

[Peter Nachtwey]

The Excel workbook referenced in post #8 uses a recursively called function named PalSum.

One problem with that workbook is that it writes solutions to a worksheet as it find them. This really slows it down when there are large numbers of valid solutions as addends are increased. The number of unique solutions increases similarly with processing time for the test cases referenced in post #13. From an efficiency standpoint, that leads me to believe the "list the valid solutions" is not the same as "count the valid solutions" for a specified target value and number of addends (i.e., listing is still O(b^n), where n = addends, regardless of memory use).

So right approach but wrong platform. Recursion is used in many optimizing techniques.



I this application one starts with a number and subtracts a plaindrome then pass the remainder back as a new number.
This method allows for easy optimization.