Talk:Multisplit: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:06, 26 April 2011

What is going on here?

So I see that we have this for some sample output:

['a', [1, 1], '', [0, 3], 'b', [2, 6], '', [1, 7], 'c']

What's with the empty strings there? Is it saying that there are empty strings at position 3 and 7 in the input string and that they correspond to separators 0 and 1? This doesn't make sense to me at all. --Mwn3d 04:27, 27 February 2011 (UTC)

The task description doesn't stand on its own at the moment. Do you mean to have arbitrary interpretation of what constitutes a match for example?
I.e. given a text of 'X123Y' and separators '1', '12', '123', '23', and '3' then there are a multitude of possible answers which would fit the initial task description. This may lead to answers that are difficult to compare due to diverging interpretations of the spec.

The output format seems to be Python specific. Do you mean it to be or could any ordered output of sub<N>, sepnum<N>, seppos<N>, ... work? --Paddy3118 04:46, 27 February 2011 (UTC)

@Mwn3d: This format is for convenience: at even (from 0) positions we have strings, at odd - separators. Different formats are suitable for different tasks.
@Paddy3118: Separators are considered in input order.

Input: 'X123Y', ['1', '12', '123', '23', '3']
Output: ['X', [0, 1], '', [3, 2], 'Y']

It is acceptable to output this information in data structures native to programming language. --DSblizzard

'a' is at an odd position according to the output, but it's a string. And that still doesn't explain where "''" came from. --Mwn3d 03:07, 28 February 2011 (UTC)

odd - if we will count from 1, OK. This format with empty strings allows us to quickly answer, what is the 1548-th separator in a string, without looking over first 1547 separators. Another format which allows to answer such question will be more complicated. --DSblizzard

I've reworded the task so that it actually describes the task rather than referring to an implementation. I'm also trying to avoid having it state that the strings and separator information have to be interleaved; that's a very odd thing to do in some languages. My aim was that the solutions given should continue to be solutions, but that the description won't stop other ways of doing the challenge; after all, we want solutions to tasks to be as idiomatic as possible in their language. –Donal Fellows 10:31, 28 February 2011 (UTC)

Correct result

How about a statement of the correct result.

For example the D example leaves separator characters unmatched, by my reading that wasn't intended.

given “a!===b=!=c” and the separators “==”, “!=” and “=”.

yielded a! <==> =b= <!=> c <=> = <!> =d (with <> demarcating separators)

shouldn't that be a <!=> <==> b <=> <!=> c

--Dgamey 11:00, 21 April 2011 (UTC)

Vincent> Double-check what a string analysed in D version.

It shouldn't match all possible separators. It should match them in the order that they are given. With that example, the first "==" in "a!===b" is matched and removed from later matching because "==" is the separator that it checks for first. If you change the order of the separators to "!=", "==", "=" then it will match like this: a <!=> <==> b <=> <!=> c. If you change the order to "=", "!=", "==" then it will match like this: a! <=> <=> <=> b <=> ! <=> c. --Mwn3d 15:27, 21 April 2011 (UTC)

Vincent> Program does exactly what you describe, except your mistake: spearators doesn't reused once they are finished, so for “a!===b=!=c” ("!=", "==", "=") it produces “a <!=> <==> b <=> !=c” - note that '!=' separator doesn't used AGAIN.

Clarification in order

While the text says "the order of the separators is significant; where there would otherwise be an ambiguity as to which separator to use at a particular point (e.g., because one separator is a prefix of another) the first separator in the collection should be used." your interpretation doesn't follow. If you have x!==y and the separators !==, !=, and = the ambiguity referred to could equally be do you parse out x !== y or x != = y. Because of the order !== precedes != the first is correct. The example I gave above slid the rules I described over the characters left to right. And as for not reusing a separator, nowhere does it say that. Basically, either interpretation could be correct at this point as the task isn't specific enough.

Most of the examples don't even clearly show output, so it's difficult to tell which are matched (The reader should not have to figure it out from listings of indices). It should be a requirement to show the output so you can see how it's being parsed out. As it stands it's difficult to tell if some of the solutions are correct under either interpretation. --Dgamey 23:11, 21 April 2011 (UTC)

