「Google にソフトウェアエンジニアとして入社して10年と10日がたちました」のクイズを解いた

Google にソフトウェアエンジニアとして入社して10年と10日がたちました — hayato.io

面白かったので、今からでも挑戦してみてほしい。 プログラミングが大変なのは最初のステップだけで、あとはひらめき。 下に解法を書く。 出題者のきらきら☆はやとたんさんの許可は得ています。

































































問題の画像はジュリア集合。 また、PNG内にJuliaというkey名で、left=0.0,top=-0.75,width=1.5,height=1.5,c=-0.?????-0.?????iというコメントがある。

一部は伏せ字でパラメタが与えられているので、伏せ字の部分を計算すれば同じ画像が生成できそう。 ここが一番大変だった。 全探索は無理なので、上位桁だけ探索して、差分が小さい値の下位桁を探索したり、画像の一部だけで差分を計算したりした。 伏せ字の部分の答えは、c=-0.75037-0.11177i。 次のプログラムで問題の画像と(ほぼ)同じ画像が得られる。

from PIL import Image
img = Image.new("RGB", (797, 797))
for y in range(797):
  for x in range(797):
    p = (x/797.*1.5)+(y/797.*1.5-0.75)*1j
    c = 0
    while c<255:
      p = p*p + (-0.75037-0.11177j)
      if abs(p)>2.:
        break
      c += 1
    img.putpixel((x, y), (c, c, c/2+128))
img.save("ans.png")
print "".join(map(chr, C))

f:id:kusano_k:20180228183855p:plain

この画像と問題の画像には差がある。 問題の画像を拡大して良く見ると、ポツポツと点が見える。 ジュリア集合にはこのような点は無いはず。

f:id:kusano_k:20180228184425p:plain

問題の画像と本来のジュリア集合で差があるところの差分を調べると次のようになっている。

32, 68, 68, 32, 32, 68, 50, 32, 32, 32, 32, 50, 32, 32, 32, 32, 32, 32, 32, 50, 32, 32, 32, 32, 32, 32, 32, 32, 48, 50, 50, 32, …

