Hofstadter Figure-Figure sequences: Difference between revisions
Added Easylang
m (→{{header|FreeBASIC}}: -fix) |
(Added Easylang) |
||
| (13 intermediate revisions by 7 users not shown) | |||
Line 32:
{{trans|Python}}
<
V cS = [2]
Line 64:
print(‘All Integers 1..1000 found OK’)
E
print(‘All Integers 1..1000 NOT found only once: ERROR’)</
{{out}}
Line 72:
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="abc">PUT {[1]: 1} IN r.list
PUT {[1]: 2} IN s.list
HOW TO EXTEND R TO n:
SHARE r.list, s.list
WHILE n > #r.list:
PUT r.list[#r.list] + s.list[#r.list] IN next.r
FOR i IN {s.list[#s.list]+1 .. next.r-1}:
PUT i IN s.list[#s.list+1]
PUT next.r IN r.list[#r.list+1]
PUT next.r + 1 IN s.list[#s.list+1]
HOW TO EXTEND S TO n:
SHARE r.list, s.list
WHILE n > #s.list: EXTEND R TO #r.list + 1
HOW TO RETURN ffr n:
SHARE r.list
IF n > #r.list: EXTEND R TO n
RETURN r.list[n]
HOW TO RETURN ffs n:
SHARE s.list
IF n > #s.list: EXTEND S TO n
RETURN s.list[n]
WRITE "R[1..10]:"
FOR i IN {1..10}: WRITE ffr i
WRITE /
PUT {} IN thousand
FOR i IN {1..40}: INSERT ffr i IN thousand
FOR i IN {1..960}: INSERT ffs i IN thousand
IF thousand = {1..1000}:
WRITE "R[1..40] + S[1..960] = [1..1000]"/</syntaxhighlight>
{{out}}
<pre>R[1..10]: 1 3 7 12 18 26 35 45 56 69
R[1..40] + S[1..960] = [1..1000]</pre>
=={{header|Ada}}==
Specifying a package providing the functions FFR and FFS:
<
function FFR(P: Positive) return Positive;
Line 80 ⟶ 119:
function FFS(P: Positive) return Positive;
end Hofstadter_Figure_Figure;</
The implementation of the package internally uses functions which generate an array of Figures or Spaces:
<
type Positive_Array is array (Positive range <>) of Positive;
Line 133 ⟶ 172:
end FFS;
end Hofstadter_Figure_Figure;</
Finally, a test program for the package, solving the task at hand:
<
procedure Test_HSS is
Line 175 ⟶ 214:
exception
when Program_Error => Ada.Text_IO.Put_Line("Test Failed"); raise;
end Test_HSS;</
The output of the test program:
<syntaxhighlight lang="text"> 1 3 7 12 18 26 35 45 56 69
Test Passed: No overlap between FFR(I) and FFS(J)</
=={{header|APL}}==
{{works with|Dyalog APL}}
<
:Field Private Shared RBuf←,1
∇r←ffr n
Line 207 ⟶ 246:
:EndIf
∇
:EndClass</
{{out}}
Line 216 ⟶ 255:
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">R(n){
if n=1
return 1
Line 234 ⟶ 273:
if !(ObjR[A_Index]||ObjS[A_Index])
return A_index
}</
Examples:<
MsgBox, 262144, , % "R(" A_Index ") = " R(A_Index) "`nS(" A_Index ") = " S(A_Index)</
Outputs:<pre>R(1) = 1, 3, 7, 12, 18, 26, 35,...
S(1) = 2, 4, 5, 6, 8, 9, 10,...</pre>
=={{header|AWK}}==
<
#
# R(1) = 1; S(1) = 2;
Line 329 ⟶ 368:
}
return S[ n ];
} # ffs</
{{out}}
<pre>
Line 338 ⟶ 377:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
FOR i% = 1 TO 10 : PRINT ;FNffr(i%) " "; : NEXT : PRINT
PRINT "First 10 values of S:"
Line 390 ⟶ 429:
IF R% <= 2*N% V%?R% = 1
NEXT I%
= S%</
<pre>
First 10 values of R:
Line 401 ⟶ 440:
=={{header|C}}==
<
#include <stdlib.h>
Line 484 ⟶ 523:
puts("\nfirst 1000 ok");
return 0;
}</
=={{header|C sharp|C#}}==
Creates an IEnumerable for R and S and uses those to complete the task
<
using System.Collections.Generic;
using System.Linq;
Line 572 ⟶ 611:
}
}
</syntaxhighlight>
Output:
<pre>1
Line 589 ⟶ 628:
{{works with|gcc}}
{{works with|C++|11, 14, 17}}
<
#include <iostream>
#include <set>
Line 654 ⟶ 693:
return 0;
}</
{{out}}
<
R(40):
1 3 7 12 18 26 35 45 56 69 83 98 114 131 150 170 191 213 236 260
Line 666 ⟶ 705:
49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 68 70
71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91
92 93 94 95 96 97 99 100 101 102 103 104 105 106 107 108 109 110 111 112</
=={{header|CLU}}==
<syntaxhighlight lang="clu">figfig = cluster is ffr, ffs
rep = null
ai = array[int]
own R: ai := ai$[1]
own S: ai := ai$[2]
% Extend R and S until R(n) is known
extend = proc (n: int)
while n > ai$high(R) do
next: int := ai$top(R) + S[ai$high(R)]
ai$addh(R, next)
while ai$top(S) < next-1 do
ai$addh(S, ai$top(S)+1)
end
ai$addh(S, next+1)
end
end extend
ffr = proc (n: int) returns (int)
extend(n)
return(R[n])
end ffr
ffs = proc (n: int) returns (int)
while n > ai$high(S) do
extend(ai$high(R) + 1)
end
return(S[n])
end ffs
end figfig
start_up = proc ()
ai = array[int]
po: stream := stream$primary_output()
% Print R[1..10]
stream$puts(po, "R[1..10] =")
for i: int in int$from_to(1,10) do
stream$puts(po, " " || int$unparse(figfig$ffr(i)))
end
stream$putl(po, "")
% Count the occurrences of 1..1000 in R[1..40] and S[1..960]
occur: ai := ai$fill(1, 1000, 0)
for i: int in int$from_to(1, 40) do
occur[figfig$ffr(i)] := occur[figfig$ffr(i)] + 1
end
for i: int in int$from_to(1, 960) do
occur[figfig$ffs(i)] := occur[figfig$ffs(i)] + 1
end
% See if they all occur exactly once
begin
for i: int in int$from_to(1, 1000) do
if occur[i] ~= 1 then exit wrong(i) end
end
stream$putl(po,
"All numbers 1..1000 occur exactly once in R[1..40] U S[1..960].")
end except when wrong(i: int):
stream$putl(po, "Error: " ||
int$unparse(i) || " occurs " || int$unparse(occur[i]) || " times.")
end
end start_up</syntaxhighlight>
{{out}}
<pre>R[1..10] = 1 3 7 12 18 26 35 45 56 69
All numbers 1..1000 occur exactly once in R[1..40] U S[1..960].</pre>
=={{header|CoffeeScript}}==
{{trans|Ruby}}
<
S = [ null, 2 ]
Line 695 ⟶ 802:
if int_array[i - 1] != i
throw 'Something\'s wrong!'
console.log '1000 integer check ok.'</
{{out}}
As JavaScript.
=={{header|Common Lisp}}==
<
(flet ((seq (i) (make-array 1 :element-type 'integer
:initial-element i
Line 733 ⟶ 840:
(take #'seq-s 960))
#'<))
(princ "Ok")</
{{out}}
<pre>First of R: (1 3 7 12 18 26 35 45 56 69)
Line 739 ⟶ 846:
=={{header|Cowgol}}==
<
include "strings.coh";
include "malloc.coh";
Line 881 ⟶ 988:
if ok != 0 then
print("All numbers 1 .. 1000 found!\n");
end if;</
{{out}}
Line 891 ⟶ 998:
=={{header|D}}==
{{trans|Go}}
<
nothrow static this() {
Line 921 ⟶ 1,028:
auto t = iota(1, 41).map!ffr.chain(iota(1, 961).map!ffs);
t.array.sort().equal(iota(1, 1001)).writeln;
}</
{{out}}
<pre>[1, 3, 7, 12, 18, 26, 35, 45, 56, 69]
Line 928 ⟶ 1,035:
{{trans|Python}}
(Same output)
<
struct ffr {
Line 978 ⟶ 1,085:
auto t = iota(1, 41).map!ffr.chain(iota(1, 961).map!ffs);
t.array.sort().equal(iota(1, 1001)).writeln;
}</
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
global rs[] ss[] .
procdecl RS_append . .
func R n .
while n > len rs[]
RS_append
.
return rs[n]
.
func S n .
while n > len ss[]
RS_append
.
return ss[n]
.
proc RS_append . .
n = len rs[]
r = R n + S n
s = S len ss[]
rs[] &= r
repeat
s += 1
until s = r
ss[] &= s
.
ss[] &= r + 1
.
rs[] = [ 1 ]
ss[] = [ 2 ]
write "R(1 .. 10): "
for i to 10
write R i & " "
.
print ""
len seen[] 1000
for i to 40
seen[R i] = 1
.
for i to 960
seen[S i] = 1
.
for i to 1000
if seen[i] = 0
print i & " not seen"
return
.
.
print "first 1000 ok"
</syntaxhighlight>
{{out}}
<pre>
R(1 .. 10): 1 3 7 12 18 26 35 45 56 69
first 1000 ok
</pre>
=={{header|EchoLisp}}==
<
(+ (FFR (1- n)) (FFS (1- n))))
Line 992 ⟶ 1,156:
(remember 'FFR #(0 1)) ;; init cache
(remember 'FFS #(0 2))
</syntaxhighlight>
{{out}}
<
(define-macro m-range [a .. b] (range a (1+ b)))
Line 1,002 ⟶ 1,166:
;; checking
(equal? [1 .. 1000] (list-sort < (append (map FFR [1 .. 40]) (map FFS [1 .. 960]))))
→ #t</
=={{header|Euler Math Toolbox}}==
<syntaxhighlight lang="euler math toolbox">
>function RSstep (r,s) ...
$ n=cols(r);
Line 1,026 ⟶ 1,190:
>all(sort(r[1:40]|s[1:960])==(1:1000))
1
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
===The function===
<
// Populate R and S with values of Hofstadter Figure Figure sequence. Nigel Galloway: August 28th., 2020
let fF q=let R,S=Array.zeroCreate<int>q,Array.zeroCreate<int>q
Line 1,039 ⟶ 1,203:
|i->S.[n]<-i+1; fN (n+1) (g+1)
fN 1 1
</syntaxhighlight>
===The Tasks===
<
let ffr,ffs=fF 960
ffr|>Seq.take 10|>Seq.iter(printf "%d "); printfn ""
let N=Array.concat [|ffs;(Array.take 40 ffr)|] in printfn "Unique values=%d Minimum value=%d Maximum Value=%d" ((Array.distinct N).Length)(Array.min N)(Array.max N)
</syntaxhighlight>
{{out}}
<pre>
Line 1,054 ⟶ 1,218:
===Unbounded n?===
n is bounded in this implementation because it is an signed 32 integer. Within such limit the 10 millionth value will have to be sufficiently unbounded. It can be found in 43 thousandths of sec.
<
let ffr,ffs=fF 10000000
printfn "%d\n%d (Array.last ffr) (Array.last ffs)
</syntaxhighlight>
1584961838
10004416
Line 1,063 ⟶ 1,227:
=={{header|Factor}}==
We keep lists S and R, and increment them when necessary.
<
SYMBOL: R V{ 1 } R set
Line 1,083 ⟶ 1,247:
: ffr ( n -- R(n) )
dup R get length - inc-SR
1 - R get nth ;</
<
{ 1 3 7 12 18 26 35 45 56 69 }
( scratchpad ) 40 iota [ 1 + ffr ] map 960 iota [ 1 + ffs ] map append 1000 iota 1 v+n set= .
t</
=={{header|FreeBASIC}}==
{{trans|BBC BASIC}}
<
if n = 1 then return 1
dim as integer i, j, r=1, s=1, v(1 to 2*n+1)
Line 1,141 ⟶ 1,305:
next i
if failed then print "Oh no!" else print "All integers from 1 to 1000 accounted for"</
{{out}}<pre>
R S
Line 1,159 ⟶ 1,323:
=={{header|Go}}==
<
import "fmt"
Line 1,214 ⟶ 1,378:
}
fmt.Println("task 4: PASS")
}</
{{out}}
<pre>
Line 1,230 ⟶ 1,394:
The following defines two mutually recursive generators without caching results. Each generator will end up dragging a tree of closures behind it, but due to the odd nature of the two series' growth pattern, it's still a heck of a lot faster than the above method when producing either series in sequence.
<
import "fmt"
Line 1,278 ⟶ 1,442:
}
fmt.Println(sum)
}</
=={{header|Haskell}}==
<
-- Functions by Reinhard Zumkeller
Line 1,304 ⟶ 1,468:
print $ ffr <$> [1 .. 10]
let i1000 = sort (fmap ffr [1 .. 40] ++ fmap ffs [1 .. 960])
print (i1000 == [1 .. 1000])</
Output:
<pre>[1,3,7,12,18,26,35,45,56,69]
Line 1,310 ⟶ 1,474:
Defining R and S literally:
<
r :: [Int]
Line 1,328 ⟶ 1,492:
print (take 10 s)
putStr "test 1000: "
print $ [1 .. 1000] == sort (take 40 r ++ take 960 s)</
output:
<pre>
Line 1,337 ⟶ 1,501:
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 1,395 ⟶ 1,559:
}
}
end</
{{libheader|Icon Programming Library}}
Line 1,416 ⟶ 1,580:
=={{header|J}}==
<
S=: 0 2 4
FF=: 3 :0
Line 1,426 ⟶ 1,590:
)
ffr=: { 0 {:: FF@(>./@,)
ffs=: { 1 {:: FF@(0,>./@,)</
Required examples:
<
1 3 7 12 18 26 35 45 56 69
(1+i.1000) -: /:~ (ffr 1+i.40), ffs 1+i.960
1</
=={{header|Java}}==
Line 1,439 ⟶ 1,603:
'''Code:'''
<
class Hofstadter
Line 1,494 ⟶ 1,658:
System.out.println("Done");
}
}</
'''Output:'''
Line 1,503 ⟶ 1,667:
=={{header|JavaScript}}==
{{trans|Ruby}}
<
var S = [null, 2];
Line 1,549 ⟶ 1,713:
throw "Something's wrong!"
} else { console.log("1000 integer check ok."); }
}</
Output:
<pre>R(1) = 1
Line 1,573 ⟶ 1,737:
to accomplish the specific tasks.
<
# input: {r,s}
Line 1,603 ⟶ 1,767:
| (.r[1:41] + .s[1:961] | sort) == [range(1;1001)] ) ;
task1(10), task2</
{{out}}
<pre>
Line 1,617 ⟶ 1,781:
'''Functions'''
<syntaxhighlight lang="julia">
type FigureFigure{T<:Integer}
r::Array{T,1}
Line 1,679 ⟶ 1,843:
end
end
</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="julia">
NR = 40
NS = 960
Line 1,723 ⟶ 1,887:
end
println("cover the entire interval.")
</syntaxhighlight>
{{out}}
Line 1,734 ⟶ 1,898:
</pre>
=={{header|Kotlin}}
Translated from Java.
<
fun ffs(n: Int) = get(0, n)[n - 1]
Line 1,770 ⟶ 1,934:
indices.forEach { println("Integer $it either in both or neither set") }
println("Done")
}</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Line 1,781 ⟶ 1,945:
2. No maximum value for n should be assumed.
<syntaxhighlight lang="mathematica">
ffr[j_] := Module[{R = {1}, S = 2, k = 1},
Do[While[Position[R, S] != {}, S++]; k = k + S; S++;
Line 1,787 ⟶ 1,951:
ffs[j_] := Differences[ffr[j + 1]]
</syntaxhighlight>
3. Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
<syntaxhighlight lang="mathematica">
ffr[10]
(* out *)
{1, 3, 7, 12, 18, 26, 35, 45, 56, 69}
</syntaxhighlight>
4. Calculate and show that the first 40 values of ffr plus the first 960 values of ffs include all the integers from 1 to 1000 exactly once.
<syntaxhighlight lang="mathematica">
t = Sort[Join[ffr[40], ffs[960]]];
Line 1,807 ⟶ 1,971:
(* out *)
True
</syntaxhighlight>
=={{header|MATLAB}} / {{header|Octave}}==
Line 1,814 ⟶ 1,978:
2. No maximum value for n should be assumed.
<
t = [1,0];
T = 1;
Line 1,837 ⟶ 2,001:
printf('Sequence S:\n'); disp(S);
end;
end; </
3. Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
Line 1,858 ⟶ 2,022:
=={{header|Nim}}==
<
var cs = @[2]
Line 1,890 ⟶ 2,054:
if all: echo "All Integers 1..1000 found OK"
else: echo "All Integers 1..1000 NOT found only once: ERROR"</
Output:
<pre>/home/deen/git/nim-unsorted/hofstadter
Line 1,897 ⟶ 2,061:
=={{header|Oforth}}==
<
ListBuffer new 1 over add R put
Line 1,917 ⟶ 2,081:
: ffs(n)
while ( S at size n < ) [ buildnext ]
n S at at ;</
Output :
Line 1,934 ⟶ 2,098:
Then we go through the first 1000 outputs, mark those which are seen, then check if all values in the range one through one thousand were seen.
<
use strict;
use warnings;
Line 1,969 ⟶ 2,133:
print "These were duplicated: @dupped\n";
}
</syntaxhighlight>
=={{header|Phix}}==
Initialising such that length(S)>length(F) simplified things significantly.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">F</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">S</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}</span>
Line 2,001 ⟶ 2,166:
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ffr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (or collect one by one)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ffr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">40</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (not actually needed)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ffs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">960</span><span style="color: #0000FF;">)</span>
Line 2,009 ⟶ 2,174:
<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;">"some error!\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
<pre>
test passed
</pre>
=={{header|PicoLisp}}==
<
(de ffr (N)
Line 2,033 ⟶ 2,198:
(inc 'S)
(inc '*RNext) )
S ) ) ) )</
Test:
<
-> (1 3 7 12 18 26 35 45 56 69)
Line 2,041 ⟶ 2,206:
(range 1 1000)
(sort (conc (mapcar ffr (range 1 40)) (mapcar ffs (range 1 960)))) )
-> T</
=={{header|PL/I}}==
<
declare n fixed binary (31);
declare v(2*n+1) bit(1);
Line 2,066 ⟶ 2,231:
end;
return (r);
end ffr;</
Output:
<pre>
Line 2,074 ⟶ 2,239:
602 640 679 719 760 802 845 889 935 982
</pre>
<
declare n fixed binary (31);
declare v(2*n+1) bit(1);
Line 2,096 ⟶ 2,261:
end;
return (s);
end ffs;</
Output of first 960 values:
<pre>
Line 2,106 ⟶ 2,271:
</pre>
Verification using the above procedures:
<
Dcl t(1000) Bit(1) Init((1000)(1)'0'b);
put skip list ('Verification that the first 40 FFR numbers and the first');
Line 2,121 ⟶ 2,286:
end;
if all(t = '1'b) then put skip list ('passed test');
</syntaxhighlight>
Output:
<pre>
Line 2,133 ⟶ 2,298:
CHR is a programming language created by '''Professor Thom Frühwirth'''.<br>
Works with SWI-Prolog and module '''chr''' written by '''Tom Schrijvers''' and '''Jan Wielemaker'''
<
:- chr_constraint ffr/2, ffs/2, hofstadter/1,hofstadter/2.
Line 2,159 ⟶ 2,324:
hofstadter(N), ffr(N1, _R), ffs(N1, _S) ==> N1 < N, N2 is N1 +1 | ffr(N2,_), ffs(N2,_).
</syntaxhighlight>
Output for first task :
<pre> ?- hofstadter(10), bagof(ffr(X,Y), find_chr_constraint(ffr(X,Y)), L).
Line 2,187 ⟶ 2,352:
Code for the second task
<
hofstadter(960),
% fetch the values of ffr
Line 2,201 ⟶ 2,366:
% to remove all pending constraints
fail.
</syntaxhighlight>
Output for second task
<pre> ?- hofstadter.
Line 2,209 ⟶ 2,374:
=={{header|Python}}==
<
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
Line 2,254 ⟶ 2,419:
print("All Integers 1..1000 found OK")
else:
print("All Integers 1..1000 NOT found only once: ERROR")</
;Output:
Line 2,261 ⟶ 2,426:
===Alternative===
<
cS = [2]
Line 2,289 ⟶ 2,454:
# the fact that we got here without a key error
print("Ok")</
Ok</
===Using cyclic iterators===
{{trans|Haskell}}
Defining R and S as mutually recursive generators. Follows directly from the definition of the R and S sequences.
<
def R():
Line 2,320 ⟶ 2,485:
# perf test case
# print sum(lst(R, 10000000))</
{{out}}
<pre>R: [1, 3, 7, 12, 18, 26, 35, 45, 56, 69]
Line 2,326 ⟶ 2,491:
True
</pre>
=={{header|Quackery}}==
<code>from</code>, <code>index</code>, and <code>end</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
As with the Phix solution, initialising to the first few elements simplified things significantly.
<syntaxhighlight lang="Quackery">
[ ' [ 1 3 7 ]
' [ 2 4 5 6 ] ] is initialise ( --> r s )
[ over size 1 -
over swap peek
dip [ over -1 peek ]
+ swap dip join
over -2 split nip do
temp put
1 + from
[ temp share
index = iff
end done
index join ]
temp release ] is extend ( r s --> r s )
[ temp put
[ over size
temp share < while
extend again ]
over
temp take 1 - peek ] is ffr ( r s n --> r s n )
[ temp put
[ dup size
temp share < while
extend again ]
dup
temp take 1 - peek ] is ffs ( r s n --> r s n )
initialise
say "R(1)..R(10): "
10 times
[ i^ 1+ ffr echo sp ]
cr cr
960 ffs drop
960 split drop
dip [ 40 split drop ]
join sort
[] 1000 times
[ i^ 1+ join ]
!=
say "All integers from 1 to 1000"
if say " not"
say " found once and only once."</syntaxhighlight>
{{out}}
<pre>R(1)..R(10): 1 3 7 12 18 26 35 45 56 69
All integers from 1 to 1000 found once and only once.</pre>
=={{header|R}}==
Global variables aren't idiomatic R, but this is otherwise an ideal task for the language. Comments aside, this is easily one of the shortest solutions on this page. This is mostly due to how R treats most things as a vector. For example, rValues starts out as the number 1, but repeatedly has new values appended to it without much ceremony.
<
sValues <- 2
ffr <- function(n)
Line 2,358 ⟶ 2,582:
This gives an output of length 960, which clearly cannot contain 1000 different values.
#Presumably, the task wants us to append rValues[1:40] and sValues[1:960].
print(table(c(rValues[1:40], sValues[1:960])))</
{{out}}
<pre>> print(rValues)
Line 2,476 ⟶ 2,700:
We store the values of r and s in hash-tables. The first values are added by hand. The procedure extend-r-s! adds more values.
<
(define r-cache (make-hash '((1 . 1) (2 . 3) (3 . 7))))
Line 2,489 ⟶ 2,713:
(define offset (- s-count last-r))
(for ([val (in-range (add1 last-r) new-r)])
(hash-set! s-cache (+ val offset) val)))</
The functions ffr and ffs simply retrieve the value from the hash table if it exist, or call extend-r-s until they are long enought.
<
(hash-ref r-cache n (lambda () (extend-r-s!) (ffr n))))
(define (ffs n)
(hash-ref s-cache n (lambda () (extend-r-s!) (ffs n))))</
Tests:
<
(displayln (map ffs (list 1 2 3 4 5 6 7 8 9 10)))
Line 2,512 ⟶ 2,736:
i))
"Test passed"
"Test failed"))</
'''Sample Output:'''
Line 2,522 ⟶ 2,746:
(formerly Perl 6)
{{works with|Rakudo|2018.03}}
<syntaxhighlight lang="raku"
my %s = 1 => 2;
Line 2,532 ⟶ 2,756:
say @ffr[^10];
say "Rawks!" if 1...1000 eqv sort |@ffr[^40], |@ffs[^960];</
Output:
<pre>
Line 2,546 ⟶ 2,770:
This REXX version is over '''15,000%''' faster than REXX version 2.
<
parse arg x top bot . /*obtain optional arguments from the CL*/
if x=='' | x=="," then x= 10 /*Not specified? Then use the default.*/
Line 2,588 ⟶ 2,812:
return s.n /*return S.n value to the invoker. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
ser: errs=errs+1; say '***error***' arg(1); return</
To see the talk section about this REXX program's timings, click here: [http://rosettacode.org/wiki/Talk:Hofstadter_Figure-Figure_sequences#timings_for_the_REXX_solutions timings for the REXX solutions]. <br>
Line 2,608 ⟶ 2,832:
===Version 2 from PL/I ===
<
* 21.11.2012 Walter Pachl transcribed from PL/I
**********************************************************************/
Line 2,679 ⟶ 2,903:
if r <= 2*n then v.r = 1
end
return s</
{{out}}
<pre>Verification that the first 40 FFR numbers and the first
Line 2,694 ⟶ 2,918:
=={{header|Ring}}==
<
# Project : Hofstadter Figure-Figure sequences
Line 2,725 ⟶ 2,949:
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
Output:
<pre>
Line 2,732 ⟶ 2,956:
First 10 values of S:
2 4 5 6 8 9 10 11 13 14
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ { 1 3 } 'R' STO { 2 } 'S' STO
≫ ''''INITFF'''' STO
≪
S DUP SIZE GET
'''DO''' 1 + '''UNTIL''' R OVER POS NOT '''END'''
S OVER + 'S' STO
R DUP SIZE GET + R SWAP + 'R' STO
≫ ''''NXTFF'''' STO
≪
'''WHILE''' R SIZE OVER < '''REPEAT NXTFF END'''
R SWAP GET
≫ ''''FFR'''' STO
≪
'''WHILE''' S SIZE OVER < '''REPEAT NXTFF END'''
S SWAP GET
≫ ''''FFS'''' STO
≪ '''INITFF'''
40 '''FFR''' DROP R
960 '''FFS''' DROP S +
1 SF 1 1000 '''FOR''' j
'''IF''' DUP j POS NOT '''THEN''' 1 CF '''END NEXT''' DROP
1 FS? "Passed" "Failed" IFTE
≫ ''''TASK4'''' STO
|
'''INITFF''' ''( -- ) ''
Initialize R(1..2) and S(1)
'''NXTFF''' ''( -- ) ''
n = last stored item of S()
n += 1 until n not in R()
append n to S()
append (n + last item of R()) to R()
'''FFR''' ''( n -- R(n) ) ''
if R(n) not stored, develop R()
Get R(n)
'''FFS''' ''( n -- S(n) ) ''
if S(n) not stored, develop S()
Get S(n)
'''TASK4''' ''( -- "Result" ) ''
Get R(40) and put R(1..40) in stack
Get S(960), append S(1..960) to R(1..40)
set flag ; for j=1 to 1000
if j not in the merged list then clear flag
Flag is still set iff all 1..1000 were in list once
|}
{{in}}
<pre>
10 FFR DROP R
TASK4
</pre>
{{out}}
<pre>
2: { 1 3 7 12 18 26 35 45 56 69 }
1: "Passed"
</pre>
=={{header|Ruby}}==
{{trans|Tcl}}
<
$s = [nil, 2]
Line 2,777 ⟶ 3,075:
assert_equal(rs_values, Set.new( 1..1000 ))
end
end</
outputs
Line 2,788 ⟶ 3,086:
===Using cyclic iterators===
{{trans|Python}}
<
y << n = 1
S.each{|s_val| y << n += s_val}
Line 2,807 ⟶ 3,105:
p S.take(10)
p (R.take(40)+ S.take(960)).sort == (1..1000).to_a
</syntaxhighlight>
{{out}}
<pre>
Line 2,816 ⟶ 3,114:
=={{header|Rust}}==
<
use std::collections::HashMap;
Line 2,892 ⟶ 3,190:
assert_eq!(f1000, s960, "Does NOT match");
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,909 ⟶ 3,207:
=={{header|Scala}}==
{{trans|Go}}
<
import scala.collection.mutable.ListBuffer
Line 2,935 ⟶ 3,233:
(1 to 10).map(i=>(i,ffr(i))).foreach(t=>println("r("+t._1+"): "+t._2))
println((1 to 1000).toList.filterNot(((1 to 40).map(ffr(_))++(1 to 960).map(ffs(_))).contains)==List())
}</
Output:
<pre>r(1): 1
Line 2,948 ⟶ 3,246:
r(10): 69
true</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program figure_figure;
init R := [1], S := [2];
print("R(1..10):", [ffr(n) : n in [1..10]]);
print("R(1..40) + S(1..960) = {1..1000}:",
{ffr(n) : n in {1..40}} + {ffs(n) : n in {1..960}} = {1..1000});
proc ffr(n);
loop while n > #R do
nextR := R(#R) + S(#R);
S +:= [S(#S)+1 .. nextR-1];
R with:= nextR;
S with:= nextR + 1;
end loop;
return R(n);
end proc;
proc ffs(n);
loop while n > #S do
ffr(#R + 1);
end loop;
return S(n);
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>R(1..10): [1 3 7 12 18 26 35 45 56 69]
R(1..40) + S(1..960) = {1..1000}: #T</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<
var s = [nil, 2]
Line 2,985 ⟶ 3,312:
say "These were missed: #{missed}"
say "These were duplicated: #{dupped}"
}</
{{out}}
<pre>
Line 3,007 ⟶ 3,334:
=={{header|Tcl}}==
{{tcllib|struct::set}}
<
package require struct::set
Line 3,049 ⟶ 3,376:
}
puts "set sizes: [struct::set size $numsInSeq] vs [struct::set size $numsRS]"
puts "set equality: [expr {[struct::set equal $numsInSeq $numsRS]?{yes}:{no}}]"</
Output:
<pre>
Line 3,069 ⟶ 3,396:
=={{header|uBasic/4tH}}==
Note that uBasic/4tH has ''no'' dynamic memory facilities and only ''one single array'' of 256 elements. So the only way to cram over a 1000 values there is to use a bitmap. This bitmap consists of an '''R''' range and an '''S''' range. In each range, a bit represents a positional value (bit 0 = "1", bit 1 = "2", etc.). The '''R'''(x) and '''S'''(x) functions simply count the number of bits set they encountered. To determine whether all integers between 1 and 1000 are complementary, both ranges are ''XOR''ed, which would result in a value other than 2<sup>31</sup>-1 if there were any discrepancies present. An extra check determines if there are exactly 40 '''R''' values.
<syntaxhighlight lang="text">Proc _SetBitR(1) ' Set the first R value
Proc _SetBitS(2) ' Set the first S value
Line 3,169 ⟶ 3,496:
_GetBitS Param(1) ' Return bit n-1 in S-bitmap
a@ = a@ - 1
Return (AND(@(64+a@/31), SHL(1,a@%31))#0)</
{{out}}
<pre>Creating bitmap, wait..
Line 3,213 ⟶ 3,540:
=={{header|VBA}}==
<
Dim R As New Collection
Dim S As New Collection
Line 3,271 ⟶ 3,598:
Debug.Print "The first 40 values of ffr plus the first 960 values of ffs "
Debug.Print "include all the integers from 1 to 1000 exactly once is "; Format(x.Count = 0)
End Sub</
<pre>The first ten values of R are:
1 3 7 12 18 26 35 45 56 69
Line 3,278 ⟶ 3,605:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
'Initialize the r and the s arrays.
Set r = CreateObject("System.Collections.ArrayList")
Line 3,349 ⟶ 3,676:
WScript.StdOut.WriteLine
End If
</syntaxhighlight>
{{Out}}
Line 3,361 ⟶ 3,688:
=={{header|Wren}}==
{{trans|Go}}
<
var s = [0, 2]
Line 3,390 ⟶ 3,717:
var allPresent = present.skip(1).all { |i| i == true }
System.print("\nThe first 40 values of ffr plus the first 960 values of ffs")
System.print("includes all integers from 1 to 1000 exactly once is %(allPresent).")</
{{out}}
Line 3,402 ⟶ 3,729:
=={{header|zkl}}==
<
var n=0, Rs=L(0,1), S=2;
if(True==reset){ n=0; Rs=L(0,1); S=2; return(); }
Line 3,413 ⟶ 3,740:
return(n+=1,R,S);
}
fcn ffrs(n) { genRS(True); do(n){ n=genRS() } n[1,2] } //-->( R(n),S(n) )</
{{out}}
<pre>
Line 3,419 ⟶ 3,746:
L(1,3,7,12,18,26,35,45,56,69)
</pre>
<
sink:=(0).pump(40,List, 'wrap(ns){ T(Void.Write,Void.Write,genRS()[1,*]) });
sink= (0).pump(960-40,sink,'wrap(ns){ T(Void.Write,genRS()[2]) });
(sink.sort()==[1..1000].pump(List)) // [1..n].pump(List)-->(1,2,3...)
.println("<-- should be True");</
{{out}}
<pre>
| |||