How to resolve the algorithm Rep-string step by step in the EchoLisp programming language

Published on 12 May 2024 09:40 PM
#Echolisp

How to resolve the algorithm Rep-string step by step in the EchoLisp programming language

Table of Contents

Problem Statement

Given a series of ones and zeroes in a string, define a repeated string or rep-string as a string which is created by repeating a substring of the first N characters of the string truncated on the right to the length of the input string, and in which the substring appears repeated at least twice in the original. For example, the string 10011001100 is a rep-string as the leftmost four characters of 1001 are repeated three times and truncated on the right to give the original string. Note that the requirement for having the repeat occur two or more times means that the repeating unit is never longer than half the length of the input string.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Rep-string step by step in the EchoLisp programming language

Source code in the echolisp programming language

(lib 'list) ;; list-rotate

;; a list is a rep-list if equal? to itself after a rotation of lam units
;; lam <= list length / 2
;; truncate to a multiple of lam before rotating
;; try cycles in decreasing lam order (longest wins)

(define (cyclic? cyclic)
    (define len (length cyclic))
    (define trunc null)

    (if (> len 1)
        (for ((lam (in-range (quotient len 2) 0 -1)))
        (set! trunc (take cyclic (- len (modulo len lam))))
         #:break (equal? trunc  (list-rotate trunc lam)) => (list->string (take cyclic lam))
         'no-rep )
   'too-short-no-rep))


(define strings '["1001110011" "1110111011" "0010010010" "1010101010"
      "1111111111" "0100101101" "0100100" "101" "11" "00" "1"])
      
(define (task strings)
	(for-each (lambda (s) 
	(writeln s (cyclic? (string->list s)))) strings))

(task strings)

"1001110011"     "10011"    
"1110111011"     "1110"    
"0010010010"     "001"    
"1010101010"     "1010"    
"1111111111"     "11111"    
"0100101101"     no-rep    
"0100100"     "010"    
"101"     no-rep    
"11"     "1"    
"00"     "0"    
"1"     too-short-no-rep

You may also check:How to resolve the algorithm Quoting constructs step by step in the Lua programming language
You may also check:How to resolve the algorithm Superellipse step by step in the Go programming language
You may also check:How to resolve the algorithm Dynamic variable names step by step in the Python programming language
You may also check:How to resolve the algorithm Magic squares of singly even order step by step in the Phix programming language
You may also check:How to resolve the algorithm Handle a signal step by step in the D programming language