Science

Louis Pasteur: Describing in simple detail one of the great discoveries (and experiments) of mankind

Posted on

“Here is an infusion of organic matter, as limpid as distilled water, and extremely alterable. It has been prepared to-day. To-morrow it will contain animalculae, little infusories, or flakes of mouldiness. I place a portion of that infusion into a flask with a long neck, like this one. Suppose I boil the liquid and leave it to cool. After a few days, mouldiness or animalculae will develop in the liquid. By boiling, I destroyed any germs contained in the liquid or against the glass ; but that infusion being again in contact with air, it becomes altered, as all infusions do. Now suppose I repeat this experiment, but that, before boiling the liquid, I draw (by means of an enameller’s lamp) the neck of the flask into a point, leaving however, its extremity open. This being done, I boil the liquid in the flask, and leave it to cool. Now the liquid of this second flask will remain pure not only two days, a month, a year, but three or four years — for the experiment I am telling you about is already four years old, and the liquid remains as limpid as distilled water. What difference is there, then, between those two vases ? They contain the same liquid, they both contain air, both are open ! Why does one decay and the other remain pure? The only difference between them is this : in the first case, the dusts suspended in air and their germs can fall into the neck of the flask and arrive into contact with the liquid, where they find appropriate food and develop; thence microscopic beings. In the second flask, on the contrary, it is impossible, or at least extremely difficult, unless air is violently shaken, that dusts suspended in air should enter the vase; they fall on its curved neck. When air goes in and out of the vase through diffusions or variations of temperature, the latter never being sudden, the air comes in slowly enough to drop the dusts and germs that it carries at the opening of the neck or in the first curves. This experiment is full of instruction ; for this must be noted, that everything in air save its dusts can easily enter the vase and come into contact with the liquid. Imagine what you choose in the air — electricity, magnetism, ozone, unknown forces even, all can reach the infusion. Only one thing cannot enter easily, and that is dust, suspended in air. And the proof of this is that if I shake the vase violently two or three times, in a few days it contains animalculae or mouldiness. Why? because air has come in violently enough to carry dust with it. And, therefore, gentlemen, I could point to that liquid and say to you, I have taken my drop of water from the immensity of creation, and I have taken it full of the elements appropriated to the development of inferior beings. And I wait, I watch, I question it, begging it to recommence for me the beautiful spectacle of the first creation. But it is dumb, dumb since these experiments were begun several years ago; it is dumb because I have kept it from the only thing man cannot produce, from the germs which float in the air, from Life, for Life is a germ and a germ is Life. Never will the doctrine of spontaneous generation recover from the mortal blow of this simple experiment.”

 

Source: https://en.wikiquote.org/wiki/Louis_Pasteur

Digital Marketing

How do I know if a web page has Google Analytics associated with it?

Posted on

For web pages you visit (and don’t own)

Note: If the web page you’re visiting uses Google Tag Manager, you won’t be able to determine whether or not the page uses Analytics. Pages using Google Tag Manager will have a container snippet instead of the Analytics tracking code. Only users with access to the Google Tag Manager container being used can see what tags (including the Analytics tracking code) are being used.

There are different ways you can find out if a web page you’re visiting (and don’t own) uses Analytics. The most common ways to check are built into most modern browsers. You can either view the source code, which instructs the browser what to load or use browser-based developer tools to see if the page is sending information to Analytics.

When you’re looking for Analytics, try both methods. It’s common for the Analytics JavaScript to be included directly on a web page, so you can see it in the source code. It’s possible for a page to call Analytics from another source. In these cases, you won’t see the JavaScript directly on the page. You’ll only be able to tell if the page is using Analytics if you check the developer tools for communication with Analytics.

If you’re using Chrome, and want to check the source code for the Analytics JavaScript:

  1. Load a web page in the Chrome browser.
  2. Right-click the page, then click View page source.
  3. You should see a lot of code. Search the page for gtag.js or analytics.js (for Universal Analytics) or ga.js (for Classic Analytics). A site can use both the Universal and Classic JavaScript libraries at the same time.

