codility - Arrays OddOccurrencesInArray

codility の OddOccurrencesInArrayを解いてみます。

問題の概要

• インプット（引数）
  • 整数の配列
    • 配列の要素の整数は奇数
    • 配列の要素数は奇数個
    • 要素の値同士のペアができるが、１要素だけペアができない値が含まれている
    • 例：[9, 3, 9, 3, 9, 7, 9]
• アウトプット（戻り値）
  • ペアができなかった要素の値
  • 例にあげた引数の場合、7 がアウトプットになります

解答

以下の方針でやってます。

• まず配列をソートする。
• ソートされているので、基本的に偶数番目と奇数番目の要素の値は一致する（ペアになる）はず。
• ペアにならなかったら、その偶数番目の値が１個だけしか存在しないものということになるので、それがそのまま答え
• 最後の最後まで進んだら最終要素が答えとなる

import java.util.Arrays;

class Solution {

    public int solution(int[] array) {
        Arrays.sort(array);

        for (int i = 0; i < array.length - 1;){
            if (array[i] != array[i + 1]) {
                return array[i];
            }
            i = i + 2;
        }
        return array[array.length - 1];
    }
}

これでやってみると結果は以下の通りで、問題ないようです。

ISBN-13を求める

ISBN や ISBN-13 の説明はWikipediaにお任せするとして

「接頭記号」 + 「グループ記号」 + 「出版者記号」 + 「書名記号」　（ハイフン除くと12桁）の値から
末尾に付与するチェックディジットまで含めたISBN-13の値を求めたい場合、
以下のようなメソッドを用意すればできます。

public final class ISBN13 {

    public static String generate(String src) {
        final String str12 = src.replace("-", "");

        if (str12.length() != 12) {
            throw new IllegalArgumentException(str12);
        }

        return str12 + checkDigit(str12);
    }

    private static int checkDigit(String str12) {
        // ウェイトの1および3
        final int[] weights = { 1, 3 };

        int sum = 0;
        for (int i = 0; i < str12.length(); i++) {
            // sum += Integer.valueOf(str12.charAt(i)) * weights[i & 1]   <- NG!!!
            sum += Character.getNumericValue(str12.charAt(i)) * weights[i & 1];
        }
        final int r = 10 - (sum % 10);
        if (r == 10) {
            return 0;
        }
        return r;
    }

試してみる

public static void main(String[] args) {
    System.out.println(ISBN13.generate("978479733720"));
    System.out.println(ISBN13.generate("978-4-7973-3720"));
    System.out.println(ISBN13.generate("978410109205"));
    System.out.println(ISBN13.generate("978030640615"));
    System.out.println(ISBN13.generate("978-0-30-640615"));
    System.out.println(ISBN13.generate("978316148410"));
}

出力結果

9784797337204
9784797337204
9784101092058
9780306406157
9780306406157
9783161484100

分かりにくいですが、ISBN-13を意味する13桁表現の値が取得できます。

2の累乗の加算で表現できる値の分解

• N個の要素の整数を持つ配列Aを与えられる（N >= 1）
• binarian(A) = pow2(A[0]) + pow2(A[1]) + ... + pow2(A[M-1])
• 上記の式で求めた結果と同じ値となるための 2の累乗n の加算 の最小の組み合わせ数を求める

例：

A[0]=1
A[1]=5
A[2]=4
A[3]=4

binarian(A) = pow2(A[0]) + pow2(A[1]) + pow2(A[2]) + pow2(A[3])
            = pow2(1) + pow2(5) + pow2(4) + pow2(4)
            = 2 + 32 + 16 + 16
            = 66

この 66 を表現する2の累乗の和の表現は以下になります（2の1乗 + 2の6乗 で表現できます）

66 = pow2(1) + pow2(6)

結果として答えは 2です。（2の1乗 と 2の6乗 の2つの組み合わせで表現できるので）

これを求めるプログラムは以下になります

import java.util.Map;
import java.util.TreeMap;

public class Solution {

    public static int solution(int[] A) {
        TreeMap<Integer, Integer> reiterations = new TreeMap<>();
        int lengthSolution = 0;
        for (int i = 0; i < A.length; i++) {
            int item = A[i];
            if (reiterations.containsKey(item)) {
                reiterations.put(item, reiterations.get(item) + 1);
            } else {
                reiterations.put(item, 1);
            }
        }
        reiterations = factorize(reiterations, reiterations.firstEntry());

        for (Map.Entry<Integer,Integer> entry : reiterations.entrySet()) {
            int value = entry.getValue();
            if (value == 1) {
                lengthSolution++;
            }
        }

        return lengthSolution;
    }

