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  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)

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


 数字 单词 向量 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)

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原创, 转载注明出处喵～