Fedora Linux Support Community & Resources Center
  #1  
Old 18th November 2013, 11:20 PM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxfirefox
Programming Challenge: Comparing Numbers in a String

One of my teachers pointed out this programming problem to me from here: http://damienkatz.net/2005/09/fun-problem.html

Quote:
Design and write, using ISO C (no C++ or language extentions), an implementation for the following function prototype:

int numcmp(const char *s1, const char *s2);

The function numcmp assumes that both null-terminated strings s1 and s2 contain one or more digits and at most one decimal point ('.'); the result for input strings not of this form is not defined. The function compares the contents of the null-terminated string s1 with the contents of the null-terminated string s2. Using a numerical interpretation for the strings, it returns a value of type int that is less than zero if s1 is less than s2; equal to zero if s1 is equal to s2; and greater than zero if s1 is greater than s2.

The function interface is similar to that of strcmp from the standard C library "string.h". It can be used in place of strcmp when a numeric comparison is needed in place of a lexicographic comparison.

The result of the function should be the same as a comparison of the numerical values of represented by the strings. (Examples: "0" is equal to "000"; "12" is equal to "0012"; "100" is greater than "99"; ".02" is greater than "0.001")

The the comparison should be implemented using only simple character processing. (It should not be implemented using float or double.)

There is no limit on the number of digits in the input strings. The implementation should not impose a restriction on the length of the strings.
Do not use any library functions (including the standard libraries) in your implementation.
Example input strings:

0
00000
001
1
000.00000
00.000000001
12345
30000000.00000000000000300000000000001000001
234982732487618236876
.0001
10000.
6787687687682344442837612836626387612387163.23435
0000100000000000000000.000000000000000000000000000 01
0000100000000000000000.000000000000000000000000000 02
I think we shouldn't limit the examples to C. Any language that doesn't make use of the standard library should be fine as long as it fits this standard.

Here's my solution in C:

Code:
#include <stdio.h>

int numcmp(const char *s1, const char *s2);

int numcmp(const char *s1, const char *s2)
{
    int retval = 0;
    int frac_flag = 0;

    while (*s1 == '0')
        s1++;
    while (*s2 == '0')
        s2++;

    while (*s1 != '\0' && *s2 != '\0') {
        if (*s1 != '.' && *s2 == '.') {
            return 1;
        }
        else if (*s1 == '.' && *s2 != '.') {
            return -1;
        }
        else if (*s1 == '.' && *s2 == '.') {
            frac_flag = 1;
            if (retval != 0) {
                return retval;
            }
        }

        if (retval == 0 && *s1 < *s2) {
            retval = -1;
        }
        else if (retval == 0 && *s1 > *s2) {
            retval = 1;
        }

        ++s1;
        ++s2;
    }

    while (*s1 != '\0') {
        if (frac_flag == 0) {
            return 1;
        }
        else if (*s1 > '0' && retval == 0) {
            return 1;
        }

        ++s1;
    }

    while (*s2 != '\0') {
        if (frac_flag == 0) {
            return -1;
        }
        else if (*s2 > '0' && retval == 0) {
            return -1;
        }

        ++s2;
    }

    return retval;
}

int main()
{
    printf("%d\n", numcmp("5", "5") == 0);
    printf("%d\n", numcmp("0015", "15") == 0);
    printf("%d\n", numcmp("0.005", ".005") == 0);
    printf("%d\n", numcmp("5", "3") == 1);
    printf("%d\n", numcmp("5", "0.3") == 1);
    printf("%d\n", numcmp("0.05", "0.005") == 1);
    printf("%d\n", numcmp("0000100000000000000000.00000000000000000000000000001","0000100000000000000000.00000000000000000000000000002") == -1);
    printf("%d\n", numcmp("5", "6") == -1);
    printf("%d\n", numcmp("5", "55") == -1);
    printf("%d\n", numcmp("5", "40") == -1);
    printf("%d\n", numcmp(".00001", "10000.") == -1);
    printf("%d\n", numcmp("100000.00000", "200000.00000") == -1);

    return 0;
}
So how would you do it?
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC

Last edited by Flounder; 18th November 2013 at 11:36 PM. Reason: Added a few things I forgot.
Reply With Quote
  #2  
Old 19th November 2013, 04:04 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Should "5." and "5" be equal? In your example numcmp("5.", "5") returns 1, not 0.
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #3  
Old 19th November 2013, 01:38 PM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxfirefox
Re: Programming Challenge: Comparing Numbers in a String

