21
\$\begingroup\$

I asked random.org for 128 random integers between 0 and 232 - 1. Since the random number generator was so eager to give the first 64 numbers first, they're obviously more random than the other 64.

Write a full program or function that returns a truthy result when one of the following 64 integers is input:

[1386551069, 1721125688, 871749537, 3410748801, 2935589455, 1885865030, 776296760, 614705581, 3841106923, 434616334, 1891651756, 1128215653, 256582433, 310780133, 3971028567, 2349690078, 489992769, 493183796, 3073937100, 3968540100, 777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391, 3676486536, 3852572850, 3498953201, 2544525180, 297297258, 3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 742719206, 2409129909, 3008020402, 328113612, 1081997633, 1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 732377595, 431649729, 2105108903, 1454214821, 997975981, 1764756211, 2921737100, 754705833, 1823274447, 450215579, 976175934, 1991260870, 710069849]

And a falsey result for the other 64 numbers:

[28051484, 408224582, 1157838297, 3470985950, 1310525292, 2739928315, 3565721638, 3568607641, 3857889210, 682782262, 2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 2017874229, 3935199786, 1136100076, 2406566087, 496970764, 2945538435, 2830207175, 4028712507, 2557754740, 572724662, 2854602512, 736902285, 3612716287, 2528051536, 3801506272, 164986382, 1757334153, 979200654, 1377646057, 1003603763, 4217274922, 3804763169, 2502416106, 698611315, 3586620445, 2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 1519642783, 924263219, 3506109843, 2916121049, 4060307069, 1470129930, 4014068841, 1755190161, 311339709, 473039620, 2530217749, 1297591604, 3269125607, 2834128510]

Any input other than one of these 128 numbers is undefined behavior.

If your solution is found programmatically, please also share the code used to generate it!

This is , so the shortest solution in bytes wins.

\$\endgroup\$
9
  • 21
    \$\begingroup\$ Since the random number generator gave the first 64 numbers first, they must be more random ಠ___ಠ \$\endgroup\$
    – Luis Mendo
    Mar 5 '16 at 16:30
  • \$\begingroup\$ You can distinguish the two sets modulo 834 \$\endgroup\$ Mar 5 '16 at 17:33
  • 1
    \$\begingroup\$ Those numbers are not random. \$\endgroup\$ Mar 5 '16 at 18:37
  • \$\begingroup\$ "Maybe, not enough information."& 33 bytes, answers the question. \$\endgroup\$ Mar 5 '16 at 19:10
  • 3
    \$\begingroup\$ @CatsAreFluffy Actually, as long as the input doesn't contain 0 or 1 and no two elements differ by 1, you can separate them by a modulo chain. e.g. separating [4 20 79] from [8 18 100] can be done by [99 79 20 17 7 4] (see if you can spot the pattern). Sure, the initial half of your answer might use a much smaller modulo than the input, but the back half consists of shifting one element at a time. \$\endgroup\$
    – Sp3000
    Mar 5 '16 at 20:22
12
\$\begingroup\$

CJam, 53 52 47 bytes

l~"X    0'ò"2/Dfb+:%"gÇâì6Ô¡÷Ç8nèS¡a"312b2b=

There's unprintables, but the two strings can be obtained by

[88 9 48 5 39 5 29 1 242]:c
[8 103 199 226 236 54 212 15 161 247 199 56 110 232 83 161 97]:c

respectively. This also shows that the code points are below 256.

This is a modulo chain answer, where we apply the following modulos to the input integer, in order:

[1153 629 512 378 242 136]

Since this list contains integers greater than 255, the list is encoded using two chars each. The decoding is done by 2/Dfb, which splits the string into chunks of length two and converts each from a base 13 number (e.g. 88*13 + 9 = 1153). However, there are two exceptions to the decoding:

  • The last number (136) is not included (see below),
  • The second-last number is represented by a single char, since the number (242) is less than 256 and splitting an odd-length array into chunks of size 2 will leave a size 1 array at the end. Thanks to @MartinBüttner for this tip!

