(Im)possible Algorithm

This is a discussion on (Im)possible Algorithm within the C Programming forums, part of the General Programming Boards category; Heh, I've just "improved" it by also removing all == as well as all loops I wonder how many know ...

  1. #16
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    Heh, I've just "improved" it by also removing all == as well as all loops
    I wonder how many know how to compare for equality without using == ?
    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.

  2. #17
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    subtract the two values and if the result is 0 they are equal. Hello asm class

  3. #18
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    In glorious non-technicolor, howsabouthisthen

    Code:
    #include <stdio.h>
    
    #define C1(a,i)   ( !a[i] || ( !(a[i]^a[i+1]) && ++i ) )
    #define C5(a,i)   ( C1(a,i) || C1(a,i) || C1(a,i) || C1(a,i) || C1(a,i) )
    #define C25(a,i)  ( C5(a,i) || C5(a,i) || C5(a,i) || C5(a,i) || C5(a,i) )
    #define C(a,i)    ( C25(a,i) )
    
    int main()
    {
        int     i;
        char    t1[] = "SsSs1234";
        char    t2[] = "ssssssssss";
    
        i=0;printf("All chars in %s are %sequal\n", t1, C(t1,i) ? "" : "NOT " );
        i=0;printf("All chars in %s are %sequal\n", t2, C(t2,i) ? "" : "NOT " );
        return 0;
    }
    Spot the clever use of the "%sequal" format specifier (short for string equal) to do the actual work
    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.

  4. #19
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Neat Jimmy!

    But I can't find the %sequal modifier in my manual
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #20
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >In glorious non-technicolor, howsabouthisthen
    It's quite beautiful in a Lon Chaney, Phantom of the Opera, hideously deformed but still brilliant underneath, way. That was close to what I was thinking of, along with the unrolled loop nasty.

    >But I can't find the %sequal modifier in my manual
    It's an undocumented modifier. Manuals don't show you the most powerful features.
    My best code is written with the delete key.

  6. #21
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    Yeah, the %sequal one of the more powerful modifiers, but keep it secret or it loses its power
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  7. #22
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Salem
    In glorious non-technicolor, howsabouthisthen

    Code:
    #include <stdio.h>
    
    #define C1(a,i)   ( !a[i] || ( !(a[i]^a[i+1]) && ++i ) )
    #define C5(a,i)   ( C1(a,i) || C1(a,i) || C1(a,i) || C1(a,i) || C1(a,i) )
    #define C25(a,i)  ( C5(a,i) || C5(a,i) || C5(a,i) || C5(a,i) || C5(a,i) )
    #define C(a,i)    ( C25(a,i) )
    
    int main()
    {
        int     i;
        char    t1[] = "SsSs1234";
        char    t2[] = "ssssssssss";
    
        i=0;printf("All chars in %s are %sequal\n", t1, C(t1,i) ? "" : "NOT " );
        i=0;printf("All chars in %s are %sequal\n", t2, C(t2,i) ? "" : "NOT " );
        return 0;
    }
    Spot the clever use of the "%sequal" format specifier (short for string equal) to do the actual work


    But run it with:
    Code:
        char    t1[] = "SsSs1234";
        char    t2[] = "ssXsssss";
    I got this output:
    All chars in SsSs1234 are NOT equal
    All chars in ssXsssss are equal


    Dave

  8. #23
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    Bleh!!!!
    Does this make it better?
    Code:
    #define C5(a,i)   ( C1(a,i) && C1(a,i) && C1(a,i) && C1(a,i) && C1(a,i) )
    #define C25(a,i)  ( C5(a,i) && C5(a,i) && C5(a,i) && C5(a,i) && C5(a,i) )
    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.

  9. #24
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    So I was right, it is broken?

    Try:

    #define C1(a,i) ( (!a[i] || !a[i+1]) || ( !(a[i]^a[i+1]) && ++i ) )
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #25
    Registered User
    Join Date
    Mar 2004
    Posts
    23
    Thanx for all your responses. Sorry, I didn't check in earlier.
    The programme was supposed to check if all characters in one string are the same, which I think, Salem's programme solved. Today, in class, we thought that if we get the first char of a string, and then concat it to the end of the string and drop the first one, it'd work:
    "abbb" get the value of 'a'
    concat a to the end of string (allocating enough space)
    "abbba", then drop the first char
    "bbba", then compare the strings. (we are allowed to used string functions provided).

    It's gonna take me a while before I can figure out Salem's solution, but it seems very interesting.

    Thanx for all your helps.
    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?

  11. #26
    Even death may die... Dante Shamest's Avatar
    Join Date
    Apr 2003
    Location
    Malaysia
    Posts
    970
    Would it be cheating if I simply used a goto?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    bool allSame( char* str )  {
      int  i = 0;
      char prev = str[i++] ;
      label:
        if ( str[i] && prev == str[i++] ) 
          goto label;
    
      return str[i] == 0;
    }
    
    int main(int argc, char *argv[])
    {
      char    t1[] = "ssSs1234";
      char    t2[] = "ssssssssss";
      
      printf("All chars in %s are %sequal\n", t1, allSame(t1) ? "" : "NOT " );
      printf("All chars in %s are %sequal\n", t2, allSame(t2) ? "" : "NOT " );
         
      getchar();
      return 0;
    }

  12. #27
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Would it be cheating if I simply used a goto?
    It depends on whether you see a goto loop as a real loop. I see it as a conditional repetition of a block of code, so goto would break the rules as that is pretty much the definition of a loop.
    My best code is written with the delete key.

  13. #28
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    Prelude...All that work to figure out what your sig says. I hate you beat this

    01010000011100100110010101101100011101010110010001 100101
    01100010011001010110000101110100011101000110100001 10100101110011

    0x48,0x65,0x78, 0x72, 0x6f, 0x63, 0x6b, 0x73, 0x62,0x6a, 0x6e, 0x73,
    0x73, 0x6f, 0x63, 0x6b, 0x73

    Just really bored actually

  14. #29
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >beat this
    What? No spaces? Slacker.
    My best code is written with the delete key.

Page 2 of 2 FirstFirst 12
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