welcome to
evildojo


HackerRank

Triangle Quest 2

Located here: https://www.hackerrank.com/challenges/triangle-quest-2?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign


tl;dr

Given N>0 and N<10, print a palindromic triangle of size N

example

N = 5

1
121
12321
1234321
123454321

The big caveat here is that we have to do this using 1 line in a for loop, and can't use anything related to strings.

The first line, the for loop, is given to us:

for i in range(1,int(raw_input())+1): #More than 2 lines will result in 0 score. Do not leave a blank line also

Lets remove that comment:

for i in range(1,int(raw_input())+1):

That's nicer :)


My first solution was:

for i in range(1,int(raw_input())+1):
    print "".join(str(x) for x in range(1, i+1)) + "".join(str(x) for x in reversed(range(1, i)))

Which was then shortened to:

for i in range(1,int(raw_input())+1):
    print "".join(str(x) for x in (range(1, i+1) + list(reversed(range(1, i)))))

But neither of these will get us past the first test case...

Googling around for ideas, I came across this:

This yielded my new solution:

from __future__ import print_function
for i in range(1,int(raw_input())+1):
    print(*(x for x in (range(1, i+1) + list(reversed(range(1, i))))), sep='')

But this won't work because of the import statement...


After a while, I got stuck, and decided to look up the solutions on the HackerRank forums...

Some of the answers at the top of the page are very interesting...

print((111111111//(10**(9-i)))**2)

print(sum(map(lambda n: 10**n, range(i)))**2)

print((eval('1'*j)**2))

x=int("1"*i) print(x*x)

I want to give these a try and then break down why they do or do not work...


Solution 1

This solution is very peculiar...

print((111111111//(10**(9-i)))**2)

Lets break this down...

First questions I have are:

  1. What is the significance of 111111111?
  2. What does a // do?
  3. What does a ** do?

1 Will probably be harder to answer without 2 and 3, so lets answer those first:

//: Floor division
**: pow(x,y) or x^y

Ok so lets understand what this numerical expression is...

111111111 divided by 
10 to the power of (9 minus i)
all to the power of 2

Why does this work?

We have to start with i = 1 in order to answer this.

Ultimately, this is just a cool number trick, but it is worth evaluating.

At i = 1, the denominator of our fraction becomes 10^8, which is 100000000.

111111111 // 100000000 = 1 in Python (naturally).

1 ** 2 = 1 naturally.

So, our first printed statement is 1.

At i = 2, the denominator of our fraction becomes 10^7, which is 10000000.

111111111 // 10000000 = 11.

11 ** 2 = 121.

At this point I realized the "trick".

All we are doing is squaring sequences of the digit 1 repeating i times.

To show this is the trick to this solution, try 11111 ** 2 or 11111 * 11111.

You should get 123454321.

Naturally, such pedantic math knowledge does not have much common application beyond recognizing certain sequences or inputs and generalized pattern matching abilities.


Non-solutions

print((eval('1'*j)**2))

x=int("1"*i) print(x*x)

These two solutions contain strings, so we can skip them


Solution 2

This is also an interesting solution...

print(sum(map(lambda n: 10**n, range(i)))**2)

To break down what is going on here, I used the following statements:

print map(lambda n: 10**n, range(1))
print map(lambda n: 10**n, range(2))
print map(lambda n: 10**n, range(3))

Which yielded:

[1]
[1, 10]
[1, 10, 100]
[1, 10, 100, 1000]
[1, 10, 100, 1000, 10000]

Hence why the summation yields the same sequence of ones we got in the first solution.

Further why we square the sums to yield the desired sequences.

Since I know that range(i) yields a list, I now understand that map takes a lambda equation for the first arg here, and a list for the second.

This is just a modified version of the number trick from the first solution.


In all, it seems that solving this problem required a bit of special insight or math/number-agility in order to see that pattern.

I was originally looking for a way to join a list of individual digits but ended up finding that others solved this problem by generating the numbers themselves.

lol, nice.