Problem Solving with Algorithms and Data Structures - Chapter 1 - Introduction

Table Of Contents

Refreshing my knowledges about algorithms in a Python way1.

1.8. Getting Started with Data

Operators

OperatorExplanation
<Less Than
>Greater Than
<=Less Than Or Equal to
>=More Than Or Equal To
==Equal To
!=Not Equal To
andBoth Operands True for the result to be True
orEither or both of the operands True for the result to be True
notNegates the original boolean value, False to True, True to False

Data Types

List

Operators

[ ]: Access an element of a sequence concatenation

+: Combine sequences together

*: Concatenate a repeated number of times (Reference the original value)

in: Ask whether an item is in a sequence

len: Ask the number of items in the sequence

[ : ]: Extract a part of a sequence

Methods

alist.append(item): Adds a new item to the end of a list

alist.insert(i,item): Inserts an item at the ith position in a list

alist.pop(): Removes and returns the last item in a list

alist.pop(i): Removes and returns the ith item in a list

alist.sort(): Modifies a list to be sorted

alist.reverse(): Modifies a list to be in reverse order

del alist[i]: Deletes the item in the ith position

alist.index(item): Returns the index of the first occurrence of item

alist.count(item): Returns the number of occurrences of item

alist.remove(item): Removes the first occurrence of item

String

Methods

astring.center(w): Returns a string centered in a field of size w

astring.count(item): Returns the number of occurrences of item in the string

astring.ljust(w): Returns a string left-justified in a field of size w

astring.lower(): Returns a string in all lowercase

astring.rjust(w): Returns a string right-justified in a field of size w

astring.find(item): Returns the index of the first occurrence of item

astring.split(schar): Splits a string into substrings at schar

Tuple

Similar to list the difference is that the members in a tuple is immutable.

>>> myTuple[1]=False

Traceback (most recent call last):
  File "<pyshell#137>", line 1, in -toplevel-
    myTuple[1]=False
TypeError: object doesn't support item assignment

Set

A set is an unordered collection of zero or more immutable Python data objects. Sets do not allow duplicates and are written as comma-delimited values enclosed in curly braces. The empty set is represented by set(). Sets are heterogeneous, and the collection can be assigned to a variable as below.

>>> {3,6,"cat",4.5,False}
{False, 4.5, 3, 6, 'cat'}
>>> mySet = {3,6,"cat",4.5,False}
>>> mySet
{False, 4.5, 3, 6, 'cat'}
>>>
Operators

in: Set membership

len: Returns the cardinality of the set

aset | otherset: Returns a new set with all elements from both sets

aset & otherset: Returns a new set with only those elements common to both sets

aset - otherset: Returns a new set with all items from the first set not in second

aset <= otherset: Asks whether all elements of the first set are in the second

Methods

aset.union(otherset): Returns a new set with all elements from both sets. The same result as aset | otherset

aset.intersection(otherset): Returns a new set with only those elements common to both sets. The same result as aset & otherset

aset.difference(otherset): Returns a new set with all items from first set not in second. The same result as aset - otherset

aset.issubset(otherset): Asks whether all elements of one set are in the other

aset.add(item): Adds item to the set

aset.remove(item): Removes item from the set

aset.pop(): Removes an arbitrary element from the set

aset.clear(): Removes all elements from the set

Dictionary

Dictionaries are collections of associated pairs of items where each pair consists of a key and a value.

Operators

myDict[k]: Returns the value associated with k, otherwise its an error

key in adict: Returns True if key is in the dictionary, False otherwise

del adict[key]: Removes the entry from the dictionary

Methods

adict.keys(): Returns the keys of the dictionary in a dict_keys object

adict.values(): Returns the values of the dictionary in a dict_values object

adict.items(): Returns the key-value pairs in a dict_items object

adict.get(k): Returns the value associated with k, None otherwise

adict.get(k,alt): Returns the value associated with k, alt otherwise

1.9 Input and Output

input("prompt message") get a string from the input.

String Formatting with %

>>> "%s %d" % ("aa", 1)
'aa 1'
>>> "%(aa)s %(bb)d" % {"aa":"aa", "bb":1}
'aa 1'

% types

CharacterOutput Format
d, iInteger
uUnsigned integer
fFloating point as m.ddddd
eFloating point as m.ddddde+/-xx
EFloating point as m.dddddE+/-xx
gUse %e for exponents less than −4 or greater than +5, otherwise use %f
cSingle character
sString, or any Python data object that can be converted to a string by using the str function.
%Insert a literal % character

Number Dealing

ModifierExampleDescription
number%20dPut the value in a field width of 20
-%-20dPut the value in a field 20 characters wide, left-justified
+%+20dPut the value in a field 20 characters wide, right-justified
0%020dPut the value in a field 20 characters wide, fill in with leading zeros.
.%20.2fPut the value in a field 20 characters wide with 2 characters to the right of the decimal point.
(name)%(name)dGet the value from the supplied dictionary using name as the key.

1.10 Control Structures

  • while keeps running until the condition is not met.
  • for keeps iterating over all the members of a collection until all of them have been iterated over.
  • The statements under if will be executed once the condition is met, otherwise python will check if the condition in elif is met, if not then next elif, stops at else (If no else then none of the statements will be executed).

List Comprehension