If you’re using Chrome, and want to use the developer tools:

  1. Load a web page in the Chrome browser.
  2. From the browser menu, select More tools > Developer tools.
  3. Click the Network tab. If you don’t see any data in the table, refresh the page.
  4. In the Initiator column, look for gtag.js or analytics.js (for Universal Analytics) or ga.js (for Classic Analytics). A site can use both the Universal and Classic JavaScript libraries at the same time.

Availability and access to these tools vary. Check your browser’s help center for more information on how to check the source code or use the developer tools.

Source: https://support.google.com/analytics/answer/1032399?hl=en

Politics

Until today, I didn’t know that Germany does not allow Google Street View

Posted on

Today I finished book II of Victor Klemperer’s “I Will Bear Witness” and in it he mentions his and his wife’s stay at Unterbernbach, Germany as refugees. I wanted to take a look at a street view of this tiny German hamlet that hosted the Klemperer’s for several weeks following their flight from bombed-out Dresden. However, I found out that Germany does not allow Google Street View ostensibly for privacy issues. News to me. Apparently, it’s been a subject of discussion for years just under my radar.  I’m happy that V. Klemperer and his wife survived their Ulysses-like travails in Nazi Germany 1933-1945. I will miss them.

Digital Marketing

Question from a new digital marketer

Posted on

Peter-Bakke-question

I’m a new digital marketer.  Let me ask you this. If I go back to him and tell him I can’t do it for $200 a month but offer a different price, in your experience, how many posts a day or week helps increase the most reach. I know, there is no hard and fast rule but if he comes back and asks how often would we need to post to see some results, how would you answer that?

PA Bakke
10:01 AM (0 minutes ago)

Hello Jim,

Please define “results” first … You need to know where you are going on the map before you can plan the trip.

To carry on the analogy, it sounds pretty obvious that this guy does not know a THING about maps, planes, trains, or automobiles, but just wants to arrive at the destination (which is… ?)

For example:

1 lead a week will require effort/cost A
10 leads a week will require B

and/or

1 new email subscriber a week will require effort/cost C
10 new email subscribers a week will require effort/cost D

etc.

Cheers, Pete

Digital Marketing

Is someone tracking email opens by you and your company? Use a simple two-step process to find out.

Posted on

Someone tracking email exchanges?

Have you ever wondered if someone is tracking email exchanges with you?

That is, unbeknownst to you, is a sender tracking email opens and non-opens by you or your company personnel? Perhaps you’ve had a series of communications with an individual. Do they secretly know that you’ve skipped opening some of their emails and read others?

If the email contains a ‘tracking pixel’ then yes, they know you’ve opened (or not opened) their email. This functionality is usually provided via sales CRM software such as Salesforce, etc.

In Gmail, there is an easy 2-step process to see if a sender is tracking your email opens. This basic process can be used for other email services as well. The downside for this process is that in order to determine if there is a tracking pixel, you have to of course open the email whether you want to or not.

1) In Gmail, open the email of interest. On the upper right, you’ll see three vertical dots. If you hover over them it will indicate “More.” Click on the dots and select “Show Original.”

2) A new tab will open up showing all the ugly internal code that makes up an email. Do a “Find” in the message (on PCs do a “CNTRL F”) and search for ‘.gif’

If you find something like ‘open.gif’ or “track.gif” you are being tracked and the sender knows that you opened the email(s).

Here’s example code (note the ‘open.gif’ instance):

<div dir=3D”ltr”>That is more of an SEO tool for website audits. Our platform has a lot of the same functionality but is far more robust. I can dive deeper tomorrow if your game for a quick call?=C2=A0<img src=3D”https://xyz.salesloftlinks.com/email_trackers/eff868f8-9726-4c88-a25e-245b527c9f92/open.gif” alt=3D”” width=3D”1″ height=3D”1″></div>

Tracking Pixel Definition:

“A tracking pixel (also called 1×1 pixel or pixel tag) is a graphic with dimensions of 1×1 pixels that is loaded when a user visits a website or opens an email, and is used to track certain user activities. With a tracking pixel, advertisers can acquire data for online marketing, web analysis or email marketing.”

Souorce: https://en.ryte.com/wiki/Tracking_Pixel

Data Analysis

Example of local business schema

Posted on