You are right it should be equal. This has been turning out to be a harder problem than I thought.

I have been reworking the solution to use only one variable besides the two passed in and this is what I have now.

Code:
#include <stdio.h>                                                                                                                                                                  
                                                                                                                                                                                    
int numcmp(const char *s1, const char *s2);                                                                                                                                         
                                                                                                                                                                                    
int numcmp(const char *s1, const char *s2)                                                                                                                                          
{                                                                                                                                                                                   
    int retval = 0;                                                                                                                                                                 
                                                                                                                                                                                    
/* Advance past all leading zeros */
    while (*s1 == '0')
        s1++;
    while (*s2 == '0')
        s2++;

/* Compare first difference and advance through the integer
 * portion of the string
 */
    while (*s1 >= '0' && *s1 <= '9' && *s2 >= '0' && *s2 <= '9') {
        if (retval == 0 && *s1 < *s2)
            retval = -1;
        else if (retval == 0 && *s1 > *s2)
            retval = 1;

        ++s1;
        ++s2;
    }

/* compare to see if one string is really longer
 * than the other
 */

    if (*s1 == '.' && *s2 != '\0' && *s2 != '.')
        return -1;
    else if (*s1 != '.' && *s1 != '\0' && *s2 == '.')
        return 1;
    else if (*s1 == '.' && *s2 == '.' && retval != 0)
        return retval;
    else if (*s1 != '.' && *s1 != '\0' && *s2 == '\0')
        return 1;
    else if (*s2 != '.' && *s2 != '\0' && *s1 == '\0')
        return -1;

/* check digits for any difference in both strings */

    while (*s1 != '\0' && *s2 != '\0') {
        if (*s1 < *s2)
            return -1;
        else if (*s1 > *s2)
            return 1;

        ++s1;
        ++s2;
    }

/* check remaining strings to see if one is greater than
   the other past the decimal point */

    while (*s1 != '\0') {
        if (*s1 > '0')
            return 1;
        ++s1;
    }

    while (*s2 != '\0') {
        if (*s2 > '0')
            return -1;
        ++s2;
    }

    return retval;
}

int main()
{
    printf("%d\n", numcmp("5", "5") == 0);
    printf("%d\n", numcmp("5.", "5") == 0);
    printf("%d\n", numcmp("0015", "15") == 0);
    printf("%d\n", numcmp("0.005", ".005") == 0);
    printf("%d\n", numcmp("5", "3") == 1);
    printf("%d\n", numcmp("5", "0.3") == 1);
    printf("%d\n", numcmp("0.05", "0.005") == 1);
    printf("%d\n", numcmp("0000100000000000000000.00000000000000000000000000001","0000100000000000000000.00000000000000000000000000002") == -1);
    printf("%d\n", numcmp("5", "6") == -1);
    printf("%d\n", numcmp("5", "55") == -1);
    printf("%d\n", numcmp("5", "40") == -1);
    printf("%d\n", numcmp(".00001", "10000.") == -1);
    printf("%d\n", numcmp("100000.00000", "200000.00000") == -1);

    return 0;
}
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC

Last edited by Flounder; 19th November 2013 at 02:00 PM.
Reply With Quote
  #4  
Old 19th November 2013, 02:02 PM
jpollard Offline
Registered User
 
Join Date: Aug 2009
Location: Waldorf, Maryland
Posts: 7,347
linuxfirefox
Re: Programming Challenge: Comparing Numbers in a String

The tests breaks down into two parts:

Trimming leading zeros is useful, but the two numbers have to be normalized first.

Normalize the two numbers at the decimal point (or end of string).

Since you now know where the decimal point is, and the starting point of both strings, the first comparison would be of the length:

This alone will tell you which is the larger without having to compare anything else (the longer one is larger...).

If both are the same then compare the first part of each string (yeah, the slow way). A difference here will tell which is larger.

If both are equal, then you compare the fractions - after trimming
trailing 0s (not the fastest, but it makes the final comparison easier). You get to quit as soon as one byte is larger than the other... If both are equal when you get to the end of one string you do know which is larger - whichever string is not at the end is the larger. (which is why trimming the trailing zeros helps).
Reply With Quote
  #5  
Old 20th November 2013, 12:41 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

I think I have a solution. It's in Java, save it as numcomp.java:
Code:
public class numcomp {
   public static boolean hasDot(String s) {
      if (s.indexOf('.') < 0) {
         return false;
      } else {
         return true;
      }
   }

