最大の子マトリックスを探す

今日のお題

各セルに1か0が入った長方形が、String[]で与えられる。その長方形の中で、1だけで満たされた最大の長方形を探し、その面積(すなわち1の数)を返すメソッドを書け。

回答

import java.util.*; 
import java.io.*;

class Main {  
  public static String MaximalSquare(String[] strArr) { 

    int rowLen = strArr.length;
    int colLen = strArr[0].length();
    int maxLen = rowLen < colLen ? rowLen : colLen;
    
    int len = maxLen;
    for(; 0 <= len; len--){
        for(int row = 0; row <= rowLen-len; row++){
            for(int col = 0; col <= colLen - len; col++){
                boolean found = false;
                if(strArr[row].charAt(col) == '1'){
                    found = true;
                    for(int i = 1; i < len; i++){
                        if(strArr[row].charAt(col+i) != '1'){
                            found = false;
                        }
                    }
                }
                
                //start searching submatrix of size len from (row,col)
                if(found){
                    boolean subFound = true;
                    for(int y = row + 1; y < row + len; y++){
                        for(int x = col; x < col + len; x++){
                            if(strArr[y].charAt(x) != '1'){
                                subFound = false;
                            }
                        }
                    }
                    if(subFound){
                        return Integer.toString(len*len);
                    }
                }
            }
        }
    }

    return "0";
  }
  
  //Coderbyteのお作法
  public static void main (String[] args) {  
    // keep this function call here     
    //Scanner s = new Scanner(System.in);
    System.out.println(MaximalSquare(new String[] {"0111", "1101", "0111"})); 
    System.out.println(MaximalSquare(new String[] {"0111", "1111", "1111", "1111"}));
  }
}

感想

問題を聞いて単純な探索アルゴリズムはすぐに思いつくのだが、配列の脳みそが劣化していてインデックス操作をいくつも間違えてしまい、面倒くさくなってデバッガで追い込む結果となった。O(n2)?だけど、きっともっとうまいアルゴリズムがあるのだろう。回答者(正答者?)がグッと減って、回答例は1個しか表示されず、その人も同じような方針で解いていた。

経路問題

今日のお題

座標1~8の8x8マスのチェス盤の上の座標が"(x y)(a b)"の形式で2つ与えられる。a > x, b > yは常に満たされる。(x y)から(a b)へ至る経路数を求めよ。

回答

import java.util.*;
import java.io.*;

class Main {
    public static String ChessboardTraveling(String str) {

        int x = str.charAt(1);
        int y = str.charAt(3);

        int a = str.charAt(6);
        int b = str.charAt(8);

        int len = (a - x) + (b - y);
        int right = a - x;

        int paths = 1;

        for (int i = len; len - right < i; i--) {
            paths *= i;
        }
        for (int i = 1; i <= right; i++) {
            paths /= i;
        }

        return Integer.toString(paths);
    }

    //mainやmainから呼ばれるメソッドのシグネチャはcoderbyteのお作法
    public static void main(String[] args) {
        // keep this function call here
        Scanner s = new Scanner(System.in);
        System.out.print(ChessboardTraveling(s.nextLine()));
    }
}

感想

小学校からお馴染みの経路問題。ここはcoderbyteなので座標は1から始まる。条件が厳しいのでparseも文字位置指定で十分。プログラムになれている人は再帰で書くのだろう。Eight queensを思い出す。

これがHardレベルというのはどうかと思うが、Easyとくらべると回答者の数がぐっと減り、テストケースで満点を取れていないようなコードが回答例に出てきたりする。これで金を取るのか。

今晩残りの時間はpermutationの計算について少し考えるのと、Java Collections Frameworkの勉強に費やす。

プログラミング再入門

ボケ防止にプログラミングの勉強を始めた。毎日のようにコードを書いていたころから10年以上が経過していて、言語(というかライブラリ)も変わっているし、記憶も錆び付いていてつらい気もする一方で、仕事ではない気楽さもあって、プラマイではとてもよい気晴らしになっている。ここ一週間はcoderbyte.comの無料問題を端っこから解いている。多言語対応が適当で、Javaメソッド名が大文字で始まっていたり、booleanではなくStringの"true"を返すように期待されていたり、気持ちの悪いところはあるが、他の人の回答例を見て色々考えたりできるもの楽しい。