<div itemscope itemtype=”http://schema.org/LocalBusiness” align=”right”>

<span itemprop=”name”>Wellbeing Institute</span><br />

<span itemprop=”address” itemscope itemtype=”http://schema.org/PostalAddress”>

<span itemprop=”streetAddress”>3615 N Prince Village Pl Ste 121</span><br />

<span itemprop=”addressLocality”>Tucson</span>

<span itemprop=”addressRegion”>AZ</span>

<span itemprop=”postalCode”>85719-2034</span><br />

<span itemprop=”telephone”>Phone: (520) 225-0584</span><br />

<span itemprop=”faxNumber”>FAX: (520) 232-2512</span><br />
</span>

<div itemprop=”image” itemscope itemtype=”http://schema.org/ImageObject”>

<img src=”https://wellbeingaz.org/wp-content/uploads/2017/12/wbi-logo-initial-close-cropped-transparent.png” alt=”Wellbeing Institute” width=”50″ itemprop=”url”>
</div>

</div>

 

### P.S.  Google gives an error if there is no image here: https://search.google.com/structured-data/testing-tool/u/0/

Data Analysis

Five tough Python interview questions: Anagram, Palindrome, Minimum Spanning Tree, Binary Search Tree, Linked Lists

Posted on

My Udacity mentor said the following about my final Python project: “Peter, to be honest, you are one of the very few students who attempted and passed (the technical interview questions) part (of the DAND+ nanodegree). In fact, I took a look at your (Python) code. It is really good.”

udacity-Peter-bakke

# coding: utf-8

# Final Interview Questions 1- 5 // Peter Bakke

######################
# Question 1 | Anagram
######################

”’
Given two strings s and t, determine whether some anagram of t is a substring of s.
For example: if s = “udacity” and t = “ad”, then the function returns True. Your function definition
should look like: question1(s, t) and return a boolean True or False.
”’

def question1(s,t):

# Do edge tests

if type(s) != str:
return “>>>Error: s must be a string”

if type(t) != str:
return “>>>Error: t must be a string”

if len(t) == 0:
return “>>>Error: t must have at least 1 character”

if len(s) == 0 :
return “>>>Error: s must have at least 1 character”

# Remove any single or multiple spaces in s and t
s = “”.join(s.split())
t = “”.join(t.split())

if len(s) < len(t):
return “>>>Error: t must have equal or fewer characters (excluding spaces) than s”

# Sort the strings
s_sorted = sorted(s.lower())
t_sorted = sorted(t.lower())

if s_sorted == t_sorted: # if true, then exact length anagram match
return True
else:

len_t = len(t)
count = 0
for i in range(0, len(t)):

find = t[i]
if find in s:
s = s.replace(t[i], “”) # remove all chars from s to solve issue of duplicate chars in s
count += 1

if count == len_t:
return True
else:
return False

def test1():

# Some edge test cases:
print “######################”
print “# Question 1 | Anagram”
print “######################”,’\n’

s = 123
t = ‘ad’
print “s = number… Expect Error: s not a string:”
print question1(s,t),’\n’

s = ‘Udacity’
t = 123
print “t = number… Expect Error: t not a string:”
print question1(s,t),’\n’

s = ”
t = ‘ad’
print “s is empty… Expect Error:”
print question1(s,t),’\n’

s = ‘Udacity’
t = ”
print “t is empty… Expect Error:”
print question1(s,t),’\n’

s = ‘Udacity’
t = ‘yticadux’
print “Expect Error: t is longer than s:”
print question1(s,t),’\n’

# Valid input test cases:

s = ‘Udacity’
t = ‘ad’
print “s =”,s,”t =”,t,”…Expect True, short anagram quiz case:”
print question1(s,t),’\n’

s = ‘Udacity1’
t = ‘city1 dau’
print “s =”,s,”t =”,t,”…Expect True, space in ‘t’:”
print question1(s,t),’\n’

s = ‘Udacity’
t = ‘cityb’
print “s =”,s,”t =”,t,”…Expect False:”
print question1(s,t),’\n’

s = ‘Udacity’
t = ‘uu’
print “s =”,s,”t =”,t,”…Expect False:”
print question1(s,t),’\n’

