Performance

Nice feedback. The following is a trivial matter.

Ceiling valiable (end1) is not necessary. This is because the square root is always an integer for a perfect square. And if I understand this method correctly, the scope of the check is "less than or equal to the square root of n".

(I'm not familiar with JavaScript, but I can write it this way in Racket.)

Also, something I overlooked, when n=1, it returns an unintended result of (1 1 1), so I added a test case.

Code
Diff
  • #lang racket
    
    (provide get-divs)
    
    (define (get-divs n)
      (if (= 1 n) (list 1)
      (let ([sqrt-n (sqrt n)])
        (define (inner x result-min result-max)
          (cond
            [(>= x sqrt-n) (append result-min (if (integer? sqrt-n) (cons sqrt-n result-max) result-max))]
            [(= 0 (modulo n x)) (inner (add1 x) (append result-min (list x)) (cons (/ n x) result-max))]
            [else (inner (add1 x) result-min result-max)]))
        (inner 2 (list 1) (list n)))))
  • 11
    #lang racket
    
    22
    33
    (provide get-divs)
    
    44
    55
    (define (get-divs n)
    
    6
      (let* ([end0 (sqrt n)]
    
    7
             [end1 (ceiling end0)])
    
    6+
      (if (= 1 n) (list 1)
    
    7+
      (let ([sqrt-n (sqrt n)])
    
    88
        (define (inner x result-min result-max)
    
    99
          (cond
    
    10
            [(>= x end1) (append result-min (if (= end0 end1) (cons end1 result-max) result-max))]
    
    11
            [(= 0 (modulo n x)) (inner (add1 x)
    
    12
                                      (append result-min (list x))
    
    13
                                      (cons (/ n x) result-max))]
    
    10+
            [(>= x sqrt-n) (append result-min (if (integer? sqrt-n) (cons sqrt-n result-max) result-max))]
    
    11+
            [(= 0 (modulo n x)) (inner (add1 x) (append result-min (list x)) (cons (/ n x) result-max))]
    
    1414
            [else (inner (add1 x) result-min result-max)]))
    
    15
        (inner 2 (list 1) (list n))))
    
    13+
        (inner 2 (list 1) (list n)))))
    
Performance
Code
Diff
  • #lang racket
    
    (provide get-divs)
    
    (define (get-divs n)
      (let ([sqrt-n (sqrt n)])
        (define (inner x result-min result-max)
          (cond
            [(> x sqrt-n) (append result-min result-max)]
            [(= 0 (modulo n x)) (inner (add1 x)
                                      (append result-min (list x))
                                      (cons (/ n x) result-max))]
            [else (inner (add1 x) result-min result-max)]))
        (inner 2 (list 1) (list n))))
  • 1
    function getDiv(n){
    
    2
        let factor0 = [];
    
    3
        let factor1 = [];
    
    4
        let end0 = Math.sqrt(n);
    
    5
        let end1 = Math.ceil(end0);
    
    6
        for (let i = 1; i !== end1; ++i) {
    
    7
            if (n % i === 0) {
    
    8
                factor0.push(i);
    
    9
                factor1.unshift(n / i);
    
    10
            }
    
    11
        }
    
    12
        if (end0 === end1) {
    
    13
            factor0.push(end0);
    
    14
        }
    
    15
        factor0.push(...factor1);
    
    16
        return factor0;
    
    17
    }
    
    1+
    #lang racket
    
    2+
    3+
    (provide get-divs)
    
    4+
    5+
    (define (get-divs n)
    
    6+
      (let ([sqrt-n (sqrt n)])
    
    7+
        (define (inner x result-min result-max)
    
    8+
          (cond
    
    9+
            [(> x sqrt-n) (append result-min result-max)]
    
    10+
            [(= 0 (modulo n x)) (inner (add1 x)
    
    11+
                                      (append result-min (list x))
    
    12+
                                      (cons (/ n x) result-max))]
    
    13+
            [else (inner (add1 x) result-min result-max)]))
    
    14+
        (inner 2 (list 1) (list n))))
    