今日のお題

最低2種類の数字を含む4桁の整数を入力として、各桁の数字を降順にソートした整数と昇順にソートした整数の差を求める操作をして、その差についてさらに同様の操作を繰り返すと6174になる。6174になるまでの操作の回数を返すメソッドを書け。

回答

問題の定義からし再帰の初歩的な問題であるが、Javaに用意されたクラスライブラリを適切に使って文字列や整数を操作しようとするとギコチナイことになる。

import java.util.*;
import java.io.*;

class Main {
    public static int KaprekarsConstant(int num) {
        return recursiveDiff(num, 1);
    }

    public static int recursiveDiff(int num, int depth) {
        int diff = sortDesc(num) - sortAsc(num);
        if (diff == 6174) {
            return depth;
        } else {
            return recursiveDiff(diff, depth + 1);
        }
    }

    public static int sortAsc(int num) {
        String numStr = "" + num;
        char[] numChars = numStr.toCharArray();
        Arrays.sort(numChars);
        return Integer.parseInt(new String(numChars));
    }

    public static int sortDesc(int num) {
        int sortedInt = sortAsc(num);
        String sortedStr = "" + sortedInt;
        String reverseSortedStr;
        if (sortedInt >= 1000) {
            reverseSortedStr = "" + sortedStr.charAt(3) + sortedStr.charAt(2) + sortedStr.charAt(1)
                    + sortedStr.charAt(0);
        } else {
            reverseSortedStr = "" + sortedStr.charAt(2) + sortedStr.charAt(1) + sortedStr.charAt(0) + '0';
        }
        return Integer.parseInt(reverseSortedStr);
    }

    //mainやmainから呼ばれるメソッドのシグネチャはcoderbyteのお作法
    public static void main(String[] args) {
        // keep this function call here
        Scanner s = new Scanner(System.in);
        System.out.print(KaprekarsConstant(Integer.parseInt(s.nextLine())));
    }
}

感想

テストケースはパスしたものの、自分のコードは1000など0が2つ以上含まれている整数を食わせるとクラッシュする。ソート済みの数字のペアのうち、小さい方を返すsortAscを使ってsortDescを実装するのがうまくない。同じことをするにしても、sortDescは必ず1000以上の整数になることが保証されているので、sortDescを使ってsortAscを実装すれば場合分けは不要になる。

そもそもなぜsortAscが頭の中で先に来たかというと、Arrays.sortにコンパレータを指定して逆順ソートする方法Arrays.sort(num, Collections.reverseOrder())が頭に入っていなかったから。

Vanilla Sky - alternative ending

2015年に北米でリリースされたVanilla Sky Blu-ray版に、エンディング部分の新しい編集が収録されているということを今になって知り愕然としました。
 
Trailerだけに含まれていた銃撃シーンやSofiaがウエディングドレスのような被り物を頭に載せているシーンなどが、劇場公開から13年の時を経て、ようやく本編とつながる形で説明されることになりました。
 
新たに公開された部分の内容そのものについて言えば、劇場公開版と比べて冗長に感じられるセリフが多く(とりわけMcCabe - カート・ラッセル)、間延びして感じられます。特にMcCabeの饒舌さはMcCabeの存在そのものと矛盾すると言う点にも違和感があります。
 
唯一良かったのは、Sofiaの"Good morning. It's time for you to wake up"と言うセリフで、これは胸に差し迫るものがあります。(起きている人間に"It's time for you to wake up"とは言わない!)とは言え、"I'm frozen and you're dead" "It's a problem"から"I'll find you again" "I'll see you in another life -- when we are both cats."へ、ユーモア、哀しみ、諦念の交錯する会話の中で、あまりに直截的かつ説明的なセリフは流れを断ち切ることになり、構成上"Good morning"を残すのは難しかったのではないかとも思います。最後の会話シーンには、今回のalternative編集のみのセリフが他にもいくつかありますが、劇場公開版ではバッサリとカットされていたことがわかります。
 