Vincent> Dgamey, please don't spread chaos in your mind to this task. There is no ambiguity, since every delimiter taken once and HIS FIRST OCCURENCE in string is used. And ONLY AFTER THAT next delimiter is considered in THE REST OF STRING. Sorry, but you're not qualified enough to discuss this task, please finish university and return to programming. Nothing personal, sorry.

Vincent, I am trying to have a discussion about the intent of the task. I still think it's unclear. If I were 100% sure that the D interpretation was wrong, I would have marked it incorrect. I did not do that. However, I do believe with a fair amount of certainty that the D interpretation is based on an incorrect interpretation (just as you believe it is right). Hence this discussion - I am using the wiki the way it is intended.

I don't believe you are the author of this task. The history indicates that would be DSblizzard. Input from the author is what is needed to clarify this. BTW this is a draft task - discussion is what these are about.

I believe the task should be required to clearly show output. I did. I also know you will think my code is incorrect based on your interpretation. But until the author clarifies the task, they should both stand.

Your capitalized text is not quoted from the description and it is your interpretation. Please reread the task description carefully and I think you may see the other interpretation is also possible.

I had suggested showing more clear output as a requirement, to make it clear what each solution accomplished. I strongly suspect that some of the other solutions would not produce the same results as the D solution.

Talking about me "spreading choas" etc. despite your claim is a very rude attempt to get personal. Please measure your responses and keep the discussion civil. If we cannot agree, then can agree to disagree and wait for clarification from the author. --Dgamey 11:14, 22 April 2011 (UTC)

Vincent, relax. The one thing I really don't care for on RC are attacks on fellow editors.

Second, the task strikes me as underspecified. From the task description, it's not clear to me whether a sequence like "!==" should be parsed as "!=" "=" or "!" "!==". In fact, as far as I can read the output of the code examples, I don't think I'm the only one who sees ambiguity there. I'm sending an email off to the task author in hopes they'll step in.

D's interpretation is wrong. Output in D's example should be a {!=} {==} b {=} {!=} c {==} {!=} d in its notation. Please use (my) Python's "Alternative version" as a reference. You can run python code at http://codepad.org. DSblizzard 06:53, 24 April 2011 (UTC)

Also, please remember to sign your comments with --~~~~ --Michael Mol 12:26, 22 April 2011 (UTC)

