9
\$\begingroup\$

Taking an interest in the challenge presented in this recent Code Review question, I've concocted a C solution (valid as C++, if I'm not mistaken) seeking to reduce both the lines of code and the running time of the program. It's a delightful challenge with no apparent value except for its being a hill to climb.

The code below has a firm "ceiling" of a maximum of 16 pairs. As there appear to be 120 million combinations using only 11 pairs, and the progression appears to be roughly 7* as many combinations for each increment in the count of pairs, I'm content to only have flown as high as 11 pairs.

With my outdated compiler and computer, some uint32_t variables remain. I suspect more advanced hardware could use uint64_t variables without loss of performance.

Admittedly terse variable names, and "conjoined" statements, have been used to make the code as compact as possible.

  • w.o is a "bit buffer" that is populated with flags and shifted. It 'tracks', in two 16 bit 'registers', recent "open" brackets, and is used to prevent appending an inappropriate "close" bracket where such would be disallowed.
  • w.no merely ensures that the number of "opens" never exceeds 1/2 of the buffer. "Pairs" implies a buffer with matching "open" and "close" characters.
  • w.rem starts with twice the number of pairs to be generated, and counts down to zero indicating the buffer has been filled (ready for counting and possibly output or verification).
  • Each level of recursion (to append one more character) has its own working buffer that is reloaded on each of 4 iterations as characters are 'proposed' by the for().
  • Characters are represented by 2 bits (4 bits to make a pair), thus the ceiling of 64/4=16 "pairs" using a uint64_t to store the assembled representations of strings.
  • For (optional) output or verification, the 2bit representations are 'decoded' into ASCII characters and printed or merely compared against predecessors to ensure ascending sequence.

Welcome is any commentary on the code, and, in particular, the algorithm and its implementation. (Although, the comment, "more appropriate on Code Golf site" is assumed and therefore unnecessary.)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

static const uint32_t N = 3; // number of pairs to gen for this run

/*
N =  5, count =      1344, Elapsed:  0.000 seconds
N =  6, count =      8448, Elapsed:  0.005 seconds
N =  7, count =     54912, Elapsed:  0.020 seconds
N =  8, count =    366080, Elapsed:  0.150 seconds
N =  9, count =   2489344, Elapsed:  1.035 seconds
N = 10, count =  17199104, Elapsed:  7.275 seconds
N = 11, count = 120393728, Elapsed: 48.182 seconds
*/

static const uint32_t MAXPAIRS = 2 * 16; // up to 16 pairs
static uint32_t cnt; // count of well-formed strings gen'd

typedef struct { uint64_t s; uint32_t n, rem, o, no; } prm;

#define MODE 1 // 0:just gen & count, 1:output strings, 2:verify seqnc
#  if MODE == 0
#   define XXX
#elif MODE == 1
#   define XXX \
        /* output string using "<>[]" vs "()[]" for clarity */ \
        char buf[ MAXPAIRS + 1 ] = {0}, *c = buf + MAXPAIRS; \
        for( w.n <<= 1; w.n--; w.s >>= 2 ) *(--c) = "<>[]"[ w.s & 0x3 ]; \
        printf( "%9d %s\n", cnt, c );
#elif MODE == 2
#   define XXX \
        /* verify "lexicographic order" */ \
        static char prev[ MAXPAIRS + 1 ] = {0}; \
        char buf[ MAXPAIRS + 1 ] = {0}, *c = buf + MAXPAIRS; \
        for( w.n <<= 1; w.n--; w.s >>= 2 ) *(--c) = "<>[]"[ w.s & 0x3 ]; \
        if( strcmp( prev, c ) < 0 ) strcpy( prev, c ); \
        else fprintf( stderr, "Failed on %s not LT %s\n", c, prev ), exit( 0 );
#endif

static void gen( prm *p ) {
    static const uint32_t oX = 0x00000001, oY = 0x00010000;

    for( uint64_t i = 0; i < 4; i++ ) {
        prm w = *p; // reload for this iteration
        if( (  (i & 1) && !(w.o & ((i==1)?oX:oY)) )  // closing X or Y not allowed
        ||  ( !(i & 1) && ++w.no > w.n ) ) continue; // max 50% can be open
        w.o = (i & 1) // is a close (odd)
            ? (w.o & ~oY) >> 1                  // cancel this open
            : (w.o << 1) | ( (i==0)?oX:oY );    // record this open
        w.s |= i << (--w.rem*2);    // good. record 2 bit character
        if( !w.rem ) { cnt++; XXX; return; } // base case
        gen( &w );  // recurse
    }
}