s = ‘Doctor Who’
t = ‘Torchwood’
print “s =”,s,”t =”,t,”…Expect True, full length anagram with 2 spaces in ‘s’:”
print question1(s,t),’\n’

#########################
# Question 2 | Palindrome
#########################

”’Given a string a, find the longest palindromic substring contained in a.
Your function definition should look like question2(a…), and return a string.
”’

# Function twice called from below to expand through string,looking for palins
# Called for both odd and even palin searches. Note that palins can be even and odd numbered in length.
# Recall that ‘aba’ (len of 3) is a palin. Single letters, the ‘odd’ letter, in that case, ‘b’, are palins, too.
def search_palin(s,len_s,low,hi,start,maxLenFound):

# expand outward from hi,low indexes as long as chars match and stay within string’s boundries.
while low >= 0 and hi < len_s and s[low] == s[hi] :
if hi – low + 1 > maxLenFound:
# found a longer palin
# var ‘start’ saves low index which equals start of palin stretching forwrd for maxLenFound chars
start = low
maxLenFound = hi – low + 1 # set the max len of the current palin
low -= 1 # Move left one char in the string
hi += 1 # Move right one char in the string
return (start, maxLenFound)

# Find the longest palindromic substring. It can even or odd in length.
def question2(s):

if type(s) != str:
return “>>>Error: Input is not a string”

len_s = len(s)

if len_s == 0:
return “>>>Error: Input string is empty”

if len_s < 2:
return s

maxLenFound = 1
start = 0
len_s = len(s)

# Loop through string one char at atime, searching for palins
for i in range(1, len_s):

# Do ‘even’ palin processing: Find the longest even length palin using starting indexes of ‘i-1’ and ‘i’.
# We are using an iter of ‘i’ = 1 with zero indexing, so we are not going to exceed lower bound.
low = i – 1
hi = i
start,maxLenFound = search_palin(s,len_s,low,hi,start,maxLenFound)

# There may also be odd-numbered palins in the string: Do ‘odd’ palin processing.
# Search for any odd length palindromes with a center point of ‘i’ that are longer than we may have found
# in the ‘even’ search above.
# Start the indexes on either side of ‘i’. Since we set the loop iter ‘i’ to 1 and we are using 0 indexing,
# we are fine and will not violate the lower bound. Proceed for search as above in the ‘even’ processing
low = i – 1
hi = i + 1
start,maxLenFound = search_palin(s,len_s,low,hi,start,maxLenFound)

return s[start:start + maxLenFound]

def test2():

print “#########################”
print “# Question 2 | Palindrome”
print “#########################\n\n”

print “Test case 10101 (expect error: not a string):\n”, question2(10101)
print “\nTest case ” (expect error: an empty string):\n”, question2(“”)
print “\nTest single char ‘a’ (expect ‘a’):\n”, question2(“ab”)
print “\nTest two char ‘bb’ (expect ‘bb’):\n”, question2(“bb”)
print “\nTest no conventional palin in the string. Return first char of string : ‘abcd’ (expect: ‘a’):\n”, question2(“abcd”)
print “\nTest for odd numbered palindrome ‘radararadar’ (expect ‘radararadar’):\n”, question2(“radararadar”)
print “\nTest for two palins in string, one even, other odd, and where odd-length palin is longer ‘aabbb’ (expect: ‘bbb’):\n”,question2(“aabbb”)

##################
# Question 3 | MST
##################

import Queue as Q
import pprint
from collections import defaultdict

”’Given an undirected graph G, find the minimum spanning tree within G. A minimum spanning tree connects
all vertices in a graph with the smallest possible total weight of edges. Your function should take in
and return an adjacency list structured like this:

{‘A’: [(‘B’, 2)],
‘B’: [(‘A’, 2), (‘C’, 5)],
‘C’: [(‘B’, 5)]}

Vertices are represented as unique strings. The function definition should be question3(G)

”’

class Node(object):
def __init__(self, value):
# ‘Name’ of node
self.value = value
self.edges = []

class Edge(object):
def __init__(self, value, node_from, node_to):
# Value = ‘Weight’
self.value = value
self.node_from = node_from
self.node_to = node_to

