Rosetta Code

Palindromic gapful numbers: Difference between revisions

Page Discussion

Palindromic gapful numbers (view source)

Revision as of 13:14, 19 April 2021

398 bytes added ,  3 years ago
Undo revision 330973 by Nig (talk)
(→‎{{header|AppleScript}}: →‎Translation of Phix "Ludicrously fast …": 6.5-fold speed increase through dumping NSMutableArray altogether. Several minor tweaks and comment changes.)
(Undo revision 330973 by Nig (talk))
Line 178:
 
===Translation of Phix "Ludicrously fast …"===
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 translationAppleScript wasversion is developed directly from the Phixoriginal, 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 helptry meto understand the processworkings myself.! OnFor mythe set machinetask, thisit's versionnot takesactually 0.12as secondsfast as the script above, which doesn't have the overhead of being able to carryhandle outridiculously large numbers and which gets the setthree taskssets —of onlyresults for each digit in a tadsingle slowersweep rather than starting at the hard-wiredbeginning scriptfor aboveeach set. TheIt's batchalso ofnot extremenearly testsas infast as the Phix demooriginal takesapparently aroundis, 1.6taking 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 ReturnAppleScript aversion "2.4" -- scriptMac objectOS containing10.10 the(Yosemite) mainor handlerslater.
 
