# Theory and Practice of Artificial Intelligence | My Assignment Tutor

Theory and Practice of Artificial IntelligenceRecursion, Examples and ExercisesDaniel PolaniSchool of Physics, Engineering and Computer ScienceUniversity of HertfordshireMarch 1, 2021All rights reserved. Permission is granted to copy and distribute these slides in full or in part for purposes ofresearch, education as well as private use, provided that author, affiliation and this notice is retained.Use as part of home- and coursework is only allowed with express permission by the responsible tutor and, inthis case, is to be appropriately referenced.Theory and Practice of Artificial Intelligence 20 / 142Exercise 2AssumptionsConsider the tower of Hanoiproblem with three poles andn disks.TaskWrite a function hanoi(.)that moves a tower of size nfrom a given start pole to atarget pole.Theory and Practice of Artificial Intelligence 21 / 142Exercise 3AssumptionsConsider the tower of Hanoiproblem with three poles andn disks.TaskWrite a function hanoi(.)that moves a tower of size nfrom a given start pole to atarget pole.Exampledef hanoi(n, start, goal, ignore):if n == 1:print start, “->”, goalreturnhanoi(n-1, start, ignore, goal)print start, “->”, goalhanoi(n-1, ignore, goal, start)hanoi(4, 1, 2, 3)Theory and Practice of Artificial Intelligence 21 / 142Stateful Functions” (Generators and Yields)Functions: information processing, then return resulta new call, new variables, new resultsGenerators: information processing, then yield resultnew call to generator retains old state andcontinues with new resultsExampledef colours():yield “red”yield “green”yield “black”for c in colours():print cExampledef colours():for c in [“red”,”green”,”black”]:yield cfor c in colours():print cTheory and Practice of Artificial Intelligence 22 / 142Exercise 4 (Permutation)AssumptionsConsider a list […]of elements.TaskWrite a generatorperm(.) that producesall permutations ofabove list.Theory and Practice of Artificial Intelligence 23 / 142Exercise 5 (Permutation)AssumptionsConsider a list […]of elements.TaskWrite a generatorperm(.) that producesall permutations ofabove list.Example (Wrong! | Why?)def insertion(e, s):for i in range(len(s)+1):s[i:i] = [e]yield sdef perm(s):if s == []:yield []else:e, s1 = s[0], s[1:]for s1p in perm(s1):for p in insertion(e,s1p):yield pfor p in perm([1,2,3,4]): print pTheory and Practice of Artificial Intelligence 23 / 142Exercise 6 (Permutation) AssumptionsExample (Right! | Why?) Consider a list […]of elements.TaskWrite a generatorperm(.) that producesall permutations ofabove list.def insertion(e, s):for i in range(len(s)+1):yield s[:i] + [e] + s[i:]def perm(s):if s == []:yield []else:e, s1 = s[0], s[1:]for s1p in perm(s1):for p in insertion(e,s1p):yield pfor p in perm([1,2,3,4]): print pTheory and Practice of Artificial Intelligence 24 / 142Copying Lists Warning: Applying Functions to ListsFunctions/generators can modify lists destructively! Exampledef modifier(s):s[2:4] = [“foo”, “bar”]s = [1,2,3,4,5,6] print “before:”, smodifier(s)print “after:”, s# [1,2,3,4,5,6]# [1,2,’foo’,’bar’,5,6] Theory and Practice of Artificial Intelligence 25 / 142Copying Lists Warning: Applying Functions to ListsFunctions/generators can modify lists destructively! Exampledef modifier(s):s[2:4] = [“foo”, “bar”]s = [1,2,3,4,5,6] print “before:”, smodifier(s)print “after:”, s# [1,2,3,4,5,6]# [1,2,’foo’,’bar’,5,6] Exampledef modifier(s):s = s[:]s[2:4] = [“foo”, “bar”]s = [1,2,3,4,5,6] print “before:”, smodifier(s)print “after:”, s# [1,2,3,4,5,6]# [1,2,3,4,5,6] Theory and Practice of Artificial Intelligence 25 / 142Proof of Correctness IQuestionHow do you demonstrate that1 you get all permutations?2 you get each permutation exactly once?Sanity CheckHow many resulting permutations?n! is a good start | it does not guarantee correctness, but ifthis is wrong, that needs fixing first.Theory and Practice of Artificial Intelligence 26 / 142Proof of Correctness IIInductionshow that base case is correct (this is trivial)assume that permutation generator for the smaller list (lengthn – 1) is correct, i.e. that1 it generates all permutations2 all of them exactly onceunder this assumption, prove that full list permutation (n)retains this property.Theory and Practice of Artificial Intelligence 27 / 142Proof of Correctness IIIProof IdeaBase Case: obvious. Empty list has only itself aspermutation. Done.Note: Not talking about debugging, only want to know whether recursion step coverseverythingRecursion Step: 1 Do we get all?Assume, some arbitrary permutation given.Is it included? We covered the case of theempty list, so assume the list is not empty.Recursion says: we know it is correct for listof shorter length n – 1.What now?2 Do we get all of them exactly once?Theory and Practice of Artificial Intelligence 28 / 142Sheep and Cow ProblemSolution Part 1E = 0C = 1S = 2start_stable = [C, C, C, C, E, S, S, S, S]goal_stable = [S, S, S, S, E, C, C, C, C]Theory and Practice of Artificial Intelligence 29 / 142Sheep and Cow Problem | ConsiderationsPossible Moves1 Cow moves one field to the right (if empty)2 Sheep moves one field to the left (if empty)3 Cow jumps over one Sheep into an empty field4 Sheep jumps over one Cow into an empty fieldTheory and Practice of Artificial Intelligence 30 / 142Sheep and Cow Problem | Considerations IIPatterns of Possible MovesCow moves right:….C_….…._C….Sheep moves left:…._S….….S_….Cow jumps right:….CS_……._SC….Sheep jumps left:…._CS….….SC_….Idea1 can only jump into emptyfield2 identify candidates formoving/jumping animal3 need to be inside field4 need to conform to one ofthe given patternsTheory and Practice of Artificial Intelligence 31 / 142Sheep and Cow ProblemSolution Part 2def successors(stable):# find empty spotempty = stable.index(E)# generate list of unfiltered candidate positionscandidates = [empty-2, empty-1, empty+1, empty+2]# keep only those which are inside the stablecandidates = [c for c in candidates if c >= 0 and c < len(stable)]# Cows can always move right, Sheep always left, and from two fields# apart, they have to jump over an opposite animalcandidates = [c for c in candidates ifstable[c:c+2] == [C, E] or # cow can move rightstable[c-1:c+1] == [E, S] or # sheep can move leftstable[c:c+3] == [C, S, E] or # cow jumps over sheepstable[c-2:c+1] == [E, C, S]] # sheep jumps over cow# make sure that all these entries are occupied# (not necessary for operation, just better style)assert not [c for c in candidates if stable[c] == E]for c in candidates:new_stable = stable[:] # make a copy# move the candidate into empty posnew_stable[c], new_stable[empty] = new_stable[empty], new_stable[c]yield new_stable # remember where we wereTheory and Practice of Artificial Intelligence 32 / 142Sheep and Cow ProblemSolution Part 3def solution(stable):if stable == goal_stable:return [stable]# else, depth firstfor new_stable in successors(stable):# print new_stablesol = solution(new_stable)if sol:return [stable] + solfor s in solution(start_stable):print sTheory and Practice of Artificial Intelligence 33 / 142

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER