覚えたら書く

IT関係のデベロッパとして日々覚えたことを書き残したいです。twitter: @yyoshikaw

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

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

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

{何かしらのコマンド等で重複データを出力した結果} | 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等 でこの現象に出くわしました。

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


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

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

f:id:nini_y:20190810083106p:plain


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

連続した整数の XOR(排他的論理和)

ある連続した整数群の XOR の結果を取得したい。

  • 引数は、MとN の2つの整数
  • M > 0
  • N > M
  • M から N までの連続した整数の XOR を結果として返す
    • 例えば X = 5, N = 8 の場合以下の通り(括弧で括った部分は2進数表現)
      • answer = 5 ^ 6 ^ 7 ^ 8 = (101 ^ 110 ^ 111 ^ 1000) = (011 ^ 1111) = (1100) = 12


愚直にやるなら以下の通りです。

public class Solution1 {

    public static int solution(int M, int N) {
        return xors(M, N);
    }

    public static int xors(int M, int N) {
        int value = M;
        for (int i = M; i < N; i++) {
            value = value ^ (i + 1);
        }
        return value;
    }
}


ただし、以下のコードでもいけるっぽい。

public class Solution2 {

    public static int solution(int M, int N) {
        return xORTrick(N) ^ xORTrick(M - 1);
    }

    private static int xORTrick(int n) {
        if (n % 4 == 0) {
            return n;
        }

        if (n % 4 == 1) {
            return 1;
        }

        if (n % 4 == 2) {
            return n + 1;
        }

        return 0;
    }
}

いけるっぽいと書いてるのは、私がコードの内容を理解してないからです・・・。
理解してないもの載せるのもどうかとは思いつつも、載せちゃいました(汗)。
(後者の方が圧倒的に高速に動作します)