Skip to content

@dyoo /unfriendly-numbers.rkt
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Unfriendly Numbers interviewstreet.com question in Racket
#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

solve can be simplified as follows:

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

Or:

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

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

@samth

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

@gyurisc

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

@dyoo
Owner

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

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

@dyoo
Owner

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
@dyoo
Owner
@gyurisc
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.