class Graph(object):
def __init__(self, nodes=[], edges=[]):
self.nodes = nodes
self.edges = edges

def insert_node(self, new_node_val):
new_node = Node(new_node_val)
self.nodes.append(new_node)

def insert_edge(self, new_edge_val, node_from_val, node_to_val):

# New code: Don’t insert B,A if A,B already in the graph
dup = False
for edge_object in self.edges:

if ((edge_object.node_from.value == node_to_val) and (edge_object.node_to.value == node_from_val)) or (edge_object.node_from.value == node_from_val) and (edge_object.node_to.value == node_to_val):
dup = True
break

if dup == False: # No duplicate found, insert this edge into graph
from_found = None
to_found = None
for node in self.nodes:
if node_from_val == node.value:
from_found = node
if node_to_val == node.value:
to_found = node
if from_found == None:
from_found = Node(node_from_val)
self.nodes.append(from_found)
if to_found == None:
to_found = Node(node_to_val)
self.nodes.append(to_found)
new_edge = Edge(new_edge_val, from_found, to_found)
from_found.edges.append(new_edge)
to_found.edges.append(new_edge)
self.edges.append(new_edge)

def get_edge_list(self):
e_list = []
for e_object in self.edges:
e = (e_object.value, e_object.node_from.value, e_object.node_to.value)
e_list.append(e)
return e_list

# For use in pushing and popping edges to/from a PriorityQueue
class edge_q_entry(object):
def __init__(self, weight, nodes_in):
self.weight = weight
self.nodes = nodes_in

# I tried to remove the following, but it is needed in Py versions < 3
def __cmp__(self, other):
return cmp(self.weight, other.weight)

###################
### Question 3 main
###################

def question3(G):

if type(G) != dict:
return “>>>Error: Input must be a dict.”

if len(G) <= 1:
return “>>>Error: Input needs more than 1 vertex”

# Insert edges into graph from input adjacency matrix … weight, node1, node2
graph = Graph()

for key in G:
for each in G[key]:
graph.insert_edge(each[1], key, each[0])

edge_q = Q.PriorityQueue()

edge_list = graph.get_edge_list()

# Create edge priority queue
for edg in edge_list:
# break edge string into edge weight edg[0] and edge nodes ie edg[1:]
# and push into the priority queue
edge_q.put(edge_q_entry(edg[0], edg[1:]))

vertex_set = set(edge_list)

MST = []

vertex_set = [set(node) for node in G.keys()]

# loop through edges until MST created
for edg in edge_list:

edg = edge_q.get() # pop the PriorityQueue which will have the next edge with a minimum weight

# Get current indexes in vertex_set of both nodes for this edge:
# Note that len(vertex_set) changes as nodes are placed in MST
for index in range(len(vertex_set)):
if edg.nodes[0] in vertex_set[index]:
index1 = index
if edg.nodes[1] in vertex_set[index]:
index2 = index

# Store the union of node subsets into the smaller node subset and remove the larger node subset
# e.g., [(set[‘A’, ‘B’]), set([‘C’, ‘D’])] becomes [(set[‘A’, ‘B’, ‘C’, ‘D’])]
# Store the edge in MST.
if index1 < index2:
vertex_set[index1] = set.union(vertex_set[index1], vertex_set[index2])
vertex_set.pop(index2) # Often one of the indexes is not in the list, so use set.pop instead of set.remove
MST.append(edg)
if index1 > index2:
vertex_set[index2] = set.union(vertex_set[index1], vertex_set[index2])
vertex_set.pop(index1)
MST.append(edg)

# Exit early when all vertices are in MST. Vertex sets reduced from n sets to 1 final set (= MST)
if len(vertex_set) == 1:
break

#
# End process MST
#

# Create the output graph matrix from the MST

graph_matrix = {}
for edge in MST:

# Append A,B
if edge.nodes[0] in graph_matrix:
graph_matrix[edge.nodes[0]].append((edge.nodes[1], edge.weight))
else:
graph_matrix[edge.nodes[0]] = [(edge.nodes[1], edge.weight)]