   public static int numcmp(String s1, String s2) {
      //Remove all leading/trailing zeros and any trailing dot
      if (s1.startsWith("0") && !s1.equals("0")) {
         return numcmp(s1.substring(1), s2);
      } else if (s1.equals(".") || s1.equals(".0")) {
         return numcmp("0", s2);
      } else if (s2.startsWith("0") && !s2.equals("0")) {
         return numcmp(s1, s2.substring(1));
      } else if (s2.equals(".") || s2.equals(".0")) {
         return numcmp(s1, "0");
      } else if ((hasDot(s1) && s1.endsWith("0")) || s1.endsWith(".")) {
         return numcmp(s1.substring(0, s1.length()-1), s2);
      } else if ((hasDot(s2) && s2.endsWith("0")) || s2.endsWith(".")) {
         return numcmp(s1, s2.substring(0, s2.length()-1));
      }

      //Handle case where both are integers
      if (!hasDot(s1) && !hasDot(s2)) {
         if (s1.length() > s2.length()) {
            return 1;
         } else if (s1.length() < s2.length()) {
            return -1;
         } else { //Same length, compare the first digit
            char c1 = s1.charAt(0);
            char c2 = s2.charAt(0);
            if (c1 > c2) {
               return 1;
            } else if (c1 < c2) {
               return -1;
            } else if (s1.length() == 1) { //Both are single digits
               return 0;
            } else { //Chop off the first digit
               return numcmp(s1.substring(1), s2.substring(1));
            }
         }
      }

      //At least one is a decimal, get the integer and decimal parts
      int dot1 = s1.indexOf(".");
      int dot2 = s2.indexOf(".");
      String intpart1 = "0";
      String decpart1 = "0";
      String intpart2 = "0";
      String decpart2 = "0";
      if (dot1 < 0) { //No dot, only an integer part
         intpart1 = s1;
      } else if (dot1 == 0) { //Starts with a dot, only a decimal part
         decpart1 = s1.substring(1);
      } else { //Has integer and decimal parts
         intpart1 = s1.substring(0, dot1);
         decpart1 = s1.substring(dot1 + 1);
      }
      if (dot2 < 0) { //No dot, only an integer part
         intpart2 = s2;
      } else if (dot2 == 0) { //Starts with a dot, only a decimal part
         decpart2 = s2.substring(1);
      } else { //Has integer and decimal parts
         intpart2 = s2.substring(0, dot2);
         decpart2 = s2.substring(dot2 + 1);
      }
      //First compare the integer parts
      int intComp = numcmp(intpart1, intpart2);
      if (intComp == 0) { //Equal integer parts, so compare the decimal parts
         //Right-pad the shortest decimal part with zeros to make the two parts have the same length
         int len1 = decpart1.length();
         int len2 = decpart2.length();
         if (len1 < len2) { //Right pad decpart1
            for (int i = len1; i < len2; i++) decpart1 += "0";
         } else if (len1 > len2) { //Right pad decpart2
            for (int i = len2; i < len1; i++) decpart2 += "0";
         }
         return numcmp(decpart1, decpart2);
      } else {
         return intComp;
      }
   }

   public static void main(String[] args) {
      System.out.println("numcmp = " + numcmp(args[0], args[1]));
   }
}
Compile it like this:
Code:
javac numcomp.java
The program takes two arguments -- the strings to compare -- which you can enclose in quotes or not (Java treats them as strings regardless).
Some sample results:
Code:
$ java numcomp "5" "5"
numcmp = 0
$ java numcomp "0015" "15"
numcmp = 0
$ java numcomp "0.005" ".005"
numcmp = 0
$ java numcomp "5" "3"
numcmp = 1
$ java numcomp "5" "0.3"
numcmp = 1
$ java numcomp "0.05" "0.005"
numcmp = 1
$ java numcomp "0000100000000000000000.00000000000000000000000000001" "0000100000000000000000.00000000000000000000000000002"
numcmp = -1
$ java numcomp "5" "6"
numcmp = -1
$ java numcomp "5" "55"
numcmp = -1
$ java numcomp "5" "40"
numcmp = -1
$ java numcomp ".00001" "10000."
numcmp = -1
$ java numcomp "100000.00000" "200000.00000"
numcmp = -1
$ java numcomp "5" "5."
numcmp = 0
$ java numcomp "00100" "100.00000"
numcmp = 0
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #6  
Old 20th November 2013, 04:40 AM
ocratato Online
Registered User
 
Join Date: Oct 2010
Location: Canberra
Posts: 2,536
linuxfirefox
Re: Programming Challenge: Comparing Numbers in a String

