Instantly share code, notes, and snippets.

Embed
What would you like to do?
UVA 136 - Ugly Number
// UVA 136 - Ugly Number
// Problem Definition: http://uva.onlinejudge.org/external/1/136.html
open System.Collections.Generic
let mutable cache1 = Dictionary<int64,bool>() //Dictionary
(*
* :()-> ()
*)
let initCache () =
cache1 <- Dictionary<int64,bool>()
(*
* :a:int64 -> b:bool -> bool
*)
let isFactor (n:int64) (d:int64):bool = n%d = 0L
(*
* :a:int64 -> b:bool -> bool
*)
let addToCacheAndRetrunResult n result:bool =
if n < 1000000L then
cache1.Add(n, result)
else
()
result
(*
* :a:int64 -> option(bool)
*)
let getFromCache n =
if n < 1000000L then
match cache1.TryGetValue(n) with
| true, res -> Some(res)
| false, _ -> None
else
None
(*
* :a:int64 -> b:bool
*)
let isUglyNumber (x:int64) :bool =
let rec checkFactors (n_org:int64) (n:int64) lfactors =
match getFromCache n with
| Some(x) -> x
| None ->
match n with
| 1L -> addToCacheAndRetrunResult n_org true
| _ ->
match lfactors with
| [] -> addToCacheAndRetrunResult n_org false
| d::xs ->
if isFactor n d then
checkFactors n_org (n/d) lfactors
elif n > d then
checkFactors n_org n xs
else
addToCacheAndRetrunResult n_org false
checkFactors x x [2L;3L;5L]
initCache() // init cache
// computing 1500th Ugly Number
seq{1L..System.Int64.MaxValue}
|> Seq.filter (isUglyNumber)
|> Seq.take 1500
|> Seq.last
// UVa 136 Problem
// Problem Definition: http://uva.onlinejudge.org/external/1/136.html
class Main {
public static void main(String[] args) {
System.out.println("The 1500'th ugly number is 859963392.");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment