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.

Sometimes right. sometimes wrong.

In line 213.

System.out.println(String.format("isSuccessorMustWait %d ", 4 * 999 / 2));

This will make most problem solved! But not all.

Here can't add because it will buffer overflow.

The test can be right sometimes.

It is strange here. you run first time wrong. But in run second time right.
When you change to jave 8 it failed again. Run again , it right.

/*
 * HCLHLock.java
 *
 * Created on April 13, 2006, 9:28 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

/**
 * Hierarchical CLH Lock
 *
 * @author Maurice Herlihy
 */
public class HCLHLock implements Lock {
  
      public static class ThreadID {
        /**
         * The next thread ID to be assigned
         **/
        private static volatile int nextID = 0;
        /**
         * My thread-local ID.
         **/
        private static ThreadLocalID threadID = new ThreadLocalID();
    
        public static int get() {
            return threadID.get();
        }
    
        /**
         * When running multiple tests, reset thread id state
         **/
        public static void reset() {
            nextID = 0;
        }
    
        public static void set(int value) {
            threadID.set(value);
        }
    
        public static int getCluster(int n) {
            return threadID.get() % n;
        }
    
        private static class ThreadLocalID extends ThreadLocal<Integer> {
            protected synchronized Integer initialValue() {
                return nextID++;
            }
        }
    }
    /**
     * Max number of clusters
     * When debug We can set to 1
     */
    static final int MAX_CLUSTERS = 8;
    /**
     * List of local queues, one per cluster
     */
    List<AtomicReference<QNode>> localQueues;
    /**
     * single global queue
     */
    AtomicReference<QNode> globalQueue;
    /**
     * My current QNode
     */
    ThreadLocal<QNode> currNode = new ThreadLocal<QNode>() {
        protected QNode initialValue() {
            return new QNode();
        };
    };

    /**
     * My predecessor QNode
     */
    ThreadLocal<QNode> preNode = new ThreadLocal<QNode>() {
        protected QNode initialValue() {
            return null;
        };
    };

    /**
     * Creates a new instance of HCLHLock
     */
    public HCLHLock() {
        localQueues = new ArrayList<AtomicReference<QNode>>(MAX_CLUSTERS);
        for (int i = 0; i < MAX_CLUSTERS; i++) {
            localQueues.add(new AtomicReference<QNode>());
        }
        QNode head = new QNode();
        globalQueue = new AtomicReference<QNode>(head);

    }

    public void lock() {
        QNode myLocalNode = currNode.get();
        int myCluster = ThreadID.getCluster(MAX_CLUSTERS);
        myLocalNode.setClusterID(myCluster);  // Problem2 dead work no happend
        AtomicReference<QNode> localQueue = localQueues.get(ThreadID.getCluster(MAX_CLUSTERS));
        // splice my QNode into local queue
        QNode myLocalPred = null;
        QNode myGlobalPred = null;
        QNode localTail = null;
        do {
            myLocalPred = localQueue.get();
        } while (!localQueue.compareAndSet(myLocalPred, myLocalNode));

        if (myLocalPred != null) {
            boolean iOwnLock = myLocalPred.waitForGrantOrClusterMaster(myCluster);
            preNode.set(myLocalPred);
            if (iOwnLock) {
                // I have the lock. Save QNode just released by previous leader
                return;
            }
        }

        // Splice local queue into global queue.
        // inform successor it is the new master

        do {
            myGlobalPred = globalQueue.get();
            localTail = localQueue.get();
        } while (!globalQueue.compareAndSet(myGlobalPred, localTail));

        // here is local Node
        localTail.setTailWhenSpliced(true);
        // wait for predecessor to release lock
        // I have the lock. Save QNode just released by previous leader
        // Global must come from local
        while (myGlobalPred.isSuccessorMustWait()) {
        }
        preNode.set(myGlobalPred);
    }

    public void unlock() {

        QNode myNode = currNode.get();
        myNode.setSuccessorMustWait(false);
        // promote pred node to current
        myNode = currNode.get();

        QNode myPred= preNode.get();
        if (myPred != null){
            myPred.unlock();
            currNode.set(myPred);
        }

    }