Here is my C++ solution using a state machine approach that makes a single pass through the strings:
Code:
#include <stdlib.h>
#include <iostream>

using namespace std;

// class that provides virtual trailing decimal and zeros for numeric string
//
class Number
{
private:
	const char *ptr;
	int state;  // 0 - integer part; 1 - on decimal point; 2 - decimal part
	char c;
public:
	Number( const char *&s );
	void next();
	char Char() { return c; }
	bool atEnd();
};

Number::Number( const char *&s )
	: ptr( s )
{
	while( *ptr == '0' ) ptr++;
	if ( *ptr == '\0' ) state = 1;
	else if ( *ptr == '.' ) state = 1;
	else state = 0;
	next();
}

bool Number::atEnd()
{
	return (*ptr == '\0');
}

void Number::next()
{
	switch ( state )
	{
		case 0:
			c = *ptr;
			ptr++;
			if ( *ptr == '\0' || *ptr == '.' ) state = 1;
			break;
		case 1:
			c = '.';
			if ( *ptr ) ptr++;
			state = 2;
			break;
		case 2:
			if ( *ptr ) c = *ptr++;
			else c = '0';
			break;
		default:
			cerr << "???" << endl;
			exit(1);
	}
}

int numcomp( const char *s1, const char *s2 )
{
	// single pass state machine solution
	Number a(s1), b(s2);
	int state = 1;
	while ( true )
	{
		char A = a.Char(), B = b.Char();
		// cout << state << " " << A << " " << B << endl;
		switch( state )
		{
			case 1:	// equal integer part digits so far
				if ( A == '.' && B == '.' ) state = 4;
				else if (A == '.') return -1;
				else if (B == '.') return +1;
				else if (A > B ) state = 2;
				else if (A < B ) state = 3;
				// else state = 1
				break;

			case 2:	// a is larger unless b is longer integer part
				if ( A == '.' && B == '.' ) return +1;
				else if ( A == '.' ) return -1;
				else if ( B == '.' ) return +1;
				break;

			case 3: // b is larger unless a is longer integer part
				if ( A == '.' && B == '.' ) return -1;
				else if ( A == '.' ) return -1;
				else if ( B == '.' ) return +1;
				break;

			case 4:	// equal integer parts so look for first difference
				// in decimal part
				if ( A > B ) return +1;
				else if ( A < B ) return -1;
				else if ( a.atEnd() && b.atEnd() ) return 0;
				break;

			default:
				cerr << "unexpected state: " << state << endl;
				return -2;
				break;
		}
		a.next(); b.next();
	}
	// not reached
	return 0;
}

int main( int argc, char *argv[] )
{
	cout << argv[1] << "  " << argv[2] << endl;
	cout << numcomp( argv[1], argv[2] ) << endl;
	return 0;
}
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.
Reply With Quote
  #7  
Old 20th November 2013, 11:13 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's a bash version:
Code:
#!/bin/bash
shopt -s extglob

# Function to format a string into a decimal format (x.y or .x)
function makeDecimalFormat () {
   local s="$1"
   if [[ "$s" == *.* ]]; then   # Decimal form, strip trailing zeros
      s="${s/%+(0)/}"
      if [[ "$s" == *. ]]; then # Don't allow a trailing dot
         s="${s}0"
      fi
   else  # Integer form, append a .0
      s="${s}.0"
   fi
   echo -n "$s"
}

