seitora learns programming

[seitora]

As I mentioned in this post here, after a decade or so of half-hearted on-again off-again attempts at learning programming I'm finally making a more serious attempt.

I'll be using this topic to basically document my daily or weekly studies, any projects I've been working on, snippets of code, and of course using this to kick my ass not to slack off.

 

[seitora]

The first language I've been learning is Python. I've been doing the lessons offered on Codecademy which go through syntax, strings, conditionals, control flows and loops, functions, lists and dictionaries, light manipulation on lists and dictionaries, and a little bit of classes. I did most of the lessons on Tuesday through Thursday, then some more today (had other stuff Friday/Saturday).

So far, it's definitely very much been a practice-makes-perfect approach for me. I still struggle a little bit with some of the range functions where 0,10 might call 0-9 or 0-10 or 1-10 or 1-11, since this isn't held consistent across all the syntax. Of course, I'm still nowhere near comfortable with the rest of the material, but at least I'm not totally lost on my own now.

The main problem is Codecademy still relies on Python 2.7. Reading up, 2.7 isn't terrible or anything, and is still widely-used, but if I'm starting from scratch my preference will be to learn the up-to-date version 3 (3.5.2 being the latest stable version), so I expect to be learning a little bit of switcharoo with syntax and new support.

In any event, the current Humble Bundle e-books is a bunch of coding books, so I bought that. I am currently going through "Automate the Boring Stuff with Python" by Al Sweigart.

Originally, the above title was in all capitals. However, instead of fetching a properly capitalised form of the title, I decided to write a quick little code to do this for me and then I would capitalise A-B-P.

Fortunately, the error message was detailed enough that I realised the 'print' function requires parentheses around whatever is being printed now, unlike in Python 2.

text = "AUTOMATE THE BORING STUFF WITH PYTHON"

print(text.lower())

 

[seitora]

Progress Report: August 21

After going through most of Codecademy's optional modules (the rest are behind a paywall), I went through the first three chapters of  "Automate the Boring Stuff with Python".

Most of it was a refresher and, so far, it seems the only two syntax changes for me my level so far is the print function requiring parentheses, and certain integer divisions now returning floating point numbers instead of rounded integers (3 / 2 could return 1 in Python 2, but 1.5 in Python 3.5.2)

The new stuff for me was a little bit of talking about general computers that gave me a better understanding of the entire field altogether, something that I know I'll be needing to be better at in the future (understanding WHY everything works, if not at the absolute lowest logic level altogether, at least at the level of my code). That was especially crucial in reading the book's section on global and local scope variables and the difference between them. I can generally follow a line of programming now and, so long as it's not using any new built-in variables I'm unfamiliar with, tell what it's supposed to do. Actually writing that same code is something that'll take time and familiarity.

Also, I learned some of the stuff regarding optional parameters (such as 'end' and 'sep' for in print variables).

That said, I am also struggling with the 'try:' and 'except:' conditional blocks. In the spoiler section is a program I wrote to perform a Collatz function. The actual function works perfectly, stopping prior to the Collatz loop if 1, 0 or any negative integer is used.

Spoiler

def collatz(number):

    if number % 2 == 0:
        return number / 2

    else:
        return number * 3 + 1

numb = input("Select a whole number value above 1.")

#try:
    #int(numb)
#except ValueError:
    #print("Invalid. You must enter an integer.")

numb = int(numb)

if numb <= 1:
    print ("That's not going to help demonstrate this program.")

else:

    while numb != 1:

        print(collatz(numb))
        numb = collatz(numb)

The problem is I'm trying to build a try: error: block in here (and I have those four lines commented out at the moment). What it should be doing is executing and, in the event of somebody entering a floating-value, return 'Value Error: Invalid. You must enter an integer.' It'll generate a ValueError or TypeError, but with the built-in error message instead.


For reference, this is the code the book provides, which actually works:

def spam(divideBy):
    return 42 / divideBy
try:
    print(spam(2))
    print(spam(12))
    print(spam(0))
    print(spam(1))
except ZeroDivisionError:
    print('Error: Invalid argument.')

giving 'Error: Invalid argument.'



chronodekar?

