From: Frank Fischer Date: 2008-11-26T18:30:41+09:00 Subject: Re: [QUIZ] Befunge (#184) --nextPart1462683.XyMqu45Hlp Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8Bit Hi, This post has not much to do with a solution of the current QUIZ, but some ideas about extensions to the QUIZ, so feel free to stop reading (and sorry for bothering you). My current solution looks almost the same as the others, so it's not so interesting. But the QUIZ inspired me to another funny problem: Try to generate Befunge-code automatically: An easy observation is, that one can split up Befunge-code into some linear pieces. Each piece of code is then connected to up to two following pieces (by a '|' or '_', I don't look at random-jumps here). So the problem is the following: given some linear pieces of codes and knowing their connections, write a program that arranges those pieces in the 80x25 (or whatever) lattice and add the right commands to realize the required connections. For example, assume a program that reads to variables and prints the greater one. The linear pieces are: &:01p&:11p` ... INPUT X,Y and TEST 01g.@ ... PRINT X 11g.@ ... PRINT Y so you have 3 pieces, and two connection (one from the first to second and one from the first to the third, depending on the topmost value on the stack). A very simple approach is to put each piece in one line, leave some lines empty and use that empty lines to connect the pieces. My implementation of this approach is attached to this message. The example above would generate the following code (without the '#'): ################### #v > v # #> &:01p&:11p`|> # # > v# # # # 01g.@ > # # # # # # 11g.@ ># ################### The attached program includes the euclidian algorithm as a second example, i.e. the program generates a Befunge-program that reads two numbers and computes the gcd. I can imagine two interesting tasks: 1. write some simple high-level-language that can be compiled to linear pieces of code with the correct connections. Together with my example one could create a language-to-Befunge compiler (i.e. using Befunge as 'assembly'). The language should support conditionals (IF, THEN, ELSE) and loops (WHILE), and perhaps, if you're really good, subroutines (the latter would be more challenging, I think). 2. write better arrangements of the code-pieces. In my implementation much space is wasted. Remember, linear pieces do not need to be in one line, the may contain turns or jumps or whatever. So one can ask a. how to generate very compact code b. how to generate code with a visually nice layout (think of a program computing Pi whose code looks like a Pi :)) c. ... These are just a view thoughts about extensions to the nice QUIZ. Bye, Frank --nextPart1462683.XyMqu45Hlp Content-Type: application/x-ruby; name="befc.rb" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="befc.rb" IyEvdXNyL2Jpbi9lbnYgcnVieQoKIyBHZW5lcmF0ZXMgdGhlIGNvZGUgdG8gc2V0IG9yIGdldCB0 aGUgdmFsdWUgb2YgYSB2YXJpYWJsZXMgc3RvcmVkIGF0CiMgcG9zaXRpb24geCx5LiBUaGUgdmFy aWFibGVzIG1heSBiZSA4IG9yIDE2LUJpdC4KIyBUaGlzIGNvZGUgZG9lcyBub3Qgd29yayB3ZWxs IHdpdGggbmVnYXRpdmUgMTYtQml0IG51bWJlcnMuIApjbGFzcyBWYXJpYWJsZQoKICAgIGRlZiBp bml0aWFsaXplKCB4LCB5LCBzaXplID0gMSApCiAgICAgICAgQHggPSB4CiAgICAgICAgQHkgPSB5 CiAgICAgICAgQHNpemUgPSBzaXplCiAgICAgICAgcmFpc2UgIlVuc3VwcG9ydGVkIHZhcmlhYmxl IHNpemU6ICN7QHNpemV9IiBpZiBzaXplICE9IDEgJiYgc2l6ZSAhPSAyCiAgICBlbmQKCiAgICAj IGdlbmVyYXRlcyB0aGUgY29kZSB0byBnZXQgdGhlIHZhcmlhYmxlJ3MgdmFsdWUgb250byB0aGUg c3RhY2suCiAgICBkZWYgZ2V0CiAgICAgICAgY2FzZSBAc2l6ZQogICAgICAgIHdoZW4gMQogICAg ICAgICAgICAiI3tAeH0je0B5fWciCiAgICAgICAgd2hlbiAyCiAgICAgICAgICAgICI4ODQqKjo6 I3tAeH0je0B5fWcrXFwlXFwje0B4KzF9I3tAeX1nXFwqKyIKICAgICAgICBlbmQKICAgIGVuZAoK ICAgICMgZ2VuZXJhdGVzIHRoZSBjb2RlIHRvIHNldCB0aGUgdmFyaWFibGUncyB2YWx1ZSB0byB0 aGUgc3RhY2sncyB0b3AuCiAgICBkZWYgc2V0CiAgICAgICAgY2FzZSBAc2l6ZQogICAgICAgIHdo ZW4gMQogICAgICAgICAgICAiI3tAeH0je0B5fXAiCiAgICAgICAgd2hlbiAyCiAgICAgICAgICAg ICI6ODg0KiolI3tAeH0je0B5fXA4ODQqKi8je0B4KzF9I3tAeX1wIgogICAgICAgIGVuZAogICAg ZW5kCgplbmQKCgojIEEgcGllY2Ugb2YgY29kZS4KY2xhc3MgRnJhZ21lbnQKCiAgICBhdHRyX2Fj Y2Vzc29yIDpjb25uZWN0X3RydWUsIDpjb25uZWN0X2ZhbHNlCgogICAgZGVmIGluaXRpYWxpemUo IGNvZGUgKQogICAgICAgIEBjb2RlID0gY29kZQogICAgZW5kCgogICAgZGVmIHRvX3MKICAgICAg ICBAY29kZQogICAgZW5kCgogICAgZGVmIHNpemUKICAgICAgICBAY29kZS5zaXplCiAgICBlbmQK ICAgIAplbmQKCgojIFByb2dyYW0gZ2VuZXJhdG9yLiAgQWxpZ25zIHRoZSBmcmFnbWVudHMgaW4g bGluZXMgYW5kIHVzZXMgZGlyZWN0b3JzCiMgdG8gY29ubmVjdCB0aGVtLiAgSWYgZnJhZ21lbnQg aGFzIG5vIGNvbm5lY3Rpb25zLCBhICdAJyBpcyBhcHBlbmRlZAojIHRvIHRoYXQgZnJhZ21lbnQu ICBJZiBpdCBjb250YWlucyB0d28gY29ubmVjdGlvbnMsIGEgJ3wnIGlzCiMgYXBwZW5kZWQsIGlm IGl0IGhhcyBvbmx5IG9uZSBjb25uZWN0aW9uLCBlaXRoZXIgYSAnXicgb3IgYW4gJ3YnIGlzCiMg YXBwZW5kZWQuICBFYWNoIGZyYWdtZW50IHVzZXMgdGhyZWUgbGluZXMsIHR3byBhbG1vc3QgZW1w dHkgbGluZXMKIyBmb3IgcmVkaXJlY3Rpb25zIGFuZCBvbmUgbGluZSB3aXRoIHRoZSBjb2RlIGl0 c2VsZi4KY2xhc3MgQ29kZQoKICAgIGRlZiBpbml0aWFsaXplCiAgICAgICAgQGZyYWdtZW50cyA9 IFtdCiAgICBlbmQKCiAgICBkZWYgYWRkKCBmcmFnbWVudCApCiAgICAgICAgQGZyYWdtZW50cyA8 PCBmcmFnbWVudAogICAgZW5kCgogICAgIyB4b2ZmIGFuZCB5b2ZmIGFyZSB1c2VkIHRvIGF2b2lk IHRoZSB2YXJpYWJsZS1zZWN0aW9uLgogICAgZGVmIHNob3coIHhvZmYsIHlvZmYgKQogICAgICAg ICMgd2UgbmVlZCBzb21lIHNwYWNlIGZvciB0aGUgaW5pdGlhbCBkaXJlY3RvcgogICAgICAgIHhv ZmYgPSBbMSwgeG9mZl0ubWF4CiAgICAgICAgCiAgICAgICAgbWF4X2xlbiA9IEBmcmFnbWVudHMu bWFwe3xmfCBmLnNpemV9Lm1heAoKICAgICAgICAjIGdlbmVyYXRlIHRoZSBjb2RlLWJ1ZmZlcgog ICAgICAgIHhkaW0gPSB4b2ZmICsgbWF4X2xlbiArIDEgKyBAZnJhZ21lbnRzLnNpemUKICAgICAg ICB5ZGltID0geW9mZiArIEBmcmFnbWVudHMuc2l6ZSAqIDMKICAgICAgICB4ZGlyc3RhcnQgPSB4 b2ZmICsgbWF4X2xlbiArIDEKICAgICAgICBkYXRhID0gKDEuLnlkaW0pLm1hcHsgIiAiICogeGRp bX0KCiAgICAgICAgIyB3cml0ZSB0aGUgY29kZSBmcmFnbWVudHMKICAgICAgICBAZnJhZ21lbnRz LmVhY2hfd2l0aF9pbmRleCBkbyB8ZiwgaWR4fAogICAgICAgICAgICB5ID0geW9mZiArIGlkeCAq IDMgKyAxCiAgICAgICAgICAgIGRhdGFbeV1beG9mZiwgZi5zaXplXSA9IGYudG9fcwogICAgICAg ICAgICBkYXRhW3ldW3hkaXJzdGFydCArIGlkeF0gPSA/PgoKICAgICAgICAgICAgIyBhcHBlbmQg dGhlIGRpcmVjdG9ycwogICAgICAgICAgICB4ID0geG9mZiArIGYuc2l6ZQogICAgICAgICAgICBk YXRhW3ldW3hdID0gCiAgICAgICAgICAgICAgICBpZiBmLmNvbm5lY3RfdHJ1ZSBhbmQgZi5jb25u ZWN0X2ZhbHNlCiAgICAgICAgICAgICAgICAgICAgP3wKICAgICAgICAgICAgICAgIGVsc2lmIGYu Y29ubmVjdF90cnVlCiAgICAgICAgICAgICAgICAgICAgP14KICAgICAgICAgICAgICAgIGVsc2lm IGYuY29ubmVjdF9mYWxzZQogICAgICAgICAgICAgICAgICAgID92CiAgICAgICAgICAgICAgICBl bHNlCiAgICAgICAgICAgICAgICAgICAgP0AKICAgICAgICAgICAgICAgIGVuZAoKICAgICAgICAg ICAgaWYgZi5jb25uZWN0X3RydWUKICAgICAgICAgICAgICAgIGRhdGFbeS0xXVt4XSA9ID8+CiAg ICAgICAgICAgICAgICBkYXRhW3ktMV1beGRpcnN0YXJ0ICsgaW5kZXhfb2YoIGYuY29ubmVjdF90 cnVlICldID0gInYiCiAgICAgICAgICAgIGVuZAogICAgICAgICAgICAgICAgICAgIAogICAgICAg ICAgICBpZiBmLmNvbm5lY3RfZmFsc2UKICAgICAgICAgICAgICAgIGRhdGFbeSsxXVt4XSA9ID8+ CiAgICAgICAgICAgICAgICBkYXRhW3krMV1beGRpcnN0YXJ0ICsgaW5kZXhfb2YoIGYuY29ubmVj dF9mYWxzZSApXSA9ICJ2IgogICAgICAgICAgICBlbmQKICAgICAgICBlbmQKCiAgICAgICAgIyBy ZWRpcmVjdCB0byB0aGUgZmlyc3QgZnJhZ21lbnQKICAgICAgICBkYXRhWzBdWzBdID0gP3YKICAg ICAgICBkYXRhW3lvZmYgKyAxXVswXSA9ID8+CgogICAgICAgIGRhdGEuam9pbigiXG4iKQogICAg ZW5kCgoKICAgIGRlZiBpbmRleF9vZiggZnJhZ21lbnQgKQogICAgICAgIEBmcmFnbWVudHMuaW5k ZXgoIGZyYWdtZW50ICkKICAgIGVuZAoKZW5kCgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMj IyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKIyBFWEFNUExFOiBtYXgoeCx5KSAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMjIyMjIyMjIyMjIyMj IyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojeCA9IFZh cmlhYmxlLm5ldygwLDEpCiN5ID0gVmFyaWFibGUubmV3KDEsMSkKCiNmX2lucHV0ID0gRnJhZ21l bnQubmV3KCAiJjoje3guc2V0fSY6I3t5LnNldH1gIiApCiNmX3ggPSBGcmFnbWVudC5uZXcoICIj e3guZ2V0fS4iICkKI2ZfeSA9IEZyYWdtZW50Lm5ldyggIiN7eS5nZXR9LiIgKQoKI2ZfaW5wdXQu Y29ubmVjdF90cnVlID0gZl94CiNmX2lucHV0LmNvbm5lY3RfZmFsc2UgPSBmX3kKCiNjb2RlID0g Q29kZS5uZXcKI2NvZGUuYWRkIGZfaW5wdXQKI2NvZGUuYWRkIGZfeAojY29kZS5hZGQgZl95Cgoj cHV0cyBjb2RlLnNob3coMiwgMCkKI2V4aXQKCiAgICAKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMj IyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiMgRVhBTVBMRTogZXVjbGlk aWFuIGFsZ29yaXRobSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIyMjIyMjIyMj IyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKCiMg UmVtYXJrOiB0aGUgY29kZSB1c2VzIDE2LUJpdCB2YXJpYWJsZXMsIHNvIG9uZSBuZWVkcyB0d28g Y2VsbHMgdG8KIyBzdG9yZSBhIHZhcmlhYmxlLiAgVGhlcmVmb3JlLCByZWFkaW5nIGFuZCB3cml0 aW5nIG9mIHZhcmlhYmxlcyByZXF1aXJlcwojIGV4dHJhIGNvZGUsIHNvIHRoZSByZXN1bHRpbmcg cHJvZ3JhbSBpcyBxdWl0ZSBsYXJnZS4KCiMgVmFyaWFibGVzCnggPSBWYXJpYWJsZS5uZXcoMCww LDIpCnkgPSBWYXJpYWJsZS5uZXcoMiwwLDIpCgoKIyBDb2RlIGZyYWdtZW50cwojKysrKysgcmVh ZCBudW1iZXJzCmZfaW5wdXQgPSBGcmFnbWVudC5uZXcoICImI3t4LnNldH0mI3t5LnNldH0iICkK IysrKysrIGlmIHggIT0geQpmX2lmX3hfbmVfeSA9IEZyYWdtZW50Lm5ldyggIiN7eC5nZXR9I3t5 LmdldH0tIiApCiMrKysrKyBpZiB4ID4geQpmX2lmX3hfZ3RfeSA9IEZyYWdtZW50Lm5ldyggIiN7 eC5nZXR9I3t5LmdldH1gIiApCiMrKysrKyB0aGVuIHggPSB4IC0geQpmX3RoZW4gPSBGcmFnbWVu dC5uZXcoICIje3guZ2V0fSN7eS5nZXR9LSN7eC5zZXR9IiApCiMrKysrKyBlbHNlIHkgPSB5IC0g eApmX2Vsc2UgPSBGcmFnbWVudC5uZXcoICIje3kuZ2V0fSN7eC5nZXR9LSN7eS5zZXR9IiApCiMr KysrKyBwcmludCB4CmZfcHJpbnQgPSBGcmFnbWVudC5uZXcoICIje3guZ2V0fS4iICkKCiMgQ29u bmVjdCB0aGUgZnJhZ21lbnRzCmZfaW5wdXQuY29ubmVjdF90cnVlID0gZl9pZl94X25lX3kKCmZf aWZfeF9uZV95LmNvbm5lY3RfdHJ1ZSA9IGZfaWZfeF9ndF95CmZfaWZfeF9uZV95LmNvbm5lY3Rf ZmFsc2UgPSBmX3ByaW50CgpmX2lmX3hfZ3RfeS5jb25uZWN0X3RydWUgPSBmX3RoZW4KZl9pZl94 X2d0X3kuY29ubmVjdF9mYWxzZSA9IGZfZWxzZQoKZl90aGVuLmNvbm5lY3RfdHJ1ZSA9IGZfaWZf eF9uZV95CgpmX2Vsc2UuY29ubmVjdF90cnVlID0gZl9pZl94X25lX3kKCgojIGFkZCB0aGUgZnJh Z21lbnRzIHRvIHRoZSBjb2RlCmNvZGUgPSBDb2RlLm5ldwpbZl9pbnB1dCwgZl9pZl94X25lX3ks IGZfaWZfeF9ndF95LCBmX3RoZW4sIGZfZWxzZSwgZl9wcmludF0uZWFjaHt8ZnwgY29kZS5hZGQg Zn0KCiMgc2hvdyB0aGUgY29kZSAod2l0aCBzcGFjZSBmb3IgMiB2YXJpYWJsZXMgaW4gKDAsMCkg Li4gKDMsMCkpCnB1dHMgY29kZS5zaG93KCAwLCAxICkKCg== --nextPart1462683.XyMqu45Hlp--