# Function to compare strings of equal length (including length 0)
function compare () {
   local S1="$1"
   local S2="$2"
   local length=${#S1}
   for ((i = 0; i < length; i++)) { # Compare characters from left to right
      if [[ "${S1:i:1}" > "${S2:i:1}" ]]; then
         echo -n 1
         return
      elif [[ "${S1:i:1}" < "${S2:i:1}" ]]; then
         echo -n -1
         return
      fi
   }
   echo -n 0
}

# Function to right-pad a string with zeros up to the provided length
function rightPad () {
   local s="$1"
   local length=$2
   while [ ${#s} -lt ${length} ]
   do
      s="${s}0"
   done
   echo -n "$s"
}

# Function to compare two strings of any lengths
function numcmp () {
   local s1="$1"
   local s2="$2"

   # Strip any leading zeros and force into a decimal format (x.y or .x)
   s1="$(makeDecimalFormat ${s1/#+(0)/})"
   s2="$(makeDecimalFormat ${s2/#+(0)/})"

   # Break each string into integer and decimal parts
   intpart1="${s1%.*}" # This could be empty
   decpart1="${s1#*.}"
   intpart2="${s2%.*}" # This could be empty
   decpart2="${s2#*.}"

   # First compare the (possibly empty) integer parts by length
   if [ ${#intpart1} -gt ${#intpart2} ]; then
      echo -n 1
   elif [ ${#intpart1} -lt ${#intpart2} ]; then
      echo -n -1
   else # The integer parts have the same length, compare them character-wise
      result="$(compare ${intpart1} ${intpart2})"
      if [[ "${result}" != "0" ]]; then  # Unequal integer parts
         echo -n ${result}
      else # Compare the decimal parts right-padded with zeros to same length
         maxlength=${#decpart1}
         if [ ${maxlength} -lt ${#decpart2} ]; then
            maxlength=${#decpart2}
         fi
         decpart1="$(rightPad ${decpart1} ${maxlength})"
         decpart2="$(rightPad ${decpart2} ${maxlength})"
         echo -n $(compare ${decpart1} ${decpart2})
      fi
   fi
}

# Compare two strings from the command-line
echo "numcmp = $(numcmp "$1" "$2")"
Sample results:
Code:
$ ./numcomp.sh 5 6
numcmp = -1
$ ./numcomp.sh 5 5.
numcmp = 0
$ ./numcomp.sh 005 5.00000
numcmp = 0
$ ./numcomp.sh 000010000000.000001000 000010000000.000002000
numcmp = -1
$ ./numcomp.sh 0.05 .005
numcmp = 1
$ ./numcomp.sh 3.14159 2.71828
numcmp = 1
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #8  
Old 20th November 2013, 11:40 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in Scheme, using the Guile interpreter (yum install guile).

Save this as numcomp.scm:
Code:
(define (adot s)
   (if (not (string-contains s ".")) (string-append s ".") s))
(define (getintpart s)
   (if (> (string-length (car (string-split s #\.))) 0) (car (string-split s #\.)) "0"))
(define (getdecpart s)
   (if (> (string-length (cadr (string-split s #\.))) 0) (cadr (string-split s #\.)) "0"))
(define (getlengths s1 s2)
   (list (max (string-length (getintpart s1)) (string-length (getintpart s2)))
         (max (string-length (getdecpart s1)) (string-length (getdecpart s2)))))
(define (normalize s lens)
   (string-append (string-pad (getintpart s) (car lens) #\0)
                  (string-pad-right (getdecpart s) (cadr lens) #\0)))
(define (numcmp s1 s2)
   (if (string>? (normalize s1 (getlengths s1 s2)) (normalize s2 (getlengths s1 s2))) 1
       (if (string<? (normalize s1 (getlengths s1 s2)) (normalize s2 (getlengths s1 s2))) -1 0)))
(define (main args)
   (display (numcmp (adot (string-trim (cadr args) #\0)) (adot (string-trim (caddr args) #\0))))
   (newline))
Run it like this:
Code:
guile --no-auto-compile -e main -s numcomp.scm string1 string2
Sample results:
Code:
$ guile --no-auto-compile -e main -s numcomp.scm 5 6
-1
$ guile --no-auto-compile -e main -s numcomp.scm 5 4.
1
$ guile --no-auto-compile -e main -s numcomp.scm 00050 14.0
1
$ guile --no-auto-compile -e main -s numcomp.scm .05 0.005
1
$ guile --no-auto-compile -e main -s numcomp.scm .005 0.00500
0
$ guile --no-auto-compile -e main -s numcomp.scm 0 .00001
-1
I tried to make this as Scheme-ish as possible (i.e. functional style). But I'm sure there has to be a way using Haskell or some other functional language that's even shorter. I bet Jamwa will come up with a 5-line Erlang example.
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #9  
Old 21st November 2013, 01:12 AM
lsatenstein Offline
Registered User
 
Join Date: Jun 2005
Location: Montreal, Que, Canada
Posts: 4,013
linuxfirefox
Re: Programming Challenge: Comparing Numbers in a String

Quote:
Originally Posted by Flounder View Post
You are right it should be equal. This has been turning out to be a harder problem than I thought.

I have been reworking the solution to use only one variable besides the two passed in and this is what I have now.

Code:
#include <stdio.h>                                                                                                                                                                  
                                                                                                                                                                                    
int numcmp(const char *s1, const char *s2);                                                                                                                                         
                                                                                                                                                                                    
int numcmp(const char *s1, const char *s2)                                                                                                                                          
{                                                                                                                                                                                   
    int retval = 0;                                                                                                                                                                 
                                                                                                                                                                                    
/* Advance past all leading zeros */
    while (*s1 == '0')
        s1++;
    while (*s2 == '0')
        s2++;

/* Compare first difference and advance through the integer
 * portion of the string
 */
    while (*s1 >= '0' && *s1 <= '9' && *s2 >= '0' && *s2 <= '9') {
        if (retval == 0 && *s1 < *s2)
            retval = -1;
        else if (retval == 0 && *s1 > *s2)
            retval = 1;

        ++s1;
        ++s2;
    }

/* compare to see if one string is really longer
 * than the other
 */

    if (*s1 == '.' && *s2 != '\0' && *s2 != '.')
        return -1;
    else if (*s1 != '.' && *s1 != '\0' && *s2 == '.')
        return 1;
    else if (*s1 == '.' && *s2 == '.' && retval != 0)
        return retval;
    else if (*s1 != '.' && *s1 != '\0' && *s2 == '\0')
        return 1;
    else if (*s2 != '.' && *s2 != '\0' && *s1 == '\0')
        return -1;

/* check digits for any difference in both strings */

    while (*s1 != '\0' && *s2 != '\0') {
        if (*s1 < *s2)
            return -1;
        else if (*s1 > *s2)
            return 1;

        ++s1;
        ++s2;
    }

/* check remaining strings to see if one is greater than
   the other past the decimal point */

    while (*s1 != '\0') {
        if (*s1 > '0')
            return 1;
        ++s1;
    }

    while (*s2 != '\0') {
        if (*s2 > '0')
            return -1;
        ++s2;
    }

    return retval;
}

int main()
{
    printf("%d\n", numcmp("5", "5") == 0);
    printf("%d\n", numcmp("5.", "5") == 0);
    printf("%d\n", numcmp("0015", "15") == 0);
    printf("%d\n", numcmp("0.005", ".005") == 0);
    printf("%d\n", numcmp("5", "3") == 1);
    printf("%d\n", numcmp("5", "0.3") == 1);
    printf("%d\n", numcmp("0.05", "0.005") == 1);
    printf("%d\n", numcmp("0000100000000000000000.00000000000000000000000000001","0000100000000000000000.00000000000000000000000000002") == -1);
    printf("%d\n", numcmp("5", "6") == -1);
    printf("%d\n", numcmp("5", "55") == -1);
    printf("%d\n", numcmp("5", "40") == -1);
    printf("%d\n", numcmp(".00001", "10000.") == -1);
    printf("%d\n", numcmp("100000.00000", "200000.00000") == -1);

    return 0;
}
Its wonderful to make arbitrary strings with leading zeros and ones. However, the atof() function is a fast and reasonable way to achive what you want.
float1= atof(s1);
float2j= atof(s2);
if(floatf1 > float2) return 1;
if (floatf2 > floatf1) return -1;
return (0);

The way I would do it without atof() and with moderate efficiency is
a) scan off leading zeros from s1, s2.
scan s1 to the point or end of string. remember where you stopped.
scan s2 to the point or end of string. remember where you stopped.
if the length of one s1 scan is more than the s2 scan, you are finished, as the longer one is larger.
if the scans are equal in length, compare byte for byte. again, you can check which is greater.
if they are equal to the where the scan stopped, then
you loop back on your function, starting with the first digits after the dots.

Consider
let s1 = 2350.
let s2 = 2350.00

the s1 scan length is 4, the s2 scan length is 4 and byte by byte comparisons show equal.
starting after the decmal point, or assumed point, the problem is simplified.
you are searching for nulls, or for the first non zero character.
the rest is just a few compares. within a second while loop.
__________________
Leslie in Montreal

Interesting web sites list
http://forums.fedoraforum.org/showth...40#post1697840
Reply With Quote
  #10  
Old 21st November 2013, 01:50 AM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxfirefox
Re: Programming Challenge: Comparing Numbers in a String

lsatenstein the only problem with using atof() or getting a count of the number of digits is it defies the problem:

Quote:
There is no limit on the number of digits in the input strings. The implementation should not impose a restriction on the length of the strings.
Do not use any library functions (including the standard libraries) in your implementation.
To give context to the requirement my teacher (he taught me Hebrew by the way as I am not a CS student) came up with this problem when he was dealing with comparing stock prices. Hence the no limit to the amount of digits. Then he figured it would make for a good problem to use when hiring.
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC
Reply With Quote
  #11  
Old 22nd November 2013, 02:28 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in Octave.

Save this script as numcmp.m:
Code:
#!/usr/bin/octave -qf
function mat = getparts(s)
   mat = strsplit(s, '.');
   if (length(mat) == 1 || length(mat{2}) == 0)
      mat{2} = '0';
   elseif length(mat{1}) == 0
      mat{1} = '0';
   end
end

function str = normalize(m, len)
   str = strcat(repmat('0', 1, len(1)-length(m{1})), m{1}, m{2}, repmat('0', 1, len(2)-length(m{2})));
end

function ret = numcmp(s1, s2)
   m1 = getparts(s1);
   m2 = getparts(s2);
   lens = max([length(m1{1}), length(m1{2})], [length(m2{1}), length(m2{2})]);
   ret  = 0;
   for c = [ normalize(m1, lens) ; normalize(m2, lens) ]
      if c(1) > c(2)
         ret = 1;
         break
      elseif c(1) < c(2)
         ret = -1;
         break
      end
   end
end

fprintf('numcmp = %d\n', numcmp(argv(){1}, argv(){2}))
Sample results:
Code:
$ ./numcmp.m 69 42
numcmp = 1
$ ./numcmp.m 5. 5
numcmp = 0
$ ./numcmp.m 0.05 .005
numcmp = 1
$ ./numcmp.m 00000000100000000.0000000000030000 00000000100000000.0000000000040000
numcmp = -1
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #12  
Old 22nd November 2013, 10:35 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in Tcl.

Save this script as numcmp.tcl:
Code:
#!/usr/bin/tclsh
proc getparts {s} {
   set parts [split $s "."]
   if {[llength $parts] == 1 } {
      set parts [lappend parts "0"]
   } elseif {[string length [lindex $parts 1]] == 0} {
      lset parts 1 "0"
   } elseif {[string length [lindex $parts 0]] == 0} {
      lset parts 0 "0"
   }
   return $parts
}

proc normalize {parts lens} {
   set str [string repeat "0" [expr [lindex $lens 0] - [string length [lindex $parts 0]]]]
   append str [join $parts ""]
   append str [string repeat "0" [expr [lindex $lens 1] - [string length [lindex $parts 1]]]]
   return $str
}

proc numcmp {s1 s2} {
   set p1 [getparts $s1]
   set p2 [getparts $s2]
   lappend lens [expr max([string length [lindex $p1 0]], [string length [lindex $p2 0]])]
   lappend lens [expr max([string length [lindex $p1 1]], [string length [lindex $p2 1]])]
   return [string compare [normalize $p1 $lens] [normalize $p2 $lens]]
}

puts "numcmp = [numcmp [lindex $argv 0] [lindex $argv 1]]"
Run it like this:
Code:
./numcmp.tcl num1 num2
Sample results:
Code:
$ ./numcmp.tcl 0011 10.
numcmp = 1
$ ./numcmp.tcl 0.05 .005
numcmp = 1
$ ./numcmp.tcl 00000000012 000000000123.1000000000000
numcmp = -1
$ ./numcmp.tcl 42 0042
numcmp = 0
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #13  
Old 22nd November 2013, 10:53 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in Lua.

Save this script as numcmp.lua:
Code:
#!/usr/bin/lua
function getparts(s)
   local mat = {}
   if s:find(".", 1, true) == nil then
      mat[1] = s
      mat[2] = "0"
   else
      for p1, p2 in s:gmatch("(%d*)%.(%d*)") do
         if #p1 > 0 then mat[1] = p1 else mat[1] = "0" end
         if #p2 > 0 then mat[2] = p2 else mat[2] = "0" end
      end
   end
   return mat
end

function normalize(m, len1, len2)
   return string.rep("0", len1-#m[1])..m[1]..m[2]..string.rep("0", len2-#m[2])
end

function numcmp(s1, s2)
   local m1 = getparts(s1)
   local m2 = getparts(s2)
   local len1 = math.max(#m1[1], #m2[1])
   local len2 = math.max(#m1[2], #m2[2])
   local n1 = normalize(m1, len1, len2)
   local n2 = normalize(m2, len1, len2)
   if n1 > n2 then return 1 elseif n1 < n2 then return -1 else return 0 end
end

print(string.format("numcmp = %d", numcmp(arg[1], arg[2])))
Run it like this:
Code:
./numcmp.lua num1 num2
Sample results:
Code:
$ ./numcmp.lua 2 3
numcmp = -1
$ ./numcmp.lua 2 1.
numcmp = 1
$ ./numcmp.lua 00000000000000000000000000002 2.
numcmp = 0
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #14  
Old 22nd November 2013, 11:25 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in JavaScript (yum install v8).

Save this as numcmp.js:
Code:
String.prototype.repeat = function(n) {
   return new Array(1 + n).join(this);
}

function getparts(s) {
   var mat = s.split(".");
   if (mat.length == 1) {
      mat[1] = "0";
   } else if (mat[0].length == 0) {
      mat[0] = "0";
   } else if (mat[1].length == 0) {
      mat[1] = "0";
   }
   return mat;
}

function normalize(m, len1, len2) {
   return "0".repeat(len1 - m[0].length) + m[0] + m[1] + "0".repeat(len2 - m[1].length);
}

function numcmp(s1, s2) {
   var m1 = getparts(s1);
   var m2 = getparts(s2);
   var len1 = Math.max(m1[0].length, m2[0].length);
   var len2 = Math.max(m1[1].length, m2[1].length);
   var n1 = normalize(m1, len1, len2);
   var n2 = normalize(m2, len1, len2);
   if (n1 > n2) {
      return 1;
   } else if (n1 < n2) {
      return -1;
   } else {
      return 0;
   }
}

print("numcmp = " + numcmp(arguments[0], arguments[1]));
Run it like this:
Code:
d8 numcmp.js -- num1 num2
Sample results:
Code:
$ d8 numcmp.js -- 1 2.
numcmp = -1
$ d8 numcmp.js -- 10 0010
numcmp = 0
d8 numcmp.js -- 000022200.000000001 .999
numcmp = 1
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #15  
Old 23rd November 2013, 01:42 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,556
linuxfedorafirefox
Re: Programming Challenge: Comparing Numbers in a String

Here's an example in Awk.

Save this as numcmp.awk:
Code:
#!/usr/bin/gawk
function rep(str, n,    i, s) {
   for (i = 0; i < n; i++) s = s str   
   return s
}

function getparts(s, m,    n) {
   n = split(s, m, ".")
   if (n == 1) m[2] = "0"; else if (length(m[1]) == 0) m[1] = "0";
   else if (length(m[2]) == 0) m[2] = "0"
}

function normalize(m, len1, len2) {
   return rep("0", len1 - length(m[1])) m[1] m[2] rep("0", len2 - length(m[2]))
}

function numcmp(s1, s2,    len1, len2, n1, n2) {
   getparts(s1, m1)
   getparts(s2, m2)
   len1 = (length(m1[1]) > length(m2[1]) ? length(m1[1]) : length(m2[1]))
   len2 = (length(m1[2]) > length(m2[2]) ? length(m1[2]) : length(m2[2]))
   n1 = normalize(m1, len1, len2)
   n2 = normalize(m2, len1, len2)
   if (n1 > n2) return 1; else if (n1 < n2) return -1; else return 0
}

BEGIN {
   print "numcmp =", numcmp(s1, s2)
}
Run it like this:
Code:
awk -v s1="first_number" -v s2="second_number" -f numcmp.awk
Sample results:
Code:
$ awk -v s1="0010" -v s2="10." -f numcmp.awk
numcmp = 0
$ awk -v s1=".010" -v s2="00110" -f numcmp.awk
numcmp = -1
$ awk -v s1="0000000000000001.5000" -v s2="1.414" -f numcmp.awk
numcmp = 1
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
Reply

Tags
challenge, comparing, numbers, programming, string

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Programming challenge: Create a GUI window RupertPupkin Programming & Packaging 133 20th February 2017 08:20 AM
Programming challenge: Query a database RupertPupkin Programming & Packaging 196 23rd March 2016 04:18 AM
Programming challenge: Approximate an area RupertPupkin Programming & Packaging 211 10th August 2015 12:40 AM
Programming challenge: Listen on a socket RupertPupkin Programming & Packaging 34 12th November 2013 03:22 AM
Programming challenge: Create a chart RupertPupkin Programming & Packaging 28 18th September 2013 12:14 AM


Current GMT-time: 05:26 (Tuesday, 27-06-2017)

TopSubscribe to XML RSS for all Threads in all ForumsFedoraForumDotOrg Archive
logo

All trademarks, and forum posts in this site are property of their respective owner(s).
FedoraForum.org is privately owned and is not directly sponsored by the Fedora Project or Red Hat, Inc.

Privacy Policy | Term of Use | Posting Guidelines | Archive | Contact Us | Founding Members

Powered by vBulletin® Copyright ©2000 - 2012, vBulletin Solutions, Inc.

FedoraForum is Powered by RedHat