4
\$\begingroup\$

Challenge: A cipher (which is a positive integer) which has any substring not divisible by 2, or has a substring divisible by 11 (other than 0), is defined as 'bad'. All other ciphers are defined as 'good'. Find the kth cipher, in ascending order, which is 'good'.

Input format

The first line of input has a single integer T, the total number of test cases. The next T lines each have an integer k on them.

Output Format

The output should contain T integers on T different lines, the kth good cipher.

Sample Input

2
1
136

Sample Output

2
4008

\$\endgroup\$
  • 1
    \$\begingroup\$ The question should be reworded as a challenge statement, with an objective winning criterion (for example, shortest code). Although I find the question interesting, general help questions are off-topic here. See: codegolf.stackexchange.com/help/on-topic \$\endgroup\$ – primo Nov 9 '13 at 16:21
  • \$\begingroup\$ Thank you. I've done so accordingly. Please do have a look at the question now. \$\endgroup\$ – Train Heartnet Nov 9 '13 at 16:32
  • \$\begingroup\$ It's much closer to the acceptable format now. The winning criteria is still missing, though. If you intend for it to be code golf (i.e. shortest code), you can add the appropriate tag. I might also recommend changing the input format, to a single value k, and then list more than one test case. As it is, languages with verbose input handling are significantly disadvantaged. \$\endgroup\$ – primo Nov 9 '13 at 16:38
  • \$\begingroup\$ Something isn't consistent: Given that 4008 is 'good', I must infer that both the substrings 0 and 00 are considered "divisible by 2". This is the normal definition. But, by that normal definition, those substrings are also "divisible by 11" and hence 4008 must be 'bad' \$\endgroup\$ – MtnViewMark Nov 9 '13 at 16:46
  • \$\begingroup\$ I just noticed that now. I've edited the question, so as to not consider 0 to be divisible by 11. \$\endgroup\$ – Train Heartnet Nov 9 '13 at 16:52
2
\$\begingroup\$

Perl, 75 74 characters

map{map{1while++$n=~/[13579]|(.+)(?(?{$^N<1|$^N%11})!)/}1..<>;$n=say$n}1..<>

I should point out that the character count is taking advantage of Perl's bizarre feature of allowing a special variable of the form $^X to be spelled with a literal ctrl-X character.

The regex extensions being utilized are also terrifying, but boy do they come in handy.

\$\endgroup\$
  • \$\begingroup\$ Or if you'd like to avoid using $^N, the variable $+ should act identically in this case. Also, (?(?{...})!) should be replaceable by (??{...}). \$\endgroup\$ – primo Nov 10 '13 at 7:53
  • \$\begingroup\$ If you're not convinced, consider the following: n×10 + n ≡ 0 (mod 11) for all n ∈ ℤ (this follows directly from the fact that 10 ≡ -1 (mod 11). Therefore, for any match /(.+)(.)/, $1%11 == $2 if and only if $&%11 == 0, which is exactly what's needed. This will break whenever $1%11 == 10, but fortunately this situation can never occur, as all 1s have already been weeded out. \$\endgroup\$ – primo Nov 12 '13 at 11:02
2
\$\begingroup\$

Haskell, 187

import Data.List
d=drop 1
e=[]:d e>>=(\z->map(\y->z++[y])"02468")
f=filter
g=f(all((>0).(`rem`11)).f(>0).map(read.('0':)).(>>=inits).tails)e
main=interact$unlines.map((g!!).read).d.lines

Could save 4 characters by inlining g, but then the code wouldn't be quite as nice.

If the input wasn't preceded by a test case count (like in the Ruby submission), then could save 6 more characters.

& runhaskell 13166-Cipher.hs 
2
1
2
136
4008
\$\endgroup\$
2
\$\begingroup\$

APL (70)

⍪{⎕{⍺⍺<Z←⍺+∧/{~2|⍵,0=11|⍵~0}⍎¨⊃,/{↑∘⍵¨⍳⍴⍵}¨↓∘Z¨0,⍳⍴Z←⍕⍵:⍵⋄Z∇⍵+1}⍨0}¨⍳⎕
\$\endgroup\$
1
\$\begingroup\$

Ruby, 231 227 219

gets
s=[]
l=[]
while(g=gets.to_i)>0
s.push g
end
z=2
until l.size>=s.max
a=z.to_s.split''
l.push z if(1..a.size).flat_map{|n|a.each_cons(n).map{|x|x.join.to_i}}.all?{|x|x<1||x%11>0&&x%2<1}
z+=1
end
puts s.map{|x|l[x-1]}

Input is terminated with an empty line.

If the input was just a list of indeces without the length, I could save 5 characters.

Sample run:

c:\a\ruby>goodc
2
1
136

2
4008

c:\a\ruby>
\$\endgroup\$
1
\$\begingroup\$

Sage Notebook, 167 166

for k in list(file(DATA+'i'))[1:]:
 j=n=0
 while j<int(k):n+=1;j+=not[t for t in[int(`n`[i:j])for i in[0..len(`n`)]for j in[i+1..len(`n`)]]if(t%11==0)*t+t%2]
 print n

Sample run ...

Input (in data file named 'i'):

2
1
136

Output:

2
4008


Python 2, 180 179

for k in[input()for i in[0]*input()]:
 j=n=0
 while j<int(k):n+=1;j+=not[t for t in[int(`n`[i:j])for i in range(len(`n`))for j in range(i+1,len(`n`)+1)]if(t%11==0)*t+t%2]
 print n

Sample run ...

>>> 2
>>> 1
>>> 136
2
4008
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.