# Also append B,A when necessary
if edge.nodes[1] in graph_matrix:
graph_matrix[edge.nodes[1]].append((edge.nodes[0], edge.weight))
else:
graph_matrix[edge.nodes[1]] = [(edge.nodes[0], edge.weight)]

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(graph_matrix)

def test3():

pp = pprint.PrettyPrinter(indent=4)

print “\n##################”
print “# Question 3 | MST”
print “##################\n\n”

print “Test for input is not a dictionary: Expecting an error msg here: ”
print question3(123),’\n\n’

print “Test for input of an empty dictionary: Expecting an error msg here: ”
print question3({}),’\n\n’

D = {‘A’: [(‘B’, 2)],
‘B’: [(‘A’, 2), (‘C’, 5)],
‘C’: [(‘B’, 5)]}

print “Test the quiz case. Expecting: ”
pp.pprint(D),’\n\n’

print “\nAnswer:\n”
question3(D)

N = {‘A’: [(‘B’, 2), (‘D’, 5)],
‘B’: [(‘A’, 2)],
‘C’: [(‘D’, 3), (‘E’, 5)],
‘D’: [(‘C’, 3), (‘A’, 5)],
‘E’: [(‘F’, 2), (‘C’, 5)],
‘F’: [(‘E’, 2)]}

print “\n\nTest non-trivial case. Expecting: ”
pp.pprint(N),’\n\n’

print “\nAnswer:\n”

question3(N)

##################
# Question 4 | LCA
##################

”’
Find the least common ancestor between two nodes on a binary search tree.
The least common ancestor is the farthest node from the root that is an ancestor of both nodes.
For example, the root is a common ancestor of all nodes on the tree, but if both nodes are descendents
of the root’s left child, then that left child might be the lowest common ancestor. You can assume that
both nodes are in the tree, and the tree itself adheres to all BST properties. The function definition
should look like question4(T, r, n1, n2), where T is the tree represented as a matrix, where the index
of the list is equal to the integer stored in that node and a 1 represents a child node, r is a non-negative
integer representing the root, and n1 and n2 are non-negative integers representing the two nodes
in no particular order. For example, one test case might be

question4([[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]],
3,
1,
4)
and the answer would be 3.

”’
# Define Binary Node class
class BNode(object):

def __init__(self, value):
self.value = value
self.left = None
self.right = None

# Define Binary Search Tree class
class BST(object):

def __init__(self, root):
self.root = BNode(root)

def insert(self, new_val): # From Udacity class
self.insert_helper(self.root, new_val)

def insert_helper(self, node, new_val): # From Udacity class
if node.value != new_val: # If same as an entry already in BST, skip

if new_val > node.value:
if node.right:
self.insert_helper(node.right, new_val)
else:
node.right = BNode(new_val)
else:
if node.left:
self.insert_helper(node.left, new_val)
else:
node.left = BNode(new_val)

def search(self, find_val):
return self.search_helper(self.root, find_val)

def search_helper(self, current, find_val):
if current:
if current.value == find_val:
return True
elif current.value < find_val:
return self.search_helper(current.right, find_val)
else:
return self.search_helper(current.left, find_val)
return False

#########
# Step 1 Create BST from input matrix
# Step 2 Validate inputs
# Step 3 Find LCA
#########

def question4(T,r,n1,n2):

# Check if matrix T is well-formed and represents a valid BST. Are other inputs valid and in bounds?
# Is T an n x n matrix and does each row have a max of two 1’s, i.e. sum of each row = 0 | 1 | 2.

error = False
error_msg = ”

# Determine if r, n1 & n2 are integers
if type(n1) != int:
error = True
error_msg = ‘>>>ERROR: node 1 is not an integer… value = {0}’.format(n1)
elif type(n2) != int:
error = True
error_msg = ‘>>>ERROR: node 2 is not an integer… value = {0}’.format(n2)
elif type(r) != int:
error = True
error_msg = ‘>>>ERROR: root is not an integer… value = {0}’.format(r)
# is r within range of matrix?
elif (r < 0) or (r > len(T)-1):
error = True
error_msg = ‘>>>ERROR: root out of range… value = {0}’.format(r)
else:
# Check for my definition of well-formed T, which = n x n matrix
for i in range(len(T)): # By row
# Check for n x n . If ANY rows are longeror shorter, error and quit
if (len(T[i]) != len(T)) :
error = True
error_msg = ‘Row ‘,i,’indicates not a n x n matrix’
# and check that sum of T inner arrays <= 2, ie only 2 children allowed
elif (sum(T[i]) > 2):
error = 1
error_msg = ‘Row ‘,i,’indicates more than 2 children’