Once the modulos have reduced the input integer to a relatively small number, we perform a lookup from a table. This table is encoded via the second string, which is converted to a base 312 number then decoded to base 2, which we index. Since CJam's array indexing wraps, we can leave out the final modulo as mentioned earlier.

Try it online | Test suite

\$\endgroup\$
5
  • 1
    \$\begingroup\$ How do you people come up with the magic moduli? \$\endgroup\$ Mar 5 '16 at 17:56
  • \$\begingroup\$ @CatsAreFluffy Just a simple DFS with a limit on the number of modulos. My current implementation is quite slow, so if I feel like the program's stuck for a while I try a different initial starting point. \$\endgroup\$
    – Sp3000
    Mar 5 '16 at 18:02
  • \$\begingroup\$ What's a DFS? (Wikipedia doesn't help.) \$\endgroup\$ Mar 5 '16 at 18:13
  • \$\begingroup\$ @CatsAreFluffy Depth-first search \$\endgroup\$
    – Sp3000
    Mar 5 '16 at 18:14
  • \$\begingroup\$ Ah. I just used a greedy algorithm. \$\endgroup\$ Mar 5 '16 at 18:18
5
\$\begingroup\$

Retina, 117 bytes

([023]3|[067]0|[1289]1|5[5689]|67|96|88|77|65|05)$|^(8|4[358]|7[147]|51|37|30)|865|349|2.{5}5|761|74[348]|728|811|990

A regex golf answer, outputting a positive integer for truthy and zero for falsy.

Try it online! | Test suite - truthy | Test suite - falsy | Regex101

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6) 233

An anonymous function returning 0 as falsy and nonzero as truthy

x=>~"lnhp2wm8x6m9vbjmrqqew9v192jc3ynu4krpg9t3hhx930gu8u9n1w51ol509djycdyh077fd1fnrzv6008ipkh0704161jayscm0l6p4ymj9acbv5ozhjzxo3j1t20j9beam30yptco033c9s3a8jwnre63r29sfbvc5371ulvyrwyqx3kfokbu66mpy9eh" // newline added for readability
.search((x.toString(36)).slice(-3))

Checking the last 3 digits in the number representation in base 36.

The check string is built so:

a=[1386551069, 1721125688, ... ]
H=x=>(x.toString(36)).slice(-3)
Q=a.map(x=>H(x)).join('')

Test

f=x=>~"lnhp2wm8x6m9vbjmrqqew9v192jc3ynu4krpg9t3hhx930gu8u9n1w51ol509djycdyh077fd1fnrzv6008ipkh0704161jayscm0l6p4ymj9acbv5ozhjzxo3j1t20j9beam30yptco033c9s3a8jwnre63r29sfbvc5371ulvyrwyqx3kfokbu66mpy9eh"
.search((x.toString(36)).slice(-3))

a=[1386551069, 1721125688, 871749537, 3410748801, 2935589455, 1885865030, 776296760, 614705581, 3841106923, 434616334, 1891651756, 1128215653, 256582433, 310780133, 3971028567, 2349690078, 489992769, 493183796, 3073937100, 3968540100, 777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391, 3676486536, 3852572850, 3498953201, 2544525180, 297297258, 3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 742719206, 2409129909, 3008020402, 328113612, 1081997633, 1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 732377595, 431649729, 2105108903, 1454214821, 997975981, 1764756211, 2921737100, 754705833, 1823274447, 450215579, 976175934, 1991260870, 710069849]
b=[28051484, 408224582, 1157838297, 3470985950, 1310525292, 2739928315, 3565721638, 3568607641, 3857889210, 682782262, 2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 2017874229, 3935199786, 1136100076, 2406566087, 496970764, 2945538435, 2830207175, 4028712507, 2557754740, 572724662, 2854602512, 736902285, 3612716287, 2528051536, 3801506272, 164986382, 1757334153, 979200654, 1377646057, 1003603763, 4217274922, 3804763169, 2502416106, 698611315, 3586620445, 2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 1519642783, 924263219, 3506109843, 2916121049, 4060307069, 1470129930, 4014068841, 1755190161, 311339709, 473039620, 2530217749, 1297591604, 3269125607, 2834128510]

