11
\$\begingroup\$

I am trying to golf down some C++. Is it possible to make this condition shorter?

X > 3 & X - Y > 1

(Apart from removing whitespace, of course.)

So, X is at least 4 but X >= Y + 2.

X and Y are integers in the [0,5] interval.

I have tried to find some bitwise formula but failed.

\$\endgroup\$
25
  • 1
    \$\begingroup\$ @JoeZ. For CodeGolf? Why? As long as it is working... \$\endgroup\$
    – Cristy
    Commented May 3, 2014 at 18:22
  • 4
    \$\begingroup\$ @Cristy yes they are, but (so far) questions asking about golfing advice are very rare whereas most questions asking for advice are indeed just general programming questions - which are off-topic. Hence, I can understand why the first reaction of people might be, "oh that's another question that actually belongs on SO", without even thinking it could be about golfing advice. I'd actually like to see more of these in the future, and maybe there'll be a tag for them some day or so, and it will be clear immediately that you know how to use this site. ;) \$\endgroup\$ Commented May 3, 2014 at 20:23
  • 4
    \$\begingroup\$ If they are integers between 0..5 inclusive, you can do the same thing with x*x-y*y>9. It's the same amount of characters, but you may be able to find a shortcut/alternative to that approach. Just another way of looking at it. \$\endgroup\$
    – Geobits
    Commented May 8, 2014 at 18:43
  • 5
    \$\begingroup\$ Use Python: 3<x>y+1 \$\endgroup\$
    – avall
    Commented May 9, 2014 at 22:32
  • 2
    \$\begingroup\$ I found a lot of solutions with Python's operator precedence, e.g. y+3<2^x, but C's operator precedence is different. I'm betting there's a 7-char solution, just have to modify my script to deal with C operator precedence instead \$\endgroup\$
    – Claudiu
    Commented Sep 15, 2014 at 1:17

2 Answers 2

11
\$\begingroup\$

After brute forcing every useful combination of symbols under 9 characters, I've found there to be no smaller solution than x>3&x-y>1.

For fun here's some funky 9 character solutions the brute forcer found:

-x<~y>4>x
~y+x>2>>y
x*x-y*y>9
~y>x/~3*x
-3>>y>y-x
~y+x<<y>2

Brute forcing was done in Python, building top-down syntax trees where no child may have an operator with precedence lower than its parent according to C's rules. To cut down on possibilities I only allowed single digit literals, and no binary operator may have two constant children. I could not possibly think of any solution that would have a two digit literal, or one that builds a constant using a binary operator. Then each expression was evaluated for [0, 5] and if it matches it gets printed.

