Rosetta Code

Palindromic gapful numbers: Difference between revisions

Page Discussion

Palindromic gapful numbers (view source)

Revision as of 13:15, 19 April 2021

398 bytes removed ,  3 years ago
→‎{{header|AppleScript}}: →‎Translation of Phix "Ludicrously fast …": 6.5-fold speed increase by dumping NSMutableDictionary altogether. Several minor tweaks and comment changes.
(Undo revision 330973 by Nig (talk))
(→‎{{header|AppleScript}}: →‎Translation of Phix "Ludicrously fast …": 6.5-fold speed increase by dumping NSMutableDictionary altogether. Several minor tweaks and comment changes.)
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 AppleScripttranslation version iswas developed directly from the originalPhix, 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 tryhelp tome understand the workingsprocess myself!. ForOn the setmy taskmachine, it'sthis notversion actuallytakes as0.12 fast as the script above, which doesn't have the overhead of being ableseconds to handlecarry ridiculously large numbers and which getsout the threeset setstasks of— results for each digit inonly a singletad sweep ratherslower than starting at the beginninghard-wired forscript each setabove. It'sThe alsobatch notof nearlyextreme astests fast asin the Phix originaldemo apparentlytakes is,around taking about twelve1.6 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-- AppleScriptReturn version "2.4" --a Macscript OSobject 10.10containing (Yosemite)the ormain laterhandlers.
 
