Collatz Tag System – The Daily Programmer #317

Collatz Tag System – The Daily Programmer #317


Hey FreeCodeCamp, welcome to another of the daily programmer webseries video And the problem today we’re going to be talking about is number 317 called a collatz tag system This one’s pretty straightforward And it shouldn’t take too long to cover, so let’s go ahead and talk about it on the whiteboard, break it down, and then implement it in Javascript. Alright, so the Collatz tag system is kind of defined like so basically you need to give it some input, for instance: a a a We need to continuously Pop off and append different things onto this queue or list based on these production rules so the algorithm kind of works like so: we need to remove the first two characters, and then we look at the first character and append that to the end, so in this case we remove these two, and we append BC at the end and we continue doing this process until we reach a halt case, in which our q is equal to the length of one. So we should end up stopping this whole simulation when we hit the final input of A. So hopefully that made sense. If not, let’s go ahead and walk through a couple of steps and this is going to run for at least like 20 or 30 iterations So I’m not going to go through all them, but again starting off the input AAA We remove the first two characters which leaves us with this one here So we have ‘a’ and then we append to the end whatever the first character was every move so in this case I have ABC So variation two we’re going to remove AB Which leaves us with C and then we’re going to look what A should convert to at the end, so again, this is going to be a BC iteration three, we remove CB which leaves us with C and we find what C converts to which is triple a Keep doing that process Where we remove CA C converts to three A’s And we continuously do that Until we hit our whole case which will be A so this should be pretty obvious that you need some type of loop where you just keep on looping over your original input while it’s greater than or equal to 2, right, because when you reach the string length of one that’s when you’re done so you’re probably need some type of while loop and you need to keep on looping and Doing those two operations where we remove the first two characters, look at what the first character was, and then append to the end of the input based on these production rules. So last time just to make it clear. Let’s write it down. We say: Loop while input length Greater than or equal to two remove first two characters Append to input based on first character. And then you just keep on repeating that. So that’s pretty easy pseudocode We should be able to map that to Javascript So let’s go ahead and go to code panning try to implement this algorithm and see if we can reproduce the Collatz tag system Hi, this is pretty fun to do – it’s really short and simple, so let’s get to it. The first thing we need to do is the query function, so I’m going to call this function ‘function tag system’, and it’s going to take an input which is going to be or character array or string So I’ll just call it ‘tape’ since I guess the tag system does something on the tape I don’t really look into it too much, but if you wanna read the Wikipedia Maybe talk about it in the comments or discussion of the subreddit Maybe you can learn more about it, but I’m just trying to go over the algorithm but anyway, so we have a Function called tag system, which I’m just going to go ahead and return, um.. ‘steps’. So in this case. I’ll say const steps is equal to an empty array and that’s going to be a Barrier Bowl or an array where we can keep track of all the steps and print them out in the console. And then down here just to get set up, I’ll go ahead and call tag system with Triple-A So at this point, we have a function called tax systems, it’s going to create an array of steps and somewhere in the algorithm in the middle we’re going to push those steps one by one as we iterate over the different, um, the rules and whatnot So the second thing that’s kind of useful to do is let’s kind of create a hash map so we can map the production rules of what the first character should be to what it needs to be appended to at the end so we can say const rules is equal to an array or an object where a maps to (I think that one maps to BC) B maps to A and C maps to triple A So now we have our production rules where we can easily just ask it: Okay, if I start with an A what do I need to append? Well, it’s going to be a- BC If I ask for a C it’s gonna give us 3 a’s and we’ll see what that’s going to do later on So then to our logic that we wrote out those three different steps: the first one is while the tape is still greater than or equal to length of 2 alright, so that means we still have more than just a single A we need to continuously do some step. And at this point we can say steps.push the tape So what is the value of the current string, or tape, at this iteration, and we’re just going ahead and push that into steps and then The second part of the rule was removing the first two characters so we can do tape.substring of 2 to give us everything after the two characters and set tape equal to that so that will set tape equal to itself Cut off the first two characters, but then we also need to append something at the very end, right? Which is where our production rules come in so we can say plus Rules and then we can say tape of index 0, which was the very first character, and then finally we do steps.push and push the final result of the tape and then of course return steps at the end so now I’m going to go ahead and run this code, and we see that it does print out all the steps so it starts with AAA, it goes ABC, CBC, CAAA, AAAAA, and then continuously goes on until it reaches the very last step where it just gets an A. And you can try this with, you know, various different inputs to see what happens, so I’ll try it with two ways and see what the output is And it just gives us three steps. I could try it with four A’s I’m sure the output’s gonna be much longer. So just make this a little bit easier to read let’s go ahead and print this out stringified, so I can say JSon.stringify – Stringify – and then pass it the tag systems, pass it ‘null’, pass it 2, For the indentation level – and then of course give us some colons there, or commas I mean, clear this, go ahead and run this, All right So now I can actually show you since it was going off the screen before, all the different console outputs of all the steps that it takes for it to reach that ending halting character of A. Cool, so that pretty much wraps up the whole problem of how do you solve the Collatz tag system in that subreddit. It’s pretty straightforward You know, just keep on looping over the tape, or the string, remove the first two characters and then append to the end whatever the production rules tell you to append, and then just continuously run this until we reach the halting case, which will just be a single character A, and then print out the steps at the end. And that’s all we do. So hopefully this tutorial is pretty good, and hopefully this kind of challenged your mind a little bit. Be sure to like this video if you thought I was good and subscribe to freecodecamp below. Alright, thanks for watching.

5 thoughts to “Collatz Tag System – The Daily Programmer #317”

  1. This is my recursive solution:

    const collatz = (_, firstTwo, rest = '') =>
    rest + { a: 'bc', b: 'a', c: 'aaa' }[firstTwo[0]]

    function tagSystem(tape) {
    console.log(tape)

    if (tape.length > 1)
    tagSystem(tape.replace(/^(w{2})(w*)/, collatz))
    }

Leave a Reply

Your email address will not be published. Required fields are marked *