7
\$\begingroup\$

I have a non-challenge, bitwise-gymnastics question that I am looking for a home for. Would this be on topic here?

Per some requirements, I am trying to pack three data points into 16-bits for the fourth position of an Assembly's Version (in .NET, the fourth position of a version number cannot exceed UInt16.MaxValue-1 ). In our build system we are trying to codify three data points into this value every time a CI build is initiated:

  • Year
  • Day of Year
  • Build Revision (resets daily, starts at 1)

The criteria are:

  • Values are unique
  • Values are reversible back to their original components
  • For Year=M, Day=N+1 produces a final result greater than Day=N
  • And by extension, all values for Year=M+1 are greater than all Year=M
    • or rather, Year=M+1, Day=1 is greater than Year=M, Day=366

(The last two points basically saying that the value between any two consecutive days is strictly increasing)

The best I've come up with is to store that as:

  • 2 bits for the number of years since 2019 (ie 2019=0)
  • 9 bits for the day of the year
  • 5 bits for the revision number

So basically: (Years << 14) | (Day << 5) | Revision

My solution works, but for various reasons I'm trying to find a way to extend the range of supportable revision numbers. I feel like I can somehow borrow some of the leftovers from the day-of-year (since I have 512-366=146 unused values) but I can't seem to find a way to make that work such that it meets my criteria and that I'd be able to reverse it.

Question:

Is it possible through some bitwise tricks to extend the supported range for the revision (and if so, how)? Or have I reached the limits of a 16-bit number?

Meta-Question:

Is this on-topic? After reading the site rules, I'm guessing no, unless it can fall into the non-challenge category. I'm not sure if this would even be on topic over on SO, but even if it were I feel like I'd get much better solutions here (assuming there even are any). Is this "puzzly enough" or should I try my luck elsewhere?

\$\endgroup\$
  • 4
    \$\begingroup\$ If you allow arbitrarily complicated and long-running compression and decompression algorithms, it's surely possible to pack optimally as long as there's at most 2^16 valid options, even with the monotonicity restriction. So, for this to be an interesting challenge and maybe reflect the goals of bit packing, I think you'd need to either make the challenge code golf to reward short solutions, or impose some sort of complexity or run-time bound or scoring function. I think this has potential as a challenge. You'd definitely need to specify the range of valid data points though. \$\endgroup\$ – xnor Aug 16 at 11:11
  • \$\begingroup\$ If you need an extra bit for rev number, the simplest solution I can see is combining days and years: allocate 10 bits for "days since 2019-01-01" (allowing for 5y, 220d (after taking into account 2 leap years)), which leaves a 6th bit for rev number. \$\endgroup\$ – GammaFunction Aug 18 at 12:20
  • \$\begingroup\$ @GammaFunction I though of that, but that takes 11bits, not 10... or is my math way off? \$\endgroup\$ – pinkfloydx33 Aug 18 at 12:28
  • \$\begingroup\$ @pinkfloydx33 Your math is right, I was wrong... The highest unsigned value in 10 bits is 2^10 - 1. By some wolframalpha searches, it would roll over on 2021-10-21. This gives you close to 3 years of 64 builds per day. and uses all your bits. So you would have to give up some of those builds for more days, or give up some of those days for more builds, or just assign all 16 bits to the build revision. Finding an algorithm which fits between 32 builds and 64 builds and that sorts could be interesting. \$\endgroup\$ – GammaFunction Aug 18 at 12:48
  • \$\begingroup\$ If you have 14 bits for day and revision number, you have 1<<14 = 16384 possibilities. Dividing by 366 gives 44.7 (call it 44 !) possibilities for the revision number. So you can pack into 14 bits as day*44 + revision But personally I would pack into 14 bits as revision * 366 + day. Because you know you need 366 possibilities for the day, but you don't know how many revisions you need. If you end up with less than 22, you can use the unused bit to extend the year field in future (4 years sounds very short to me.) Decoding is by integer division and modulo. \$\endgroup\$ – Level River St Aug 27 at 1:05
8
\$\begingroup\$

Every challenge requires objective winning criteria. You would need to prepare a set of those before presenting your challenge to us. If you choose to make your challenge a pure code golf, since "should theoretically work for any input" doesn't work here, you'll need to specify the set of possible inputs. If you want to us to maximize the number of years (making code length (technically) a secondary criterion), you'll need to fix the number of revisions and vice versa.

Language-specific challenges are discouraged. While language restrictions aren't expressly forbidden, arbitrary restrictions tend to be unwelcome. There have been some quite successful challenges posted in the past, but their language restrictions have been justified in each case. That doesn't seem to be the case for your question.

If you want to restrict the set of possible operations, you may find it prohibitively difficult to define the list of things one cannot do as languages - and golfing languages in particular - are surprisingly diverse. Defining a whitelist - and even basing your scoring criteria on it - is quite doable though. As before, make sure the restriction improves the challenge. Something that's trivial in a normal language can be tricky with just bitwise operations.

Do note that solutions to code golf challenges will always be ... golfed. Copy-pasting them into your production codebase will result in your place's code reviewers' displeasure. And even if you merely hope to extract the respective algorithm from us, even that might, even with non-golfing languages, prove to be difficult.

Do make sure to get some eyeballs on your challenge before posting it here. Post it in the sandbox and if that doesn't bring it enough attention, the chat may be able to help. Both to nail down the specification and to make sure your challenge is interesting and not a duplicate.

Regarding your specific question - if you just fix the ranges for each input, the optimal solution will be just a bit of arithmetic. If you ban arithmetic, people will simulate arithmetic with bitwise operations. If you drop the monotonicity requirement and only ask for a bit packing algorithm with the fewest number of gates, people will note that 356 ~= 3*128 making the challenge quite a bit easier than on the surface (in a way that splitting day of year into day + month doesn't help with). Now, if you fix the ranges in a way that prevents that simplifications, that might suffice to create an interesting challenge. The chat should be able to help you choose the constraints.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .