Add++, 146 bytes
D,g,@~~,L2_|*;;*|_2L,@,g,D
D,ff,@^^,BG€gBF;;FBg€GB,@D1:?:
xx:?
aa:1
`bb
Bxx;;B
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy
O;;O:,B,`,|,`,>$,`,*W`
Try it online!
Fun fact: This was 272 bytes long before the explanation was started, now it beats Java.
Outputs True for perfectly balanced strings, and False otherwise
To my great satisfaction, this beats the boring palindromize version by 2 bytes, to prevent the result being printed twice. I have also aimed to have as little dead code as possible, nevertheless there are still some commented-out sections, and the code exits with an error code of 1, after printing the correct value.
NB : A bug with the BF commands was fixed while this answer was in development.
How it works
The code starts by defining the two key functions, \$\mathit{ff}\$ and \$g\$. These two functions are used to calculate the next step in the process of removing pairs, and work entirely from \$\mathit{ff}\$ i.e. only \$\mathit{ff}\$ is called from the main program, never \$g\$. If we define the input string as \$S\$, \$\mathit{ff}(S)\$ modifies \$S\$ in the following way:
First, identical adjacent characters in \$S\$ are grouped together. For an example of \$abbbaabacc\$, this yields the array \$[[a], [bbb], [aa], [b], [a], [cc]]\$. Over each of the sublists (i.e. the identical groups), we run the function \$g\$, and replace the sublists with the result of the function.
\$g\$ starts by unpacking the group, splatting the characters onto the stack. It then pushes the number of characters on the stack and takes the absolute difference with \$2\$ and that number. We'll call this difference \$x\$. Lets see how this transforms the respective inputs of \$[a]\$, \$[bb]\$ and \$[ccc]\$:
$$[a] \Rightarrow [a, 1]$$
$$[bb] \Rightarrow [b, b, 0]$$
$$[ccc] \Rightarrow [c, c, c, 1]$$
As you can see \$x\$ indicates how many of the next character we wish to keep. For simple pairs, we remove them entirely (yielding 0 of the next character), for lone characters we leave them untouched, or yield 1 of them, and for groups where \$x > 2\$, we want \$x - 2\$ of the character. In order to generate \$x\$ of the character, we repeat the character with *, and the function naturally returns the top element of the stack: the repeated string.
After \$g(s)\$ has been mapped over each group \$s\$, we splat the array to the stack to get each individual result with BF. Finally, the ^ flag at the function definition (D,ff,@^^,) tells the return function to concatenate the strings in the stack and return them as a single string. For pairs, which yielded the empty string from \$g\$, this essentially removes them, as the empty string concatenated with any string \$r\$ results in \$r\$. Anything after the two ;; is a comment, and is thus ignored.
The first two lines define the two functions, \$\mathit{ff}\$ and \$g\$, but don't execute \$\mathit{ff}\$ just yet. We then take input and store it in the first of our 4 variables. Those variables are:
- \$\mathit{xx}\$ : The initial input and previous result of applying \$\mathit{ff}\$
- \$\mathit{yy}\$ : The current result of applying \$\mathit{ff}\$
- \$\mathit{aa}\$ : The loop condition
- \$\mathit{bb}\$ : Whether \$\mathit{yy}\$ is truthy
As you can see, all variables and functions (aside from \$g\$) have two letter names, which allows them to be removed from the source code fairly quickly, rather than having a comment with a significant amount of \$\mathit{xyab}\$. \$g\$ doesn't do this for one main reason:
If an operator, such as €, is run over a user defined function \$\mathit{abc}\$, the function name needs to be enclosed in {...}, so that the entire name is taken by the operator. If however, the name is a single character, such as \$g\$, the {...} can be omitted. In this case, if the function name was \$\mathit{gg}\$, the code for \$\mathit{ff}\$ and \$g\$ would have to change to
D,gg,@~~,L2_|*;;*|_2L,@D (NB: -2 bytes)
D,ff,@^^,BG€{gg}BF;;FB}gg{€GB,@D?: (NB: +6 bytes)
which is 4 bytes longer.
An important term to introduce now is the active variable. All commands except assignment assign their new value to the active variable and if the active variable is being operated on, it can be omitted from function arguments. For example, if the active variable is \$x = 5\$, then we can set \$x = 15\$ by
x+10 ; Explicit argument
+10 ; Implicit argument, as x is active
The active variable is \$x\$ by default, but that can be changed with the ` command. When changing the active variable, it is important to note that the new active variable doesn't have to exist beforehand, and is automatically assigned as 0.
So, after defining \$\mathit{ff}\$ and \$g\$, we assign the input to \$\mathit{xx}\$ with xx:?. We then need to manipulate our loop conditions ever so slightly. First, we want to make sure that we enter the while loop, unless \$\mathit{xx}\$ is empty. Therefore, we assign a truthy value to \$\mathit{aa}\$ with aa:1, the shortest such value being \$1\$. We then assign the truthiness of \$\mathit{xx}\$ to \$\mathit{bb}\$ with the two lines
`bb
Bxx
Which first makes \$\mathit{bb}\$ the active variable, then runs the boolean command on \$\mathit{xx}\$. The respective choices of \$\mathit{aa} := 1\$ and \$\mathit{bb} := \neg \neg \mathit{xx}\$ matter, as will be shown later on.
Then we enter our while loop:
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy
A while loop is a construct in Add++: it operates directly on code, rather than variables. Constructs take a series of code statements, separated with , which they operate on. While and if statements also take a condition directly before the first , which consist of a single valid statement, such as an infix command with variables. One thing to note: the active variable cannot be omitted from the condition.
The while loop here consists of the condition aa*bb. This means to loop while both \$\mathit{aa}\$ and \$\mathit{bb}\$ are truthy. The body of the code first makes \$\mathit{yy}\$ the active variable, in order to store the result of \$\mathit{ff}(x)\$. This is done with
`yy,$ff>xx
We then activate our loop condition \$\mathit{aa}\$. We have two conditions for continued looping:
- 1) The new value doesn't equal the old value (loop while unique)
- 2) The new value isn't the empty string
One of Add++'s biggest drawbacks is the lack of compound statements, which necessitates having a second loop variable. We assign our two variables:
$$\mathit{aa} := \mathit{xx} \neq \mathit{yy}$$
$$\mathit{bb} := \neg \neg (\mathit{yy})$$
With the code
`aa,xx|yy,`bb,Byy
Where | is the inequality operator, and B converts to boolean. We then update the \$\mathit{xx}\$ variable to be the \$\mathit{yy}\$ variable with xx:yy, in preperation for the next loop.
This while loop eventually reduces the input into one of two states: the empty string or a constant string, even when applied to \$\mathit{ff}\$. When this happens, either \$\mathit{aa}\$ or \$\mathit{bb}\$ result in False, breaking out of the loop.
After the loop is broken, it can break for one of two reasons, as stated above. We then output the value of \$\mathit{aa}\$. If the loop was broken due to \$\mathit{x} = \mathit{y}\$, then both the output and \$\mathit{aa}\$ are False. If the loop was broken because \$\mathit{yy}\$ was equal to the empty string, then \$\mathit{bb}\$ is falsy and \$\mathit{aa}\$ and the output are truthy.
We then reach our final statement:
O
The program can now be in one of three states, in all of which the active variable is \$\mathit{bb}\$:
- 1) The input was empty. In this case, the loop didn't run, \$\mathit{aa} = 1\$ and \$\mathit{bb} = \mathrm{False}\$. The correct output is \$\mathrm{False}\$.
- 2) The input was perfectly balanced. If so, the loop ran, \$\mathit{aa} = \mathrm{True}\$ and \$\mathit{bb} = \mathrm{False}\$. The correct output is \$\mathrm{False}\$
- 3) The input was not perfectly balanced. If so, the loop ran, \$\mathit{aa} = \mathrm{False}\$ and \$\mathit{bb} = \mathrm{True}\$. The correct output is \$\mathrm{True}\$
As you can see, \$\mathit{bb}\$ is equal to the expected output (albeit reversed from the logical answer), so we simply output it. The final bytes that help us beat Java come from the fact that \$\mathit{bb}\$ is the active variable, so can be omitted from the argument, leaving us to output either \$\mathrm{True}\$ or \$\mathrm{False}\$, depending on whether the input is perfectly balanced or not.
Is throwing an error valid? – Shaggy – 2018-06-25T17:24:08.983
1While it may be too late to change it now, I feel like the "twist" part of the challenge is rendered almost pointless if you allow comments or similar "dead" code. – Geobits – 2018-06-25T17:26:43.227
11@Geobits I disagree. For one I think that disallowing dead code is just a mire of vague definitions and never turns out fun anyway. For two I think allowing comments lowers the bar of entry. For three I believe that the comment-less code will inevitably be better scoring than the comment-full code. Maybe the twist isn't fun but it would definitely be less fun if I added unenfoceable restrictions to make answers do it in a particular way. – Post Rock Garf Hunter – 2018-06-25T17:32:53.277
4Unary doesn't give a damn about your source restriction rule, mwahahahaha (that is ... as long as the answer has an even number of bytes). – Arnauld – 2018-06-25T17:41:06.930
@Shaggy I think the default allows it. I can't find the post though. I'll defer to that so if you can find the proper consensus go ahead. – Post Rock Garf Hunter – 2018-06-25T17:42:22.197
2@Geobits One thing that might have encouraged more creative answers is to factor the number of steps to get to the empty string into the scoring. Using comments tends to cause this number to be quite high because the comments naturally nest where as a lower score requires you to interlace the pairs quite a bit. Obviously it is too late to make that change though. – Post Rock Garf Hunter – 2018-06-25T18:12:32.750
Can
<empty-string>and<loop-forever>be the two consistent "values"? – dylnan – 2018-06-25T18:17:30.8131@dylnan The empty string can be, looping forever however is not valid output. – Post Rock Garf Hunter – 2018-06-25T18:18:12.140
@Shaggy I think throwing an error is valid output and you wouldn't even care about the output/return value in the other case, since programs can by default output via exit code. In Javascript's particular case, the output values would be exit code 0 for perfectly paired strings and exit code 1 for non-perfectly paired strings, which are two distinct values therefore fulfilling the criteria.
– Mr. Xcoder – 2018-06-25T18:48:27.643Can the input be empty? If so, what does it output? – caird coinheringaahing – 2018-06-27T22:40:10.960
@cairdcoinheringaahing The empty input is true. – Post Rock Garf Hunter – 2018-06-27T22:40:43.627