    public static TreeMap<Integer, Integer> factorize(TreeMap<Integer, Integer> remaining,
                                                      Map.Entry<Integer, Integer> entry) {
        int key = entry.getKey();
        int value = entry.getValue();

        if (value > 1 && value % 2 == 0) {
            if (remaining.containsKey(key + 1)) {
                remaining.put(key + 1, remaining.get(key + 1) + value / 2);
                remaining.put(key, 0);
            } else {
                remaining.put(key + 1, value / 2);
                remaining.put(key, 0);
            }
        } else if (value > 1 && value % 2 == 1) {
            if (remaining.containsKey(key + 1)) {
                remaining.put(key + 1, remaining.get(key + 1) + (value - 1) / 2);
                remaining.put(key, 1);
            } else {
                remaining.put(key + 1, (value - 1) / 2);
                remaining.put(key, 1);
            }
        }

        while (remaining.higherEntry(key) != null) {
            if (remaining.higherEntry(key).getValue() > 1) {
                factorize(remaining, remaining.higherEntry(key));
            }
            key++;
        }
        return remaining;
    }
}

念のために [1, 5, 4, 4]の配列を渡して試してみると

public class Main {

    public static void main(String[] args) {
        int[] test = {1, 5, 4, 4};
        System.out.println(Solution.solution(test));
    }
}

出力結果

2

予定通りの結果が得られています

sort と uniq で出現回数順にランキング

Linux なんかで、何かしらのコマンドの結果から重複したデータを出力して、
その結果を出現回数順に並べたいというのがまーまーよくあります。

ほぼ、イディオムみたいなもんです。（が、自分は毎日使うわけではなく忘れることがあるのでここにメモしておくことにしました）

やり方は、sort と uniq コマンド利用して以下の通りです

{何かしらのコマンド等で重複データを出力した結果} | sort | uniq -c | sort -nr

例えばコマンドで以下のような重複するデータを含むIPアドレス群（例えばWebサーバへのアクセス元のIPアドレス群）が得られた場合

106.73.78.92
171.193.59.149.168
209 207.46.204.192
203 59.106.108.114
105.72.77.110
120 66.249.70.136
120 66.249.70.136
137 78.46.120.35
202 66.249.69.107
107.72.78.97
106 66.249.69.121
105.72.77.110
137 78.46.120.35
129 66.249.69.65
105.72.77.110
120 66.249.70.136
117 66.249.69.131
107.72.78.97
105.72.77.110
106 66.249.69.121

これらに対して先ほどのコマンドを実行すると結果は以下になります（出現回数とIPアドレスが出現回数の降順で表示されます）

   4 105.72.77.110
   3 120 66.249.70.136
   2 137 78.46.120.35
   2 107.72.78.97
   2 106 66.249.69.121
   1 209 207.46.204.192
   1 203 59.106.108.114
   1 202 66.249.69.107
   1 171.193.59.149.168
   1 129 66.249.69.65
   1 117 66.249.69.131
   1 106.73.78.92

このぐらいのコマンドの使い方は記憶しておけよって言われそうですが・・・。

Office365製品の画面がチラつく時の対策

Microsoft の Office製品（Office 2016のみ？）を使っていると、
急にウィンドウ内が白くなってそのウィンドウをクリックしないと実際にそこに書かれている内容が参照できない。
というような チラつき、画面の点滅 のような現象が発生することがあります。

一度発生すると、ずっと発生し続けて相当に面倒な状態になります。（まともに内容が表示されない、画面描画が遅い・・・）
私は、Outlook等 でこの現象に出くわしました。

端末環境にもよると思いますが、私の場合は
ハードウェア グラフィック アクセラレータを無効化することで本現象が発生しなくなりました。

設定手順は、対象製品を起動した上で、
[ファイル] > [オプション] > [詳細設定] > [ハードウェア グラフィック アクセラレータを無効にする] にチェックを入れる。 です。

設定画面は以下のようになっています。

同じような現象にはまってしまってる人が、これで解消すればよいのですが・・・。