int main( void ) {
    prm p = { 0, N, N+N };

    clock_t tic = clock();
    gen( &p );
    clock_t toc = clock();

    printf( "N = %d", N );
    printf( ", count = %9d", cnt );
    printf( ", Elapsed: %6.3f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC );

    return 0;
}

EDIT:

The response from @J_H has pointed out the absence of any explanation of w.s.

Responding to this, for the sake of future readers, with NO intention to invalidate that welcome response:

  • w.s is the 64 bit 'string' (or 'symbol') buffer into which are assembled the up to 32x2 bit representation of one "well formed" collection of symbols. (32 single characters maximum for 16 "pairs" of brackets maximum.)

My thanks to @J_H for pointing out the absence of this explanation in my question.

\$\endgroup\$
12
  • 4
    \$\begingroup\$ Hey @FerricOxide, C and C++ are nice, from any other contributor. But, ummm, isn't it obligatory that you do it in rust 🦀 ? i64! \$\endgroup\$
    – J_H
    Commented Jun 15 at 23:45
  • 2
    \$\begingroup\$ @J_H I'll start to use Rust when the court case is settled (in my favour) and they start paying me those (backdated) licensing fees for naming their language after me... :-D \$\endgroup\$
    – Fe2O3
    Commented Jun 16 at 1:13
  • \$\begingroup\$ Well, all I can say is "UB". When C compilers stop making daemons fly out my nose, then I'll consider C a serious competitor to Rust. \$\endgroup\$
    – J_H
    Commented Jun 16 at 1:14
  • 1
    \$\begingroup\$ @Fe2O3 Filling in balanced pairs within delimiters isn’t what I had in mind. I go into more detail here, although my description of how to generate all strings that begin with a given prefix is still a bit hand-wavey. \$\endgroup\$
    – Davislor
    Commented Jun 16 at 8:21
  • 1
    \$\begingroup\$ Whenever the algorithm generates a ), it wants to recurse, and generate all valid sequences with the same preceding characters and a [ in place of the ), then backtrack to where it left off. With the data structures I suggested (where we first memo-ize every balanced string of { and } as an array of the positions of each opening brace), that would finding the subrange of memo-ized solutions whose first several opening braces are in the right places, and generating only the bit patterns to determine whether each pair is () or [] whose higher-order bits match the prefix. \$\endgroup\$
    – Davislor
    Commented Jun 16 at 8:37

3 Answers 3

5
\$\begingroup\$

size of test

static const uint32_t N = 3; // number of pairs to gen for this run