Vincent> Guys, your fantasy used in wrong direction. In input we have string (most probably PIECE of some log or program's config, whatever) and ordered delimiters. It's not a big thinking effort to realise, that ordering of delimiters has meaning - they assume special format of input string, not just stupid "split by space" task. Vincent> Second, you, Dgamey, "Mr. Change Conditions To My Own", leave task description alone from your ugly results - only author can do it. Name yourself as sh*ty as you can for such cheat behaviour.

Vincent, the author of the task has clarified the intent in these talk pages. You continue to insult editors, refuse to sign your updates as requested by the owner of the site. You're behavior is not supportive of the site, the owner, or other editors. I only changed the task description to what the owner had documented here above. Please think about what you are doing.--Dgamey 11:06, 26 April 2011 (UTC)

Small inaccuracy in the smaller non-RE Python version?

This is a reason to tighten the task description, as I think the task description relies too much on the original Python implementation at the moment. --Paddy3118 08:16, 28 February 2011 (UTC)

I'm not tempted in a formulation of Rosetta tasks, therefore feel free to rewrite the task as you see fit.--DSblizzard 09:33, 28 February 2011 (UTC)

J implementation

implementation

The J implementation currently looks like this:

<lang j>multisplit=:4 :0

 'sep begin'=.|:t=. y /:~&.:(|."1)@;@(i.@#@[ ,.L:0"0 I.@E.L:0) x
 end=. begin + sep { #@>y
 last=.next=.0
 r=.2 0$0
 while.next<#begin do.
   r=.r,.(last}.x{.~next{begin);next{t
   last=.next{end
   next=.1 i.~(begin>next{begin)*.begin>:last
 end.
 r=.r,.;~last}.x

)</lang>

The first line uses a fair bit of point free code (because it was convenient, and easy for me) and many Rosetta readers are likely to have problems reading it. And task currently has people puzzled, so perhaps a fuller discussion would also be helpful.

sep begin

The first line of this multisplit defines two variables: sep and begin

<lang j> y=. '==';'!=';'='

  x=. 'a!===b=!=c'
  'sep begin'=.|:t=. y /:~&.:(|."1)@;@(i.@#@[ ,.L:0"0 I.@E.L:0) x
  sep

1 0 2 0 2 2 2 1 2

  begin

1 2 2 3 3 4 6 7 8</lang>

(Note: its normally bad practice to use variables named 'x' and 'y' because they get values bound to them in functions. However, for purposes of illustration I think it's fine to pull code out of a function and use that with explicitly assigned values.)

Here, sep is a list of 0, 1 or 2, with 0 corresponding to '==', 1 corresponding to '!=' and 2 corresponding to '='. And, begin is a list of corresponding character positions. The values in begin are in non-decreasing order, and the values in sep are ascending when they correspond to equal values in begin.

So, how does that work?

E. finds locations where substrings match:

In other words, for each character in the right argument, we have a 1 if the substring in the left argument begins there.

Or, we can get indices instead of a bit mask:

Except we need to deal with multiple separators, and they can be differing lengths which means that representing them as a homogeneous array would be bad (every item in a homogeneous array must have the same length). But we can put them in boxes, and have an array of boxes:

But now we need to tell I.@E. that it is not supposed to work on the boxes directly, instead it needs to work inside the boxes.

Ok, so great, but now we need to combine the results from those different boxes so we can work with them. Except, before that, right now the boxes distinguish which separator we are using, and we are going to need to add that, explicitly, so we do not lose track of that information after the boxes are gone. In other words, we have three boxes so we need three different values to label their contents with:

<lang j> i.@# '==';'!=';'=' 0 1 2

  ('==';'!=';'=') i.@#@[ 'a!===b=!=c'

0 1 2</lang>

So, let's add the labels to each of the values in each of the boxes:

<lang j> 0 1 2 (,.L:0"0) 2 3;1 7;2 3 4 6 8 ┌───┬───┬───┐ │0 2│1 1│2 2│ │0 3│1 7│2 3│ │ │ │2 4│ │ │ │2 6│ │ │ │2 8│ └───┴───┴───┘

  ('==';'!=';'=') (i.@#@[ ,.L:0"0 I.@E.L:0) 'a!===b=!=c'

┌───┬───┬───┐ │0 2│1 1│2 2│ │0 3│1 7│2 3│ │ │ │2 4│ │ │ │2 6│ │ │ │2 8│ └───┴───┴───┘</lang>

(In the first example, we needed parenthesis to tell the computer that 0 2 3 was not meant to be combined. In the second example, we need parenthesis to tell the computer that we want the result of the left and right verbs to be the arguments for the verb in the middle.)

So, now we are ready to combine them:

and sort them:

This suggests a simplification -- The &.:(."1) means we are reversing each row before we sort and then reversing them back after each sort. But this busy work could be eliminated by reversing the order of the columns. I might change the code (and this writeup), but I am not going to do that now -- and someone else can (and delete this paragraph) if they get to that before I do.

Finally, to assign this array to two different values, we need an array of two items, so we transpose the array.

But before transposing it we save a copy in the variable t because we need that for the "extra credit" part of this task.

other pre-loop setup

<lang j> end=. begin + sep { #@>y

 last=.next=.0
 r=.2 0$0</lang>

end has the same structure as begin and sep, and gives the character position where each separator ends. It's just the beginning character location plus the length of each corresponding separator.

next will be our loop variable -- it's the index of the next value from begin/sep/t/end to be used.

last will be our "the last separator ended here" value, which we will be using to search for the next value for next

Finally, r will hold our result. It's arranged horizontally rather than vertically, because that uses less screen real estate on rosettacode. And, fortuitously, that makes it easier to select out just the string values (the useful part) from the "extra credit" result.

while. loop

next is an index into any of begin/sep/t/end and when it goes off the end, we are done.

<lang j>r=.r,.(last}.x{.~next{begin);next{t</lang>

This has three important parts:

r=.r,.value (the result builder).
last}.x{.~next{begin (the substring extractor), and
next{t (the extra credit assignment)

The first time through the loop, last and <next> will be 0, and the first value from begin is 1, so last}.x{.~next{begin is equivalent to 0}.'a!===b=!=c'{.~1 or: take the first 1 character from that string and drop the first 0 characters from it. That's the substring containing the single character 'a'. Likewise, 0{t will be the value 1 1.

Next, we save the value where this delimiter instance ends. In other words last takes on the value 3.

Finally, we use that ending location to find our next delimiter instance. begin>:last, the first time through the loop, is equivalent to

And, that would be enough, but I did not want an infinite loop if someone happened to use an empty delimiter, so I added an explicit test for that. It's just a safety measure, and does not actually matter for the required test case. But next{begin is still 1, so:

Anyways, I find the index of the first value where these two bitmasks are both set. (*. is J's boolean and operator.) <lang j> 0 1 1 1 1 1 1 1 1 *. 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1

  (i.&1)0 1 1 1 1 1 1 1 1 *. 0 0 0 1 1 1 1 1 1

3</lang>

The next time through the loop, next will be 3. And, when we are done, one of these bitmasks will be all zeros, so next wil l be larger than the the bitmask length.

ending

Finally, we have one last bit of code to execute: <lang j>r=.r,.;~last}.x</lang>

This gives us the "tail end" -- everything appearing after the last valid separator (or the entire argument string if none were valid). Since there is no separator terminating this instance, I use an empty value to represent its details.

F# incorrect

In this part of the F# example, you can see that it is incorrect: <lang fsharp>> "a!===b=!=c".Split([|"="; "!="; "=="|], System.StringSplitOptions.None);; val it : string [] = [|"a"; ""; ""; "b"; ""; "c"|]</lang>

"a!===b=!=c" should be split like this (because of the order of the delimeters):

a!, =, =, =, b, =, !, =, c

"=" comes first in the delimeters list. "!=" should never be matched because the "=" has already been matched by the first delimeter in the list. If "!=" could be matched before "=", then the order of the delimeters wouldn't matter. Since the order matters, you scan for "=" first. --Mwn3d 18:50, 21 April 2011 (UTC)

That is not how the splitting algorithm works for the original example (Python), and does not match the task description. The order in which the delimiters appear only matters when multiple delimiters match at the same position. When there is only one delimiter which matches at a position, there is no ambiguity. And the matching is implicitly from left to right. In other words, it's the D and Java implementations which are incorrect, not the F# implementation. --Rdm 19:01, 21 April 2011 (UTC)

This task has been a problem for me from the start. So what you're saying is the input string "abb" and delimiter list ["b", "ab"] would match "ab" (the first two characters) and then "b" (the third character)? I'd like to see example inputs and outputs in the task description. I'll just take the Java example down until I understand the task better. --Mwn3d 19:22, 21 April 2011 (UTC)

Yes, you would get three empty strings matching "abb" against the list "b","ab". Anyways, it's basically:

  for (i= 0; i < inputString.stringLength; i++) {
     for (j= 0; j < separators.arrayLength; j++) {
        if (inputString.substring(i, separators[j].stringLength) == separators[j]) {
            split inputString here
            advance i until it is at the end of this instance of separator j
        }
     }
  }
  whatever remains of inputString after the last separator gets included in the result

</lang> --Rdm 19:57, 21 April 2011 (UTC)

@@ Line 64: / Line 64: @@
 Vincent> Guys, your fantasy used in wrong direction. In input we have string (most probably PIECE of some log or program's config, whatever) and ordered delimiters. It's not a big thinking effort to realise, that ordering of delimiters has meaning - they assume special format of input string, not just stupid "split by space" task.
 Vincent> Second, you, Dgamey, "Mr. Change Conditions To My Own", leave task description alone from your ugly results - only author can do it. Name yourself as sh*ty as you can for such cheat behaviour.
+:: Vincent, the author of the task has clarified the intent in these talk pages.  You continue to insult editors, refuse to sign your updates as requested by the owner of the site.  You're behavior is not supportive of the site, the owner, or other editors. I only changed the task description to what the owner had documented here above. Please think about what you are doing.--[[User:Dgamey|Dgamey]] 11:06, 26 April 2011 (UTC)
 ==Small inaccuracy in the smaller non-RE Python version?==