-- Return a script object containing the main handlers.
-- It could be loaded as a library instead if there were any point in having such a library.
on getWorks()
script theWorks
use framework "Foundation" -- For its NSMutableDictionary class and methods.
property outerX11 : missing value▼
else▼
property countLimit : missing value▼
▲ property outerX11outerDigit : missing value
property outerDigit_x11 : missing value
▲ property countLimitsearchLimit : missing value
property to_skip : missing value
property palcount : missing value
property skipd : {{}, {}, {}, {}, {}, {}, {}, {}, {}}
property skipdOuterskipdSub : missing value
property palsoutput : missing value
-- Work out what the remainder fromwould thebe division ofif the positive decimal integernumber described as valueone whichor istwo
-- one or two instances of the digit 'digitd' separated bywith 'gap' zeros andbetween followedthem byand 'shift' zeros following,
-- (and which may not be realisabletoo aslarge anfor AppleScript, number)were divided by the value 'outerX11outerDigit_x11', a multiple of 11.
on rmdr(digitd, gap, shift)
-- Remainders fromUnlike the divisionoriginal Phix, this ofhandler left-shifteddoesn't decimalsmaintain bya multipleslarge ofcache, 11but reliablycomputes repeatits
-- everyusable sixlow placesdividend shiftedon >the 2,fly soby usereducing ashifts dividend> with9 theto equivalentequivalents digitbetween shifts4 <and 9.
set coefficientmultiplier to 10 ^ ((shift - 34) mod 6 + 34)
if (gap > -1) then set coefficientmultiplier to coefficientmultiplier + 10 ^ ((gap + shift - 23) mod 6 + 34)
return (digitd * coefficientmultiplier mod outerX11outerDigit_x11) as integer
end rmdr
-- Recursively inferfind from remainder arithmetic anysuccessive palindromic gapful numbers beginning and ending with
-- ((count'outerDigit' lhs)and *keep 2text +versions gap)of digitsthose whose outer digit isin the firstrequired value incount lhsrange.
-- Append text versions of any falling in the current keep range to the 'pals' list.
on palindromicGapfuls(lhs, gap, remainder)
-- lhs: eg {9, 4, 5} of a potential 945…5499459549 result. (Text eg. "945" in the original.)
-- gap: length of inner to be filled in
-- remainder: remainder of outer, eg 9400049 mod 11, butpreviously derived from rmdr() results.
set shift to (count lhs) -- left shift of(should inneralways equal length(samelhs), I think) as its right shift).
-- This translation'sHere, 'skipd' isisn't a monolithic dictionary with four-deepelement AppleScriptkeys, listbut structurea indexedlist with the9 elementssublists,
-- each containing 99 smaller dictionaries with two-element keys. The values of the original
-- of the original dictionary's keys: (skipd) -> outermost digit -> shift -> gap -> remainder (+ 1).
-- 'outerDigit' and 'remainder' key elements are used to index this structure. Since 'outerDigit'
-- The outermost digit element doesn't change during a search based on it, so the script property
-- 'skipdOuter' has beenbut presetone tovalue skipd'sper outer-th sublist indigit, the set-up for the current search. 'outerDigit'th sublist is prefetched and assigned
-- Populate it just enough here to ensure that the slotproperty about'skipdSub' toin bethe checkedset-up for a 'skip' valueeach existssweep.
repeatset (shift|key| -to (count{gap, my skipdOuter)) timesshift}
set skip to (item set(remainder end+ 1) of my skipdOuter toskipdSub)'s {}objectForKey:(|key|)
if (skip is missing value) then -- Key not in dictionary. Set 'skip' high for the 'if' test below.
end repeat▼
repeat (gap - (count itemset shiftskip ofto my skipdOuter)) timessearchLimit
else
set end of item shift of my skipdOuter to {}▼
end repeat set skip to (skip as real) div 1
end if▼
repeat (remainder + 1 - (count item gap of item shift of my skipdOuter)) times
if (palcount + skip set> endto_skip) ofthen item-- gap(Also ofif itemthey're shiftequal, of my skipdOuter to missing valueoriginally.)
end repeat▼
set skip to item (remainder + 1) of item gap of item shift of my skipdOuter
if ((skip is missing value) or (palcount + skip > to_skip)) then
set skip to 0
set template to lhs & missing value & reverse of lhs -- Palindrome template list.
set mid to shift + 1 -- Index of its middle position.
set nextGap to gap - 2
repeat with d from 0 to 9
set nextRem to (remainder + rmdr(d, nextGap, shift)) mod outerX11outerDigit_x11
if (gap > 2) then
set skip to skip + palindromicGapfuls(lhs & d, nextGap, nextRem)
else if (nextRem is 0) then
-- A palindrome of lhs's contents around gap ds would be … gapful.
set palcount to palcount + 1
if (palcount > to_skip) then
--if This(gap oneis would2) be in the current keep range, so realise it as text and store it.then
if (gap is 2) then set ditem mid of template to {d, d} -- Not d * 11 asin case d could beis 0.
setelse end-- of my pals toif (lhsgap &is d & reverse of lhs1) as textthen
▲ set end of set item shiftmid of my skipdOutertemplate 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
else
set skip to skip + 1
end if
end if
if (palcount = countLimitsearchLimit) then exit repeat
end repeat
if (palcount < to_skip) then set (item (remainder + 1) of item gap of item shift of my skipdOuterskipdSub)'s tosetObject:(skip) skipforKey:(|key|)
else
set palcount to palcount + skip
Line 255 ⟶ 264:
end palindromicGapfuls
-- Set upReturn a searchlist forof numeric texts representing the last 'keep' of the first 'countLimit' PGNs > 100 whose outer digit is 'outersearchLimit',
set h to h & "-- palindromic gapful numbers > 100 endingwhich withbegin "and &end firstOuter &with ":"'digit'.▼
-- call the recursive process for each palindrome width, and eventually return the stored numeric texts.
on collect(outerdigit, countLimitsearchLimit, keep)
-- Initialise these script object properties for the current search.
set outerX11outerDigit to outer * 11digit
set my countLimitouterDigit_x11 to countLimitouterDigit * 11
set to_skipmy searchLimit to countLimit - keepsearchLimit
set hto_skip to "FirstsearchLimit "- & countLimitkeep▼
set palcount to 0
set skipdOuterskipdSub to item outerouterDigit of my skipd
set palsoutput to {}
-- Also locals and TIDsLocals.
set lhsgap to {1 -- Initially 1 digit between the outer} pair.
set gaplhs to 1{outerDigit} -- NumberInitial ofleft digitsend between outerof pairpalindomes.
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to "" -- For list-to-text coercions.
repeat until (palcount = countLimitsearchLimit)
set remainder to rmdr(outerouterDigit, gap, 0)
palindromicGapfuls(lhs, gap, remainder)
set gap to gap + 1
Line 277 ⟶ 287:
set AppleScript's text item delimiters to astid
return palsoutput
end collect
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
end script
tell theWorks to initialiseSkipd()
return theWorks
end getWorks
 
(* Test code *)
 
-- Return an integer as text with the appropriate English ordinal suffix
on ordinalise(n)
-- Adapted from Victor Yee (adapted from NG (adapted from Jason Bourque) & Paul Skinner)
set units to n mod 10
if ((units > 3) or ((n - units) mod 100 is 10) or (units < 1) or (units mod 1 > 0)) then return (n as text) & "th"
return (n as text) & item units of {"st", "nd", "rd"}
end ordinalise
 
on doTask()
Line 301 ⟶ 310:
{1.0E+13, 1, 9, 9}, {1.0E+14, 1, 9, 9}, ¬
{1.0E+15, 1, 2, 4}}
-- set tests to {{20, 20, 1, 9}, {100, 15, 1, 9}, {1000, 10, 1, 9}} -- The RCset task.
set output to {}
Line 308 ⟶ 317:
set AppleScript's text item delimiters to " "
repeat with i from 1 to (count tests)
set {countLimitsearchLimit, keep, firstOuterfirstEndDigit, lastOuterlastEndDigit} to item i of tests
ifset (countLimit|from| =to searchLimit - keep) then+ 1
else if (firstOutersearchLimit = lastOuterkeep) then▼
▲ set h to "First " & countLimit
set hr to ordinalise(countLimit)"First " & searchLimit▼
else if (keep > 1) then
set hr to "Last " & keep & (" of first " & countLimit)searchLimit
▲ else
▲ set h to ordinalise(countLimit)
▲ end if
if ((keep = 1) and (firstOuter = lastOuter)) then
set h to h & " palindromic gapful number > 100 ending with " & firstOuter & ":"▼
▲ else if (firstOuter = lastOuter) then
▲ set h to h & " palindromic gapful numbers > 100 ending with " & firstOuter & ":"
else
set hr to h & " palindromic gapful numbers > 100 ending with digits from " & firstOuter & ("searchLimit toas " & lastOutertext) & ":th")
end if
ifset (is >to 1)" then> set100 endending ofwith output to ""
setif end(keep of> output1) then set s to h"s" & s
repeatset witht outerto from(lastEndDigit firstOuteras totext) & lastOuter":"
if (firstEndDigit is not lastEndDigit) then set t to "digits " & firstEndDigit & " to " & t
set end of output to theWorks's (collect(outer, countLimit, keep)) as text▼
set end of output to ""
▲ set end of set houtput to hr & " palindromic gapful number > 100 ending with " & firstOuters & ":"t
repeat with digit from firstEndDigit to lastEndDigit
▲ set end of output to theWorks's (collect(outerdigit, countLimitsearchLimit, keep)) as text
end repeat
end repeat
set AppleScript's text item delimiters to linefeed
set output to (rest of output) as text
set AppleScript's text item delimiters to astid
Line 339 ⟶ 346:
 
