# HW 8

Ivan Christian

# 1

public static void foo()
{
    float yesterday =readNumber()
    float today = readNumber()
        
    if (yesterday > today)
    {
        // debug here
        doSomething1();
    }
    
    else
    {
        if (yesterday != today)
        {
            // debug here
            doSomething2();
        }
        else
        {
            // debug here
            dosomething3();
        }
    }
} 

For statement coverage, all the statements are covered if the debug is done at each junction of the if statement.

If we know that the 1st branch is visited more often than the 2nd and the 2nd more often than the 3rd branch, then 2 statements are enough. This is because if no debug is generated, 1st branch is assumed to be run without issues. This will reduce the overhead as by process of elimination we know what is being checked. Any lower number of debug checks will not cover all the statements

public static void foo()
{
    float yesterday = readNumber();
    float today = readNumber();
        
    if (yesterday > today)
    {
        // debug here
        doSomething1();
    }
    
    else
    {
        if (yesterday != today)
        {
            
            doSomething2();
        }
        else
        {
            // debug here
            dosomething3();
        }
    }
} 

# 2

from numpy.random import randint
from numpy.random import rand

import string
import random

# objective function
def palindrome_fitness(x):
	score = 0
	midpoint = int(len(x)/2)
	left_side = x[:midpoint]
	right_side = x[midpoint:]
	for i in range(midpoint):
		if left_side[::-1][i] == right_side[i]:
			score -= 1
	return score

# tournament selection
def selection(pop, scores, k=3):
	# first random selection
	selection_ix = randint(len(pop))
	# creates 2 random integer and compare the scores of the 3
	for ix in randint(0, len(pop), k-1):
		# check if better (e.g. perform a tournament)
		if scores[ix] < scores[selection_ix]:
			selection_ix = ix
	return pop[selection_ix]
 
# crossover two parents to create two children
def crossover(p1, p2, r_cross):
	# children are copies of parents by default
	c1, c2 = p1, p2
	# check for recombination
	if rand() < r_cross:
		# select crossover point that is not on the end of the string
		pt = randint(1, len(p1)-2)
		# perform crossover
		c1 = p1[:pt] + p2[pt:]
		c2 = p2[:pt] + p1[pt:]
	return [c1, c2]
 
# mutation operator
def mutation_char(charstring, r_mut):
	mutated_char = ""
	for i in range(len(charstring)):
		# check for a mutation
		if rand() < r_mut:
			mutated_char += random.choice(char_space)
		else:
			mutated_char += charstring[i]
	return mutated_char

# function to generate random string of characters
def generate_char(n_bits):
	gen_char = ''
	for i in range(n_bits):
		gen_char += random.choice(char_space)
	return gen_char
 
# genetic algorithm
def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):
	# initial population of random character strings
	pop = [generate_char(n_bits) for _ in range(n_pop)]
	# keep track of best solution
	best, best_eval = 0, objective(pop[0])
	# enumerate generations
	for gen in range(n_iter):
		# evaluate all candidates in the population
		scores = [objective(c) for c in pop]
		#print(f"scores at iteration {gen}: {scores}")
		# check for new best solution
		for i in range(n_pop):
			if scores[i] < best_eval:
				best, best_eval = pop[i], scores[i]
				print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))
		# select parents from the random selection function
		selected = [selection(pop, scores) for _ in range(n_pop)]
		# create the next generation
		children = list()
		for i in range(0, n_pop, 2):
			# get selected parents in pairs
			p1, p2 = selected[i], selected[i+1]
			# crossover and mutation
			for c in crossover(p1, p2, r_cross):
				# mutation
				c = mutation_char(c, r_mut)
				# store for next generation
				children.append(c)
		# replace population
		pop = children
	return [best, best_eval]

