﻿Problem Solving with Algorithms and Data Structures - Chapter 1 - Introduction - Terminal In A Simputer

# Simputer

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

This post is part 1 of the "Problem Solving with Algorithms and Data Structures Reading" series:

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=False

Traceback (most recent call last):
File "<pyshell#137>", line 1, in -toplevel-
myTuple=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`, `i`Integer
`u`Unsigned integer
`f`Floating point as m.ddddd
`e`Floating point as m.ddddde+/-xx
`E`Floating point as m.dddddE+/-xx
`g`Use `%e` for exponents less than −4 or greater than +5, otherwise use `%f`
`c`Single character
`s`String, 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)
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()
```