188.md (8025B)
1 Source: https://codeforces.com/blog/entry/4633 2 3 Roco is a very simple language. On one hand, it's esoteric, so everything you need to know about it fits in two pages. On the other hand, it's powerful enough to enable writing rather complicated programs in it without racking one's brains over each elementary operation (like in Brainfuck). Being able to refer variables using names (numerical, but names nevertheless) is already a gift to the programmer :-) 4 5 #### [188A - Hexagonal Numbers](/contest/188/problem/A "Surprise Language Round 6") 6 7 As usual, the first problem tests the competitor's understanding of basic arithmetic operations. The solution is very similar to the example. 8 9 ``` 10 iin [0] 11 mul [1] [0] 2 12 dec [1] 13 mul [1] [1] [0] 14 iout [1] 15 ac 16 ``` 17 18 Starting with the second one, the problems need learning the main feature of the language — the coroutines. A coroutine is a named piece of code executed in an endless loop. Something in between a procedure (without input parameters and variables, but with a name used for calling it) and a loop (without loop counter or break conditions, but with a chance to break it at any moment), coroutines allow to implement both these concepts. 19 20 #### [188B - A + Reverse B](/contest/188/problem/B "Surprise Language Round 6") 21 22 The key element of this problem is reversing a number (we knew how to add the second number to it ever since the example). There are two ways to do this: either read the number as a sequence of characters and accumulate its reverse simultaneously, or read the number as, well, a number and calculate its reverse using math. I used the second approach, so I needed a single loop-like coroutine which stopped when the number being reversed turned zero. 23 24 ``` 25 /* coroutine to reverse a number [1] into [2] */ 26 co reverse { 27 eq [3] [1] 0 28 if [3] 29 ac 30 31 /* find current number modulo 10 */ 32 mod [3] [1] 10 33 /* add it to reversed number */ 34 mul [2] [2] 10 35 add [2] [2] [3] 36 /* and divide current number */ 37 div [1] [1] 10 38 } 39 40 iin [0] 41 iin [1] 42 ca reverse 43 add [2] [2] [0] 44 iout [2] 45 ac 46 ``` 47 48 #### [188C - LCM](/contest/188/problem/C "Surprise Language Round 6") 49 50 In other languages the easiest way to get LCM of two numbers is recursive. The specifics of Roco is that one can't write a recursion with a single coroutine calling itself — after the second call of the coroutine its execution continues from the place where it stopped last time. So it was easier to rewrite the standard algorithm as a loop. 51 52 ``` 53 /* [0] - a 54 [1] - b 55 */ 56 co gcd { 57 eq [2] [0] 0 58 if [2] 59 ac 60 set [2] [1] 61 set [1] [0] 62 mod [0] [2] [1] 63 } 64 65 iin [0] 66 iin [1] 67 set [3] [0] 68 set [4] [1] 69 ca gcd 70 /* now [1] is gcd */ 71 div [5] [3] [1] 72 mul [5] [5] [4] 73 iout [5] 74 ac 75 ``` 76 77 #### [188D - Asterisks](/contest/188/problem/D "Surprise Language Round 6") 78 79 Ok, let's move on to a more complicated task: here we need a nested loop, the outer one running through the lines and the inner one — through the asterisks in the line. The inner loop will be called several times (from each iteration of the outer one), so here one could meet the mentioned feature of the coroutines for the first time. 80 81 ``` 82 /* [0] - * quantity 83 [1] - current line 84 [2] - current * in line 85 */ 86 87 co one_row { 88 lt [3] [1] [2] 89 if [3] 90 ac 91 cout 42 92 inc [2] 93 } 94 95 co print_all { 96 lt [3] [0] [1] 97 if [3] 98 ac 99 set [2] 1 100 ca one_row 101 cout 10 102 inc [1] 103 } 104 105 iin [0] 106 set [1] 1 107 ca print_all 108 ac 109 ``` 110 111 #### [188E - HQ9+](/contest/188/problem/E "Surprise Language Round 6") 112 113 This time one can't solve this problem in one line using regular expressions, since this language has none. So one has to do it in an old-fashioned way, reading characters one-by-one and checking them for equality with each of the required ones. The code is rather long — there are three characters to compare each one to, and the answer has to be printed char-by-char, but overall there is nothing complex here. 114 115 ``` 116 /* [0] - YES or NO 117 [1] - current char 118 */ 119 120 co one_char { 121 cin [1] 122 123 eq [2] [1] 10 124 if [2] 125 ac 126 127 /* H */ 128 eq [2] [1] 72 129 or [0] [0] [2] 130 /* Q */ 131 eq [2] [1] 81 132 or [0] [0] [2] 133 /* 9 */ 134 eq [2] [1] 57 135 or [0] [0] [2] 136 } 137 138 co say_yes { 139 cout 89 140 cout 69 141 cout 83 142 cout 10 143 ac 144 } 145 146 co say_no { 147 cout 78 148 cout 79 149 cout 10 150 ac 151 } 152 153 set [0] 0 154 ca one_char 155 /* output the result stored in [0] */ 156 if [0] 157 ca say_yes 158 dec [0] 159 if [0] 160 ca say_no 161 ac 162 ``` 163 164 Three last problems are almost real programming :-) They use the fact that in Roco variables are referenced not by names but by their indices in the heap, and the index can in turn be the contents of a variable. One can do more interesting things with arrays, but the programs become longer and more error-prone. 165 166 #### [188F - Binary Notation](/contest/188/problem/F "Surprise Language Round 6") 167 168 The bad thing about the binary notation is that the digits are calculated right-to-left but have to be printed left-to-right. This can be done without arrays (reverse the number in binary using the math trick from [188B - A + Reverse B](/contest/188/problem/B "Surprise Language Round 6") and then print its digits in the same order as they are calculated), but I used an array solution which first calculates the digits and writes them into an array and then goes through the array from the end to the start and prints the digits. 169 170 ``` 171 /* [0] - current number 172 [1] - index of last digit calculated 173 [2]..[9] - service cells 174 [10]..[[1]] - the actual digits of the number 175 */ 176 177 co calculate_digits { 178 /* stop when the number is 0 */ 179 eq [3] [0] 0 180 if [3] 181 ac 182 183 /* get next digit - put it to its location directly */ 184 mod [[1]] [0] 2 185 /* update the number and its notation length */ 186 div [0] [0] 2 187 inc [1] 188 } 189 190 co output_digits { 191 /* stop when the next digit printed will be outside of the number */ 192 eq [3] [1] 9 193 if [3] 194 ac 195 196 /* output the digit at [1] */ 197 iout [[1]] 198 dec [1] 199 } 200 201 202 iin [0] 203 set [1] 10 204 ca calculate_digits 205 dec [1] 206 ca output_digits 207 ac 208 ``` 209 210 #### [188G - Array Sorting](/contest/188/problem/G "Surprise Language Round 6") 211 212 Unlike Befunge, in Roco the memory size limit is technical, not conceptual, so one could coed counting sort as well as comparison-based sort. Here is a code for the former one. 213 214 ``` 215 /* [1]..[100] - the counts of numbers 216 [101] - quantity of numbers 217 [102] - current number 218 [103] - current index 219 */ 220 221 iin [101] 222 223 set [103] 1 224 co init { 225 eq [104] [103] 101 226 if [104] 227 ac 228 set [[103]] 0 229 inc [103] 230 } 231 ca init 232 233 set [103] 0 234 co read { 235 eq [104] [103] [101] 236 if [104] 237 ac 238 iin [102] 239 inc [[102]] 240 inc [103] 241 } 242 ca read 243 244 set [102] 1 245 co print_sorted { 246 eq [104] [102] 101 247 if [104] 248 ac 249 set [103] 1 250 co print_one_number { 251 gt [104] [103] [[102]] 252 if [104] 253 ac 254 iout [102] 255 cout 32 256 inc [103] 257 } 258 /* due to coroutine property (!), call only for positive quantity of numbers*/ 259 gt [104] [[102]] 0 260 if [104] 261 ca print_one_number 262 inc [102] 263 } 264 ca print_sorted 265 ac 266 ``` 267 268 #### [188H - Stack](/contest/188/problem/H "Surprise Language Round 6") 269 270 This problem required to simulate a stack using an array — nothing too complicated, especially since the data never overflows and never attempts to do invalid calculations. 271 272 ``` 273 /* [0] - current character 274 [1] - current stack size 275 [2]..[9] - service 276 [10]... - stack 277 */ 278 279 co plus { 280 dec [1] 281 add [3] [1] 9 282 add [4] [3] 1 283 add [[3]] [[3]] [[4]] 284 ac 285 } 286 287 co multiply { 288 dec [1] 289 add [3] [1] 9 290 add [4] [3] 1 291 mul [[3]] [[3]] [[4]] 292 ac 293 } 294 295 co number { 296 sub [2] [0] 48 297 inc [1] 298 add [3] [1] 9 299 set [[3]] [2] 300 ac 301 } 302 303 co process { 304 cin [0] 305 /* end of line */ 306 eq [2] [0] 10 307 if [2] 308 ac 309 /* digit - push on the stack */ 310 gt [2] [0] 47 311 if [2] 312 ca number 313 eq [2] [0] 43 314 if [2] 315 ca plus 316 eq [2] [0] 42 317 if [2] 318 ca multiply 319 } 320 321 set [2] 0 322 ca process 323 /* output the topmost element of the stack */ 324 add [2] [1] 9 325 iout [[2]] 326 ac 327 ```