char_space = string.ascii_lowercase 
# define the total iterations
n_iter = 200
# bits
n_bits = 64
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / float(n_bits)
# perform the genetic algorithm search
best, score = genetic_algorithm(palindrome_fitness, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
print('f(%s) = %f' % (best, score))

Result

>0, new best f(slprdyiqiuozyygvojxvqwlutqcqelknwfhvaclnykzbnlmensfdnqlpppxmruwz) = -2.000
>0, new best f(jkywbbanggkfscfrpqdbojmctkzwmxphhazthrxjaqzsqdlzriehdrzygggdslni) = -3.000
>0, new best f(qiqcixsehoyhczyhlksnuwnrsbmhpsgacxwuhavlmpwizakomvyrwvzduvcawqtw) = -4.000
>1, new best f(xvgnfvokaybpvwvdyuauulfllmyhubgilmcaxkalleljjmrzdgvcjskaanogmdrv) = -5.000
>2, new best f(irzyzdbiwcndznixzljhmkuhhifullrtvlslfdhuenzsqdlzrieydrzygggdslni) = -6.000
>9, new best f(jtmoaieucledgiqvamcdmbdlmbfuoixhlelswfsmarzmdaeakmiwgpbieglblutg) = -7.000
>10, new best f(jtmoaieucledgiqvamcdmbdmvoaszqhjfyfasywqndbmdaeakmiwvpbieglblutg) = -8.000
>12, new best f(jtmoajqewlekgiqvamcdmbdmvoaszqhjfyfasywqndbmdaeakmiwvpbieglblutg) = -9.000
>14, new best f(btulpjmewueogiqvamcdmydddocqelkcwphvqclnyqwmdtuakmiwgpbieglblutg) = -10.000
>14, new best f(btuebjqewqbhbiqvamcdmyddvooszqhjfyqasywqndbmdaeakmiwrpbieglbjutg) = -11.000
>16, new best f(btuepjqewsengiquamcdmqddvoaszqhjfyqascuqddbmdaeakmiwrpbieglpjutg) = -12.000
>18, new best f(btulpjmegbkdwiquamcdmyddvooszqhjfwqasywqndbmdaeakmiwgpbieglblutg) = -13.000
>19, new best f(btulpjqegbkdwiqvamcdmbdkvooszqhjfyqasywqndbmdaeakmiwgpbieglblutg) = -14.000
>21, new best f(btulpjqegbkdwiqvamcdmbddvoaszqhjfhqmsywqndbmdaeakbiwrpbieglblutg) = -15.000
>23, new best f(btulpjmegbkdwiqvamcdmbddvooszqhjfyqzseubddbmdtuakbiwwpbieglblutg) = -16.000
>24, new best f(btulpnmegbkdwiqvamcdmbddvooszqhjfyqzscuqddbmdteakmiwgpbiemlblutg) = -17.000
>28, new best f(ftulpjmegbkdwiqvaucdmbddvooszqhjfyqzschbddbmdtuakmiwrpbiemlblutg) = -18.000
>31, new best f(btulpjmegbkdwiqvaucdmbddvuoszqmjuyqzscuqddbmdtuakbiwwpbiemlblutg) = -19.000
>35, new best f(btulylsegbkdwixvaucdmbddvuoszqmjuyqzsruqddbmdtuakniwdpbieglrlutj) = -20.000
>38, new best f(btulylgegbkdwiqvaucdmbddvtoszqhjuqqzschbddbmdcuakniwdpbieglrlutj) = -21.000
>40, new best f(utulylgegbkdwikvaucdmbddbuoszqhjfyqzscubddbmdtuakniwdpbieglrluta) = -22.000
>42, new best f(utulylgegbkdwikvaucdmbddbuoszqhjfyqzscubddbmdtuakniwdpbgeglrluta) = -23.000
>46, new best f(btulylgegbpdwiqvaucdmbddbuoszqhjfyqzscubddbmdeuakniwdpbgeglrlutj) = -24.000
>52, new best f(btulylgegbpdwiqvaucdmbddbuoszqqjfqqzstubddbmdsuakhiwdpbgeglrlutj) = -25.000
>56, new best f(btulylgegbpdwiqvaucdmbddbuaszqqjfqqzstubddbmdsuakhiwdpbgeglrlutb) = -26.000
>59, new best f(btulylgegbpdwikpaucdmbddbucszqhjfyqzscubddbmdcuakoiwdpbgeglrlutb) = -27.000
>64, new best f(btulylgegbpdwiqpaucdmbddbucszqhjfyqzscubddbmdcuapoiwdpbgeglrlutb) = -28.000
>75, new best f(btulylgegbpdwiqvaucdmbddbucszqqqqqqzscubddbmdcuakhiwdpbgeglrlutb) = -29.000
>87, new best f(btultlgegbpdwitpaucdmbddbucszqqqqqqzscubddbmdcuakoiwdpbgegltlutb) = -30.000
>88, new best f(btultlgegbpdwihpaucdmbddbucszqqqqqqzscubddbmdcuavhiwdpbgegltlutb) = -31.000
>105, new best f(btultlgegbpdwiokaucdmbddbucszqqqqqqzscubddbmdcuakoiwdpbgegltlutb) = -32.000
Done!
f(btultlgegbpdwiokaucdmbddbucszqqqqqqzscubddbmdcuakoiwdpbgegltlutb) = -32.000000

In order to get the fitness function for a palindrome, we need to make sure that the end goal is to get the firsthalf (index 0 until midpoint) the same as the reversed secondhalf (midpoint to end) substring. the maxFitness score that we want is -32 (since if each element in the first and secondhalf substrings are the same then the maxFitness score would be half of 64).

# 3

from numpy.random import randint
from numpy.random import rand

import string
import random

desired_url = "http://www.ietf.org/rfc/rfc1738.txt"

# objective function
def URL_fitness(x, target = desired_url):
	score = 0
	for i in range(len(x)):
		score += abs(ord(x[i]) - ord(target[i]))
	return score

# tournament selection
def selection(pop, scores, k=3):
	# first random selection
	selection_ix = randint(len(pop))
	# creates 2 random integer and compare the scores of the 3
	for ix in randint(0, len(pop), k-1):
		# check if better (e.g. perform a tournament)
		if scores[ix] < scores[selection_ix]:
			selection_ix = ix
	return pop[selection_ix]
 
# crossover two parents to create two children
def crossover(p1, p2, r_cross):
	# children are copies of parents by default
	c1, c2 = p1, p2
	# check for recombination
	if rand() < r_cross:
		# select crossover point that is not on the end of the string
		pt = randint(1, len(p1)-2)
		# perform crossover
		c1 = p1[:pt] + p2[pt:]
		c2 = p2[:pt] + p1[pt:]
	return [c1, c2]
 
# mutation operator
def mutation_char(charstring, r_mut):
	mutated_char = ""
	for i in range(len(charstring)):
		# check for a mutation
		if rand() < r_mut:
			mutated_char += random.choice(char_space)
		else:
			mutated_char += charstring[i]
	return mutated_char

# function to generate random string of characters
def generate_char(n_bits):
	gen_char = ''
	for i in range(n_bits):
		gen_char += random.choice(char_space)
	return gen_char
 
# genetic algorithm
def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut):
	# initial population of random character strings
	pop = [generate_char(n_bits) for _ in range(n_pop)]
	# keep track of best solution
	best, best_eval = 0, objective(pop[0])
	# enumerate generations
	for gen in range(n_iter):
		# evaluate all candidates in the population
		scores = [objective(c) for c in pop]
		#print(f"scores at iteration {gen}: {scores}")
		# check for new best solution
		for i in range(n_pop):
			if scores[i] < best_eval:
				best, best_eval = pop[i], scores[i]
				print(">%d, new best f(%s) = %.3f" % (gen,  pop[i], scores[i]))
		# select parents from the random selection function
		selected = [selection(pop, scores) for _ in range(n_pop)]
		# create the next generation
		children = list()
		for i in range(0, n_pop, 2):
			# get selected parents in pairs
			p1, p2 = selected[i], selected[i+1]
			# crossover and mutation
			for c in crossover(p1, p2, r_cross):
				# mutation
				c = mutation_char(c, r_mut)
				# store for next generation
				children.append(c)
		# replace population
		pop = children
	return [best, best_eval]