if error == False: # Continue, n1 & n2 are int() AND tree is well formed

root = T[r]

# Create an instance of binary search tree
tree = BST(r)

# Create Btree from matrix:
# First, process the root from the matrix T
for j in range(len(T)): # Loop thru items in root row
if T[r][j] == 1:
#print “……………insert”,j
tree.insert(j) # insert the value into the BST

# Process all other matrix rows, skipping root done above
for i in range(len(T)):
if i == r: # Skip root row, already processed
continue
else:
for j in range(len(T)): # Loop thru items in row
#print “j:”, j, “…value:”, T[i][j]
if T[i][j] == 1:
#print “……………insert”,j
tree.insert(j) # insert the value into the BST

# Determine if n1 & n2 are in the tree
if tree.search(n1) == False:
error = True
error_msg = ‘>>>ERROR: n1 not in BST… value = {0}’.format(n1)
else:
if tree.search(n2) == False:
error = True
error_msg = ‘>>>ERROR: n2 not in BST… value = {0}’.format(n2)

#
# No validation or edge errors, OK to find LCA
#
if error == False:

# Start with the root. We know from above tests that T is well formed and
# that both n1 and n2 are integers in the BTree
node = tree.root
while node.left != None or node.right != None: # We still have a path

# if both vales are less than the current node, we go to the left
if node.value > n1 and node.value > n2:
node = node.left

# if both vales are greater than the current node, we go to the right
elif node.value < n1 and node.value < n2:
node = node.right

# we find the answer, return it
else:
return node.value

else:
return error_msg # at least one n is not in tree
else:
return error_msg # Tree format error or other input error

def test4():

print “\n\n##################”
print “# Question 4 | LCA”
print “##################\n”

print “# Format = question4(T,r,n1,n1)\n# Where:\n# T = ancestry matrix, r = root, n1 & n2 = comparison nodes\n\n”

# Quiz case:

