{"id":1788,"date":"2011-05-25T14:24:48","date_gmt":"2011-05-25T14:24:48","guid":{"rendered":"http:\/\/cemclinux1.math.uwaterloo.ca\/~cscircles\/wordpress\/?page_id=1788"},"modified":"2011-05-25T14:24:48","modified_gmt":"2011-05-25T14:24:48","slug":"15a-basic","status":"publish","type":"page","link":"https:\/\/olescs.hkmu.edu.hk\/python\/15a-basic\/","title":{"rendered":"15A: Termination Determination"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nOriginal lesson author: David Pritchard, daveagp@gmail.com, http:\/\/cscircles.ca<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/-->\n<p><em>Exercises 15A, 15B, and 15C can be completed in any order.<\/em><\/p>\n<p>In this lesson you will complete a long and complex problem that has been broken into parts for you. This lesson also introduces <code>str.split()<\/code>, a useful method for splitting strings: it deletes all of the spaces, and then returns a list of all of the words in the string. The original string is not modified.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform0\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox0'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Examples of <code>str.split()<\/code><div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 188px;'><textarea wrap='off' name='usercode0' id='usercode0'  cols=10 rows=7 readonly='readonly'  style = 'height : 188px;'  class='pyboxCode RO'>\nS = 'This is a string'\nwords = S.split()\nprint(words)\nprint(len(words))\nprint(words[1])\nprint(S)   # S is not changed\nprint('  Another example  of split '.split())<\/textarea><\/div>\n<div id='pbhistory0' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit0' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(0)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(0,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"b042ccd05e773224458ce9ab17cca164\"\/>\n<div id='pbresults0' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit0\").value = \"Run program\";document.getElementById(\"inputInUse0\").value = \"N\";<\/script>\n<\/p>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> You can call\u00a0<code>split()<\/code> with special arguments to do more sophisticated splitting, but we don't need this ability below. If you are interested, check the <a href=\"http:\/\/docs.python.org\/py3k\/library\/stdtypes.html#str.split\">Python documentation<\/a>. <\/span><\/td><\/table><\/p>\n<p>Now we get to the task at hand. The old programming language <a href=\"http:\/\/en.wikipedia.org\/wiki\/BASIC\">BASIC<\/a> was famous for its numbered lines and <code>goto<\/code> statements. For this exercise, you will implement a simple version of BASIC with just these features. Specifically, the input to your program will consist of several lines in the format<\/p>\n<p style=\"text-align: center\"><code>\u00ablabel\u00bb goto \u00abtarget\u00bb<\/code><\/p>\n<p>where\u00a0<code>\u00ablabel\u00bb<\/code>\u00a0and <code>\u00abtarget\u00bb<\/code>\u00a0are positive integers. The <em>label<\/em>\u00a0is like the name or address of the line;\u00a0<em>all labels are unique.<\/em>\u00a0The <em>target<\/em> tells you the label of the line to move to next. The last line of the program is\u00a0<code>\u00ablabel\u00bb END<\/code>\u00a0indicating that you should stop once you move to this line.\u00a0Here is a sample BASIC program:<\/p>\n<pre>5 GOTO 30\n10 GOTO 20\n20 GOTO 10\n30 GOTO 40\n40 END<\/pre>When BASIC runs the program, this is what happens. We begin at the first line (with label 5). The line with label 5 has target 30, so next we go to the line with label 30. Then line 30 tells us to go to line 40. Line 40 tells us to END. So, the program terminated successfully.<\/p>\n<p>On the other hand, a BASIC program can also loop forever. Here is an example:<\/p>\n<pre>10 GOTO 21\n21 GOTO 37\n37 GOTO 21\n40 END<\/pre>The program starts at line 10, but then it loops forever between lines 21 and 37.<\/p>\n<p><strong>Your task<\/strong> is to write a Python program, which reads a BASIC program as input. If the program terminates, your program should print\u00a0<code>success<\/code>. If the program enters an infinite loop, your\u00a0program should print <code>infinite loop<\/code>.\u00a0Assume each target equals some valid label and that all labels are unique, so you do not have to do error-checking.<\/p>\n<p>There are several ways you could do this, but in this lesson we have chosen one simple approach that breaks the problem in to 3 sub-tasks. (In lesson 15C you have one large problem and design the sub-tasks yourself.)<\/p>\n<h2>Sub-task 1: Reading the program<\/h2>\n<p>To read the program, we need to keep calling <code><a href=\"\/5-input\/\">input()<\/a><\/code>. However, we need to stop calling <code>input()<\/code> once the last line (the one with <code>END<\/code>) is reached, to avoid an <code>EOFError<\/code>.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform1\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox1'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Reading the Program<\/span><\/div>Write a function <code>getBASIC()<\/code> which takes no arguments, and does the following: it should keep reading lines from input using a while loop; when it reaches the end it should return the whole program in the form of a list of strings. (Hints: about\u00a0<a class=\"hintlink\"  id=\"hintlink2\">lists<\/a> and\u00a0<a class=\"hintlink\"  id=\"hintlink3\">stopping<\/a>)<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode1' id='usercode1'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory1' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput1\">You may enter input for the program in the box below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit1' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch1\" value=\"Input Switch\" onclick=\"pbInputSwitch(1,'N')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(1)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(1,'N')\" ><\/td>\n<\/tr><\/table><select id='pbSelect1' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(1,'15a.getbasic')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(1);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"6c902a898cd352905e59e4a948f963fa\"\/>\n<div id='pbresults1' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(1);});pbInputSwitch(1,\"N\");<\/script>\n<\/p>\n<h2>Sub-task 2: Go to it!<\/h2>\n<p>Once we have read the program, we need to be able to move from line to line in the program. To accomplish this, we ask you to write the following subroutine.<br \/>\n<form class=\"pbform\" action=\"#\" id=\"pbform4\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox4'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Go to it!<\/span><\/div>Define a function <code>findLine(prog, target)<\/code> to perform the following. Assume <code>prog<\/code> is a list of strings containing a BASIC program, like the type generated by <code>getBASIC()<\/code>; assume <code>target<\/code> is a string containing a line number, which is the target of a GOTO statement. The function should return the index <code>i<\/code> (a number between <code>0<\/code> and <code>len(prog)-1<\/code>) such that <code>prog[i]<\/code> is the line whose label equals\u00a0<code>target<\/code>. <a class=\"hintlink\"  id=\"hintlink5\">Hint<\/a>\u00a0<br\/><strong>Sample input\/output:<\/strong> If you call <\/p>\n<pre>findLine(['10 GOTO 20','20 END'], '10')<\/pre> then the output should be <code>0<\/code>, since item 0 of the list is the line with label 10.<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode4' id='usercode4'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory4' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput4\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit4' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch4\" value=\"Input Switch\" onclick=\"pbInputSwitch(4,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(4)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(4,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect4' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(4,'15a.goto')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(4);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"ac782943c2ab9fe93f047e3f2a8fb981\"\/>\n<div id='pbresults4' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(4);});pbInputSwitch(4,\"Y\");<\/script>\n<\/p>\n<h2>Sub-task 3: Smart Simulation<\/h2>\n<p>In the previous two exercises, we handled the <em>input routine<\/em> and the <em>searching task<\/em>. These will be useful to make writing the main program shorter. However, there is still a major question: how can we actually solve the original problem? The most straightforward way would be to simulate the BASIC program:<\/p>\n<ul>\n<li>let <code>prog<\/code> be the BASIC program (an array of strings)<\/li>\n<li>start a counter called <code>location<\/code> at 0, since we begin on the first line of the program<\/li>\n<li>while True,\n<ul>\n<li>if <code>prog[location]<\/code> is the END line, return \"success\" and stop.<\/li>\n<li>let <code>T<\/code> be the target string indicated in <code>prog[location]<\/code><\/li>\n<li>let the new value of\u00a0<code>location<\/code> be\u00a0<code>findLine(prog, T)<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>But, there is a major problem: this doesn't detect infinite loops, and if the BASIC program has an infinite loop, then the Python program will also loop forever. What we wanted was that the program should print \"infinite loop\" in this situation. We leave this problem for you to solve; we give a hint below.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform6\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox6'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Smart Simulation<\/span><\/div>Write a function <code>execute(prog)<\/code> to do the following. Assume\u00a0<code>prog<\/code> is a list of strings containing the BASIC program, like before. Then, your function\u00a0should return either \"<code>success<\/code>\" or \"<code>infinite loop<\/code>\" depending on whether the program terminates, or loops forever. <strong>Important<\/strong>: you should assume the procedure <code>findLine(prog, target)<\/code> defined in sub-task 2 is already defined, you do not need to re-write it. <a class=\"hintlink\"  id=\"hintlink7\">Hint<\/a> <div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode6' id='usercode6'  cols=10 rows=20   class='pyboxCode RW'>\n# here is a broken solution to get you started\ndef execute(prog):\n  location = 0\n  while True:\n    if location==len(prog)-1: return \"success\"\n    #get T from prog[location] via str.split\n    location = findLine(prog, T)\n<\/textarea><\/div>\n<div id='pbhistory6' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput6\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode6' value='# here is a broken solution to get you started\\ndef execute(prog):\\n  location = 0\\n  while True:\\n    if location==len(prog)-1: return \\\"success\\\"\\n    #get T from prog[location] via str.split\\n    location = findLine(prog, T)\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit6' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch6\" value=\"Input Switch\" onclick=\"pbInputSwitch(6,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(6)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(6,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect6' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(6,'15a.main')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(6,descape($('#defaultCode6').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(6);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse6\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"6\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"8cb015415ecc3a1fb073b9dfce9ec79c\"\/>\n<div id='pbresults6' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(6);});pbInputSwitch(6,\"Y\");<\/script>\n<\/p>\n<h2>Putting it all together<\/h2>\n<p>To test your code as a complete solution, copy and paste your previous solutions into the following template.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform8\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox8'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>BASIC Simulator<\/span><\/div>Put together your BASIC simulator.<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode8' id='usercode8'  cols=10 rows=20   class='pyboxCode RW'>\n# def getBASIC from subtask 1\n\n# def findLine from subtask 2\n\n# def execute from subtask 3\n\nprint(execute(getBASIC()))\n<\/textarea><\/div>\n<div id='pbhistory8' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput8\">You may enter input for the program in the box below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode8' value='# def getBASIC from subtask 1\\n\\n# def findLine from subtask 2\\n\\n# def execute from subtask 3\\n\\nprint(execute(getBASIC()))\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit8' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch8\" value=\"Input Switch\" onclick=\"pbInputSwitch(8,'N')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(8)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(8,'N')\" ><\/td>\n<\/tr><\/table><select id='pbSelect8' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(8,'15a.overall')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(8,descape($('#defaultCode8').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(8);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse8\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"8\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"65fa257da1397c3584f44a84247679b0\"\/>\n<div id='pbresults8' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(8);});pbInputSwitch(8,\"N\");<\/script>\n<\/p>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> If your programming language is slightly more complicated, then it's\u00a0<em>impossible<\/em>\u00a0to write a termination-checking program. This was the earliest important theorem in computer science, proven by <a href=\"http:\/\/en.wikipedia.org\/wiki\/Alan_Turing\">Alan Turing<\/a> in the 1930s, and nowadays people refer to the result by saying \"the\u00a0<a href=\"http:\/\/en.wikipedia.org\/wiki\/Halting_problem\">Halting Problem<\/a>\u00a0is undecidable.\" <\/span><\/td><\/table><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Exercises 15A, 15B, and 15C can be completed in any order. In this lesson you will complete a long and complex problem that has been broken into parts for you. This lesson also introduces str.split(), a useful method for splitting &hellip; <a href=\"https:\/\/olescs.hkmu.edu.hk\/python\/15a-basic\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1788","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/1788"}],"collection":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/comments?post=1788"}],"version-history":[{"count":0,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/1788\/revisions"}],"wp:attachment":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/media?parent=1788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}