Talk:Longest string challenge: Difference between revisions
→Not pointless: more on comparisons and math restrictions (as have been the last few updates) |
→Intent of Restrictions: more on intent and balance of intent |
||
Line 33: | Line 33: | ||
Beyond thinking outside the box, the restrictions need to be clear and will probably get reworded. |
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. --[[User:Dgamey|Dgamey]] 06:10, 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. --[[User:Dgamey|Dgamey]] 12:35, 13 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. --[[User:Dgamey|Dgamey]] 12:35, 13 August 2011 (UTC) |
Revision as of 06:10, 14 August 2011
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)?
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)
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)
- 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)
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)
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)
- 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)
No arithmetic operations
- "No arithmetic operations, such as addition and subtraction, may be used."
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)
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 pointerp
, i.e.p + 1
. Andif (p)
is the same asif (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)
- Well, the
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)
- 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)