Length of longest contiguous digits exercise
Csaba Gabor
length of the longest contiguous block of (numeric, base 10)
digits in a string. Something in the form of:
var mystr = "xy97 z0326 0654 943ab"
alert (... mystr ...) => 4
Further examples:
"" and "fred" => 0
"234" => 3
"10/23/2009" => 4
"12 345678901234567 89" => 15
"I usually awake after 9:30" => 2
"372 Myrtle Lane" => 3
"New York, NY 10001-2345" => 5
Note: If your solution involves a loop, then you should wrap
it in a function. Can you write it without any explicit loops?
Enjoy,
Csaba Gabor from Vienna
PS. In an attempt to forestall certain questions/comments:
This is an exercise - I encountered it this morning. I am posting
since my solution brushes on some interesting javascript points.
Wow, ought I really to be writing this? And just in case, my
shoe size is nine and a half US.
Jake Jarvis
> I'm looking for a "compact" expression that will return the
> length of the longest contiguous block of (numeric, base 10)
> digits in a string. Something in the form of:
>
> var mystr = "xy97 z0326 0654 943ab"
> alert (... mystr ...) => 4
>
> Further examples:
> "" and "fred" => 0
> "234" => 3
> "10/23/2009" => 4
> "12 345678901234567 89" => 15
> "I usually awake after 9:30" => 2
> "372 Myrtle Lane" => 3
> "New York, NY 10001-2345" => 5
>
>
> Note: If your solution involves a loop, then you should wrap
> it in a function. Can you write it without any explicit loops?
rhino 1.7R2:
function f(string) {
var x = [i.length for each (i in string.match(/\d+/g))];
return x.length ? Math.max.apply(null, x) : 0;
}
> PS. In an attempt to forestall certain questions/comments:
> This is an exercise - I encountered it this morning. I am posting
> since my solution brushes on some interesting javascript points.
> Wow, ought I really to be writing this?
Yes, I think so, leaves less room for speculation and misinterpretation.
--
Jake Jarvis
VK
> I'm looking for a "compact" expression that will return the
> length of the longest contiguous block of (numeric, base 10)
> digits in a string. Something in the form of:
>
> var mystr = "xy97 z0326 0654 943ab"
> alert (... mystr ...) => 4
>
> Further examples:
> "" and "fred" => 0
> "234" => 3
> "10/23/2009" => 4
> "12 345678901234567 89" => 15
> "I usually awake after 9:30" => 2
> "372 Myrtle Lane" => 3
> "New York, NY 10001-2345" => 5
>
> Note: If your solution involves a loop, then you should wrap
> it in a function. Can you write it without any explicit loops?
First I'd like to stress again that I am strongly opposing to
SqueeseCrypt'ing and I am trying to eliminate it in the controllable
environment by all possible means: from no doughnuts for the office
breakfast :) to no more contracts for that pathner :|
The reasons are - besides the readability and maintainability issues -
that SqueeseCrypt'ing very often involves most refine parts of
language specs and respectively makes the product dependent on the
perfect engine implementation and in case of alas often specs
ambiguity - dependent on that exact reading implemented on the
development machine. See for instance the issue discussion followed in
"Splicing exercise".
All this applies to SqueeseCrypt'ing only thus "creating the program
that does the necessary job by using the minimum significant
characters in the source code". It doesn't affect the code
optimization and superfluous instructions removal where I'm totally
supportive.
Having pronounced all these blah-blah :) here would be my solution:
function f(str) {
var re = new RegExp('(\\d+)', 'g');
RegExp.lastIndex = -1;
var tmp = null;
var max = 0;
while ((tmp = re.exec(str)) != null) {
if (tmp[0].length > max) {
max = tmp[0].length;
}
}
return max;
}
Richard Cornford
> I'm looking for a "compact" expression that will return the
> length of the longest contiguous block of (numeric, base 10)
> digits in a string.
function lenSort(a, b){
a = a.length;
b = b.length;
return (a < b) - (a > b);
}
(inputString.split(/[\D]/).sort(lenSort)[0]||'').length
Richard.
Johannes Baagoe
> function lenSort(a, b){
> a = a.length;
> b = b.length;
> return (a < b) - (a > b);
> }
>
> (inputString.split(/[\D]/).sort(lenSort)[0]||'').length
(inputString.split(/[\D+]/).sort(lenSort)[0]||'').length
would be more efficient.
lenSort could be simplified and defined anonymously :
(inputString.split(/[\D+]/).sort(
function(a, b) {return a.length - b.length;}
)[0]||'').length
--
Johannes
Johannes Baagoe
> lenSort could be simplified and defined anonymously :
>
> (inputString.split(/[\D+]/).sort(
> function(a, b) {return a.length - b.length;}
> )[0]||'').length
Oops, sorry :
(inputString.split(/[\D+]/).sort(
function(a, b) {return b.length - a.length;}
Gregor Kofler
[snip]
> PS. In an attempt to forestall certain questions/comments:
> This is an exercise - I encountered it this morning. I am posting
> since my solution brushes on some interesting javascript points.
Show your efforts. Or are we supposed to do some homework for you?
Gregor
Johannes Baagoe
> Or are we supposed to do some homework for you?
Don't you ever program for *fun* ?
--
Johannes
Thomas 'PointedEars' Lahn
It's still not going to work as intended, because [\D+] matches either a
single \D (not a decimal digit) or a single `+'. The both of you were
probably looking for
(inputString.split(/\D+/).sort(
function(a, b) { return b.length - a.length; }
)[0] || '').length
PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
Richard Cornford
> Richard Cornford :
>
>> function lenSort(a, b){
>> a = a.length;
>> b = b.length;
>> return (a < b) - (a > b);
>> }
>
> > (inputString.split(/[\D]/).sort(lenSort)[0]||'').length
>
> (inputString.split(/[\D+]/).sort(lenSort)[0]||'').length
>
> would be more efficient.
No, but putting a + after the closing square bracket might (and was
the thought in my mind when I wrote it, but not what I typed).
> lenSort could be simplified and defined anonymously :
>
> (inputString.split(/[\D+]/).sort(
> function(a, b) {return a.length - b.length;}
> )[0]||'').length
Inline means that a function object is created each time the
expression is evaluated, which seems likely to be more than once else
who cares how short it is. And anonymous means that a potentially
generally useful function for sorting by the length of items in an
array (might sort arrays of arrays, strings in arrays or objects with
length properties) is unavailable to the rest of the system.
Richard.
Johannes Baagoe
> It's still not going to work as intended, because [\D+] matches either a
> single \D (not a decimal digit) or a single `+'. The both of you were
> probably looking for
>
> (inputString.split(/\D+/).sort(
> function(a, b) { return b.length - a.length; }
> )[0] || '').length
ACK.
--
Johannes
Johannes Baagoe
> Inline means that a function object is created each time the expression
> is evaluated, which seems likely to be more than once else who cares how
> short it is. And anonymous means that a potentially generally useful
> function for sorting by the length of items in an array (might sort
> arrays of arrays, strings in arrays or objects with length properties)
> is unavailable to the rest of the system.
I understood the exercise as a call for cute one-liners, not something
that may actually be called thousands of times in production code.
In that spirit, the "+" in the RegExp seems justified to me even if it
adds one character. Global variables or functions do not, especially not a
quite unnecessarily complicated sort function. YMMV.
--
Johannes
Gregor Kofler
> Gregor Kofler :
>
>> Or are we supposed to do some homework for you?
>
> Don't you ever program for *fun* ?
Frequently.
Gregor
Asen Bozhilov
> I'm looking for a "compact" expression that will return the
> length of the longest contiguous block of (numeric, base 10)
> digits in a string. Something in the form of:
>
> var mystr = "xy97 z0326 0654 943ab"
> Can you write it without any explicit loops?
function f(str)
{
var count = 0;
str.replace(/\d+/g, function(a)
{
if (a.length > count)
{
count = a.length;
}
});
return count;
}
Dr J R Stockton
4g2000vbi.googlegroups.com>, Fri, 23 Oct 2009 02:15:40, Csaba Gabor
<dan...@gmail.com> posted:
>I'm looking for a "compact" expression that will return the
>length of the longest contiguous block of (numeric, base 10)
>digits in a string.
S = "123xx000000004hh65453kk"
X = []
X[0] = String(eval("Math.max(" + S.match(/(\d+)/g) + ")")).length
X[1] = eval(
"Math.max('" + S.match(/(\d+)/g).join("'.length,'") + "'.length" + ")"
)
The first result neglects leading zeros; the second does not. They
should also work with split(/\D+/).
The sorting methods might do better to reverse the sort order.
--
(c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton@physics.org
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct <= 4-line sig. separator as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)
Jorge
wrote:
>
> (inputString.split(/\D+/).sort(
> function(a, b) { return b.length - a.length; }
> )[0] || '').length
s.split(/\D+/).sort(function(a,b){return b.length-a.length})
[0].length;
--
Jorge.
kangax
or:
s.match(/\d+/g).sort(function(a,b){return b.length-a.length})[0].length
--
kangax
Asen Bozhilov
> or:
>
> s.match(/\d+/g).sort(function(a,b){return b.length-a.length})[0].length
That is error prone. If `s' doesn't contains any decimal digit, match
will be return primitive value null. In documentation match use
RegExp.prototype.exec. See 15.10.6.2 in ECMA 3.
VK
I may be wrong but I am getting an impression that the "spice" of this
exercise is not in inner sort functions for regexp matches but in
using back-references and "controllable greediness" in regexp.
Something like a minor case of Diophantine equation solution algorithm
by Doug McIlroy from "Perl cookbook":
http://books.google.com/books?id=IzdJIax6J5oC&pg=PA217&lpg=PA217&dq=Diophantine+Equation+doug+mcilroy&source=bl&ots=z6Bj9w89hR&sig=JcPQvOa_CRSeq6ip2jnw3dVBAR8&hl=en&ei=y9viSoCkN4bY-Qbs4MTpAQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAoQ6AEwAA#v=onepage&q=Diophantine%20Equation%20doug%20mcilroy&f=false
I am personally in regexps like a pig in oranges :) :( but just
remembered that unusual regexp application from my book so searched
for it online. If my feelings are anyhow right then the solution can
be a single regexp return value.
Thomas 'PointedEars' Lahn
The CMC7 Printed Image Specification is not relevant here, and
it has no subsection 15.10.6.2. It has been withdrawn anyway.
PointedEars
--
Danny Goodman's books are out of date and teach practices that are
positively harmful for cross-browser scripting.
-- Richard Cornford, cljs, <cife6q$253$1$8300...@news.demon.co.uk> (2004)
Richard Cornford
>On Oct 23, 6:16 pm, Thomas 'PointedEars' Lahn wrote:
>>
>> (inputString.split(/\D+/).sort(
>> function(a, b) { return b.length - a.length; }
>> )[0] || '').length
>
> s.split(/\D+/).sort(function(a,b){return b.length-a.length})
> [0].length;
In JScript the expression - "fred".split(/\D+/).length - produces the
value zero, while in JavaScript(tm) it produces 2. JavaScript(tm) leaves
the two empty strings at each end of "fred" while JScript does not. If
an array has zero length then looking up the element with the '0' index
will result in undefined, and attempting to read the - length - property
of undefined will result in a runtime error. The - || '' - in my
original handled that possibility, and the odds are that if someone had
a serious use for this expression they would want it work with JScript.
Richard.
Richard Cornford
> Richard Cornford :
>> Inline means that a function object is created each time the
>> expression is evaluated, which seems likely to be more than once
>> else who cares how short it is. And anonymous means that a
>> potentially generally useful function for sorting by the length
>> of items in an array (might sort arrays of arrays, strings in
>> arrays or objects with length properties) is unavailable to the
>> rest of the system.
>
> I understood the exercise as a call for cute one-liners,
There is certainly that implication, but also talk of wrapping the whole
thing up in a function in the event of its becoming too cumbersome or
not being practical for a single expression. If there is a reason for
having a pre-declared function here I would rather that function be a
general function for comparing lengths than a very specific function
that would tell you the length of the longest continuous sequence of
decimal digits in a spring.
> not something that may actually be called thousands of times in
> production code.
That never would have happened. Even looping through each character in
the string counting the lengths of sequences wouldn't take more than 10
lines of code.
> In that spirit, the "+" in the RegExp seems justified to me even
> if it adds one character. Global variables or functions do not,
Who is saying that it has to be global, but even if global then so what?
Give it a descriptive name and the odds of significant naming
collisions are extremely low (and imply someone creating a function that
does one thing and giving it a name that implies that it does another).
> especially not a
> quite unnecessarily complicated sort function. YMMV.
In context the extra complexity of that sort function is not necessary,
but as a general sort function the risk of its returning NaN might be
better avoided.
Richard.
Jorge
wrote:
> Jorge wrote:
> >On Oct 23, 6:16 pm, Thomas 'PointedEars' Lahn wrote:
>
> >> (inputString.split(/\D+/).sort(
> >> function(a, b) { return b.length - a.length; }
> >> )[0] || '').length
>
> > s.split(/\D+/).sort(function(a,b){return b.length-a.length})
> > [0].length;
>
> In JScript the expression - "fred".split(/\D+/).length - produces the
> value zero, while in JavaScript(tm) it produces 2. JavaScript(tm) leaves
> the two empty strings at each end of "fred" while JScript does not. If
> an array has zero length then looking up the element with the '0' index
> will result in undefined, and attempting to read the - length - property
> of undefined will result in a runtime error.
I see, JScript (again), I should stop ignoring it so blatantly.
> The - || '' - in my
> original handled that possibility,
Perfect. Very well done.
> and the odds are that if someone had
> a serious use for this expression they would want it work with JScript.
Seriousness is directly proportional to M$-compliance, seriousness is
directly proportional to M$-compliance, seriousness is... (repeat 100
times :-)
--
Jorge.
Dr J R Stockton
0g2000vbl.googlegroups.com>, Fri, 23 Oct 2009 14:26:17, Asen Bozhilov
<asen.b...@gmail.com> posted:
>On 23 ïËÔ, 12:15, Csaba Gabor <dans...@gmail.com> wrote:
>> I'm looking for a "compact" expression that will return the
>> length of the longest contiguous block of (numeric, base 10)
>>
>> var mystr = "xy97 z0326 0654 943ab"
>> ...
>> Can you write it without any explicit loops?
>
>function f(str)
>{
> var count = 0;
> str.replace(/\d+/g, function(a)
> {
> if (a.length > count)
> {
> count = a.length;
> }
> });
> return count;
>}
Use
count = Math.max(count, a.length) // untested
and you also avoid conditional statements.
Your anonymous function returns undefined. It *might* be faster to
return either an empty string or a string of the same length as "a"; you
do, after all, have one to hand.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF3 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Thomas 'PointedEars' Lahn
> On Oct 24, 1:20 pm, Asen Bozhilov <asen.bozhi...@gmail.com> wrote:
>> On 24 ïËÔ, 05:10, kangax <kan...@gmail.com> wrote:
>> > or:
>>
>> > s.match(/\d+/g).sort(function(a,b){return b.length-a.length})[0].length
>>
>> That is error prone. If `s' doesn't contains any decimal digit, match
>> will be return primitive value null. In documentation match use
>> RegExp.prototype.exec. See 15.10.6.2 in ECMA 3.
>
> I may be wrong but I am getting an impression that the "spice" of this
> exercise is not in inner sort functions for regexp matches but in
> using back-references and "controllable greediness" in regexp.
You *are* wrong.
> Something like a minor case of Diophantine equation solution algorithm
> by Doug McIlroy from "Perl cookbook": [URL]
> I am personally in regexps like a pig in oranges :) :( but just
> remembered that unusual regexp application from my book so searched
> for it online. If my feelings are anyhow right then the solution can
> be a single regexp return value.
"regexp return value" is gibberish again. However,
(s.match(/\d+/g) || [""]).sort(
function(a, b) {
return b.length - a.length;
})[0].length
is a solution (applying what you might mean) that apparently has not been
posted yet (a fix for kangax's solution). It should score over Richard's
split() solution if the average length of the decimal numbers in `s' is
shorter than the average length of the delimiting non-decimal characters in
`s' (as less characters need to be matched then), and it does not require a
workaround for JScript in any case (older, unsupporting versions aside).
Asen Bozhilov
wrote:
> Use
> count = Math.max(count, a.length) // untested
> and you also avoid conditional statements.
>
> Your anonymous function returns undefined. It *might* be faster to
> return either an empty string or a string of the same length as "a"; you
> do, after all, have one to hand.
When i post my solution, after that i modified my code, and your
correction is exactly what i modified :)
That is code on my local machine:
function f(str)
{
var count = 0;
str.replace(/\d+/g, function(a)
{
count = Math.max(a.length, count);
return a;
});
return count;
}
Csaba Gabor
> I'm looking for a "compact" expression that will return the
> length of the longest contiguous block of (numeric, base 10)
>
> var mystr = "xy97 z0326 0654 943ab"
>
> Further examples:
> "" and "fred" => 0
> "234" => 3
> "10/23/2009" => 4
> "12 345678901234567 89" => 15
> "I usually awake after 9:30" => 2
> "372 Myrtle Lane" => 3
> "New York, NY 10001-2345" => 5
>
> Note: If your solution involves a loop, then you should wrap
To clarify, the intent of the exercise was not "cute" solutions.
Rather, my interest was on array transformations as a way of
looking at these types of problems (a value needed from an
array of data) rather than loops. Loops are still implied,
but javascript internal loops ought to be far more efficient
than explicit for loops. The reason for the alert(...mystr...)
form was to encourage the single expression solution.
There have been a lot of good ideas on this exercise. One thing
that might make things easier is the realization that the values
of the digits are immaterial. In particular, by doing
s.replace(/\d/,"1") the problem is reduced to that of finding
the longest sequence of 1s. That makes a difference because
now we don't have to worry about pesky leading 0s and sorting
lexigraphically is now equivalent to sorting numerically.
All four of the following examples assume that the source
string is s.
For example, we can now do:
alert((s.replace(/\d/g,"1") // convert nums to all 1s
.split(/\D+/) // make array of the 1 strings
.sort() // sort them (longest at end)
.slice(-1)[0]||'') // get the final one
.length); // and show its length
Using Math.max is not so smooth because the degenerate
cases on FF/IE are treated differently by Math.max
The problem can be circumvented by augmenting each
string by 1, and then subtracting 1 off of the length
at the end. Note that the "1 " string being prepended
serves two purposes. The 1 ensures that match will find
at least one entry, and the space ensures that the first
numeric sequence has a non one prefixing it so that it
will be augemented by 1 in the next step.
alert((Math.max.apply(0, // Take a max
('1 ' // Corresponds to 0
+ s.replace(/\d/g,"1")) // Convert each digit to 1
.replace(/\D1/g," 11") // Augment each # (except 1st) by "1"
.match(/\d+/g) // Make an array of the 1 strings
)+'') // Coerce max to string
.length-1); // Find augmented len, subtract 1
For Vikram's pleasure, here are two RegExp approaches.
This first one works by removing a digit from each
contiguous block of digits on each iteration of a loop.
The length of the longest contiguous block is the number
of iterations through the loop until all the digits are gone.
for (var c=0; // counter c
s.match(/\d/); // Loop until no more digits in s
s=s.replace( // Remove a 1 from each block
/\d(?=\D|$)/g)) // of digits
++c; // Count the number of iterations
alert(c);
This final method is a "loopless" regular expression, but
internally it's quite busy. I was surprised to have it
come out so compactly. As with all my examples, the digits
are first replaced with a 1. The match is divided into two
parts. The shorter left half accounts for those cases
where there is no digit in the original string.
The right helf of the match is a bit trickier, and I will
gloss over some of the details. The (1+) says to identify
a complete contiguous block of 1s. It's complete because
the 1+ is greedy and slurps up as many 1s as it can (If
the rest of the pattern fails, then it will also fail if
less 1s are slurped up - I think PHP regular expressions
have a way of preventing the backtracking, but I don't
think javascript regular expressions support it).
In any case, this contiguous block of 1s is remembered
(captured). Now here's the important point: If this
is the longest contiguous block, then this captured
string must not appear at any other point in the string.
In other words, our match will be successful, if our
captured string does not match anywhere in the rest
of the string! In other words, we want to do a
negative lookahead at every remaining character in the
string, and that is exactly what the rest of the
right half is doing. Now should the captured group
match (which means that the overall pattern fails at
that point), that means there is a group of 1s to the
right of the current point which are at least as long
and so the pattern will eventually migrate the
captured block of 1s to that point and try from there.
The [1] accesses the captured (longest) block.
Under FF, this is undefined when there is no capture
(which happens when there are no digits in the
original string, so for that reason there is a ||""
along with surrounding parens. Finally, the length
of the captured (longest) block is returned.
Here's the expression (comments in the regular
expression must be removed before running):
alert((
s.replace(/\d/g,"1") // Convert all digits to 1
.match(/^\D*$| // Match if no 1s
(1+) // Capture block of 1s
(.(?!\1))*$/) // Match if captured block
// is not repeated
[1]||"") // Access captured block
.length); // and get its length
Csaba Gabor from Vienna
VK
Bingo! Proudly reminding my hint I tried to give:
http://groups.google.com/group/comp.lang.javascript/msg/0076433d24517f82
:)
In my my other attempts I was also first uniforming all digits to
convert the task from stringified to numeral aspect but I was using 9
instead of 1, a reflection of my maximalism or of my greediness :)
All attempts were dropped any way as my regexp skills are highly
insufficient.
Thank you for the mind gim!
wilq
function a(a){
return Math.max.apply(Math,a.replace(/(\b.+?\b)/g,function(b,c)
{ return c.match(/\D/) ? " " : c.length}).split(/\b/));
}
;D