Code
Diff
  • open BatBig_int
    
    let fib x =
      let rec big_fib n a b = match n with
        | 1 ->  a + b
        | _ -> big_fib (Stdlib.(-) n 1) (a + b) a in
      match x with
      | 0 -> "0"
      | 1 -> "1"
      | _ -> big_fib (Stdlib.(-) x 1) (big_int_of_int 1) (big_int_of_int 0) |> string_of_big_int;;
    
  • 11
    open BatBig_int
    
    22
    33
    let fib x =
    
    4
      let rec big_fib =
    
    5
        let cache = Hashtbl.create 10000000 in
    
    6
        (fun x ->
    
    7
          if (equal x zero) then zero
    
    8
          else if (equal x one) then one
    
    9
          else
    
    10
            begin
    
    11
              try 
    
    12
                Hashtbl.find cache (int_of_big_int x)
    
    13
              with
    
    14
                Not_found ->
    
    15
                let result = big_fib (x - one) + big_fib (x - (big_int_of_int 2)) in
    
    16
                Hashtbl.add cache (int_of_big_int x) result;
    
    17
                result
    
    18
            end) in
    
    19
      big_fib (big_int_of_int x) |> string_of_big_int;;
    
    4+
      let rec big_fib n a b = match n with
    
    5+
        | 1 ->  a + b
    
    6+
        | _ -> big_fib (Stdlib.(-) n 1) (a + b) a in
    
    7+
      match x with
    
    8+
      | 0 -> "0"
    
    9+
      | 1 -> "1"
    
    10+
      | _ -> big_fib (Stdlib.(-) x 1) (big_int_of_int 1) (big_int_of_int 0) |> string_of_big_int;;
    
Code
Diff
  • let project_euler_problem_1 = 
      let rec loop i result = match i with
      | 0 -> result 
      | n when i mod 3 = 0 -> loop (i - 1) (result + n)
      | n when i mod 5 = 0 -> loop (i - 1) (result + n)
      | _ -> loop (i - 1) result in
      loop 999 0;; 
  • 1
    let projectEulerProblemOne = [1 .. 999] |> List.filter(fun x -> x % 3 = 0 || x % 5 = 0) |> List.sum
    
    1+
    let project_euler_problem_1 = 
    
    2+
      let rec loop i result = match i with
    
    3+
      | 0 -> result 
    
    4+
      | n when i mod 3 = 0 -> loop (i - 1) (result + n)
    
    5+
      | n when i mod 5 = 0 -> loop (i - 1) (result + n)
    
    6+
      | _ -> loop (i - 1) result in
    
    7+
      loop 999 0;; 
    

memoize recursion

Code
Diff
  • open BatBig_int
    
    let fib x =
      let rec big_fib =
        let cache = Hashtbl.create 10000000 in
        (fun x ->
          if (equal x zero) then zero
          else if (equal x one) then one
          else
            begin
              try 
                Hashtbl.find cache (int_of_big_int x)
              with
                Not_found ->
                let result = big_fib (x - one) + big_fib (x - (big_int_of_int 2)) in
                Hashtbl.add cache (int_of_big_int x) result;
                result
            end) in
      big_fib (big_int_of_int x) |> string_of_big_int;;
    
  • 1
    module Example where
    
    1+
    open BatBig_int
    
    22
    3
    import Data.Semigroup (Endo(..),stimes)
    
    4
    5
    fib :: Integer -> Integer
    
    6
    fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
    
    3+
    let fib x =
    
    4+
      let rec big_fib =
    
    5+
        let cache = Hashtbl.create 10000000 in
    
    6+
        (fun x ->
    
    7+
          if (equal x zero) then zero
    
    8+
          else if (equal x one) then one
    
    9+
          else
    
    10+
            begin
    
    11+
              try 
    
    12+
                Hashtbl.find cache (int_of_big_int x)
    
    13+
              with
    
    14+
                Not_found ->
    
    15+
                let result = big_fib (x - one) + big_fib (x - (big_int_of_int 2)) in
    
    16+
                Hashtbl.add cache (int_of_big_int x) result;
    
    17+
                result
    
    18+
            end) in
    
    19+
      big_fib (big_int_of_int x) |> string_of_big_int;;
    

switch function (char-upcase -> char-downcase -> char-upcase ....)

