Does Two Integer arrays Come from one sequence

Question:

There is a list of int arrays; the next int array is the explanation of the previous one.

For example, if the first one is [1], the next int array would be [1, 1], it means the previous array has a number one, the next array would be [2, 1], means the previous array has two one, and so on.

1

1 1

2 1

1 2 1 1

1 1 1 2 2 1

3 1 2 2 1 1

So the question would be: given a two int arrays A and B, you need determine whether they come form one sequence? In other word, whether you can induce from A to B, or from B to A?

Answer:

It seems that we can just induce from A, and get its next int array, and its next's next array, if one int array equals B, then we can return true.

But this problem is that what if A and B don't come from one sequence, when we stop?

We don't know.

In this problem, we can think reversely, if we starts from A, and get A's previous array, if it equals B, we can return true, if not, we continue. But if not, when we stop?

The first case: we can’t conclude previous array from the curry array:

Two cases:

1.      When the current int array has odd numbers, we stop, as it's impossible to get its previous array. The reason is simple: (a[i], b[i]) describes one item of previous array, if current array has odd numbers, (a0, b0) .. (a[n], b[n]), a[n+1], a[n+1] can't describe one item of previous array.

2.      When the current int array has even digits, but have some invalid pairs, such as (0 1).

Another case: if we deduce from A, and get it's parent, and its parent's parent, what if we get A again, if we continue, it will loop for ever. So in this case, we should return false, why?

