Summarize and say sequence: Difference between revisions

{{trans|C++}}

 

V longest = 0

 

DefaultDict[Char, Int] map

L(c) n

print(‘[#.] Iterations: #.’.format(test, result.len + 1))

print(result.join("\n"))

 

{{out}}

 

=={{header|Ada}}==

with Ada.Containers.Vectors;

procedure SelfRef is

IO.Put (mseed, Width => 1); New_Line;

len := Iterate (mseed, True);

{{out}}

<pre>21 Iterations:

=={{header|Aime}}==

{{trans|C}}

next(text s)

{

 

return 0;

{{out}}

<pre>longest length is 21

=={{header|AutoHotkey}}==

Not optimized in the slightest.

; The following directives and commands speed up execution:

#NoEnv

return errorlevel

}

Output:

<pre>Seeds: 9009 9090 9900

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM list$(30)

maxiter% = 0

IF d%(I%) o$ += STR$d%(I%) + STR$I%

NEXT

'''Output:'''

<pre>

 

=={{header|Bracmat}}==

= seq N next

. ( next

)

& out$("Iterations:" !max !seqs)

Output:

<pre> Iterations:

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>longest length: 21

 

=={{header|C++}}==

#include <iostream>

#include <string>

return 0;

}

{{out}}

<pre>

 

=={{header|Clojure}}==

"simplifies form of reduce calls"

[bindings & body]

(zero? cmp) (conj max-seqs new-seq)))))

 

 

The above code saves a lot of time by only calculating summary step sequences for one

but the one here will serve.

 

"produce all the permutations of a finite sequence"

[ds]

(println "Sequence:")