A.textContent=a.map(x=>f(x))
B.textContent=b.map(x=>f(x))
<table>
  <tr><th>first 64 - truthy</th></tr><tr><td id=A></td></tr>
  <tr><th>other 64 - falsy</th></tr><tr><td id=B></td></tr>
</table>  

\$\endgroup\$
3
\$\begingroup\$

Jelly, 30 bytes

ȷ;€ȷḥ€⁸ḋ“¡`Ṿc-MrKṪZiṣ$Ṅ(ṀQ’B¤Ḃ

Try it online!

This answer was almost entirely automatically generated, using this automated encoder (which I wrote myself, and have previously used in another challenge); here's where the original algorithm (which I created myself) comes from. Because Jelly isn't so great at interprocess communication, the encoder generates a Sage program that generates a Jelly program that prints the final golfed program.

There were three manual tweaks to the automated result: two were golfing uses of base-generic builtins that dealt with base 2 into the (shorter) versions that are specific to binary, and one was to change the program from a full program into a function (so that I could easily test it on every test case – the byte count is the same either way, you just need to change the way it takes input from (function argument) into, e.g., ³ (command-line argument)).

The generator has a couple of deficiencies that mean that it randomly fails sometimes; for a (and therefore only two outputs), this chance is much higher than normal (hard to estimate exactly, but likely above 50%). Fortunately, it randomly happened to work first time 🙂

Explanation

ȷ;€ȷḥ€⁸ḋ“¡`Ṿc-MrKṪZiṣ$Ṅ(ṀQ’B¤Ḃ
 ;                              Form a pair of
  €                               each number from 1 to
ȷ                                   1000
   ȷ                              and 1000
     €                          and use each pair as
    ḥ                             a hash configuration, to hash
      ⁸                             this function's argument.
       ḋ                        Take the dot product {of the list of hashes}
                            ¤     and a constant determined by
                           B        taking the list of binary digits of
        “¡`Ṿc-MrKṪZiṣ$Ṅ(ṀQ’           [a magic constant]
                             Ḃ  {Output} its least significant bit.

As usual, the algorithm is to pass the inputs we're given through a list of hash functions to create a list of hashes (the list created this way is longer than it needs to be, to save bytes specifying how long it needs to be), then take the dot product of the list of hashes and a magic constant calculated by the program I linked above.

The reason this works is that each input/output pair that we need to set effectively corresponds to a requirement on the parity of the number of set bits in certain positions in the magic constant, e.g. the requirement that 1386551069 maps to 1 means that out of the bit positions in the magic constant that correspond to hash functions that hash 1386551069 to an odd number, an odd number of them need to be a 1 bit in order for the program to give the correct output in that case. This sort of requirement can be expressed as a linear equation in the finite field GF(2), making it possible to calculate what the magic constant should be simply via writing down all the equations (which is what the first stage of the generator program does) and solving them (which is what the Sage program that it outputs does). There might not be a solution, of course, but given an entirely randomly chosen set of simultaneous equations (i.e. each variable has a random coefficient in every equation), if the number of equations is no greater than the number of variables, the odds that they turn out to be solvable are actually pretty high, and they were here.

I did end up with a bit of luck converting the resulting equations to Jelly – the first bit of the list that needs to be encoded in the magic constant happens to be a 1, so it's possible to compress it by base-converting it into a number (which couldn't be done if it had a leading zero, as the leading zero would then be missing upon base-converting back). This is only a problem because Jelly base conversions are big-endian (extra trailing zeroes past the last useful hash function wouldn't have an effect), so wouldn't affect a golfing language that had this generic algorithm available as a builtin. Fortunately, this particular set of inputs and outputs managed to dodge the issue (and it's a deficiency with the decompressor that sits around the magic constant, rather than the technique for finding the magic constant itself).

As a side note, the magic constant is 17 bytes long (not 16, the theoretical minimum for 128 input → output pairs) because not all of the 256 bytes of the Jelly codepage are able to appear in a compressed literal – 6 of them are quotes (which can't appear unescaped because they'd be interpreted as ending the string, and there isn't an escape syntax), so only 250 of them are actually available, and that makes string literals a little longer than they would be in base 256.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 218 217 bytes

Fold[Mod,#,{834,551,418,266,228,216,215,209,205,199,198,195,178,171,166,162,154,151,146,144,139,137,122,120,117,114,110,106,101,98,95,88,84,67,63,61,60,57,55,51,45,44,43,41,40,35,34,30,27,26,25,23,20,14,13,11,10,9}]<1

For whatever reason, a set of moduli exists that allows us to distinguish two sets just by whether or not, after applying the moduli, the result is zero or not. The long list of moduli was generated by this program:

Block[{data1, data2, n, mods}, 
 data1 = {1386551069, 1721125688, 871749537, 3410748801, 2935589455, 
   1885865030, 776296760, 614705581, 3841106923, 434616334, 
   1891651756, 1128215653, 256582433, 310780133, 3971028567, 
   2349690078, 489992769, 493183796, 3073937100, 3968540100, 
   777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391,
    3676486536, 3852572850, 3498953201, 2544525180, 297297258, 
   3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 
   2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 
   742719206, 2409129909, 3008020402, 328113612, 1081997633, 
   1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 
   732377595, 431649729, 2105108903, 1454214821, 997975981, 
   1764756211, 2921737100, 754705833, 1823274447, 450215579, 
   976175934, 1991260870, 710069849};
 data2 = {28051484, 408224582, 1157838297, 3470985950, 1310525292, 
   2739928315, 3565721638, 3568607641, 3857889210, 682782262, 
   2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 
   2017874229, 3935199786, 1136100076, 2406566087, 496970764, 
   2945538435, 2830207175, 4028712507, 2557754740, 572724662, 
   2854602512, 736902285, 3612716287, 2528051536, 3801506272, 
   164986382, 1757334153, 979200654, 1377646057, 1003603763, 
   4217274922, 3804763169, 2502416106, 698611315, 3586620445, 
   2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 
   1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 
   1519642783, 924263219, 3506109843, 2916121049, 4060307069, 
   1470129930, 4014068841, 1755190161, 311339709, 473039620, 
   2530217749, 1297591604, 3269125607, 2834128510};
 n = 1;
 mods = {};
 While[Intersection[Mod[data1, n], Mod[data2, n]] != {}, n++];
 FixedPoint[
  (mods = Append[mods, n]; data1 = Mod[data1, n]; 
    data2 = Mod[data2, n]; n = 1;
    While[Intersection[Mod[data1, n], Mod[data2, n]] != {}, n++]; 
    n) &
  , n];
 {mods, {Fold[Mod, data1, mods], Fold[Mod, data2, mods]}}
 ]

First output is the moduli, second and third outputs are the two lists, having applied the moduli. The two long lists are the sets.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can probably compress a part of the list into a string. \$\endgroup\$ Mar 6 '16 at 1:25
2
\$\begingroup\$

PowerShell, v3+ 194 bytes

$args[0]%834%653-in(40..45+4,8,12,51,60,64,69,76,84,86,93,97,103,117+137..149+160,162,178+195..209+215..227+255,263+300..329+354,361,386,398,417,443,444+469..506+516,519,535,565,581,586,606,618)

A little bit of a different approach, so I figured I would post it. It's not going to win shortest, but it may give someone else ideas to shorten their code.

We're still taking the input integer $args[0] and applying modulo operations to it, so nothing different there. In the above, we're using the -in operator (hence v3+ requirement) so this will output True for values that are in the truthy test case.

However, I'm attempting to find resultant arrays where we can leverage the .. range function to shorten the byte count, yet still have distinct arrays between the truthy and falsey values. We can do this since behavior other than the truthy/falsey input is undefined, so if the range catches values outside of the truthy/falsey input, it doesn't matter the output.

It's a pretty manual process so far, as the goal is to try and find the modulo where one of truthy or falsey arrays has large gap(s) between numbers and the other array has large amounts of numbers in that gap. I've mostly been going by intuition and gut feel so far, but I may eventually write a brute-forcer to solve this. The above is the shortest I've (mostly manually) found so far.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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