Talk:Longest string challenge

Generalization

This is an interesting programming challenge. An active discussion is needed to strike a balance between generalization and defeating the task.

• I would expect to see a number of languages mark this as omit.
• Would this only be possible for languages with implicit iteration?
• Would it be fair to relax the lists to lists of lists or supplementary lists in cases of languages like C that represent strings as arrays?
• Etc.

How about a discussion here of how this would apply to a few languages (say in the top 20 or so)?

Suitability and Applicability

There needs to be an anchor for the emerging discussion on the suitability of this task for RC as the comments are under several headings.

When I borrowed this problem as a task, I did so not knowing if the task has general applicability. I did state this at the top of the talk page and I did want a discussion. I think the discussion so far has some value. I'm not sure about the ultimate outcome. --Dgamey 19:12, 14 August 2011 (UTC)

It might be appropriate to put some kind of a warning see this discussion on the task page to read the discussion. Is there a template for that? --Dgamey 19:12, 14 August 2011 (UTC)

What options are there if the task doesn't survive? It evolves into something else possibly removing the restrictions? Is there a dead tasks template? Other? --Dgamey 19:12, 14 August 2011 (UTC)

A number of observations have been made in the restrictions section. I knew that they could be controversial. I also knew there would need to be a discussion around them and they would require elaboration. That's happening on the talk page. It's not clear to me yet that how this will play out. --Dgamey 19:36, 14 August 2011 (UTC)

One of the things that I like to see on this site is how to do things in other languages that you are unfamiliar with or less familiar with. My C is very rusty and I thought it would probably get an omit for this task. But the solution mildly surprised me and fits what I believe is the intent. Because of that it also means I'll remember that aspect of C now. I'm willing to guess that other people on this site may have a similar sentiment. --Dgamey 19:36, 14 August 2011 (UTC)

Whatever does happen, I'd like to see this discussion preserved. Even if in the worst case it's only something to point people at to show why this kind of thing didn't work. If it just gets deleted, then someone a month or a year from know could do something similar. --Dgamey 19:36, 14 August 2011 (UTC)

Similar to Averages/Mode

The problem statement itself (without the restrictions) is very similar to Averages/Mode, except that you do not need to compute the counts of elements, instead taking the length of the string serves as its "count". --208.80.119.69 00:43, 13 August 2011 (UTC)

Except that in mode you can use comparison operators and arithmetic operators. You're not allowed to do either here. Besides that, I still don't think it's really that similar. --Mwn3d 00:59, 13 August 2011 (UTC)

Can't load https link

Firefox won't load the reference link due to invalid SSL cert. --Ledrug 00:08, 13 August 2011 (UTC)

In firefox you can *temporarily* accept the cert. The site is scheduled for upgrade and I can ask if there is a way that http can be allowed for anonymous users. --Dgamey 11:55, 13 August 2011 (UTC)

The TWiki Twisty (show/hide) appears to break in newer firefox and IE. If you have something like NoScript and don't trust the scripts on the site it will show all of the hidden material below the headings. --Dgamey 11:55, 13 August 2011 (UTC)

Rereading

I think the task description should explicitly forbid (or permit, if that was the intent) reading the input twice. —Kevin Reid 03:08, 13 August 2011 (UTC)

An interesting point. Since I was not the originator of the challenge, I can't answer. My take is if it isn't explicitly forbidden and it's not a cheat on one of the restrictions it should be allowed without stating it explicitly. As there are a lot of very creative people out there the list of techniques could get quite large. --Dgamey 12:20, 13 August 2011 (UTC)

Well, my preference is that given that the task is to read from "standard input", and standard input may not be a seekable file, this is prohibited implicitly (and so should also be prohibited explicitly to avoid permitting semi-broken solutions). —Kevin Reid 14:43, 13 August 2011 (UTC)

Now you have me curious, you must have a rereading solution in mind. If the description were to read from standard input or a file, that would allow rereading. I'd probably want to see a comment to the effect that it would break on stdin. Since this is more about alternate/creative ways around the restrictions, I think it would be fine. --Dgamey 07:09, 14 August 2011 (UTC)