A's parent array A[p'] is unqiue, A[p']'s parent A[p''] is also unique.

..

A[p'']

A[p']

A <--

..

...

A[p'']

A[p']

A <--

So the whole array sequence would be a loop. if we search from A, and meet A again, and no B during the path. So B would not be in the sequence.

Also remember that if the previous process determines whether B is in front of A in one sequence, we still need determine whether A is in front of B in some sequence.

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/jefferyyuan/myAlgorithms.

package org.codeexample.jefferyyuan.sameSequence;
import java.util.ArrayList;
import java.util.List;
import org.codeexample.common.Utils;

public class AlgorithmSameSequnce {
 
    /**
     * see
     * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
     * <p>
     * 
     * @param arrayA
     * @param arrayB
     * @return
     */
    public static boolean isInSameSequnce(int[] arrayA, int[] arrayB) {
        return isInSameSequnce(Utils.toList(arrayA), Utils.toList(arrayB));
    }
 
    /**
     * see
     * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
     */
    public static boolean isInSameSequnce(List<Integer> listA,
            List<Integer> listB) {
        List<Integer> listACopy = new ArrayList<Integer>(listA);
        if (isInSameSequnceImpl(listA, listACopy, listB))
            return true;
        List<Integer> listBCopy = new ArrayList<Integer>(listB);
        return isInSameSequnceImpl(listB, listBCopy, listA);
    }
 
    private static boolean isInSameSequnceImpl(List<Integer> listA,
            List<Integer> interim, List<Integer> listB) {
        List<Integer> previous = getPrevious(interim);
        if (previous.equals(listB))
            return true;
        // meet listA again
        if (previous.equals(listA))
            return false;
        if (previous.isEmpty())
            return false;
        return isInSameSequnceImpl(listA, previous, listB);
    }
 
    /**
     * Return the previous array, for example, the previous array of [2, 1]
     * would be [1, 1], the previous of [1, 2, 1, 1] would be [2, 1]. 
 
     * If the list is invalid or can't induce its previous array, return one
     * empty list.
     * 
     * @param list
     * @return
     */
    private static List<Integer> getPrevious(List<Integer> list) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // if the list has odd number, return empty list;
        if (list.size() % 2 == 1)
            return result;
 
        for (int i = 0; i <= list.size() - 2;) {
            int times = list.get(i++);
 
            // no previous row for input [0, 1],
            if (times == 0)
                return new ArrayList<Integer>();
            int digit = list.get(i++);
            for (int j = 0; j < times; j++) {
                result.add(digit);
            }
        }
        return result;
    }
}

Is Successive Array?

Question: 

Given an unordered int list, except 0, each number can appear only once, 0 can be regarded as any number. Now we need determine whether the digits from the list are logically successive,

For example,

3, 2, 1 would be considered as successive.

0, 3, 1 also is successive, as 0 can be regarded as 2.

0, 0, 3, 1 also is successive as 0, 0 can be regarded as (0, 2), or (2, 4).

Answer:

First, simplify this question, if there can be only one 0, and can't be considered as any number. How we determine whether the array is successive?

In this case, we can get the maximum and minimum of this array, if (max - min) = (length of the array -1), then this array is considered as successive. This is very straightforward.

So back to the original problem, suppose the length of the array is n, and there is x 0, and thus n-x non-zeros, so we can get the inequality:  if (max - min) <= (n -1), this array is successive.

0, 3, 1 ==> (3-1) = len -1 = 2

0, 0, 3, 1 ==> (3-1) < len - 1 = 3

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/jefferyyuan/myAlgorithms.

package org.codeexample.jefferyyuan.successiveArray;

public class SuccessiveArray {
  
  /**
   * see http://programer-tips.blogspot.com/ 2011/08/is-array-successive.html
   * 
   * Determine whether the unordered array is logically successive, 0 can be
   * regarded as any number. For example, [0, 3, 1] is successive, as 0 can be
   * regarded as 2.
   * 
   * @param array
   * @return
   */
  public static boolean isArraySuccessive(int[] array) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    
    for (int i = 0; i < array.length; i++) {
      int temp = array[i];
      if (temp == 0) continue;
      if (temp < min) {
        min = temp;
      }
      if (temp > max) {
        max = temp;
      }
    }
    return (max - min) <= (array.length - 1);
  }
}

Implementation Variants of Singleton Pattern

Singleton is one of the most common design patterns, but it has many implementation variants: lazy Instantiation, eager Instantiation, static holder idiom, and etc. Static holder idiom is my favorite.

package org.codeexample.jefferyyuan.javacode.singletons;

import java.io.Serializable;

public class SinletonVariants {}

/**
 * When the singleton class is referenced, its instance would not be created,
 * and also Java guarantees that the class initialization is atomic.
 * 
 * So using the static holder idiom, we combine the benefit of lazy
 * instantiation and no further synchronization after the instance is created,
 * 
 * My favorite, always use this one.
 */
class SingletonHolderIdiom {
  private SingletonHolderIdiom() {}
  
  private static class SingletonHolder {
    private static final SingletonHolderIdiom instance = new SingletonHolderIdiom();
  }
  
  public static SingletonHolderIdiom getInstance() {
    return SingletonHolder.instance;
  }
}

/**
 * To maintain the singleton guarantee, you have to declare all instance fields
 * transient and provide a readResolve method that directly return the static
 * instance, also you must use eager instantiation.
 * 
 * see Effective Java 2nd Edition: Item 3: Enforce the singleton property with a
 * private constructor or an enum type
 */
class SerializableSingleton implements Serializable {
  private static final long serialVersionUID = 1L;
  private static SerializableSingleton instance = new SerializableSingleton();
  
  private SerializableSingleton() {}
  
  public static SerializableSingleton getInstance() {
    return instance;
  }
  
  // readResolve method to preserve singleton property
  private Object readResolve() {
    return instance;
  }
}

/**
 * This variant avoids the drawback of eager instantiation, as no resources are
 * allocated before the instance is actually accessed, but further
 * synchronization might seem unnecessary and expensive after the instance is
 * already constructed.
 * 
 */
class SingletonLazyInstantiation {
  private static SingletonLazyInstantiation instance;
  
  private SingletonLazyInstantiation() {}
  
  public static synchronized SingletonLazyInstantiation getInstance() {
    if (instance == null) {
      instance = new SingletonLazyInstantiation();
    }
    return instance;
  }
}

/**
 * This would initialize this singleton class eagerly, when the class is loaded
 * at first time. Thus, it may happen that the singleton instance is constructed
 * even if it is not accessed. This is a drawback, especially when the
 * construction is complex and time/resource consuming. The good part of this
 * variant is its simplicity.
 * 
 */
class SingletonEagerInstantiation {
  private static SingletonEagerInstantiation instance = new SingletonEagerInstantiation();
  
  private SingletonEagerInstantiation() {}
  
  public static SingletonEagerInstantiation getInstance() {
    return instance;
  }
}

Learning Java Integer Code and Puzzles

1. Question - What the program would output?

int i = 127;
boolean b = (Integer.valueOf(i) == Integer.valueOf(i));
System.err.println(b);
i = 128;
b = (Integer.valueOf(i) == Integer.valueOf(i));
System.err.println(b);

We can immediately know the answer after we look at the source code.

public static Integer valueOf(int i) {
    if(i >= -128 && i <= IntegerCache.high)
        return IntegerCache.cache[i + 128];
    else
        return new Integer(i);
}

We can know it doesn't cache all Integer values, as this may consume too much memory, so it just caches the numbers between [-128, 127] in the static IntegerCache class, for other int numbers, each time it would return a new Integer. Class Long also only caches the numbers between [-128, 127].

The output of the previous program would be obvious now: true and false.

2. Autobox and Auto-unbox

2. 1 How is it implemented in JDK?

Simply put, when we call "Integer wrapper = 2;", the java compile would translate it to "Integer wrapper = Integer.valueOf(wrapper);".

When we call "int i = wrapper;", the java compile would translate it to "int i = wrapper.intValue();".

You can verify this by using javap to look. at the compiled java class: javap -c IntegerTester.

Long.valueOf(0L).equals(0)?

2.2 What would be the output of the following program?

Long l = 0L;
Integer i = 0;
System.out.println(l.equals(i));
System.out.println(i.equals(l));

The program above is same as:

So let's look at the JDK source code again:

public final class Integer extends Number 
  implements Comparable<Integer> {
    public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
    }
}
public final class Long extends Number 
  implements Comparable<Long> {
    public boolean equals(Object obj) {
      if (obj instanceof Long) {
          return value == ((Long)obj).longValue();
      }
      return false;
    }
}

