How to resolve the algorithm Hofstadter Figure-Figure sequences step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Hofstadter Figure-Figure sequences step by step in the Racket programming language

Table of Contents

Problem Statement

These two sequences of positive integers are defined as:

The sequence

S ( n )

{\displaystyle S(n)}

is further defined as the sequence of positive integers not present in

R ( n )

{\displaystyle R(n)}

. Sequence

R

{\displaystyle R}

starts: Sequence

S

{\displaystyle S}

starts:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Hofstadter Figure-Figure sequences step by step in the Racket programming language

Source code in the racket programming language

#lang racket/base

(define r-cache (make-hash '((1 . 1) (2 . 3) (3 . 7))))
(define s-cache (make-hash '((1 . 2) (2 . 4) (3 . 5) (4 . 6))))

(define (extend-r-s!)
  (define r-count (hash-count r-cache))
  (define s-count (hash-count s-cache))
  (define last-r (ffr r-count))
  (define new-r (+ (ffr r-count) (ffs r-count)))
  (hash-set! r-cache (add1 r-count) new-r)
  (define offset (- s-count last-r))
  (for ([val (in-range (add1 last-r) new-r)])
    (hash-set! s-cache (+ val offset) val)))


(define (ffr n)
  (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))))


(displayln (map ffr (list 1 2 3 4 5 6 7 8 9 10)))
(displayln (map ffs (list 1 2 3 4 5 6 7 8 9 10)))

(displayln "Checking for first 1000 integers:")
(displayln (if (equal? (sort (append (for/list ([i (in-range 1 41)])
                                       (ffr i))
                                     (for/list ([i (in-range 1 961)])
                                       (ffs i)))
                             <)
                       (for/list ([i (in-range 1 1001)])
                         i))
               "Test passed"
               "Test failed"))

You may also check:How to resolve the algorithm Sorting algorithms/Permutation sort step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Interactive programming (repl) step by step in the BASIC programming language
You may also check:How to resolve the algorithm Determine if a string is squeezable step by step in the Phix programming language
You may also check:How to resolve the algorithm Function composition step by step in the jq programming language
You may also check:How to resolve the algorithm Juggler sequence step by step in the Python programming language