値の範囲がASCIIコードっぽいので、文字に直す。

 DD  D2    2       2        022    A 22 2  0 1   20 00  0      2  2 0     D D         2 0        60 2    0   4    7  0   0  6  002  2 02  63      222 72   2   22      2  0 0             2   6 2     00 2                0   0  0  0          D  2   0  2 7  F  2     2   4    C        0            7       0   02  D  D     2         0 0     0  2 0    6  02002 2   2   2 00    0C 1 3      0     2D   2D2 2  0  0   C   F     022 0   1  02      0  6             32     2        2  B2       22      6                    020   0      2  02  0    3     2       D2        2  00   0E         0   87   0 20     EF     2    2 34  1    2   D2  D      DDD  00    2  6    0   2     6 2   2         2   0    6 3 93 2 0  0    2     D 2  20 2  2   6 2   2   0      2  200   2   200       0    30 0  0   2 DD        2       0  2  0    20        0  02    0 6             23               2  2            20       0 0    0          2   2   22             6 20   2                 20      7         22 6    0     2 2     0   22    3    A  22       D  DD   D        A00 E 0 2      2  9 22 2          02   0      3  6      0       D  2 D   2  2  7 2             F7 50              0 0     4  1  370 0      2 2     D 2 0        0   2 0   00 0 4    200 0      0  2202 0  2  38  2 2    DD 2 2    22     2  0C    2   0        2                2       3 83936  2    C2  D  2  D  D   00    2  7  2  2  20 220  0    20 0        2  2     3    00       2  D22   2    2      7 0   2 2  7 0    2        0B  200 0  02 73     02   2        D    D 2 200 2 0      2   2   7      222          2 2        0 3   20 00    D 22 2DD2 0      2 22    0 0    2     0         2          0  3 6 5C 00   A 2D 2D  D 2 D 2 0      0      020      7 220 000   2072 2       7   37 2  2 0     D     D 22 0     0 2 63200 2   0 04 4    0 22     2   0  0          022 22  D 2    D    D     2    2 2  2 0 2   260 20   2   A      0 0    2 9 2    0        D       D  22   0  0     20     2  8 6 2 2 0     07       2     6  3     0    D    D  2       22     11       0     8    2      2 2 0          4     2        22   2    2      2 20 72 0      0        0   0   0   2 2      2  3   2000 0 2  DD        DD      2 2     2 2   2            2   2 0     0  2  2    6       B       D  2D    2           02    0 0   00  0      0               7             22           0 0  0   4   7    2  2 7 7   2         00     0 0    34 0   2 2 2    2   DD    2 20  000          2 0 4             9 22 0      6 3 7     2 2     DD     2  20 002  22       00 0 C   6  0 020027 2 7   2  02 2    33  2   0    D   22 2D   202  0   27        20 2   72 22  20    9     2   0  0      2  2 2 222 D      2   0   200      02       6 6       2        02 2     3   5   0     D D   D    D  22   0           0    6   0  0         0  2      5  3   2  20   D      22D2 2  0  02      02C           9   2 2        0 00         493 0     D2     DD 2   D   2     0     2   0   5   2      0C 0 6    2    2   536   0        2     D 2D2 20     225  00 0        5        2 2  F   2   0   0      2   002   D  2 D DD2  0  2     602   2    0        00 002  6  2  0 0        1    0        22D      D    0       0    2 2    8 702     2      070      6 1 8 00  22    2 2  2  2 2   2   02       A0  2 2   6  20        2      20220 1     3   0 2 D D  D  2      0       00 2   200    0      0    00    2   0 0      3 31   2 0  D  D  D  D DD     2 0      27           4 22 2   200 7 2C2  2       6 32     2  2 2      22  2     22 2    C0  0   2            0   50       20 63   2 0     2    2 2      2  2        0         A02    0            0 0    0 725 4         D D D D  2       0 0  0  C2   22   07  9  0  2   2 2  72    2     3    3  2 0  2       D  D     20     0   02  2 0  2 6           0        0        66   0    D     2           22  22  0     02   0   622  00   2  2   2    2 4 6        2   2 D  D    2   0    2  0  2  0 02     0   000   20  2     0   00 684       0   2     2            0 0        0    2         0   2   F 020       5   63    2          D D2 D         02   22  2 0   2  28   2        2      0 22           0 0    2   2        002    26    2  2   0  0 2220  0     02    2          5      2  2 DDD   D 2       0  0    020 00 0 2   2    2     0        2     3    0   22  DD   2     D  202 022    00  202   C  E 0 002  2  0277    2    0        2 0 00D2 2   2D         2 0     2   02 2    7  70 2 02   20 4     0 2 2  8  5  0     2D   2  2        00   2            22            0    6 0A   0000  3    2   0   2            D0   22  2 1  202  0 0  26  2 0     202    720   2  3   3   2   2    2 DD   D2 22  2       02   0 22     6   2         9 2  222       6   202  0     D     2  D  2  00  0  0  02 0  0   390  0   2    6 0 0        3   6 0  22   2 D     2  2 0     2 0      2   0      62   2 00   5D        0   335        2 D      D2 DDD2      0 2 7  0 00  2          20         2C 0  22  6     0 2 00  2D 2       2   2    20   22  22   2  67             2     2 00  63 3   2    2 D  D   2      B        02  0 2    0 20  6F 20     0 0 6       2   09  21   0 0         2D   20     20 2 4  2 0        2F 0 2 2  2 2  50   00   2    3       2   2  2 D  D   A   0 0 20    0  0 220   E6   0     2   2 0  2    0     3 0  22       D        7  0      0   2 2 0       4       2 0    2     2 0 4  6  2    0   D  D22 D2    C20 2        20       0   6 2  0  0     E 2 2   02   6 53 2    0 2  2    2  2          0        22 0 2   5 0 22               0 0        0     0     D 2 D  D 2  2   2 2  0    0   2    2720  0     5   0   2   72       2 0   D        22D      0  0     0 0 2         5 2    2 2  0  2   0 2   666    0                 2D 0         6         00    2 0      0 4      02 0    3    22   22         DD D  22 2  2 0        0  2 2   E0 00          0 0   22            2       2  D 22      0  0       200 0  209         0020   0      00       0          D    22    0          9 2  2 2      202 22     0       2 02 2      6  0  000      D  DDD      2            2       0         7  6      2202     6    2 22         D        0   2  24  0   00 2   646 70  20 C  8   220 0   C   63 7 0      2 22    22 2         2 3 22     20     22C   0 2 2  6  0     0   3   3       2  D    2  D2    2 0        0       00  D 2 202     26  2   0 22 0     6   000     D   B   D   0     2  6 0       22 27  00  0       6    222   A  12  C   2 20  22    

ここでだいぶ悩んだ。 ジュリア集合との差分で値を埋め込む方式では、元の画像が明るいところには値を埋め込めないので、値が埋め込まれている位置には意味が無い……?とか、空白と16進数の文字で出現頻度に偏りがあるが……?とか考えた。

