Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lecture "Brute-force algorithms", exercise 4 #18

Open
essepuntato opened this issue Nov 26, 2018 · 16 comments
Open

Lecture "Brute-force algorithms", exercise 4 #18

essepuntato opened this issue Nov 26, 2018 · 16 comments
Labels
Exercise The exercises that are introduced in the lectures.

Comments

@essepuntato
Copy link
Contributor

essepuntato commented Nov 26, 2018

Write in Python the function def my_range(stop_number) which behave like the built-in function range() introduced in Section "Insertion sort" and returns a proper list, and accompany the function with the related test case. It is not possible to use the built-in function range() in the implementation.

@essepuntato essepuntato added the Exercise The exercises that are introduced in the lectures. label Nov 26, 2018
@delfimpandiani
Copy link

Ok, so this one I found both easier (because in terms of operations, finding the range was clearer than the enumeration) and harder than the previous exercise.

As I understood, the instruction was to define in Python a function called my_range(input_list) which should behave like the built-in function range(). In the lecture notes Section "Insertion sort", it says that inputting range(4) returns the range([0, 1, 2, 3]), which is a kind of list. However, when I tried it in Python, instead of range([0, 1, 2, 3], it returned range(0, 4) -- meaning, it did not return a "list" per se.

Therefore, I decided to opt for a solution that got me closer to the "list" result as defined in the lecture notes, in the form of range([0, 1, 2, 3]). My solution returns the list, but it does not return it as a function with the word 'range'.

def my_range(input_list):
    result = (list()) # new empty list where to store the resulting list
    len_input_list = len(input_list) #the list length is the same as the range I am trying to find
    for i in range(len_input_list):  # for each number in the range (between 0 and the list length)
        new_item = i #create a new item of the result list, which will be a number
        result.append(new_item) # apend the item to the new list
    return result
    

# accompany the function with the related test case

# Test case for the algorithm
def test_my_range(input_list, expected):
    result = my_range(input_list)
    if expected == result:
        return True
    else:
        return False

# Three different test runs
print(test_my_range([15, 38, 56, 4], [0, 1, 2, 3]))
print(test_my_range(["A", "B"], [0, 1]))
print(test_my_range(["A", 78, "Hola"], [0, 1, 2]))

# True
# True
# True

I'll keep an eye out for you guys' answers, to see how to include range() in the result of the user-defined function. Otherwise, Prof. @essepuntato, could you please clarify if it is necessary, and if so, how to do it? Thank you 👍

@hizclick
Copy link

hizclick commented Nov 27, 2018

The range() function has two sets of parameters.
start: Starting number of the sequence.
stop: Generate numbers up to, but not including this number. For example, range(0, 4) generates integers from 0 up to, but not including, 4.

so the function my_range has 3 inputs one for starting number, the second one for ending number and the last one to accept an input list.
range(3, 6)= 3,4,5
range(0,9) = 0,1,2,3,4,5,6,7,8
in a list=[1,2,3,4,5,6,7] range(1,5), will out put [2,3,4,5]
for the list ["ab","cd","eg","hi","jk"] and range(1,4) the out put will be ["cd","eg","hi"]

here is my code I think it will work for all inputs

def get_range(end,items="",start=0): #initializing the start position to 0
	my_list=[]
	if len(items)!= 0: #check if a list is passed to get_range() function
		for position, item in enumerate(items):
			if(start<=position<end):
				my_list.append(item)
		return my_list
	else:
		end = end -1
		while start<=end:
			my_list.append(end)
			end -=1
		my_list.reverse()
		return my_list

def test_get_range(expected,end,items="",start=0):
	result = get_range(end,items,start)
	if result == expected:
		return True
	else:
		return False
		 
print(test_get_range([2,3],3,[1,2,3,4],1)) 
#expected result, ending number, items in the list, starting position
print(test_get_range([1,2,3],4,"",1))
print(test_get_range([3,4,5],6,"",3))
print(test_get_range([2,3],3,[1,2,3,4,5],1))
print(test_get_range([2,3,4,5],5,[1,2,3,4,5,6,7],1))
print(test_get_range(["cd","eg","hi"],4,["ab","cd","eg","hi","jk"],1))
print(test_get_range(["cd","eg","hi","jk"],4,["ab","cd","eg","hi","jk"],1))

#true
#true
#true
#true
#true
#true
#false





@essepuntato
Copy link
Contributor Author

essepuntato commented Nov 27, 2018

Hi @delfimpandiani

It is not possible to use the built-in function range() in the body of your my_range function. However there is a clear mistake in the definition of the exercise (my fault), since range takes in input a number –– apologises!

@hizclick
Copy link

hizclick commented Nov 27, 2018

def test_my_range(n,expected):
	if my_range(n) == expected:
		return True
	else:
		return False
def my_range(n):
	n= n- 1
	my_list=[]
	while n>=0:
		my_list.append(n)
		n -= 1
	my_list.reverse()
	return(my_list)
print(test_my_range(4,[0,1,2,3]))
print(test_my_range(3,[0,1,2]))
print(test_my_range(5,[0,1,2,3,4]))
print(test_my_range(6,[0,1,2,3]))

#True 
#True 
#True  
#False

@federicabologna
Copy link

My method is basically identical to the one implemented by @Hizkie . In fact, the only difference is that I subtract "1" inside the while loop, instead of before the while statement.
Still, I had problems in printing the function, since Python would return "<list_reverseiterator object at 0x000001AAB7D662B0>".

def my_range(n):
    result = []
    while n > 0:
        n -= 1
        result.append(n)
    return reversed(result)

print(my_range(4))

<list_reverseiterator object at 0x000001AAB7D662B0>

Then, I looked up my colleagues' answers and found that they expressed the inversion as "result.reverse()" and not as "reversed() - the second option was the one presented in class. After using that expression, Python finally returned the expected results.

def test_my_range(n, expected):
    result = my_range(n)
    if result == expected:
        return True
    else:
        return False

def my_range(n):
    result = []
    while n > 0:
        n -= 1
        result.append(n)
    result.reverse()
    return(result)

print(test_my_range(4, [0, 1, 2, 3]))
print(test_my_range(3, [3, 2, 1]))

True
False

@essepuntato Professor, my questions are now:
1 - what does the code returned by Python mean?
2 - what is the difference between the two expressions?

@delfimpandiani
Copy link

Given Prof. Peroni's edit of the prompt, I looked at Hizkiel's solution and decided to find a similar solution but without having to reverse the list. I used his same test examples and it works just as well:

def test_my_range(n,expected):
    if my_range(n) == expected:
        return True
    else:
        return False
def my_range(stop):
    n= 0
    my_list=[]
    while n<=(stop -1):
        my_list.append(n)
        n += 1
    return(my_list)
print(test_my_range(4,[0,1,2,3]))
print(test_my_range(3,[0,1,2]))
print(test_my_range(5,[0,1,2,3,4]))
print(test_my_range(6,[0,1,2,3]))

#True 
#True 
#True  
#False

1 similar comment
@delfimpandiani
Copy link

Given Prof. Peroni's edit of the prompt, I looked at Hizkiel's solution and decided to find a similar solution but without having to reverse the list. I used his same test examples and it works just as well:

def test_my_range(n,expected):
    if my_range(n) == expected:
        return True
    else:
        return False
def my_range(stop):
    n= 0
    my_list=[]
    while n<=(stop -1):
        my_list.append(n)
        n += 1
    return(my_list)
print(test_my_range(4,[0,1,2,3]))
print(test_my_range(3,[0,1,2]))
print(test_my_range(5,[0,1,2,3,4]))
print(test_my_range(6,[0,1,2,3]))

#True 
#True 
#True  
#False

@MattiaSpadoni
Copy link

I tried like this, sorry, but screenshots are the easiest way to share it (yes I have 1158 unread e-mails).

image

@EleonoraPeruch
Copy link

EleonoraPeruch commented Nov 27, 2018

# Test case for the algorithm
def test_my_range(stop_number, expected):
    result = my_range(stop_number)
    if expected == result:
        return True
    else:
        return False

# Code of the algorithm
def my_range(stop_number):
    stop_number >= 0    # my_range takes a non negative number as input
    # return a list of values from 0 
    # to the one preceding stop_number
    output_my_range = list() # the list to return
    input_number = 0         # the list starts from 0 
    while input_number < stop_number: 
            output_my_range.append(input_number)
            input_number += 1
    return output_my_range

# Run some tests
print(test_my_range((4), ([0, 1, 2, 3])))
print(test_my_range((4), ([0, 1, 2, 3, 4])))
print(test_my_range((4), ([0, 1, 2])))

True
False
False

@SeverinJB
Copy link

# Testing Algorithm
def test_my_range(input_value, expected): 
    result = my_range(input_value) 
    if expected == result: 
        return True 
    else: 
        return False

# Algorithm
def my_range(input_value): 
    range_object = []
    while input_value > 0: 
        input_value = input_value - 1
        range_object.append(input_value)
    range_object.reverse()
    return range_object

# Testing Input
print(test_my_range(3, [0,1,2]))
print(test_my_range(4, [0,1,2,3]))
print(test_my_range(0, []))

@friendlynihilist
Copy link

@essepuntato: Professor, while reaching the same conclusions (more or less), I've also experienced the exact same problem mentioned by my colleague @federicafaithbologna. Could reversed(<input_list>) be used in this code instead of result.reverse(). Thank you!

def test_my_range(stop_number, expected):
    result = my_range(stop_number)
    if expected == result:
        return True
    else:
        return False

def my_range(stop_number):
    result = []

    while stop_number > 0:
            stop_number = stop_number - 1
            result.append(stop_number)
    result.reverse() #question about this
    return result


print(test_my_range(6, [0, 1, 2, 3, 4, 5])) #true
print(test_my_range(7, [0, 1, 2, 3, 4, 5, 6, 7])) #false
print(test_my_range(5, [0, 1, 2, 3])) #false
print(test_my_range(4, [0, 1, 2, 3])) #true

@ilsamoano
Copy link


#test
def test_myrange(n,expected):
    result= myrange(n)
    
    if result == expected:
        return True
    else:
        return False
        
#code
def myrange(n):
    newlist = []
   
    while n >0:
        n = n - 1
        newlist.append(n)
    newlist.reverse()
    return newlist

#test evaluation
print (test_myrange(4,[0,1,2,3,]))

@mangiafrangette
Copy link

def test_my_range(stop_number, expected):
    return my_range(stop_number) == expected

def my_range(stop_number):

    stop_number = stop_number - 1
    range_list = []
    while stop_number >= 0:
        range_list.append(stop_number)
        stop_number = stop_number -1

    return list(reversed(range_list))

stop_number = 9
expected = list(range(stop_number))
print(test_my_range(stop_number, expected))

@tceron
Copy link

tceron commented Nov 29, 2018

Thanks to the help of @delfimpandiani I was finally able to run it. :D
range

@andreamust
Copy link

def test_my_range(stop_number, expected):
    result = my_range(stop_number)
    if result == expected:
        return True
    else:
        return False



def my_range(stop_number):
    result = list()
    start_number = 0
    stop_number >= 0

    while start_number < stop_number:
        result.append(start_number)
        start_number += 1

    return result


print(test_my_range((3), ([0, 1, 2])))   #True
print(test_my_range((4), ([0, 1, 2, 3, 4])))    #False
print(test_my_range((-4), ([-3, -2, -1, 0])))     #False

@essepuntato
Copy link
Contributor Author

essepuntato commented Dec 1, 2018

Hi all,

here my take on the exercise (available also as Python file in the GitHub repository), with some comments:

# Test case for the algorithm
def test_my_range(stop_number, expected):
    result = my_range(stop_number)
    if expected == result:
        return True
    else:
        return False


# Code of the algorithm
def my_range(stop_number):
    l = list()
    while stop_number > 0:
        stop_number = stop_number - 1
        l.insert(0, stop_number)
    return l


print(test_my_range(0, []))
print(test_my_range(4, [0, 1, 2, 3]))

Some comments:

  1. @federicafaithbologna about your question on the difference between reversed(<ordered collection>) and <list>.reverse().

    The first is a simple built-in function that Python has. That function returns a new object, i.e. an iterator (which is a kind of list, but it is not really alist) of a collection of ordered elements such as a list, and allows you to browse such list from the last element to the first one. Since this function is generically developed to handle any kind of ordered collection, it can be also used with tuples, for instance, and it always create a new object leaving the original one as before.

    The second is actually a method that can be called on any object of class list. As anticipated in one of the previous lectures, a method is a special kind of function that can be used only with objects of a specific class. In fact, you can use such <list>.reverse() on a list you have, but for instance it cannot be used with an object of class tuple, since the class tuple does not implement the reverse() method. In addition, this method does not generate a new object but actually changes the list itself, by positioning the items in reverse order. For instance, try to run the following code in Python Tutor to see graphically the differences:

    l = ["a", "b", "c"]  # create a new list
    it = reversed(l)  # create a new object iterator which allow on to browse the list in reverse order
    print(l)  # print the list, which contains the items in the same order as before
    print(it)  # print the object iterator, which is not the original list
    l.reverse()  # it reorders the items in the list in reverse order
    print(l)  # print the list, that changed as a consequece of the previous method
    

    I hope it is clearer now. Anyway, when you have similar doubts, I would sugget to start from the official Python documentation (linked in the lecture notes on Programming Languages for your convenience) to see if it clarifies your issues. For instance, see the definition provided for reversed and reverse there.

  2. test-driven development: all the tests must be passed in order to claim that an algorithm returns what it is expected. If a test execution return False, the test is not passed. If you need to check the non-compliancy of the execution of a function on purpose, then you have to create an additional testing function that returns True if the condition of the test is not passed. Remeber: first write the test, then develop the algorithm/function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Exercise The exercises that are introduced in the lectures.
Projects
None yet
Development

No branches or pull requests