000. Monchoka! Weekly Algos by your neighbourly scheme-r ;)

00 Binary Weight.md

Prelude

Hi folks! In the last LUG--- atm of this writing, there was a discussion around having community events, and algos and CTFs were enthusiastically proposed. The idea was to have our community hack on something together on (this past) Sunday, but that unfortunately never came to be--- I guess people did not get the bandwidth. That withstanding, I had volunteered to take up posting an algo problem every other week as we figure out how to make these community events more practical; so here we are!

I'll be scavenging for cool algos, CTFs and post them as weekly challenges. Let's see how this goes(I really hope I can keep this up!)

Let's take this as an opportunity to:

• explore new lang features (I've learnt quite a bit about GUILE this way, and I hope to do so with Rust);
• get some form of intellectual stimulation;
• see how other LUGers think;
• prep for interviews in an enjoyable fun way; and
• <insert your awesome reason here>

PS: If you have any cool suggestions, feel free to reach out to me on mail :)

This Week's Challenge

Issue 0 - Hamming Weight

Source: https://is.gd/lR9u7I

Write a function that takes an unsigned integer and returns the number of "1" bits it has.

Examples:
Input: n = 00000000000001011
Output: 3

Input: n = 0000100000
Output: 1

Input: n = 11111111110
Output: 10

Post your solutions as comments to this gist

@princebett, it's important to note that Rust doesn't really support TCO atm of this writing; thereby writing recursive fns is ill-advised. For big inputs, you have the possibility of getting some stack overflow. With that said, if you have to use a tail-recursive call, you could pull in extra deps that "trampoline"[0] your tail-recursive functions :)

[0] Trampolining is a technique that converts tail recursive fns into their iterative equivalents, thereby only using one stack frame

Tramp.rs actually does some heap allocation making it slower than just looping.

#lang racket

(module+ test
  (require rackunit)
  (check-equal? (count-ones #b00000000000001011) 3)
  (check-equal? (count-ones #b0000100000) 1)
  (check-equal? (count-ones #b11111111110) 10)
  (check-equal? (count-ones 5) 2))

(define/contract (count-ones v)
  (-> exact-nonnegative-integer? exact-nonnegative-integer?)
  (length
   (filter (lambda [c] (char=? c #\1))
	   (string->list (format "~B" v)))))

So, I felt a little weird, like I was cheating with the code above, since I did not actually compute the binary values myself. As such, just to assuage my critical voices, here's the new code, with my own computation of the binary values:

#lang racket
(require racket/contract)

(module+ test
  (require rackunit)
  (check-equal? (hamming-weight #b00000000000001011) 3)
  (check-equal? (hamming-weight #b0000100000) 1)
  (check-equal? (hamming-weight #b11111111110) 10)
  (check-equal? (hamming-weight 5) 2))

(define/contract (nonnegative-integer->binary-list n)
  (-> exact-nonnegative-integer?
      (listof (lambda (x) (or (zero? x) (= x 1)))))
  (define (->binary quot binlist)
    (cond
      [(zero? quot) binlist]
      [(->binary (quotient quot 2) (cons (modulo quot 2) binlist))]))
  (cond
    [(or (zero? n) (= n 1)) (cons n '())]
    [else (->binary (quotient n 2) (cons (modulo n 2) '()))]))

(define/contract (hamming-weight v)
  (-> exact-nonnegative-integer? exact-nonnegative-integer?)
  (length
   (filter (lambda [n] (= n 1))
	   (nonnegative-integer->binary-list v))))

```racket #lang racket (module+ test (require rackunit) (check-equal? (count-ones #b00000000000001011) 3) (check-equal? (count-ones #b0000100000) 1) (check-equal? (count-ones #b11111111110) 10))

I like the use of contracts although I've come to prefer to typed racket. TBH, when it comes to the actual grind, I use neither :(

(define/contract (count-ones v) (-> exact-nonnegative-integer? exact-nonnegative-integer?) (length (filter (lambda [c] (char=? c #\1)) (string->list (format "~B" v))))) ```

Here are the same solns in Racket: #+begin_src scheme #lang racket/base (require racket/contract) (require racket/contract) (define/contract (hamming-weight n) (-> exact-nonnegative-integer? integer?) (define (iter count n) (if (= n 0) count (iter (+ count 1) (bitwise-and n (- n 1))))) (iter 0 n)) (hamming-weight #b00000000000001011) #+end_src I prefer typed racket: #+begin_src scheme #lang typed/racket (: hamming-weight (-> Integer Integer)) (define (hamming-weight n) (define (iter count n) (if (= n 0) count (iter (+ count 1) (bitwise-and n (- n 1))))) (iter 0 n)) (hamming-weight #b00000000000001011) #+end_src and one in Haskell(couldn't help myself): #+begin_src haskell {-# LANGUAGE BinaryLiterals #-} import Data.Bits hammingWeight :: (Num a, Bits a, Num b) => a -> b hammingWeight n = iter 0 n where iter count x = if x == 0 then count else iter (count + 1) (x .&. (x - 1)) #+end_src Cheers!

…

-- Bonface M. K. D4F09EB110177E03C28E2FE1F5BBAE1E0392253F Humble GNU Emacs User / Bearer of scheme-y parens Curator: <https://upbookclub.com> / Twitter: @BonfaceKilz