Palindromic gapful numbers: Difference between revisions

<langsyntaxhighlight lang="applescript">on doTask()

return doTask()</langsyntaxhighlight>

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.

<syntaxhighlight lang ="applescript">use-- AppleScriptReturn version "2.4" --a Macscript OSobject 10.10containing (Yosemite)the ormain laterhandlers.

useproperty frameworkouterX11 "Foundation": missing value

property skipd : {{}, {}, {}, {}, {}, {}, {}, {}, {}}

property outputskipdOuter : {}missing -- Output list.value

-- Work out the remainder whenfrom the decimaldivision numberof formedthe frompositive onedecimal orinteger two instances of thevalue digitwhich 'digit'is

-- one or two instances of digit 'digit' separated by 'gap' zeros and followed by 'shift' zeros is divided by 'dd', a two-digit multiple of 11. :)

-- dividendevery cansix beplaces quicklyshifted derived> for2, /any/so combinationuse ofa digitdividend shiftswith fromthe equivalent digit shifts < 10 without9.

if (digitgap is> 0-1) then returnset digitcoefficient to coefficient + 10 ^ ((gap + shift - 2) mod 6 + 3)

return (vdigit * coefficient mod ddouterX11) as integer

-- Recursively constructinfer palindromicfrom gapfulremainder numbersarithmetic andany storepalindromic asgapful text those which fall within the requirednumbers range.with

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

set shift to (count lhs) -- left shift of inner (shouldsame alwaysas equalits length(lhsright shift),. I think)

-- Inof the original Phix, dictionary's keys: (skipd') is-> aoutermost dictionarydigit with-> shift four-element> keysgap -> remainder (+ 1).

-- Here,The tooutermost easedigit theelement congestiondoesn't inchange AppleScript/ASObjC, it'sduring a listsearch ofbased 99on it, so the muchscript smallerproperty

-- 0Populate -it 98,just isenough usedhere insteadto withensure 1that addedthe toslot itabout to indexbe thechecked for a 'skip' value listexists.

-- the process. The set taskend completesof moremy quicklyskipdOuter withoutto them, but they{}

setrepeat |key|(gap to- {gap,(count item shift, outer}of my skipdOuter)) times

set skip to (item (remainderset +end 1)of item shift of my skipd)'sskipdOuter to objectForKey:(|key|){}

ifend (skip is missing value) thenrepeat

repeat (remainder + 1 -- Key not in dictionary.(count Engineeritem agap highof additionitem resultshift inof themy nextskipdOuter)) test.times

set skipend of item gap of item shift of my skipdOuter to searchLimitmissing value

elseend repeat

set skip to item (skipremainder as+ real1) divof 1item gap of item shift of my skipdOuter

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

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 lhs_shld to {d, d} -- Not d * 11. (as d maycould be 0.)

elseset --end ifof my pals to (gaplhs is& 1d & reverse of lhs) thenas text

if (palcount = searchLimitcountLimit) then exit repeat

if (palcount < to_skip) then (set item (remainder + 1) of item gap of item shift of my skipd)'sskipdOuter setObject:(skip)to forKey:(|key|)skip

-- ReturnSet up a listsearch of numeric texts representingfor the last 'keep' of the first 'countLimit' PGNs > 100 whose outer digit is 'outer',

on collect(digitouter, searchLimitcountLimit, keep)

-- Set thisInitialise script object's properties for the current batchsearch.

set my searchLimitouterX11 to searchLimitouter * 11

set to_skipmy countLimit to searchLimit - keepcountLimit

set outputskipdOuter to {}item outer of my skipd

--set Locals.pals to {}

set-- lhsAlso tolocals {digit}and TIDs.

set gaplhs to 1{outer}

set shiftgap to 01 -- Number of digits between outer pair.

set AppleScript's text item delimiters to "" -- For list-to-text coercions.

repeat until (palcount = searchLimitcountLimit)

set remainder to rmdr(digitouter, gap, shift, digit * 110)

return outputpals

-- set tests to {{20, 20, 1, 9}, {100, 15, 1, 9}, {1000, 10, 1, 9}} -- ToThe do the setRC task only.

set {searchLimitcountLimit, keep, firstEndDigitfirstOuter, lastEndDigitlastOuter} to item i of tests

setif |from|(countLimit to searchLimit -= keep) + 1then

set rh to "Last " & keep & (" of first " & searchLimitcountLimit)

set rh to h & " palindromic gapful numbers > 100 ending with digits from " & firstOuter & (searchLimit" asto text)" & lastOuter & "th:")

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 output to (rest of output) as text

doTask()</langsyntaxhighlight>

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

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

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

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

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

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

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

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

<langsyntaxhighlight lang="c">#include <stdbool.h>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="cpp">#include <iostream>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromesgapful(digit, pow)

(1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(10)}\n" }</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count)

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count)

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">struct PalindromicGapfuls

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count, keep)

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count, keep)

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">struct PalindromicGapfuls

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count, keep)

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">struct PalindromicGapfuls

puts (Time.monotonic - start).total_seconds</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">class PalNo

