Finding a winner in a "long list"

Question

This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win" markets for 13 games. A punter can select any combination of the possible outcomes which are encoded in a following way:

1 - home team wins
2 - draw
4 - away team wins
3 - home team wins or draw
5 - home team wins or away team wins
6 - draw or away team wins
7 - home team wins or draw or away team wins

Meaning a [3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7] represents a selection where punter put following bets:

• "home team wins or draw" in a first game
• "home team wins" in games 2-12
• "home team wins or draw or away team wins" in 13th game

After games are finished there will be another 13 elements list representing winning outcomes, for example: [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] means that in a first game away team won and in all other games home team won.

The question is if I'm missing any properties within those numbers that will make finding a winning bets easier than comparing each number one by one? Like in our case case checking if there are bets that has 4,5, 6 or 7 for the first game and 1, 3, 5 or 7 for rest of them.

Answer 1

The bitwise and of the bet and result is nonzero if and only if the bet is winning. Further, the bitwise and has exactly one bit set if the bet wins.

To see this, note that the encoding of a bet has bit $1$ set iff it wins if the home team wins, bit $2$ set iff it wins if the game is a draw, and bit $4$ set iff it wins if the away team wins.

For example, if our bet is 6 - draw or away team wins, its binary encoding is 110. Then if the away team wins, the result is encoded as 100 and the bitwise and is 100. If the home team wins, the result is encoded as 001 and the bitwise and is 000.

In the word-ram model this can even help us calculate the result asymptotically faster: if the encodings of the bets and results are stored consecutively in binary with 3 bits per number, then counting the number of bits in the bitwise and of these two sequences gives the number of won bets in $\mathcal{O}(\frac{n}{w})$ with $w$ bits per word. Similarly all winning bets could be found in $\mathcal{O}(\frac{n}{w} + r)$ where $r$ is the number of winning bets. Of course this assumes the representation of the data is convenient for us, if it isn't, we need $\mathcal{O}(n)$ work to change its representation.

For example, the bets [3, 6, 1] and results [4, 2, 1] would be represented as 110011100 and 001010100 respectively, the bitwise and of which is 000010100. This indeed has two set bits corresponding to the two winning bets.