From the code, we can see if the type of parameter is not same, these method would return false.

So the output of previous program would be false, false.

Autobox and auto-unbox are good features, as it will convert the primitive type or wrapper type to the needed one, and we can write less code, but we should use it carefully, as usually, it may create object under the hood, if we are unaware of this, it may cause big performance penalty.

public void test(Integer i) {
    while (i < 0) {
        --i;
    }
}

In the previous program, in each step, JVM actually does this: it calls i.intValue(), subtracts it by one, and then create a new Integer value.

For JVM, it would be same as:

while (i.intValue() &lt; 0) {

    i = Integer.valueOf(i.intValue() - 1);

}

So in each step, we would unnecessary create one Integer value and call intValue methods twice.

Try to use javap to look at the compiled class file.

If we know this, we can change our code like the below, it would be faster.

public void test(Integer i) {
      int j = i;
      while (j < 0) {
           --j;
      }
      i = j;
}

In our code, it's to better use primitive type as often as possible. 

In Integer class there are many other interesting and useful methods, some methods are listed below, is it cool and a little confusing? Try to figure it out.

public final class Integer extends Number 
  implements Comparable<Integer> {
    public static int reverseBytes(int i) {
        return ((i >>> 24)           ) |
               ((i >>   8) &   0xFF00) |
               ((i <<   8) & 0xFF0000) |
               ((i << 24));
    }
    public static int reverse(int i) {
        // HD, Figure 7-1
 i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
 i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
 i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
 i = (i << 24) | ((i & 0xff00) << 8) |
     ((i >>> 8) & 0xff00) | (i >>> 24);
 return i;
    }
    public static int bitCount(int i) {
        // HD, Figure 5-2
 i = i - ((i >>> 1) & 0x55555555);
 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 i = (i + (i >>> 4)) & 0x0f0f0f0f;
 i = i + (i >>> 8);
 i = i + (i >>> 16);
 return i & 0x3f;
    }
}

Reference:

The Advantages and Traps of Autoboxing

Rearranging Letters to Form Word

Question:

Rearranging the letters to form a word is a very funny algorithm problem, and it has several variants. Here we will talk about the problem – the most efficient way to find out whether we can rearrange these letters and form a word, and if yes, return all words that can be constructed.

For input [d, a, e, p, n, p], we can rearrange them into a word "append".

Answers:

We can think about our commonly-used data structure - HashMap, if we can build one HashMap from the dictionary, and then query it using some key, the running time would be O(1). Brilliant!!!

But what would be key and value? 

First the input order doesn't matter, "atc" is same as "tac", or "cta", so we can order the input, "atc", "tac", "cta" would all be sorted as "act".

Also we may construct several words from the letters, for example, we can form "act", "cat" from the letters - "atc".

So we can build the HashMap from the dictionary, the key would be the sorted letters; the value would be a list containing all words that can be constructed by rearranging the order of these letters.

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/jefferyyuan/myAlgorithms.

package org.codeexample.jefferyyuan.algorithm.wordPuzzles;

import java.io.*;

import java.util.*;

import java.util.regex.Pattern;

public class Dictionary {

    private Map> wordMap = new HashMap<>();

    /**

     * @param dictionaryFile, the file contains list of words,

     * each line may contain several words that are separated by space.

     * @throws IOException

     */