Code
Diff
  • #lang racket
    (provide hellOwOrld)
    
    (define (hello-f n lst result)
      (if (null? lst) result
       (let ([char-f (if (= n 0) char-upcase char-downcase)]
             [n (if (= n 0) 1 0)])
          (hello-f n (cdr lst) (append result (list (char-f (car lst))))))))
    
    (define (hellOwOrld str)
      (list->string (hello-f 0 (filter (lambda (x) (not (char-whitespace? x)))
                                           (string->list (string-downcase str))) (list))))
    
  • 11
    #lang racket
    
    22
    (provide hellOwOrld)
    
    33
    4
    (define (hello-upcase lst result)
    
    4+
    (define (hello-f n lst result)
    
    55
      (if (null? lst) result
    
    6
       (hello-downcase (cdr lst) (append result (list (char-upcase (car lst)))))))
    
    7
    8
    (define (hello-downcase lst result)
    
    9
      (if (null? lst) result
    
    10
       (hello-upcase (cdr lst) (append result (list (char-downcase (car lst)))))))
    
    6+
       (let ([char-f (if (= n 0) char-upcase char-downcase)]
    
    7+
             [n (if (= n 0) 1 0)])
    
    8+
          (hello-f n (cdr lst) (append result (list (char-f (car lst))))))))
    
    1111
    1212
    (define (hellOwOrld str)
    
    13
      (list->string (hello-upcase (filter (lambda (x) (not (char-whitespace? x)))
    
    11+
      (list->string (hello-f 0 (filter (lambda (x) (not (char-whitespace? x)))
    
    1414
                                           (string->list (string-downcase str))) (list))))
    
Arrays

tail recursion version

Code
Diff
  • let remove xs index =
      let rec loop n hd tl = match tl with
      | [] -> xs
      | _::tl when n = 0 -> (List.rev hd) @ tl
      | t::tl' -> loop (n - 1) (t :: hd) tl' in
      loop index [] xs;;
  • 11
    let remove xs index =
    
    2
      let rec remove' (xs, index) =
    
    3
        match xs with
    
    4
        | [] -> []
    
    5
        | x::xs' -> if index = 0 then xs' else x::(remove' (xs', index - 1))
    
    6
      in
    
    7
      if index < 0 then xs else remove' (xs, index)
    
    8
    ;;
    
    2+
      let rec loop n hd tl = match tl with
    
    3+
      | [] -> xs
    
    4+
      | _::tl when n = 0 -> (List.rev hd) @ tl
    
    5+
      | t::tl' -> loop (n - 1) (t :: hd) tl' in
    
    6+
      loop index [] xs;;
    
Strings
Code
Diff
  • let char_list_of_string s = List.init (String.length s) (String.get s);;
    let string_of_char_list s = List.to_seq s |> String.of_seq;;
    
    let format_string_of_int x =
      let char_list = string_of_int x |> char_list_of_string |> List.rev in
      let rec loop lst work result = match (work, lst) with
      | (_ , []) -> (work @ result) |> string_of_char_list
      | (_::_::_::[], _) -> loop lst [] ((','::work) @ result)
      | (_, x::xs) -> loop xs (x::work) result in
      loop char_list [] [];;
  • 1
    module Format where
    
    1+
    let char_list_of_string s = List.init (String.length s) (String.get s);;
    
    2+
    let string_of_char_list s = List.to_seq s |> String.of_seq;;
    
    22
    3
    import Data.Bits ((.|.))
    
    4
    import Data.Char (chr)
    
    5
    6
    f :: Integer -> [Char]
    
    7
    f n = f' [chr $ (.|.) 48 $ fromIntegral $ mod n 10] (div n 10) where
    
    8
      f' :: [Char] -> Integer -> [Char]
    
    9
      f' sol 0 = sol
    
    10
      f' acc n = f'' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) acc) (div n 10) where
    
    11
        f'' :: [Char] -> Integer -> [Char]
    
    12
        f'' sol 0 = sol
    
    13
        f'' acc n = f''' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) acc) (div n 10) where
    
    14
          f''' :: [Char] -> Integer -> [Char]
    
    15
          f''' sol 0 = sol
    
    16
          f''' acc n = f' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) $ (:) ',' acc) (div n 10) 
    
    4+
    let format_string_of_int x =
    
    5+
      let char_list = string_of_int x |> char_list_of_string |> List.rev in
    
    6+
      let rec loop lst work result = match (work, lst) with
    
    7+
      | (_ , []) -> (work @ result) |> string_of_char_list
    
    8+
      | (_::_::_::[], _) -> loop lst [] ((','::work) @ result)
    
    9+
      | (_, x::xs) -> loop xs (x::work) result in
    
    10+
      loop char_list [] [];;
    

tail recursion version

Code
Diff
  • let merge_lists a b =
      let rec loop a b result =
        match a, b with
        | c, [] | [], c -> (List.rev result) @ c 
        | ax::a', bx::_ when ax < bx -> loop a' b (ax::result)
        | _, bx::b' -> loop a b' (bx::result) in
      loop a b [];;
  • 1
    let rec merge_lists a b =
    
    2
      match a, b with
    
    3
      | c, [] | [], c -> c
    
    4
      | ax::a', bx::_ when ax < bx -> ax::(merge_lists a' b)
    
    5
      | _, bx::b' -> bx::(merge_lists b' a)
    
    6
    ;;
    
    1+
    let merge_lists a b =
    
    2+
      let rec loop a b result =
    
    3+
        match a, b with
    
    4+
        | c, [] | [], c -> (List.rev result) @ c 
    
    5+
        | ax::a', bx::_ when ax < bx -> loop a' b (ax::result)
    
    6+
        | _, bx::b' -> loop a b' (bx::result) in
    
    7+
      loop a b [];;
    