>>> sqlist=[x*x for x in range(1,11)]
>>> sqlist
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> sqlist=[x*x for x in range(1,11) if x%2 != 0]
>>> sqlist
[1, 9, 25, 49, 81]
>>>[ch.upper() for ch in 'comprehension' if ch not in 'aeiou']
['C', 'M', 'P', 'R', 'H', 'N', 'S', 'N']

1.11 Exception Handling

>>> try:
...     print(a)
... except Exception as err:
...     print(type(err))
...     for arg in err.args:
...             print(arg)
...
<class 'NameError'>
name 'a' is not defined

1.12 Function Defining

>>> def square(n):
...    return n**2
...
>>> square(3)
9
>>> square(square(3))
81

1.13 Object-Oriented Programming in Python: Defining Classes

1.13.1 A Fraction Class

fractionthing.py

def gcd(m, n):
    while m % n != 0:
        oldm = m
        oldn = n

        m = oldn
        n = oldm % oldn
    return n

class Fraction:
    def __init__(self, top, bottom):
        self.num = top
        self.den = bottom
    def show(self):
        print(self.num, "/", self.den)
    def __str__(self):
        return str(self.num) + "/" + str(self.den)
    def __add__(self, otherfraction):
        newnum = self.num * otherfraction.den + otherfraction.num * self.den
        newden = self.den * otherfraction.den
        com = gcd(newnum, newden)
        return Fraction(newnum//com, newden//com)
    def __eq__(self, other):
        firstnum = self.num * other.den
        secondnum = self.den * other.num

        return firstnum == secondnum
>>> from fractionthing import Fraction
>>> a=Fraction(10,12423)
>>> a.show()
10 / 12423
>>> a
<test.Fraction object at 0x7f764f0e70f0>
>>> str(a)
'10/12423'
>>> print(a)
10/12423
>>> a.__str__()
'10/12423'
>>> b=Fraction(7,123782161)
>>> a+b
<test.Fraction object at 0x7f764f1039e8>
>>> c=a+b
>>> print(c)
1237908571/1537745786103
>>> a==b
False
>>> a.__eq__(b)
False

1.13.2 Inheritance: Logic Gates and Circuits

Self-Check:

class LogicGate:

    def __init__(self,n):
        self.name = n
        self.output = None

    def getName(self):
        return self.name

    def getOutput(self):
        self.output = self.performGateLogic()
        return self.output


class BinaryGate(LogicGate):

    def __init__(self,n):
        LogicGate.__init__(self,n)

        self.pinA = None
        self.pinB = None

    def getPinA(self):
        if self.pinA == None:
            return int(input("Enter Pin A input for gate "+self.getName()+"-->"))
        else:
            return self.pinA.getFrom().getOutput()

    def getPinB(self):
        if self.pinB == None:
            return int(input("Enter Pin B input for gate "+self.getName()+"-->"))
        else:
            return self.pinB.getFrom().getOutput()

    def setNextPin(self,source):
        if self.pinA == None:
            self.pinA = source
        else:
            if self.pinB == None:
                self.pinB = source
            else:
                print("Cannot Connect: NO EMPTY PINS on this gate")


class AndGate(BinaryGate):

    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a==1 and b==1:
            return 1
        else:
            return 0

class OrGate(BinaryGate):

    def __init__(self,n):
        BinaryGate.__init__(self,n)

    def performGateLogic(self):

        a = self.getPinA()
        b = self.getPinB()
        if a == 1 or b == 1:
            return 1
        else:
            return 0

class UnaryGate(LogicGate):

    def __init__(self,n):
        LogicGate.__init__(self,n)

        self.pin = None

    def getPin(self):
        if self.pin == None:
            return int(input("Enter Pin input for gate "+self.getName()+"-->"))
        else:
            return self.pin.getFrom().getOutput()

    def setNextPin(self,source):
        if self.pin == None:
            self.pin = source
        else:
            print("Cannot Connect: NO EMPTY PINS on this gate")


class NotGate(UnaryGate):

    def __init__(self,n):
        UnaryGate.__init__(self,n)

    def performGateLogic(self):
        if self.getPin():
            return 0
        else:
            return 1

class NorGate(BinaryGate):

    def __init__(self, n):
        BinaryGate.__init__(self, n)

    def performGateLogic(self):
        self.pinA = self.getPinA()
        self.pinB = self.getPinB()

        if self.pinA == 0 and self.pinB == 0:
            return 1
        else:
            return 0

class NandGate(BinaryGate):

    def __init__(self, n):
        BinaryGate.__init__(self, n)

    def performGateLogic(self):
        self.pinA = self.getPinA()
        self.pinB = self.getPinB()

        if self.pinA == 0 or self.pinB == 0:
            return 1
        else:
            return 0

class Connector:

    def __init__(self, fgate, tgate):
        self.fromgate = fgate
        self.togate = tgate

        tgate.setNextPin(self)

    def getFrom(self):
        return self.fromgate

    def getTo(self):
        return self.togate



def main():
   g1 = AndGate("G1")
   g2 = AndGate("G2")
   g3 = NorGate("G3")
   g5 = NotGate("G5")
   g6 = NotGate("G6")
   g7 = AndGate("G7")
   c1 = Connector(g1, g3)
   c2 = Connector(g2, g3)
   c3 = Connector(g1, g5)
   c4 = Connector(g2, g6)
   c5 = Connector(g5, g7)
   c6 = Connector(g6, g7)
   print(g3.getOutput() == g7.getOutput())

main()