32 type Mem = Map[Int, Int] |
31 type Mem = Map[Int, Int] |
33 |
32 |
34 import io.Source |
33 import io.Source |
35 import scala.util._ |
34 import scala.util._ |
36 |
35 |
|
36 // ADD YOUR CODE BELOW |
|
37 //====================== |
37 |
38 |
38 // TASKS |
39 // (5) |
39 //======= |
|
40 |
|
41 // (5) Write a function jtable that precomputes the "jump |
|
42 // table" for a bf-program. This function takes a bf-program |
|
43 // as an argument and Returns a Map[Int, Int]. The |
|
44 // purpose of this map is to record the information about |
|
45 // pc positions where '[' or a ']' are stored. The information |
|
46 // is to which pc-position do we need to jump next? |
|
47 // |
|
48 // For example for the program |
|
49 // |
|
50 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
|
51 // |
|
52 // we obtain the map |
|
53 // |
|
54 // Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
|
55 // |
|
56 // This states that for the '[' on position 5, we need to |
|
57 // jump to position 20, which is just after the corresponding ']'. |
|
58 // Similarly, for the ']' on position 19, we need to jump to |
|
59 // position 6, which is just after the '[' on position 5, and so |
|
60 // on. The idea is to not calculate this information each time |
|
61 // we hit a bracket, but just look up this information in the |
|
62 // jtable. You can use the jumpLeft and jumpRight functions |
|
63 // from Part 1 for calculating the jtable. |
|
64 // |
|
65 // Then adapt the compute and run functions from Part 1 |
|
66 // in order to take advantage of the information stored in the jtable. |
|
67 // This means whenever jumpLeft and jumpRight was called previously, |
|
68 // you should immediately look up the jump address in the jtable. |
|
69 |
|
70 |
|
71 def jtable(pg: String) : Map[Int, Int] = ??? |
40 def jtable(pg: String) : Map[Int, Int] = ??? |
72 |
|
73 |
41 |
74 // testcase |
42 // testcase |
75 // |
43 // |
76 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
44 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
77 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
45 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
78 |
46 |
79 |
47 |
80 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
48 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
81 def run2(pg: String, m: Mem = Map()) = ??? |
49 def run2(pg: String, m: Mem = Map()) = ??? |
82 |
50 |
83 |
|
84 // testcases |
51 // testcases |
85 // time_needed(1, run2(load_bff("benchmark.bf"))) |
52 // time_needed(1, run2(load_bff("benchmark.bf"))) |
86 // time_needed(1, run2(load_bff("sierpinski.bf"))) |
53 // time_needed(1, run2(load_bff("sierpinski.bf"))) |
87 |
54 |
88 |
55 |
89 |
56 |
90 // (6) Write a function optimise which deletes "dead code" (everything |
57 // (6) |
91 // that is not a bf-command) and also replaces substrings of the form |
|
92 // [-] by a new command 0. The idea is that the loop [-] just resets the |
|
93 // memory at the current location to 0. In the compute3 and run3 functions |
|
94 // below you implement this command by writing the number 0 to mem(mp), |
|
95 // that is write(mem, mp, 0). |
|
96 // |
|
97 // The easiest way to modify a string in this way is to use the regular |
|
98 // expression """[^<>+\-.\[\]]""", which recognises everything that is |
|
99 // not a bf-command and replace it by the empty string. Similarly the |
|
100 // regular expression """\[-\]""" finds all occurrences of [-] and |
|
101 // by using the Scala method .replaceAll you can replace it with the |
|
102 // string "0" standing for the new bf-command. |
|
103 |
58 |
104 def optimise(s: String) : String = ??? |
59 def optimise(s: String) : String = ??? |
105 |
60 |
106 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
61 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
107 |
62 |
115 // |
70 // |
116 // time_needed(1, run3(load_bff("benchmark.bf"))) |
71 // time_needed(1, run3(load_bff("benchmark.bf"))) |
117 |
72 |
118 |
73 |
119 |
74 |
120 // (7) Write a function combine which replaces sequences |
75 // (7) |
121 // of repeated increment and decrement commands by appropriate |
|
122 // two-character commands. For example for sequences of + |
|
123 // |
|
124 // orig bf-cmds | replacement |
|
125 // ------------------------------ |
|
126 // + | +A |
|
127 // ++ | +B |
|
128 // +++ | +C |
|
129 // | |
|
130 // ... | |
|
131 // | |
|
132 // +++....+++ | +Z |
|
133 // (where length = 26) |
|
134 // |
|
135 // Similar for the bf-command -, > and <. All other commands should |
|
136 // be unaffected by this change. |
|
137 // |
|
138 // Adapt the compute4 and run4 functions such that they can deal |
|
139 // appropriately with such two-character commands. |
|
140 |
|
141 |
|
142 def combine(s: String) : String = ??? |
76 def combine(s: String) : String = ??? |
143 |
77 |
144 // testcase |
78 // testcase |
145 // combine(load_bff("benchmark.bf")) |
79 // combine(load_bff("benchmark.bf")) |
146 |
80 |
147 |
|
148 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
81 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ??? |
149 |
|
150 |
82 |
151 // should call first optimise and then combine on the input string |
83 // should call first optimise and then combine on the input string |
152 // |
84 // |
153 def run4(pg: String, m: Mem = Map()) = ??? |
85 def run4(pg: String, m: Mem = Map()) = ??? |
154 |
86 |