\$\endgroup\$
7
  • \$\begingroup\$ I really like x*x-y*y>9. Perhaps you should try multi-digit constants as well? (also, parentheses) \$\endgroup\$ Commented Mar 11, 2015 at 9:21
  • \$\begingroup\$ @JanDvorak me too. It expresses well the logic of "distance between x and y". I think if you plot this in a chart, it would become more obvious. \$\endgroup\$
    – sehe
    Commented Mar 11, 2015 at 9:26
  • \$\begingroup\$ @JanDvorak I don't think parentheses can ever be a smaller solution. A smaller solution can be a max of 8 characters, of which 2 must be xy, and 2 must be the parentheses, leaving only 4 characters of logic. I'll try running the brute forcer with 2 digit constants, but I really don't think it'll give a result. \$\endgroup\$
    – orlp
    Commented Mar 11, 2015 at 9:27
  • \$\begingroup\$ How about, x, y, a constant, a pair of parentheses and two operators? \$\endgroup\$ Commented Mar 11, 2015 at 9:29
  • \$\begingroup\$ @JanDvorak Knock yourself out, (a#b)$c is the format. Out of abc two must be x and y, leaving 3 possible locations for [0-9xy], and only one flip of xy. Only interesting operators are +-*/&|^<>, so 9 possibilities. Thus total possibilities is less than 3*12*2*9*9 < 5832. \$\endgroup\$
    – orlp
    Commented Mar 11, 2015 at 9:42
0
\$\begingroup\$

In response to the (awesome) golfs by orlp:

Correctness must come first

  • Most of these break down for some integer types. This includes the version from the OP
  • Interestingly they do work for int16_t - so there is the assumption. Probably the bit shifts would need to +16 for 32 bit ints (that's pretty much everywhere these days). This makes them a character bigger...

The only "correct" way to write it, IMO is (x>3) && (x > y+1), which may be golfed down to x>3&x>y+1 (9 characters).

(You really need to take the possibility of (larger) unsigned types into consideration, especially since unsigned-ness is "contagious" in C++ expressions. I suppose "fixing" that with the appropriate static_cast<>s would kinda defeat the purpose...)

UPDATE

With the following tests I've been able to figure out which expressions actually work reliably:

Live On Coliru

#define REPORT(caption, expr) do {\
    do_report(caption, [](T x, T y) -> bool { return (expr); }, #expr); } while (false)

template <typename T> struct driver {
    static void run() {
        std::cout << "\n" << __PRETTY_FUNCTION__ << "\n";

        // the only two correct implementations:
        REPORT("MASTER"  , (x>3) && (x>y+1));
        REPORT("GOLF"    , x>3&x>y+1);
        REPORT("lookup"  , "000000000000000000000000111000111100"[x*6+y]-'0');

        // failing sometimes:
        REPORT("question", (x>3)&(x-y>1));
        REPORT("orlp0"   , x>3&x-y>1);
        REPORT("orlp2"   , ~y+x>2>>y);
        REPORT("orlp3"   , x*x-y*y>9);
        REPORT("orlp4"   , ~y>x/~3*x);
        REPORT("orlp5"   , -3>>y>y-x);
        REPORT("orlp6"   , ~y+x<<y>2);

        // failing always
        REPORT("orlp1"   , -x<~y>4>x);
    }
private:
    static void do_report(std::string const& caption, bool (*f)(T,T), char const* expression) {
        std::string r;
        for (T x = 0; x < 6; ++x) for (T y = 0; y < 6; ++y) r += f(x, y)?'1':'0';
        bool const correct = "000000000000000000000000111000111100" == r;
        std::cout << (correct?"OK\t":"ERR\t") << r << "\t" << caption << "\t" << expression << "\n";
    }
};

int main() {
    driver<int8_t>::run();
    driver<int16_t>::run();
    driver<int32_t>::run();
    driver<int64_t>::run();

    driver<uint8_t>::run();
    driver<uint16_t>::run();
    driver<uint32_t>::run();
    driver<uint64_t>::run();
}

Output on coliru, here for reference:

static void driver<T>::run() [with T = signed char]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = short int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = long int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = unsigned char]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = short unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
ERR 000000000000000000000000111001111100    question    (x>3)&(x-y>1)
ERR 000000000000000000000000111001111100    orlp0   x>3&x-y>1
ERR 111111011111001111000111111011111101    orlp2   ~y+x>2>>y
ERR 011111001111000111000011111001111100    orlp3   x*x-y*y>9
ERR 111111111111111111111111111111111111    orlp4   ~y>x/~3*x
ERR 111111011111001111000111111011111101    orlp5   -3>>y>y-x
ERR 111111011111001111000111111011111101    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = long unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
ERR 000000000000000000000000111001111100    question    (x>3)&(x-y>1)
ERR 000000000000000000000000111001111100    orlp0   x>3&x-y>1
ERR 111111011111001111000111111011111101    orlp2   ~y+x>2>>y
ERR 011111001111000111000011111001111100    orlp3   x*x-y*y>9
ERR 111111111111111111111111111111111111    orlp4   ~y>x/~3*x
ERR 111111011111001111000111111011111101    orlp5   -3>>y>y-x
ERR 111111011111001111000111111011111101    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

Summary

Since this about the "cost" of repeating source code elements, you might use a lookup table. You can "hide" the lookup table, so it is either

 LUT[x][y]

or

 LUT[x*6+y]

Of course you can be pedantic and obtuse and rename the LUT

 L[x][y]

So my "version" is ... 7 characters. (Or make if a function and L(x,y) is even shorter).

Or, more importantly: correct, testable and maintainable.

\$\endgroup\$
1
  • \$\begingroup\$ Added a "true" golf. No shorter than 9 characters, but the first one to be correct! \$\endgroup\$
    – sehe
    Commented Mar 11, 2015 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.