[SPOILERS] Novice's nominal nonchalance

[zakalwe]

I finally beat 19, but i got a 1/10 in steps and 2/10 in boxes. I'm guessing there's a recursion-based solution that i didn't go for

Major kudos for solving it without recursion, though! That sounds painful.

[pindicator]

After solving all the puzzles once i made myself go to a coffee shop snd get away from the whole thing. So what am i doing at said coffee shop? Writing out potentially better solutions to 19

[Ichabod]

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

I know that what I wrote is confusing, but I'm really having trouble with it. Guess my high school level math and logic reached their limit...

[pindicator]

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

I know that what I wrote is confusing, but I'm really having trouble with it. Guess my high school level math and logic reached their limit...

Yeah, I'm not doing too hot with it either. Either I freeze the game or have two arrows in my Keep Uniq box (or both) - I'm just not seeing something conceptually

[pindicator]

Okay, got it Took a while, but once recursion clicked getting a genius on 19 wasn't too rough

[zakalwe]

I made it too, although my solution is slightly "wasteful" because...

I'm abusing the unbounded storage by letting a Store box double as a Redirect.

My stats:



The solution:

The algorithm is:
1. If the string is empty, you're done. (Checked using Store->Load->Compare.)
2. Delete all occurrences of the first character (saving it in storage throughout).
3. Recursively remove all duplicates in the remaining string.
4. Insert the original first character at the head of the string.

[pling]

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

Spoilering this, coz you might be enjoying figuring it out for yourself and I wouldn't want to ruin that by trying to explain it (If I even make enough sense to help )

The first time it comes out of the box it's empty, then on the next level out you load a character in and it's not empty when it exits that time. Remember it does the thing after the recursion box every time it pops up a level of the recursion. To understand it, it helps to step through the whole thing but the little animation you get from the puzzle just zooms past the recursion levels. I don't know if that makes enough sense to help?

Here's what my solution to 17 actually does when stepping through the first test case "aaaa" -> "bcde" (and using a longish test to work through helps me to follow what's going on when I think about it):

Code:

aaaa
ENTER PROGRAM
aaaa
test: is it empty? no
aaaa
increment all characters
bbbb
store first character [store contains: b]
bbbb
delete first character
bbb
  ENTER RECURSION LEVEL 1
  bbb
  test: is it empty? no
  bbb
  increment all characters
  ccc
  store first character [store contains: cb]
  ccc
  delete first character
  cc
    ENTER RECURSION LEVEL 2
    cc
    test: is it empty? no
    cc
    increment all characters
    dd
    store first character [store contains: dcb]
    dd
    delete first character
    d
      ENTER RECURSION LEVEL 3
      d
      test: is it empty? no
      d
      increment all characters
      e
      store first character [store contains: edcb]
      e
      delete first character
      []
        ENTER RECURSION LEVEL 4
        []
        test: is it empty? YES!
        []
        EXIT RECURSION LEVEL 4
      []
      load character out of storage [store contains: dcb]
      e
      EXIT RECURSION LEVEL 3
    e
    load character out of storage [store contains: cb]
    de
    EXIT RECURSION LEVEL 2
  de
  load character out of storage [store contains: b]
  cde
  EXIT RECURSION LEVEL 1
cde
load character out of storage [store empty]
bcde
EXIT PROGRAM
bcde

[zakalwe]

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

I know that what I wrote is confusing, but I'm really having trouble with it. Guess my high school level math and logic reached their limit...

As an introduction to recursion, this puzzle game is probably quite brutal. You could try reading about it on Wikipedia first.

One thing to keep in mind is that hardware cannot actually be recursive in the sense it's depicted in this game. That would require infinitely nested and minute circuitry. In reality, recursion is a software abstraction that builds on so-called stacks. The Store and Load boxes in the game actually implement a stack, so there is technically no need to ever use recursion in this game, beyond saving space on the board (or if the Store/Load boxes are unavailable).

You are right that you need a "base case" that breaks the recursion, although it doesn't have to be implemented using the IsEmpty box. Some kind of conditional test is always required, though, or you will recurse infinitely. Generally, all recursive functions tend to be structured as follows:

