-
-
Save dyoo/2417377 to your computer and use it in GitHub Desktop.
#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 "..")))) |
Or:
(define (solve friendly unfriendlies)
(for/sum ([d (divisors friendly)]
#:unless (some-divides? unfriendlies d))
1))
Thanks Sam; I'll simplify as you suggest by using for/sum.
Do you not like #:unless
? Also, I think if
is clearer than cond
here.
Is this ruby? I cannot recognize the language. Can you please explain what for/sum does?
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))
Hi dyoo. Thanks for the answer. This looks like an interesting language. Does this code pass all testcases on interviewstreet?
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.
solve
can be simplified as follows: