Google Code Jam 2016 Round 1B Problem A in J language

You just made a new friend at an international puzzle conference, and you asked for a way to keep in touch. You found the following note slipped under your hotel room door the next day:

"Salutations, new friend! I have replaced every digit of my phone number with its spelled-out uppercase English representation ("ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" for the digits 0 through 9, in that order), and then reordered all of those letters in some way to produce a string S. It's up to you to use S to figure out how many digits are in my phone number and what those digits are, but I will tell you that my phone number consists of those digits in nondecreasing order. Give me a call... if you can!"

You would to like to call your friend to tell him that this is an obnoxious way to give someone a phone number, but you need the phone number to do that! What is it?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S of uppercase English letters.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of digits: the phone number.

Limits

1 ≤ T ≤ 100.
A unique answer is guaranteed to exist.

Small dataset

3 ≤ length of S ≤ 20.

Large dataset

3 ≤ length of S ≤ 2000.

Sample

Input	Output
4 OZONETOWER WEIGHFOXTOURIST OURNEONFOE ETHER	Case #1: 012 Case #2: 2468 Case #3: 114 Case #4: 3

解题思路：

由于这道题是给出的是字符串，并且是由任意数量的、0-9这10个数字的英文单词乱序组成的。那么最早的反应是动规？不过已经不会写了。但也因此找到了另一个好办法。

首先把"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"写出来，然后留下出现过的字母，它们是"EFGHINORSTUVWXZ"，共15个。

现在我们来画一个表，它将表示每个单词所用的字母的个数及位置。

数字	单词	向量
		0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
		E F G H I N O R S T U V W X Z
0	ZERO	(1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1)
1	ONE	(1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
2	TWO	(0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0)
3	THREE	(2, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0)
4	FOUR	(0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0)
5	FIVE	(1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0)
6	SIX	(0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0)
7	SEVEN	(2, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0)
8	EIGHT	(1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
9	NINE	(1, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0)

如果我们将上面的10个向量组成矩阵的话，我们将得到一个10x15的矩阵，这里假定所得的矩阵为A。

接下来，由于是任意个数的0-9组合，我们可以将此题看为一个求解线性方程组xA=b的题目。x是一个1x10的列向量，其意义为每个数字的个数。b是一个1x15的列向量，其意义为每个字母的个数，且b可以通过给出的输入计算。

要求解xA=b，最简单的办法就是左右两边同时右乘A的逆。可惜这里A并非方阵，不能求逆矩阵。不过说来也巧，观察上表，正好有5列都只有唯一的一个1，它们分别是第2(G)、10(U)、12(W)、13(X)、14(Z)列，这也就意味着，只要其中一列所对应的字母出现了n次，那么唯一的那个1在行上所对应的数字一定出现了n次。比如第2列的G，在0-9的字母中，只有8, EIGHT, 才带有G，因此如果G出现了n次，那么EIGHT必定出现n次！

于是我们就可以先利用上述方法消去5列，得到一个10x10的矩阵，然后就可以利用如下式子来求解x了。（当然，在消去的过程中，b中相应字母的计数要减少）

xA   = b
xAA^-1= bA^-1
x    = bA^-1

我们得到的新的矩阵D如下，

数字	单词	向量
		0 1 3 4 5 6 7 8 9 11
		E F H I N O R S T V
0	ZERO	(1 0 0 0 0 1 1 0 0 0)
1	ONE	(1 0 0 0 1 1 0 0 0 0)
2	TWO	(0 0 0 0 0 1 0 0 1 0)
3	THREE	(2 0 1 0 0 0 1 0 1 0)
4	FOUR	(0 1 0 0 0 1 1 0 0 0)
5	FIVE	(1 1 0 1 0 0 0 0 0 1)
6	SIX	(0 0 0 1 0 0 0 1 0 0)
7	SEVEN	(2 0 0 0 1 0 0 1 0 1)
8	EIGHT	(1 0 1 1 0 0 0 0 1 0)
9	NINE	(1 0 0 1 2 0 0 0 0 0)

此时对D求逆，然后右乘于b，再在对应位置上加上刚才消去的5列，即可得出结果。

Solutions in J lang

#!/usr/bin/env jconsole

NB. convert string to decimal
atoi=: 10"_#. '0123456789'"_ i. ]

NB. convert number to string
itoa=: ":"0

NB. all possible letters
letters=: 'EFGHINORSTUVWXZ'

NB. inverted matrix
inverted=: %. 10 10 $ 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 2 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 2 0 0 0 0 0

NB. handle significant columns
significant=: 3 : 0
    column=. > 0 { y
    number=. > 1 { y
    word=. > 2 { y 
    
    value=. column { counter
    phonenumber=: value number } phonenumber
    
    positions=. letters i. word
    counter=: (value -~ counter {~ positions) positions } counter
)

NB. Handle case
case=: 3 : 0
    NB. convert the number of cases into decimal
    cases=: atoi > 0 { y
    current=: 0
    line=: 0
    while. current ~: cases do.
        NB. take input, compute and print
        current=: >: current
        line=: >: line

        NB. setup counter
        counter=: 0 $~ # letters
        n=: > line { y

        NB. count times for each letter
        count=: (~. n) ;" 0 (+/ " 1 =n)

        NB. the number of letters, no duplication
        isolations=: 0 { $ count

        NB. fill in the counter
        index=: 0
        while. index ~: isolations do.
            pair=: index { count
            counter=: (> 1 { pair) (letters i. > 0 { pair) } counter
            index=: >: index
        end.

        NB. initialize phonenumber
        phonenumber=: 10 $ 0

        NB. there are some significant columns
        significant 2  ; 8 ; 'EIGHT'
        significant 10 ; 4 ; 'FOUR'
        significant 12 ; 2 ; 'TWO'
        significant 13 ; 6 ; 'SIX'
        significant 14 ; 0 ; 'ZERO'

        NB. solve the linear equation
        vector=: 1 10 $ 0 1 3 4 5 6 7 8 9 11 { counter
        partial=: vector (+/ . *) inverted
        phonenumber=: 0 { partial + 1 10 $ phonenumber

        NB. assemble the result
        number=: 0
        result=: ''
        while. number ~: 10 do.
            count=: number { phonenumber
            while. count ~: 0 do.
                result=: result , itoa number    
                count=: <: count
            end.
            number=: >: number
        end.

        NB. print the result
        result=: 'Case #' , (itoa current) , ': ' , result
        result (1!:2) 4
        echo ; ":&.> ''
    end.
)

NB. get data and handle them
] input=: <;._1 LF , stdin ''
case input
exit 0

Cocoa