YouTubeに上がっていたので、興味のある方はエンディングの部分だけであれば今すぐ見ることができます。
 
ところで、個人的にサザエさんやマスオさんが何歳だと聞いても全く何も感じないのですが、David Aamesが32-33歳で、いつのまにか彼の年齢を追い越してしまったことを考えると、感慨深いものがあります。Vanilla Skyの撮影シーンを訪ねて初めてNYCへ出かけてから10年近くの時間が経ってしまいましたが、未だに秋のセントラルパークへは行けていません。実行力の欠如を認めざるを得ません。好きな映画ですら反省材料は見つかるものです。意識高い系とは、そういうことです。
 
どうでもいいのですが。

Voice assistants 観察日記

質問: "How long does it take to charge Apple Watch?"

みなさんの回答:

Siri via Apple Watch "Let's search the web for that on your iPhone"

Siri via iPhone "I can do that. What are you trying to find out, Koichiro?"

Alexa via Echo Show "Sorry. I am not sure."

Google via iPhone Google app "2.5 hours. According to TechRader, recharging the smartwatch to 80% takes 1.5 hours...."

コメント: さすがGoogle。Siriは他人事。Alexaは質問を理解できていないのを誤魔化そうとしている。

英語の「書ける」と「話せる」

twitter.com

これはあるかな、と思ってます。

 

英語には単語ひとつひとつの発音として辞書に書かれている発音と、日常会話として文章の中で出てくるときの別の発音方法とが併存していて、ニュースやスピーチの英語と比べてネイティブ同士の日常会話では後者が頻発します。他にも要素がありますが、結果として、ある程度文法や語彙の力もあるし、ゆっくりなら自分の言いたいことも言えるのに、なぜか相手の英語は聞き取りづらいという非対称な状況が発生する気がします。

自分の場合、どうしても話が聞き取りづらいネイティブスピーカーの同僚がいたのですが、たまたま彼の話している英語の録音があったのでそれを何度か繰り返して聞いてみた結果、英語の言語としては確実にそこにあるであろう音をそもそも発音していないパターンが多いことに気がつきました。ネイティブスピーカー同士でも、彼の英語は若干もごもご聞こえるようで、会議で聞き直されたりしているのは見かけるのですが、こちらの耳とか理解の問題ではなく、そもそもこちらが英語の字面から想定している音が物理的に届いていないにも関わらず、他のネイティブや英語生活の長い社員は全く問題なく伝わっていることがあるとわかったのは目から鱗が落ちる思いでした。

いくつか教材的なものを探した結果、Jenniger ESLというYouTube上の英語講座での説明がとてもわかりやすかったです。Fast speechという切り口で、発音が脱落したり変化するパターンを色々と説明してくれます。

www.youtube.com

なお私の勤め先ではノンネイティブばかりだったりするので、はっきりと単語単語を発音する同僚が多く、実は、この発音問題で苦労する機会はあまり多くありません。ノンネイティブ同士は、凝った言い回しもしないので、その意味でも会話が楽ですね。

年次評価

こちらへ来て初めての年次評価がありました。

会社が同じとはいえ、日本を出た上で、これまで携わったことのない仕事をしても普通に通用するのかという点が一つの個人的な勝負ポイントだったわけですが、マネージャーから見た評価としては一応の合格点をもらえたようで、昨年今頃から始まった「渡航プロジェクト」がようやく一段落ついたという気がします。

とはいえ、課題がない訳ではありません。自覚もあるところですが、peer feedbackでも一貫して指摘されたのが、もっと会議で発言すべしという内容でした。英語についての自信を深めることが大切だと思っていますが、特に同じようなメンバーの中では「こいつは発言しない」という見方が固定してしまってからでは遅いので、いわゆる一つの射撃しつつ前進をする必要がありそうです。