Directory:

1. End-seeking weirdness: problem statement, problem solution
   
2. Chaining simple Ifs: problem statement, problem solution.
   

---

You may be aware that TI-BASIC's control flow is somewhat unique. Unlike many languages, which are pre-parsed to identify which blocks of code belong to each conditional, TI-BASIC handles control flow line-by-line, as the program is running. You're likely familiar with the fact that you shouldn't put Goto's in If-Then blocks because of a memory leak; this is because of the parser's efforts to keep track of control flow.

To implement the control flow that programmers are familiar with, many statements in TI-BASIC can jump to the nearest End at the same depth as the original statement: If-Then without Else, the Else statement itself, and For( and While if their loop condition is not met.

Because of incorrect assumptions in the TI-BASIC parser, it is possible for two different control flow statements to find the same End when looking for a jump destination. The puzzle is to construct a program where this actually happens. A further puzzle asks if it is possible for three or more different control flow statements to find the same End, etc. No illegal tokens, no crazy parser bugs, etc.

I think the easiest way to keep this puzzle spoiler-free is for you to DM me your solutions, and I'll evaluate them myself.

A final list of people who sent me submissions that passed my tests, in order of my receiving them:

1. Zeroko, using a different method than my solution.
   
2. fghsgh, using the same technique as Zeroko.
   
3. commandz, using the same technique as Zeroko.
   
4. LogicalJoe, using the same method as my solution.
   
5. pi644721, using the same method as my solution.
   
6. Wavejumper3, using the same method as my solution.
   
7. Zeroko and fghsgh devised a joint solution using the same method as my solution.
   
8. Kerm, using the same method as my solution.
   
9. Merth, using the same method as my solution but ??? TI-82 only???
   
10. linkjt9, using the same method as my solution.
    

I'll release my solution to this puzzle on 8/10 or after two correct submissions, whichever is later; feel free to discuss your observations in this thread.

A text file with the solution I will post has md5 hash 0a3c7e77d61ecb02cf2f4f8e22a12354.

My observations are this was a fun puzzle! Even though I misinterpreted it the first time around and sent you a wrong submission the second time

Also, my calculator has a broken screen, so I should get a bonus point for that:

Well, this was a lot of fun, and I’m happy to see that so many people submitted solutions (over 80% of the people who submitted solutions eventually produced a correct one, which is fantastic to see!).
Here's a very similar solution to the one that spawned this puzzle (with some pedagogical changes):

Code:

Ignoring the control-flow catastrophe in the middle, let’s take for granted that the outer For( loop runs exactly twice, once with K=0 and once with K=1. Let’s consider each of these cases individually. We’ll first consider the K=1 case, as it is more straightforward than the K=0 case.

---

Case: K=1

If 1
Then
Goto A
End
While 0
Lbl A
Else
End

The bolded code is the path taken. Remember, the calculator executes the program line by line, so a Lbl/Goto in the middle of an If statement like this does not affect the interpretation of the If statement.
So, stepping through this program:

• If 1:Then: The calculator sets aside a little piece of memory to remember that it had taken a true If-Then statement.
  
• Goto A: the Goto is taken (without disturbing that little piece of memory set aside earlier)
  
• Else: The Else checks the little piece of memory to see if it had taken a true If-Then statement (ERR:SYNTAX otherwise), and searches for an End to jump to, which it finds immediately. We won’t yet consider the exact mechanics of searching for an End. This Else is the first conditional to search for and find this End statement.
  
• End: The End frees the little piece of memory.
  

Now, let’s perform the same analysis on the program when K=0.

Case: K=0

If 0
Then
Goto A
End
While 0
Lbl A
Else
End

In this case, both the If statement and the While loop fail to meet their conditions and search for Ends:

• If 0:Then: The condition fails, so the If statement searches for an End and finds the End after the Goto. Execution continues after this End statement.
  
• While 0: This condition also fails, and it finds the End statement after the Else. This While is the second conditional to search for and find this End statement.
  

The While finding this End is somewhat unexpected, so it’s worth examining exactly what happens when a While or For( loop searches for an End. (n.b. I suppose this isn't strictly necessary to understand the solution. Still, the point of this puzzle was to get you thinking about the minutiae of control flow, so I present it anyway.) It’s straightforward: the While checks the first tokens of successive lines, adding one to a counter if it finds a For(/While/Repeat/If-Then and subtracting one if it encounters an End. The search ends if it encounters an End when the counter is back where it started, and there is no error for reaching the end of the program.

I speculate that at the time when the End-searching was implemented, someone incorrectly assumed that every Else would be preceded by an If-Then (or, more generously, deemed it unnecessary given the additional time-and-space cost of doing it “right”). My less-generous theory is perhaps corroborated by merth’s finding that an isolated Else does not throw an ERR:SYNTAX on specific early TI-82 versions (later pinpointed by Logical to be 8.0 or earlier).

Using my method, you cannot find three statements that find the same End. Specifically, you would need to find three control statements A, B, C such that

• A, B, C all search for an End
  
• A ignores B and C when looking for its End (*)
  
• B ignores C when looking for its End
  

I am thoroughly convinced that the starred condition cannot be met without using DelVar or some undiscovered method.

Using DelVar forms the basis of Zeroko’s first solution. Because While only checks the first token on each line, a While placed on the same line as a DelVar will not be seen (the following elegant solution for three conditionals is due to commandz):

Code:

---

The file that generates the hash in my first post follows. (I was concerned that because the program was so short and low-entropy, someone might decide brute-forcing my hash was easier than solving my puzzle, so I added a random string at the end.)

Code:

Structure 1 with Goto: 23 bytes
Code:

Structure 2 with For(: 23 bytes
Code:


Assuming a reset calculator [all variables start null'd] [as is standard]:

Structure 2 with Ans: 21 bytes
Code:



Bonus, structure 2 with IS>(, courtesy of iPhoenix: 25 bytes
Code:

Here was my submission. It may syntax error on your modern calcs, but if you've got an old one (like 1995), it might work!


Code:

Using merth's structure we can achieve 17 bytes:
Code:

I suppose I can reuse this thread for more control flow puzzles as I devise them.

---

One advanced use of the If statement looks like this:

Code:

In this code, the Disp is only reached if A is false or B is true. A proof:

Suppose A is false. Then If B is skipped and flow continues directly at the Disp 1. Now suppose A is true. Then If B is checked and Disp 1 is reached if and only if B is true.

What if I repeat this one hundred times (like the following)?

Code:

Under what conditions will 1 be printed? You can assume 100=dim(L1 and sum(L1=0)+sum(L1=1)=100. I say that a certain value of L1 allows 1 to be printed if the above program with 100 If statements will execute Disp 1 when L1 has that value.

Your solution should have the following components:

• A simple, concise description of every value of L1 that will allow a 1 to be printed.
  
• A convincing argument for the following two points:
  1. Every list that matches your description will allow a 1 to be printed.
     
  2. You have found every such list. (i.e. no lists which do not match your description will allow a 1 to be printed)
     

I think the easiest way to keep this puzzle spoiler-free is for you to DM me your solutions, and I'll evaluate them myself.

A list of people who sent me submissions that passed my tests, in order of receipt (I will probably only update this once or twice daily because I'm rather busy):

1. kg583
   
2. merth
   
3. linkjt9
   
4. commandz (smallest solution)
   
5. LogicalJoe
   
6. Zeroko
   
7. Michael2_3B
   
8. fghsgh
   

I'll release my solution to this puzzle on October 6th or after two correct submissions, whichever is later; feel free to discuss your observations in this thread.

Put me on da list cause I cracked it!

well this is actually quite complicated, I've been trying it for an hour, and I see how it works, I just can't seem to explain part of it.

Fun puzzle indeed. Pretty simple when you realize the pattern

Bump! Not sure if you forgot about this or something else happened, but it’s after October 6th and there have been more than two correct submissions.

Something else did in fact happen. iPhoenix is currently gone for like a week or so. Answer will probably come eventually.

I put my answer in a Flowchart if it helps.

“One hundred If statements” are quite a few– let’s start with just four and keep an eye out for things we can prove.

These input values allow 1 to be printed:

Code:
and these do not:

Code:

What patterns do you see? More specifically (and perhaps more fruitfully), are there any properties that apply to every member of the first set of lists but not the second?

---

One possible observation is that every member of the second set has an odd number of trailing zeros. This seems intuitively correct to me, but it’s not yet a convincing argument– perhaps this property only works if the number of Ifs is the square of an even prime or something.

You all presented me with several great arguments. Zeroko gave a very concise inductive argument, while kg583 and commandz had the cute idea of using a DFA that recognized the same strings as the Ifs (both kg and cbg were motivated by RegExes). Everyone else devised something similar to the argument below. This argument more or less directly proves the observation-based hypothesis above. Even though I deliberately only asked for “reasonable arguments,” I’ve filled in enough logical gaps that most would consider this to be rigorous proof. There are a few cute moments when you write it all out!

What do zeros and ones in the input actually do? A 1 in the input array guarantees that the next If statement is executed. There are two cases, as each If 1 is either taken or jumped over.

• Suppose the If 1 is jumped over; i.e. there is an If 0 before the If 1, and this If 0 is executed (single-line Ifs can only skip a single line, so this is the only way that the If 1 can be skipped in our setup). Then the statement after the If 1 is executed because the If 1 was jumped over.
  
• Suppose the If 1 is taken. Then the statement after the If 1 is executed because the condition is true, and that’s what If statements do.
  

Thus a 1 in the input array guarantees that the next If statement is executed in every case. This is the observation that inspired this problem

Then if we have a string like <complete mess>100000000, we can ignore the <complete mess> and consider only the trailing zeros.

From here, the proof is more straightforward. Every executed If 0 skips another If 0, so pairs of elements in L1 are consumed. If there are an odd number of zeros, then the If 0 immediately preceding the Disp will be executed and the Disp will be skipped. Otherwise, the Disp is executed, which is what was to be shown.

---

There was some discussion in SAX about how the RegEx-based solution works. I demonstrate that (1|0.)+ matches the correct strings and that it matches our English solution of "has an even number of trailing zeros".

This regex implements the following process:

1. Start from the beginning
   
2. if you see a 1 then check the next character
   
3. if you see a 0, skip the next character and check the character after it
   

i.e. it directly implements what If statements do.

This regex checks for strings built from three units: 1, 01, and 00. Every unit has an even number of trailing zeros, so every string built entirely from them has an even number of trailing zeros.

Probably uncoincidentally, KG's (1+|0.)* solution below directly corresponds with the minimal-node "textbook" DFA that meets our requirements. However, his (1|0.)+ solution is shorter as a RegEx, a little clearer to understand, and simpler to prove.

Great work, iPhoenix.

So yes, essentially the problem boils down to counting the number of trailing zeros. Here is my TI-Basic, one-liner solution:

Code:


This code will produce a 1 (true) if the number of trailing zeros is even, otherwise it produces 0.

As seen in the code, we are essentially just counting the number of cumulative sum values that equal the total sum of L1, and checking if it's even. But there is a caveat:

(Using a sample smaller than the supposed 100 elements, for clarity)
Consider an L1 that equals {1,0,1,0,0,0}
The cumSum of that would be {1,1,2,2,2,2}

The number of cumSum values that equal the total sum of L1 is 4. We then want to subtract max(L1) from that to get 3, which is the correct number of trailing zeros that we have. However, I actually add max(L1) (which comes out to a total of 5) because it makes for smaller code, and still produces the correct result in the evenness checker. 5 is an odd number, so the code produces a 0.

Now consider that L1 is all 0's: {0,0,0,0,0,0}
The cumSum of that is also all 0's: {0,0,0,0,0,0}.

So, the number of cumSum values that equal the total sum is 6. This is where max(L1) becomes important: since there are no 1's present in L1, it doesn't add anything, and now only checks if 6 is an even number. The code therefore produces a true result, and reaches the final "Disp" line from the original puzzle.

After hearing that kg583's regex was only 8 characters long, I decided (for no practical reason whatsoever) to try and find something even shorter.
Since I don't think it's possible to do so with regex, I switched to Jelly, an extremely concise language designed for code golf, which long time Cemetech users might remember from jacobly's Advent of Code solutions a few years back.
Because it was my first time using the language, it took me a bit to figure out how chains worked, but I eventually produced this Jelly program: Ui1%2
It does an Upend (array reverse) operation, then finds the index of 1, then takes that modulo 2. That's equivalent to finding the number of trailing zeroes, then checking if it's odd.

My solution was initially just a DM to iPhoenix containing (1+|0.)+, though not long after I realized this can be reduced to just 7 characters: (1|0.)+

This regex captures a bit more directly how If statements work: a 1 always invokes the next If, while a 0 jumps over it, regardless of its value. Staring at 0. long enough should then show you the even trailing zeros condition.

I, with great labor, extracted something vaguely closer to a proof than a regex out of both of you

Commandz sent me a regex which checked for the beginning and ending of the string. To make kg's comparable with cbg's I took the liberty of extending it to (1|0.)+$, which is the mysterious 8 character regex.