-- 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
property outerDigitouterX11 : missing value▼
use framework "Foundation" -- For its NSMutableDictionary class and methods.
property searchLimitcountLimit : missing value▼
▼
▲ property outerDigit : missing value
property outerDigit_x11 : missing value
▲ property searchLimit : missing value
property to_skip : missing value
property palcount : missing value
property skipd : {{}, {}, {}, {}, {}, {}, {}, {}, {}}
property skipdSubskipdOuter : missing value
property outputpals : missing value
-- Work out what the remainder wouldfrom bethe ifdivision of the decimalpositive number describeddecimal asinteger onevalue orwhich twois
-- one or two instances of the digit 'ddigit' withseparated by 'gap' zeros betweenand themfollowed andby 'shift' zeros following,
-- and (which may not be toorealisable largeas foran AppleScript, were dividednumber) by the value 'outerDigit_x11outerX11', a multiple of 11.
on rmdr(ddigit, gap, shift)
-- UnlikeRemainders from the original Phix, thisdivision handlerof doesn'tleft-shifted maintaindecimals aby largemultiples cache,of but11 computesreliably itsrepeat
-- usableevery lowsix dividendplaces onshifted the> fly2, byso reducinguse shiftsa >dividend 9with tothe equivalentsequivalent betweendigit 4shifts and< 9.
set multipliercoefficient to 10 ^ ((shift - 43) mod 6 + 43)
if (gap > -1) then set multipliercoefficient to multipliercoefficient + 10 ^ ((gap + shift - 32) mod 6 + 43)
return (ddigit * multipliercoefficient mod outerDigit_x11outerX11) as integer
end rmdr
-- Recursively findinfer successivefrom palindromicremainder gapfularithmetic numbersany beginningpalindromic andgapful endingnumbers with
-- 'outerDigit'((count andlhs) keep* text2 versions+ ofgap) thosedigits inwhose outer digit is the requiredfirst countvalue in rangelhs.
-- 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 9459549945…549 result. (Text eg. "945" in the original.)
-- gap: length of inner to be filled in
-- remainder: remainder previouslyof outer, eg 9400049 mod 11, but derived from rmdr() results.
set shift to (count lhs) -- left shift (shouldof alwaysinner equal length(lhs), I think) same as its right shift).
-- Here,This translation's 'skipd' isn'tis a monolithic dictionary with four-elementdeep keys,AppleScript butlist astructure listindexed with 9the sublists,elements
-- of the original dictionary's keys: (skipd) -> outermost digit -> shift -> gap -> remainder (+ 1).
-- each containing 99 smaller dictionaries with two-element keys. The values of the original
-- The outermost digit element doesn't change during a search based on it, so the script property
-- 'outerDigit' and 'remainder' key elements are used to index this structure. Since 'outerDigit'
-- 'skipdOuter' has butbeen onepreset valueto perskipd's outer-th digit,sublist in the 'outerDigit'thset-up for the current search. sublist is prefetched and assigned
-- Populate it just enough here to ensure that the propertyslot 'skipdSub'about into thebe set-upchecked for eacha 'skip' value sweepexists.
setrepeat |key|(shift to- {gap,(count shift}my skipdOuter)) times
set skip to (item (remainderset + 1)end of my skipdSub)'sskipdOuter to objectForKey:(|key|){}
end repeat▼
if (skip is missing value) then -- Key not in dictionary. Set 'skip' high for the 'if' test below.
repeat (gap - (count setitem skipshift toof searchLimitmy skipdOuter)) times
set end setof item midshift of templatemy skipdOuter to d{}▼
else
end set skip to (skip as real) div 1repeat
repeat (remainder + 1 - (count item gap of item shift of my skipdOuter)) times
end if▼
if (palcount + skip >set to_skip)end thenof --item (Alsogap ifof they'reitem equal,shift originally.)of my skipdOuter to missing value
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 outerDigit_x11outerX11
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-- (gapThis isone 2)would thenbe in the current keep range, so realise it as text and store it.
if (gap is 2) then set item mid of templated to {d, d} -- Not d *11 in11 caseas d iscould be 0.
elseset --end ifof my pals to (gaplhs is& 1d & reverse of lhs) thenas text
▲ 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
else
set skip to skip + 1
end if
end if
if (palcount = searchLimitcountLimit) then exit repeat
end repeat
if (palcount < to_skip) then (set item (remainder + 1) of item gap of item shift of my skipdSub)'sskipdOuter setObject:(skip)to forKey:(|key|)skip
else
set palcount to palcount + skip
Line 264 ⟶ 255:
end palindromicGapfuls
-- ReturnSet up a listsearch of numeric texts representingfor the last 'keep' of the first 'searchLimitcountLimit' PGNs > 100 whose outer digit is 'outer',
-- call the recursive process for each palindrome width, and eventually return the stored numeric texts.
-- palindromic gapful numbers > 100 which begin and end with 'digit'.▼
on collect(digitouter, searchLimitcountLimit, keep)
-- Initialise these script object properties for the current search.
set outerDigitouterX11 to digitouter * 11
set outerDigit_x11my countLimit to outerDigit * 11countLimit
set my searchLimitto_skip to searchLimitcountLimit - keep
set to_skip to searchLimit - keep▼
set palcount to 0
set skipdSubskipdOuter to item outerDigitouter of my skipd
set outputpals to {}
-- LocalsAlso locals and TIDs.
set gaplhs to 1 -- Initially 1 digit between the {outer pair.}
set lhsgap to {outerDigit}1 -- InitialNumber leftof enddigits ofbetween outer palindomespair.
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to "" -- For list-to-text coercions.
repeat until (palcount = searchLimitcountLimit)
set remainder to rmdr(outerDigitouter, gap, 0)
palindromicGapfuls(lhs, gap, remainder)
set gap to gap + 1
Line 287 ⟶ 277:
set AppleScript's text item delimiters to astid
return outputpals
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 310 ⟶ 301:
{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 setRC task.
set output to {}
Line 317 ⟶ 308:
set AppleScript's text item delimiters to " "
repeat with i from 1 to (count tests)
set {searchLimitcountLimit, keep, firstEndDigitfirstOuter, lastEndDigitlastOuter} to item i of tests
setif |from|(countLimit to searchLimit -= keep) + 1then
▲ set to_skiph to searchLimit"First -" keep& countLimit
if (searchLimit = keep) then▼
set r to "First " & searchLimit▼
else if (keep > 1) then
set rh to "Last " & keep & (" of first " & searchLimitcountLimit)
▲ else
▲ set rh to "First " & searchLimitordinalise(countLimit)
▲ end if
if ((keep = 1) and (firstOuter = lastOuter)) then
set end of output set h to rh & " palindromic gapful number > 100 ending with " & sfirstOuter & t":"▼
▲ else if (searchLimitfirstOuter = keeplastOuter) then
▲ -- set h to h & " palindromic gapful numbers > 100 whichending beginwith and" end& withfirstOuter & 'digit'.":"
else
set rh to h & " palindromic gapful numbers > 100 ending with digits from " & firstOuter & (searchLimit" asto text)" & lastOuter & "th:")
end if
setif s(i to> "1) >then 100set endingend withof output to ""
ifset (keepend >of 1) then set soutput to "s" & sh
setrepeat twith toouter (lastEndDigitfrom asfirstOuter text) &to ":"lastOuter
set end of output to theWorks's (collect(digitouter, searchLimitcountLimit, keep)) 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
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 346 ⟶ 339:
 
{{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 357 ⟶ 350:
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 368 ⟶ 361:
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 379 ⟶ 372:
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 390 ⟶ 383:
968697796869 968706607869 968715517869 968724427869 968733337869
 
100000th palindromic gapful numbernumbers > 100 ending with digits from 1 to 9:
178788887871
278788887872
Line 401 ⟶ 394:
96878077087869
 
1000000th palindromic gapful numbernumbers > 100 ending with digits from 1 to 9:
17878799787871
27878799787872
Line 412 ⟶ 405:
9687870990787869
 
10000000th palindromic gapful numbernumbers > 100 ending with digits from 1 to 9:
1787878888787871
2787878888787872
Line 444 ⟶ 437:
96878787878786133168787878787869
 
1.0E+15th palindromic gapful numbernumbers > 100 ending with digits from 2 to 4:
27878787878787888878787878787872
3087878787878783113878787878787803
Nig
557

edits

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