ArjunKumar12
Posts: 7
Joined: Fri Mar 22, 2019 6:11 am

Recursive Triangle Python Project

Tue Jul 27, 2021 7:32 am

Hello Everyone, Can anyone tell me below code is correct or not? I am working on a recursive triangle python project and looking to source code. I have found the below code on interviewbit and want to know your expert advice, Is it optimize code? and also I have checked this same code on Github.

Code: Select all

def triangle(n):
    return recursive_triangle(n, n)

def recursive_triangle(x, n):
    # First we must verify that both input values are integers.
    if type(x) != int or type(n) != int:
        return 'error'
    # If x is bigger than n, we will still only print the full triangle, so we can set them equal.
    if x > n:
        x = n
    # If either value is zero, the output should be an empty string because there are no lines or triangle to print.
    if x == 0 or n == 0:
        return ''
    # Let's set some variable names to help us out.
    star_print = n
    line_number = x
    # I'll create an empty string that we can concatenate values to.
    line_print = ''

# The difference value will determine how many shapes are needed to fill the line before the stars are printed.
    difference = star_print - line_number
    # If difference is not zero, we will print that value of spaces before the stars. The star print will be the
    # remainder, also known as line number.
    if difference != 0:
        line_print += ' '*difference
        line_print += '*'*line_number
    # If difference is zero, then we can just fill the line with stars.
    else:
        line_print += '*'*star_print
    # If the line number is greater than one, we can return our string and use the recursive call to run the function
    # again with the line number as one value less.
    if line_number > 1:
        return line_print+'\n'+str(recursive_triangle(line_number-1, star_print))
    # If the line number is exactly one, then we don't need to use the recursive call.
    elif line_number == 1:
        return line_print

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 7:50 am

ArjunKumar12 wrote:
Tue Jul 27, 2021 7:32 am
Is it optimize code?
Optimised for what...

Speed,
Code size,
Ease of writing,
Getting job offers from interviews,
Other?

If it's speed or code size I would note that Python is a very slow and requires a run time system, I'd optimise it by rewriting it in an efficient language like C, C++, Pascal, Rust, Ada.
Memory in C++ is a leaky abstraction .

ArjunKumar12
Posts: 7
Joined: Fri Mar 22, 2019 6:11 am

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 1:15 pm

Optimize for code size?

User avatar
B.Goode
Posts: 12768
Joined: Mon Sep 01, 2014 4:03 pm
Location: UK

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 2:01 pm

ArjunKumar12 wrote:
Tue Jul 27, 2021 1:15 pm
Optimize for code size?


As a very crude first response, I'd suggest that if you are concerned about 'code size' - whatever that means - you wouldn't be writing in Python...

(As already stated before you gave that reply.)

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 3:19 pm

ArjunKumar12 wrote:
Tue Jul 27, 2021 1:15 pm
Optimize for code size?
That statement is a question.

The same question I was asking you.

What do you actually want to achieve?

But while we are here. If you really want the smallest possible code to create that triangle with a recursive algorithm then you are going to code it in a compiled language like C, C++, Pascal, Ada, Rust...

All those languages get com[piled down to about the minimal amount of actual machine instructions required to do the job. Unlike language like BASIC, Python, Javascript, Java etc, that require an extensive run time support system to be hauled around to run them.
Memory in C++ is a leaky abstraction .

ghp
Posts: 2023
Joined: Wed Jun 12, 2013 12:41 pm
Location: Stuttgart Germany
Contact: Website

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 6:12 pm

Code efficiency:
"Finally, the golden rule of optimization: don't optimize unless you know you need to, and measure rather than guessing.
You can measure different methods using the timeit module. That can tell you which is fastest, instead of random strangers on the internet making guesses."
from https://stackoverflow.com/questions/131 ... -in-python

User avatar
jahboater
Posts: 7314
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Recursive Triangle Python Project

Tue Jul 27, 2021 6:25 pm

ArjunKumar12 wrote:
Tue Jul 27, 2021 1:15 pm
Optimize for code size?
That's a bit of an oddity with an interpreted language llike Python
Your code is 1569 bytes which is very small, considerably smaller than a compiled language executable.
But the Python interpreter needed to run it is huge:

Code: Select all

$ ls -l python3.9
-rwxr-xr-x 1 root root 12577980 May 16 03:35 python3.9
A compiled language such as C would produce a program that's a few KB in size - which runs without an interpreter (obviously).
But even the C program would require one or two libraries!

:)