If you can read the file twice then there's no need to keep an accumulator. Read once to find longest length, read again, along the way print anything that long. --Ledrug 07:47, 14 August 2011 (UTC)

Ah, obvious (now that I'm up and had coffee). As worded the task also doesn't necessarily prohibit the use of a temporary file either. In Icon a file is a datatype and could be argued as a cheat. Not sure about other languages. --Dgamey 15:13, 14 August 2011 (UTC)

Restrictions

What is the purpose of the restrictions? This is a chrestomathy. We would get a better language comparison, if we removed the restrictions. Markhobley 09:24, 13 August 2011 (UTC)

The basic task is very simple, the point of the restrictions is try and get people to think a bit out of the box and make it a bit more challenging. --Dgamey 12:00, 13 August 2011 (UTC)

I'm not sure whether that is the objective of rosettacode, because this is a chrestomathy. If the task has a good implementation that can be achieved through the use of operators, then we should be able to use them here. This could possibly be a challenge for a programming challenge site, but I don't know of one off hand. Alternatively, we could possibly make the restrictions optional. Markhobley 14:55, 13 August 2011 (UTC)

The restrictions were really part of the original intent and not an optional add on. That is the intent is to see ways of dealing with things a bit out of the ordinary. I would argue that there are other puzzles and challenges on the site and that limitations are not counter to the intent of the site. There is also nothing preventing a Longest string task either. --Dgamey 18:57, 13 August 2011 (UTC)

These restrictions are self contradictory, unless perhaps viewed through the blinkers of some particular language specifications. For example, a string is a list of characters but some languages might obscure this issue. For example, anything which conditionally chooses between two options involves some sort of comparison but a restriction on "comparison operators" might make sense in the context of a specific language spec. And so on... So I think this is a bad problem for this site. It assumes too much about the language used to implement the problem and since it's doing this in the restrictions it is essentially restricting the languages used to implement the task, which I believe is a no-no here. --Rdm 17:24, 14 August 2011 (UTC)

I too am wary about the general applicability of this task. --Paddy3118 18:29, 14 August 2011 (UTC)

I started a section on general suitability. I understand you being wary but still think the discussion may be useful in several ways. Understanding how tasks get defined clarified for example. It's not a science by any stretch. --Dgamey 19:26, 14 August 2011 (UTC)

The intent of the restrictions was to make it a bit more interesting, not just to exclude things. I've already said the restrictions need some more explanation to find the right balance. --Dgamey 19:26, 14 August 2011 (UTC)

Maybe think again about my suggestion of making the restrictions optional. Possibly something like. "Optionally try to produce an implementation that does not utilize foo or bar." (Where foo and bar are the facilities that you want to restrict). Markhobley 19:44, 14 August 2011 (UTC)

Remember also that it is the interest of the reader that is of primary concern, rather than the interest of the implementer. If you want to challenge the implementer, then maybe another site would be more suitable for this. Restricting things makes the provided code less optimal and less practical. Markhobley 19:51, 14 August 2011 (UTC)

I'm not there yet as I want to hear more. I am beginning to think that the intent isn't being stated in a positive way. Restrictions are by definition negative. What was the original intent here? Really, it was to get people to think outside of their particular box. This problem can be solved very conventionally and that's boring and pedestrian. The point perhaps is in your language of choice how would you solve this creatively showing off some of your language capabilities? This also lets people have a little bit of fun with it. The restrictions could be more guidance/example in this case. --Dgamey 19:56, 14 August 2011 (UTC)

Intent of Restrictions

Beyond thinking outside the box, the restrictions need to be clear and will probably get reworded.

Because the original problem came from an Icon site and talked only peripherally about implementing in other languages, I expected that the task description would require clarification. Also, my intent was not so much to use the restrictions as a way of excluding languages; hence the discussions here are really about clarifying the tasks description to allow solutions without eliminating the challenge aspect. --Dgamey 06:10, 14 August 2011 (UTC)

I think based on discussions re: 'explict' operations the intent is coming out. I'd like to leave it for a few days and see if the discussion stabilizes before updating the task description with specifics. I'll temporarily add a note to refer to the discussion re: intent. --Dgamey 06:15, 14 August 2011 (UTC)

All of the restrictions apply to any called routines such as libraries. I suppose if there was a native built-in library function that returned the longest strings that would be allowable; but, library routines shouldn't be used to cheat on the restrictions. --Dgamey 12:35, 13 August 2011 (UTC)

No comparisons

"No comparison operators may be used."

This would also cover built-in comparison functions like lt(a,b). Instead of "operators" it should probably read "operators/functions" or "operations" possibly with "built-in" in front. Now if you can write a comparison function that doesn't use these things, that would work. --Dgamey 12:35, 13 August 2011 (UTC)

(1) Do equality operators count as comparison operators? In particular, do "pointer-equality" operators which do not even do data-structure-specific examinations count? (2) Do pattern-matching (regular expressions, structural patterns, etc.) operators count? —Kevin Reid 14:44, 13 August 2011 (UTC)

Based on the discussions below about the C cmp() function, I think the main intent was to avoid explicit less/greater than comparisons and comparisons of the contents of the data (i.e. two strings). Beyond end of string detection, I'm not sure how equality tests would help. So I think the answer to (1) is no. The question in (2) is a bit more complicated, the Icon solution (and others on the original TWiki) use the built in string scanning/pattern matching to consume length so this kind of thing was not intended to count as a comparison. A full-blown regular expression might allow other ways to solve this than by consuming length. Provided it avoided explicit comparison and math it should probably be allowed. It would have to be a built-in regexp as a regexp procedure in the source language would likely violate one or more of the restrictions. But also, because of it's portability it really isn't showing off the characteristics of the language even if reg exp is built in and is a bit of a cheat in that sense. If it were the only way to do it, then yes, but if there were other ways to do it I think the intent of the task is to see those other ways. I could see some people submitting a regexp and non regexp version to show the variety. --Dgamey 06:00, 14 August 2011 (UTC)

No arithmetic operations

"No arithmetic operations, such as addition and subtraction, may be used."

I think this is clear. --Dgamey 12:35, 13 August 2011 (UTC)

Based on discussions below this is really about explicit math. It wasn't intended to exclude functions that implicitly advance a pointer/cursor. --Dgamey 06:00, 14 August 2011 (UTC)

Use only integers and strings

"The only datatypes you may are use are integer and string. In particular, you may not use lists."

To avoid semantic arguments, "lists" means lists/arrays/vectors in the broader sense. However, clearly in the case of C, where strings are arrays of characters, this needs to be relaxed a bit. Using arrays for other than strings would be a cheat here. --Dgamey 12:35, 13 August 2011 (UTC)

These restrictions are utterly nonsensical in J. Consider for example, in the C implementation p = &p[1]. Is that an arithmetic operator? In essence, it's computing p= p+1. Anyways, in J, the restrictions make no sense except by reinterpreting the meaning of the language in much the way that p = &p[1] may be reinterpreted as p= p+1. --Rdm 17:36, 14 August 2011 (UTC)

Since I don't know J, I really can't say and I can't really understand how they are nonsensical. I have to take your word on that. But I'm curious and would like to understand more. Beyond that I think the applicability of the task should be discussed in one place. It's starting to fragment. --Dgamey 19:02, 14 August 2011 (UTC)

Not pointless

I had to chuckle at the comment on the C submission as I think it proves the point quite well. Clearly, I need to document the point better :)