mutual recursion

Code
Diff
  • #lang racket
    (provide hellOwOrld)
    
    (define (hello-upcase lst result)
      (if (null? lst) result
       (hello-downcase (cdr lst) (append result (list (char-upcase (car lst)))))))
    
    (define (hello-downcase lst result)
      (if (null? lst) result
       (hello-upcase (cdr lst) (append result (list (char-downcase (car lst)))))))
    
    (define (hellOwOrld str)
      (list->string (hello-upcase (filter (lambda (x) (not (char-whitespace? x)))
                                           (string->list (string-downcase str))) (list))))
    
  • 1
    public class HeLlOwOrLddddd {
    
    2
      public static String convert(String input) {
    
    3
          String salida = "";
    
    4
          boolean mayus = true;
    
    5
          for (int i=0;i<input.length();i++){
    
    6
            if (Character.isLetter(input.charAt(i))){
    
    7
                if (mayus){
    
    8
                    salida+=Character.toUpperCase(input.charAt(i));
    
    9
                    mayus=false;
    
    10
                }else{
    
    11
                    salida+=Character.toLowerCase(input.charAt(i));
    
    12
                    mayus=true;
    
    13
                }
    
    14
            }        
    
    15
        }
    
    16
          return salida;
    
    1+
    #lang racket
    
    2+
    (provide hellOwOrld)
    
    1717
    18
      }
    
    19
    }
    
    4+
    (define (hello-upcase lst result)
    
    5+
      (if (null? lst) result
    
    6+
       (hello-downcase (cdr lst) (append result (list (char-upcase (car lst)))))))
    
    7+
    8+
    (define (hello-downcase lst result)
    
    9+
      (if (null? lst) result
    
    10+
       (hello-upcase (cdr lst) (append result (list (char-downcase (car lst)))))))
    
    11+
    12+
    (define (hellOwOrld str)
    
    13+
      (list->string (hello-upcase (filter (lambda (x) (not (char-whitespace? x)))
    
    14+
                                           (string->list (string-downcase str))) (list))))
    

true -> 1, false -> 0

OR:

or(2) = 1 + 1 -> true
or(1) = 1 + 0 -> true
or(1) = 0 + 1 -> true
or(0) = 0 + 0 = 0 -> false

or(x) = if x > 0 -> true

AND:

and(2) = 1 + 1 -> true
and(1) = 1 + 0 -> false
and(1) = 0 + 1 -> false
and(0) = 0 + 0 -> false

and(x) = if x > 1 (or x == 2) -> true

XOR

xor(2) = 1 + 1 -> false
xor(1) = 1 + 0 -> true
xor(1) = 0 + 1 -> true
xor(0) = 0 + 0 -> false

xor(x) = if x == 0 -> true

Code
Diff
  • let int_of_bool = function
      | true -> 1
      | false -> 0;;
     
    let (|||) x y =  (int_of_bool x) + (int_of_bool y) > 0;;
    let (&&&) x y = (int_of_bool x) + (int_of_bool y) > 1;;
    let (|!|) x y = (int_of_bool x) + (int_of_bool y) = 1;;
  • 1
    bool Or(bool a, bool b){
    
    2
    	if(!a){
    
    3
    		if(!b){
    
    4
    			return false;
    
    5
    		}
    
    6
    	}
    
    7
    	return true;
    
    8
    }
    
    9
    10
    bool Xor(bool a, bool b){
    
    11
    	return a != b;	
    
    12
    }
    
    13
    14
    bool And(bool a, bool b){
    
    15
    	if(a){
    
    16
    		if(b){
    
    17
    			return true;
    
    18
    		}
    
    19
    	}
    
    20
    	return false;
    
    21
    }
    
    1+
    let int_of_bool = function
    
    2+
      | true -> 1
    
    3+
      | false -> 0;;
    
    4+
     
    
    5+
    let (|||) x y =  (int_of_bool x) + (int_of_bool y) > 0;;
    
    6+
    let (&&&) x y = (int_of_bool x) + (int_of_bool y) > 1;;
    
    7+
    let (|!|) x y = (int_of_bool x) + (int_of_bool y) = 1;;
    