{{output}}
<pre style="font-size:80%">First 20 palindromic gapful numbers > 100 ending with digits from 1 to 9:
121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591
242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392
Line 350 ⟶ 357:
9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069
 
Last 15 of first 100 palindromic gapful numbers > 100 ending with digits from 1 to 9:
165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971
265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972
Line 361 ⟶ 368:
95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569
 
Last 10 of first 1000 palindromic gapful numbers > 100 ending with digits from 1 to 9:
17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871
27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872
Line 372 ⟶ 379:
9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
 
Last 5 of first 10000 palindromic gapful numbers > 100 ending with digits from 1 to 9:
1787557871 1787667871 1787777871 1787887871 1787997871
2787557872 2787667872 2787777872 2787887872 2787997872
Line 383 ⟶ 390:
968697796869 968706607869 968715517869 968724427869 968733337869
 
100000th palindromic gapful numbersnumber > 100 ending with digits from 1 to 9:
178788887871
278788887872
Line 394 ⟶ 401:
96878077087869
 
1000000th palindromic gapful numbersnumber > 100 ending with digits from 1 to 9:
17878799787871
27878799787872
Line 405 ⟶ 412:
9687870990787869
 
10000000th palindromic gapful numbersnumber > 100 ending with digits from 1 to 9:
1787878888787871
2787878888787872
Line 437 ⟶ 444:
96878787878786133168787878787869
 
1.0E+15th palindromic gapful numbersnumber > 100 ending with digits from 2 to 4:
27878787878787888878787878787872
3087878787878783113878787878787803
Nig
557

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/295864"