<langsyntaxhighlight lang="fsharp">

<langsyntaxhighlight lang="factor">USING: formatting fry io kernel lists lists.lazy locals math

[ show-palindromic-gapfuls ] 2tri@</langsyntaxhighlight>

<langsyntaxhighlight lang="freebasic">function is_gapful( n as uinteger ) as boolean

print_range(yays(), 991, 1000)</langsyntaxhighlight>

In [{{FormulaeEntry|page=https://wiki.formulae.org/?script=examples/Palindromic_gapful_numbers this] page you can see the solution of this task.}}

<langsyntaxhighlight lang="go">package main

}</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Control.Monad (guard)

putStrLn "\ndone."</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Data.List (sort, unfoldr)

]</langsyntaxhighlight>

<syntaxhighlight lang="text">

<langsyntaxhighlight lang="java">

<langsyntaxhighlight lang="julia">import Base.iterate, Base.IteratorSize, Base.IteratorEltype

</langsyntaxhighlight>{{out}}

<langsyntaxhighlight lang="ruby">import strutils # for number input

echo (epochTime() - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">import strutils # for number input

echo (epochTime() - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">import times

echo (epochTime() - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="pascal">program PalinGap;

end.</langsyntaxhighlight>{{out}}<pre style="height:35ex;overflow:scroll;font-size:87%">

<langsyntaxhighlight lang="perl">use strict;

}</langsyntaxhighlight>

-- same as (400000 rem 99 + 40 rem 99) rem 99, and further 40 rem 99 50500

--

-- AlsoFurther, when9459549 fillingrem a99 "hole", such asis the finalsame 9, weas find

-- (the sum of rem 99 on all of those pieces) rem v 99

-- Finding eg 400040 rem 99 can also be simplified, 9451549it remis 99of =course 19,the

-- same as (400000 rem 99 + 945254940 rem 99) =rem 2999, and further 40 rem 99

-- is the same as (4 rem 99[already 9453549known])*10 rem 99 =[smaller 39,nos].

-- 9456549 rem 99 =v 69,

-- 94575499450549 rem 99 = 79,9

-- 94585499451549 rem 99 = 8919, and

-- 94595499452549 rem 99 = 029,

-- 9453549 rem 99 ^= 39,

-- But actually we can predict what will fit from the9456549 partialrem sum99 of= 69,

-- prior pieces rem 99, ie 9000009..50500, and the same9457549 canrem be99 said= 79,

-- what the "outer" actually are, but what their sum9459549 rem 99 is= 0, and

-- likewise for larger and larger holes. ^

-- AsIf we stumblelater acrossfind largerourselves andlooking largerat holes,the whatsame wesize learnhole, canwith

-- bethe usedsame toouter skip morerem and morethe similar,same suchrem that99 findingoutmost therequirement, we

<span style="color: #000080;font-style:italic;">-- ie <nowiki>{{</nowiki>{91}, {91}, {91}, {91}, {91}, {91}, {91}, {91}, {9}1<nowiki>}}</nowiki>,

-- if k cache[digit][n] &= remainder(cache[digit][n][$]4*10^(m-1),nn11) [already known] then

<pre style="font-size: 11px10px">

<langsyntaxhighlight Phixlang="phix">--count = 100000

end while</langsyntaxhighlight>

<langsyntaxhighlight lang="prolog">init_palindrome(Digit, p(10, Next, 0)):-

print_numbers(991, 1000, Numbers).</langsyntaxhighlight>

<langsyntaxhighlight lang="python">from itertools import count

print('', re.sub(r"[{},\[\]]", '', txt))</langsyntaxhighlight>

<langsyntaxhighlight lang="python">'''Palindromic gapful numbers'''

main()</langsyntaxhighlight>

<syntaxhighlight lang="raku" perl6line>constant @digits = '0','1','2','3','4','5','6','7','8','9';

@npal.hyper.map: -> \this { next unless (my \test = digit ~ this ~ digit) %% divisor; test }

}</langsyntaxhighlight>

<langsyntaxhighlight lang="rexx">/*REXX program computes and displays palindromic gapful numbers, it also can show those */

return</langsyntaxhighlight>

<langsyntaxhighlight lang="ring">

<langsyntaxhighlight lang="ruby">def palindromesgapful(digit, pow)

(1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(10)}\n" }</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count)

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count)

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">class PalindromicGapfuls

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count, keep)

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">def palindromicgapfuls(digit, count, keep)

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">class PalindromicGapfuls

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">

<langsyntaxhighlight lang="ruby">class PalNo

puts (Time.now - start)</langsyntaxhighlight>

<langsyntaxhighlight lang="rust">fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="rust">fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">class PalindromeGenerator (digit, base=10) {

})</langsyntaxhighlight>

<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Conv, Fmt

}</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">// 10,True --> 101,111,121,131,141,151,161,171,181,191,202, ..

}</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">println("First 20 palindromic gapful numbers:");

}</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">/* We can also thread the whole mess, which for this case, is a 3.75 speed up

}</langsyntaxhighlight>