この文字列の長さは6241文字である。 ところで、問題の画像のサイズは797x797ピクセルだった。 なぜ800x800ではなく、こんな中途半端な値なのだろう? 797は素数だった。 また、6241は792素因数分解できる。

ということで、この文字列を79文字ごとに改行して正方形にしてみる。

 DD  D2    2       2        022    A 22 2  0 1   20 00  0      2  2 0     D D  
       2 0        60 2    0   4    7  0   0  6  002  2 02  63      222 72   2  
 22      2  0 0             2   6 2     00 2                0   0  0  0        
  D  2   0  2 7  F  2     2   4    C        0            7       0   02  D  D  
   2         0 0     0  2 0    6  02002 2   2   2 00    0C 1 3      0     2D   
2D2 2  0  0   C   F     022 0   1  02      0  6             32     2        2  
B2       22      6                    020   0      2  02  0    3     2       D2
        2  00   0E         0   87   0 20     EF     2    2 34  1    2   D2  D  
    DDD  00    2  6    0   2     6 2   2         2   0    6 3 93 2 0  0    2   
  D 2  20 2  2   6 2   2   0      2  200   2   200       0    30 0  0   2 DD   
     2       0  2  0    20        0  02    0 6             23               2  
2            20       0 0    0          2   2   22             6 20   2        
         20      7         22 6    0     2 2     0   22    3    A  22       D  
DD   D        A00 E 0 2      2  9 22 2          02   0      3  6      0       D
  2 D   2  2  7 2             F7 50              0 0     4  1  370 0      2 2  
   D 2 0        0   2 0   00 0 4    200 0      0  2202 0  2  38  2 2    DD 2 2 
   22     2  0C    2   0        2                2       3 83936  2    C2  D  2
  D  D   00    2  7  2  2  20 220  0    20 0        2  2     3    00       2  D
22   2    2      7 0   2 2  7 0    2        0B  200 0  02 73     02   2        
D    D 2 200 2 0      2   2   7      222          2 2        0 3   20 00    D 2
2 2DD2 0      2 22    0 0    2     0         2          0  3 6 5C 00   A 2D 2D 
 D 2 D 2 0      0      020      7 220 000   2072 2       7   37 2  2 0     D   
  D 22 0     0 2 63200 2   0 04 4    0 22     2   0  0          022 22  D 2    
D    D     2    2 2  2 0 2   260 20   2   A      0 0    2 9 2    0        D    
   D  22   0  0     20     2  8 6 2 2 0     07       2     6  3     0    D    D
  2       22     11       0     8    2      2 2 0          4     2        22   
2    2      2 20 72 0      0        0   0   0   2 2      2  3   2000 0 2  DD   
     DD      2 2     2 2   2            2   2 0     0  2  2    6       B       
D  2D    2           02    0 0   00  0      0               7             22   
        0 0  0   4   7    2  2 7 7   2         00     0 0    34 0   2 2 2    2 
  DD    2 20  000          2 0 4             9 22 0      6 3 7     2 2     DD  
   2  20 002  22       00 0 C   6  0 020027 2 7   2  02 2    33  2   0    D   2
2 2D   202  0   27        20 2   72 22  20    9     2   0  0      2  2 2 222 D 
     2   0   200      02       6 6       2        02 2     3   5   0     D D   
D    D  22   0           0    6   0  0         0  2      5  3   2  20   D      
22D2 2  0  02      02C           9   2 2        0 00         493 0     D2     D
D 2   D   2     0     2   0   5   2      0C 0 6    2    2   536   0        2   
  D 2D2 20     225  00 0        5        2 2  F   2   0   0      2   002   D  2
 D DD2  0  2     602   2    0        00 002  6  2  0 0        1    0        22D
      D    0       0    2 2    8 702     2      070      6 1 8 00  22    2 2  2
  2 2   2   02       A0  2 2   6  20        2      20220 1     3   0 2 D D  D  
2      0       00 2   200    0      0    00    2   0 0      3 31   2 0  D  D  D
  D DD     2 0      27           4 22 2   200 7 2C2  2       6 32     2  2 2   
   22  2     22 2    C0  0   2            0   50       20 63   2 0     2    2 2
      2  2        0         A02    0            0 0    0 725 4         D D D D 
 2       0 0  0  C2   22   07  9  0  2   2 2  72    2     3    3  2 0  2       