T =[[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]

”’
Root = 3

3
/ \
0 4
\
1

”’

print ‘Edge cases: \n’
print ‘Expect error for root not an integer: question4(T,1.1111,0,4):\n’, question4(T,1.1111,0,4), ‘\n’
print ‘Expect error for root not in BST: question4(T,14,0,4):\n’, question4(T,14,0,4), ‘\n’
print ‘Expect error for node 1 not in BST: question4(T,3,22,4):\n’, question4(T,3,22,4), ‘\n’
print ‘Expect error for node 2 not in BST: question4(T,3,0,32):\n’, question4(T,3,0,32), ‘\n\n’

print “T =[[0, 1, 0, 0, 0], \n”
print ” [0, 0, 0, 0, 0],\n”
print ” [0, 0, 0, 0, 0],\n”
print ” [1, 0, 0, 0, 1],\n”
print ” [0, 0, 0, 0, 0]]\n”

print ‘\n Root = 3\n\n’
print ‘ 3\n’
print ‘ / \ \n’
print ‘ 0 4\n’
print ‘ \ \n’
print ‘ 1 \n’

print ‘Quiz case: Expect correct answer of 3 for question4(T,3,1,4):\n’, question4(T,3,1,4), ‘\n’
print ‘Quiz case: Expect correct answer of 0 for question4(T,3,0,1):\n’, question4(T,3,0,1), ‘\n’

##########################
# Question 5 | Linked List
##########################

”’Find the element in a singly linked list that’s m elements from the end. For example,
if a linked list has 5 elements, the 3rd element from the end is the 3rd element.
The function definition should look like question5(ll, m), where ll is the first node of a linked list
and m is the “mth number from the end”. You should copy/paste the Node class below to use as a
representation of a node in the linked list. Return the value of the node at that position.

class Nodell(object):
def __init__(self, data):
self.data = data
self.next = None
”’

class Node_ll(object):

def __init__(self, value):
self.value = value
self.next = None

class LinkedList(object):

def __init__(self, head=None):
self.head = head # Init head node to None

def append(self, new_element):
# Start at the head
current = self.head
# does the head have a pointer in it?
if self.head:
# Yes, move thru linked list
while current.next:
current = current.next

# Got to the end of the singly linked list, ie current.next = None
current.next = new_element
else:
# No, just set the head value
self.head = new_element

def circular_check(self, head):

# Start at head
node1 = head
node2 = head

while node2 != None:

#print “\n——n1:”,node1.next.value,”n2:”,node2.next.value

node1 = node1.next

#print “++n1:”,node1.next.value,”n2:”,node2.next.value

if node2.next != None:
node2 = node2.next.next
#print “……. n1:”,node1.next.value,”n2:”,node2.next.value
else:
return False

if node1 is node2:
return True

return False

def get_length(self,lst):

if self.circular_check(lst) == True:
return “Linked List is circular”

r = 1
# Start at the head
current = self.head
# does the head have a pointer in it?
if self.head:
# Yes, move thru linked list
while current.next:
current = current.next
r += 1

else:
# No, just set the head value
self.head = new_element

return r # ‘r’ being the length

def question5(llist, m):

error = ”

# Is m an integer?
if type(m) != int:
error = “>>> ERROR: m = ” + str(m) + ” … is not an integer.”
return error

# Do we have a Linked List?
if type(llist) != LinkedList:
error = “>>> ERROR: The input list is not a linked list”
return error

# is the linked list circular?
if llist.circular_check(llist.head) == True:
error = “>>> ERROR: The linked list is circular”
return error

# get the length of ll
length = llist.get_length(llist.head)

# Check boundry conditions
if m <= 0 :
error = “>>> ERROR: m = ” + str(m) + ” … m must be greater than 0″
return error
elif m >= length:
error = “>>> ERROR: m = ” + str(m) + ” … m must be less than the length of the linked (list – 1) = ” + str(length-1)
return error

# Get the m’th element from end of ll
current = llist.head

for i in range(length – m):
#print current.value
current = current.next

return current.value

# Testing
def test5():

print “##########################”
print “# Question 5 | Linked List”
print “##########################\n\n”

# Test case
# Set up some Elements
n1 = Node_ll(1)
n2 = Node_ll(2)
n3 = Node_ll(3)
n4 = Node_ll(4)
n5 = Node_ll(5)

# Set up the Linked List
ll = LinkedList(n1)

ll.append(n2)
ll.append(n3)
ll.append(n4)
ll.append(n5)

print “question5(ll, 1.1) should generate error, ‘m is not an integer’.\n'”, question5(ll, 1.1), “‘\n”

print “question5(123, 4) should generate error, ‘the input list is not a node-based linked list’.\n'”, question5(123, 4), “‘\n”

print “question5(ll, 0) should generate error, m out of bounds.\n'”, question5(ll, 0), “‘\n”

print “question5(ll, 5) should generate error, m out of bounds.\n'”, question5(ll, 5), “‘\n”

print “question5(ll, 4) should successully return result of 2 :\n”, question5(ll, 4), “\n”

# Test for Circular LL… point last node to first node to create circular linked List
# Error msg should be printed indicating circular list.
n5.next = n1
print “question5(ll, 4) after linking n5 to n1, function should generate error, ‘The linked list is circular’:\n”, question5(ll, 4), “\n”

if __name__ == “__main__”:
test1()
test2()
test3()
test4()
test5()

# In[ ]:

Books

I carry within me these shards and fragments of memories

Posted on

“I carry within me these shards and fragments of memories, some of which I would like to forget. These pieces of a life are finally incomprehensible. We are not the sum of events, although those on the outside sometimes use events to define us. We are not our titles or positions or accomplishments. We are distinct from these. We puzzle over ourselves as time, with its ruthless and swift gait, sweeps our lives into the past. The lives that went before mine, the lives that will come after mine, seem sometimes to merge, bound together by common rituals, the physical and spiritual wanderings that come with human existence and the strangeness of it all.”

— Chris Hedges, Losing Moses on the Freeway

losing moses on the freeway - Peter Bakke