Begin a new Kumite
Search
About
  • Filter by Language:
  • Kumite (ko͞omiˌtā) is the practice of taking techniques learned from Kata and applying them through the act of freestyle sparring.

    You can create a new kumite by providing some initial code and optionally some test cases. From there other warriors can spar with you, by enhancing, refactoring and translating your code. There is no limit to how many warriors you can spar with.

    A great use for kumite is to begin an idea for a kata as one. You can collaborate with other code warriors until you have it right, then you can convert it to a kata.

An implementation of the Sieve of Eratosthenes for finding prime numbers, fully focusing on performance.

The biggest performance gains come from forcing data set manipluation loops to be performed in the C-level code inside Python and not inside loops within the source code of the sieve. The places where this is used in particular are:

  • Striking out compounds in the sieve using the list[start::skip] = list syntax
  • Creating the final list of primes by using compress() to filter primes from the sieve
from math import sqrt, ceil
from itertools import compress

def sieve(until):
    if until < 2:
        return []
    store_len = until >> 1
    is_prime = [True] * store_len
    for offset, number in enumerate(range(3, int(sqrt(until)) + 1, 2)):
        if is_prime[offset]:
            first_compound_at = (number*number-3) >> 1
            nr_of_compounds = int(ceil((store_len-first_compound_at) / number))
            is_prime[first_compound_at::number] = [False] * nr_of_compounds
    return [2] + list(compress(range(3, until + 1, 2), is_prime))
Algorithms

This is my implementation of the Baillie-PSW prime number test. It is my response to a kumite title that claimed a fast prime test, while the implemented check was not actually that fast.

The response as provided by the isPrime() function is not simply a boolean, but instead a tuple providing two values: a boolean indicating probably primality and a string describing the test to lead to the provided conclusing.
Knowing the actual test that triggered the outcome has proven a very valuable tool during development. If this were production code, I'd most likely make the isPrime() function return a boolean directly.

It was great fun to puzzle together all the required pieces and to translate mathmatical notation into working programming code! I learned a lot of new things about modular arithmatics.