D  D     20     0   02  2 0  2 6           0        0        66   0    D     2 
          22  22  0     02   0   622  00   2  2   2    2 4 6        2   2 D  D 
   2   0    2  0  2  0 02     0   000   20  2     0   00 684       0   2     2 
           0 0        0    2         0   2   F 020       5   63    2          D
 D2 D         02   22  2 0   2  28   2        2      0 22           0 0    2   
2        002    26    2  2   0  0 2220  0     02    2          5      2  2 DDD 
  D 2       0  0    020 00 0 2   2    2     0        2     3    0   22  DD   2 
    D  202 022    00  202   C  E 0 002  2  0277    2    0        2 0 00D2 2   2
D         2 0     2   02 2    7  70 2 02   20 4     0 2 2  8  5  0     2D   2  
2        00   2            22            0    6 0A   0000  3    2   0   2      
      D0   22  2 1  202  0 0  26  2 0     202    720   2  3   3   2   2    2 DD
   D2 22  2       02   0 22     6   2         9 2  222       6   202  0     D  
   2  D  2  00  0  0  02 0  0   390  0   2    6 0 0        3   6 0  22   2 D   
  2  2 0     2 0      2   0      62   2 00   5D        0   335        2 D      
D2 DDD2      0 2 7  0 00  2          20         2C 0  22  6     0 2 00  2D 2   
    2   2    20   22  22   2  67             2     2 00  63 3   2    2 D  D   2
      B        02  0 2    0 20  6F 20     0 0 6       2   09  21   0 0         
2D   20     20 2 4  2 0        2F 0 2 2  2 2  50   00   2    3       2   2  2 D
  D   A   0 0 20    0  0 220   E6   0     2   2 0  2    0     3 0  22       D  
      7  0      0   2 2 0       4       2 0    2     2 0 4  6  2    0   D  D22 
D2    C20 2        20       0   6 2  0  0     E 2 2   02   6 53 2    0 2  2    
2  2          0        22 0 2   5 0 22               0 0        0     0     D 2
 D  D 2  2   2 2  0    0   2    2720  0     5   0   2   72       2 0   D       
 22D      0  0     0 0 2         5 2    2 2  0  2   0 2   666    0             
    2D 0         6         00    2 0      0 4      02 0    3    22   22        
 DD D  22 2  2 0        0  2 2   E0 00          0 0   22            2       2  
D 22      0  0       200 0  209         0020   0      00       0          D    
22    0          9 2  2 2      202 22     0       2 02 2      6  0  000      D 
 DDD      2            2       0         7  6      2202     6    2 22         D
        0   2  24  0   00 2   646 70  20 C  8   220 0   C   63 7 0      2 22   
 22 2         2 3 22     20     22C   0 2 2  6  0     0   3   3       2  D    2
  D2    2 0        0       00  D 2 202     26  2   0 22 0     6   000     D   B
   D   0     2  6 0       22 27  00  0       6    222   A  12  C   2 20  22    

これを縦に読むと2がだいたい交互に出てくることに気が付く。 縦に読んで、空白を削除すると、

2B2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2B0A7C20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020207C0A7C202020202020202020202020202020202020202020202020202020202020436F6E67726174756C6174696F6E7321202020202020202020202020202020202020202020202020202020202020207C0A7C20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020207C0A7C20202020202020202020202020202022446F20746865207269676874207468696E672E204D61792074686520636F6465206265207769746820796F752E222020202020202020202020202020207C0A7C20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020207C0A7C20202020202020202020202020202020202020202020202020205468616E6B20796F7520666F7220796F75722074696D652E2020202020202020202020202020202020202020202020202020207C0A7C20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020207C0A7C20437265617465642062792062383630636132383364303135643833396631303433313237353336666232393063373438646665353938373439613635323363623130663635653031323561207C0A7C20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020207C0A2B2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2D2B

となる。16進数として文字列に直すと、

+-----------------------------------------------------------------------------+
|                                                                             |
|                              Congratulations!                               |
|                                                                             |
|               "Do the right thing. May the code be with you."               |
|                                                                             |
|                          Thank you for your time.                           |
|                                                                             |
| Created by b860ca283d015d839f1043127536fb290c748dfe598749a6523cb10f65e0125a |
|                                                                             |
+-----------------------------------------------------------------------------+

「画像に隠されたメッセージ」はDo the right thing. May the code be with you.なので、私(@kusano_k)の場合は、

$ echo -n 'kusano_k' 'Do the right thing. May the code be with you.' | sha256sum
ffc5b750d7a37441f98ca4f9e4912bf7ad956934a4e9b4fe1740a935bd056235  -

10周年おめでとうございます!