    static class QNode {
        // private boolean tailWhenSpliced;
        private static final int TWS_MASK = 0x80000000;
        // private boolean successorMustWait= false;
        private static final int SMW_MASK = 0x40000000;
        // private int clusterID;
        private static final int CLUSTER_MASK = 0x3FFFFFFF;
        AtomicInteger state;

        public QNode() {
            state = new AtomicInteger(0);
        }

        boolean waitForGrantOrClusterMaster(int myCluster) {

            while (true) {
                if (getClusterID() == myCluster && !isTailWhenSpliced() && !isSuccessorMustWait()) {
                    return true;

                } else if (getClusterID() != myCluster || isTailWhenSpliced()) {
                    return false;
                }
            }
        }

        public void unlock() {
            int oldState = 0;
            int newState = ThreadID.getCluster(MAX_CLUSTERS) & CLUSTER_MASK;
            // successorMustWait = true;
            newState |= SMW_MASK;
            // tailWhenSpliced = false;
            newState &= (~TWS_MASK);
            do {
                oldState = state.get();
            } while (!state.compareAndSet(oldState, newState));
        }

        public int getClusterID() {
            return state.get() & CLUSTER_MASK;
        }

        public void setClusterID(int clusterID) {
            int oldState, newState;
            do {
                oldState = state.get();
                newState = (oldState & ~CLUSTER_MASK) | clusterID;
            } while (!state.compareAndSet(oldState, newState));
        }

        public boolean isSuccessorMustWait() {
//          TODO: In low machine , still may failed
//          The magic print
//          spin a little long?
//            System.out.println(String.format("isSuccessorMustWait %d ", 4 * 999  / 2));

//            Try sleep it was not same as println
//            Sleep yield the cpu. But print cpu don't yield and just
//            try{
//                Thread.sleep(100);
//            }
//            catch (InterruptedException e){
//                ;
//            }
            return (state.get() & SMW_MASK) != 0;
        }

        public void setSuccessorMustWait(boolean successorMustWait) {
            int oldState, newState;
            do {
                oldState = state.get();
                if (successorMustWait) {
                    newState = oldState | SMW_MASK;
                } else {
                    newState = oldState & ~SMW_MASK;
                }
            } while (!state.compareAndSet(oldState, newState));
        }

        public boolean isTailWhenSpliced() {
            return (state.get() & TWS_MASK) != 0;
        }

        public void setTailWhenSpliced(boolean tailWhenSpliced) {
            int oldState, newState;
            do {
                oldState = state.get();
                if (tailWhenSpliced) {
                    newState = oldState | TWS_MASK;
                } else {
                    newState = oldState & ~TWS_MASK;
                }
            } while (!state.compareAndSet(oldState, newState));
        }

    }

    // superfluous declarations needed to satisfy lock interface
    public void lockInterruptibly() throws InterruptedException {
        throw new UnsupportedOperationException();
    }

    public boolean tryLock() {
        throw new UnsupportedOperationException();
    }

    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        throw new UnsupportedOperationException();
    }

    public Condition newCondition() {
        throw new UnsupportedOperationException();
    }

}
Code
Diff
  • def is_prime(n: int) -> bool:
        if n < 5:
            return n in (2, 3)
        if not n & 1 or not n % 3:
            return False
        return not any(not n%i or not n%(i+2) for i in range(5, int(n**0.5) + 1, 6))
  • 1
    is_prime = lambda n: n == 2 or n > 2 and n % 2 and all(n % i for i in range(3, int(n**.5) + 1, 2))
    
    1+
    def is_prime(n: int) -> bool:
    
    2+
        if n < 5:
    
    3+
            return n in (2, 3)
    
    4+
        if not n & 1 or not n % 3:
    
    5+
            return False
    
    6+
        return not any(not n%i or not n%(i+2) for i in range(5, int(n**0.5) + 1, 6))
    