char_space = string.ascii_lowercase + string.digits + string.punctuation
# define the total iterations
n_iter = 500
# bits
n_bits = len(desired_url)
# define the population size
n_pop = 1000
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / float(n_bits)
# perform the genetic algorithm search
best, score = genetic_algorithm(URL_fitness, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
print('f(%s) = %f' % (best, score))

Results

>0, new best f(g.jt_/!$/>-@5c<'%+)%oc%+4xj<q9:z[)i) = 1148.000
>0, new best f(?l{\#?!1&+]"\{s^u%z\+$0|ylwh=!;/[ox) = 1117.000
>0, new best f(abwo=])?sc<h#?-{2)1,{!v!~fq:&$&3l/#) = 986.000
>0, new best f(~(nc8"4~@@|_7~1;szi1n;8`%up,$j~1nz$) = 964.000
>0, new best f(;^8b%ny~~`ytbad&{k~8}(j$j_xhe][}zxt) = 895.000
>0, new best f(a}wf@4&^1w|zf(s'!8o<xrp+)g2]=#*8nij) = 772.000
>1, new best f(\\{}%\=e~n(}jyl+8kb[<4|>~x`@kda19^r) = 750.000
>1, new best f(\\{}%g=e~n(}jyl+8k]m{>w?(>?(}:22}ze) = 717.000
>2, new best f(]qyt0+'<y1h8fzv8en\/zhbzk_~;r('#>~<) = 692.000
>2, new best f(gine])-?qb,~5}j`?xn~{~$*~]g.90>;gd:) = 673.000
>2, new best f(\\{}%g=e~n(}jyl+8k]m{>u,d6b]/a!.ujc) = 646.000
>3, new best f(\\{}%g=e~n(}jyl+8k]m{nu,d]']/a!.ujc) = 634.000
>3, new best f(gine])-?qb,~2qcfjh@%h=`-m<l-g+h.igu) = 604.000
>3, new best f(k1yw.."'`b,t{d]_yil[\]c/w\d-^+6-re<) = 587.000
>3, new best f(]qyt0+'<y1h8fzv,en\/zhbzku6183@#pnm) = 527.000
>4, new best f(\\{}%\=e~n(.jyv,en\/ohbzku6183@#pnm) = 477.000
>5, new best f(]ryt0+:?qw8y~szpiqg?\gk.yt6190>;gdx) = 429.000
>6, new best f(i{pf-/-ow|:g`~{-iqg?\gk.ytzh_'*1e^r) = 367.000
>8, new best f(]qyt5+-rvo&bg~;"vzr%}nl?sd6190);gdx) = 328.000
>8, new best f(gunt5+-rzo.bg~b3rn\/w%s7vnl-86]1e^r) = 291.000
>8, new best f(]qyt5+-rzn(}jyl+8kd4sv]4{ad\:/68hwx) = 288.000
>9, new best f(giny5+-rzo.bg~b3ri{0y^j!rud/86]?e^r) = 270.000
>9, new best f(qxat0/=ryn(`gwl+kk34sv]4imh(:/68hwx) = 267.000
>9, new best f(gint5+-rzo.ba~b>ri{0y^j7nnh'86?;urc) = 228.000
>10, new best f(giny5+-rzo.bg~b3ri{0y^j!rgd/9<>;urc) = 209.000
>13, new best f(_pkv;'&qvo.bg~b,rnf2jqi7nnl-.+>;hwx) = 208.000
>13, new best f(zvjj;'&s|u(}jyl<iqg/zhb"if`%907+k{u) = 198.000
>14, new best f(_pkt5+-r~n(`gwb3rkd0y^j!rgd/9<>;urc) = 195.000
>15, new best f(gunt5+-rzo._jyl)s|i'zh]7nn`-86?1e^r) = 194.000
>15, new best f(]unt5+-rz|._jyl)s|^/z^b!l_d-90>5urc) = 191.000
>15, new best f(cinv;'&qvo.bg~b,rqf2jr]4xsd-90>5ysx) = 181.000
>15, new best f(]unt5+1rzo._p{z-iqg4shb$vk^.9068hwx) = 176.000
>15, new best f(gq{m5+-rzn._jyl)snf2joi&w]i.64=8pxm) = 168.000
>15, new best f(]qyp5+-rvo/bf~b3rng3h_b4{ad9:/68hwx) = 165.000
>16, new best f(giyp5+-rvo/bf~b3rng3h_b4{ad9:/68hwx) = 163.000
>17, new best f(]unt5+-rzo._jyl-iqg4shb$vk^.9068hwx) = 154.000
>18, new best f(nupt5+-rvo/_jyl-iqg4shb$vk^.9068hwx) = 146.000
>19, new best f(gsny;+-rzo.bg~b,rqg3h_b4{ad99.7+k{u) = 143.000
>20, new best f(]ryt5+-r}n.bhwo-iqg7q`]7ne`-866(qwv) = 142.000
>20, new best f(dpyt5+-rvo+bg~b-iqg0zhi-nnh/:/65qwx) = 138.000
>21, new best f(]qyp5+-svo/bf~b3rni/zhb$vki.648/ixu) = 135.000
>22, new best f(guyt5.-rvr%bjyl)s|i.zhb0if`1907+hwx) = 134.000
>23, new best f(gqyt5+-ryy,g`yb,rsg5s]c4om^.9765ezy) = 133.000
>23, new best f(nukt>/-ow|.bgyl+iqg/qh]4xsd-836(qwx) = 124.000
>25, new best f(d|yt5+-ryy-g`~l)rqf/zhb4xjd-836(qwx) = 123.000
>25, new best f(gunt5+-svo/bf~b3rng3hg`4om^.648/nxu) = 122.000
>26, new best f(goyh5,/ryy,gfkb3rni/qhc-pf`-906,hwx) = 108.000
>28, new best f(iunm5+-svo/bfsb,rri/phb4xsd3936(qwx) = 106.000
>29, new best f(gsny;+-zzo,gfkb3rni/qhc-pf`-9/6(qwv) = 104.000
>29, new best f(gsnt1+-rzo.bgsb,rri/u`c/if`1648/ixu) = 100.000
>30, new best f(gs{t5+,ryy/g`sb2iqg0yhb/rfd/<568qwu) = 96.000
>31, new best f(gutt5+-zzo,gfkb3rni/qhc-pf`-<56-qwu) = 92.000
>33, new best f(hqyt5+-rzy,g`uc+ini/qhc-pf`18/8/ixu) = 89.000
>34, new best f(nutq5-/rvz/gpsb2iqg0yhb/rid.906'txu) = 87.000
>36, new best f(jqpt5+-ryy/g`sb3rri/qhc-pf`-<56-qwu) = 85.000
>36, new best f(guvt5+-rzy,g`ub+vqg/qhc-pf`-<56-qwu) = 83.000
>38, new best f(hqvt5+-rz|.bgyh-kqg4sgi/ofc1648/nxu) = 81.000
>38, new best f(guvt5+-rzy,g`ub+vrf/qhc)pf`1848/nxu) = 78.000
>40, new best f(gryq5-/rvx.kgwb,rqh/qhc4of`-<56-zwu) = 77.000
>41, new best f(hqqx8+-vyy/ggsb,rqf2qhc-pf`-456-qwu) = 74.000
>41, new best f(hqqx8+-vyy/ggwb3rrh/qhc-pf`1648/nxu) = 68.000
>44, new best f(gstt5,0{vx.kgwb,krf/qhc-pfc/947+qwx) = 63.000
>45, new best f(gstt5,0{vx.kgwb,krf/qhc-pfd.956-qwu) = 62.000
>47, new best f(jquo9+-rvt+kgwi-oqg2sgc/pfc1348/nxu) = 58.000
>49, new best f(jquo9+-rvt+kgwi-oqg2sgc/pfc1348-qwu) = 56.000
>49, new best f(iutt?+0vyy.igwi-oqg/qhb/rid3906.ywu) = 55.000
>51, new best f(gsvt9.-svx.kgsh,rrf0shc/pfc1348/zxu) = 50.000
>53, new best f(jquo9/-rvv+kfse,oqg/qgc-pfc-836/nxu) = 49.000
>54, new best f(jquo9/-rvv+kfse,oqg/qgc-pfc/646-qwu) = 46.000
>61, new best f(goto9+/svx/igse,org2sgc/pfd1348-qwu) = 44.000
>62, new best f(goto9+/svx/igse,org2sgc/pfd1348/txu) = 40.000
>64, new best f(jquo9/-yvx.kgse,org2qhb/rfd/959-txu) = 39.000
>66, new best f(jsto9.-svx.ggse,oqf/qhc-pfc1648.qwu) = 38.000
>70, new best f(gsto9+.vvx.gbsg-org2sgc/pfc1848-qwu) = 35.000
>70, new best f(gsto9+/vvx.kgsh-krg/qgc/rfd1648.qwu) = 33.000
>73, new best f(gsuo9/-rvv/igse,oqf/sgc/pfc1848-txu) = 31.000
>75, new best f(huto9./yvy/ggsh,rrg/qgc/pfc1848-txu) = 30.000
>76, new best f(jstp9/-svx.ifsb.org/qgc/rfd/647,txu) = 29.000
>78, new best f(gstp9/-svx.ifsb.org/qgc/rfd/647,txu) = 28.000
>79, new best f(huto9./uyw/igse,oqg0qhc/pfc1948.txs) = 26.000
>79, new best f(huto9./uyv/hgtg-oqg/qgc/pfc1848-txu) = 24.000
>84, new best f(gstp9/-svx.ifse-org0shc/rfc1648-txu) = 23.000
>92, new best f(gsto9//yvw.ggsg-org/ugc/rfc1848-txu) = 22.000
>93, new best f(gvtp9/-wvx.ifsg-org/qgc/ofc1848/txu) = 21.000
>95, new best f(huto9/-wvx.ifsg-org/qgc/ofc1648/txu) = 20.000
>95, new best f(guto9/-wvx.ifse.org/shc/qfc1648-txu) = 19.000
>96, new best f(gutp8/0vvw.igse.org/qgc/rfc1848-txu) = 17.000
>111, new best f(gstp9./vvw.igsg.org/sgc/rfc1848-txu) = 16.000
>111, new best f(gutp8//vvw.ifse.org/sgc/rfc1848-txu) = 15.000
>126, new best f(hutp9//wvx.ifsg-org/qgc/rfc1848.txu) = 13.000
>142, new best f(futp9//wvw.iesg-org/qgc/rfc1638.txu) = 12.000
>152, new best f(hstp9//wvw.iesg-org/qgc/rfc1848/txt) = 11.000
>164, new best f(hutp9//wvw.iesg-org/sgc/rfc1838/txt) = 10.000
>172, new best f(http9//wvw.iesg-org/sgc/rfc1838.txt) = 8.000
>209, new best f(http9//wvw.iesg-org/qfc/rfc1838.txt) = 7.000
>229, new best f(http9//wvw.ietg-org/qfc/rfc1838.txt) = 6.000
>255, new best f(http9//wvw.ietf-org/sfc/rfc1838.txt) = 5.000
>263, new best f(http://wvw.ietf-org/sfc/rfc1838.txt) = 4.000
>287, new best f(http://wvw.ietf-org/qfc/rfc1738.txt) = 3.000
>294, new best f(http://wvw.ietf.org/sfc/rfc1738.txt) = 2.000
>308, new best f(http://www.ietf.org/rfc/rfc1838.txt) = 1.000
>373, new best f(http://www.ietf.org/rfc/rfc1738.txt) = 0.000
Done!
f(http://www.ietf.org/rfc/rfc1738.txt) = 0.000000