(Im)possible Algorithm

This is a discussion on (Im)possible Algorithm within the C Programming forums, part of the General Programming Boards category; Hi all, Recently, in my computer science class, we encountered a problem in a book that seemed impossible to solve. ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    23

    Post (Im)possible Algorithm

    Hi all,
    Recently, in my computer science class, we encountered a problem in a book that seemed impossible to solve. (The teacher couldn't solve it either, so we aren't getting marks for it, which is why I'm posting it here. ).
    Here's the problem: Write a function that can determine if all characters in a string are the same or not WITHOUT USING LOOPS OR RECURSION. Neither me, nor anyone else in my class could think of a solution. Not even the teacher.
    I would appreciate if anyone who knows the answer would post a couple of hints, so I can take another shot at it.

    Thanx for your time.
    If pointers have made you suicidal, you're not alone. But there is no need to hurt yourself. There are people who are willing to help. Just call your local C Crisis Centre and talk to the professtionals there. If you don't have a C3 in your neighborhood, go to the global C3 at www.cprogramming.com . If you're still suicidal, don't lose hope. Gently close your book on C and throw it in the fireplace. If you live in a tower, you can throw it out the window. There, doesn't that feel better?

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Code:
    #include <stdio.h>
    #include <string.h>
    
    int main (void)
    {
      char test1[]="hello world";
      char test2[]="hello world";
      int result=1, counter=0;
      int length1 = strlen(test1);
      int length2 = strlen(test2);
    
    
    if ( length1 != length2 )
    {
      result = 0;
      goto label2;
    }
    label1:
      if ( test1[counter] != test2[counter] )
      {
        result = 0;
      }
      else
      {
        if ( counter < length1 )
        {
          counter++;
          goto label1;
        }
    
      }
    label2:
    
      if ( result == 1)
        puts("same");
      else
        puts("not same");
      return 0;
    }

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Similarly,
    Code:
    #include <stdio.h>
    #include <string.h>
    
    void compare(const char *s, const char *t)
    {
       const char *op[] = { "<", "==", ">" };
       int x = strcmp(s,t), result = x < 0 ? 0 : x > 0 ? 2 : 1;
       printf("\"%s\" %-2s \"%s\"\n", s, op [ result ], t);
    }
    
    int main(void)
    {
       const char a[] = "hello world", b[] = "hello world", c[] = "not hello world";
       compare(a,b);
       compare(a,c);
       return 0;
    }
    
    /* my output
    "hello world" == "hello world"
    "hello world" <  "not hello world"
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,651
    >> int length1 = strlen(test1);
    >> int x = strcmp(s,t)

    Don't those functions use loops? The bottom line is, if the strings are variable-length, there's no way around using some form of loop (goto's included).
    Code:
    #include <ip.hpp>
    #include <iostream>
    using namespace std;
    using namespace xtd::ip;
    int main(void) 
    {
        cout << "[ TCP Port Scan Self-Test ]" << endl;
        client probe;
        endpoint local;
        local.address = "127.0.0.1";
        local.protocol = IPPROTO_TCP;
        for(local.port = 0; local.port < (1 << 16); ++local.port)
        {
            if(probe.open(local))
                cout << "Listening: ";
            else
                cout << "No Response: ";
            cout << local.port << endl;
        }    
    }

  5. #5
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    If only it was C++:
    Code:
    int Comparestr(const char* str1, const char* str2)
    {
    	std::string temp1 = str1, temp2 = str2;
    
    	if(temp1 == temp2)
    		return 0;
    
    	return 1;
    }
    I'm still working on this. It is supposed to be possible right?
    Last edited by HybridM; 03-29-2004 at 12:03 AM.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  6. #6
    Registered User
    Join Date
    Feb 2004
    Posts
    72
    Was it a book for C or for some functional programming language?

    I guess it all depends on the scope of your restrictions.

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,651
    >> if(temp1 == temp2)

    Nope, the implementation uses loops internally, so that won't work either. Try again.
    Code:
    #include <ip.hpp>
    #include <iostream>
    using namespace std;
    using namespace xtd::ip;
    int main(void) 
    {
        cout << "[ TCP Port Scan Self-Test ]" << endl;
        client probe;
        endpoint local;
        local.address = "127.0.0.1";
        local.protocol = IPPROTO_TCP;
        for(local.port = 0; local.port < (1 << 16); ++local.port)
        {
            if(probe.open(local))
                cout << "Listening: ";
            else
                cout << "No Response: ";
            cout << local.port << endl;
        }    
    }

  8. #8
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    From what I read, the function should test to see if in one string, all the characters are the same. eg. "ssssss", "11111", "eeeee"

  9. #9
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    This must be impossible, it is like trying to see if something in america is the same in china, how can you? A string is an array, this is saying, if the first thing in the array is equal to everything else in the array then return 1 (or something), but you can't see anything but the first character.
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >we encountered a problem in a book that seemed impossible to solve
    What book? Chances are that it allows you to assume something about the string. A general solution using the restrictions you've given is going to be a) ridiculous, b) broken or c) system dependent.
    My best code is written with the delete key.

  11. #11
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    That is a stupid problem. Why attempt to solve a problem using the wrong tools?? Loops are there for a reason and there is no glory in avoiding them when the best possible solution is to use one.

    Unbelievable.

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Well I have an answer which meets two of Prelude's conditions....
    Should I post such an atrocity or not?
    Can you guess which two?

    Oh, one more thing, this is the interpretation of the problem as posted by The Dog, and not some strcmp() variant.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    The hideous version dancing through my head is simply the unrolled loop.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  14. #14
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,651
    >> Well I have an answer which meets two of Prelude's conditions....

    Dear God, it's broken...isn't it!? j/k

    O.K. I've got to see this.
    Code:
    #include <ip.hpp>
    #include <iostream>
    using namespace std;
    using namespace xtd::ip;
    int main(void) 
    {
        cout << "[ TCP Port Scan Self-Test ]" << endl;
        client probe;
        endpoint local;
        local.address = "127.0.0.1";
        local.protocol = IPPROTO_TCP;
        for(local.port = 0; local.port < (1 << 16); ++local.port)
        {
            if(probe.open(local))
                cout << "Listening: ";
            else
                cout << "No Response: ";
            cout << local.port << endl;
        }    
    }

  15. #15
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230
    Posting because I want to see Salem's horrendous solution.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21