# (Im)possible Algorithm

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 03-28-2004
Cikotic
(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.

• 03-28-2004
Thantos
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; }```
• 03-28-2004
Dave_Sinkula
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" */```
• 03-28-2004
Sebastiani
>> 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).
• 03-29-2004
HybridM
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?
• 03-29-2004
major_blagger
Was it a book for C or for some functional programming language?

I guess it all depends on the scope of your restrictions.
• 03-29-2004
Sebastiani
>> if(temp1 == temp2)

Nope, the implementation uses loops internally, so that won't work either. Try again.
• 03-29-2004
The Dog
From what I read, the function should test to see if in one string, all the characters are the same. eg. "ssssss", "11111", "eeeee"
• 03-29-2004
chrismiceli
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.
• 03-29-2004
Prelude
>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.
• 03-29-2004
VirtualAce
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.
• 03-29-2004
Salem
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.
• 03-29-2004
Dave_Sinkula
The hideous version dancing through my head is simply the unrolled loop. :p
• 03-29-2004
Sebastiani
>> 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.
• 03-29-2004
-KEN-
Posting because I want to see Salem's horrendous solution.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last