Code
Diff
  • from math import sqrt, ceil
    from itertools import compress
    
    TRIAL_DIVISION_UNTIL=1000
    
    
    def isPrime(n):
        """This primality check implements the composite Baillie-PSW test.
           See: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
    
           Input:
               n: the number to check
           Output:
               a tuple containing two elements:
               - True if (probable) prime, False otherwise
               - The name of the test that lead to that conclusion
           """
        if not isInteger(n):
            return (False, "not an integer")
        if isBelowLowestPrime(n):
            return (False, "below lowest prime")
        if isLowPrime(n):
            return (True, "low prime")
        if isTrialDivisionCompound(n):
            return (False, "trial division")
        if not isRabinMillerProbablePrime(n):
            return (False, "rabin-miller")
        if isPerfectSquare(n):
            return (False, "perfect square")
        if not isLucasProbablePrime(n):
            return (False, "lucas")
        return (True, "passed all tests")
    
    
    def isInteger(n):
        return int(n) == n
            
            
    def isBelowLowestPrime(n):
        return n < 2
    
    
    def isLowPrime(n):
        return (
            n <= TRIAL_DIVISION_UNTIL and
            n in lowPrimes
        )
    
    
    def isTrialDivisionCompound(n):
        return any(
            n % prime == 0
            for prime in lowPrimes
            if prime < n
        )
    
    
    def isRabinMillerProbablePrime(n):
        """Based on pseudo code for the Rabin-Miller algorithm.
           See: https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
           This simple version implements only a single pass using base 2,
           as prescribed by the Baillie-PSW specification."""
        (factor, exponent) = factorizeBase2(n - 1)
        x = pow(2, factor, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(exponent - 1):
            x = pow(x, 2, n)
            if x == 1:
                return False
            elif x == n - 1:
                return True
        return False
    
    
    def isPerfectSquare(n):
        """A quick check to make sure that no perfect squares are fed to the
           Lucas probable prime check."""
        return isqrt(n) ** 2 == n
    
    
    def isqrt(n):
        """Integer square root, see:
          https://en.wikipedia.org/wiki/Integer_square_root"""
        x = n
        y = (x + 1) >> 1
        while y < x:
            x = y
            y = (x + n // x) >> 1
        return x
    
    
    def isLucasProbablePrime(n):
        """Code based on "Implementing a Lucas probable prime test" to be found at:
           https://en.wikipedia.org/wiki/Lucas_pseudoprime"""
    
        def getLucasSequenceInputAsSuggestedBySelfridge():
            seq = ((-1 if i&1 else 1) * (i*2 + 5) for i in range(0, n>>1))
            D = next((D for D in seq if jacobi(D, n) == -1))
            Q = (1 - D) // 4
            P = 1
            return D, Q, P
    
        D, Q, P = getLucasSequenceInputAsSuggestedBySelfridge()
    
        def computeLucasValue(subscript):
            U = V = k = 0
            for digit in format(subscript, "b"):
                U, V, k = doubleK(U, V, k)
                if digit == "1":
                    U, V, k = incrementK(U, V, k)
            return U, V, subscript
    
        def doubleK(U, V, subscript):
            return (U*V) % n,  (pow(V, 2, n) - 2 * pow(Q, subscript, n)) % n, subscript << 1
    
        def incrementK(U, V, subscript):
            U, V = (P*U + V), (D*U + P*V)
            makeEven = lambda x: x+n if x&1 else x
            div2modn = lambda x: (x >> 1) % n
            return (div2modn(makeEven(U)), div2modn(makeEven(V)), subscript+1)
    
        # Weak check.
        U, V, k = computeLucasValue(n+1)
        if U != 0:
            return False
    
        # Strong check.
        (factor, exponent) = factorizeBase2(n + 1)
        U, V, k = computeLucasValue(factor)
        if U == 0 or V == 0:
            return True
        for r in range(exponent-1):
            U, V, k = doubleK(U, V, k)
            if V == 0:
                return True
    
    
    def factorizeBase2(factor, exponent=0):
        """Factor out 2 from a number. For example factorizeBase2(80) returns (5, 4),
           which indicates that 2 ** 5 + 4 == 80."""
        if factor&1:
            return (factor, exponent)
        return factorizeBase2(factor >> 1, exponent + 1)
    
    
    def jacobi(a, n):
        """Compute the Jacobi symbol. The code uses ideas from:
           https://www.academia.edu/1012630/A_binary_algorithm_for_the_Jacobi_symbol"""
        t = 1
        while a:
            if a < 0:
                a = -a
                if n&3 == 3: t = -t
            while not a&1:
                a = a >> 1
                if n&7 == 3 or n&7 == 5: t = -t
            if (a < n):
                a, n = n, a
                if a&3 == 3 and n&3 == 3: t = -t
            a = (a - n) >> 1
            if n&7 == 3 or n&7 == 5: t = -t
        return t if n == 1 else 0
    
    
    def sieve(until):
        """This is an optimized sieve-algorithm that I created for an exercism.io assignment.
           On my system, it is able to produce primes until 10,000,000 in half a second.
           See: http://exercism.io/submissions/a6085623b76a6747d300420e"""
        if until < 2:
            return []
        store_len = until >> 1
        is_prime = [True] * store_len
        for offset, number in enumerate(range(3, int(sqrt(until)) + 1, 2)):
            if is_prime[offset]:
                first_compound_at = (number*number-3) >> 1
                nr_of_compounds = int(ceil((store_len-first_compound_at) / number))
                is_prime[first_compound_at::number] = [False] * nr_of_compounds
        return [2] + list(compress(range(3, until + 1, 2), is_prime))
    
    
    lowPrimes = set(sieve(TRIAL_DIVISION_UNTIL))
  • 1-import math
    2-def isprime(num):
    3- if num<2 or int(num)!=num: return False
    4- if not num%2 and num>2: return False
    5- for n in range(3,math.ceil((num-1)**.5)+1,2):
    6- if not num%n:
    7- return False
    8- return True
    1+from math import sqrt, ceil
    2+from itertools import compress
    3+
    4+TRIAL_DIVISION_UNTIL=1000
    5+
    6+
    7+def isPrime(n):
    8+ """This primality check implements the composite Baillie-PSW test.
    9+ See: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
    10+
    11+ Input:
    12+ n: the number to check
    13+ Output:
    14+ a tuple containing two elements:
    15+ - True if (probable) prime, False otherwise
    16+ - The name of the test that lead to that conclusion
    17+ """
    18+ if not isInteger(n):
    19+ return (False, "not an integer")
    20+ if isBelowLowestPrime(n):
    21+ return (False, "below lowest prime")
    22+ if isLowPrime(n):
    23+ return (True, "low prime")
    24+ if isTrialDivisionCompound(n):
    25+ return (False, "trial division")
    26+ if not isRabinMillerProbablePrime(n):
    27+ return (False, "rabin-miller")
    28+ if isPerfectSquare(n):
    29+ return (False, "perfect square")
    30+ if not isLucasProbablePrime(n):
    31+ return (False, "lucas")
    32+ return (True, "passed all tests")
    33+
    34+
    35+def isInteger(n):
    36+ return int(n) == n
    37+
    38+
    39+def isBelowLowestPrime(n):
    40+ return n < 2
    41+
    42+
    43+def isLowPrime(n):
    44+ return (
    45+ n <= TRIAL_DIVISION_UNTIL and
    46+ n in lowPrimes
    47+ )
    48+
    49+
    50+def isTrialDivisionCompound(n):
    51+ return any(
    52+ n % prime == 0
    53+ for prime in lowPrimes
    54+ if prime < n
    55+ )
    56+
    57+
    58+def isRabinMillerProbablePrime(n):
    59+ """Based on pseudo code for the Rabin-Miller algorithm.
    60+ See: https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
    61+ This simple version implements only a single pass using base 2,
    62+ as prescribed by the Baillie-PSW specification."""
    63+ (factor, exponent) = factorizeBase2(n - 1)
    64+ x = pow(2, factor, n)
    65+ if x == 1 or x == n - 1:
    66+ return True
    67+ for _ in range(exponent - 1):
    68+ x = pow(x, 2, n)
    69+ if x == 1:
    70+ return False
    71+ elif x == n - 1:
    72+ return True
    73+ return False
    74+
    75+
    76+def isPerfectSquare(n):
    77+ """A quick check to make sure that no perfect squares are fed to the
    78+ Lucas probable prime check."""
    79+ return isqrt(n) ** 2 == n
    80+
    81+
    82+def isqrt(n):
    83+ """Integer square root, see:
    84+ https://en.wikipedia.org/wiki/Integer_square_root"""
    85+ x = n
    86+ y = (x + 1) >> 1
    87+ while y < x:
    88+ x = y
    89+ y = (x + n // x) >> 1
    90+ return x
    91+
    92+
    93+def isLucasProbablePrime(n):
    94+ """Code based on "Implementing a Lucas probable prime test" to be found at:
    95+ https://en.wikipedia.org/wiki/Lucas_pseudoprime"""
    96+
    97+ def getLucasSequenceInputAsSuggestedBySelfridge():
    98+ seq = ((-1 if i&1 else 1) * (i*2 + 5) for i in range(0, n>>1))
    99+ D = next((D for D in seq if jacobi(D, n) == -1))
    100+ Q = (1 - D) // 4
    101+ P = 1
    102+ return D, Q, P
    103+
    104+ D, Q, P = getLucasSequenceInputAsSuggestedBySelfridge()
    105+
    106+ def computeLucasValue(subscript):
    107+ U = V = k = 0
    108+ for digit in format(subscript, "b"):
    109+ U, V, k = doubleK(U, V, k)
    110+ if digit == "1":
    111+ U, V, k = incrementK(U, V, k)
    112+ return U, V, subscript
    113+
    114+ def doubleK(U, V, subscript):
    115+ return (U*V) % n, (pow(V, 2, n) - 2 * pow(Q, subscript, n)) % n, subscript << 1
    116+
    117+ def incrementK(U, V, subscript):
    118+ U, V = (P*U + V), (D*U + P*V)
    119+ makeEven = lambda x: x+n if x&1 else x
    120+ div2modn = lambda x: (x >> 1) % n
    121+ return (div2modn(makeEven(U)), div2modn(makeEven(V)), subscript+1)
    122+
    123+ # Weak check.
    124+ U, V, k = computeLucasValue(n+1)
    125+ if U != 0:
    126+ return False
    127+
    128+ # Strong check.
    129+ (factor, exponent) = factorizeBase2(n + 1)
    130+ U, V, k = computeLucasValue(factor)
    131+ if U == 0 or V == 0:
    132+ return True
    133+ for r in range(exponent-1):
    134+ U, V, k = doubleK(U, V, k)
    135+ if V == 0:
    136+ return True
    137+
    138+
    139+def factorizeBase2(factor, exponent=0):
    140+ """Factor out 2 from a number. For example factorizeBase2(80) returns (5, 4),
    141+ which indicates that 2 ** 5 + 4 == 80."""
    142+ if factor&1:
    143+ return (factor, exponent)
    144+ return factorizeBase2(factor >> 1, exponent + 1)
    145+
    146+
    147+def jacobi(a, n):
    148+ """Compute the Jacobi symbol. The code uses ideas from:
    149+ https://www.academia.edu/1012630/A_binary_algorithm_for_the_Jacobi_symbol"""
    150+ t = 1
    151+ while a:
    152+ if a < 0:
    153+ a = -a
    154+ if n&3 == 3: t = -t
    155+ while not a&1:
    156+ a = a >> 1
    157+ if n&7 == 3 or n&7 == 5: t = -t
    158+ if (a < n):
    159+ a, n = n, a
    160+ if a&3 == 3 and n&3 == 3: t = -t
    161+ a = (a - n) >> 1
    162+ if n&7 == 3 or n&7 == 5: t = -t
    163+ return t if n == 1 else 0
    164+
    165+
    166+def sieve(until):
    167+ """This is an optimized sieve-algorithm that I created for an exercism.io assignment.
    168+ On my system, it is able to produce primes until 10,000,000 in half a second.
    169+ See: http://exercism.io/submissions/a6085623b76a6747d300420e"""
    170+ if until < 2:
    171+ return []
    172+ store_len = until >> 1
    173+ is_prime = [True] * store_len
    174+ for offset, number in enumerate(range(3, int(sqrt(until)) + 1, 2)):
    175+ if is_prime[offset]:
    176+ first_compound_at = (number*number-3) >> 1
    177+ nr_of_compounds = int(ceil((store_len-first_compound_at) / number))
    178+ is_prime[first_compound_at::number] = [False] * nr_of_compounds
    179+ return [2] + list(compress(range(3, until + 1, 2), is_prime))
    180+
    181+
    182+lowPrimes = set(sieve(TRIAL_DIVISION_UNTIL))

This is a fix for the published but broken kata

function isArray(arr) {
  return Object.prototype.toString.call(arr) === "[object Array]";
};
Code
Diff
  • require 'rubygems'
    
    #gems are stored in a hash with the key set to the name of the gem and the value is the version.
    #the trick is to get the hash to an array and join the version number to the gem name.
    #Feedback appreciated.
    
    def local_gems
       Gem::Specification.sort_by{ |g| [g.name.downcase, g.version] }.group_by{ |g| g.name }
    end
    
    puts local_gems.map{ |name, specs| 
      [ 
        name,
        specs.map{ |spec| spec.version.to_s }.join(',')
      ].join(' ') 
    }
  • 1-puts `gem list`
    1+require 'rubygems'
    2+
    3+#gems are stored in a hash with the key set to the name of the gem and the value is the version.
    4+#the trick is to get the hash to an array and join the version number to the gem name.
    5+#Feedback appreciated.
    6+
    7+def local_gems
    8+ Gem::Specification.sort_by{ |g| [g.name.downcase, g.version] }.group_by{ |g| g.name }
    9+end
    10+
    11+puts local_gems.map{ |name, specs|
    12+ [
    13+ name,
    14+ specs.map{ |spec| spec.version.to_s }.join(',')
    15+ ].join(' ')
    16+}
Code
Diff
  • require 'prime'
    
    def is_prime(n)
       n.prime?
    end
  • 1+require 'prime'
    2+
    11 def is_prime(n)
    22 n.prime?
    33 end
ES2015
Babel
Objects

Joeun's implementation of the pick function in the 'underscore' library. I have extended the library with a new function with a clever name. :) Called 'flick' which is the inverse of 'pick'. Some object/booger picking operations. lol

Code
Diff
  • var _ = {};
    
    // Joeun's Pick implementation (GREAT JOB!)
    _.pick = (target, ...keys) => {
      if (typeof keys[0] == 'function') {
    
        var predicate = keys[0];
        keys = Object.keys(target);
        
        return keys.reduce((obj, key) => {
          return predicate(target[key], key, target) ? (obj[key] = target[key], obj) : obj;
        }, {})
      }
    
      return keys.reduce((obj, key) => {
        return obj[key] = target[key], obj;
      }, {});
    };
    
    // Robert.Cutright's implementation of the inverse of pick (called flick);
    // In other words, you supply the keys you want to throw away.
    _.flick = (target, ...keys) => {
      if (typeof keys[0] == 'function') {
    
        var predicate = keys[0];
        keys = Object.keys(target);
        
        return keys.reduce((obj, key) => {
          return predicate(target[key], key, target) ? obj : (obj[key] = target[key], obj);
        }, {})
      }
    
      var obj = Object.assign({}, target);
      Object.keys(obj).filter(key => keys.includes(key) ? delete obj[key] : obj[key]);
      return obj;
    };
    
  • 11 var _ = {};
    22
    3+// Joeun's Pick implementation (GREAT JOB!)
    33 _.pick = (target, ...keys) => {
    44 if (typeof keys[0] == 'function') {
    6+
    55 var predicate = keys[0];
    66 keys = Object.keys(target);
    77
    88 return keys.reduce((obj, key) => {
    99 return predicate(target[key], key, target) ? (obj[key] = target[key], obj) : obj;
    1010 }, {})
    1111 }
    1212
    1313 return keys.reduce((obj, key) => {
    1414 return obj[key] = target[key], obj;
    1515 }, {});
    18+};
    19+
    20+// Robert.Cutright's implementation of the inverse of pick (called flick);
    21+// In other words, you supply the keys you want to throw away.
    22+_.flick = (target, ...keys) => {
    23+ if (typeof keys[0] == 'function') {
    24+
    25+ var predicate = keys[0];
    26+ keys = Object.keys(target);
    27+
    28+ return keys.reduce((obj, key) => {
    29+ return predicate(target[key], key, target) ? obj : (obj[key] = target[key], obj);
    30+ }, {})
    31+ }
    32+
    33+ var obj = Object.assign({}, target);
    34+ Object.keys(obj).filter(key => keys.includes(key) ? delete obj[key] : obj[key]);
    35+ return obj;
    1616 };
Fundamentals
Lambdas
Functional Programming
Functions
Declarative Programming
Control Flow
Basic Language Features

Lambda recursion.

/**
 * Created by ice1000 on 2017/5/2.
 *
 * @author ice1000
 */
fun main(args: Array<String>) {
	fun lambda(it: Int): Int =
			if (it <= 2) 1 else lambda(it - 1) + lambda(it - 2)
	(1..10).map(::lambda) // .forEach(::println)

	var lambda2: (Int) -> Int = { it }
	lambda2(1)
	lambda2 = { if (it <= 2) 1 else lambda(it - 1) + lambda(it - 2) }
	(1..10).map(lambda2) // .forEach(::println)
}

Takes the square root of an int and returns a double.

double sqrt (int a,int accuracy=20) {
  double out = a;
  for(int i=0;i<accuracy;i++) {
    out = (out+a/out)/2;
  }
  return out;
}
Fundamentals

'\n' is faster and more effective than std::endl.

Code
Diff
  • #include <iostream>
    
    using namespace std;
    int helloCplusplus(){
      cout << "Hello Cplusplus" << '\n';
      return 0;
    }
  • 11 #include <iostream>
    22
    33 using namespace std;
    44 int helloCplusplus(){
    5- cout << "Hello Cplusplus" << endl;
    5+ cout << "Hello Cplusplus" << '\n';
    66 return 0;
    77 }

Parses an expression.

def parse(expr): #The main parser
  ps = 0 #Number of open parentheses
  cval = 0 #Current value
  op = "+" #Current operation
  accum = "" #Accumulating value
  for i in range(len(expr)):
    c = expr[i]
    if c in ["+","-"] and not ps: #Operation not inside parens
      if op=="+": #Addition
        cval+=parse_fact(accum)
      else: #Subtraction
        cval-=parse_fact(accum)
      accum = "" #Reset the value
      op = c #New operation once that was calculated
    else:
      if c=="(": ps+=1 #Open paren
      if c==")": ps-=1 #Close paren
      accum+=c #Add a character to accumulating value
  if op=="+": #Do the operation one more time
    cval+=parse_fact(accum)
  else:
    cval-=parse_fact(accum)
  return cval
def parse_fact(term):
  ps = 0
  cval = 1
  op = "*"
  accum = ""
  for i in range(len(term)):
    c = term[i]
    if c in ["*","/"] and not ps:
      if op=="*":
        cval*=parse_val(accum)
      else:
        cval/=parse_val(accum)
      accum = ""
      op = c
    else:
      if c=="(": ps+=1
      if c==")": ps-=1
      accum+=c
  if op=="*":
    cval*=parse_val(accum)
  else:
    cval/=parse_val(accum)
  return cval
def parse_val(val):
  if val[0] == "(": #Parenthetical expression
    return parse(val[1:-1]) #Cut off parentheses and reevaluate
  else:
    return float(val) #Not parenthetical
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;
}

If it does not work, just say :).

template<typename T>
T add(T a, T b){
	return a-(-b);
}
Code
Diff
  • public class Primes {
      public static boolean isAPrime(int number) {
        if(number == 1 || number == 2) return true;
        else {
          for(int i = 3; i*i < number; i +=2) {
            if (number % i == 0) return false;
          }
        }
        return true;
      }
    }
  • 11 public class Primes {
    22 public static boolean isAPrime(int number) {
    3+ if(number == 1 || number == 2) return true;
    4+ else {
    5+ for(int i = 3; i*i < number; i +=2) {
    6+ if (number % i == 0) return false;
    7+ }
    8+ }
    33 return true;
    44 }
    55 }
Algorithms
Mathematics
Numbers

For greater efficiency, I give you a lookup table that cuts down execution time by up to 40%!

6035ms from 10958ms

Code
Diff
  • def factorial(x):
        result = 1
        if len(factorial.lookup) <= x:
            factorial.lookup = [1] * (x + 1)
            for i in range(2, x + 1):
                result *= i
                factorial.lookup[i] = result
            return result
        return factorial.lookup[x]
    factorial.lookup = []
  • 11 def factorial(x):
    22 result = 1
    3- for i in range(2, x + 1):
    4- result *= i
    5- return result
    3+ if len(factorial.lookup) <= x:
    4+ factorial.lookup = [1] * (x + 1)
    5+ for i in range(2, x + 1):
    6+ result *= i
    7+ factorial.lookup[i] = result
    8+ return result
    9+ return factorial.lookup[x]
    10+factorial.lookup = []
Code
Diff
  • def ls(dir):
        import os    
        return(os.listdir(dir))
  • 1-import os
    2-print(os.listdir('directorypath'))# Replace 'directorypath' with path to directory
    1+def ls(dir):
    2+ import os
    3+ return(os.listdir(dir))
Code
Diff
  • import java.util.*;
    class Solution {
      
    	      private int[] getNumDigits(int number) {
            int[] digits = new int[10];
    
            while (number != 0) {
                digits[number % 10]++;
                number = number / 10;
            }
    
            return digits;
        }
    
        public int retSmallestPositiveInteger() {
    
            for (int num = 100; num < Integer.MAX_VALUE; num++) {
                boolean isEquals = true;
                int[] digits = getNumDigits(num);
                for (int i = 2; (i <= 6) && isEquals; i++) {
                    isEquals = isEquals && Arrays.equals(digits, getNumDigits(num * i));
                }
                if (isEquals)
                    return num;
            }
            return 0;
        }
    }
  • 11 import java.util.*;
    22 class Solution {
    33
    4-
    5- public static int retSmallestPositiveInteger() {
    6- for(int i=1; ; i++) {
    7- if(hasSameDigits(i, i*2) && hasSameDigits(i, i*3) && hasSameDigits(i, i*4) && hasSameDigits(i, i*5) && hasSameDigits(i, i*6))
    8- return i;
    9- }
    10- }
    11-
    12- private static boolean hasSameDigits(int x, int y) {
    13- char[] xdigits = Integer.toString(x).toCharArray();
    14- char[] ydigits = Integer.toString(y).toCharArray();
    15- Arrays.sort(xdigits);
    16- Arrays.sort(ydigits);
    17- return Arrays.equals(xdigits, ydigits);
    18- }
    4+ private int[] getNumDigits(int number) {
    5+ int[] digits = new int[10];
    6+
    7+ while (number != 0) {
    8+ digits[number % 10]++;
    9+ number = number / 10;
    10+ }
    11+
    12+ return digits;
    13+ }
    14+
    15+ public int retSmallestPositiveInteger() {
    16+
    17+ for (int num = 100; num < Integer.MAX_VALUE; num++) {
    18+ boolean isEquals = true;
    19+ int[] digits = getNumDigits(num);
    20+ for (int i = 2; (i <= 6) && isEquals; i++) {
    21+ isEquals = isEquals && Arrays.equals(digits, getNumDigits(num * i));
    22+ }
    23+ if (isEquals)
    24+ return num;
    25+ }
    26+ return 0;
    27+ }
    1919 }

Kumite Experiment!

public class HelloWorld 
{

  public static int Execute()
  {
    System.out.println("My first Kumite");
    return 1;
  }
}
Code
Diff
  • def sortinggggggggggg (arr) :
      Soreteddddd = sorted (arr)
      print (Soreteddddd)
      return Soreteddddd
    sortinggggggggggg ([2,0,25,3])
    
  • 11 def sortinggggggggggg (arr) :
    22 Soreteddddd = sorted (arr)
    3+ print (Soreteddddd)
    33 return Soreteddddd
    44 sortinggggggggggg ([2,0,25,3])
Code
Diff
  • # caesar cipher shifted of 13 characters with maketrans for python 2.7
    from string import maketrans as mktr, ascii_uppercase as asuc
    
    def caesar(s):
        return s.translate(mktr(asuc, asuc[13:] + asuc[:13]))
    
  • 11 # caesar cipher shifted of 13 characters with maketrans for python 2.7
    2-from string import maketrans
    3-import string
    2+from string import maketrans as mktr, ascii_uppercase as asuc
    3+
    44 def caesar(s):
    5- print(s)
    6- s=s.translate(maketrans(string.ascii_uppercase, string.ascii_uppercase[13:]+string.ascii_uppercase[:13]))
    7- return s
    5+ return s.translate(mktr(asuc, asuc[13:] + asuc[:13]))

Sometimes one has a vector with pairs (key, value), where one wants to fold over all the values with the same key.
What is the best way to do that in Rust?

The example uses a vector, but perhaps it would be better with an iterator as argument, to make it more general?

fn reduce<TK, TV, TS, F>(v : Vec<(TK, TV)>,
                     s : TS,
                     f : F) -> Vec<(TK, TV)>
                     where F : Fn(TS, TV) -> TS {
    // Code
    vec![]
}

Code returns the int that is different from all other ints in an array. Function takes odd size array that contains all the same ints except for 1

int stray(std::vector<int> numbers) {
    
    for(auto n = numbers.begin(); n != numbers.end(); ++n ){
        if (*n != numbers[0]) {
            if (*n != *(n + 1))
                return *n;
            else
                return numbers[0];
        }
    }
};
Strings

Last Character of a string in JS.

Code
Diff
  • const lastChar=(s)=>s.slice(-1)
    
  • 1-def last_char(str):
    2- return str[-1]
    1+const lastChar=(s)=>s.slice(-1)
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char plaintext[100];
char ciphertext[100];
int length;
int key;
  cout<<"enter the plain message\n\n";
  cin.getline(plaintext,99,'\n');
cout<<"enter the key :";
cin>>key;
cout<<"----------\n";
cout<<"the cipher message\n\n";
length=strlen(plaintext);
int i = 0;
	 for(i=0;i<length;i++)
{
	if(plaintext[i]==' ')
{
  ciphertext[i]=' ';
  cout<<ciphertext[i];
  continue;
}
  int y=(int)plaintext[i];
  if (y>96)
{
  y=y-32;
  plaintext[i]=(char)y;
}
int x =((((int)plaintext[i]-65)+key)%26)+65;
ciphertext[i]=(char)x;
cout<<ciphertext[i];
}
cout<<"\n\n";
return(0);
}