/*
N =  5, count = ...

Thank you kindly for those beautiful timing figures, I found them very helpful.

Maybe default to N of 8 or 9? Given that 8 is still compatible with a sub-second interactive edit-compile-debug cycle? I'm just thinking that it is more interesting, as it exercises more states.

I found the Review Context very helpful. Consider pushing some of it into source code comments so it doesn't get lost. For example the "up to 16 pairs" comment could be more explicit about "bit pairs".

The descriptions of o, no, rem similarly belong in the source. And I confess I have no idea what s denotes, nor why we're willing to devote 64 bits to it, and to it alone.

meaningful identifier

#   define XXX

Yeah... That's not a name!

Thank you for the {0, 1, 2} rundown, very helpful. But we're looking for a verb, and XXX isn't one. ("Three hard things in CS...." Sorry, I don't know the right name. As the Author, that's on you.)

My essential difficulty is that you abdicated on the whole DbC thing. I don't know what promises you're signed up for, so I can't tell if XXX is "correct" under the rules you're defining. The helpful comments ("output", "verify") give me a clue. But they're not enough.

Also, please tell me the mental pronunciation for prm. Maybe it's a TLA? No idea what it might denote. "Parenthesis recursive mumble"?

summary

Cryptic identifiers aside, I feel there's a lot of magic in the OP code, such as i looping up to 3 in gen(), or the {x, y} relationship. Compact representation is fine, but document it, and exercise it with a test suite. I am looking for variants and invariants, and am not finding them explicitly called out. The more explicit you are, the more easily collaborators will be able to reason about this code.

\$\endgroup\$
3
  • \$\begingroup\$ All good and constructive criticisms and observations! Thank you. ("prm" is my personal TLA for "parameters", the container of current values to be used... Point taken!) And "XXX" was simply me being lazy. I had thought of "MODEFUNC", or something similar, but, again, just laziness... Much appreciation for your time and commentary! :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 16 at 1:45
  • 1
    \$\begingroup\$ Well, the first one is easy then! Just go with param. // In a slightly related vein, it's pretty interesting to do "foreign language" reviews, or "pseudo foreign language" where at least some of the idenfitiers are trying to be English identifiers. Because there's always abbrev's, and in a foreign language they are really hard to guess. Which helps me to see the difficulties I am posing for ESL engineers tasked with trying to read my source code. And marking wordboundaries is a big help. \$\endgroup\$
    – J_H
    Commented Jun 16 at 1:47
  • \$\begingroup\$ In particular, now that you've mentioned it, I've got it backwards. The "timings" block in mixed into the code, and the "doco" about some of the variables used is somewhere outside, lost in the text description... Good point! \$\endgroup\$
    – Fe2O3
    Commented Jun 16 at 1:47
5
\$\begingroup\$

A hard-earned "senior's moment" (lasting longer than a moment), and a micro-optimisation...


the "Doh!"

I usually don't pay attention to effects like actual "time trial" comparisons.
And, using an (older) IDE, instead of make, means I don't often dabble with the compile flags.

Duplicating some of the test results from earlier:

N =  9, count =   2489344, Elapsed:  1.035 seconds
N = 10, count =  17199104, Elapsed:  7.275 seconds
N = 11, count = 120393728, Elapsed: 48.182 seconds

And, now specifying speed optimisation for compilation (Doh!)

i =  9, count =   2489344, Elapsed:  0.922 seconds
i = 10, count =  17199104, Elapsed:  6.453 seconds
i = 11, count = 120393728, Elapsed: 45.859 seconds

Micro-optimisation

Times:

i =  9, count =   2489344, Elapsed:  0.906 seconds
i = 10, count =  17199104, Elapsed:  6.279 seconds
i = 11, count = 120393728, Elapsed: 44.862 seconds

The following lines of code replace their counterparts one-for-one in the code example of the question above. The revised times (on my hardware) are reported above.

    static const uint32_t oX[4] = { 0x00000001, 0x00000001, 0x00010000, 0x00010000 };

    for( uint64_t i = 0; i < 4; i++ ) {
        prm w = *p; // reload
        if( (  (i & 1) && !(w.o & oX[i]) // closing X or Y not allowed
        ||  ( !(i & 1) && ++w.no > w.n ) ) ) continue; // max 50% can be open
        // open flag -- i is odd ? cancel it : record it
        w.o = (i & 1) ? (w.o & ~oX[2]) >> 1 : (w.o << 1) | oX[i];

Using a few more bytes of memory, instead of some instructions, shaves another ~2% off the run time of the algorithm. Just something to note.

\$\endgroup\$
1
\$\begingroup\$

Been playing with this for a few minutes...

Using the same "boilerplate" code, here are some "substitution" lines (to replace their counterparts in the posted code above) to generate strings consisting of up to 10 pairs based on a palette of 4 pairs of matching characters: (), <>, [] and {}.

static const uint32_t MAXQUADS = 20; // max 10 pairs @ 3bits/each in 60 (64) bits
...
typedef struct { uint64_t s, o; uint32_t n, rem, no; } prm; // NB: o promoted!
...
#elif MODE == 1 // output string
#   define XXX \
        char buf[ MAXQUADS + 1 ] = {0}, *c = buf + MAXQUADS; \
        for( w.n <<= 1; w.n--; w.s >>= 3 ) *(--c) = "()<>[]{}"[ w.s & 0x7 ]; \
        ...
#elif MODE == 2 // verify "lexicographic order"
#   define XXX \
        static char prev[ MAXQUADS + 1 ] = {0}; \
        char buf[ MAXQUADS + 1 ] = {0}, *c = buf + MAXQUADS; \
        for( w.n <<= 1; w.n--; w.s >>= 3 ) *(--c) = "()<>[]{}"[ w.s & 0x7 ]; \
        ...
#endif

static void gen( prm *p ) {
    // L1 is a workaround for my old compiler. 1LL for modern 64bit notation
    // 8 + 1 constant 64bit flags to set/test/clear bits in w.o "open" tracker
    static const uint64_t L1 = 1, oX[] = {
        L1<< 0, L1<< 0,
        L1<<16, L1<<16,
        L1<<32, L1<<32,
        L1<<48, L1<<48,
    }, oXXXX = oX[0] | oX[2] | oX[4] | oX[6];

    for( uint64_t i = 0; i < 8; i++ ) {
        ...
        if( (i & 1) && !(w.o & oX[i]) // close does not match open
        || !(i & 1) && ++w.no > w.n ) continue; // max 50% can be open

        // open flag -- i is odd ? cancel it : record it
        w.o = (i & 1) ? (w.o & ~oXXXX) >> 1 : (w.o << 1) | oX[i];
        w.s |= i << (--w.rem*3);    // good. record 3 bit character
        ...
    }
}
...
    prm p = { 0, 0, N, N+N }; // in main(). notice 'N's shifted to right.

It's nice when code can be so easily adapted to serve a similar-but-different task. Most of these changes were simply amplifying 2 different brace/bracket pairs to 4 different brace/bracket pairs.

Note: to use only 3 pairs of characters, change the for() loop range to be 0-5 (instead of this 0-7), and manipulate the "decode" strings from 4 pairs down to only the 3 pairs desired. (Maintain ascending ASCII sequence of the pairs used, if that is important to the purpose.) Because the 'encoding' would still use 3 bits to represent each of 6 different characters, the maximum limit is the same 10 pairs (or 20 character long strings.)

\$\endgroup\$

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.