While I think about how to word it, let me explain. This site allows people to compare implementations in different languages. Restrictions force people to find other ways. To choose the road less traveled. Now this may require a technique that would be useful in some other problem but perhaps overkill in the simple unrestricted case. This can show people different techniques. The C contribution's cmp procedure is a case in point (I think). My C is very rusty (entirely seized up) and it doesn't look like a cheat to me. But I only have an inkling of how it may work. I'd have to crack my old copy of K&R and scratch my head a bit for it to be clear. A fluent C programmer would 't need to, but on the other hand they wouldn't be on this site to read code. Where I failed in the task description is to require people to provide some description of how they got around the restriction so that people coming from other languages will be able to understand. I'll add this to the task description. --Dgamey 13:01, 13 August 2011 (UTC)

Well, the cmp function doesn't contain arithmetic operators is not the same as the code uses no arithmetics. &p[1] is taking address of the next element of pointer p, i.e. p + 1. And if (p) is the same as if (p != 0), so one may argue if that contains comparison operator: it certain contains comparison operation. If these are allowed, because pointers can be converted to integers, there really isn't any restriction on arithmetics now: you can increment p by &p[1] and decrement it by &p[-1], you can compare it to zero, then you can do addition and subtraction; with those you can do mulplication and division; if you work hard enough you can probably get a whole math library in there. --Ledrug 19:57, 13 August 2011 (UTC)

