Programming Praxis

Home | Pages | Archives

Two Simple Tasks

January 5, 2021 9:00 AM

Happy New Year! May 2021 be a better year than 2020.

We have two simple tasks today:

First: Write a program that prints the sequence 1, 5, 10, 50, 100, … up to a given limit.

Second: Write a program that finds all three-digit numbers n such that n/11 equals the sum of the squares of the three digits.

Your task is to write programs that solve the two tasks given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Share this:

Posted by programmingpraxis

Categories: Exercises

Tags:

10 Responses to “Two Simple Tasks”

  1. 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)))

    By chaw on January 5, 2021 at 11:14 AM 

  2. (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)))

    By PaulGE (@PaulGE4) on January 5, 2021 at 11:21 AM

  3. 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

    By Zack on January 5, 2021 at 2:02 PM

  4. 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

    By Daniel on January 7, 2021 at 5:18 AM

  5. 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

    By Daniel on January 7, 2021 at 7:18 AM

  6. 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)

    By Jan Van lent on January 8, 2021 at 10:50 AM

  7. 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)

    By Jan Van lent on January 8, 2021 at 10:51 AM

  8. 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

    By Jan Van lent on January 8, 2021 at 10:56 AM

  9. 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
>

    By Kevin Short on January 10, 2021 at 8:14 PM

  10. 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

    By Adam Beguelin on January 17, 2021 at 1:50 PM

Leave a Reply

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.