Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Unfriendly Numbers interviewstreet.com question in Racket

View unfriendly-numbers.rkt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
#lang racket/base
 
;; Unfriendly numbers
;; https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15
 
;; We'll provide a single function to solve this problem.
;;
;; Note that this module itself can be run as a main program, due to the
;; "main" submodule at the bottom of this file.
;;
;; Tests can also be executed via "raco test" of this module.
(provide solve)
 
(require racket/sequence)
 
 
;; Here's its definition:
 
;; solve: number (vectorof number) -> number
;; Returns the number of divisors of friendly that do not divide any of the numbers in unfriendlies.
(define (solve friendly unfriendlies)
(define divs (divisors friendly))
(for/sum ([d divs])
(cond [(some-divides? unfriendlies d)
0]
[else
1])))
 
;; divides?: number number -> boolean
;; Returns true if n evenly divides m.
(define (divides? m n)
(zero? (remainder m n)))
 
;; divisors: number -> sequence
;; Returns the divisors of m.
(define (divisors m)
(define (divides-m? i)
(divides? m i))
(sequence-filter divides-m? (in-range 1 (add1 m))))
 
;; some-divides?: (vectorof number) number -> boolean
;; Returns true if div divides some number in nums.
(define (some-divides? nums div)
(for/or ([n (in-vector nums)]) (divides? n div)))
 
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
;; Test cases just to sanity check the solution.
;; Use: "raco test unfriendly-numbers.rkt" to run the tests.
(module+ test
(require rackunit)
(printf "Running tests\n")
(check-equal? (solve 16 #(2 5 7 4 3 8 3 18)) 1)
(check-equal? (solve 16 #(2 5 7 4 3 8 3 18 16)) 0)
(check-equal? (solve 16 #()) 5)
(check-equal? (solve 1 #(1)) 0))
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
;; When executed as the main, we read two lines of input, according to the input
;; specification in the problem statement. In reality, we don't care about lines,
;; so our reading is a little looser.
(module+ main
(define n (read))
(define friendly (read))
(define unfriendlies
(for/vector #:length n ([i (in-range n)])
(read)))
(solve friendly unfriendlies))
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
;; This submodule provides all the exports, not just 'solve'.
(module+ all
(provide (all-from-out (submod ".."))))
samth commented

solve can be simplified as follows:

(define (solve friendly unfriendlies)
  (for/sum ([d (divisors friendly)]) 
    (if (some-divides? unfriendlies d) 0 1)))
samth commented

Or:

(define (solve friendly unfriendlies)
  (for/sum ([d (divisors friendly)]
            #:unless (some-divides? unfriendlies d))
    1))
Owner
dyoo commented

Thanks Sam; I'll simplify as you suggest by using for/sum.

samth commented

Do you not like #:unless? Also, I think if is clearer than cond here.

gyurisc commented

Is this ruby? I cannot recognize the language. Can you please explain what for/sum does?

Owner
dyoo commented

gyurisc: the language is Racket. The for/sum is a loop, but it collects and adds all the items that the loop's body creates. In the case above, we either add 0 or 1 as we walk through the list of numbers. For more examples of for/sum, see http://docs.racket-lang.org/reference/for.html#(form._((lib._racket/private/base..rkt)._for/sum))

gyurisc commented

Hi dyoo. Thanks for the answer. This looks like an interesting language. Does this code pass all testcases on interviewstreet?

Owner
dyoo commented

It does pass the single test case provided by the interviewstreet folks. I added a few more test cases in my gist, though it's by no means a comprehensive suite.

gyurisc commented
Owner
dyoo commented
gyurisc commented
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.