(doseq [ds result]

 

=={{header|CLU}}==

digit_count: array[int] := array[int]$fill(0,10,0)

for c: char in string$chars(s) do

s := summarize(s)

end

{{out}}

<pre>Seed values: 9009 9090 9900

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 = {}

console.log max_i, max_seq

 

 

<pre> 9900 ["2920", "192210", "19222110", "19323110", "1923123110", "1923224110", "191413323110",

=={{header|Common Lisp}}==

Doesn't do cache, and takes forever.

(let* ((s (sort (map 'list #'identity str) #'char>))

(out (list (first s) 0)))

(let ((r (find-longest 1000000)))

(format t "Longest: ~a~%" r)

9900

2920

19281716151423228110

19281716151413427110

 

=={{header|D}}==

===Slow High-level Version===

{{trans|Ruby}}

 

string[] selfReferentialSeq(string n, string[] seen=[]) nothrow {

foreach (const idx, const val; max_vals[0].text.selfReferentialSeq)

writefln("%2d %s", idx + 1, val);

{{out}}

<pre>values: [9009, 9090, 9900]

===More Efficient Version===

{{trans|Python}}

 

struct Permutations(bool doCopy=true, T) {

A036058_length!true(n.text);

}

The output is similar to the Python entry.

 

{{trans|C}}

From the C version, with a memory pool for a faster tree allocation.

 

struct MemoryPool(T, int MAX_BLOCK_BYTES = 1 << 17) {

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.

 

Extra credit: searching up to 1e+10 does not find a longer sequence.

 

(lib 'hash)

(lib 'list) ;; permutations

(writeln (expt 10 n) '--> 'max-sequence= (1+ seqmax) 'nodes= (length (hash-values H))))

{{out}}

(task 6)

1 (9009 9090 9900)

10000000000 --> max-sequence= 21 nodes= 188493

 

 

=={{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.

class

SELF_REFERENTIAL_SEQUENCE

 

end

{{out}}

<pre>

=={{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]))

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 ""

{{out}}

<pre>

=={{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, &nbsp; <tt>21</tt> &nbsp; is the first number to be skipped because it's a permutation of &nbsp; <tt>12</tt>.

math.functions math.ranges math.statistics math.text.utils

prettyprint sequences sets ;

"Sequence:" print >numbers . ;

 

{{out}}

<pre>

=={{header|Go}}==

Brute force

 

import (

}

return r

Output:

<pre>

=={{header|Groovy}}==

Solution:

def number = delegate as String; def sequence = []

 

}

}

Test:

 

println "\nLargest sequence size among seeds < 1,000,000\n"

println "Size: ${max.seqSize}\n"

println "Sample sequence:"

Output:

<pre>Largest sequence size among seeds < 1,000,000

=={{header|Haskell}}==

Brute force and quite slow:

import Data.List (group, sort)

 

map show -- turn the numbers into digits

[1..1000000] -- The input seeds

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

every (n := "") ||:= (0 < Counts[i := 9 to 0 by -1]) || i # assemble counts

return integer(n)

 

{{libheader|Icon Programming Library}}

exists at the maximum sequence length. As with the first example, it works

in both Icon and Unicon.

 

procedure main(A)

every s := !seqTab do (write() & every write(!(!s\1)[2]))

end

Output with <tt>limit = 1000000</tt>:

<pre>

=={{header|J}}==

Given:

digits=: 10&#.inv"0 :. ([: ".@; (<'x'),~":&.>)

summar=: (#/.~ ,@,. ~.)@\:~&.digits

sequen=: ~.@(, summar@{:)^:_

values=: ~. \:~&.digits i.1e6

 

The values with the longest sequence are:

 

9900 9090 9009

# sequen 9900

19281716151423228110

19281716151413427110

 

Notes:

<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

 

<code>summar</code> computes the summary successor.

 

 

<code>sequen</code> computes the complete non-repeating sequence of summary successors

=={{header|Java}}==

{{works with|Java|8}}

import java.util.concurrent.ConcurrentHashMap;

import java.util.stream.IntStream;

}

}

 

<pre>Seeds:

 

=={{header|Javascript}}==

function selfReferential(n) {

n = n.toString();

return [...new Set(res)];

}

 

=={{header|jq}}==

def runs:

reduce .[] as $item

;

 

{{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

19281716151413430000,

19182716152413230000

 

=={{header|Julia}}==

 

function findnextterm(prevterm)

 

selfseq(1000000)

The longest sequence length is 21.

 

 

=={{header|Kotlin}}==

 

const val LIMIT = 1_000_000

println()

}

 

{{out}}

=={{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

print("\n\nIterations: " .. highest)

print("\nSample sequence:")

{{out}}

<pre>Seed values: 9009 9090 9900

 

=={{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,;;]]]

 

<pre>Values: {9009, 9090, 9900}

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.

echo "Seed values: ", seeds.join(", ")

echo "Sequence for $#:".format(seeds[0])

 

{{out}}

 

=={{header|Perl}}==

my @a;

$a[$_]++ for split '', shift;

 

print "longest ($mlen): @mlist\n";

{{out}}

<pre>longest (21): 9009 9090 9900

=={{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>

<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"}

=={{header|PicoLisp}}==

Using 'las' from [[Look-and-say sequence#PicoLisp]]:

(let L (mapcar format (chop Seed))

(make

(println 'Values: (cdr Res))

(println 'Iterations: (car Res))

Output:

<pre>Values: (9009 9090 9900)

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):

for n in starts:

print()

 

;Output:

 

=={{header|q}}==

sumsay:ls desc@ / summarize & say

 

rpt["Seeds"]" "sv string raze seeds where its=top / all forms of top seed/s

rpt["Iterations"]string top

{{out}}

<pre>

 

=={{header|Racket}}==

#lang racket

 

(printf "Numbers: ~a\nLength: ~a\n" (string-join nums ", ") len)

(for ([n seq]) (printf " ~a\n" n))

{{out}}

<pre>

{{Works with|rakudo|2018.03}}

 

my $longest = 0;

my %seen;

}

return @perms;

 

{{out}}

The REXX language supports &nbsp; '''sparse''' &nbsp; (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.*/

do k=1 for words(q); say word(q, k)

end /*k*/

{{out|output|text=&nbsp; when using the default inputs:}}

<br>(Shown at five-sixths size.)

=={{header|Ruby}}==

Cached for performance

def selfReferentialSequence_cached(n, seen = [])

return $cache[n] if $cache.include? n

selfReferentialSequence_cached(max_vals[0]).each_with_index do |val, idx|

puts "%2d %d" % [idx + 1, val]

output

<pre>values: [9009, 9090, 9900]

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

dTrec(Vector[(Int, Int)](), num)

}

 

{{out}}

=={{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} {

puts "\t$seed"

}

Output:

<pre>

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))

(put-line `Iterations: @(length result)`)

(put-line)

 

{{out}}

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`))

(when (> l len) (set len l) (set nums nil))

(when (= l len) (push x nums))))

 

{{out}}

==={{trans|Racket}}===

 

(defmacro for-accum (accum-var-inits each-vars . body)

(let ((accum-vars [mapcar first accum-var-inits])

*seq))))

(put-line `Numbers: @{nums ", "}\nLength: @len`)

 

{{out}}

{{libheader|Wren-seq}}

{{libheader|Wren-math}}

 

var limit = 1e6

System.print()

}

 

{{out}}

 

=={{header|zkl}}==

 

fcn lookAndJustSaying(seed){ // numeric String --> numeric String

.filter(fcn(s){ s[0]!="0" }) : Utils.Helpers.listUnique(_);

println(max," iterations for ",zs.concat(", "));

Ignoring permutations cut run time from 4 min to 9 sec.

{{out}}