5 kyu
Esolang Interpreters #2 - Custom Smallfuck Interpreter
1,216 of 4,044donaldsebleung
Loading description...
Esoteric Languages
Interpreters
Algorithms
Tutorials
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
nice kata, I found the solution in 2 days
Random tests in Python do not contain any loops or no-ops, therefore only testing a subset of the specified behaviour.
Python fork which implements better random testing: https://www.codewars.com/kumite/66c8182e4d7ff9aec7c3b877
If approved I'll port the changes to JS as well.
Most of the kata I solved in 30 minutes, but I can't get how the [ ] are suppose to be working..
Отличный ката, как и вся серия. Конечно хотелось бы при решении иметь более подробное описание задачи. Автору ката большое спасибо.
True, they could explicitly mention nested loops.
This comment has been hidden.
fixed in OP's fork
python new test framework is required. updated in this fork
Approved
Why does the C# tests not have an example of '[' and ']'? I do not understand how these work, could someone give a simple example of '[' and ']' in the code string along with the a tape string and the expected result?
answering my own question here are two C# unit tests for the brackets
Broken test
*[>*]expects all bits to be flipped, but it is only first bit that has to be flipped.You're wrong. Check better please. Please don't raise issues so lightly. In general, it is not reasonable to suppose without very solid and concrete elements that a fixed test could be wrong when a kata has been solved thousands of times like this one. Please refer to the documentation: https://docs.codewars.com/training/troubleshooting
Actually 5 loop tests are broken, check my solution.
What do you mean I am wrong? I checked that tests don't conform to kata description.
You didn't mention the language nor the initial state of the tape. Whether you're wrong or right is irrelevant, given that your issue report is lacking necessary information.
sisyphean task
No examples with '[' and ']' in C++. It's not quite clear for me how they work.
Same for Js.
Same for Lua.
Can someone please provide the expected result for the following TypeScript test? Only one failing for me and would like to debug in my local IDE. Thanks!
My code's logging of arguent values/lengths
Nevermind -- figured it out. Had to do with instances where I wasn't re-flipping the bit when the cell index didn't change because I was referencing the input tape (which wasn't flipping bits) and not the output tape
Thanks for a great kata @donaldsebleung - I'm starting to work on understanding interpreters (and I just started learning about esolangs) so this kata was a perfect exercise.
Also, it's just the right difficulty: not too difficult for a first experience but also not too trivial - you have to account for some complexity, and there are some good debugging cases.
Thanks again! Looking forward to working through the series and other related kata now.
[[]>>*>] How does this with a tape of 000 return 000?
Description states:
Hence:
0]. that is past the end.Help please!
[>*]00000.As I understand the brackets, the opening bracket (
[) checks the current value of the pointer in the data tape.If the current value is
0, then control jumps to the position after the closing bracket and executes that (in this example, the program terminates as there are no more commands).If the current value is
1, control passes to the next command (in this case>).Therefore, if I've got this right, this series of commands should immediately terminate because the data tape starts with
0so the opening bracket should jump control to beyond the closing bracket.But the testcase that I'm struggling with expects the output to be
011111, which means that the opening bracket found a0and passed control to the next command (>) i.e. the opposite of what I'm expecting.Any thoughts?
COBOL translation.
Reviewed, looks good to be approved.
Approved
From C++ test cases:
[[]*>*>*>],000is for some reason supposed to return 000, how???[- jump past matching], since everything is zero anyway*>- flip the first bit and go to the second*>- flip the second and go to the third*>- flip the third, go out of bounds and terminate since we're out of bounds.We flipped all three bits, the tape is now 111. My solution passes everything except for this one, even random tests.
So why are you still executing things inside this first
[? The matching]is the last character, so your pointer should go past it immediately.Damn, I didn't realize that "matching" doesn't mean "the next one you find", my bad then. Thanks for the quick reply.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
There should be fixed tests with input containing
[and]in JS at leastNice kata. However I think the description is misleading when saying Smallfuck terminates when [...] All commands have been considered from left to right. Indeed, for example in case the code is [>*] and the tape contains only '0', all inner commands are ignored. At first I understood I needed to check that every code's cell was executed at least once before ending, and it's not the case. IMHO description would be clearer if it said that the program terminates when code's pointer (sorry if pointer is not the correct word) goes out of bound, just like for the tape.
Poorly explained kata, and severe lack of examples to boot.
I pass all test_cases successfully,however after trying to attempt,compiler shows the next warning that leads to abortion. What am i doing wrong?
double free or corruption (out) UndefinedBehaviorSanitizer:DEADLYSIGNAL ==1==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x000000000000 (pc 0x7f294086da10 bp 0x7ffc8c9815c0 sp 0x7ffc8c981370 T1) ==1==The signal is caused by a READ memory access. ==1==Hint: address points to the zero page. ==1==WARNING: invalid path to external symbolizer! ==1==WARNING: Failed to use and restart external symbolizer! #0 0x7ff45c353a0f (/lib/x86_64-linux-gnu/libc.so.6+0x40a0f) #1 0x7ff45c39c966 (/lib/x86_64-linux-gnu/libc.so.6+0x89966) #2 0x7ff45c3a39d9 (/lib/x86_64-linux-gnu/libc.so.6+0x909d9) #3 0x7ff45c3aaf69 (/lib/x86_64-linux-gnu/libc.so.6+0x97f69) #4 0x429a1a (/workspace/test+0x429a1a) #5 0x426f1e (/workspace/test+0x426f1e) #6 0x426a27 (/workspace/test+0x426a27) #7 0x42662b (/workspace/test+0x42662b) #8 0x42d8f5 (/workspace/test+0x42d8f5) #9 0x425cdd (/workspace/test+0x425cdd) #10 0x7ff45c334bf6 (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6) #11 0x404619 (/workspace/test+0x404619)
UndefinedBehaviorSanitizer can not provide additional info. ==1==ABORTING
I guess you're probably trying to access a container's element (string or vector) with an invalid index, but it's hard to say. You can post your code with a spoiler flag in order to get further help, it's hard to help you without knowing your code (Undefined Behaviour gives few informations).
Anyway this is not a kata's issue (I've just solved this kata in C++ with no problem), but a personal question, so I close the issue.
How can check the output I failed? I do not see the code input. I only see the tape input and the output. Thanks
You should be able to print whatever you fancy but that depends on your language.
Anyway this is not a kata issue but a personnal question, so I close the issue.
C translation. Please review.
Description cannot be approved, recent changes from related record must be merged first. :)
Seeing a few questions on the bracket cmds, I thought I might try to offer (a rather verbose) explanation of these commands. Nomenclature: The string of commands (e.g. '>') I call 'code-tape' and the string of 0's and 1's (e.g. '10010') I call data-tape. Additionally, 'code pointer' points to the current cmd to execute
Can you give an example of tape and code with nested brackets? I don't understand what the situation is. My code works except with nested brackets. Thanks
If the program which makes you fail is small enough to be printed, you can print it and copy from the test output panel to your local IDE.
See if this paragraph of FAQ is of any help.
I second hobovsky: It's a fantastic practice and technique to print the test cases out from codewars; simple as printing the data to the screen; doing so you will see an example where a nested loop; for python (you will also get the tape, and proper output too; a gerat way to debug):
Awesome kata!
This comment has been hidden.
I have passed all the test cases,but the cost of time is over, so i failed!
Julia translation
I suggest to have the "bad source" with unmatched brackets in tests. That way the
[and]operations processing would be tested for not going out of the code bounds. I feel that my current solution would fail this way.Why I really like this kata is the fact that it was a good example of TDD. I didn't understood the jump description, but started implementing the other 3 commands and passed the user-tests. Of course I failed the final tests, but that is TDD => test - fail - refactore - pass. The explaination in the test-log was really helpfull and after understanding what [] are doing or are expected to do it was simply refactoring. To make sure my already implemented functionality is not broken I used the user-tests and that it what TDD is for: don't be afraid to change and only implement what is asked. Great learning effect - Thanks
I don't understand what symbols "[" and "]" do. Please give examples.
Yeah, even after reading the "Questions" tab I still don't understand how they work
Neither do I.
same
This comment has been hidden.
Because if 1 OP is 1 cycle, by jumping PAST you are saving 1 cycle, otherwise wasted.
Me gustó el ejercicio ♥
Any possibility of adding a Rust translation?
Write and submit one yourself? It's not people's job to make katas accessible in all languages.
C++ translation added. Please review!
Approved.
The instructions are so confusing !!!!
i got it this way :
[[][][]] the corresponding brackets for the bracket index 0 is the last one and vice versa . but it seems it's not this?
Can u explain me the right instruction plz, thanks!!
This comment has been hidden.
You have a cell which has a value of
0or1. Based on it and your position (i.e. if you're inside the loop or not), you choose the according action:I have it running perfectly locally, but when I attempt it stalls on the following:
"[>*]", "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
Instantanous locally, on your system it times out after 12 seconds.
If I alter the "Run Sample Tests" to contain the attempt stuff it runs perfectly fine. Only fails on the attempt.
If it's not a server problem, then you do actually enter an infinite loop somehow. You could add an operations counter and make it stop the function execution when it reaches some very big value (with a message to stdout ofc) to verify this.
This comment has been hidden.
You can always print the function inputs to the console, e.g.
That's so obvious I don't know why I didn't think of that...
gotta admit, it was difficult af, but in the end managed to finish it. Good job op!
Thanks for the encouraging words, glad you found it challenging and worthwhile :)
I was confused by the [ and ] brackets in the code, since they aren't mentioned in any of the examples of the instructions. But browsing through the comments I saw some testcases which helped me understand what exactly they do.
This comment has been hidden.
This comment has been hidden.
If i clearly understand the task, your test could never return True, with command like this. There are no * so input will be always equal to output (zeros string in this example). Moreover for first tape value (0) first command [ will jump to the las element of command string. It will be ] so interpreter will skip this command. If i miss something, let me know =)
Description is poorly written. The programming challenges should have clear and well defined instructions with primitive examples for basic cases of command. The trickiest command of "[" and "]" were not assigned any example cases in attempt. This description ruined the whole KATA experience for me.
The description is a bit confusing. Does the termination case "All commands have been considered from left to right" mean just "the end of command tape was reached" or all the commands should actually be performed? I consider the former and my code passes, but it would be nice if the description was fixed.
Can I get some extra fake internet points for making (possibly) the smallest Smallfuck interpretator? :P
Deleted Nevermind, I was confused... Now working on nested loops.
Is there a C# test case I can use for nested loops?
My code keeps timing out, and I can't print the input (my Console.WriteLine instructions aren't getting hit for whatever test is timing out), but I'm fairly certain it's taking too long to process code containing at least one nested loop.
In Visual Studio, my code runs fine against all the sample tests, and I "Simple Loop" test I devised myself, but I can't find any real-world examples of the kind of test that's causing my solution to timeout on Codewars. :(
It'd be really great to include such a test in the sample tests for this Kata.
Edit: Nevermind about the test. I found the bug in my FindMatchingBracket method, which was causing an infinite loop under certain circumstances. I've now successfully completed the Kata.
It was good, but it took me awhile to wrap my head around the requirements for [ and ]. I'd still definitely like to see a test using those under Sample Tests, and/or clearer instructions for what they mean.
As per the description it says, ']' - Jump back to matching [ (if value at current cell is nonzero). The statement in bracket 'if value at current cell is nonzero' is not correct. If we encounter ']' we need to always return back to matching '['.
Consider a scenario where matching '[' was encountered at 0 and current pointer is at non zero it needs to move forward.
you're wrong:
the 0 here is the value under the pointer, not the "address of the pointer in the tape". So
if '[' was encountered at 0, the value under the pointer IS 0 and you effectively move forward in any case.This comment has been hidden.
Your interpreter doesn't account for non-command characters - it fails to increment the instruction pointer (
index) in that case. Consider incrementing the instruction pointer unconditionally.Also, I think there might be a minor logical flaw in the way you handle
[and]which might be another possible cause of getting stuck in an infinite loop.This comment has been hidden.
The code snippet you provided does not handle nested brackets properly. For example, in the program shown below, it will match the following opening and closing brackets together which is incorrect:
That's definitely something I didn't think about, but the test case doesn't have any nested brackets so it should still be returning the correct result.
Would you mind posting your full solution here (and mark it as spoiler)?
This comment has been hidden.
You're actually failing test
[>*]with your code.You have a bug in the section of your code where you handle the command '[' and ']'.
Hint: What type does tapeList in your code hold?
hehe I was working on it on the train and noticed the mistake I made, thanks :) I got it to submit with the extra nested bracket code.
Hey, I've made a C# translation, please review and approve.
Many thanks for your contribution; reviewed and approved :D
This comment has been hidden.
The ']' command can also cause the pointer to move backwards.
This comment has been hidden.
I don't know, whether this is related to the codewars performance or not, but I keep getting this error while submitting my solution:
The server timed out running the request. This may be due to an issue with the backend server. Please try again.BTW: The example testcases are all passing fine.
Mostly likely this is a CW problem.
Have you tried preview.codewars.com?
duplicate comment
How to test that specific kata on preview.codewars.com?
Just replace
wwwwithpreview.You might need to log in on there again but otherwise everything's almost the same. Even saved kata code is across both sites.
Hi, I got the same problem with a Go implementation. I tried on preview and it worked after a while, but my level did not increase. Is it a feature of preview ?
Well. Got the exact same error. It's really strange. If my code would be inefficient, i would get a timeout, don't I? Other Katas are working fine, except this one: https://www.codewars.com/kata/the-millionth-fibonacci-kata Everytime i want to submit my solution, there is this network error :/
@zruf I had the same error but it worked at least one time on preview. I've just retried on it but now timeout occurs too. I think there may be a huge test case that causes the problem ...
@zruf Finally I finished it. It appeared that my code did not handle correctly loops and nested loops. It ran forever causing the timeout. Maybe you should have a look at that.Hint : you could run your code just to log the entries and test it quietly on your computer.
Same with my Python one, however I am pretty sure that it is a server issue as nothing is printed to output, even though I had a print statement at the beginning of the function.
Thanks @imatmati. You were right. I didn't handle nested loops correctly ;-) It's working now!
Very simple easy kata, actually easier than the 2kyu brainf__k :)
Wtf, this is a 4kyu one
Was about to say... :p
This kata slew me. Hot damn.
This comment has been hidden.
Upon reviewing your solution, the first question that comes to mind is, "Why doesn't your interpreter accept any arguments as input?" Your interpreter should receive two arguments, the first one being the Smallf**k code to be executed and the second one being the initial state of the memory tape.
By the way, the solution you posted above isn't rendering properly and is rather hard to read. Consider formatting it using Markdown next time.
Thank you for the tip, I'll learn about markdown and re-write the question in a more readable manner. As seen on edit counts, I spent some time trying to get it as readable as possible. And the interpreter has been accepting these arguments, I just forgot it while writing the pseudo-pseudo-code for the question.
No problem :D Since you marked your comment as a spoiler, you may directly copy and paste your current Python solution here (within a Markdown code block) instead of writing pseudo-code as people who haven't solved the Kata yet cannot see it. That way, it should be easier for me to test your current solution and potentially identify the problem. Cheers :D
This comment has been hidden.
@imprezobus,
Many thanks for posting your solution above; I have tested your solution and found the cause of the timeouts - your solution fails to increment
cwhenever it encounters a non-command character resulting in an infinite loop. I would suggest that instead of incrementingconly when the command is*,>or<, you should perhaps consider incrementingcunconditionally in your while loop. Hope this helps and don't hesitate to ping me again in case of any further problems.Cheers, donaldsebleung
You, kind sir, have just unlocked me. My code still fails, but now its a failure I can analyse myself, and I'm sure I'll finish it shortly - I was unsure if I did "[" and "]" properly, and now I know I didn't.
This is really an amazing Kata, with the quality of Test Cases being uncomparable to what I have seen here, and I will definitely finish all of those in the series.
I hope that you realise that your work is succesfull in making people better programmers - and therfore changing their lives for the better. Thank you.
@imprezobus,
Glad to hear that my comment has aided you in debugging your interpreter and many thanks for your kind words and compliments. Once you've completed every Kata in this Series and if you enjoy this Series then don't forget to check out my RoboScript series as well as it is also (to some extent) related to esoteric programming languages and how to interpret them.
Cheers, donaldsebleung
I were definitely planning to follow up on rest of your work once I finished this series. Best Regards, Michał Krukowski
This comment has been hidden.
This distinction doesn't matter, because:
[jumps on a], current cell must be 0 and so the]will never have any effectsI figured it out because I found the test cases with brackets you posted in this comment section but I reccomend that you include at least one example test case with brackets in the instructions or do a simple step by step work through of a code that includes brackets writing on a tape so it's easier to understand what you are trying to do.
This comment has been hidden.
AFAIK the test cases for this Kata do not specifically test against inefficient solutions so unless you deliberately come up with an extremely inefficient solution, all tests should be executed in around 2 seconds or so. Chances are that your solution doesn't handle
[]properly and ends up in some sort of infinite loop.If you still need further help, feel free to specify the language in which you are experiencing the problem and post your solution here (and mark it as a spoiler, of course) and I'll see if I can help :)
Thanks for reply, that means I messed it up
This comment has been hidden.
Resolving this Issue because:
A few things to note before you file an "Issue" on a Kata:
I am using JAVA
Thanks for taking the time to tell me which language you are referring to. Of course it's Java (again, sigh) - a few other users have commented that Java is a special snowflake here on Codewars in terms of writing and translating Kata.
If you are still stuck on this Kata and would like help regarding why the assertions are failing, please copy and paste the relevant test output here (including key details such as actual and expected values, and the arguments passed into your interpreter) so I may investigate this "Issue" and determine whether it is a problem of this Kata or a problem of your solution.
Additionally, you could also copy and paste your current solution here and mark it as a spoiler, and I'll see if I can spot the problem (I don't really know Java though). Hope this helps :)
Hi,
I checked it and the
actualandexpectedare effectively swapped in Java. I forked the translation to correct it. ;-)Cheers,
B4B
@Blind4Basics,
Many thanks for the fix, your fork of @ggmoy's Java Translation has been reviewed and approved :D
Cheers, donaldsebleung
P.S. B4B, a little bit off topic, but I would like to confirm once more that the order of arguments in a typical JUnit assertion is [message, ]expected, actual? I will make sure to keep that in mind when reviewing future Java translations :)
Implementing a simple TM in JavaScript was fun. One of my favorite kata so far. Looking forward to the next 2.
Glad to hear that you enjoyed it; don't forget to check out other Kata I have authored :D
I'm having an issue with the Java translation:
It states that I've passed all tests having 0 failures when I click on Attempt but the button doesn't switch to submit my final solution so I can't finish it and get the honor.
Can you please look into it?
Thanks.
Currently Codewars platform is experiencing issues. This is not a problem of the kata.
Thanks for the quick reply! I'll try again later then.
Thanks, great kata! After doing some other "interpreter" type katas, it was moderately easy :-)
Swift translation kumited. Please review and accept if satisfactory.
Many thanks for your contribution; reviewed and approved :D
Really good kata serie
This series makes me want to learn how compilers work.
Glad to hear that my Kata Series has piqued your interest in compilers and interpreters :D Don't forget to check out my other Kata Series as well :D ;)
This is also a really nice one.
Ruby-Translation kumited!
http://www.codewars.com/kumite/58d5c635ba746247150000db?sel=58d5c635ba746247150000db
Could you check and approve it, please?
Many thanks for your contribution; reviewed and approved :D
Java-Translation kumited!
http://www.codewars.com/kumite/58d3c04d7a4ea9bb2f00008f?sel=58d3c04d7a4ea9bb2f00008f
Could you check and approve it, please?
Approved :D
Python-Translation kumited!
http://www.codewars.com/kumite/58d2d9d51e4ac7002b000321?sel=58d2d9d51e4ac7002b000321
Could you check and approve it, please?
Many thanks for your contribution; reviewed and approved :D
Had a lot of fun doing this Kata, even a guy at my job got interested in it :D Thanks!
You're welcome, and glad you enjoyed it :D
A great challenge, Donald!
FYI, the link to 3rd esolang interpreter challenge is broken on the description page.
Thanks for the compliment, glad you enjoyed the challenge :D
And thanks for notifying me on the broken link, will be fixing it now :) It became broken because the site admin censored the f-word in the Kata name recently.
Should be fixed now :)
This comment has been hidden.
@glecbec,
I am aware that there aren't exactly many tests including loops in this Kata, partly because these test cases take quite a long time to make in my opinion and take even longer to manually trace them through to determine what output it will produce for a given tape. If you believe that there is a serious lack of test cases regarding loops, you can post a few more rigorous test cases here and I will be happy to add them to my Kata :D
Many thanks for your feedback and contribution :)
Cheers, donaldsebleung
Voilà:
These may not capture every edge case, but they at least are an example of one level of nesting that requires proper bracket matching.
Added, thanks a lot :D
i think that also some test whit '[[][]]' type of bracket will be nice i boted that my solution dosent work in this type of loops
The Lua version desperately needs these tests. I was at a complete loss until I found these.
Despite being oddly named, this kata was refreshingly exciting to solve!
Trivial having already done boolfuck since I was able to reusee my class for that, but still fun!
I'd recommend ordering all your *fuck Katas into a series with links to the others on each Kata since they are so related, build on eachother, and increase in complexity.
@nickkwest,
Glad you enjoyed completing my Kata :D
As for ordering all of my ____f**k Kata into a "series", I have already done it informally under the "You May Also Like" header where I included the links to the other Esolang Interpreter Kata I have authored in chronological order. Or do you recommend I remake this into a formal Kata Series with an actual name for the Series and related Kata being ordered by difficulty and such?
Many thanks for your precious feedback :D
Cheers, donaldsebleung
Actually, many thanks for your suggestion - I've just made my mind up to transform these 3 inter-related Kata into an official Kata Series with a shared description and such :D A fourth Kata in this Series is also well underway :D
Awesome, ya, I was suggesting the formal series option (though I didn't really know it yesterday). I've stumbled upon a couple other series and they make for a good experience. Since your's go together so well and build on eachother I think it works well as a series.
Glad you made it into a series, hope others find them and enjoy them.
TypeScript translation
This comment has been hidden.
@JebPotly,
You're welcome, glad you enjoyed my Kata that much :D
On another note, if you're up for a challenge, you may also want to try out this Kata of mine (if you haven't done so already).
Cheers, donaldsebleung
@JebPotly you weren't the only one, I too was a bit confused. I consider it to be a part of the exercise though, figuring out what the task on hand actually is.
Anyway, @donaldsebleung: loved the kata! Thanks for providing it :-)
This comment has been hidden.
Errr... WHAT!!???!?
And following your logic I marked yours as well even if I do not undertand this logic if yours...