Code:

IF <base case> THEN:
  <trivial solution>
ELSE:
  <incremental step(s) converging towards the base case>
  <recurse on simplified sub-problem(s)>

In other words, you try to simplify the problem somehow, and make one or more recursive calls to solve the simpler sub-problems.

[zakalwe]

I also found a neat 7-box solution to level 12:

It completed in 1400 steps, for 9/10. It can't get a perfect score, because the inner loop is four boxes long. Obviously 10/10 for boxes, though.

[Ichabod]

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

Spoilering this, coz you might be enjoying figuring it out for yourself and I wouldn't want to ruin that by trying to explain it (If I even make enough sense to help )

The first time it comes out of the box it's empty, then on the next level out you load a character in and it's not empty when it exits that time. Remember it does the thing after the recursion box every time it pops up a level of the recursion. To understand it, it helps to step through the whole thing but the little animation you get from the puzzle just zooms past the recursion levels. I don't know if that makes enough sense to help?

Here's what my solution to 17 actually does when stepping through the first test case "aaaa" -> "bcde" (and using a longish test to work through helps me to follow what's going on when I think about it):

Code:

aaaa
ENTER PROGRAM
aaaa
test: is it empty? no
aaaa
increment all characters
bbbb
store first character [store contains: b]
bbbb
delete first character
bbb
  ENTER RECURSION LEVEL 1
  bbb
  test: is it empty? no
  bbb
  increment all characters
  ccc
  store first character [store contains: cb]
  ccc
  delete first character
  cc
    ENTER RECURSION LEVEL 2
    cc
    test: is it empty? no
    cc
    increment all characters
    dd
    store first character [store contains: dcb]
    dd
    delete first character
    d
      ENTER RECURSION LEVEL 3
      d
      test: is it empty? no
      d
      increment all characters
      e
      store first character [store contains: edcb]
      e
      delete first character
      []
        ENTER RECURSION LEVEL 4
        []
        test: is it empty? YES!
        []
        EXIT RECURSION LEVEL 4
      []
      load character out of storage [store contains: dcb]
      e
      EXIT RECURSION LEVEL 3
    e
    load character out of storage [store contains: cb]
    de
    EXIT RECURSION LEVEL 2
  de
  load character out of storage [store contains: b]
  cde
  EXIT RECURSION LEVEL 1
cde
load character out of storage [store empty]
bcde
EXIT PROGRAM
bcde

I really can't understand recursion. It doesn't seem to make sense, however I look at it. As far as I can see, the only way of breaking a recursion loop (on stages 17 and 18) is by adding that "is it empty?" box. So how come the solution that comes out of the recursion box is not empty?

I know that what I wrote is confusing, but I'm really having trouble with it. Guess my high school level math and logic reached their limit...

As an introduction to recursion, this puzzle game is probably quite brutal. You could try reading about it on Wikipedia first.

One thing to keep in mind is that hardware cannot actually be recursive in the sense it's depicted in this game. That would require infinitely nested and minute circuitry. In reality, recursion is a software abstraction that builds on so-called stacks. The Store and Load boxes in the game actually implement a stack, so there is technically no need to ever use recursion in this game, beyond saving space on the board (or if the Store/Load boxes are unavailable).

You are right that you need a "base case" that breaks the recursion, although it doesn't have to be implemented using the IsEmpty box. Some kind of conditional test is always required, though, or you will recurse infinitely. Generally, all recursive functions tend to be structured as follows:

Code:

IF <base case> THEN:
  <trivial solution>
ELSE:
  <incremental step(s) converging towards the base case>
  <recurse on simplified sub-problem(s)>

In other words, you try to simplify the problem somehow, and make one or more recursive calls to solve the simpler sub-problems.

Thanks, Pling and Zakalwe, now I think I got it. I haven't realized that the recursion had levels, so now I can at least make sense of my lvl 17 and 18 solutions. After the first time it breaks the recursion loop with the conditional box and exit the grid, it'll keep on going on the rest of the previous level path, exiting through the recursion box (and until it ends the recursion levels.

That's pretty fascinating stuff for my untrained mind. :D