Thanks for the explanation, my rusty old C memory had it about half figured out. Now while there is admittedly an end of string comparison and pointer advancement happening, I think this passes the spirit of the task. The implicit end of string test is a != comparison for a very specific purpose and the addressing is implicitly moving through a string. Looking at the solutions posted to the Unicon TWiki, automatically advancing a character was fine but if someone used s[p+1] it was considered in violation of the intent. --Dgamey 05:33, 14 August 2011 (UTC)

Also, Icon is implicitly advancing a cursor (&pos) inside the string scanning/matching which strikes me as equivalent to what is happening inside of cmp. --Dgamey 06:04, 14 August 2011 (UTC)

Icon uses boolean datatypes

'move(1)' must return something coerced to a boolean for the if statement/expression to work on its return value. In fact, their are more conditionals, so things are getting coerced to booleans there too. I think the problem statement could prove tough to tie down ;-)
--Paddy3118

Yet more. From the Icon comments:

move(1) - succeeds/fails ...

So move is a conditional itself. Which is not allowed. So the Icon example does not meet the conditions of the task statement!?

The language of the task is very loose and seems to be set up to dazzle students unwilling to argue a point when learning a new language. --Paddy3118 19:32, 13 August 2011 (UTC)

Icon success/failure is more like exception than data, in that they implicitly propagate outwards. In any event, some boolean stuff has to be there, because eventually one has to answer "is this longer than before". I think the goal is to avoid explicitly storing anything into a variable other than ints and strings, or explicitly doing math. It's gimmicky for sure, but it could be fun. --Ledrug 20:09, 13 August 2011 (UTC)

I'm not sure about explicitly storing, but the spirit of the task *is* to avoid explicit math and comparisons. In particular, avoiding explicit less/greater comparisons. --Dgamey 05:19, 14 August 2011 (UTC)

Icon has no boolean type. Expressions succeed (returning a value) or fails and do not. It's a form of short circuit evaluation. For example, it is not possible in Icon to run out of bounds of a list, string, etc. as doing so fails. 'move(1)' returns the next character in the string being scanned or fails if there is none. --Dgamey 05:19, 14 August 2011 (UTC)

Similarly, s[n] succeeds returning the n-th element of s (string or list) or fails --Dgamey 06:55, 14 August 2011 (UTC)

Request for Python explanation

Hi Ledrug,
Could you give me a brief explanation as to why your later Python example of: <lang python>import fileinput

1. return len(a) - len(b) if positive, 0 otherwise

def longer(a, b):

   while len(a) and len(b):
       a, b = a[1:], b[1:]
   return len(a)

longest, lines = , for x in fileinput.input():

   if longer(x, longest):
       lines, longest = x, x
   elif not longer(longest, x):
       lines += x

print(lines, end=)</lang>

Replaces: <lang python>import fileinput import operator as op

maxlen, maxlines = 0, for line in fileinput.input():

   ll = len(line)
   if op.gt(ll, maxlen):
       maxlen, maxlines = ll, line
   elif op.eq(ll, maxlen):
       maxlines = op.concat(maxlines, line)

print(maxlines, end=)</lang> It would help me understand the task a little better. Thanks. --Paddy3118 06:39, 14 August 2011 (UTC)

Under "No comparisons" above, Dgamey specifically listed "no comparison functions like lt(a, b)", so that pretty much ruled out op.gt. op.concat would have been fine, but lines += x is simpler. The longer function uses only substring and boolean operations (the and can be turned into nested if blocks if booleans ops are not allowed), so I think it does not breach the requirement of the task. --Ledrug 06:51, 14 August 2011 (UTC)

Ta. --Paddy3118 09:31, 14 August 2011 (UTC)