Saved some brackets :)

Code
Diff
  • function add(a, b){
      return a- -b;
    }
  • 11 function add(a, b){
    2- return a - (-b);
    2+ return a- -b;
    33 }
Numbers
Integers
Algorithms

Find number of digits with an unrolled div loop.

Code
Diff
  • // Unrolled div loop
    fn digits(mut n: u64) -> usize {
      let mut l = 1;
      loop {
        if n < 10 {
          return l;
        }
        if n < 100 {
          return l + 1;
        }
        if n < 1000 {
          return l + 2;
        }
        if n < 10000 {
          return l + 3;
        }
        n /= 10000;
        l += 4;
      }
    }
  • 1+// Unrolled div loop
    11 fn digits(mut n: u64) -> usize {
    2- let mut l = 1;
    3- while n >= 10 {
    4- n /= 10;
    5- l += 1;
    3+ let mut l = 1;
    4+ loop {
    5+ if n < 10 {
    6+ return l;
    66 }
    7- l
    8+ if n < 100 {
    9+ return l + 1;
    10+ }
    11+ if n < 1000 {
    12+ return l + 2;
    13+ }
    14+ if n < 10000 {
    15+ return l + 3;
    16+ }
    17+ n /= 10000;
    18+ l += 4;
    19+ }
    88 }
Code
Diff
  • {-# LANGUAGE QuasiQuotes, TemplateHaskell, TypeFamilies #-}
    {-# LANGUAGE OverloadedStrings, GADTs, FlexibleContexts, MultiParamTypeClasses #-}
    {-# LANGUAGE NoMonomorphismRestriction, GeneralizedNewtypeDeriving #-}
    module Movies where
    import Database.Persist (insertMany)
    import Database.Persist.Sqlite (runSqlite, runMigration)
    import Database.Persist.TH (mkPersist, mkMigrate, persistUpperCase, share, sqlSettings)
    share [mkPersist sqlSettings, mkMigrate "migrateTables"] [persistUpperCase|
    Movies
       title    String
       year     Int
       rating   Int
       deriving Eq Show
    |]
    
    mkMoviesDB :: IO ()
    mkMoviesDB = runSqlite "/tmp/movies.db" $ do
      runMigration migrateTables
      insertMany
        [ Movies "Rise of the Planet of the Apes" 2011 77
        , Movies "Dawn of the Planet of the Apes" 2014 91
        , Movies "Alien" 1979 97
        , Movies "Aliens" 1986 98
        , Movies "Mad Max" 1979 95
        , Movies "Mad Max 2: The Road Warrior" 1981 100
        ]
      return ()
    
  • 99 Movies
    1010 title String
    1111 year Int
    1212 rating Int
    1313 deriving Eq Show
    1414 |]
    15+
    1515 mkMoviesDB :: IO ()
    1616 mkMoviesDB = runSqlite "/tmp/movies.db" $ do
    1717 runMigration migrateTables
    1818 insertMany
    1919 [ Movies "Rise of the Planet of the Apes" 2011 77
    2020 , Movies "Dawn of the Planet of the Apes" 2014 91
    2121 , Movies "Alien" 1979 97
    2222 , Movies "Aliens" 1986 98
    2323 , Movies "Mad Max" 1979 95
    2424 , Movies "Mad Max 2: The Road Warrior" 1981 100
    2525 ]
    2626 return ()
const html = '<iframe width=100% height=640 src="https://stemkoski.github.io/Three.js/Particle-Engine.html"></iframe>';
console.log(html);
Code
Diff
  • def is_prime(n):
        return n == 2 or n > 1 and all(n % i for i in range(3, int(n**0.5)+1, 2))
  • 11 def is_prime(n):
    2- return n > 1 and all(n % i for i in range(2, int(n**0.5)+1))
    2+ return n == 2 or n > 1 and all(n % i for i in range(3, int(n**0.5)+1, 2))
Code
Diff
  • def distance_count(x, y):
        return sum((xi-yi)**2 for xi, yi in zip(x, y))**0.5
    
  • 1-def distance_count(a,b):
    2- return sum([(i-j)**2 for (i,j) in zip(a,b)])**0.5
    3-
    1+def distance_count(x, y):
    2+ return sum((xi-yi)**2 for xi, yi in zip(x, y))**0.5
Code
Diff
  • def get_list(l):
        return ' '.join(l)
  • 1-def get_list(may):
    2- new_str = ''
    3- for i in may:
    4- new_str += i + ' '
    5- return new_str[:-1]
    1+def get_list(l):
    2+ return ' '.join(l)
console.log('Hola mundo');
Ruby on Rails
Frameworks
rails
Ruby Gems

In this varation, I have refactored the code so that the execute helper wraps up the transaction rollback as part of its method call. It also will try to parse the response as json and provide that as the 2nd argument, DRYing up the code as more tests are added.

Mathematics
Algorithms
Numbers

Removed duplicate code and multiple executions of fmod by calculating it before all the places where it's needed, reducing probability of copy/paste error and slightly improving performance.
Also added a space before every left bracket, for readability (personal preference).

Code
Diff
  • function calcTokenCost($price, $token) {
        if ($price == 0 && $token == 0) {
            return 0;
        }
        if ($price < $token) {
            return $token;
        }
        $mod = fmod($price, $token);
        if ($mod < ($token / 2)) {
            return $price - $mod;
        }
        return $price + $token - $mod;
    }
  • 1-function calcTokenCost($price, $token){
    2- if ($price == 0 && $token == 0){
    1+function calcTokenCost($price, $token) {
    2+ if ($price == 0 && $token == 0) {
    33 return 0;
    44 }
    5- if ($price < $token){
    5+ if ($price < $token) {
    66 return $token;
    77 }
    8- if (fmod($price, $token) < ($token / 2)){
    9- return $price - fmod($price, $token);
    8+ $mod = fmod($price, $token);
    9+ if ($mod < ($token / 2)) {
    10+ return $price - $mod;
    1010 }
    11- return $price + $token - fmod($price, $token);
    12+ return $price + $token - $mod;
    1212 }
hsamuelsonFailed Tests

R Tests

plot a quadradic from 0-10, with the equation x^2

print("Hellow")
#THis doesnt work becasue R is not supported yet

It is usefull for algorithmic tasks, where your code has to have certain complexity. It is not a save way of using In/out, so I woudln't reccomend using it somewhere else besides webpages like SPOJ etc. where programms read from standard input and write to standard output. It should compile with newest gcc and -std=c++11 flag.
Try to write your own functions for fixed point types and cstrings! =)

Bibliography:
http://www.algorytm.edu.pl/fast-i-o.html

#include <cstdio>

template <class type>
inline void getUI ( type* des ) // reads unsigned integer from input
{
  register char c = 0;
  while ( c <= ' ' ) c = getc_unlocked(stdin);
  (*des) = 0;
  while ( c > ' ' )
  {
    (*des) = (*des) * 10 + ( c - '0' );
    c = getc_unlocked(stdin);
  }
}
template <class type>
inline void putUI ( type src ) // writes unsigned integer to output
{
  if ( src == 0 )
  {
    putc_unlocked( '0', stdout );
    return;
  }
  register char c [21];
  register short k = 0;
  while ( src > 0 )
  {
    c[k ++] = src % 10 + '0';
    src /= 10;
  }
  -- k;
  while ( k >= 0 )
    putc_unlocked( c[k --], stdout );
}

int main ()
{
  putUI(2000);
}
Code
Diff
  • print("Hello World")
  • 1-cat("Hello World!\n")
    1+print("Hello World")
Testing

When writing python katas, you might want to create modules that can be imported by the solution or tests.

This kata shows how to by manipulating sys.path to allow importing from /home/codewarrior folder and writing a python file there.

import sys
HOME_DIR = '/home/codewarrior'

def make_module(module_name):
    if HOME_DIR not in sys.path:
        sys.path.append(HOME_DIR)

    moduleContent = 'foo = lambda x: x+1'
    with open('{}/{}.py'.format(HOME_DIR, module_name), 'w') as moduleFile:
        moduleFile.write(moduleContent)

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

function lowestPermutedMultiple(n) {
    let base = n;
    let numDigits = n.toString().length;
    let i = 1;
    let solution = i;
    while ((n * i).toString().length <= numDigits) {
        if (base.toString().split('').sort().join('') == (n*i).toString().split('').sort().join('')) {
            solution = i;
        }
        i++;
    }
    return solution;
}
Code
Diff
  • SELECT name FROM greetings
    WHERE upper(greeting) like '%HELLO%';
  • 11 SELECT name FROM greetings
    2-WHERE greeting='Hello';
    2+WHERE upper(greeting) like '%HELLO%';

I needed to iterate a block on a value n times and return the value to solve a kata. Getting f(f(..f(x)..)) applying f n times. This is the trivial solution:

n.times do
  x = f.call(x)
end
return x

As times returns n rather than anything in the block a separate return x is needed after the block. Also x = modified x is needed. Wouldn't it be nice to have something built in for this purpose? like

x.modify(n, &block)

It turns out that we can achieve something pretty close to this with the built in inject. As times without a block returns an Enumerator, as most Enumerable functions do, (yielding increasing numbers), with the daisy chaining of Enumerables, using only the accumulator of inject this works fine:

n.times.inject(x) { |x| block.call(x) }

However this doesn't work :( as inject in this case feeds in the index:

n.times.inject(x, &block)
class Object
  def modify(n)
    return to_enum :modify unless block_given?
    case n
    when Enumerator then n.each.inject(self) { |acc| yield(acc) }
    when Numeric    then n.times.inject(self) { |acc| yield(acc) }
    end    
  end
end

p 5.modify 2.times, &:~@ # flipping bits twice

A really arcaic calculator for pi, that takes ages to get a little precision.

var ex431 = function(tries){
    var inc=0, outc=0, x, y;
    
    while(tries>0){
        x =  Math.random();
        y =  Math.random();
        
        if (x*x + y*y <= 1) inc++;
        else outc++;
        tries--;
    }
    return inc/(inc+outc);
}

Changed s.ToLower() → s.ToUpperInvariant(), fitting msdn recommended best practices for strings.

Code
Diff
  • using System;
    using System.Linq;
    
    public class Kata
    {
        public static int DuplicateCount(string s) => 
            s.ToUpperInvariant()
             .GroupBy(c => c)
             .Count(g => g.Skip(1).Any());
    }
  • 11 using System;
    22 using System.Linq;
    33
    44 public class Kata
    55 {
    66 public static int DuplicateCount(string s) =>
    7- s.ToLower()
    8- .GroupBy(c => c)
    9- .Count(g => g.Skip(1).Any());
    7+ s.ToUpperInvariant()
    8+ .GroupBy(c => c)
    9+ .Count(g => g.Skip(1).Any());
    1010 }
dpleshkovFailed Tests

Quine

This is a quine in Python 2 (Will not work in 3).

_='_=%r;print _%%_';print _%_
Code
Diff
  • module NCR where
    
    --Combinations nCr
    comb:: Integer -> Integer -> Integer
    comb n r = factorial n `div` (factorial r * factorial (n-r))
      where
      factorial n = foldr (*) 1 [2..n]
  • 11 module NCR where
    22
    33 --Combinations nCr
    44 comb:: Integer -> Integer -> Integer
    5-comb n r | n/=r = (factorial n) `div` (factorial r * factorial (n-r) )
    6- | n==r = (factorial n) `div` (factorial r)
    7-
    8-factorial n= foldl (*) 1 [1..n]
    5+comb n r = factorial n `div` (factorial r * factorial (n-r))
    6+ where
    7+ factorial n = foldr (*) 1 [2..n]

Allow for passing parents into the constructor. Also, add some spaces to make code consistent. Also, avoid mutating parents array, just for the sake of it.

Code
Diff
  • class Human {
      constructor (firstName = '', lastName = '', parents = []) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.parents = parents;  // modern family. who takes parental care?
      }
      
      filterMyFamily(humans) {
        return humans.filter(human => human.lastName === this.lastName)
      }
      
      hasParent(p) {
        return this.parents.some(parent => parent === p);
      }
      
      hasChild(c) {
        return c.hasParent(this);
      }
      
      addParent(p) {
        if (!this.hasParent(p)) this.parents = [ ...this.parents, p ];
        return this;
      }
    }
  • 11 class Human {
    2- constructor (firstName = '', lastName = '') {
    2+ constructor (firstName = '', lastName = '', parents = []) {
    33 this.firstName = firstName;
    44 this.lastName = lastName;
    5- this.parents = []; // modern family. who takes parental care?
    5+ this.parents = parents; // modern family. who takes parental care?
    66 }
    7+
    77 filterMyFamily(humans) {
    88 return humans.filter(human => human.lastName === this.lastName)
    99 }
    1010
    11- addParent(p){
    12- if (!this.hasParent(p)) this.parents.push(p);
    13- return this;
    12+ hasParent(p) {
    13+ return this.parents.some(parent => parent === p);
    1414 }
    1515
    16- hasChild(c){
    16+ hasChild(c) {
    1717 return c.hasParent(this);
    1818 }
    1919
    20- hasParent(p){
    21- return this.parents.some(parent => parent === p);
    20+ addParent(p) {
    21+ if (!this.hasParent(p)) this.parents = [ ...this.parents, p ];
    22+ return this;
    2222 }
    2323 }