Ad
eseharavs.深紅心

Fast way to get all the divisors of a number (no sort, Racket)

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)))))
    • #lang racket
    • (provide get-divs)
    • (define (get-divs n)
    • (let* ([end0 (sqrt n)]
    • [end1 (ceiling end0)])
    • (if (= 1 n) (list 1)
    • (let ([sqrt-n (sqrt n)])
    • (define (inner x result-min result-max)
    • (cond
    • [(>= x end1) (append result-min (if (= end0 end1) (cons end1 result-max) result-max))]
    • [(= 0 (modulo n x)) (inner (add1 x)
    • (append result-min (list x))
    • (cons (/ n x) result-max))]
    • [(>= 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))))
    • (inner 2 (list 1) (list n)))))
eseharavs.深紅心

Fast way to get all the divisors of a number (no sort, Racket)

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))))
    • function getDiv(n){
    • let factor0 = [];
    • let factor1 = [];
    • let end0 = Math.sqrt(n);
    • let end1 = Math.ceil(end0);
    • for (let i = 1; i !== end1; ++i) {
    • if (n % i === 0) {
    • factor0.push(i);
    • factor1.unshift(n / i);
    • }
    • }
    • if (end0 === end1) {
    • factor0.push(end0);
    • }
    • factor0.push(...factor1);
    • return factor0;
    • }
    • #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))))
eseharavs.esehara

Fibonacci ( OCaml, Dynamic programming)

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;;
    • 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;;
    • 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;;
eseharavs.wichu

Project Euler - problem 1

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;;
    • let projectEulerProblemOne = [1 .. 999] |> List.filter(fun x -> x % 3 = 0 || x % 5 = 0) |> List.sum
    • 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;;
eseharavs.JohanWiltink

Fibonacci ( OCaml, Recursive memoization)

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;;
    • module Example where
    • open BatBig_int
    • import Data.Semigroup (Endo(..),stimes)
    • fib :: Integer -> Integer
    • fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
    • 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;;
eseharavs.esehara

HeLlOwOrLddddd

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))))
    • #lang racket
    • (provide hellOwOrld)
    • (define (hello-upcase lst result)
    • (define (hello-f n 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)))))))
    • (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-upcase (filter (lambda (x) (not (char-whitespace? x)))
    • (list->string (hello-f 0 (filter (lambda (x) (not (char-whitespace? x)))
    • (string->list (string-downcase str))) (list))))
eseharavs.深紅心

Remove Element from Array

Arrays
Data Types

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;;
    • let remove xs index =
    • let rec remove' (xs, index) =
    • match xs with
    • | [] -> []
    • | x::xs' -> if index = 0 then xs' else x::(remove' (xs', index - 1))
    • in
    • if index < 0 then xs else 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;;
eseharavs.深紅心

Make my numbers formatted

Strings
Data Types
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 [] [];;
    • module Format where
    • 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;;
    • import Data.Bits ((.|.))
    • import Data.Char (chr)
    • f :: Integer -> [Char]
    • f n = f' [chr $ (.|.) 48 $ fromIntegral $ mod n 10] (div n 10) where
    • f' :: [Char] -> Integer -> [Char]
    • f' sol 0 = sol
    • f' acc n = f'' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) acc) (div n 10) where
    • f'' :: [Char] -> Integer -> [Char]
    • f'' sol 0 = sol
    • f'' acc n = f''' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) acc) (div n 10) where
    • f''' :: [Char] -> Integer -> [Char]
    • f''' sol 0 = sol
    • f''' acc n = f' ((:) (chr $ (.|.) 48 $ fromIntegral $ mod n 10) $ (:) ',' acc) (div n 10)
    • 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 [] [];;
eseharavs.深紅心

Merge two sorted lists

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 [];;
    • let rec merge_lists a b =
    • match a, b with
    • | c, [] | [], c -> c
    • | ax::a', bx::_ when ax < bx -> ax::(merge_lists a' b)
    • | _, bx::b' -> bx::(merge_lists b' a)
    • ;;
    • 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 [];;
eseharavs.user41686

HeLlOwOrLddddd

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))))
    • public class HeLlOwOrLddddd {
    • public static String convert(String input) {
    • String salida = "";
    • boolean mayus = true;
    • for (int i=0;i<input.length();i++){
    • if (Character.isLetter(input.charAt(i))){
    • if (mayus){
    • salida+=Character.toUpperCase(input.charAt(i));
    • mayus=false;
    • }else{
    • salida+=Character.toLowerCase(input.charAt(i));
    • mayus=true;
    • }
    • }
    • }
    • return salida;
    • #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))))
eseharavs.Icesyst

and, or and xor without "&&" and "||"

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;;
    • bool Or(bool a, bool b){
    • if(!a){
    • if(!b){
    • return false;
    • }
    • }
    • return true;
    • }
    • bool Xor(bool a, bool b){
    • return a != b;
    • }
    • bool And(bool a, bool b){
    • if(a){
    • if(b){
    • return true;
    • }
    • }
    • return false;
    • }
    • 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;;
eseharavs.user8654865

Number of digits

Numbers
Data Types
Integers
Algorithms
Logic
Code
Diff
  • let number_of_digits x = 
  String.concat "" ["1"; String.make (x - 1) '0'] |> int_of_string;;
    • fn digits(mut n: u64) -> usize {
    • let mut l = 1;
    • while n >= 10 {
    • n /= 10;
    • l += 1;
    • }
    • l
    • }
    • let number_of_digits x =
    • String.concat "" ["1"; String.make (x - 1) '0'] |> int_of_string;;
eseharavs.valeri.burlacu

Sum of the letters (ASCII)

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"]))
    • class Kata{
    • public static String verifySum(String nameOne, String nameTwo) {
    • int[] sumOfNames = new int[]{0, 0};
    • if (nameOne == null || nameTwo == null) {
    • return "NULL";
    • }
    • for (int i = 0; i < nameOne.length(); i++){
    • sumOfNames[0] += nameOne.charAt(i);
    • }
    • for (int i = 0; i < nameTwo.length(); i++){
    • sumOfNames[1] += nameTwo.charAt(i);
    • }
    • return sumOfNames[0] == sumOfNames[1] ? "TRUE" : "FALSE";
    • }
    • }
    • #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"]))
eseharavs.深紅心

Array#flip method

Recursion
Algorithms
Computability Theory
Logic
Theoretical Computer Science
Arrays
Data Types
Methods
Functions
Object-oriented Programming
Control Flow
Basic Language Features
Fundamentals
Programming Paradigms
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)))
    • (ns flip.core)
    • (defn flip [xs]
    • (if (reversible? xs)
    • (map flip (reverse xs))
    • xs))
    • #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)))
eseharavs.pychi

Recursive Factorials

Code
Diff
  • let factorial n =
  let rec loop n result = match n with
  | 0 -> result
  | _ -> loop (n - 1) (result * n) in
  loop n 1;;
    • def factorial(n):
    • # your code goes here
    • return
    • let factorial n =
    • let rec loop n result = match n with
    • | 0 -> result
    • | _ -> loop (n - 1) (result * n) in
    • loop n 1;;
Loading more items...