Google Code Jam - New Lottery Game

Ruby, 107

I expected this would be a much shorter program.

gets
loop{a,b,k=gets.split.map &:to_i
puts"Case ##{$.-1}: #{[*0...a].product([*0...b]).count{|x,y|x&y<k}}"}

Explanation

  • The first line of input can be ignored.
  • $. is the last read line number.
  • [*0...x] is a quick way to turn the Range into an Array. It uses the splat operator (*). Note that the Range is an exclusive one (... instead of ..).
  • Array#count takes a block. It will only count the elements for which the block returns a truthy value.

APL (63)

It's the I/O that costs a lot.

↑{a b k←¯1+⍳¨⎕⋄'Case #',(⍕⍵),': ',⍕+/∊k∊⍨a∘.{2⊥∧/⍺⍵⊤⍨10/2}b}¨⍳⎕

Explanation:

  • {...}¨⍳⎕: read a number N from the keyboard, and run the following function for each number from 1 to N.
  • a b k←¯1+⍳¨⎕: read three numbers from the keyboard, generate a list from 0..n-1 for each, and store these in a, b, and k.
  • a∘.{...}b: for each combination of values from a and b:
    • ⍺⍵⊤⍨10/2: get the 10-bit binary representation for both values (this is enough given the limits)
    • ∧/: and together all pairs of bits
    • 2⊤: turn it back into a number
  • k∊⍨: for each of these values, test if it is in k
  • +/: sum the result
  • 'Case #',(⍕⍵),': ',⍕: generate the output string for this case
  • : turn the result into a matrix, so each string ends up on a separate line.

Test:

      ↑{a b k←¯1+⍳¨⎕⋄'Case #',(⍕⍵),': ',⍕+/∊k∊⍨a∘.{2⊥∧/⍺⍵⊤⍨10/2}b}¨⍳⎕
⎕:
      5
⎕:
      3 4 2
⎕:
      4 5 2
⎕:
      7 8 5
⎕:
      45 56 35
⎕:
      103 143 88
Case #1: 10   
Case #2: 16   
Case #3: 52   
Case #4: 2411 
Case #5: 14377

Tags:

Code Golf