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.

mmakaay

mmakaay's Kumite #3

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))
mmakaayvs. pythonRules

Fast Prime checker

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))

Recent Relatives:

matt c

Array.isArray FIX

This is a fix for the published but broken kata

function isArray(arr) {
  return Object.prototype.toString.call(arr) === "[object Array]";
};
JordanMack92vs. 10XLFailed Tests

Get Installed Gems

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+}

Recent Relatives:

JordanMack92vs. nekokat

Fast Primality Test in Ruby

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

Recent Relatives:

robert.cutrightvs. Joeun

Pick a value from object using key.

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 };

Recent Relatives:

ice1000Failed Tests

Kotlin lambda recursion

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)
}
pythonRules

Square root

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;
}
ElMagovs. Icesyst

Hello C++!

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 }

Recent Relatives:

pythonRules

Expression parser

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
Icesyst

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

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;
}
Icesyst

add without '+'

If it does not work, just say :).

template<typename T>
T add(T a, T b){
	return a-(-b);
}
offr0advs. Trollderim

Trollderim's Kumite #1

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 }

Recent Relatives:

theropodMusingsvs. pyramidka

Factorial

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 = []

Recent Relatives:

tobbazvs. Subhrajit_

Listing All Files in a Directory

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))

Recent Relatives:

rpc1vs. vkapse

vkapse's Kumite #3

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 }

Recent Relatives:

KChallenge

Hello World!

Kumite Experiment!

public class HelloWorld 
{

  public static int Execute()
  {
    System.out.println("My first Kumite");
    return 1;
  }
}
MrZizoScreamvs. MrZizoScreamFailed Tests

No Loop Sorting Array

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])

Recent Relatives:

pyramidkavs. mmalkavian

caesar cipher shifted of 13 characters with maketrans for python 2.7

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]))

Recent Relatives:

bofh69Failed Tests

Fold over common keys like in the MapReduce pattern?

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![]
}
squidotti

Odd number out

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];
        }
    }
};
አወል እሸቱvs. anonymous_monkey

Last Char

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)

Recent Relatives:

abdul3zizFailed Tests

Monoalphabetic Encryption 

#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);
}
acatalinavs. Khallister

How To: Read the user's solution within your test cases

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 }

Recent Relatives:

henninglivevs. henninglive

Number of digits

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 }

Recent Relatives:

jhoffnervs. wizzupFailed Tests

test - SQLite interaction

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 ()

Recent Relatives:

10XLFailed Tests

Use an Iframe to load a URL in the output or description.

const html = '<iframe width=100% height=640 src="https://stemkoski.github.io/Three.js/Particle-Engine.html"></iframe>';
console.log(html);
MikaelCallvs. gregoryltwong

Check Prime number - quickest

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))

Recent Relatives:

MikaelCallvs. leigaoyi

Calculate the distance of two points in N dimensions

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

Recent Relatives:

anonymous_monkeyvs. theIceberg

Print Hello world From Lists: Beginner's way

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)

Recent Relatives:

UnnamedFailed Tests

Trying to import numpy in Python 3.6.0

import numpy
W01fw00dFailed Tests

Brújula Aquí

console.log('Hola mundo');
jhoffnervs. jhoffner

How To: Test a Rails controller

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.

Recent Relatives:

ricardonunesvs. poalrom

Calculate token cost from a given price and delimiter

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 }

Recent Relatives:

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
d0n14Failed Tests

Fast I/0 ( unsigned integers )

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);
}
hsamuelsonvs. evaristorFailed Tests

Hello R

Code
Diff
  • print("Hello World")
  • 1-cat("Hello World!\n")
    1+print("Hello World")

Recent Relatives:

macobo

How To: Creating new importable python modules

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)
dkollar

Permuted Multiples

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;
}
sarabaduARGvs. DDawson

Basic Select (SQL)

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%';

Recent Relatives:

phaul

iterate function on object n times

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
GoncalertaFailed Tests

Pi Inefficient Calculator

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);
}
KelsonBallvs. emilwall

Playing with the DuplicateCount kata

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 }

Recent Relatives:

dpleshkovFailed Tests

Quine

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

_='_=%r;print _%%_';print _%_
j.hnvs. brander

Combinations

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]

Recent Relatives:

Virzenvs. Virzen

amartis's Kumite #5

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 }

Recent Relatives: