Hofstadter Figure-Figure sequences: Difference between revisions
Content added Content deleted
m (→version 1: added/changed whitespace and comments and the link, changed a variable's name.) |
(rearranges in order of the language.) |
||
Line 218: | Line 218: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|C}}== |
||
<lang c>#include <stdio.h> |
|||
<lang lisp>;;; equally doable with a list |
|||
#include <stdlib.h> |
|||
(flet ((seq (i) (make-array 1 :element-type 'integer |
|||
:initial-element i |
|||
:fill-pointer 1 |
|||
:adjustable t))) |
|||
(let ((rr (seq 1)) (ss (seq 2))) |
|||
(labels ((extend-r () |
|||
(let* ((l (1- (length rr))) |
|||
(r (+ (aref rr l) (aref ss l))) |
|||
(s (elt ss (1- (length ss))))) |
|||
(vector-push-extend r rr) |
|||
(loop while (<= s r) do |
|||
(if (/= (incf s) r) |
|||
(vector-push-extend s ss)))))) |
|||
(defun seq-r (n) |
|||
(loop while (> n (length rr)) do (extend-r)) |
|||
(elt rr (1- n))) |
|||
// simple extensible array stuff |
|||
(defun seq-s (n) |
|||
typedef unsigned long long xint; |
|||
(loop while (> n (length ss)) do (extend-r)) |
|||
(elt ss (1- n)))))) |
|||
typedef struct { |
|||
(defun take (f n) |
|||
size_t len, alloc; |
|||
(loop for x from 1 to n collect (funcall f x))) |
|||
xint *buf; |
|||
} xarray; |
|||
xarray rs, ss; |
|||
(format t "First of R: ~a~%" (take #'seq-r 10)) |
|||
void setsize(xarray *a, size_t size) |
|||
(mapl (lambda (l) (if (and (cdr l) |
|||
{ |
|||
(/= (1+ (car l)) (cadr l))) |
|||
size_t n = a->alloc; |
|||
(error "not in sequence"))) |
|||
if (!n) n = 1; |
|||
(sort (append (take #'seq-r 40) |
|||
(take #'seq-s 960)) |
|||
while (n < size) n <<= 1; |
|||
#'<)) |
|||
if (a->alloc < n) { |
|||
(princ "Ok")</lang>output<lang>First of R: (1 3 7 12 18 26 35 45 56 69) |
|||
a->buf = realloc(a->buf, sizeof(xint) * n); |
|||
Ok</lang> |
|||
if (!a->buf) abort(); |
|||
a->alloc = n; |
|||
} |
|||
} |
|||
void push(xarray *a, xint v) |
|||
{ |
|||
while (a->alloc <= a->len) |
|||
setsize(a, a->alloc * 2); |
|||
a->buf[a->len++] = v; |
|||
} |
|||
// sequence stuff |
|||
void RS_append(void); |
|||
xint R(int n) |
|||
{ |
|||
while (n > rs.len) RS_append(); |
|||
return rs.buf[n - 1]; |
|||
} |
|||
xint S(int n) |
|||
{ |
|||
while (n > ss.len) RS_append(); |
|||
return ss.buf[n - 1]; |
|||
} |
|||
void RS_append() |
|||
{ |
|||
int n = rs.len; |
|||
xint r = R(n) + S(n); |
|||
xint s = S(ss.len); |
|||
push(&rs, r); |
|||
while (++s < r) push(&ss, s); |
|||
push(&ss, r + 1); // pesky 3 |
|||
} |
|||
int main(void) |
|||
{ |
|||
push(&rs, 1); |
|||
push(&ss, 2); |
|||
int i; |
|||
printf("R(1 .. 10):"); |
|||
for (i = 1; i <= 10; i++) |
|||
printf(" %llu", R(i)); |
|||
char seen[1001] = { 0 }; |
|||
for (i = 1; i <= 40; i++) seen[ R(i) ] = 1; |
|||
for (i = 1; i <= 960; i++) seen[ S(i) ] = 1; |
|||
for (i = 1; i <= 1000 && seen[i]; i++); |
|||
if (i <= 1000) { |
|||
fprintf(stderr, "%d not seen\n", i); |
|||
abort(); |
|||
} |
|||
puts("\nfirst 1000 ok"); |
|||
return 0; |
|||
}</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
Line 355: | Line 404: | ||
Verified</pre> |
Verified</pre> |
||
=={{header| |
=={{header|Common Lisp}}== |
||
<lang lisp>;;; equally doable with a list |
|||
<lang c>#include <stdio.h> |
|||
(flet ((seq (i) (make-array 1 :element-type 'integer |
|||
#include <stdlib.h> |
|||
:initial-element i |
|||
:fill-pointer 1 |
|||
:adjustable t))) |
|||
(let ((rr (seq 1)) (ss (seq 2))) |
|||
(labels ((extend-r () |
|||
(let* ((l (1- (length rr))) |
|||
(r (+ (aref rr l) (aref ss l))) |
|||
(s (elt ss (1- (length ss))))) |
|||
(vector-push-extend r rr) |
|||
(loop while (<= s r) do |
|||
(if (/= (incf s) r) |
|||
(vector-push-extend s ss)))))) |
|||
(defun seq-r (n) |
|||
(loop while (> n (length rr)) do (extend-r)) |
|||
(elt rr (1- n))) |
|||
(defun seq-s (n) |
|||
// simple extensible array stuff |
|||
(loop while (> n (length ss)) do (extend-r)) |
|||
typedef unsigned long long xint; |
|||
(elt ss (1- n)))))) |
|||
(defun take (f n) |
|||
typedef struct { |
|||
(loop for x from 1 to n collect (funcall f x))) |
|||
size_t len, alloc; |
|||
xint *buf; |
|||
} xarray; |
|||
(format t "First of R: ~a~%" (take #'seq-r 10)) |
|||
xarray rs, ss; |
|||
(mapl (lambda (l) (if (and (cdr l) |
|||
void setsize(xarray *a, size_t size) |
|||
(/= (1+ (car l)) (cadr l))) |
|||
{ |
|||
(error "not in sequence"))) |
|||
size_t n = a->alloc; |
|||
(sort (append (take #'seq-r 40) |
|||
if (!n) n = 1; |
|||
(take #'seq-s 960)) |
|||
#'<)) |
|||
while (n < size) n <<= 1; |
|||
(princ "Ok")</lang>output<lang>First of R: (1 3 7 12 18 26 35 45 56 69) |
|||
if (a->alloc < n) { |
|||
Ok</lang> |
|||
a->buf = realloc(a->buf, sizeof(xint) * n); |
|||
if (!a->buf) abort(); |
|||
a->alloc = n; |
|||
} |
|||
} |
|||
void push(xarray *a, xint v) |
|||
{ |
|||
while (a->alloc <= a->len) |
|||
setsize(a, a->alloc * 2); |
|||
a->buf[a->len++] = v; |
|||
} |
|||
// sequence stuff |
|||
void RS_append(void); |
|||
xint R(int n) |
|||
{ |
|||
while (n > rs.len) RS_append(); |
|||
return rs.buf[n - 1]; |
|||
} |
|||
xint S(int n) |
|||
{ |
|||
while (n > ss.len) RS_append(); |
|||
return ss.buf[n - 1]; |
|||
} |
|||
void RS_append() |
|||
{ |
|||
int n = rs.len; |
|||
xint r = R(n) + S(n); |
|||
xint s = S(ss.len); |
|||
push(&rs, r); |
|||
while (++s < r) push(&ss, s); |
|||
push(&ss, r + 1); // pesky 3 |
|||
} |
|||
int main(void) |
|||
{ |
|||
push(&rs, 1); |
|||
push(&ss, 2); |
|||
int i; |
|||
printf("R(1 .. 10):"); |
|||
for (i = 1; i <= 10; i++) |
|||
printf(" %llu", R(i)); |
|||
char seen[1001] = { 0 }; |
|||
for (i = 1; i <= 40; i++) seen[ R(i) ] = 1; |
|||
for (i = 1; i <= 960; i++) seen[ S(i) ] = 1; |
|||
for (i = 1; i <= 1000 && seen[i]; i++); |
|||
if (i <= 1000) { |
|||
fprintf(stderr, "%d not seen\n", i); |
|||
abort(); |
|||
} |
|||
puts("\nfirst 1000 ok"); |
|||
return 0; |
|||
}</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 1,246: | Line 1,246: | ||
1 3 7 12 18 26 35 45 56 69 |
1 3 7 12 18 26 35 45 56 69 |
||
All Integers 1..1000 found OK</pre> |
All Integers 1..1000 found OK</pre> |
||
=={{header|PicoLisp}}== |
|||
<lang PicoLisp>(setq *RNext 2) |
|||
(de ffr (N) |
|||
(cache '(NIL) N |
|||
(if (= 1 N) |
|||
1 |
|||
(+ (ffr (dec N)) (ffs (dec N))) ) ) ) |
|||
(de ffs (N) |
|||
(cache '(NIL) N |
|||
(if (= 1 N) |
|||
2 |
|||
(let S (inc (ffs (dec N))) |
|||
(when (= S (ffr *RNext)) |
|||
(inc 'S) |
|||
(inc '*RNext) ) |
|||
S ) ) ) )</lang> |
|||
Test: |
|||
<lang PicoLisp>: (mapcar ffr (range 1 10)) |
|||
-> (1 3 7 12 18 26 35 45 56 69) |
|||
: (= |
|||
(range 1 1000) |
|||
(sort (conc (mapcar ffr (range 1 40)) (mapcar ffs (range 1 960)))) ) |
|||
-> T</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Line 1,332: | Line 1,305: | ||
1 3 7 12 18 26 35 45 56 69 |
1 3 7 12 18 26 35 45 56 69 |
||
Rawks!</pre> |
Rawks!</pre> |
||
=={{header|PicoLisp}}== |
|||
<lang PicoLisp>(setq *RNext 2) |
|||
(de ffr (N) |
|||
(cache '(NIL) N |
|||
(if (= 1 N) |
|||
1 |
|||
(+ (ffr (dec N)) (ffs (dec N))) ) ) ) |
|||
(de ffs (N) |
|||
(cache '(NIL) N |
|||
(if (= 1 N) |
|||
2 |
|||
(let S (inc (ffs (dec N))) |
|||
(when (= S (ffr *RNext)) |
|||
(inc 'S) |
|||
(inc '*RNext) ) |
|||
S ) ) ) )</lang> |
|||
Test: |
|||
<lang PicoLisp>: (mapcar ffr (range 1 10)) |
|||
-> (1 3 7 12 18 26 35 45 56 69) |
|||
: (= |
|||
(range 1 1000) |
|||
(sort (conc (mapcar ffr (range 1 40)) (mapcar ffs (range 1 960)))) ) |
|||
-> T</lang> |
|||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
Line 1,581: | Line 1,581: | ||
print("Ok")</lang>output<lang>[1, 3, 7, 12, 18, 26, 35, 45, 56, 69] |
print("Ok")</lang>output<lang>[1, 3, 7, 12, 18, 26, 35, 45, 56, 69] |
||
Ok</lang> |
Ok</lang> |
||
===Using cyclic iterators=== |
===Using cyclic iterators=== |