Numbers
Integers
Algorithms
Code
Diff
  • let number_of_digits x = 
      String.concat "" ["1"; String.make (x - 1) '0'] |> int_of_string;;
  • 1
    fn digits(mut n: u64) -> usize {
    
    2
        let mut l = 1;
    
    3
        while n >= 10 {
    
    4
            n /= 10;
    
    5
            l += 1;
    
    6
        }
    
    7
        l
    
    8
    }
    
    1+
    let number_of_digits x = 
    
    2+
      String.concat "" ["1"; String.make (x - 1) '0'] |> int_of_string;;
    
Code
Diff
  • #lang racket
    (provide verify-sum)
    (define (string->number-sum x)
      (apply + (map char->integer (string->list x))))
    
    (define (verify-sum x y)
      (cond 
       [(or (null? x) (null? y)) "NULL"]
       [(= (string->number-sum x) (string->number-sum y)) "TRUE"]
       [else "FALSE"]))
  • 1
    class Kata{
    
    2
      
    
    3
      public static String verifySum(String nameOne, String nameTwo) {
    
    4
            int[] sumOfNames = new int[]{0, 0};
    
    5
            
    
    6
            if (nameOne == null || nameTwo == null) {
    
    7
                return "NULL";
    
    8
            }
    
    9
            
    
    10
            for (int i = 0; i < nameOne.length(); i++){
    
    11
                sumOfNames[0] += nameOne.charAt(i);
    
    12
            }
    
    13
            
    
    14
            for (int i = 0; i < nameTwo.length(); i++){
    
    15
                sumOfNames[1] += nameTwo.charAt(i);
    
    16
            }
    
    17
            
    
    18
            return sumOfNames[0] == sumOfNames[1] ? "TRUE" : "FALSE";
    
    19
        }
    
    20
    }
    
    1+
    #lang racket
    
    2+
    (provide verify-sum)
    
    3+
    (define (string->number-sum x)
    
    4+
      (apply + (map char->integer (string->list x))))
    
    5+
    6+
    (define (verify-sum x y)
    
    7+
      (cond 
    
    8+
       [(or (null? x) (null? y)) "NULL"]
    
    9+
       [(= (string->number-sum x) (string->number-sum y)) "TRUE"]
    
    10+
       [else "FALSE"]))
    
Recursion
Algorithms
Computability Theory
Theoretical Computer Science
Arrays
Methods
Functions
Object-oriented Programming
Control Flow
Basic Language Features
Fundamentals
Classes
Code
Diff
  • #lang racket
    (provide flip)
    (define (flip xs)
      (define (inner xs result)
              (if (= (length xs) 0) 
                result 
                (inner (cdr xs) 
                       (append (list
                        (if (list? (car xs)) (inner (car xs) (list)) (car xs))) 
                        result))))
      (inner xs (list)))
      
  • 1
    (ns flip.core)
    
    2
    3
    (defn flip [xs]
    
    4
      (if (reversible? xs) 
    
    5
        (map flip (reverse xs))
    
    6
        xs))
    
    1+
    #lang racket
    
    2+
    (provide flip)
    
    3+
    (define (flip xs)
    
    4+
      (define (inner xs result)
    
    5+
              (if (= (length xs) 0) 
    
    6+
                result 
    
    7+
                (inner (cdr xs) 
    
    8+
                       (append (list
    
    9+
                        (if (list? (car xs)) (inner (car xs) (list)) (car xs))) 
    
    10+
                        result))))
    
    11+
      (inner xs (list)))
    
    12+
      
    
Code
Diff
  • let factorial n =
      let rec loop n result = match n with
      | 0 -> result
      | _ -> loop (n - 1) (result * n) in
      loop n 1;; 
  • 1
    def factorial(n):
    
    2
        # your code goes here
    
    3
        return
    
    1+
    let factorial n =
    
    2+
      let rec loop n result = match n with
    
    3+
      | 0 -> result
    
    4+
      | _ -> loop (n - 1) (result * n) in
    
    5+
      loop n 1;; 
    
Loading more items...