G2048

Forum Attachments

Summary:

Optimize this program

G2048

Michael (guest) 23 Aug 2015 22:55

I've created a version of 2048 which I believe is the smallest which is coded in Ti-Basic. Can you make it smaller? If not, enjoy the program as-is!

PROGRAM:G2048
Goto Ø
Lbl M
If not(sum(L1
End
For(A,2,dim(L1
If L1(A:Then
For(B,A,2,~1
If L1(B)=L1(B-1) or not(L1(B-1
Then
L1(B-1)+L1(B → L1(B-1
0 → L1(B
1 → Ø
Else
2 → B
End:End:End:End:End
Lbl Ø
Delvar Ø 0identity(4 → [A]
SetupEditor G2048
Menu("2048","LOAD",L,"NEW",N
Lbl L
~1 → Ø
For(A,1,4)
For(B,1,4)
lG2048(4A+B-4 → [A](A,B
End:End
Lbl N
AxesOff
FnOff
ZStandard
ZInteger
Ø+1 → Ø
Repeat Ans=45
If Ø:Then
Repeat not([A](X,Y
randInt(1,4 → X
randInt(1,4 → Y
End
2+2(rand>.9 → [A](X,Y
End
ClrDraw
For(A,~36,36,18
5A/6
Line(A,~30,A,30
Line(~36,Ans,36,Ans:End
For(A,1,4
For(B,1,4
Text(15A-10,18B-5," " \\15sp
[A](A,B
If Ans
Text(15A-10,18B+1-2int(log(Ans)),Ans
End:End
Repeat Ans
Text(~1,0,90," " \\1sp
getKey
End
Delvar Ø
If Ans=25:Then
For(X,1,4
seq([A](B,X),B,1,4 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](B,X
End:End:End
If Ans=26:Then
For(X,1,4
seq([A](X,B),B,4,1,~1 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](X,5-B
End:End:End
If Ans=34:Then
For(X,1,4
seq([A](B,X),B,4,1,~1 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](5-B,X
End:End:End
If Ans=24:Then
For(X,1,4
seq([A](X,B),B,1,4 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](X,B
End:End:End:End
seq([A](int((A+3)/4),1+4fpart((A-1)/4)),A,1,16) → lG2048

Re: G2048

Trenly 24 Aug 2015 04:32

I didn't read it all thoroughly because it wasn't in a code block, but to me it seems like there might be a memory leak or two. I'll go and double check later.

Edit: I think all of your lines that read as below cause memory leaks because they are all in "if/then" loops and "for" loops.

If L: Goto M

Last edited on 24 Aug 2015 04:37 by Trenly Show more

Re: G2048

lirtosiast 24 Aug 2015 16:05

There are no memory leaks in this program. Memory leaks occur when an If:Then, While, or For block never reaches its End; here the For block reaches an End each time. The first iteration it reaches the End in the subroutine, and the second time it reaches the End in the main program.

A subprogram in this form has advantages: storing where to return to in the main program is unnecessary, as the For( has already been pushed onto the stack. Additionally it is possible to have statements like Michael's If:End that conditionally return to the main program. I commend Michael for finding this innovative way to implement subroutines.

Re: G2048

Michael2_3B 24 Aug 2015 04:41

First of all, please surround your code in [[ code ]] and [[ /code ]] (without the spaces). It looks better.

Secondly, you could definitely use this as a learning experience. I would recommend trying to use labels and gotos less, as it's very easy to go wrong with those and have memory leaks. For example,

For(L,~1,0
If L:Goto M
End

This will cause a memory leak. I don't even understand why you have a for loop there in the first place though, since Goto M will do the exact same thing. Even then you will still have a memory leak though. You just need to make sure that where the goto is jumping to doesn't jump into or out of a code block that's not in the same code block as the goto. When I say code block, I'm sure you know that I mean things like If…Then…End or loops such as Repeat or While or For(.

Third:

If not(sum(L1
End

There is no point to this. I could be wrong, but I believe that End is useless. If you're wanting to stop the program, try the command "Stop" instead. Along with it should be a ClrHome and other cleanup things that you need.

There are probably more issues that could be pointed out, but those are the one's I noticed at a quick glance.

Re: G2048

earthnite 24 Aug 2015 21:25

It is possible to use Lbl and Goto to jump out of code blocks and not cause memory leaks, one an easy way to make sure there are no memory leaks is to indent the program and make sure Lbl and Goto are on the same level on indentation, but, it is possible to use Lbl and Goto to give the same section of code different indentation at different parts in the program.

Even though the use of Lbl and Goto are likely to cause memory leaks, that is not always the case.

The indented version of the code, ignoring indentation caused by Lbl and Goto

PROGRAM:G2048
Goto Ø
Lbl M
If not(sum(L1
End
For(A,2,dim(L1
  If L1(A
  Then
    For(B,A,2,~1
      If L1(B)=L1(B-1) or not(L1(B-1
      Then
        L1(B-1)+L1(B → L1(B-1
        0 → L1(B
        1 → Ø
      Else
        2 → B
      End
    End
  End
End
End
Lbl Ø
Delvar Ø 0identity(4 → [A]
SetupEditor G2048
Menu("2048","LOAD",L,"NEW",N
Lbl L
~1 → Ø
For(A,1,4)
  For(B,1,4)
    lG2048(4A+B-4 → [A](A,B
  End
End
Lbl N
AxesOff
FnOff
ZStandard
ZInteger
Ø+1 → Ø
Repeat Ans=45
  If Ø
  Then
    Repeat not([A](X,Y
      randInt(1,4 → X
      randInt(1,4 → Y
    End
    2+2(rand>.9 → [A](X,Y
  End
  ClrDraw
  For(A,~36,36,18
    5A/6
    Line(A,~30,A,30
    Line(~36,Ans,36,Ans:End
    For(A,1,4
      For(B,1,4
        Text(15A-10,18B-5," " \\15sp
        [A](A,B
        If Ans
        Text(15A-10,18B+1-2int(log(Ans)),Ans
      End
    End
    Repeat Ans
    Text(~1,0,90," " \\1sp
    getKey
  End
  Delvar Ø
  If Ans=25
  Then
    For(X,1,4
      seq([A](B,X),B,1,4 → L1
      For(L,~1,0
        If L
        Goto M
      End
      For(B,1,4
        L1(B → [A](B,X
      End
    End
  End
  If Ans=26
  Then
    For(X,1,4
      seq([A](X,B),B,4,1,~1 → L1
      For(L,~1,0
        If L
        Goto M
      End
      For(B,1,4
        L1(B → [A](X,5-B
      End
    End
  End
  If Ans=34
  Then
    For(X,1,4
      seq([A](B,X),B,4,1,~1 → L1
      For(L,~1,0
        If L
        Goto M
      End
      For(B,1,4
        L1(B → [A](5-B,X
      End
    End
  End
  If Ans=24
  Then
    For(X,1,4
      seq([A](X,B),B,1,4 → L1
        For(L,~1,0
          If L
          Goto M
        End
        For(B,1,4
          L1(B → [A](X,B
        End
      End
    End
  End
  seq([A](int((A+3)/4),1+4fpart((A-1)/4)),A,1,16) → lG2048

It appears that the extra ends in the sub program cancel out the missing ends in the main program. If you follow the code, you will find that the program structure in this program is quite…interesting.

*How to tell if there are memory leaks in a program
-Follow the code and keep track of the stack
-If the stack can go below 0, you have the opposite problem
-If the stack goes to infinity, you have a memory leak
-If the program ends with stuff in the stack, no problem, the stack is cleared when the program ends

For example, this program does not cause a memory leak, even though the stack is at 100 at the end of the program

0→A
Lbl A
If A<100
Then
  A+1→A
  Goto A

Good job Michael, there are many things to be learned about this program.

Re: G2048

Michael2_3B 24 Aug 2015 23:26

Wow, okay then, thanks.

The program he made was very confusing to me, and it still is. Honestly that's not how I would structure or even think about coding a program, but I guess it works…

I guess I can try to learn from this program, but overall I think I don't think I'll need this level of complexity in the future.

Michael (guest) 25 Aug 2015 03:55

I structured it this way, with internal subprograms, because to me, one large program is better than several smaller programs.

Re: G2048

kgmstwo 26 Aug 2015 15:50

This is somewhat misleading. Your example program that "does not cause a memory leak" actually does cause a memory leak- like you said, the stack is at 100. That is the leaked memory, which is inaccessible for the remainder of the program and could also slow the calculator down for the remainder of the program according to the wiki. Causing the stack to "go to infinity" will cause a memory error.

Michael's method of internal subprograms is a version of the "branching out of loops" section from the subprograms page, which is derived from Brad Wentz's looptrick. It's really cool and new to me- I'd always just avoided Goto like the plague!

Re: G2048

earthnite 27 Aug 2015 00:01

The reason I say this does not cause a memory leak is because this program takes a fixed amount of memory, like the following code:

Repeat 1
  Repeat 1
    Repeat 1
      Repeat 1
        Repeat 1
          Repeat 1
            Repeat 1
              Repeat 1
                Repeat 1
                  Repeat 1
                    ...you get the idea

This could take a lot of memory, but it does not cause ERR:MEMORY unless your calculator simply does not have enough memory to run the program. Imagine a very large program that creates a very large stack, that does not mean there is a memory leak, it just means it takes up a lot of memory. Not that the above programs are a good way to code, I just didn't feel like writing a program to do something useful. Also, think applications in recursion, could take a lot of memory, but could also be very useful, at the cost of a memory intensive program.

-Programs that can take an infinite amount of memory are a problem.
-Programs that take a very large amount of memory are ok, but should be avoided if possible.

Last edited on 27 Aug 2015 00:06 by earthnite Show more

Re: G2048

kgmstwo 27 Aug 2015 03:30

I understood you the first time. As the page on memory-leaks says, a memory leak can cause, but is not the same as, an ERR:MEMORY; and there is also an actual disadvantage to writing programs like you example "not a memory leak" programs. A memory leak is when you load up the stack with pointers that your program will never use, which you rely on the termination of the program to clear off the stack. Why should you worry about a finite (or "fixed" as you called it) memory leak? In addition to reducing the amount of memory the program has to allocate variables, due to a bug this will apparently also slow down the program. That's not to say that loading up on the stack is bad, just like you said, sometimes it is needed. The whole reason for the name "memory leak" is that you might load up the stack with things that you don't need, and it's just left their taking up memory until the program exits.

Last edited on 27 Aug 2015 06:19 by kgmstwo Show more

Re: G2048

earthnite 27 Aug 2015 05:16

Ok, good clarification, I was on the assumption that said program required such a structure, not that the example programs were using the structure effectively.

Michael (guest) 24 Aug 2015 13:13

Those For loops go to an internal subprogram (the lines in between Lbl M and Lbl Ø).

The If sum(not(L1 actually is part of the subprogram, and exits out of the subprogram if L1 is empty.

Here's the code:

PROGRAM:G2048
Goto Ø
Lbl M
If not(sum(L1
End
For(A,2,dim(L1
If L1(A:Then
For(B,A,2,~1
If L1(B)=L1(B-1) or not(L1(B-1
Then
L1(B-1)+L1(B → L1(B-1
0 → L1(B
1 → Ø
Else
2 → B
End:End:End:End:End
Lbl Ø
Delvar Ø 0identity(4 → [A]
SetupEditor G2048
Menu("2048","LOAD",L,"NEW",N
Lbl L
~1 → Ø
For(A,1,4)
For(B,1,4)
lG2048(4A+B-4 → [A](A,B
End:End
Lbl N
AxesOff
FnOff
ZStandard
ZInteger
Ø+1 → Ø
Repeat Ans=45
If Ø:Then
Repeat not([A](X,Y
randInt(1,4 → X
randInt(1,4 → Y
End
2+2(rand>.9 → [A](X,Y
End
ClrDraw
For(A,~36,36,18
5A/6
Line(A,~30,A,30
Line(~36,Ans,36,Ans:End
For(A,1,4
For(B,1,4
Text(15A-10,18B-5," " \\15sp
[A](A,B
If Ans
Text(15A-10,18B+1-2int(log(Ans)),Ans
End:End
Repeat Ans
Text(~1,0,90," " \\1sp
getKey
End
Delvar Ø
If Ans=25:Then
For(X,1,4
seq([A](B,X),B,1,4 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](B,X
End:End:End
If Ans=26:Then
For(X,1,4
seq([A](X,B),B,4,1,~1 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](X,5-B
End:End:End
If Ans=34:Then
For(X,1,4
seq([A](B,X),B,4,1,~1 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](5-B,X
End:End:End
If Ans=24:Then
For(X,1,4
seq([A](X,B),B,1,4 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](X,B
End:End:End:End
seq([A](int((A+3)/4),1+4fpart((A-1)/4)),A,1,16) → lG2048

Also, I didn't know how to put in code blocks. :)

Shorter

kgmstwo 26 Aug 2015 16:14

PROGRAM:G2048
Goto Ø
Lbl M
If not(sum(L1
End
For(A,2,dim(L1
If L1(A:Then
For(B,A,2,~1
If L1(B)=L1(B-1) or not(L1(B-1
Then
L1(B-1)+L1(B → L1(B-1
0 → L1(B
1 → Ø
Else
2 → B
End:End:End:End:End
Lbl Ø
Delvar Ø 0identity(4 → [A]
SetupEditor G2048
Menu("2048","LOAD",L,"NEW",N
Lbl L
~1 → Ø
For(A,1,4)
For(B,1,4)
lG2048(4A+B-4 → [A](A,B
End:End
Lbl N
AxesOff
FnOff
ZStandard
ZInteger
Ø+1 → Ø
Repeat K=45
If Ø:Then
Repeat not([A](X,Y
randInt(1,4 → X
randInt(1,4 → Y
End
2+2(rand>.9 → [A](X,Y
End
ClrDraw
For(A,~36,36,18
5A/6
Line(A,~30,A,30
Line(~36,Ans,36,Ans:End
For(A,1,4
For(B,1,4
Text(15A-10,18B-5," " \\15sp
[A](A,B
If Ans
Text(15A-10,18B+1-2int(log(Ans)),Ans
End:End
Repeat Ans
Text(~1,0,90," " \\1sp
getKey→K
End
Delvar Ø
For(X,1,4
seq([A](B,X(K=25 or K=34)+B(K=24 or K=36),B(K=25 or K=34)+X(K=24 or K=36),1,4 → L1
For(L,~1,0
If L:Goto M
End:For(B,1,4
L1(B → [A](B(K=25)+X(K=26)+(5-B)(K=34)+X(K=24),X(K=25)+(5-B)(K=26)+X(K=34)+B(K=24)
End:End:End
seq([A](int((A+3)/4),1+4fpart((A-1)/4)),A,1,16) → lG2048

I used piecewise-expressions to combine the code for the four arrow key presses.

Last edited on 27 Aug 2015 03:58 by kgmstwo Show more

Re: Shorter

lirtosiast 27 Aug 2015 02:02

Nice golf, but you can now also eliminate the subroutine calling code by writing it inline.

Re: Shorter

kgmstwo 27 Aug 2015 03:05

PROGRAM:G2048
Delvar θ 0identity(4 → [A]
SetupEditor G2048
Menu("2048","LOAD",L,"NEW",N
Lbl L
‾1 → θ
List►matr(seq(⌊G2048(4A-3,A,1,4),seq(⌊G2048(4A-2,A,1,4),seq(⌊G2048(4A-1,A,1,4),seq(⌊G2048(4A,A,1,4)→ [A]
Lbl N
AxesOff
FnOff
ZStandard
ZInteger
θ+1 → θ
Repeat K=45
If θ:Then
Repeat not([A](X,Y
randInt(1,4 → X
randInt(1,4 → Y
End
2+2(rand>.9 → [A](X,Y
End
ClrDraw
For(A,‾36,36,18
5A/6
Line(A,‾30,A,30
Line(‾36,Ans,36,Ans:End
For(A,1,4
For(B,1,4
Text(15A-10,18B-5," " \\15sp
[A](A,B
If Ans
Text(15A-10,18B+1-2int(log(Ans)),Ans
End:End
Repeat Ans
Text(‾1,0,90," " \\1sp
getKey→K
End
Delvar θ
For(X,1,4
seq([A](B,X(K=25 or K=34)+B(K=24 or K=36),B(K=25 or K=34)+X(K=24 or K=36),1,4 → L₁
For(A,2,dim(L₁)-2dim(L₁)(not(sum(L₁
For(B,A,2,‾1+2not(L₁(A)
L₁(B)=L₁(B-1) or not(L₁(B-1→Z
not(Z)L₁(B-1)+Z(L₁(B-1)+L₁(B → L₁(B-1
not(Z)L1(B → L1(B
not(Z)θ+Z → θ
ZB+not(Z)2 → B
End:End
For(B,1,4
L₁(B → [A](B(K=25)+X(K=26)+(5-B)(K=34)+X(K=24),X(K=25)+(5-B)(K=26)+X(K=34)+B(K=24)
End:End:End
seq([A](int((A+3)/4),1+4fpart((A-1)/4)),A,1,16) → lG2048

Nice! Inlining also lets you get rid of the surrounding for loop over L.
I piecewised out the conditional on sum(L₁ and L₁(A into their respective for loops, and the assignments that were in the subprogram. You could also substitute Z if you wanted to eliminate one more line.
I also replaced characters using the ones from the char box. The ~ for the negative sign had been really bothering me.

EDIT:

I also replaced

For(A,1,4)
For(B,1,4)
⌊G2048(4A+B-4 → [A](A,B
End:End

with

List►matr(seq(⌊G2048(4A-3,A,1,4),seq(⌊G2048(4A-2,A,1,4),seq(⌊G2048(4A-1,A,1,4),seq(⌊G2048(4A,A,1,4)→ [A]

Last edited on 27 Aug 2015 03:58 by kgmstwo Show more