Code
Diff
  • digit_sum = lambda n: sum(map(int, str(abs(n))))
  • 1
    def digit_sum(n: int) -> int:
    
    2
        return sum(map(int, str(abs(n))))
    
    1+
    digit_sum = lambda n: sum(map(int, str(abs(n))))
    

Recent Moves:

Fundamentals
Numbers
Integers
Code
Diff
  • is_odd = lambda x: x&1
  • 1
    def is_odd(input):
    
    2
        return input & 1
    
    1+
    is_odd = lambda x: x&1
    
Fundamentals
Code
Diff
  • function binaryGap($n) {
      $binary = trim(decbin($n), 0);
      preg_match_all('/[0]+/', $binary, $match);
      $max = 0;
      foreach ($match[0] as $zeros) {
        $max = max($max, strlen($zeros));
      }
      return $max;
    }
  • 11
    function binaryGap($n) {
    
    2
      
    
    2+
      $binary = trim(decbin($n), 0);
    
    3+
      preg_match_all('/[0]+/', $binary, $match);
    
    4+
      $max = 0;
    
    5+
      foreach ($match[0] as $zeros) {
    
    6+
        $max = max($max, strlen($zeros));
    
    7+
      }
    
    8+
      return $max;
    
    33
    }
    
Algorithms
Algebra
Mathematics
Code
Diff
  • #include <math.h>
    
    int sumMultiples (int N, int k){
      int  countMultiples = floor(N/k);
      int  sumMultiples = 0.5*k*countMultiples*(countMultiples+1);
      return sumMultiples;
    }
    
    int solution (int N, int a, int b){
      return sumMultiples(N, a)+sumMultiples(N, b)-sumMultiples(N, a*b);
    }
    
    
  • 1
    using System;
    
    1+
    #include <math.h>
    
    22
    3
    namespace Kumite
    
    4
    {
    
    5
      public class Problem
    
    6
      {
    
    7
        public static long Sum(int N)
    
    8
        {
    
    9
          // Add your code here.
    
    10
          
    
    11
          return 0;
    
    12
        }
    
    13
      }
    
    3+
    int sumMultiples (int N, int k){
    
    4+
      int  countMultiples = floor(N/k);
    
    5+
      int  sumMultiples = 0.5*k*countMultiples*(countMultiples+1);
    
    6+
      return sumMultiples;
    
    1414
    }
    
    8+
    9+
    int solution (int N, int a, int b){
    
    10+
      return sumMultiples(N, a)+sumMultiples(N, b)-sumMultiples(N, a*b);
    
    11+
    }
    
    12+
Code
Diff
  • module Div2 where
    
    import Data.Word (Word64)
    import Data.Bits (shiftR)
    
    div2 :: Word64 -> Word64
    div2 = flip shiftR 1
  • 1
    unsigned long long div2(unsigned long long a){
    
    2
      //Use binary operators...I-O
    
    3
      return a >> 1;
    
    4
    }
    
    1+
    module Div2 where
    
    2+
    3+
    import Data.Word (Word64)
    
    4+
    import Data.Bits (shiftR)
    
    5+
    6+
    div2 :: Word64 -> Word64
    
    7+
    div2 = flip shiftR 1
    

okay, but why if if when you can if else if ?

Code
Diff
  • import java.util.*;
    interface HighLow {
      static int[] printLargestAndSmallest(int[] nums) {
            int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
            for(int i=0;i<nums.length; i++){
                if(max<nums[i])max=nums[i]; else  //  <----
                if(min>nums[i])min=nums[i];
            }
            return nums == null || nums.length==0 ? null : new int[]{min, max};
        }
    }
  • 11
    import java.util.*;
    
    22
    interface HighLow {
    
    33
      static int[] printLargestAndSmallest(int[] nums) {
    
    44
            int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
    
    55
            for(int i=0;i<nums.length; i++){
    
    6
                if(max<nums[i])max=nums[i];
    
    6+
                if(max<nums[i])max=nums[i]; else  //  <----
    
    77
                if(min>nums[i])min=nums[i];
    
    88
            }
    
    99
            return nums == null || nums.length==0 ? null : new int[]{min, max};
    
    1010
        }
    
    1111
    }
    

Recent Moves: