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
声明: 本文为0xBBC原创, 转载注明出处喵~

发表评论

电子邮件地址不会被公开。 必填项已用*标注