-join("$args"-split'\b'|%{(,$(,$_[0]*$n+$_))[!!($n=$($_-1))]})
Try it online!
Breakdown
What a mess!
Starting from $args
, which is a single element array containing the RLE string, I'm forcing into an actual string by wrapping it quotes.
Then split it by word boundary (\b
in regex). That will give me an array of strings, where each element is either a number or the BF token(s) that come after the number. So in the example, the first 4 elements of this split array are 10
,+]>+>
,3
,+>
(all are string).
Next, I pipe that into ForEach-Object
(%
) to deal with each element.
The middle is a well-known PowerShell golfism, with a twist; it's essentially a DIY ternary operator, in which you create a 2 element array then index into it using the boolean expression you want to test, whereby a false result gives you element 0 and a true result gives you element 1.
In this case, I actually create a single element array with the unary comma ,
operator, because I don't want output in the true case.
First let's look at the indexer, even though it gets executed later.
The idea of this is that $_
(the current element) could either be a valid number, or some other string. If it's a number, I want $n
to be the value of that number minus 1 (as a number, not a string). If it's not, I want $n
to be false-y.
PowerShell usually tries to coerce the right-hand value to the type of the left side, but it can depend on the operation. For addition, "10"+5
would give you a new string, "105"
, whereas 10+"5"
will give you an integer (15
).
But strings can't be subtracted so instead PowerShell can infer the numeric value automatically with a string on the left side of subtraction, therefore "10"-5
gives 5
.
SO, I start with $_-1
, which will give me the number I want when $_
is actually a number, but when it's not I get nothing. On the surface, "nothing" is falsey, but the problem is that is stops execution of that assignment, so $n
will retain its previous value; not what I want!
If I wrap it in a subexpression, then when it fails, I get my falsey value: $($_-1)
.
That all gets assigned to $n
and since that assignment is itself wrapped in parentheses, the value that was assigned to $n
also gets passed through to the pipeline.
Since I'm using it in the indexer, and I want 1
if the conversion succeeded, I use two boolean-not
expressions !!
to convert this value to boolean. A successful number conversion ends up as true, while the falsey nothingness gives us that sweet, sweet 0
that allows for returning the only element in that fake ternary array.
Getting back to that array, the element is this: $("$($_[0])"*$n*$_)
$(,$_[0]*$n+$_)
"$($_[0])"
- this is an annoyingly long way of getting the first character of the current element (let's say, getting +
from +[>+
), but as a string and not as a [char]
object. I need it to be a string because I can multiply a string by a number to duplicate it, but I can't do that with a character.
Actually I managed to save 4 characters by using a [char]
array instead of a string (by using another unary comma ,
), so I was able to remove the quotes and extra sub-expression. I can multiply an array to duplicate its elements. And since the entire result of this iteration ends up being an array anyway and needs to be -join
ed, using an array here incurs no additional cost.
Then, I multiply that string array by $n
, to duplicate it $n
times. Recall that $n
could be $null
or it could be the value of the preceding digits minus one.
Then +$_
adds the current element onto the end of the duplicated first character of that element. That's why $n
is minus one.
This way, 10+[>+
ends up with $n
equal to 9, then we make 9 +
's and add that back to the +[>+
string to get the requisite 10, plus the other single elements along for the ride.
The element is wrapped in a subexpression $()
because when $n
is $null
, the entire expression fails, so creating the array fails, so the indexer never runs, so $n
never gets assigned.
The reason I used this ternary trick is because of one of its peculiarities: unlike a real ternary operator, the expressions that define the elements do get evaluated whether or not they are "selected", and first for that matter.
Since I need to assign and then use $n
on separate iterations, this is helpful. The ternary array element value gets evaluated with the previous iteration's $n
value, then the indexer re-assigns $n
for the current iteration.
So the ForEach-Object
loops ends up outputting everything its supposed to (a bunch of errors we ignore), but as an array of new strings.
So that whole thing is wrapped in parentheses and then preceded by unary -join
to give the output string.
I'm confused. Is the goal to output the fixed string corresponding to translating the given string? – xnor – 2017-11-02T12:57:53.817
Is the program given as input, or should we hardcode it? – user202729 – 2017-11-02T12:57:56.977
Your task is to write the shortest program/function that translates the following RLE Brainfuck fragment into regular Brainfuck program - Should our submissions work for any valid Brainfuck code or just that piece of code? You should also include the desired output by the way. – Mr. Xcoder – 2017-11-02T12:58:04.620
Although this is a valid challenge, it received 2 VTC (at the time of writing this comment) as unclear (up to the site's standard). You can try the Sandbox next time.
– user202729 – 2017-11-02T13:01:55.743Hi, I edited the description. The program should work for any valid RLE BF code and display the translated program. – Galen Ivanov – 2017-11-02T13:02:03.880
10Hi, I downvoted this question because I feel that it's going to be dominated by one or two RLE-based regex algorithms that are then just copied to each language's individual regex formatting. There's very little room to golf anything here. – AdmBorkBork – 2017-11-02T13:04:15.197
13
This looks a lot like a generic run-length decoding challenge. The difference here is that multidigit numbers are supported. I think it's still a dupe, but I won't hammer it.
– xnor – 2017-11-02T13:04:18.353@user202729 Thanks, I'll use it next time. – Galen Ivanov – 2017-11-02T13:13:34.253
@AdmBorkBork Hi, Thanks for the feedback. Now I understand that my idea was stupid. – Galen Ivanov – 2017-11-02T13:34:05.837
Hi, I added clarification that the shortest code in each language wins. – Galen Ivanov – 2017-11-02T13:42:45.193
4@xnor The other difference is that digits are not always present — this form of RLE guarantees far less structure, and IMO can lead to interesting techniques (compare my Python answer here with the one in the linked challenge!) – Lynn – 2017-11-02T14:22:09.817
@GalenIvanov Can the input contain things like
0<
? – Lynn – 2017-11-02T14:22:37.8031@Lynn I haven't explicitly described this, but as is seen in the example, 1 is ommited; adding 0 doesn't make the string shorter, so the answer is no, no zeroes can prepend a command. – Galen Ivanov – 2017-11-02T14:45:19.840
6The other direction would be more interesting, I think (i.e. transform a brainfuck programm in the shortest equivalent RLE brainfuck program). – Paŭlo Ebermann – 2017-11-02T22:04:49.760
I kinda sorta implemented this language awhile ago if anyone's interested.
– Carcigenicate – 2017-11-04T23:11:56.490@PaŭloEbermann It'd be really difficult to prove that it was the shortest equivalent. You'd need to recognize that, e.g.,
>+++<[>++++<-]
is equivalent to12+
, but only if the second cell is 0 always 0 when the code is executed, which requires some serious static analysis if it appears inside any looping/branching structures. And since in the general case, pretty much any interesting static analysis is going to reduce to the halting problem, it may actually be impossible to prove optimality. Converting to an equivalent RLE-BF program would be possible, though. – Ray – 2017-11-06T14:53:15.1201@Ray I meant some "weaker" form of equivalence, basically the one implemented by this challenge (i.e. two RLE brainfuck programs are equivalent if they expand to the same brainfuck program). Finding the shortest (or one of the shortest, as
++
and+2
have the same length) from such a family should be easily decidable. The general equivalence in the computer science meaning is non-decidable, of course. – Paŭlo Ebermann – 2017-11-06T20:17:18.847