PS, the C/C++/Rust/Fortran/Etc equivalent would run orders of magnitude faster, because the translation and optimization are done once - before the program is run.
Whereas the Python program has to be translated every single time you run it. And since any optimization is done each time the program runs, it is minimal.
A compiled language can spend as long as it likes optimizing the program because its done separately beforehand.

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 5:50 am

jahboater wrote:
Tue Jul 27, 2021 6:25 pm
Your code is 1569 bytes which is very small, considerably smaller than a compiled language executable.
I reckon that algorithm written in C could be coaxed into producing less than 1569 bytes of executable code. (Hint, avoid things like printf and the the standard library. We are optimising, right?)

Hmm...There is a challenge for any keen C, C++, Pascal, Ada, Rust programmers :)
Memory in C++ is a leaky abstraction .

gordon77
Posts: 5915
Joined: Sun Aug 05, 2012 3:12 pm

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 6:54 am

When the OP says " I am working on a recursive triangle python project ..." surely they want to use python ?

User avatar
jahboater
Posts: 7314
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 7:44 am

Heater wrote:
Wed Jul 28, 2021 5:50 am
jahboater wrote:
Tue Jul 27, 2021 6:25 pm
Your code is 1569 bytes which is very small, considerably smaller than a compiled language executable.
I reckon that algorithm written in C could be coaxed into producing less than 1569 bytes of executable code. (Hint, avoid things like printf and the the standard library. We are optimising, right?)

Hmm...There is a challenge for any keen C, C++, Pascal, Ada, Rust programmers :)
The aarch64 executable for this "hello world" program without printf takes 6120 bytes .....

Code: Select all

#include <unistd.h>

int
main( void )
{
  write(1, "Hello world\n", 12);
}
gcc -Os -s hello.c -o hello
This cheating version for x86_64 doesn't use the C library, takes 4104 bytes ...

Code: Select all

int
main( void )
{
  asm("syscall" :: "a" (1), "D" (1), "S" ("Hello world\n"), "d" (12) );
}
Removing the unneeded ELF sections leaves 2128 bytes ...

Code: Select all

$ ls -l hello 
-rwxr-xr-x 1 jah jah 2128 Jul 28 08:52 hello
Python wins, perhaps Rust can get closer to 1569 bytes.

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 10:23 am

gordon77 wrote:
Wed Jul 28, 2021 6:54 am
When the OP says " I am working on a recursive triangle python project ..." surely they want to use python ?
I have no doubt that is true.

However when I see someone tenaciously banging in screws with a hammer I can't help myself pointing out that there is a better tool for the job.

Anyway the OP's question lies in "...want to know your expert advice, Is it optimize code?". Well, I stated how I would do it.
Memory in C++ is a leaky abstraction .

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 10:29 am

jahboater wrote:
Wed Jul 28, 2021 7:44 am
The aarch64 executable for this "hello world" program without printf takes 6120 bytes .....
On this Mac M1 it's even a lot bigger than that.

However if I were to build that program for a micro-controller, statically linked against a minimal C library it would only be a handful of bytes.
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 7314
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 10:33 am

Heater wrote:
Wed Jul 28, 2021 10:29 am
jahboater wrote:
Wed Jul 28, 2021 7:44 am
The aarch64 executable for this "hello world" program without printf takes 6120 bytes .....
On this Mac M1 it's even a lot bigger than that.

However if I were to build that program for a micro-controller, statically linked against a minimal C library it would only be a handful of bytes.
With this perhaps:

Code: Select all

-ffreestanding
   Assert that compilation targets a freestanding environment.  This implies
   -fno-builtin.  A freestanding environment is one in which the standard library may not
   exist, and program startup may not necessarily be at "main".  

Heater
Posts: 18513
Joined: Tue Jul 17, 2012 3:02 pm

Re: Recursive Triangle Python Project

Wed Jul 28, 2021 11:02 am

Yeah. Something like that.
Memory in C++ is a leaky abstraction .

Return to “Python”