The Grand Integer Lottery

Grand Integer Lottery (Python 3)

[Go to the problem at Hackerrank]

Problem Description

The Grand Integer Lottery is a deterministic search over a integer sequence ranging from S to E, based on a set of integers {n}=[n₁, ..., n_N].

Let's define the concept contiguous occurrence in string format (COSF) of a number a in a number b: we say that there is a contiguous occurrence in string format of a in b if, when both are considered as strings, a occurs as a contiguous block in b.

Examples of COSF: 3 in 13, 23 in 1234.

Examples of non-COSF: 3 in 12, 23 in 32134.

The lottery sequence is defined as the subset L of [S, E] such that for any l in L it is true that there is COSF of some integer n_k in l.

Example: S=1, E=35, {n}=[3, 11], then the lottery sequence is [3, 11, 13, 23, 30, 31, 32, 33, 34, 35].

The winning number P is defined as the Pth number in the lottery sequence if there is one, otherwise there is none.

Functional programming in Python (3.x, not 2.x)

Let's suppose that we already have the input data: S, E, {n} and P.

The lottery sequence can be generated in-line:

lotseq = list(filter((lambda l: any(x >= 0 for x in [l.find(x) for x in n])), [str(x) for x in list(range(S,E+1))]))

And the output is a simple if-else evaluation:

if P <= len(lotseq):
    print(lotseq[P-1])
else:
    print('DOES NOT EXIST')

Wow! Not so fast! 

Well that was easy. Considering that no timeout appear when using this implementation, we will not study the complexity of the solution. Instead, we will focus on understanding the power of each sub-expression.

First, the initial integer sequence [S, E]:

[str(x) for x in list(range(S,E+1))]

This snippet of code creates a sequence of strings where each element an integer in [S, E] converted to string format. Simple right? Second, the COSF implementation:

l.find(x)

That is not cheating. Python find function for string actually implements COSF. Here l is an element of lotseq. Third, deciding is an element of the initial sequence is to be placed in the lottery sequence:

any(x >= 0 for x in [l.find(x) for x in n])

This is the decision rule. It predicates if there is COSF of any element of n in l. Finally, applying the decision rule for every element of the initial sequence: 

list(filter((lambda l: any(x >= 0 for x in [l.find(x) for x in n])), [str(x) for x in list(range(S,E+1))]))

We made use of a lambda expression to define an anonymous in-line functional, and then applied it to the initial in a special way. This special way called filter takes one element of the initial sequence at a time and puts it in the lottery sequence only if the decision rule is satisfied. After assigning the result of this supercalifragilisticexpialidocious function to a variable, it's just a matter of finding the correct winning number, if there is any.

The Code

 The complete code that solves the challenge is given below:

# Grand Integer Lottery, by Juan Pablo Vega
# IEEEXtreme 8.0 (2014)
S, E, P, N = [int(k) for k in raw_input().split()]

n= []
for k in range(N):
    n.append(str(int(input())))

lotseq = list(filter((lambda l: any(x >= 0 for x in [l.find(x) for x in n])), [str(x) for x in list(range(S,E+1))]))

if P <= len(lotseq):
    print(lotseq[P-1])
else:
    print('DOES NOT EXIST')

You can download it here.

Alternative solution

A slightly different code:

# Grand integer lottery. Alternative solution by Juan I. Carrano.
# IEEEXtreme 8.0 (2014)
S, E, P, N = [int(k) for k in raw_input().split()]

nn = []
for dummy in xrange(N):
    nn.append(raw_input().strip())

def vale(t):
    coso = str(t)
    return any(ns in coso for ns in  nn)

lseq = [t for t in xrange(S, E+1) if vale(t)]

try:
    print lseq[P-1]
except IndexError:
    print "DOES NOT EXIST"

Download it.

More

In this Drive folder you will find code and test cases.