I was looking around on the web and I found this Google Code Jam Puzzle. I really liked it so I decided to post it here.

New Lottery Game

The Lottery is changing! The Lottery used to have a machine to generate a random winning number. But due to cheating problems, the Lottery has decided to add another machine. The new winning number will be the result of the bitwise-AND operation between the two random numbers generated by the two machines.

To find the bitwise-AND of X and Y, write them both in binary; then a bit in the result in binary has a 1 if the corresponding bits of X and Y were both 1, and a 0 otherwise. In most programming languages, the bitwise-AND of X and Y is written X&Y.

For example: The old machine generates the number 7 = 0111. The new machine generates the number 11 = 1011. The winning number will be (7 AND 11) = (0111 AND 1011) = 0011 = 3.

With this measure, the Lottery expects to reduce the cases of fraudulent claims, but unfortunately an employee from the Lottery company has leaked the following information: the old machine will always generate a non-negative integer less than A and the new one will always generate a non-negative integer less than B.

Catalina wants to win this lottery and to give it a try she decided to buy all non-negative integers less than K.

Given A, B and K, Catalina would like to know in how many different ways the machines can generate a pair of numbers that will make her a winner.

Could you help her?


The first line of the input gives the number of test cases, T. T lines follow, each line with three numbers A B K.


For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of possible pairs that the machines can generate to make Catalina a winner.


1 ≤ T ≤ 100. Small dataset

1 ≤ A ≤ 1000. 1 ≤ B ≤ 1000. 1 ≤ K ≤ 1000. Large dataset

1 ≤ A ≤ 109. 1 ≤ B ≤ 109. 1 ≤ K ≤ 109. Sample

Input                 Output
5                     Case #1: 10
3 4 2                 Case #2: 16
4 5 2                 Case #3: 52
7 8 5                 Case #4: 2411
45 56 35              Case #5: 14377
103 143 88

In the first test case, these are the 10 possible pairs generated by the old and new machine respectively that will make her a winner: <0,0>, <0,1>, <0,2>, <0,3>, <1,0>, <1,1>, <1,2>, <1,3>, <2,0> and <2,1>. Notice that <0,1> is not the same as <1,0>. Also, although the pair <2, 2> could be generated by the machines it wouldn't make Catalina win since (2 AND 2) = 2 and she only bought the numbers 0 and 1.

Here's the link for actual problem: https://code.google.com/codejam/contest/2994486/dashboard#s=p1

This is code-golf, so shortest code wins. Good Luck

  • \$\begingroup\$ Is a trailing newline optional and a leading newline allowed? \$\endgroup\$ – John Dvorak Nov 1 '14 at 7:14

Ruby, 107

I expected this would be a much shorter program.

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


  • 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.
  • \$\begingroup\$ Any chance you can do $<.map{...}? \$\endgroup\$ – John Dvorak Nov 1 '14 at 6:42
  • \$\begingroup\$ It's actually two characters longer, because it has to take an argument. \$\endgroup\$ – britishtea Nov 1 '14 at 14:59

APL (63)

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

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


  • {...}¨⍳⎕: 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.


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

Golfscript - 74 64

Here is my Golfscript solution (could probably be improved):

n/(;0:m;{[~0:w.{{.2$&3$<w+:w;)}4$*;)0}5$*];'Case #'m):m': 'w n}%

Here is the pseudocode I used for this:

Split string at newlines
Get rid of first element (this is not needed, as I am looping through each element anyway)
Let m=0 (case #)
For each group of 3 numbers A, B, and K:
  Let w=0 (number of winning combinations)
      If (A&B)<K
        Let w=w+1 (one more winning combination)
  Let m=m+1 (case # incremented)
  Output("Case #",m,": ",w,"/n")

Assumes valid input.


CJam - 62

Could probably be improved; this is just a port of my Golfscript answer.

qN/(;{[~0_{{_2$&3$<V+:V;)}4$*;)0}5$*];"Case #"T):T": "V0:V;N}%

Ruby - 145

I'm still learning Ruby, so there's probably a shorter way to do this.

(1..gets.to_i).each{|_|a,b,k=gets.split.map{|x|x.to_i};x=0;(0...k).each{|i|(0...a).each{|j|(0...b).each{|k|x+=1 if j&k==i}}};p"Case ##{_}: #{x}"}


( 1 .. gets.to_i ).each{ | _ |
    a, b, k = gets.split.map{ | x | x.to_i }
    x = 0

    ( 0 ... k ).each{ | i |
        ( 0 ... a ).each{ | j |
            ( 0 ... b ).each{ | k |
                x += 1 if j & k == i

    p "Case ##{_}: #{x}"
  • 1
    \$\begingroup\$ Looping with #map is one character shorter than with #each. You don't need to loop trough 0...k, you can simply check if the binary and is lower than k. When you're only calling a method without arguments in a block you can use Symbol#to_proc (x.map &:to_i). \$\endgroup\$ – britishtea Nov 1 '14 at 4:59

J, 90 (70)

I/O to stdin/stdout, works as a script (90).

,&LF@('Test #'&,)"1@(":@#,{:)\@:}.@:(': '&,"1)@(+/@,@(>`(17 b./&i.)/@|.)&.".;._2)&.stdin''

Input on stdin, output implicit in REPL (akin to APL, I believe) (70).

'Test #',"1(":@#,{:)\}.': ',"1+/@,@(>`(17 b./&i.)/@|.)&.".;._2 stdin''

Ergh, J isn't good at I/O requirements like these.

For the curious, the part doing the heavy work is +/@,@(>`(17 b./&i.)/@|.)&."., which solves a single line of the problem (taking and returning a string).


CJAM - 57

0li{)"Case #"\':Sl~:K;L\{(2$,{1$&@+\}%~}h;\;{K<},,N4$}\*;

I think this can be golfed further.

0                                  acts as a counter for the case #
  li{                              accepts the first line of input as integer/opens block
     )                             iterates counter
      "Case #"\':S                 adds "Case #X: " to stack (though in 4 parts)
       l~:K;L\                     takes next line of input, assign K, add null array
          (2$,                     decrease B and generate list of number <A
            1$&                    Copy the current value of B, do & with current n<A
             @+\                   Add the new possible lottery number to array
           }%~                     loop for each element if the list of numbers <A
         }h                        loop which repeats for all numbers less than B
       ;/;{K<},,                   trim and count the possible numbers less than K
      N4$                          add new line and copy the counter back in place
  }\*                              runs the block T times
;                                  removes the counter so it doesn't print


Case #1: 10
Case #2: 16
Case #3: 52
Case #4: 2411
Case #5: 14377
  • \$\begingroup\$ li{"Case #"]_,6/)+~':Sl~:K;L\{(2$,{1$&@+\}%~}h;\;{K<},,N}* for fun, this does the same thing but instead of having a counter for case#, it counts the number of elements in the stack. \$\endgroup\$ – kaine Nov 1 '14 at 23:32

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.