4
\$\begingroup\$

I came across this problem by accident and gave it a go. I think my solution works as it has passed all the unit tests I wrote. Given I just started learning F# a couple of weeks I would love to have some feedback on the code regarding both its accuracy and its quality.

To be clear about the problem, given an integer number, check whether the number has at least 3 same digits in it e.g. 1222, 12222, 222, 123123123 are both counted as yes.

module Miscellaneous = 
    let (|ThreeSame|_|) = function
        | (l : int list) when l.Length > 20 -> Some()
        | x :: y :: z :: _ when x = y && y = z -> Some()
        | _ -> None

    ///<summary>
    /// Given any integer convert its digits into a list
    ///</summary>
    ///<param name="number">The integer</param>
    ///<returns>
    ///A int list
    ///</returns>
    let convertNumberToList (number: bigint) = 
        let numberString = string number
        numberString.ToCharArray() 
        |> Array.map (string >> int) //use composition to replace (fun x -> int (string x))
        |> Array.toList

type NumberCheck() =
        ///<summary>
        /// A helper function to check whether a list of numbers contains three or more
        /// same numbers
        ///</summary>
        ///<param name="l">The list to be checked</param>
        ///<param name="sorted">The flag to indicate whether the given list is sorted or not</param>
        ///<returns>
        /// True if there are at least 3 same numbers; False otherwise
        ///</returns>
        static member private TripleNumberHelper(l : int list, ?sorted) =
            if l.Length < 3 then false
            else
                if defaultArg sorted false then
                    match l with
                    | Miscellaneous.ThreeSame -> true
                    | _ -> NumberCheck.TripleNumberHelper(l.Tail, true)
                else
                    let sortedList = l |> List.sort
                    match sortedList with
                    | Miscellaneous.ThreeSame -> true
                    | _ -> NumberCheck.TripleNumberHelper(sortedList.Tail, true)

        ///<summary>
        /// Test whether a number has 3 or more same digits in it
        ///</summary>
        ///<param name="number">The number to be checked</param>
        ///<returns>
        ///Ture of False
        ///</returns>
        static member TripleNumber(number : bigint) = 
            let l = Miscellaneous.convertNumberToList number
            NumberCheck.TripleNumberHelper(l)
\$\endgroup\$
  • \$\begingroup\$ Using groupBy on the digits would be a straightforward way to do this. \$\endgroup\$ – hocho Jan 4 '16 at 6:55
  • \$\begingroup\$ @hocho many thanks for the comments and totally agree that using groupBy is a much better way of doing it. I have given it a try and please have a look at my implementation and any feedback is appreciated. \$\endgroup\$ – stt106 Jan 4 '16 at 12:47
  • 1
    \$\begingroup\$ @hocho Performance wise, using groupBy is also better as it's O(n) whereas the original way needs sorting hence is O(nlogn) ? \$\endgroup\$ – stt106 Jan 4 '16 at 12:57
  • \$\begingroup\$ countBy is even better that groupBy here. Glad you could get a fine solution! \$\endgroup\$ – hocho Jan 5 '16 at 8:41
2
\$\begingroup\$

You can make the solution a lot shorter by using built-in functions to do most of the heavy lifting.

let hasThreeSameDigits (num: bigint) =
    num.ToString()
    |> Seq.countBy id
    |> Seq.filter (fun (_, count) -> count >= 3)
    |> (not << Seq.isEmpty)
\$\endgroup\$
  • \$\begingroup\$ Ok, I think there is a minor improvement to use Seq.exists (fun (_, count) -> count >= 3) compared with using Seq.filter (which is always O(n)) \$\endgroup\$ – stt106 Jan 19 '16 at 15:32
  • \$\begingroup\$ @stt106: Actually, that isn't an improvement because sequences are evaluated lazily. That is, once an element makes it past Seq.filter and is evaluated by Seq.isEmpty, the expression returns. \$\endgroup\$ – Daniel Jan 20 '16 at 20:17
  • \$\begingroup\$ Once the first element passes filter, isEmpty will see it and return false. In the case isEmpty returns true, yes, the entire sequence will have been evaluated. But it would be no different with your snippet using exists. \$\endgroup\$ – Daniel Jan 20 '16 at 20:30
  • \$\begingroup\$ It's not a compiler optimization. It's simply the behavior of IEnumerable<T>. It works the same in other .NET languages. \$\endgroup\$ – Daniel Jan 20 '16 at 20:54
  • \$\begingroup\$ @Daniel sorry for asking such a silly question about lazy evaluation on IEnumerable \$\endgroup\$ – stt106 Jan 28 '16 at 14:09
2
\$\begingroup\$

Followed upon @hocho's comment and agree that using groupBy is much better as it can generalise the solution to check any number of same digit rather than limited to just 3 from my initial implementation. I have also simplified the helper method which converts a number into a collection; returning a sequence is enough as there is no need to return an array.

let convertNumberToSeq (number: bigint) = 
        let numberString = string number
        numberString.ToCharArray() 
        |> Seq.map (string >> int)

///<summary>
/// Check whether a given number has at least n same digits
///</summary>
///<param name="number">The given number</param>
///<param name="n">How many same digits to be checked</param>
///<returns>
///True if there are n same digits otherwise False
///</returns>
let SameDigitCheck (number : bigint) (n : int) = 
    if n < 2 then failwith "n must be at least 2"
    let digits = convertNumberToSeq number
    let q = query { for digit in digits do groupBy digit into g; select g }
    q |> Seq.exists (fun x -> Seq.length x >= n)
\$\endgroup\$
  • \$\begingroup\$ if n < 2 then failwith "n must be at least 2" <- why? It seems legit to me to ask if a number has 0 or 1 same digits, it will just return true all the times \$\endgroup\$ – Caridorc Jan 4 '16 at 15:07
  • \$\begingroup\$ @Caridorc I just didn't think it makes any practical sense to ask for 0 or 1 same digit but I do understand your point. \$\endgroup\$ – stt106 Jan 4 '16 at 15:42
  • 1
    \$\begingroup\$ Not by hand, but if you have a loop from 0 to x checking this property, true is better than failing \$\endgroup\$ – Caridorc Jan 4 '16 at 17:30
  • \$\begingroup\$ I've removed the last sentence as answers shouldn't be used to seek further reviews. \$\endgroup\$ – Jamal Jan 19 '16 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.