Created
April 18, 2012 23:32
-
-
Save dyoo/2417377 to your computer and use it in GitHub Desktop.
Unfriendly Numbers interviewstreet.com question in Racket
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 "..")))) |
I was wondering if it can pass the the last 3 tests where they test for
large number of unfriendly numbers.
On Wed, May 2, 2012 at 9:01 PM, Danny Yoo < ***@***.*** > wrote:
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.
---
Reply to this email directly or view it on GitHub:
https://gist.github.com/2417377
##
Have a question on gadgets? - http://www.askaboutgadgets.com
On Wed, May 2, 2012 at 3:12 PM, gyurisc ***@***.*** wrote:
I was wondering if it can pass the the last 3 tests where they test for
large number of unfriendly numbers.
If you can tell me what those tests are, I can run them. They're not
included in the Unfriendly-Numbers_testcases.zip file included in the
assignment page, so I have no way of knowing otherwise what they're
testing against.
This tests are not known, but basically they are testing for the edge cases. For large number of unfriendly numbers. If your code is correct then it will past the first test. The third test, I believe is testing for N being very large, but within the limits of the specified value for N.
##
Gyuris Krisztián
Sent with Sparrow (http://www.sparrowmailapp.com/?sig)
…On Wednesday, May 2, 2012 at 9:19 PM, Danny Yoo wrote:
On Wed, May 2, 2012 at 3:12 PM, gyurisc
***@***.*** ***@***.***)>
wrote:
> I was wondering if it can pass the the last 3 tests where they test for
> large number of unfriendly numbers.
If you can tell me what those tests are, I can run them. They're not
included in the Unfriendly-Numbers_testcases.zip file included in the
assignment page, so I have no way of knowing otherwise what they're
testing against.
---
Reply to this email directly or view it on GitHub:
https://gist.github.com/2417377
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.