In any case, I've finished up with trying to figure that out on my own, so I'll leave it for now and move on (or maybe post it onto reddit's learnpython subreddit).


Also yesterday, I went through the devlog for Papers, Please, since it struck me as a game that probably required a minimalist amount of work. One guy took just under 10 months to do that from scratch, and I got no idea of how many hours he actually put in during that time on a daily basis either. Pretty interesting read and seeing some of the techniques he used, even if some of the higher-level stuff doesn't quite make sense to me yet.

 

[chronodekar]

The first language I've been learning is Python.

I'm currently doing web development in the language. We have a rather old code base at work, so Python 2.7 for us. However, the official guideline from the Python community is to use Python 3 for a new work and only fall back to 2.7 if you have something that isn't ported over. That said, don't worry too much about the differences between the two - if you know one, it's easy to switch to the other. What you want to avoid however, is using Python 3 with a tutorial built around Python 2.x (and vice-versa). Like you've seen with the print function, the differences aren't much, but as you get into the tutorial/book that you're following, those differences can really frustrate. And for a learner, the last thing you need is to be wondering - is the error because of something you didn't understand or because of some 2.x vs 3.x difference.

I find the website - https://www.codewars.com/ to be very useful to exercise my skills. What I do, is try to solve one problem a day from them (actually its about 3 or 4 times a week). I started at the bottom level and am up to 6 kyu now. The thing to keep in mind with the site, is not just to solve the puzzles, but to compare your answers with what others have given (you see them after you've solved an exercise) and learn/explore about new syntax. I became familiar with list comprehensions that way.

-chronodekar

EDIT: Just saw your new post after this reply. Reading it now.

 

[chronodekar]

By Collatz, I'm assuming you are referring to this,
https://en.wikipedia.org/wiki/Collatz_conjecture
(first I'm encountering it!)

Also, this forum supports code blocks.

print('hello world')

Indentation is very important in Python and it will makes things easier to read if you format as above.

I'm guessing that you have trouble raising an exception if the number is 0 or negative? This should work,

if numb < 1:
    raise ValueError('Invalid input')

Useful Tutorial (if you want to move into web development):
http://tutorial.djangogirls.org/en/python_introduction/

An Awesome link (probably useless for a beginner - but bookmark it!),
https://github.com/vinta/awesome-python

Since you are on IRC, check out #python on freenode - it's a friendly place! (I lurk there and on #django)

-chronodekar

 

[Schema]

reddit.com/r/python

Also, Read Code

 

[Shirotsume]

More importantly, read old code that you've written. See that stupid fucking bullshit you wrote that's nigh uncomprehensible and a totally assbackwards way of doing it? That's why you comment- so those that thing worse, better, or differently than you, even future you, can understand what tyhe fuck your'e doing.

 

[PCHeintz72]

More importantly, read old code that you've written. See that stupid fucking bullshit you wrote that's nigh uncomprehensible and a totally assbackwards way of doing it? That's why you comment- so those that thing worse, better, or differently than you, even future you, can understand what tyhe fuck your'e doing.

I tell that to the guys at work all the time... comment, document. Programmers may not generally make the best documentation, but a few well placed half comments can make even bad code at least understandable later.

 

[Shirotsume]

Another bit of advice- unless you're doing something fairly specialized, comments should care more about WHY you're doing something, and how it interacts with the rest of the project as a whole.

I don't care about comments- or git/svn/cvs commits- that merely explain WHAT you did. I have eyes, I can see what it does. I want to know why you did it that way without having to bust out gdb or some bullshit to follow the execution path of the program and all its various idiosyncrasies.

 

[seitora]

Indentation is very important in Python and it will makes things easier to read if you format as above.

I'm guessing that you have trouble raising an exception if the number is 0 or negative? This should work,

if numb < 1:
    raise ValueError('Invalid input')

-chronodekar

Hello chronodekar:

The actual program works fine and prints out all the numbers leading up to 1 easily, and catches 0, 1, negative integers and floating point values. Rather, I was trying to get it to print 'Invalid. You must enter an integer.' if you actually entered a floating point value.

For some reason, it wouldn't print that specific message, but today when I looked  back at it and removed the hashtags to turn the commented lines back into code, it worked today. Very strange.


I didn't realise about the code function on this site, actually. I used the quote function because it still kept my indents, but the code function should definitely be cleaner to read.

Thanks for the other links, I'll be taking a look at them when I get there.

More importantly, read old code that you've written. See that stupid fucking bullshit you wrote that's nigh uncomprehensible and a totally assbackwards way of doing it? That's why you comment- so those that thing worse, better, or differently than you, even future you, can understand what tyhe fuck your'e doing.

Oh, I fully expect that that'll be the case.

 

[seitora]

Progress for August 22

So I went through Chapters 4 and 5 of Automate the Boring Stuff with Python yesterday, dealing with Lists and Dictionaries. 

I've got a 'cheat sheet' of syntax on-hand to refer to, and I've also got the Pocket Python Reference book that might be slightly out of date (covers up to Python 3.4, I don't know if there's any syntax difference between 3.4 and 3.5). I'm astounded and quite frankly intimidated even by how many functions I HAVEN'T encountered yet!


I've done a few exercises from the book, and a few of my own to familiarise myself with using lists and dictionaries:


This one takes manual input for the names of all your cats until your hit enter with no further input, then spits out a sentence listing your cats' names and the number you have.

Spoiler

catnames = []
catnumber = 0

while True:

    name = input("Insert a cat name here. If you are done, hit enter : ")

    if name == "":
        break

    catnames.append(name)
    catnumber += 1

    #every new cat name is appended to the catnames list
    #meanwhile, we keep a running track of how many cats there are
    #the list and number of cats will be used right away here
    

def printcat(name):

    if len(name) == 1:
        print("Your cat's name is " + name[0])

    elif len(name) == 0:
        print("Oh you poor dear, you don't have any cats :(")

    #A condition to catch somebody with no cats
    #The condition for 1 cat is to be grammatically correct in the event of
    #one cat in the household

    else:

        text = "Your cats' names are "
        var1 = 0

        for i in name:

            text += name[var1] + ", "

            var1 += 1

            if var1 == catnumber - 1:
                text = text + "and " + name[var1] + "."
                print(text)
                break

    #The for function retrieves each cat's name, starting at index 0, and
    #adds the cat name onto the sentence assigned to variable 'text'.
    #The if function nestled inside the for function activates when the second
    #to last cat name has been added to put in the grammar to end the sentence
    #followed by finally breaking the function
            

printcat(catnames)

Then I realised a way to reduce the else function at the end by several lines, so that was a case where I realised how I could steamline my code only a few minutes after writing it . Both functions still have the problem of the inappropriate use of an Oxford comma when you only have two cats, which would only require another elif function for if you have two cats.

Spoiler

catnames = []
catnumber = 0

while True:

    name = input("Insert a cat name here. If you are done, hit enter : ")

    if name == "":
        break

    catnames.append(name)
    catnumber += 1

    #every new cat name is appended to the catnames list
    #meanwhile, we keep a running track of how many cats there are
    

def printcat(name):

    if len(name) == 1:
        print("Your cat's name is " + name[0])

    elif len(name) ==0:
        print("Oh you poor dear, you don't have any cats :(")

    #A condition to catch somebody with no cats
    #The condition for 1 cat is to be grammatically correct in the event of
    #one cat in the household

    else:

        text = "Your cats' names are "

        for i in range(len(name)):

            if i == catnumber - 1:
                text = text + "and " + name[i] + "."
                print(text)
                break

            text += name[i] + ", "



    #The for function retrieves each cat's name, starting at index 0, and
    #adds the cat name onto the sentence assigned to variable 'text'.
    #The if function nestled inside the for function activates when the second
    #to last cat name has been added to put in the grammar to end the sentence
    #followed by finally breaking the function
            

printcat(catnames)

This one was an exercise using the 'in' function. You input a sentence, and if there are any vowels the program strips the sentence and returns it to you.

Spoiler

vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']

#purpose of this program is to return an input sentence with all vowels
#removed. Vowels list is used to ascertain what to remove.

def strip(text):

    string = ""

    for letter in text:

        if letter not in vowels:
            string += letter

    #if function adds any letters that aren't vowels to the string

    return string

answer = input("Put something here and it will be returned with vowels removed!")

print(strip(answer))

For this last one, this is the end-of-chapter project suggest in Automate The Boring Stuff with Python. The first function is to write out the inventory list with one item per line. 

The second part is to return the items from a loot list into a dictionary, where multiple iterations of an item in a list are added on.

Then the third part of the exercise was to add the second dictionary to the first. It was at this point that I realised that while Python has a few ways to add two dictionaries together, none of them work for what I needed. If two dictionaries have an identical key, the value of the key in the second dictionary overwrites the value of the key in the first dictionary. This is true even if all the values are all numbers and not strings!

At that point I went to bed since I was tired. I'll see what I can do today with that. I think I'll have to write a loop that uses a .get() function.

Spoiler

inventory = {'arrow': 12, 'gold coin' : 42, 'rope' : 1,
             'torch': 6, 'dagger': 1}

print(inventory)

def inList(bag):

    #intended to print each item and the number of that item on a separate line
    #plus print out the running total of all items

    print("Inventory:")

    number = 0

    for k in bag.keys():
        print(str(bag[k]) + " " + k)
        number += bag[k]

    print("Total number of items: " + str(number))

inList(inventory)



dragonLoot = ['gold coin', 'dagger', 'gold coin', 'gold coin', 'ruby']

def addItem(bag):

    #starts with an empty dictionary which adds item from a list. If
    #a list item is already a key in the dictionary, the value of the key
    #increases one. If the list item does not exist, then it is added as
    #a key to the dictionary with a start value of 1.

    tempLoot = {}

    for item in bag:

        if item in tempLoot.keys():
            tempLoot[item] += 1

        else:
            tempLoot.setdefault(item, 1)

    return tempLoot

print(addItem(dragonLoot))

 

[seitora]

Progress Report August 26

I got lazy the last few days, doing a few minutes of reading but not much up until yesterday. Going through Automate the Boring Stuff with Python still.

Syntax is still an issue for me as far as familiarity goes, which has tripped me up a few times. I'm also running into issues where I'm manipulating a single piece of data and both the act of calling it and then manipulating it requires a significant amount of methods. In one of the programs you'll see that I call a piece of data and manipulate it once and place it in a temporary variable, then perform a few manipulations on that variable, just so that I can split the code into two lines instead of one really ugly long line. Less optimised, but far easier for me to follow. In the former method, I kept hitting lots of syntax errors such as where I would forget to close brackets or parentheses, since there were so many things happening in a single line.

What I'm getting in the better habit of doing though is writing each little bit of code first, and then testing it, before continuing on. Usually with a test print() function to make sure data is being transformed the way I want it. 



This first program is a makeshift password locker that is run from the command line with the input 'passwordlocker.py pw 'account'. If I wanted to execute the program and then input the account I'm looking for there, I would change the variable 'account' to an input function.

Spoiler

#! python3

#a test project for a password locker. No real passwords here.

passwords = { 'email' : 'dragon',
              'TFF' : 'birthday',
              'LinkedIn' : 'Pikachu',
              'Amazon' : 'qwerty'
}

import sys, pyperclip

#print(sys.argv)

if len(sys.argv) < 2:
    
    """sys.argv comes with one argument already. Any subsequent argument is
    meant to call for the account type to input the password for. If there is
    no second argument, then there is no account to put a password in for,
    therefore it should shut down the program."""

    print("This is a rudimentary password account manager program.")
    sys.exit()

account = sys.argv[1]
    
if account in passwords:

    pyperclip.copy(passwords[account])
    print("The password for " + account + "has been copied to your clipboard.")

else:
    print("There is no account named " + account)

This next program takes whatever you have in your clipboard. If your clipboard has multiple lines on it (lines separated by an actual line break), then it'll add a '* ' to the start of each line and return it to your clipboard. If it only has one line, the program does that too. This is a rudimentary start for transforming large sequences of text with formatting of some sort.

Spoiler

#! python3

#a program to take all the lines on your clipboard, and then return
#them to you with a '* ' attached at the start

import pyperclip

text = pyperclip.paste()

sentences = text.split('\n')

#the '\n' section is crucial here to avoid splitting every single word, when
#you might have multiple words on a single line

for i in range(len(sentences)):
    sentences[i] = "* " + sentences[i]

text = '\n'.join(sentences)

pyperclip.copy(text)

This final program is meant to take a list with multiple sublists, such as this:

tableData = [['apples', 'oranges', 'cherries', 'banana'],
                    ['Alice', 'Bob', 'Carol', 'David'],
                    ['dogs', 'cats', 'moose', 'goose']]

and spit it out so that it looks like this:

   apples     Alice      dogs 
  oranges    Bob       cats 
  cherries   Carol  moose 
   banana  David  goose 

The formatting comes out godawful on this forum, but basically each column is supposed to be right-justified. The other tricky thing is that each sublist is printed from top to bottom, not left to right, so I have to print out tableData[0][0], then tableData[1][0], as opposed to tableData[0][1].

This is the one that could really be optimised, throwing out an entire for loop and two variables, but doing that would of course create a single line of ridiculously long length. It also assumes that each sublist has the same number of items.

Spoiler

tableData = [['apples', 'oranges', 'cherries', 'banana'],
             ['Alice', 'Bob', 'Carol', 'David'],
             ['dogs', 'cats', 'moose', 'goose']]

colWidth = []


"""This for loop finds the longest character length of each string in the
three lists and appends this character length to colWidth. Lists within lists
are referred to as sublists here. Main lists cannot use the word list since
list is an in-built Python variable.

colWidth will be used after the for loop to determine the spacing required
for right-justification for my table."""

for mainl in range(len(tableData)):

    colWidthTemp = []

    for sublist in range(len(tableData[mainl])):

        length = len(tableData[mainl][sublist])
        colWidthTemp.append(length)

    colWidth.append(max(colWidthTemp))

#print(colWidth)


"""This quick function creates a new list, where all the values here are
1 greater than in colWidth. This technically isn't required but is easier
to keep track of."""

rightJust = []

for num in range(len(colWidth)):
    rightJust.append(colWidth[num] + 1)


"""Because the purpose in generating the table is to go through the first
index item of each list before moving to the next line, instead of going
through each sublist per line, we have to iterate through list[x][0], then
through list [x][1]. Thus tempNum is set at 0 to start, and we iterate through
index 0 of each list, then tempNum is changed to 1, and we iterate through
index 1 of each list, etc.

The variable textTemp is not necessary and is less optimised. However, as
the coder it is easier to keep track of than to write this as a full line:

    print(tableData[subNum][tempNum].rjust(rightJust[subNum], " "), end=" ")

Instead of keeping the text variable and adding onto it with the three
iterations before printing it, I could also print each word separately,
then add a newline function to the end of each line in place of print(text).
"""

tempNum = 0

for num in range(len(tableData[0])):

    text = ""

    for subNum in range(len(tableData)):

        textTemp = tableData[subNum][tempNum]

        text = text + textTemp.rjust(rightJust[subNum]) + " "
        
        #print(textTemp.rjust(rightJust[subNum], " "), end=" ")

    tempNum += 1
    print(text)

 

[Schema]

General Comments:

iterating by index is generally considered non-pythonic.

Also take a quick look at

http://stackoverflow.com/questions/8234445/python-format-output-string-right-alignment

and

https://docs.python.org/3/library/functions.html#zip / https://docs.python.org/3.0/library/itertools.html#itertools.zip_longest

Keep it up!

 

[seitora]

I haven't been slacking off, I promise!

Really. Over the last two months I've been participating in MIT's 6.00.1x course for Python. Final exam starts tomorrow, and so far I have a 73.21/75 marks possible. I'm hesitant to post any of my work from my problem sets until the course is actually over, though. The first four weeks were at about the bounds of what I knew already, but week 3 had recursion, week 5 got into object-oriented programming and algorithmic complexity. OOP so far has been a blast. Tough, of course, but once I got more used to the actual syntax the rest has fallen into place a little easier.


I remember saying several months back that there was an issue I had with trying to add two dictionaries together that might have identical keys. I looked at it again today and thought to myself "...really? I had trouble with that?"

Spoiler

def updateInv(inv, loot):

    """Assumes both inv and loot are dictionaries. All keys are strings and
       all values are integers. Dictionaries do not need equal number of entries
       to start. Dictionaries may share keys, in which case the value of
       the loot dictionary is to be added onto the inventory dictionary, NOT
       to replace it.

       Updates the inventory with the generated loot dictionary from lootDict.


    """

    for key in loot:

        try:
            inv[key] += loot[key]

        except:
            inv[key] = loot[key]

 

[seitora]

Finally started doing Project Euler.

Problem 1, but I'm going to attempt to build a recursive version of this and see how significantly it increases my clock time.

Spoiler

#Find the sum of all the multiples of 3 or 5 below 1000.

"""
Assumes one running total, adding 3, 5, 6, 9, 10, 12, 15, etc

Assumes _below_ 1000, meaning 1000 as a multiple of 5 is not included.
"""


def multiSum(natNum1, natNum2, maxNum):

  """
natNum should be a natural number

maxSum - 1 is the highest number in the range that will be looked at.
ie. 1000, will only look up to 999, just like in the Python range function.
  """

  total = 0
  count = 0

  while maxNum > count:
    if count % natNum1 == 0 or count % natNum2 == 0:
      total += count

    count += 1


  return total



  """
If I wanted to generalise this program, write a function that finds the
greatest common divisor of two numbers, and increase the range by the GCD
each time. However, since the GCD of 3 and 5 is 1, that would be useless here.

Alternatively, I could use recursion once I find the lowest common multiple LCM
 In the example of 3 and 5, the LCM is 15, and
the sum up to there is 3 + 5 + 6 + 9 + 10 + 12 + 15. That's 7 elements being
summed up together, with the total of 45.

The sum of up to 30 is 195, but instead of saying 18, 20, 21..., it can also
be described as (3 + 15), (5 + 15), (6 + 15), where we have the 7 elements of
0 - 15 plus (7 elements * 15) = 45 (sum 1-15) + 45 + 105 (sum 16-30).
Sum 31-45 would be 45 + 7 * 30, sum 46-60 would be 45 + 7 * 45, etc
  """

 

[seitora]

I actually realised even that program above is a little inelegant since I have one more variable than I need to use.

Spoiler

def multiSum(natNum1, natNum2, maxNum):

  """
natNum should be a natural number

maxSum - 1 is the highest number in the range that will be looked at, using
the range function.
  """

  total = 0

  for i in range(maxNum):
    if i % natNum1 == 0 or i % natNum2 == 0:
      total += i

  return total

I decided to expand on this program to be able to hand really large numbers a lot quicker. I couldn't figure out how to make it recursive, but I was able to make it iterative. I do this by finding the prime factors of each number and combining them to find the least common multiple, then using an easy principle to iterate by the size of the LCM instead of by 1. In the test case (232, 543, 20000000), the first program takes 5.5 seconds, but this revised program below takes 0.05 seconds.

Spoiler

"""At low numbers buildDict would be unnecessary, but at far bigger numbers
it would be practically a requirement for quicker runtime.
"""


def primeFactors(num):

    primeList = []
    denom = 2

    while num > 1:

        if num % denom == 0:
            primeList.append(denom)
            num /= denom
            denom = 2
        else:
            denom += 1

    return primeList

def buildDict(aList):

    newDict = { }

    for element in aList:
        try:
            newDict[element] += 1
        except:
            newDict[element] = 1

    return newDict


def LCM(num1, num2):

    if num1 % num2 == 0:
        return num2

    elif num2 % num1 == 0:
        return num1

    else:
        prime1 = buildDict(primeFactors(num1))
        prime2 = buildDict(primeFactors(num2))
        prime3 = prime1.copy()

        for key in prime2:
            if key not in prime3:
                prime3[key] = prime2[key]

            else:
                if prime2[key] <= prime3[key]:
                    pass

                else:
                    prime3[key] = prime2[key]

    lcm = 1

    for element in prime3:

        lcm = lcm * element ** (prime3[element])

    return lcm

        

def quickSum(num1, num2, numMax):

    lcm = LCM(num1, num2)

    base = 0
    elements = 0

    for i in range(1,lcm+1):
        if i % num1 == 0 or i % num2 == 0:
            base += i
            elements += 1

    total = 0

    cmIncrement = lcm
    counter = 0

    while numMax > cmIncrement:

        total += base + elements * counter * lcm

        cmIncrement += lcm
        counter += 1

    cmIncrement -= lcm

    for i in range(cmIncrement + 1,numMax):
        if i % num1 == 0 or i % num2 == 0:
            total += i   


    return total
      

 

[chronodekar]

I remember the feeling of awe when I first understood what recursion actually did - calling the same function again. Back then, I used to think that all good programmers did recursion all the time. Many years later, I learned that it was more about trade-offs than blindly implementing it everywhere. Broadly speaking, there are two ways to handle a repetitive task - recursion and iteration.

Iteration is what your for-loops do. Change a counter, but perform the same set of actions. Recursion is about calling the same function until some kind of stop condition is reached. A big difference between the two is in how memory is utilized. Each time you do a recursive call, you push the current memory state onto the stack. Which means a lot of memory waste if you do something like a 1000+ recursive call depth instead of using for-loops. This, of-course will depend on specifics of the situation.

About the first euler problem, a solution I like to talk about is to just use a loop for 1000, a couple of IF statements to check for i%3 == 0 in one and i%5 == 0 in the other. If it matches either just add the number to the count. Then, have another if statement to check for i%15 ==0 since those numbers would be added twice by the earlier step, so subtract once to set things right.

Doing it in this manner makes the solution a O(n) complexity answer.

-chronodekar

 

[seitora]

chronodekar, you don't actually even need to have a statement to check for i % 15 == 0. What I did is put a statement to check for i%3 OR i% 5, so multiples of 3 and 5 such as 15 are still only added once.

Looking at the Euler discussion forum, there's actually an even more elegant solution, through the use of (n/2)(l+a) for finding the sum of a sequence of terms. At small values such as what the first problem asks for with (3, 5, 1000), that would work pretty well on its own.

I gave myself the challenge of writing something to cut down on processing times at REALLY big numbers to basically extend my learning and understanding on my own initiative, and basically experience with thinking out problems. I would eliminate the last function of my revised program, and instead code something to find the last possible term for each value. For example, if I was given something like (12763, 339521, 100,000,000,000):

#Find least common multiple of 12763 and 339521 (primeFactors, buildDict, and LCM functions will do this really quick)
#Find last possible term of 12763, 339521, and the LCM range 100,000,000,000
#This could be accomplished by taking 100,000,000,000 - 12763, dividing it by 12763. I get 7835148.5, so round up to 7835149 and multiply by 12763. I get 7835148 * 12763 = 99,999,993,924. I know it's the 7835148th term and the maximum within the range of 100,000,000,000.
#Do this for 339521 and the LCM. Find the sum of the sequences for 12763 and 339521, add them, then subtract the sum sequence for the LCM.




I'll be fooling around with a lot of my own projects, too, and maybe use PyGame to do a couple of simpler things (number game, move onto something like a platformer or bullet hell). The first big project I have on my mind is doing something like a rogue-like RPG, played out over a board-game style map.

 

[chronodekar]

Looks like you got the point! Note: I wrote that it's a solution I like to _talk_ about and not that it's the most optimal solution. When I take interviews, almost everyone who's expanded more about the solution will be approved for the next round - when hired, they turn out pretty good too!

Disappointingly, I've met waay too many folks with 2 - 4 years of 'industry' experience who don't know how to write FizzBuzz ... T_T

-chronodekar

 

[seitora]

I looked at the FizzBuzz problem since you just mentioned it now. Maybe in other languages it might be difficult, but Python? I could have that done in a few minutes.

Spoiler

a = 'Fizz'
b = 'Buzz'

for i in range (1, 101):

    if i % 3 == 0 and i% 5 == 0:
        print(a + b)    

    elif i % 3 == 0:
        print(a)

    elif i % 5 == 0:
        print(b)

    else:
        print(i)

I could also get rid of the elif statements and have 'if 3' followed by 'if 5', to print Fizz and Buzz separately on 15, 30... but then they'd print on separate lines (I could nest in another conditional to prevent a line break, but at that point I'd be running through more conditional checks than with the above if/elif/else statement).

 

[seitora]

And so I'll try to do at least one Euler problem a day even if I'm feeling absolutely lazy about everything else, just to continue staying sharp.

Problem 3 asks to find the largest prime factor of a number. I actually wrote a function to do that earlier, but in the process I wrote a lengthy documentation on how it works and a note on how to optimise it (I like to be really thorough on explaining this stuff )

Spoiler

[/code]
"""This program is designed to find the largest prime factor
of a number. Because any number can be described as the product of all of
its prime factors (8 = 2 * 2 * 2, 18 = 2 * 3 * 3, etc), the main function
of this program is to take a number, and divide by a denominator starting
at 2. If the number is divisible by the denominator, the denominator is
appended to a prime Factors list. The number is divided by the denominator
and set as the new number, and denom is set back to 2. The function repeats
until the resulting number is 1, at which point all prime factors have been
found.

ie. 35 / 5, new number of 7, list is [5]
7 / 7, new number of 1, list is [5, 7]
[5, 7] are the factors of 35

The prime factors list is then returned.

From there, all that is required to find the largest prime factor is to run
a simple max() function on the prime factors list.

How to speed up this program: instead of increasing the denominator by 1
each time (11 not divisible by 2?  Divide by 3, then 4, then 5, then 6, etc),
put in a pre-existing list of prime numbers that the denominator ticks
through every time [2, 3, 5, 7, 11, 13, 17...].

"""



def primeFactors(num):

    primeList = []
    denom = 2

    while num > 1:

        if num % denom == 0:
            primeList.append(denom)
            num /= denom
            denom = 2
        else:
            denom += 1

    return primeList


print(max(primeFactors(600851475143)))

[/code]

 

[seitora]

Euler problem 4: Find the largest possible product of two 3-digit problems that is a palindrome (ie. 967769). I spent more time writing the doc string than I did the actual program. Optimisation could be done by coming up with a quicker method to tick to the next palindrome if the current case fails. The current program uses three things to cut down on the brute-force time.

Spoiler

"""
This program is designed to find the largest possible product of two 3-digit
numbers that is a palindrome, ie. 978879

This program brute-forces the solution, with three principles designed to
minimise the amount of time required to brute force.

a) The largest product of two 3-digit numbers, 999 * 999 = 998001. Therefore,
the largest possible palindrome number less than this is 997799, and this is
used as our starting case. We merely need to find the first instance of a
palindrome product counting back from 997799, instead of counting up from
100 * 100 = 10000 and finding the largest possible palindrome product.

b) If 997799 cannot be expressed as the product of two 3-digit numbers, it
ticks down by 1100 to 996699, and will continue ticking down by 1100. At 990099,
the program adds 9900, then subtracts 10010 to get 989989.

c) The 'square-root' factors rule. For an example, if you are finding the factor
of 100, you can find factors of 1, 2, 4, 5, 10. After the square-root, which is
10, I know the remaining factors will be 20, 25, 50, and 100, because those
were the quotients from dividing 100 by 1, 2, 4, 5. I use this principle, but
counting from 999 down to the square root of the palindrome instead. In the
case of 997799, square root is 998.89. If I get to 998 and there is still no
value where palindrome % denom = 0, I tick down to the next palindrome.

Square root value is rounded and used as the last denominator value.

Program could be generalised further to work for any length of digit products,
ie largest palindrome product of 4-digit values, 5-digit values, etc

"""




import math

def solvePalin(pMax):

    testCase = pMax
    solveFlag = False
    testTrue = ()

    while True:

        root = round(math.sqrt(testCase))
        denom = 999

        while denom >= root:

            if testCase % denom == 0:
                solveFlag = True
                testTrue = (testCase, denom, int(testCase / denom))
                break

            else:
                denom -= 1

        if solveFlag:
            break

        else:
            if int(testCase/100) % 100 == 0:
                #990099 / 100 = 9900.99, int(9900.99) = 9900, 9900 % 100 = 0
                #This tells me to add 9900 on and subtract 10010 to get 989989
                
                if int(testCase/10) % 100 == 0:
                    testCase += 9900
                    testCase += 90090
                    testCase -= 100001

                else:
                    testCase += 9900
                    testCase -= 10010

            else:
                testCase -= 1100

    return testTrue

print(solvePalin(997799))

 

[Schema]

And so I'll try to do at least one Euler problem a day even if I'm feeling absolutely lazy about everything else, just to continue staying sharp.

Problem 3 asks to find the largest prime factor of a number. I actually wrote a function to do that earlier, but in the process I wrote a lengthy documentation on how it works and a note on how to optimise it (I like to be really thorough on explaining this stuff )

Spoiler

[/code]
"""This program is designed to find the largest prime factor
of a number. Because any number can be described as the product of all of
its prime factors (8 = 2 * 2 * 2, 18 = 2 * 3 * 3, etc), the main function
of this program is to take a number, and divide by a denominator starting
at 2. If the number is divisible by the denominator, the denominator is
appended to a prime Factors list. The number is divided by the denominator
and set as the new number, and denom is set back to 2. The function repeats
until the resulting number is 1, at which point all prime factors have been
found.

ie. 35 / 5, new number of 7, list is [5]
7 / 7, new number of 1, list is [5, 7]
[5, 7] are the factors of 35

The prime factors list is then returned.

From there, all that is required to find the largest prime factor is to run
a simple max() function on the prime factors list.

How to speed up this program: instead of increasing the denominator by 1
each time (11 not divisible by 2?  Divide by 3, then 4, then 5, then 6, etc),
put in a pre-existing list of prime numbers that the denominator ticks
through every time [2, 3, 5, 7, 11, 13, 17...].

"""



def primeFactors(num):

    primeList = []
    denom = 2

    while num > 1:

        if num % denom == 0:
            primeList.append(denom)
            num /= denom
            denom = 2
        else:
            denom += 1

    return primeList


print(max(primeFactors(600851475143)))

[/code]

What happens if you remove 'denom = 2' in the while section?

 

[seitora]

What happens if you remove 'denom = 2' in the while section?

It should actually speed up. In the case of say 36, it'll find 2 as a prime factor, then 2 as a prime factor again, so [2, 2] with remainder of 9. Once it finds 3 as another prime factor, it shouldn't tick back down to 2, because I've already disproven 2 as being a prime factor for a 3rd time. I'm not sure why I have that in there (I'm probably just used to restoring the denominator value after I've found a true value and then ticking up again another until I find another true value).

 

[Schema]

What happens if you remove 'denom = 2' in the while section?

It should actually speed up. In the case of say 36, it'll find 2 as a prime factor, then 2 as a prime factor again, so [2, 2] with remainder of 9. Once it finds 3 as another prime factor, it shouldn't tick back down to 2, because I've already disproven 2 as being a prime factor for a 3rd time. I'm not sure why I have that in there (I'm probably just used to restoring the denominator value after I've found a true value and then ticking up again another until I find another true value).

   Exactly