Sherlock and The Beast

I have recently written the program for the Sherlock and The Beast' HackerRank challenge. That's working fine, but the problem is that it takes too much time if a big number is given as a input. I would like you to help me out in optimizing my code so that it could run under 16 seconds, which is needed.

from collections import Counter
def isDecent(n):
digits = list(map(int, str(n)))
if not set(str(n)).issubset('35'): return False
threes = Counter(digits)[3]
fives = Counter(digits)[5]
if threes % 5 == 0 and fives % 3 == 0: return True
else: return False

inps = []
decents = []
t = int(input())
for i in range(t): inps.append(int(input()))
for inp in inps:
if inp == 1:
decents.append(-1)
continue
n=2
while True:
if(isDecent(n) and len(str(n)) == inp): break
n+=1
if n != 2: decents.append(n)
else: decents.append(-1)
for decent in decents: print(decent)


Is there any thing that could be used to optimize it?

-
Can't you just people answer it rather than editing? :P nevamind. – Mohammad Areeb Siddiqui Mar 7 '14 at 15:04
How long did it take you to write the above code? – rolfl Mar 7 '14 at 15:15
10 min @rolfl :) – Mohammad Areeb Siddiqui Mar 7 '14 at 15:51
FYI, the Java solution below ranked with score 30... apparently the maximum. – rolfl Mar 7 '14 at 16:34

Your algorithm is way off.... ;-)

Let's consider the solution to a decent number.

For any decent number, the more 5's we put at the front, the better.

So, let's break it down to some maths....:

• d => number of digits in the decent number
• f => number of fives in the decent number
• t => number of threes in the decent number

also

• d = f + t
• f % 3 == 0
• t % 5 == 0

We have:

d = f + t


Algorithm:

// tmp number of five values is the number of digits
ftmp = d
// decrease the number of fives (by the number of threes in a batch)
// until both the rules f % 3 == 0 and t % 5 == 0 are satisfied
while ftmp % 3 != 0 : ftmp -= 5

check the ftmp is a valid value
if ftmp % 3 != 0 : return -1;

f = ftmp;
t = d - f

return "5" x f + "3" x t


Writing it in Java, I have the following:

private static String sherlock(final int target) {
int threes = 0;
int fives = 0;
int digits = target;
while (digits > 0) {
if (digits % 3 == 0) {
fives = digits;
break;
}
digits -= 5;
}
threes = target - digits;
if (digits < 0 || threes % 5 != 0) {
return "-1";
}
StringBuilder sb = new StringBuilder(target);
while (fives-- > 0) {
sb.append("5");
}
while (threes-- > 0) {
sb.append("3");
}
return sb.toString();
}


For me, on my laptop, this solves the 100000 digit problem in less than 1 millisecond. First I 'warm up' Java with the first 10,000 solutions....

Then I run some big ones....

public static void main(String[] args) {
int cnt = 0;
long ms = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
cnt += sherlock(i).length();
}
ms = System.currentTimeMillis() - ms;
System.out.println("Warmup created " + cnt + " characters in " + ms + " Milliseconds");
for (int i : new int[] { 1, 3, 5, 11, 19, 100000 }) {
long nanos = System.nanoTime();
String val = sherlock(i);
nanos = System.nanoTime() - nanos;
System.out.printf("    request digits %d : actual digits %d Value %s in (%.3fms)%n",
i, val.length(), val.length() > 20 ? "too long" : val, nanos / 1000000.0);
}
}


This produces the output:

Warmup created 49995011 characters in 703 Milliseconds
request digits 1 : actual digits 5 Value 33333 in (0.004ms)
request digits 3 : actual digits 3 Value 555 in (0.012ms)
request digits 5 : actual digits 5 Value 33333 in (0.003ms)
request digits 11 : actual digits 11 Value 55555533333 in (0.002ms)
request digits 19 : actual digits 19 Value 5555555553333333333 in (0.002ms)
request digits 100000 : actual digits 100000 Value too long in (0.622ms)

-
There is an easier solution that does not involve loops. But it seems you may already know this... codereview.stackexchange.com/questions/67837/… – Francisco Aguilera Apr 20 at 0:44

Your approach seems all wrong, throw all that code away <- that's the code review.

You have to think about combinations, this is not like finding prime numbers.

n:1 -> Because you can only build numbers with 33333 and 555 you cannot find anything

n:2 -> same as 1

n:3 -> Can only be '555', again because your building blocks for the number are 555 and 33333

n:4 -> Impossible, you cant use 33333 ( too long ) and if you used 555 then you have 1 digit left which is useless

n:5 -> Can only be 33333, that's the only thing that fits

etc. etc.

You have to fit in blocks of 5 and 3 digit strings to get to n'.

The last tip as per the question, for n=8 you could have

55533333 or 33333555, obviously you need to try to put 555 in front because 5 > 3.

Hope this helps.

Edit: The code of @rolfl should do the trick otherwise you can perhaps find inspiration in the JS version ( http://jsbin.com/dalor/2/edit ):

function repeatString( s , n )
{
return n ? new Array( n + 1 ).join( s ) : "";
}

function getDecentNumber( n )
{
var threes = 0,
fives  = 0,
remainingDigits = +n;
while (remainingDigits > 2) {
if (remainingDigits % 3 === 0) {
fives = remainingDigits;
break;
}
remainingDigits -= 5;
}
threes = n - fives;
if (remainingDigits < 0 || threes % 5)
return "-1";

return repeatString( '5', fives ) + repeatString( '3', threes );
}

console.log( getDecentNumber( 1 ) );
console.log( getDecentNumber( 3 ) );
console.log( getDecentNumber( 5 ) );
console.log( getDecentNumber( 8 ) );
console.log( getDecentNumber( 11 ) );

-
I didn't understand. – Mohammad Areeb Siddiqui Mar 7 '14 at 15:51
This fails in some cases if you pass in a string to getDecentNumber(). Try it with '3' rather than 3. Obviously the fix is to use n = parseInt(n) before the first var in getDecentNumber. The reason I mention this is using the code as-is in the hackerrank javascript boilerplate may lead to the issue. – Greg Mar 7 '14 at 17:11
Agreed, solved, but more subtly ;) – konijn Mar 7 '14 at 17:24