Length of longest contiguous digits exercise

C

Csaba Gabor

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?

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.
 
V

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;
}
 
R

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.
<snip>

function lenSort(a, b){
a = a.length;
b = b.length;
return (a < b) - (a > b);
}

(inputString.split(/[\D]/).sort(lenSort)[0]||'').length

Richard.
 
G

Gregor Kofler

Csaba Gabor meinte:

[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
 
T

Thomas 'PointedEars' Lahn

Johannes said:
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;}
)[0]||'').length

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
 
R

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.
 
D

Dr J R Stockton

In comp.lang.javascript message <b51c662c-25a5-4a0d-9c60-04582681d23c@q1
4g2000vbi.googlegroups.com>, Fri, 23 Oct 2009 02:15:40, Csaba Gabor
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.
 
A

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;
}
 
J

Jorge

  (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;
 
A

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.
 
T

Thomas 'PointedEars' Lahn

Asen said:
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.

The CMC7 Printed Image Specification is not relevant here, and
it has no subsection 15.10.6.2. It has been withdrawn anyway.


PointedEars
 
V

VK

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.
Something like a minor case of Diophantine equation solution algorithm
by Doug McIlroy from "Perl cookbook":

http://books.google.com/books?id=Iz...e&q=Diophantine Equation doug mcilroy&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.
 
D

Dr J R Stockton

In comp.lang.javascript message <867d40ac-de57-440a-8c2b-58424f2b2f07@f1
0g2000vbl.googlegroups.com>, Fri, 23 Oct 2009 14:26:17, Asen Bozhilov
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.
 
J

Jorge

Jorge said:
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 :)
 
T

Thomas 'PointedEars' Lahn

VK said:
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": ).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).


PointedEars"]
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).


PointedEars[/QUOTE]
 
A

Asen Bozhilov

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;
}
 
C

Csaba Gabor

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?


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
 
V

VK

Csaba said:
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

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!
 
W

wilq

Maybe less performant but...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top