I was trying to work this through recursion, I'm not exactly sure if I got it right. but I think I'm on the right track, since it seems that the greatest sum usually consists of a 3 and/or 2's.
def great_mult(num):
lists = []
if num <= 3:
lists.append(num)
return lists
if num % 3 == 0:
num = (num - 3)
lists.append(3)
lists.extend(great_mult(num))
else:
num = (num - 2)
lists.append(2)
lists.extend(great_mult(num))
return lists
It's nice to finally have some time to try the problems shown in class.
Friday, 5 April 2013
Free Lunch
Understanding the Problems:
Free lunch consists of a group of friends trying to determine who gets free lunch. The way they decide is that they arrange themselves in a circle and start counting the positive natural numbers in order. The person at the most north of the circle starts counting from 1. Anyone who says an even natural number gets removed from the circle. When we reach the last person this wraps around and goes back to the person at the beginning. This continues until there is exactly one person left, and this person gets free lunch in the end.
Devise a Plan:
I'm going to perform a few basic examples to help clear out exactly what happens
Carry out the Plan:
So a few examples to help clear out what happens in different situations, I left the index underneath and used a list because I was preparing it so that I could code it easily later on. The case below, is just a simple example without any complications.
[1, 2, 3, 4]
(0, 1, 2, 3) - Index
[1, 3]
(0, 1) - Index
[1] - Last One = 1
Here there is no complication in reaching the person who gets free lunch since the number of people stays even until you reach the last person. You just continuously remove the person who is at an odd index in python terms.
[1, 2, 3, 4, 5]
(0, 1, 2, 3, 4,) - Index
[5, 1, 3]
(0, 1, 2) - Indes
[3, 5]
(0, 1) - Index
[3]- Last One = 3
Here is were it gets a bit more tricky, since the last item is on an even index, (the number of people is odd) and is right after someone who gets removed. For the python code to work that person becomes the technical new "first person" and we start counting from them. That is why the 5 moves to the front and then the 3 gets moved to the front, since the lists are odd.
def remove_odd_index(L):
''' Remove the odd indeces, which corrolate to the "person"
counting the even natural numbers.
# Once the list has a length of 1 return that item, which means once theres only one person left,
# you have the winner.
if len(L) == 1:
return L[0]
# Go through all the odd indices and remove them.
work = L[:]
for i in range(1, len(L), 2):
work.remove(L[i])
# If there is now an odd number of people then the last person because the first
# in the new "set" of people
if len(L) % 2 != 0:
work.insert(0, L[-1])
work = work[:-1]
# Continue calling the function until there is one person left
return remove_eve_ind(work)
Look Back:
I tried doing it with circles and it made it harder to actually see the pattern when dealing with certain numbers of people, such as the pattern of how to deal with even number of people and the pattern that there is when dealing with an odd number of people. It took me a little while to figure out how to insert the last item at the front of the list, and had a lapse in brain power trying to remember that I could just slice the list to remove the last item, but that was just some rustiness in coding. The general concept of the problems I understand when I kept it as a line because it was easier to see that I could just move the last person in an odd numbered list to the front and continued from there.
I also want to thank Mandy from http://mandyxu.blog.com for showing me this problem, it was actually pretty fun to figure it out the code for this.
Free lunch consists of a group of friends trying to determine who gets free lunch. The way they decide is that they arrange themselves in a circle and start counting the positive natural numbers in order. The person at the most north of the circle starts counting from 1. Anyone who says an even natural number gets removed from the circle. When we reach the last person this wraps around and goes back to the person at the beginning. This continues until there is exactly one person left, and this person gets free lunch in the end.
Devise a Plan:
I'm going to perform a few basic examples to help clear out exactly what happens
Carry out the Plan:
So a few examples to help clear out what happens in different situations, I left the index underneath and used a list because I was preparing it so that I could code it easily later on. The case below, is just a simple example without any complications.
[1, 2, 3, 4]
(0, 1, 2, 3) - Index
[1, 3]
(0, 1) - Index
[1] - Last One = 1
Here there is no complication in reaching the person who gets free lunch since the number of people stays even until you reach the last person. You just continuously remove the person who is at an odd index in python terms.
(0, 1, 2, 3, 4,) - Index
[5, 1, 3]
(0, 1, 2) - Indes
[3, 5]
(0, 1) - Index
[3]- Last One = 3
Here is were it gets a bit more tricky, since the last item is on an even index, (the number of people is odd) and is right after someone who gets removed. For the python code to work that person becomes the technical new "first person" and we start counting from them. That is why the 5 moves to the front and then the 3 gets moved to the front, since the lists are odd.
def remove_odd_index(L):
''' Remove the odd indeces, which corrolate to the "person"
counting the even natural numbers.
# Once the list has a length of 1 return that item, which means once theres only one person left,
# you have the winner.
if len(L) == 1:
return L[0]
# Go through all the odd indices and remove them.
work = L[:]
for i in range(1, len(L), 2):
work.remove(L[i])
# If there is now an odd number of people then the last person because the first
# in the new "set" of people
if len(L) % 2 != 0:
work.insert(0, L[-1])
work = work[:-1]
# Continue calling the function until there is one person left
return remove_eve_ind(work)
Look Back:
I tried doing it with circles and it made it harder to actually see the pattern when dealing with certain numbers of people, such as the pattern of how to deal with even number of people and the pattern that there is when dealing with an odd number of people. It took me a little while to figure out how to insert the last item at the front of the list, and had a lapse in brain power trying to remember that I could just slice the list to remove the last item, but that was just some rustiness in coding. The general concept of the problems I understand when I kept it as a line because it was easier to see that I could just move the last person in an odd numbered list to the front and continued from there.
I also want to thank Mandy from http://mandyxu.blog.com for showing me this problem, it was actually pretty fun to figure it out the code for this.
Monday, 1 April 2013
Computable Halt! ...... never mind
I found this concept so strange, the way we prove a function is not computable is by assuming it is computable and showing that it is a halting function and since a halting function is not computable then we can safely assume that our original function is not computable.
I find a lot of these concepts strange but I understand why the proof structure works. If something can't exist then you can't really say it does within your function.
After the assignment I was doing one of the tutorial problems, which was pretty similar to the assignment and it helped clear up some of the stuff that I was unsure of.
Here's how I did it.
Reduce halt to allstop.
all stop(P) = { True if P(x) halts for every input x,
{ False, otherwise'
def half(P, x):
def all stop(P):
#Check if P(x) halts
# for every input X
# Assume computable
def not_f(x)
P(x)
return "You shall halt"
return all stop(not_f, x)
The way I explained it to complete the proof was that if P(x) halted, that meant not_f(x) halts, which causes allstop(P) to return True. In the end this means that halt returns True as well. If P(x) doesn't halt, then not_f(x) doesn't halt which means allstop(P) would return False, which would cause the halting function to return False. So when P(x) halts, allstop returns True and halt(P, x) returns True and when P(X) doesn't halt, then allstop returns False and halt(P, x) returns False. So This means I have technically written a working halting function, which doesn't exist to my knowledge. So then we can safely assume that allstop is not computable since it is a halting function.
I hope that explanation makes sense, took a bit of explanation from my assignment partner for it to make sense of it when we were working on the assignment.
I find a lot of these concepts strange but I understand why the proof structure works. If something can't exist then you can't really say it does within your function.
After the assignment I was doing one of the tutorial problems, which was pretty similar to the assignment and it helped clear up some of the stuff that I was unsure of.
Here's how I did it.
Reduce halt to allstop.
all stop(P) = { True if P(x) halts for every input x,
{ False, otherwise'
def half(P, x):
def all stop(P):
#Check if P(x) halts
# for every input X
# Assume computable
def not_f(x)
P(x)
return "You shall halt"
return all stop(not_f, x)
The way I explained it to complete the proof was that if P(x) halted, that meant not_f(x) halts, which causes allstop(P) to return True. In the end this means that halt returns True as well. If P(x) doesn't halt, then not_f(x) doesn't halt which means allstop(P) would return False, which would cause the halting function to return False. So when P(x) halts, allstop returns True and halt(P, x) returns True and when P(X) doesn't halt, then allstop returns False and halt(P, x) returns False. So This means I have technically written a working halting function, which doesn't exist to my knowledge. So then we can safely assume that allstop is not computable since it is a halting function.
I hope that explanation makes sense, took a bit of explanation from my assignment partner for it to make sense of it when we were working on the assignment.
Subscribe to:
Posts (Atom)