Palindromic gapful numbers: Difference between revisions

See [https://www.rosettacode.org/wiki/Palindromic_gapful_numbers#Ludicrously_fast_to_10.2C000.2C000.2C000.2C000.2C000.2C000th the original's] comments for an explanation of the logic. While this AppleScript version is developed directly from the original, comparing the two may be difficult as I've pulled things around a bit for AppleScript efficiency and have relabelled some of the variables for consistency and to try to understand the workings myself! For the set task, it's not actually as fast as the script above, which doesn't have the overhead of being able to handle ridiculously large numbers and which gets the three sets of results for each digit in a single sweep rather than starting at the beginning for each set. It's also not nearly as fast as the Phix original apparently is, taking about twelve seconds to complete the same tests. But that's still not bad. Like the original, it's constrained not by the resolution of the results it can return, but by how many of them it can count using native number classes.

<lang applescript>use AppleScript version "2.4" -- Mac OS 10.10 (Yosemite) or later.

-- Return a script object containing the main handlers.

use framework "Foundation" -- For its NSMutableDictionary class and methods.

property outerDigit : missing value

property outerDigit_x11 : missing value

property searchLimit : missing value

property skipdSub : missing value

property output : missing value

-- Work out what the remainder would be if the decimal number described as one or two

-- instances of the digit 'd' with 'gap' zeros between them and 'shift' zeros following,

-- and which may be too large for AppleScript, were divided by the value 'outerDigit_x11'.

on rmdr(d, gap, shift)

-- Unlike the original Phix, this handler doesn't maintain a large cache, but computes its

-- usable low dividend on the fly by reducing shifts > 9 to equivalents between 4 and 9.

set multiplier to 10 ^ ((shift - 4) mod 6 + 4)

if (gap > -1) then set multiplier to multiplier + 10 ^ ((gap + shift - 3) mod 6 + 4)

return (d * multiplier mod outerDigit_x11) as integer

-- Recursively find successive palindromic gapful numbers beginning and ending with

-- 'outerDigit' and keep text versions of those in the required count range.

-- lhs: eg {9, 4, 5} of a potential 9459549 result. (Text eg. "945" in the original.)

-- remainder: remainder previously derived from rmdr() results.

set shift to (count lhs) -- left shift (should always equal length(lhs), I think)

-- Here, 'skipd' isn't a monolithic dictionary with four-element keys, but a list with 9 sublists,

-- each containing 99 smaller dictionaries with two-element keys. The values of the original

-- 'outerDigit' and 'remainder' key elements are used to index this structure. Since 'outerDigit'

-- has but one value per outer digit, the 'outerDigit'th sublist is prefetched and assigned

-- to the property 'skipdSub' in the set-up for each sweep.

set |key| to {gap, shift}

set skip to (item (remainder + 1) of my skipdSub)'s objectForKey:(|key|)

if (skip is missing value) then -- Key not in dictionary. Set 'skip' high for the 'if' test below.

set skip to searchLimit

else

set skip to (skip as real) div 1

end if

if (palcount + skip > to_skip) then -- (Also if they're equal, originally.)

set template to lhs & missing value & reverse of lhs -- Palindrome template list.

set mid to shift + 1 -- Index of its middle position.

set nextRem to (remainder + rmdr(d, nextGap, shift)) mod outerDigit_x11

if (gap is 2) then

set item mid of template to {d, d} -- Not d*11 in case d is 0.

else -- if (gap is 1) then

set item mid of template to d

-- else if (gap is 0) then

-- set item mid of template to ""

-- else

-- set template to d

end if

set end of my output to template as text

if (palcount = searchLimit) then exit repeat

if (palcount < to_skip) then (item (remainder + 1) of my skipdSub)'s setObject:(skip) forKey:(|key|)

-- Return a list of numeric texts representing the last 'keep' of the first 'searchLimit'

-- palindromic gapful numbers > 100 which begin and end with 'digit'.

on collect(digit, searchLimit, keep)

-- Initialise these script object properties for the current search.

set outerDigit to digit

set outerDigit_x11 to outerDigit * 11

set my searchLimit to searchLimit

set to_skip to searchLimit - keep

set skipdSub to item outerDigit of my skipd

set output to {}

-- Locals.

set gap to 1 -- Initially 1 digit between the outer pair.

set lhs to {outerDigit} -- Initial left end of palindomes.

set AppleScript's text item delimiters to ""

repeat until (palcount = searchLimit)

set remainder to rmdr(outerDigit, gap, 0)

return output

on initialiseSkipd()

repeat with thisList in my skipd

repeat 99 times

set end of thisList to current application's class "NSMutableDictionary"'s new()

end repeat

end repeat

end initialiseSkipd

tell theWorks to initialiseSkipd()

-- set tests to {{20, 20, 1, 9}, {100, 15, 1, 9}, {1000, 10, 1, 9}} -- The set task.

set {searchLimit, keep, firstEndDigit, lastEndDigit} to item i of tests

set |from| to searchLimit - keep + 1

if (searchLimit = keep) then

set r to "First " & searchLimit

set r to "Last " & keep & " of first " & searchLimit

set r to (searchLimit as text) & "th"

set s to " > 100 ending with "

if (keep > 1) then set s to "s" & s

set t to (lastEndDigit as text) & ":"

if (firstEndDigit is not lastEndDigit) then set t to "digits " & firstEndDigit & " to " & t

set end of output to ""

set end of output to r & " palindromic gapful number" & s & t

repeat with digit from firstEndDigit to lastEndDigit

set end of output to theWorks's (collect(digit, searchLimit, keep)) as text

set output to (rest of output) as text

<pre style="font-size:80%">First 20 palindromic gapful numbers > 100 ending with digits 1 to 9:

Last 15 of first 100 palindromic gapful numbers > 100 ending with digits 1 to 9:

Last 10 of first 1000 palindromic gapful numbers > 100 ending with digits 1 to 9:

Last 5 of first 10000 palindromic gapful numbers > 100 ending with digits 1 to 9:

100000th palindromic gapful number > 100 ending with digits 1 to 9:

1000000th palindromic gapful number > 100 ending with digits 1 to 9:

10000000th palindromic gapful number > 100 ending with digits 1 to 9:

1.0E+15th palindromic gapful number > 100 ending with digits 2 to 4: