Programming Praxis

10 Responses to “Two Simple Tasks”

1. chaw said

   January 5, 2021 at 11:14 AM

   I felt like generalizing the first problem a bit and am including my
   solution in standard R7RS Scheme below, along with a simple solution
   to the second one as well. Happy 2021 to all!

   (import (scheme base)
           (scheme write)
           (only (srfi 1)
                 circular-list every)
           (srfi 8))
   
   (define-syntax assert
     (syntax-rules ()
       ((_ pred ...) (unless (and pred ...)
                       (display "Failed assertion: ")
                       (display '(pred ...))
                       (newline)
                       (error "assertion failure"))))) 
   
   (define (multi-geometric-progression-fold kons knil init multipliers limit)
     (assert (number? init) (pair? multipliers) (every number? multipliers))
     (let f ((seed knil)
             (term init)
             (muls (apply circular-list multipliers)))
       (if (>= term limit)
           seed
           (f (kons term seed)
              (* term (car muls))
              (cdr muls)))))
   
   (assert (equal? '(1000 500 100 50 10 5 1)
                   (multi-geometric-progression-fold cons '() 1 '(5 2) 1001)))
   
   (assert (equal? '(1008 1008 252 252 84 84 21 21 7)
                   (multi-geometric-progression-fold cons '() 7 '(3 1 4 1) 2001)))
   
   (assert (equal? '(10000 5000 1000 500 100 50 10 5 1)
                   (multi-geometric-progression-fold cons '() 1 '(5 2) 10001)))
   
   (define (digits n)
     (if (zero? n)
         '(0)
         (let f ((n n)
                 (digits '()))
           (if (zero? n)
               digits
               (receive (quot rem) (floor/ n 10)
                 (f quot
                    (cons rem digits)))))))
   
   (define (q2)
     (let f ((n 110)
             (m 10) ; n/11 = m
             (r '()))
       (if (> n 999)
           (reverse r)
           (f (+ n 11)
              (+ m 1)
              (if (= m (apply + (map square (digits n))))
                  (cons n r)
                  r)))))
   
   (assert (equal? '(550 803) (q2)))
   
2. PaulGE (@PaulGE4) said

   January 5, 2021 at 11:21 AM

   (defun 5-1-sequence (limit)
     (cons 1 (loop :for f := t :then (not f)
                   :for n := 5 :then (* (if f 5 2) n)
                   :while (< n limit)
                   :collect n)))
   
   (assert (equalp (5-1-sequence 100001)
                   '(1 5 10 50 100 500 1000 5000 10000 50000 100000)))
   
   (defun print-5-1-sequence (limit)
     (let ((*print-right-margin* 72))
       (pprint (5-1-sequence limit)))
     (values))
   
   (print-5-1-sequence 10000001)
   
   ;; (1 5 10 50 100 500 1000 5000 10000 50000 100000 500000 1000000 5000000
   ;;  10000000)
   
   
   (defun find-numbers (min max such-as)
     (loop
       :for i :from min :to max
       :when (funcall such-as i)
         :collect i))
   
   (defun square (x) (* x x))
   
   (assert (equalp (find-numbers 0 999
                                 (lambda (n)
                                   (let ((a (truncate n 100))
                                         (b (mod (truncate n 10) 10))
                                         (c (mod n 10)))
                                     (= (/ n 11)
                                        (+ (square a) (square b) (square c))))))
                   '(0 550 803)))
   
3. Zack said

   January 5, 2021 at 2:02 PM

   Such a good way to start the new coding year :-) Here is my take on this drill using Julia 1.5.2: https://pastebin.com/AjpJg1Hn. Cheers
4. Daniel said

   January 7, 2021 at 5:18 AM

   Here’s a solution to the first task in x86-64 assembly using Linux system calls.

   ; sequence.asm
   
   ; Description
   ;   Print the sequence 1, 5, 10, 50, 100, ... up to the specified limit
   ; Synopsis
   ;   ./sequence LIMIT
   ; Build
   ;   nasm -felf64 sequence.asm
   ;   ld -o sequence sequence.o
   ; Warning
   ;   Overflow and invalid input is not checked/handled
   
     global _start
   
     section .text
   _start:
     ; make sure there is single argument
     cmp qword [rsp], 2
     jne exit_failure
     ; load argument as integer into rax then r8
     mov rax, 0 ; limit
     mov r8, [rsp + 16] ; address of next digit
     mov r9, 10
   atoi:
     movzx r10, byte [r8]
     cmp r10, 0
     je atoi_end
     mul r9
     sub r10, 48
     add rax, r10
     add r8, 1
     jmp atoi
   atoi_end:
     mov r8, rax ; limit
     mov r9, 1 ; current value
     ; r10 and r12 multipliers are swapped on each iteration
     ; skipped r11 since it's clobbered by syscall below
     mov r10, 5
     mov r12, 2
   main_loop:
     cmp r9, r8
     jg exit_success
     ; print r9
     mov rax, r9
     mov rbp, rsp
     sub rsp, 1
     mov byte [rsp], `\n`
     mov r13, 1 ; number of bytes
   digit_loop:
     xor rdx, rdx
     mov r14, 10
     div r14
     add r13, 1
     sub rsp, 1
     add rdx, 48
     mov [rsp], dl
     cmp rax, 0
     jne digit_loop
     mov rax, 1 ; write system call
     mov rdi, 1 ; stdout
     mov rsi, rsp ; address of string
     mov rdx, r13 ; number of bytes
     syscall
     mov rsp, rbp
     mov rax, r9
     mul r10
     mov r9, rax
     ; swap r10 and r12 using xor
     xor r10, r12
     xor r12, r10
     xor r10, r12
     jmp main_loop
   exit_failure:
     mov rdi, 1
   exit_success:
     xor rdi, rdi
     ; intentional fallthrough
   exit:
     mov rax, 60 ; exit system call
     syscall
   

   Example usage:

   $ ./sequence 9999
   1
   5
   10
   50
   100
   500
   1000
   5000
   
5. Daniel said

   January 7, 2021 at 7:18 AM

   Here’s a solution to the second task in x86-64 assembly using Linux system calls.

   ; search.asm
   
   ; Description
   ;   Find all three digit numbers whose squared digits sum to the number divided
   ;   by 11
   ; Synopsis
   ;   ./search
   ; Build
   ;   nasm -felf64 search.asm
   ;   ld -o search search.o
   
     global _start
   
     section .text
   _start:
     mov r8, 110 ; current number
     mov r9, 10 ; current number divided by 11
     mov r10, 10 ; radix
   loop:
     cmp r8, 1000
     jge exit
     mov r11, 0 ; sum of digits
     mov rcx, 3
     mov r12, r8 ; workspace for extracting digits
   digit_loop:
     xor rdx, rdx
     mov rax, r12
     div r10
     mov r12, rax
     mov rax, rdx
     mul rax
     add r11, rax
     loop digit_loop
     cmp r11, r9
     jne continue_loop
     mov r12, r8
     mov r13, `\n`
     mov rcx, 3
   print_loop:
     xor rdx, rdx
     mov rax, r12
     div r10
     add rdx, 48
     shl r13, 8
     or r13, rdx
     mov r12, rax
     loop print_loop
     push r13
     mov rax, 1 ; write system call
     mov rdi, 1 ; stdout
     mov rsi, rsp ; address of string
     mov rdx, 4 ; number of bytes
     syscall
     sub rsp, 8
   continue_loop:
     add r8, 11
     add r9, 1
     jmp loop
   exit:
     xor rdi, rdi
     mov rax, 60 ; exit system call
     syscall
   

   Example usage:

   $ ./search
   550
   803
   
6. Jan Van lent said

   January 8, 2021 at 10:50 AM

   A Lua solution for the first task.

   function print_seq(N)
      local i = 1
      while true do
         if i <= N then print(i) else break end
         i = i*5
         if i <= N then print(i) else break end
         i = i*2
      end
   end
   
   print_seq(500)
   
7. Jan Van lent said

   January 8, 2021 at 10:51 AM

   Lua solution for the first task using mutual tail calls.

   function print_seq1(i, N)
      if i <= N then
         print(i)
         print_seq5(5*i, N)
      end
   end
   
   function print_seq5(i, N)
      if i <= N then
         print(i)
         print_seq1(2*i, N)
      end
   end
   
   print_seq1(1, 500)
   
8. Jan Van lent said

   January 8, 2021 at 10:56 AM

   Lua solution for the second task. Brute force stepping through all the numbers from 100 to 999 rather than just multiples of 11. This allows interpreting n/11 as floor division (see commented line), giving more solutions.

   for d0 = 0, 9 do
      for d1 = 0, 9 do
         for d2 = 1, 9 do
   	 n = d2*100 + d1*10 + d0
   	 --m = math.floor(n/11)
   	 m = n / 11
   	 sumsq = d2^2 + d1^2 + d0^2
   	 if m == sumsq then
   	    print(n, sumsq)
   	 end
         end
      end
   end
   
9. Kevin Short said

   January 10, 2021 at 8:14 PM

   A response for “Two Simple Tasks”, written in Racket:
   


   (define (print-comma-sep-list data)
     (let loop ([str "~a"] [li data])
       (cond
         [(empty? li) (printf ".\n")]
         [else (printf str (first li))
               (loop ", ~a" (rest li))])))
   
   (define (simp-task-1 lim)
     (let loop ([mult 1] [seed 1] [ans '()])
       (let ((val (* mult seed)))
         (if (<= val lim)
             (loop (if (equal? seed 5) (* mult 10) mult) (if (equal? seed 1) 5 1) (cons val ans))
             (print-comma-sep-list (reverse ans))))))
   
   (define (simp-task-2)
     (for ([i (in-range 100 1000)])
       (cond
         [(equal?
           (/ i 11)
           (foldl (lambda (s v) (+ (expt (string->number (list->string (list s))) 2) v))
                  0
                  (string->list (number->string i))))
          (printf "~a\n" i)])))
   

   
   And here are the results:
   


   Welcome to DrRacket, version 7.9 [3m].
   Language: racket, with debugging; memory limit: 128 MB.
   > (simp-task-1 500000)
   1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000.
   > (simp-task-2)
   550
   803
   > 
   
10. Adam Beguelin said

    January 17, 2021 at 1:50 PM

    I’m trying to learn JavaScript. So here are my answers written in JS and run with node…

    var start = [“1”, “50”]

    function addzero(t) {
    return [t[0] += ‘0’, t[1] += ‘0’]
    }

    let max = 1000000
    for (var i = 0; i < 10; i++) {
    var r = addzero(start)
    if (r[0] > max || r[1] > max) return
    console.log(r.shift(),r.shift())
    }

    // prax1.js

    for (let i = 100; i < 1000; i++) {
    let d = i.toString().split(”)
    let dig = d.map(Number)
    let sum = dig[0] * dig[0] + dig[1]* dig[1] + dig[2] * dig[2]
    if (i/11 == sum) console.log(i/11, dig, sum)
    }

    % node prax1.js
    50 [ 5, 5, 0 ] 50
    73 [ 8, 0, 3 ] 73