3 Replies - 1982 Views - Last Post: 28 March 2010 - 06:18 AM Rate Topic: -----

#1 mapexx  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 23
  • Joined: 30-November 09

PYTHON - determining the longest chain in a sequence

Posted 24 March 2010 - 04:20 PM

I want my program to prompt the user for a range of values(such as 1-15), perform a sequence of operations on each value until it equals one, and then count the length of each chain. I then need to know which chain had the longest length. For example, I have these functions that performs the operations:

# determines if a number is even or odd
def determineOdd(num):
    if num % 2 == 0:
        return False
    else:
        return True

# performs operations depending if the number is even or odd
def tempHS(num):
    values = []
    print num, "->",
    while num != 1:
        values.append(num)
        if determineOdd(num):
            num = 3 * num + 1
        else:
            num /= 2
        if num != 1:
            print num,"->",
        else:
            print num,

    length = len(values)
    print "; length = ",length




After I prompt the user for a range of values, I then want my function to return the lengths of each chain.

I am not sure how to have it return which value had the longest chain(longest length). Any ideas?


Output would look something like this for values 13-15:

 
13  -> 40  -> 20  -> 10  -> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 10

14  -> 7  -> 22  -> 11  -> 34  -> 17  -> 52  -> 26  -> 13  -> 40  -> 20  -> 10
-> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 18

15  -> 46  -> 23  -> 70  -> 35  -> 106  -> 53  -> 160  -> 80  -> 40  -> 20  -> 1
0  -> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 18

etc..

Thank you

This post has been edited by mapexx: 24 March 2010 - 04:22 PM


Is This A Good Question/Topic? 0
  • +

Replies To: PYTHON - determining the longest chain in a sequence

#2 chemicalfan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 88
  • Joined: 16-October 09

Re: PYTHON - determining the longest chain in a sequence

Posted 25 March 2010 - 07:12 AM

Off the top of my head, I'd store the chain lengths per user value as a dictionary (appending the user value as a key, and chain length as a value). Then at the end, query the dictionary to get the highest value (you might need to convert to a list for this, I'm not sure)
Was This Post Helpful? 0
  • +
  • -

#3 mapexx  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 23
  • Joined: 30-November 09

Re: PYTHON - determining the longest chain in a sequence

Posted 27 March 2010 - 03:33 PM

I haven't yet learned how to use dictionaries. Any other suggestions?
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5875
  • View blog
  • Posts: 12,757
  • Joined: 16-October 07

Re: PYTHON - determining the longest chain in a sequence

Posted 28 March 2010 - 06:18 AM

In order to find the longest, you first have to have to function that returns something useful. Just printing isn't going to help.

Your method can be simply written like this:
def tempHS(num):
	values = [num,]
	while num != 1:
		if num % 2 == 0:
			num /= 2
		else:
			num = 3 * num + 1
		values.append(num)
	return values



Printing can be done pretty simply:
def printResults(hsList):
	print "%s ; length = %d" % (' -> '.join([str(i) for i in hsList]), len(hsList))



Now you can tell which is longer:
(l1, l2) = (tempHS(13), tempHS(14))
if len(l1) < len(l2):
	printResults(l2)
else:
	printResults(l1)



I'll leave finding the longest in a list of choices to you.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1