    public Dictionary(String dictionaryFile) throws IOException {

        init(dictionaryFile);

    }

    private void init(String dictionaryFile) throws IOException {

        FileReader fr = new FileReader(new File(dictionaryFile));

        FileReader fr = new FileReader(file);

        BufferedReader br = new BufferedReader(fr);

        Pattern pattern = Pattern.compile("\\s+");

        while (true) {

            String line = br.readLine();

            if (line == null) {

                break;

            }

            String[] words = pattern.split(line);

            for (String word : words) {

                word = word.trim();

                if (!word.isEmpty()) {

                    String sortedWord = getMapKey(word);

                    HashSet matchedWordSet = wordMap.get(sortedWord);

                    if (matchedWordSet == null) {

                        matchedWordSet = new HashSet<>();

                    }

                    matchedWordSet.add(word);

                    wordMap.put(sortedWord, matchedWordSet);

                }

            }

        }

    }

    private String getMapKey(String letters) {

        char[] chars = letters.toCharArray();

        Arrays.sort(chars);

        return String.valueOf(chars);

    }

    /**

     * Return a list of word that can constructed by rearranging these letters.

     *

     * @param letters

     * @return a hash set that containing all words, if can't find one, return

     *         empty list, instead of null to avoid NPE in client code.

     * @throws IllegalArgumentException if parameter is null.

     */

    public Set formWords(String letters)

            throws IllegalArgumentException {

        if (letters == null) {

            throw new IllegalArgumentException("parameter can't be null.");

        }

        Set wordsSet = wordMap.get(getMapKey(letters));

        if (wordsSet == null) {

            wordsSet = new HashSet<>();

        }

        return wordsSet;

    }

}

This article is migrated from my another blog: http://programmer-plus.blogspot.com/, but I found that I forgot my username for that blog. DARN!!!

Python Scripts to Reverse Words in Notepad++

Just another user python script that can reverse selected words in notepad++, such as from such as from ＂types.core.services.projecta.codeexample.com" to "com.codeexample.projecta.services.core.types".

The complete code is as below:

# change this if the delimiter is not .

delimiter = ".";

selected = editor.getSelText();

reversed = delimiter.join(selected.split('.')[::-1]);

editor.replaceSel(reversed);

To view the complete code, please refer: https://github.com/jefferyyuan/tools/blob/master/notepadplusplus-plugins/reversewords.py

About how to install the PythonScript, create a user python script, run it from Scripts submenu, assign the script to the toolbar, or assign it a shortcut, please read http://npppythonscript.sourceforge.net/docs/latest/usage.html#installation.

Python Scripts to Change Selected Text from SBC to DBC in Notepad++

When I use Google pinyin, sometimes, it’s in SBC (全角) mode; the typed text would be SBC cases, such as “ｈｅｌｌｏ　ｗｏｒｌｄ”, the typed text is totally useless to me. In the past, I have to delete them and retype. This sucks and time wasted.

So after learned from http://npppythonscript.sourceforge.net/ that: we can use python scripts to extend notepad++ function easily, so I decide to write a notepad++ addon, which can change the selected text from SBC cases to DBC cases.

So now, I only need select the text, click button in the toolbar, the text will be changed from SBC to DBC cases, from ＂ｈｅｌｌｏ　ｗｏｒｌｄ＂　to "hello world". 

Life is much easier now :)

The complete code is as below:

def SBCToDBC(ustring):

    '''From http://bbs.chinaunix.net/thread-1762033-1-1.html'''

    result = ''

    for uchar in ustring:

        inside_code = ord(uchar)

        if inside_code == 12288:

            inside_code = ' ';

        elif not inside_code in range(32, 127):

            inside_code -= 65248;            

        if inside_code in range(32, 127):

            result += unichr(inside_code).encode('utf-8', 'ignore');

        else:

            result +=uchar;                    

    return result.encode('utf-8', 'ignore');

selected = editor.getSelText().decode('utf8');

reversed = SBCToDBC(selected) 

editor.replaceSel(reversed);

To view the complete code, please refer: https://github.com/jefferyyuan/tools/blob/master/notepadplusplus-plugins/SBCtoDBC.py

About how to install the PythonScript, create a user python script, run it from Scripts submenu, assign the script to the toolbar, or assign it a shortcut, please read http://npppythonscript.sourceforge.net/docs/latest/usage.html#installation.

For more information, please refer: https://plus.google.com/101157854606139706613/posts/68pAvApmZ34