Summarize and say sequence: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 63:
{{trans|C++}}
<
V longest = 0
Line 88:
print(‘[#.] Iterations: #.’.format(test, result.len + 1))
print(result.join("\n"))
print("\n")</
{{out}}
Line 163:
=={{header|Ada}}==
<
with Ada.Containers.Vectors;
procedure SelfRef is
Line 224:
IO.Put (mseed, Width => 1); New_Line;
len := Iterate (mseed, True);
end SelfRef;</
{{out}}
<pre>21 Iterations:
Line 251:
=={{header|Aime}}==
{{trans|C}}
<
next(text s)
{
Line 326:
return 0;
}</
{{out}}
<pre>longest length is 21
Line 399:
=={{header|AutoHotkey}}==
Not optimized in the slightest.
<syntaxhighlight lang="autohotkey">
; The following directives and commands speed up execution:
#NoEnv
Line 433:
return errorlevel
}
</syntaxhighlight>
Output:
<pre>Seeds: 9009 9090 9900
Line 463:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
DIM list$(30)
maxiter% = 0
Line 503:
IF d%(I%) o$ += STR$d%(I%) + STR$I%
NEXT
= o$</
'''Output:'''
<pre>
Line 535:
=={{header|Bracmat}}==
<
= seq N next
. ( next
Line 606:
)
& out$("Iterations:" !max !seqs)
);</
Output:
<pre> Iterations:
Line 637:
=={{header|C}}==
<
#include <stdlib.h>
#include <string.h>
Line 759:
return 0;
}</
{{out}}
<pre>longest length: 21
Line 836:
=={{header|C++}}==
<
#include <iostream>
#include <string>
Line 880:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 953:
=={{header|Clojure}}==
<
"simplifies form of reduce calls"
[bindings & body]
Line 998:
(zero? cmp) (conj max-seqs new-seq)))))
(def results (find-longest 1000000))</
The above code saves a lot of time by only calculating summary step sequences for one
Line 1,008:
but the one here will serve.
<
"produce all the permutations of a finite sequence"
[ds]
Line 1,026:
(println "Sequence:")
(doseq [ds result]
(println (apply str ds))))</
=={{header|CLU}}==
<
digit_count: array[int] := array[int]$fill(0,10,0)
for c: char in string$chars(s) do
Line 1,088:
s := summarize(s)
end
end start_up</
{{out}}
<pre>Seed values: 9009 9090 9900
Line 1,120:
This takes less than a second to run, even though the only real optimization is to exclude integers that don't have their digits descending.
<
sequence = (n) ->
cnts = {}
Line 1,164:
console.log max_i, max_seq
</syntaxhighlight>
<pre> 9900 ["2920", "192210", "19222110", "19323110", "1923123110", "1923224110", "191413323110",
Line 1,173:
=={{header|Common Lisp}}==
Doesn't do cache, and takes forever.
<
(let* ((s (sort (map 'list #'identity str) #'char>))
(out (list (first s) 0)))
Line 1,201:
(let ((r (find-longest 1000000)))
(format t "Longest: ~a~%" r)
(ref-seq-len (first (first r)) t))</
9900
2920
Line 1,222:
19281716151423228110
19281716151413427110
19182716152413228110</
=={{header|D}}==
===Slow High-level Version===
{{trans|Ruby}}
<
string[] selfReferentialSeq(string n, string[] seen=[]) nothrow {
Line 1,265:
foreach (const idx, const val; max_vals[0].text.selfReferentialSeq)
writefln("%2d %s", idx + 1, val);
}</
{{out}}
<pre>values: [9009, 9090, 9900]
Line 1,293:
===More Efficient Version===
{{trans|Python}}
<
struct Permutations(bool doCopy=true, T) {
Line 1,471:
A036058_length!true(n.text);
}
}</
The output is similar to the Python entry.
Line 1,477:
{{trans|C}}
From the C version, with a memory pool for a faster tree allocation.
<
struct MemoryPool(T, int MAX_BLOCK_BYTES = 1 << 17) {
Line 1,610:
printf("Allocated %d Rec tree nodes.\n", nNodes);
//recPool.freeAll;
}</
Faster than the C entry, run-time is about 1.16 seconds using the dmd compiler (about 1.5 without memory pool). Same output as the C entry.
Line 1,616:
Extra credit: searching up to 1e+10 does not find a longer sequence.
<
(lib 'hash)
(lib 'list) ;; permutations
Line 1,729:
(writeln (expt 10 n) '--> 'max-sequence= (1+ seqmax) 'nodes= (length (hash-values H))))
</syntaxhighlight>
{{out}}
<
(task 6)
1 (9009 9090 9900)
Line 1,765:
10000000000 --> max-sequence= 21 nodes= 188493
</syntaxhighlight>
=={{header|Eiffel}}==
Only checks numbers where digits are in ascending order. Digits with trailing zeros have to be treated as ascending numbers (special case). Calculates all the permutations in the end.
<syntaxhighlight lang="eiffel">
class
SELF_REFERENTIAL_SEQUENCE
Line 1,968:
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,002:
=={{header|F_Sharp|F#}}==
Takes ~0.4 sec. to filter numbers less than 1 million with digits in descending order, so don't know why all the emphasis on optimization. Doesn't use any strings which maybe is good.
<
// Summarize and say sequence . Nigel Galloway: April 23rd., 2021
let rec fN g=let n=let n,g=List.head g|>List.countBy id|>List.unzip in n@(g|>List.collect(fun g->if g<10 then [g] else [g/10;g%10]))
Line 2,013:
printf "Permutations of "; n.Head|>List.rev|>List.iter(printf "%d"); printfn " produce:"
for n in n do (for n,g in List.countBy id n|>List.sort|>List.rev do printf "%d%d" g n); printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 2,041:
=={{header|Factor}}==
Like the Eiffel example, this program saves time by considering only seed numbers whose digits are in increasing order (zeros are exempt). This ensures that extra permutations of a number are not searched, as they produce equivalent sequences (aside from the first element). For instance, <tt>21</tt> is the first number to be skipped because it's a permutation of <tt>12</tt>.
<
math.functions math.ranges math.statistics math.text.utils
prettyprint sequences sets ;
Line 2,077:
"Sequence:" print >numbers . ;
MAIN: main</
{{out}}
<pre>
Line 2,110:
=={{header|Go}}==
Brute force
<
import (
Line 2,184:
}
return r
}</
Output:
<pre>
Line 2,225:
=={{header|Groovy}}==
Solution:
<
def number = delegate as String; def sequence = []
Line 2,250:
}
}
}</
Test:
<
println "\nLargest sequence size among seeds < 1,000,000\n"
Line 2,258:
println "Size: ${max.seqSize}\n"
println "Sample sequence:"
max.seeds[0].selfReferentialSequence.each { println it }</
Output:
<pre>Largest sequence size among seeds < 1,000,000
Line 2,291:
=={{header|Haskell}}==
Brute force and quite slow:
<
import Data.List (group, sort)
Line 2,316:
map show -- turn the numbers into digits
[1..1000000] -- The input seeds
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 2,356:
every (n := "") ||:= (0 < Counts[i := 9 to 0 by -1]) || i # assemble counts
return integer(n)
end</
{{libheader|Icon Programming Library}}
Line 2,396:
exists at the maximum sequence length. As with the first example, it works
in both Icon and Unicon.
<
procedure main(A)
Line 2,425:
every s := !seqTab do (write() & every write(!(!s\1)[2]))
end
</syntaxhighlight>
Output with <tt>limit = 1000000</tt>:
<pre>
Line 2,457:
=={{header|J}}==
Given:
<
digits=: 10&#.inv"0 :. ([: ".@; (<'x'),~":&.>)
summar=: (#/.~ ,@,. ~.)@\:~&.digits
sequen=: ~.@(, summar@{:)^:_
values=: ~. \:~&.digits i.1e6
allvar=: [:(#~(=&<.&(10&^.) >./))@~.({~ perm@#)&.(digits"1) </
The values with the longest sequence are:
<
9900 9090 9009
# sequen 9900
Line 2,491:
19281716151423228110
19281716151413427110
19182716152413228110</
Notes:
Line 2,497:
<code>digits</code> is an invertible function that maps from a number to a sequence of digits and back where the inverse transform converts numbers to strings, concatenates them, and then back to a number.
<
3 2 1
digits inv 34 5
345</
<code>summar</code> computes the summary successor.
<
10 11 12</
<code>sequen</code> computes the complete non-repeating sequence of summary successors
Line 2,515:
=={{header|Java}}==
{{works with|Java|8}}
<
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.IntStream;
Line 2,591:
}
}
}</
<pre>Seeds:
Line 2,622:
=={{header|Javascript}}==
<
function selfReferential(n) {
n = n.toString();
Line 2,640:
return [...new Set(res)];
}
</syntaxhighlight>
=={{header|jq}}==
<
def runs:
reduce .[] as $item
Line 2,703:
;
task(1000000)</
{{out}}
<div style="overflow:scroll; height:400px;">
<
The maximal length to convergence for seeds up to 1000000 is 21.
The corresponding seeds are the allowed permutations
Line 2,735:
19281716151413430000,
19182716152413230000
]</
=={{header|Julia}}==
<
function findnextterm(prevterm)
Line 2,799:
selfseq(1000000)
</
The longest sequence length is 21.
Line 2,873:
=={{header|Kotlin}}==
<
const val LIMIT = 1_000_000
Line 2,940:
println()
}
}</
{{out}}
Line 3,016:
=={{header|Lua}}==
Runs in about nine seconds under LuaJIT. Uses memoisation via the global table 'nextTerm'.
<
function findNext (nStr)
local nTab, outStr, pos, count = {}, "", 1, 1
Line 3,068:
print("\n\nIterations: " .. highest)
print("\nSample sequence:")
for _, v in pairs(hiSeq[1]) do print(v) end</
{{out}}
<pre>Seed values: 9009 9090 9900
Line 3,098:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
DisplaySequence[ x_ ] := NestWhileList[selfRefSequence,x,UnsameQ[##]&,4]
data= {#, Length@DisplaySequence[#]}&/@Range[1000000];
Print["Values: ", Select[data ,#[[2]] == Max@data[[;;,2]]&][[1,;;]]]
Print["Iterations: ", Length@DisplaySequence[#]&/@Select[data ,#[[2]] == Max@data[[;;,2]]&][[1,;;]]]
DisplaySequence@Select[data, #[[2]] == Max@data[[;;,2]]&][[1]]//Column</
<pre>Values: {9009, 9090, 9900}
Line 3,133:
A version which uses a cache to store the number of iterations and thus avoids to compute the sequence for each permutation. The version without cache runs in more than 9 seconds. This version runs in less than 300 ms.
<
var cache: Table[seq[char], int] # Maps key -> number of iterations.
Line 3,178:
echo "Seed values: ", seeds.join(", ")
echo "Sequence for $#:".format(seeds[0])
for s in sequence($seeds[0]): echo s</
{{out}}
Line 3,207:
=={{header|Perl}}==
<
my @a;
$a[$_]++ for split '', shift;
Line 3,244:
print "longest ($mlen): @mlist\n";
print join("\n", seq($_)), "\n\n" for @mlist;</
{{out}}
<pre>longest (21): 9009 9090 9900
Line 3,271:
=={{header|Phix}}==
Optimisation idea taken from CoffeeScript, completes in under a second.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"000000"</span>
Line 3,348:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cycle length is "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">maxcycle</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestseen</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<!--</
<pre>
{"9900","9009","9090"}
Line 3,377:
=={{header|PicoLisp}}==
Using 'las' from [[Look-and-say sequence#PicoLisp]]:
<
(let L (mapcar format (chop Seed))
(make
Line 3,392:
(println 'Values: (cdr Res))
(println 'Iterations: (car Res))
(mapc prinl (selfRefSequence (cadr Res))) )</
Output:
<pre>Values: (9009 9090 9900)
Line 3,421:
The number generation function follows that of Look-and-say with a sort. only the first of any set of numbers with the same digits has the length of its sequence calculated in function max_A036058_length, although no timings were taken to check if the optimisation was of value.
<
def A036058(number):
Line 3,485:
for n in starts:
print()
A036058_length(str(n), printit=True)</
;Output:
Line 3,519:
=={{header|q}}==
<
sumsay:ls desc@ / summarize & say
Line 3,530:
rpt["Seeds"]" "sv string raze seeds where its=top / all forms of top seed/s
rpt["Iterations"]string top
rpt["Sequence"]"\n\n","\n"sv raze seq where its=top</
{{out}}
<pre>
Line 3,565:
=={{header|Racket}}==
<
#lang racket
Line 3,602:
(printf "Numbers: ~a\nLength: ~a\n" (string-join nums ", ") len)
(for ([n seq]) (printf " ~a\n" n))
</syntaxhighlight>
{{out}}
<pre>
Line 3,634:
{{Works with|rakudo|2018.03}}
<syntaxhighlight lang="raku"
my $longest = 0;
my %seen;
Line 3,679:
}
return @perms;
}</
{{out}}
Line 3,714:
The REXX language supports '''sparse''' (stemmed) arrays, so this program utilizes REXX's hashing of
<br>array elements to speed up the checking to see if a sequence has been generated before.
<
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 1 /*Not specified? Then use the default.*/
Line 3,747:
do k=1 for words(q); say word(q, k)
end /*k*/
end /*j*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default inputs:}}
<br>(Shown at five-sixths size.)
Line 3,827:
=={{header|Ruby}}==
Cached for performance
<
def selfReferentialSequence_cached(n, seen = [])
return $cache[n] if $cache.include? n
Line 3,863:
selfReferentialSequence_cached(max_vals[0]).each_with_index do |val, idx|
puts "%2d %d" % [idx + 1, val]
end</
output
<pre>values: [9009, 9090, 9900]
Line 3,894:
This example creates a ParVector, which is a collection type that inherently uses parallel processing, of all seeds within the range, maps each seed to a tuple containing the seed, the sequence, and the number of iterations, sorts the collection by decreasing sequence length, then shows the relevant information for the maximal sequences at the head of the collection.
<
import scala.annotation.tailrec
Line 3,928:
dTrec(Vector[(Int, Int)](), num)
}
}</
{{out}}
Line 3,960:
=={{header|Tcl}}==
<!-- The first version of this code had a neat trick with sorting the strings characters and using a counting regexp, but it was very slow -->
<
foreach c [split $n ""] {incr t($c)}
foreach c {9 8 7 6 5 4 3 2 1 0} {
Line 4,008:
puts "\t$seed"
}
}} 1000000</
Output:
<pre>
Line 4,045:
This is a close, almost expression-by-expression transliteration of the Clojure version.
<
(defmacro reduce-with ((acc init item sequence) . body)
^(reduce-left (lambda (,acc ,item) ,*body) ,sequence ,init))
Line 4,102:
(put-line `Iterations: @(length result)`)
(put-line)
(put-line `Sequence: @(strfy result)`))))</
{{out}}
Line 4,120:
Like in Common Lisp, TXR's <code>sort</code> is destructive, so we take care to use <code>copy-str</code>.
<
(let* ((s [sort (copy-str str) <])
(out `@[s 0]0`))
Line 4,146:
(when (> l len) (set len l) (set nums nil))
(when (= l len) (push x nums))))
(list nums len)))</
{{out}}
Line 4,175:
==={{trans|Racket}}===
<
(defmacro for-accum (accum-var-inits each-vars . body)
(let ((accum-vars [mapcar first accum-var-inits])
Line 4,220:
*seq))))
(put-line `Numbers: @{nums ", "}\nLength: @len`)
(each ((n seq)) (put-line ` @n`)))</
{{out}}
Line 4,252:
{{libheader|Wren-seq}}
{{libheader|Wren-math}}
<
import "/math" for Nums
Line 4,322:
System.print()
}
}</
{{out}}
Line 4,397:
=={{header|zkl}}==
<
fcn lookAndJustSaying(seed){ // numeric String --> numeric String
Line 4,428:
.filter(fcn(s){ s[0]!="0" }) : Utils.Helpers.listUnique(_);
println(max," iterations for ",zs.concat(", "));
zs.pump(Console.println,sequence,T("concat",", "));</
Ignoring permutations cut run time from 4 min to 9 sec.
{{out}}
|