text:
The Return of FizzBuzz
Intro
Beauty lies in the eye of the beholder. Output lies in the choice of the compiler. There are some codes that give different outputs based on what language they are executed in. Take for instance, the code given below:
# include <stdio.h>
# define print(a) int main(){printf("C is better"); return 0;}
print("Python is better")

When executed in C, it prints "C is better". When using a python interpreter, it prints "Python is better".
Challenge
The challenge is a modification of the FizzBuzz challenge. Write a code that gives different outputs based on language it is executed in. When executed with the first language, it prints all numbers from 1 to 1000 (both inclusive) which are not divisible by 2. If a number is divisible by 2, it outputs "FizzBuzz". When executed with the second language, if a number is not divisible by 3, it is printed. Else, the string "FizzBuzz" is printed.
Example
Output when executed in language 1 would be
1 FizzBuzz 3 FizzBuzz 5 FizzBuzz 7 FizzBuzz 9 FizzBuzz ... (upto FizzBuzz 999 FizzBuzz)

Output when executed in language 2 would be
1 2 FizzBuzz 4 5 FizzBuzz 7 8 FizzBuzz 10 11 FizzBuzz 13 14 FizzBuzz ... (upto 998 FizzBuzz 1000)

Optional Challenge
You can optionally allow the program to execute in more than 2 languages. For the ith language, every multiple of (i+1) is substituted with FizzBuzz. It isn't necessary, but at least 2 languages are compulsory.
Constraints
Need to write a fully functioning code. For instance, a method/function/procedure alone (which could not independently execute) would not be acceptable
Can use only 1 file
All outputs to be printed to standard output (not to standard error)
All other standard rules of code-golf apply
EDIT: Fixed a loophole:
No taking of user inputs during execution
Edit I got a comment saying  the question wasn't clear if a non-empty separator is mandatory between the numbers. Assume it's not mandatory
Scoring
Total score = Number of bytes in the program.
Winning
Consider different participation brackets (based on number of languages being used). Person with least characters in each bracket can be considered a winner.

Beauty lies in the eye of the beer holder. But, without beer, those bonus points looks rather negative? As in < 0.

Golfing languages are esoteric languages, that are designed for golfing. How can you tell the difference?

My bad, I see now that the bonus points works as subtractions from the number of bytes.

@Λ̸̸ esoteric languages which were built specifically for golfing are golfing languages. The rest are esoteric

Can we output as a list in any of the used languages (i.e. [1, 2, "FizzBuzz", 4, 5, "FizzBuzz", ...])?

@KevinCruijssen Not sure. Haven't set any problems before this. What do you think?

@AbhayAravinda You should definitely allow that.

Ok then. It's allowed.

When you say compiling you are making assumptions about language features. Not all languages are compiled. You should probably remove any reference to compiling

The distinction between esoteric / golfing / language is unclear. How can we tell if a language is either of those categories? You should probably get rid of those categories, or else give a list or a way to tell the category of any language

Normally, options count as different languages. However, there is potential for abuse where a language exposes some options in a parameter. Using the $- parameter in Zsh, I found a 50 byte program with a score of -850 points (45 different option combinations). It's linked in my current Bash/Zsh answer. I think this could be allowed, except for the purpose of bonus, where it only counts as one language. The line between "implementation" and "version" is really fuzzy, so I'm not sure how to differentiate.

@LuisMendo I think I made it a bit more clear by making although the names may no longer be accurate

@GammaFunction I was completely unaware of this. Do you have any suggestions to fix this?

Apologies to all. When I wrote the question, I hadn't really calculated the loopholes and possible abuses. requesting those with privileges to feel free to edit the question to close the gaps

I'd suggest scrapping the bonus points - that way you don't have to worry about the (artificial) distinction between esoteric/golfing/normal languages. Also solves the problem pointed out by @GammaFunction.

@Dingus That might affect answers already posted

Also, you're free to choose whatever acceptance criterion you like, but I'd suggest reading How long should I wait before accepting an answer and Remove the Accept Feature if you haven't already.

@JoKing fixed it

It is not precised if a non-empty separator is mandatory between the numbers, in some languages having none would save bytes, is it allowed to have no separator?

@Kaddath fixed it

Would it be considered cheating to write an R answer that makes use of R.version to produce a very-high-n solution with all the different versions of R? (There may be similar exploits for other languages)

@JDL Relevant discussion on meta

Thanks @Dingus, though that discussion didn't seem to reach a conclusion other than perhaps to say "it's up to the OP" I guess I'll let the votes decide.

05AB1E / 05AB1E (legacy) / 2sable, 27 bytes
3°Lv®dтнOÌyDrÖi"FizzBuzz"},

2: Try it online in 2sable.
3: Try it online in 05AB1E.
4: Try it online in 05AB1E (legacy).
Explanation:
Let's start with a bit of history of these three languages. The development of 05AB1E started at the start of 2016 (or actually, the very first git-commit was on December 21st, 2015). This new codegolf language was being built in Python as backend. Mid 2016 2sable was branched of the 05AB1E version (July 7th, 2016 to be exact), and the strength of 2sable in comparison to that old 05AB1E version was added: implicit inputs. Later on implicit input was also added to 05AB1E, and 2sable was basically a forgotten version right after it was created on that day July 7th, 2016.
Then in mid-2018, a new 05AB1E version was being started, this time completely rewritten in Elixir instead of Python, with loads of new builtins added and some builtins changed or even removed.
So, let's go over the code and see what it does in each of the three languages:
3°                          # Push 10^3: 1000 (NOTE: I'm unable to use builtin `₄` for
                            # 1000, since it wasn't available in 2sable yet)
  Lv                        # Loop `y` in the range [1,1000] (NOTE: I'm unable to use
                            # builtin `E` for the [1,n] loop, since it wasn't available
                            # in 2sable nor the legacy version yet)
    ®                       #  Push -1
     d                      #  2sable: check if -1 only consist of digits (falsey / 0)
                            #  05AB1E (legacy): check if -1 is an integer (truthy / 1)
                            #  New 05AB1E: check if -1 is non-negative ≥0 (falsey / 0)
      т                     #  2sable: no-op, so does nothing
                            #  05AB1E (legacy) / new 05AB1E: push 100
       н                    #  Pop and push its first character
                            #   2sable: does this for the 0 of the `d` falsey result
                            #   05AB1E (legacy) / new 05AB1E: 100 → 1
        O                   #  Sum all values on the stack:
                            #   2sable: 0
                            #   05AB1E (legacy): 2 (1+1)
                            #   New 05AB1E: 1 (0+1)
         Ì                  #  Increase it by 2
                            #   2sable: 2
                            #   05AB1E (legacy): 4
                            #   New 05AB1E: 3
          yD                #  Push the loop value `y` two times
            r               #  Reverse the values on the stack
             Öi          }  #  If `y` is divisible by the value we calculated earlier:
               "FizzBuzz"   #   Push string "FizzBuzz"
                          , #  Pop and print the top value with trailing newline

Note: the O to sum the stack will also add the previous value that was divisible (since we've duplicated it with D, but only popped and printed "FizzBuzz"). But since we know it's divisible, the increased sum in that next iteration doesn't make a difference to the divisibility check.

you forgot to mention the score

@AbhayAravinda Added

Had to edit the question due to lot of ambiguity. Consider reading the new question. Apologies for inconvenience  caused.

@AbhayAravinda I've removed the score

Python 2/Python 3, 81 61 57 54 bytes
-20 with thanks to @KevinCruijssen
-4 with thanks to @dingledooper for the idea (prints from 1000 to 1)
-3 with thanks to @Ayxan by losing an unneeded int
x=1000
while x:print((x,'FizzBuzz')[x%(3/2*2)<1]);x-=1

Uses the differences of the / operator in Python 2 and 3. In Python 2 3/2 is 1 (integer division) while in Python 3 it is 1.5.
Try it online (Python 2)!
Try it online (Python 3)!
Python 2/Python 3, 81 bytes
import sys
print([(x,'FizzBuzz')[x%sys.version_info[0]<1]for x in range(1,1001)])

Try it online (Python 2)!
Try it online (Python 3)!
Although it is longer, I am keeping the original as I think it is pretty cool the way the version numbers tie in with the the requirement for 2nd and 3rd elements :-)

int(3/2*2) instead of sys.version_info[0] saves a couple of bytes.

@KevinCruijssen Thanks. I was messing about with the integer division idea then got caight up on a phone call!

Had to edit the question due to lot of ambiguity. Consider reading the new question. Apologies for inconvenience  caused.

No problem. I have removed the original bonus.

59 bytes if you print one on each line.

54 bytes

Fortran (GFortran)/Ruby, 80 79 75 bytes
print&!1.upto(1e3)do|i|puts i%3<1?"
*,(i,'FizzBuzz',i=1,999,2)!"[7,8]:i
end

Try it online! (Fortran), Try it online! (Ruby)
The Fortran compiler just sees
print&
*,(i,'FizzBuzz',i=1,999,2)
end

(! is the comment character in Fortran). The Ruby interpreter sees the full program, but we hide the otherwise invalid (Fortran) syntax at the start of the second line by wrapping it in a string.

Accepted  for being earliest answer.

"Accepted for being earliest answer." "First answer" ins't the winning criterion.  Since you've specified code-golf as the winning criterion, you should wait a at least a few days and accept the answer with the lowest score then.

@Jonah In winning, I think I clearly mentioned under early bird category that the earliest answer would be accepted.

Ok. Got rid of acceptance

Had to edit the question due to lot of ambiguity. Consider reading the new question. Apologies for inconvenience  caused.

@AbhayAravinda Thanks.  For more context, it's basically a logical problem.  1. You can only have one winning criteria.  There are no categories, because you can only accept one answer (unless you want to award bounties using your own reputation points).  2. Given that there can only be one winner, you have to choose between code golf and "first answer that meets these criteria".  Separate point: the latter is rarely done here because it's unfair.  Since there's no set start time, it's just a lottery for the people that happen to view your question first.

JavaScript/PHP 5.4+, 83 81 bytes
This was a somewhat simple, but fun challenge.
The code is really simple (outputs to the console in JavaScript and to stdout in PHP with -r):

for($i=0;$i<1e3;)[console.log,'printf'][+![]]("%s\n",++$i%(2+![])?$i:'FizzBuzz');

For JavaScript, outputs FizzBuzz on even numbers, while in PHP outputs in multiples of 3.

The code picks which function to call to output the value based on +![] (previously +!'0').
An empty array ([]) (previously was '0' - a string with 0) is a truthy value in JavaScript, but a falsy value in PHP.
An array is an object in JavaScript, and all objects are truthy in JavaScript.
Using this, one can do ![] to detect if the code is in JavaScript (false) or PHP (true).
Since Javascript would coerce false to a string, the + is needed to ensure it is a numeric value.
Using this same value, one can just do 2+![], resulting in 3 for PHP (2+!false = 2+true = 3) and 2 for JavaScript (2+!true = 2+false = 2).
That value is then used to check if it is a multiple.
The $i=0 is required because JavaScript will throw an Uncaught ReferenceError: $i is not defined.
The \n in the output can't be replaced because newlines are line terminators in JavaScript, causing a syntax error if replaced with an actual newline.
Without the \n, PHP would output "12FizzBuzz45FizzBuzz[...]".
JavaScript's console ignores it just fine.

+1 for picking two entirely different languages and not just relying on subtle differences between versions or implementations of the same language and for not abusing comments

@Philipp I think I will disappoint you :( JavaScript and PHP share a huge chunk of their syntax. Making polyglots with JavaScript and PHP is sorta easy. But thank you for the enthusiasm.

Perl 4, 54 48 bytes
for(;$i++<1e3;){print$i%(2+true)?$i:'FizzBuzz';}

Try it online!
PHP, 54 48 bytes
for(;$i++<1e3;){print$i%(2+true)?$i:'FizzBuzz';}

Try it online!
Simple: uses PHP's auto conversion from boolean true to integer 1 while PERL doesn't
EDIT: saved 3 bytes with a leading space separator instead of a trailing one
EDIT2: saved 6 bytes by removing the separator

+1 for picking two entirely different languages and not just relying on subtle differences between versions or implementations of the same language and for not abusing comments.

@Philipp Thanks, it seems that in the earliest stages of PHP creation, when Rasmus Lerdorf was creating his Personal Home Page and wasn't aware yet he was creating a language, he was coding in PERL. PHP source is written from C, but the syntax similiarities with PERL can be explained by that

Zsh +X/Bash, 58 bytes
for i in {1..1000};{ ((i%${#-}))&&echo $i||echo FizzBuzz;}

Try it online!
This uses the $- parameter, which holds some options used by the shell. By default, it is 569X in Zsh, and hB in Bash. Unsetting the -X option in Zsh results in a parameter of 569. Since ${#-} is the length of that parameter in both Bash and Zsh, we %2 in Bash and %3 in Zsh.

Zsh/Bash, 65 bytes
a=(2 3)
for i in {1..1000};{ ((i%a[1]))&&echo $i||echo FizzBuzz;}

Zsh: Try it online!
Bash: Try it online!
Zsh arrays are one-indexed, Bash arrays are zero-indexed. The surrounding { } in the loop are needed in Bash, not in Zsh.

Normally, options count as different languages. However, there is potential for abuse where the options are visible in a parameter. (Ab)Using the $- parameter in Zsh allows for a 50 byte program runnable in 45 "languages" (N = 2..46)

At first I thought you were abusing similarities (like I have done), but then I looked. +1

Had to edit the question due to lot of ambiguity. Consider reading the new question. Apologies for inconvenience  caused.

Perl 5, 60 54 bytes
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

Try it online!
PHP, 60 54 bytes
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

Try it online!
Perl 4, 60 54 bytes
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

Try it online!
Another answer, a bit longer with 3 languages!!!
still the same difference with true between PHP and PERL, but in PERL 5 and PHP ** takes precedence over the opposite operator -, while the contrary in PERL 4
EDIT: saved 6 bytes by removing the separator

R (various versions); 74,626 languages; 61 bytes
z=1:1000;z[z%%as.double(R.version$`svn rev`)==0]="fizzbuzz";z

This answer may be ruled to be illegal depending on whether different svn revisions count as different languages or not.
(Is there a more efficient way to convert text to numeric than as.double that will work with the oldest versions of R? I feel like there is, but I cannot remember it.)
This program will continue to work as long as R continues to release versions and the number of languages will increase. I ran this using R 3.5.0.
Haven't included 74,626 TIO links for obvious reasons. here is one for a recent version of R, but it is not very interesting as it is >1000 in the list, so there are no actual instances of fizzbuzz.

this deserves an equivalent of the IOCCC Abuse of the rules award! :)

I'd say that only the first 1000 versions of R would count then, since everything after that will produce identical results given the sample range.

just using $sv is shorter. strtoi might work instead of as.double?

I have a nagging feeling that $-completion wasn't in very early versions of R (was it in S-plus?). strtoi might have been around the whole time though — it's annoyingly hard to find documentation for ancient versions of R!

@Darrel there is no requirement that the outcome change, just that the solution is a valid program in the specified language(s). If the challenge had said 1 million instead of 1000, this solution would still work (with minor modifications)

Befunge-98 / Befunge-93, 55 bytes
1+:.:"}"8*-!#@_5j$1+:.1+" zzuBzziF",,,,,,,,,:"}"8*-!#@_

Try it in 98!
Try it in 93!
This is based on the introduction of jump in Befunge 98. By jumping in 98 the part 1+:. (add 1, duplicate, print) is only executed in Befunge 93.

C 89 (gcc)/C 99 (gcc) 64 bytes
i;main(){while(i++<1e3)printf(i%(2//**/
+1)?"%d":"FizzBuzz",i);}

Try online (C 89)
Try online (C 99)
Explanation:
You can find an explanation on how this works here.

The difference is that C99 recognizes // as the start of a comment, whereas C89 doesn't? Including an explanation makes the answer better!

@CrisLuengo Yes. I added a link to the explanation. Sorry, my first time.

Io/Erlang (escript), 134 bytes
Outputs a string as a list of codepoints in Erlang. Halts with an error in Io.
1%1+1000 repeat(i,if((i+1)%2<1,"FizzBuzz",i+1)println)
main(_)->io:write([if I rem 3<1->"FizzBuzz";1<2->I end||I<-lists:seq(1,1000)]).

Try it online! (in Io)
Try it online! (in Erlang)

JavaScript (Node.js), 58 bytes
for(i=0;i++<1e3;)console.log(i%(2+(this>{}))?i:'FizzBuzz')

Try it online!
JavaScript (V8), 58 bytes
Try it online!

Remove the +0 part for -2, for(i=0;i++<1e3;)console.log(i%(2+(this>{}))?i:'FizzBuzz').

@Λ̸̸ Yea forgot the part when optimizing

Python 2,  136 133 130 bytes
Saved 3 bytes thanks to ceilingcat!!!
Saved 3 bytes thanks to Abhay Aravinda!!!
#define print(a)i;main(){for(;i++<1e3;)printf(i%3?"%d":"FizzBuzz",i);}
print(''.join(i%2and`i`or"FizzBuzz"for i in range(1,1001)))

Try it online!
C (gcc), 136 133 130 bytes
Saved 3 bytes thanks to ceilingcat!!!
Saved 3 bytes thanks to Abhay Aravinda!!!
#define print(a)i;main(){for(;i++<1e3;)printf(i%3?"%d":"FizzBuzz",i);}
print(''.join(i%2and`i`or"FizzBuzz"for i in range(1,1001)))

Try it online!

@ceilingcat Nice one - thanks! :-)

Also, for the python part print(''.join(i%2andior"FizzBuzz"for...

Also, based on other C answers, moving i to outside main allows i++<1e3 saving a byte

@AbhayAravinda Well spotted golfs - thanks! :-)

C (gcc), 132 128 101 99 84 82 81 bytes
main(){for(int i;i++<1e3;)__builtin_printf(i%(2+sizeof'a'%2)?"%d":"fizzbuzz",i);}

Try it online!
C++ (gcc), 132 128 101 99 84 82 81 bytes
main(){for(int i;i++<1e3;)__builtin_printf(i%(2+sizeof'a'%2)?"%d":"fizzbuzz",i);}

Try it online!
-27 -28 bytes from ceilingcat (plus another inspired by ceiling cat)
-15 bytes from Ayxan

@ceilingcat Ah, well done.  I got myself so stuck on using the __cplusplus that I missed golfing it after it showed up so many times.  Interesting use of the builtin printf to avoid the include for c++.

@ceilingcat Good idea on that one, but bit-wise not is unnecessary if you pick a different value for j on that first line.

84 bytes

@Ayxan Oh, very nice.  I forgot that C++ character literals were actual chars rather than ints.

Bash/Perl, 96 bytes
eval 'for i in `seq 500`;do echo $((i*2-1))FizzBuzz;done;exit';print$_%3?$_:FizzBuzz for 1..1000

This is based on an old Perl trick to get a Perl program to run as Perl, if executed as it were a shell program. If executed in either language, it takes the argument to eval, and tries to execute it (Bash) or compile, then execute it (Perl). When run as Bash, it dutifully execute the code, printing the numbers, replacing every second number with FizzBuzz, then exits. Perl, OTOH, tries to compile the string, which fails. It then carries on the execute the second statement, printing out the numbers, replacing every third with FizzBuzz.
Since non-empty separators are allowed, when executed in Bash, there will only be newlines after each FizzBuzz, while when executed in Perl, no whitespace will be outputted at all.
Try it online! (Bash)
Try it online! (Perl)

Perl -M5.010/C (gcc -w), 112 bytes
//;say$_*2-1,Fizzbuzz for 1..500;<<'}';
main(){for(int i=1;i<1001;i++){i%3?printf("%d",i):printf("FizzBuzz");}
}

Try it online! (C)
Try it online! (Perl)
This hides the Perl code behind a C++ style comment, and the C code inside a Perl here doc, using the final character of the C code as the here doc terminator. The C++ style comment marker looks like an empty regular expression to Perl, which happily executes it, to no visible effect. Just as the here doc which is in void context.
The C version does not print any whitespace, the Perl version prints a newline after each FizzBuzz.

Befunge-93/Perl -M5.010, 125108 Bytes
#  v            .:  <>
say $_*2-1,# >:1+:3%|
#  >:8555***-|
             @
,,,,,,,,"FizzBuzz" #<^
for 1..500

Try it online!
Try it online!
This can probably easy golfed down further, but I'm far from a Befunge expert. This code cannot be separated into different pieces of code, where each language ignores the part written in the different language -- the ,,,,,,,,"FizzBuzz" section is used by both Perl and Befunge.
To explain it further, what Perl sees, after removing the comments, is:
say $_*2-1,,,,,,,,,"FizzBuzz" for 1..500

and what Befunge sees is:
#  v            .:  <>
             >:1+:3%|
   >:8555***-|
             @
,,,,,,,,"FizzBuzz" #<^

JavaScript (Node.js) / Ruby / Python 2 / Python 3 / Perl 5 / PHP + -d short_open_tag=on -d output_buffering=on / Bash, 311 bytes
s=0;f='FizzBuzz';0//1;'''=;y=/.__id__;eval"s+=1;puts s%3>0?s:f;"*1e3;%q}<?ob_end_clean();$i=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;#?>";while(s<1e3)console.log(++s%2?s:f)//';for i in {1..1000};{ a=($f);echo ${a[((i%8))]:-$i};} #''';exec('s+=1;print(s if s%(5if 3/2>1else 4)else f);'*1000)

Try them all online! (truncates to the first 25 lines of each language)
I know there's no benefit to adding more languages, but I enjoyed this so thought I'd have a try at adding a few. Overall I'd like to share more of the code if possible, but the different looping structures make it pretty tricky. I'm sure there's a way I could share the Python and Ruby code to reduce some bytes, so I'll play with that more next.
JavaScript (Node.js) (with comments and unused strings removed)
s=0;f='FizzBuzz';0
while(s<1e3)console.log(++s%2?s:f)

Ruby (with comments and unused strings removed)
s=0;f='FizzBuzz';0//1;'''=;y=/.__id__;eval"s+=1;puts s%3>0?s:f;"*1e3;die;

0//1;.../.__id__;: this is 0 / /1;.../.__id__ where /1;.../ is a RegExp and the __id__ property is just a short property that exists on the RegExp object that returns a number to prevent a type error. This uses string repetition and eval as it was slightly shorter (but a true Rubyist might be able to correct me!).
Python 2 / Python 3 (with comments and unused strings removed)
s=0;f='FizzBuzz';0//1;exec('s+=1;print(s if s%(5if 3/2>1else 4)else f);'*1000)

This uses the classic floored integer division check for Python 2 vs. 3 and string repetition the same as Ruby because it was shorter (although, again, any Pythonistas please feel free to correct me!)
Perl 5 + -M5.10.0 (with unused strings removed/truncated)
s=...=...=;y=...=...=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;

This uses Perl's s/// and y/// (tr///) operators to ignore most of the code. This is the same code as is used for PHP and works because there's no true in Perl, so the bareword true evaluates to 0.
PHP + -d short_open_tag=on -d output_buffering=on (with non-executed code removed)
<?ob_end_clean();$i=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;#?>

A bit cheaty, but uses a pretty well known technique of the output_buffering option and ob_end_clean() to discard the content before the first <?, then die;#?> before the rest of the program is parsed, basically 'hiding' the PHP program within strings and comments of the others. The majority of this code is shared with Perl.
Bash (with comments and unused strings removed)
s=0;f='FizzBuzz';0//1;for i in {1..1000};{ a=($f);echo ${a[((i%8))]:-$i};}

Because of how variables are set in Bash (var=value) we can share f='FizzBuzz' from the JavaScript, Ruby, Python code, but it's pretty much just on its own. The useful thing with Bash is that ''' isn't a syntax error, it's just concatenating an empty string and the start of a new string, so Bash pretty much just 'ignores' (executes and returns an error) all the code and it's relatively easy to find a space to drop it into.

Python 2 / Python 3 / Octave, 109 bytes
This is an add-on to @ElPedro's answer, adding Octave to his clever solution for Python 2 and 3.
x=1000;
while x>0%1:print((x,'FizzBuzz')[x%(3/2*2)<1]);x-=1;"""
printf('%d FizzBuzz %d ',x,x-1)
x-=3;
end%"""

Try it online! (Python 2)
Try it online! (Python 3)
Try it online! (Octave)


text:
Leon's shooting range problem
Leon's story
Leon is a professional sling shooter and he comes to a shooting range everyday to practice. A casual target is not a challenge for him anymore so before shooting he first covers the target of radius 1.0 with k rectangle stickers. He then fires n shots that cannot hit the stickers.

What's special about Leon is that he always shoots randomly but with a uniform distribution.
Leon everyday takes on a bigger challenge and puts more stickers. However he started noticing that shooting takes too much time now so he decided to ask you for the best strategy.

Task
Implement a program which will randomly pick n points with the lowest time complexity possible. Each point should be inside a circle target, and none of them lands in any of k rectangle stickers.
Input:
List of k rectangles in whatever form fits you.
Eg. where each rectangle is a list of:
[x_min, x_max, y_min, y_max]

The list could be:
[[0.1, 0.3, -0.2, 0.1], [-0.73, -0.12, 0.8, 1.4]]

Output:
List of coordinates of n points in whatever form fits you.
Rules:

Points have to be picked randomly with uniform distribution
Every point lays inside a circle
None of the points lays inside a rectangle sticker
Stickers can overlap each other
Circle's radius is equal to 1.0 and its center is at coordinates (0.0, 0.0)
Every coordinate is in form of floating point number
For edge cases - choose whatever fits you

EDIT:
Thanks to @Luis Mendo and @xnor it turned out that one more rule might be useful.

With each new sticker 1/4 of the remaining board will be covered. This means that having k stickers the uncovered part of the target will be (3/4)^k of the whole.

Rating
The best time complexity wins!
EDIT:
For the sake of rating we will assume that k and n are linearly proportional, meaning that O(k^2 + n) will be rated equally to O(k + n^2)

Do you mean asymptotic time complexity? Also, how do you define time complexity for algorithms with random running time (like rejection samping)?

@LuisMendo Yes, asymptotic time complexity. For random running time take average number of operations for different k, n and rectangles' placement or whatever variable is significant for your approach

What precision is required on the chosen floats?

@Jonah Anything of a precision of 4 or more decimals should work

One possible strategy is rejection sampling, that is picking a random point in the circle, and if it overlaps a rectangle, then repeating. How should one treat the expected number of trials for the purposes of time complexity. For a "typical case", this is a constant, but if the rectangles are made to cover all but a tiny part of the circle, it can be arbitrarily high.

How do we compare run-times of solutions that make different tradeoffs in n and k? It seems to me that whether you have many points or many rectangles affects how effective it is to  try to preprocess the rectangles and their area before generating points.

@xnor For purpose of this challenge it should be enough if we notated eg. t as ratio of target covered by stickers. Following this formula we can calculate the average number of draws will be (-1/(t-1))(if I'm not mistaken).

@Elgirhath I understand and agree with that, but it's still not clear to me how to deal the the t-dependence in the asymptotic complexity when scoring a solution.

@xnor I've made an edit to the post which should solve this problem.

This should be possible in (n+k) log(nk), but this doesn't halt

Area-based algorithm, \$O(k^2+n\log(k))\$
Our general strategy is to instead select points (outside the sticker rectangles) from the square (-1,-1) to (1,1), then repeat if we don't get a point within the circle. On average, we will have to select \$\frac{4}{\pi}\$ points from the square for each point in the circle.
The runtime is not depend on rectangle coverage, but it does depend on measures of rectangle intersection (denoted L in the complexity analysis in the code). For the listed complexity, I use \$L=O(k)\$, which is probably not tight. If \$L=O(\log(k))\$ can be proven, then the complexity is \$O((k+n)\log(k))\$ (see get_heights for an algorithmic alternative).
Define "open area" to be the area that points could be generated in. Recall that we are using a square instead of a circle, so the total area is piece-wise linear in x.

Precompute the total open height function \$h(x)\$ (this is piece-wise constant, so store the change at each transition: either the start or end of a new rectangle). Similarly, pre-compute the cumulative areas \$\int_{-1}^{x} h(x)\$, which is piece-wise linear, so once again store the value at each transition. This can be done in \$O(k \log(k))\$ time

Precompute the intervals on which y coordinates can be distributed for a given x (again, only storing this interval on each transition). This might be able to be done in \$O(k \log(k))\$, but this algorithm only succeeds at \$O(k^2)\$ time

Generate points. For each point: (average \$\frac{4}{\pi} n\$ times for a total runtime of \$O(n\log(k))\$
a. Choose a random value \$r\$ for the area (\$O(1)\$)
b. Find \$x\$ such that \$\int_{-1}^{x} h(t) dt = r\$. This is accomplished through binary search on the pre-computed heights \$h\$ and cumulative areas \$\int h\$, so this is done in \$O(\log(k))\$ time
c. Choose a random value \$y\$ for the given x such that (x,y) is in an open area. Through similar binary search as 3b, this is done in \$O(\log(k))\$ time
d. Reject the point if it is outside the circle (constant factor 4/pi)

The total runtime is \$O(k\log(k)) + O(k^2) + O(n\log(k)) = O(k^2+n\log(k))\$
In the following example images, I used the same n=10000, so more rectangle coverage meant a higher density of points.

Full python code below, including matplotlib display:
import math
import random
# for binary search
import bisect
# matplotlib for plotting the output points
import matplotlib.pyplot as plt
import matplotlib

def find_le(ls, x):
    # find_le is O(log(|ls|))
    # Find rightmost value less than or equal to x in ls
    i = bisect.bisect_right(ls, x)
    return i-1, ls[i-1]

class Interval:
    def __init__(self, lo, hi):
        # each range is tuple (lo, hi)
        # ranges shall be sorted in ascending order
        # each range does not overlap with other ranges
        self.ranges = [(lo, hi)]

    def remove(self, lo, hi):
        new_ranges = []
        for self_range in self.ranges:
            if lo <= self_range[0] <= hi < self_range[1]:
                new_ranges.append((hi, self_range[1]))
            elif self_range[0] < lo <= self_range[1] <= hi:
                new_ranges.append((self_range[0], lo))
            elif self_range[0] < lo < hi < self_range[1]:
                new_ranges.append((self_range[0], lo))
                new_ranges.append((hi, self_range[1]))
            elif lo <= self_range[0] < self_range[1] <= hi:
                pass
            elif hi <= self_range[0] or self_range[1] <= lo:
                # no overlap
                new_ranges.append(self_range)
        self.ranges = new_ranges

    def cache_lengths(self):
        # If L is the number of subintervals of this Interval
        # then cache_lengths is O(L) ⊂ O(k)

        # in cum_lengths, (0.6, 0.7) means that the total length to the
        # left of x=0.7 in this interval is 0.6
        self.cum_lengths = [(0, -1)]
        last_length = 0
        for self_range in self.ranges:
            length = self_range[1] - self_range[0]
            self.cum_lengths.append((last_length, self_range[0]))
            last_length += length
        self.total_length = last_length

    def random_point(self):
        # If L is the number of subintervals of this Interval
        # then random_point is O(log(L)) ⊂ O(log(k))
        r = random.random()*self.total_length
        # This find_le is O(log(L))
        i, (length_left, x_left) = find_le(self.cum_lengths, (r,))
        return (r - length_left) + x_left

    def __repr__(self):
        return "I" + str(self.ranges)

def interval_complement(rects):
    # O(L) where L is the length of rects list
    interval = Interval(-1, 1)
    for rect in rects:
        interval.remove(rect.bottom, rect.top)
    return interval

class Rect:
    def __init__(self, left, right, bottom, top):
        self.left = min(left, right)
        self.right = max(left, right)
        self.bottom = min(bottom, top)
        self.top = max(bottom, top)
        self.width = self.right - self.left
        self.height = self.top - self.bottom

    def __repr__(self):
        return f"Rect({self.left}, {self.right}, {self.bottom}, {self.top})"

    def overlap(self, others):
        # returns vertical (y) overlap between self and other rects
        total_overlap = 0
        # https://pyinterval.readthedocs.io/en/latest/guide.html#operations is
        # looking so tempting right now, but unions/merges would
        # require Principle Inclusion-Exclusion which can be k^2 worst case
        starts = sorted(others, key=lambda rect: rect.bottom, reverse=True)
        ends = sorted(others, key=lambda rect: rect.top, reverse=True)
        active_rects = set()
        overlap_start = self.bottom
        while ends:
            if starts and starts[-1].bottom < ends[-1].top:
                active_rect = starts.pop()
                if not active_rects and active_rect.bottom > self.bottom:
                    # This is the start of an overlap interval
                    overlap_start = active_rect.bottom
                active_rects.add(active_rect)
            else:
                active_rect = ends.pop()
                active_rects.remove(active_rect)

                if not active_rects:
                    # This is the end of an overlap interval
                    # Rare cases of negative = started and ended below start of self
                    total_overlap += max(0, min(active_rect.top, self.top) - overlap_start)
        return total_overlap

    def as_matplotlib_rect(self):
        return matplotlib.patches.Rectangle((self.left, self.bottom), self.width, self.height)

def get_heights(rects):
    # get_heights is O(k log(k)) total
    # Sorting: O(k log(k))
    # Use these lists as a queue
    starts = sorted(rects, key=lambda rect: rect.left, reverse=True)
    ends = sorted(rects, key=lambda rect: rect.right, reverse=True)
    # list of tuples (open height starting at x, x, open intervals starting at x)
    heights = [(2, -1, Interval(-1,1))]
    active_rects = set()
    while ends:
        # inner loop performed once for k left edges and k right edges,
        # so this is O(k)
        if starts and starts[-1].left < ends[-1].right:
            # next x-pos is the start of a new rect
            rect = starts.pop()
            height_diff = rect.height - rect.overlap(active_rects)
            height = heights[-1][0] - height_diff
            active_rects.add(rect)
            # interval_complement is O(L) so this is O(k^2), not sure if it is O(k log(k))
            heights.append((height, rect.left, interval_complement(active_rects)))
        else:
            # next x-pos is the end of an old rect
            rect = ends.pop()
            active_rects.remove(rect)
            # rect.overlap is O(L) as well
            height_diff = rect.height - rect.overlap(active_rects)
            # Two choices to get O(k log(k)):
               # 1. prove that |active_rects| is O(log(k)) under the given approaches
               # 2. avoid using interval_complement on each transition using some increments approach, and avoid doing rect.overlap on each transition
            height = heights[-1][0] + height_diff
            heights.append((height, rect.right, interval_complement(active_rects)))
    heights.append((2, 1, Interval(-1,1)))
    # cum_areas is the cumulative areas from -1 to x (of not rects)
    # Not subtracting curve because we will be sampling from square
    cum_areas = [(0, -1, Interval(-1, 1))]
    last_height = 2
    for height, x, interval in heights[1:]:
        last_area, last_x, _ = cum_areas[-1]
        new_area = (x-last_x)*last_height
        cum_areas.append((last_area + new_area, x, interval))
        last_height = height
    return (heights, cum_areas)

def random_pick_points(rects, num_points):
    # random_pick_points is O((n+k) log(k))
    # Step 1. Precompute heights: O(k log (k))
    heights, cum_areas = get_heights(rects)
    total_area = cum_areas[-1][0]
    points = []
    # Step 2. Precompute vertical intervals: O(k)
    for _, _, y_interval in cum_areas:
        y_interval.cache_lengths()
    # Step 3. Sample points outside rects and within circle
    # Total time complexity of this loop is O(n log(k))
    while len(points) < num_points:
        # This loop is reached average (4/pi)*n = O(n) times
        # Each occurence has complexity O(log(k))
        # Step 3a. Choose a random area value
        area = random.random()*total_area
        # Step 3b. Choose the x value such that area is the total area
        # outside rects and within 2x2 square to the left of x
        # There are 2k+1 total cum_areas so this find_le is O(log(k))
        i, (area_left, x_left, y_interval) = find_le(cum_areas, (area,))
        height, _, _ = heights[i]
        x = x_left + (area - area_left) / height
        # Step 3c. Choose a y value uniformly in the open spaces of that x value
        # Interval.random_point() is O(log(k))
        y = y_interval.random_point()
        # Step 3d. Rejection sample until points are inside the circle
        # On average, takes constant 4/pi random points to land within the circle
        if x*x + y*y < 1:
            points.append((x, y))
    # Done!
    return points

def display_points(rects, points):
    fig, ax = plt.subplots(1)
    ax.plot(*zip(*points), 'ko', markersize=1, alpha=0.5)
    ax.axis([-1, 1, -1, 1])
    ax.add_collection(
        matplotlib.collections.PatchCollection(
            [rect.as_matplotlib_rect() for rect in rects],
            facecolor = 'r', edgecolor='None', alpha=0.5
        )
    )
    plt.show()

def display_random_points(rects, num_points):
    points = random_pick_points(rects, num_points)
    display_points(rects, points)

def random_rects(k):
    return [Rect(*[random.random()*2-1 for _ in range(4)]) for i in range(k)]

k = 20
# rects = random_rects(k)
# print("Rects:", rects)
n = 10000
# print("Points:", random_pick_points(rects, n))
display_random_points(random_rects(k), n)

Try it online I guess, if you can read a list of points.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Number of tilings on a triangular board with triangular tiles
Background
Consider the shape \$T(n)\$ consisting of a triangular array of \$\frac{n(n+1)}{2}\$ unit regular hexagons:

John Conway proved that \$n = 12k + 0,2,9,11\$ if and only if \$T(n)\$ can be tiled (i.e. exactly covered without overlapping) with \$T(2)\$. At the same time, he also proved that no coloring argument could prove the fact. (Yes, this is yet another Conway challenge.)
Challenge
Let's define \$a_n\$ as the number of distinct tilings of \$T(n)\$ by \$T(2)\$. Compute as many terms of \$a_n\$ as possible in 10 minutes.
Reflection and/or rotation of a tiling is considered distinct from itself, unless the two are identical.
The program that prints the largest number of terms wins. In case of tie, the one that prints the last term in shorter time wins.
I have a Windows 10 machine with Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz and 32GB RAM, with Ubuntu 18.04 installed in WSL. Please include the instructions to run your code and where it works (Windows or Linux).
Output format (with test cases)
The submission should print the results infinitely for each \$n\$ starting from 0. Each line should include the values of \$n\$ and \$a_n\$. Here is first 21 lines of the expected output:
0 1
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 2
10 0
11 8
12 12
13 0
14 72
15 0
16 0
17 0
18 0
19 0
20 0
21 185328
22 0
23 4736520
24 21617456
25 0
26 912370744
27 0
28 0
29 0
30 0
31 0
32 0

Test cases for \$n \le 20\$ are generated using a naive Python 3 program. \$a_{21}\$ through \$a_{32}\$ (meaningful highest being \$a_{26}\$) were found using Arnauld's JS submission.
Notably, neither the full sequence 1, 0, 1, 0, 0, 0, ... nor the stripped-down one 1, 1, 2, 8, 12, 72, ... is on OEIS yet. As I don't have an OEIS account, I will let anyone interested to post this sequence (both versions) to OEIS (please leave a comment before you do). The sequence of nonzero indices is A072065. Edit: The sequence is on A334875, thanks to Lyxal.
Leaderboard

Rust with rustc -O by Anders Kaseorg, Score 44 at 45s
C++ with g++ -O3 by l4m2, Score 35 at 7min
Javascript with node by Arnauld, Score 32 at 1.8s

Pending

(none)

Do reflections / rotations of a tiling count as the same tiling or different?

@LevelRiverSt They count as different (unless they exactly match, of course). e.g. T(9) has only one tiling modulo reflection/rotation, which has 3-fold rotational symmetry. It is distinct from its mirror image, so a_9 = 2.

It start to seem that faster runner need external storage

@Bubbler are you sure conway meant T(2) by "tribone"? it doesn't look like a bone

@ngn Changed the title, though I had to describe it in a roundabout way because the T(2) has only a generic name. Does it sound good now? (Note to others: multiple papers describe a "tribone" as a tile made of three hexagons in a straight line. The only source of naming T(2) a tribone seems to be Tilings by Ardila and Stanley, which I suspect to be wrong.)

@Bubbler sounds better to me. thanks.

JavaScript (Node.js), N =  22 25  32 in ~2 seconds
A recursive search using bit masks and a cache to keep track of patterns whose result is already known.
It doesn't make much sense to try go further in Node. Using a binary matrix is significantly slower and BigInts are even slower. It should rather be ported to a language natively supporting 64-bit integers.
'use strict';

let ts = new Date;

for(let n = 0; n <= 32; n++) {
  console.log(
    n.toString().padStart(2) + ' ' +
    solve(n).toString().padStart(10) + ' ' +
    '(' + ((new Date - ts) / 1000).toFixed(2) + ')'
  );
}

function solve(n) {
  // trivial cases
  if(![0, 2, 9, 11].includes(n % 12)) {
    return 0;
  }
  if(n == 0) {
    return 1;
  }

  // We work on a triangle stored as an array of bit masks:
  //   8 7 6 5 4 3 2 1 0 |
  //  -------------------+---  With this format, the tribones
  //   . . . . . . . . A | 0   are turned into the following
  //   . . . . . . . A A | 1   trominos:
  //   . . . . . . B B C | 2
  //   . . . . . D B C C | 3    X O    and    . X
  //   . . . . D D E E F | 4    O .           O O
  //   . . . G H H E F F | 5
  //   . . G G H I I J J | 6   where 'X' is the arbitrary anchor
  //   . K L L M I N J O | 7   point used in this code
  //   K K L M M N N O O | 8
  let a = Array(n).fill(0),
      cache = a.map(_ => new Object);

  // recursive search, starting at (x, y) = (0, 0)
  return (function search(x, y) {
    // if we've reached the last row, make sure it's complete
    if(y == n - 1) {
      if(a[y] == (1 << n) - 1) {
        return 1;
      }
      return 0;
    }

    // if we are beyond the last column, go on with the next row
    if(x < 0) {
      y++;

      // either return the result from the cache right away
      if(cache[y][a[y]] !== undefined) {
        return cache[y][a[y]];
      }
      // or do a full search
      return cache[y][a[y]] = search(y, y);
    }

    // if (x, y) is already set, advance to the next column
    if(a[y] >> x & 1) {
      return search(x - 1, y);
    }

    let res = 0;

    // try to insert X O
    //               O .
    if(x && !(a[y] >> x - 1 & 1)) {
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
      res += search(x - 2, y);
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
    }

    // try to insert . X
    //               O O
    if(!(a[y + 1] >> x + 1 & 1)) {
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
      res += search(x - 1, y);
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
    }

    return res;
  })(0, 0);
}

Try it online!
Output
 0          1 (0.00)
 1          0 (0.00)
 2          1 (0.00)
 3          0 (0.00)
 4          0 (0.00)
 5          0 (0.00)
 6          0 (0.00)
 7          0 (0.00)
 8          0 (0.00)
 9          2 (0.00)
10          0 (0.00)
11          8 (0.00)
12         12 (0.01)
13          0 (0.01)
14         72 (0.01)
15          0 (0.01)
16          0 (0.01)
17          0 (0.01)
18          0 (0.01)
19          0 (0.01)
20          0 (0.01)
21     185328 (0.05)
22          0 (0.05)
23    4736520 (0.24)
24   21617456 (0.60)
25          0 (0.60)
26  912370744 (2.18)
27          0 (2.18)
28          0 (2.18)
29          0 (2.18)
30          0 (2.18)
31          0 (2.18)
32          0 (2.18)

@Bubbler I think this is going to be the last version. You may want to run it again on your own machine. (NB: Since this is using 32-bit integers, it simply can't work for N > 32.)

Trying to get more terms by switching to BigInt made Node crash (JS heap out of memory)...

Seems you use lots of memory, how much?

Oh you actually only go to 26. 33 is out-of-time

https://paste.ubuntu.com/p/x97FJtvVQb/

On my computer without directly answer 0 when already know it's impossible, https://paste.ubuntu.com/p/KBYWG9w7Y9/

Rust, \$n \le 44\$ in 42 seconds
Build with rustc -O.  Uses about 800 MiB of memory for \$n = 38\$, and \$39 \le n \le 44\$ are trivial.  \$n = 45\$ will almost definitely run out of both time and memory on any reasonable system.
It works by dynamic programming where the states are the presence or absence of hexagons at \$(k - 1, 1), \dotsc, (k - 1, i), (k, i + 1), \dotsc, (k, k)\$; we advance \$i\$ to \$i + 1\$ by considering the addition of tribone \$(k, i + 1), (k - 1, i), (k - 1, i + 1)\$ or \$(k, i + 1), (k - 1, i + 1), (k, i + 2)\$.
use std::iter::Peekable;
use std::mem;

struct Merge<Xs: Iterator, Ys: Iterator>(Peekable<Xs>, Peekable<Ys>);

impl<Xs: Iterator<Item = (u64, u128)>, Ys: Iterator<Item = (u64, u128)>> Iterator
    for Merge<Xs, Ys>
{
    type Item = (u64, u128);
    fn next(&mut self) -> Option<(u64, u128)> {
        if let Some(x) = self.0.peek() {
            if let Some(y) = self.1.peek() {
                if x.0 < y.0 {
                    self.0.next()
                } else if x.0 > y.0 {
                    self.1.next()
                } else {
                    let x = self.0.next().unwrap();
                    let y = self.1.next().unwrap();
                    Some((x.0, x.1 + y.1))
                }
            } else {
                self.0.next()
            }
        } else {
            self.1.next()
        }
    }
}

fn main() {
    for n in 0..63 {
        if 0xa05 & 1 << n % 12 == 0 {
            println!("{} 0", n);
        } else {
            let mut count: Vec<(u64, u128)> = vec![(!(!0 << n) << 1, 1)];
            let mut count1 = vec![];

            for k in (1..n + 1).rev() {
                for i in 0..k - 1 {
                    count1.extend(Merge(
                        Merge(
                            count
                                .iter()
                                .filter(|&&(b, _)| !b & 3 << i == 0)
                                .map(|&(b, c)| (b & !(3 << i), c))
                                .peekable(),
                            count
                                .iter()
                                .filter(|&&(b, _)| !b & 6 << i == 0)
                                .map(|&(b, c)| (b & !(6 << i), c))
                                .peekable(),
                        )
                        .peekable(),
                        count
                            .iter()
                            .filter(|&&(b, _)| b & 2 << i == 0)
                            .map(|&(b, c)| (b | 2 << i, c))
                            .peekable(),
                    ));
                    mem::swap(&mut count, &mut count1);
                    count1.clear();
                    if i == 1 {
                        count.retain(|&(b, _)| b & 6 != 2);
                    }
                }
                count.retain(|&(b, _)| b & 1 << k == 0);
            }
            assert_eq!(count.len(), 1);
            assert_eq!(count[0].0, 0);
            println!("{} {}", n, count[0].1);
        }
    }
}

Try it online!
(TIO times out after \$n = 37\$.)
Output
0 1
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 2
10 0
11 8
12 12
13 0
14 72
15 0
16 0
17 0
18 0
19 0
20 0
21 185328
22 0
23 4736520
24 21617456
25 0
26 912370744
27 0
28 0
29 0
30 0
31 0
32 0
33 3688972842502560
34 0
35 717591590174000896
36 9771553571471569856
37 0
38 3177501183165726091520
39 0
40 0
41 0
42 0
43 0
44 0

I don't seem to understand the second paragraph; is this broken profile dynamic programming?

@mypronounismonicareinstate I haven’t heard that term, and it’s hard to figure out what it means without referencing the Google cache of a post on a blog that went down, but it seems to be essentially the same idea.

It does run up to n=44 in 45 seconds on my PC (and fails while trying to allocate more memory at around 3 minutes). Nice job.

I tried your text way in C++, and on $n=44$ there are $100483899$ elements, or 1.6GB if each element use 16 bytes(two int64s). How you use 800MB on $n=38$?

Oh you ran backward

@l4m2 For $n = 38$ there are 17184752 elements at the highest point; they are 24 bytes each ((u64, u128)) because $A(38) > 2^{64}$, and they get shuffled between 2 vectors. For $n = 44$ we already know $A(44) = 0$.

Tested, for $n=45$ with some memory compression disk usage maximum was 2.3GB at end of line(maybe *2 for not and end of line, and *3/2 for using int128 rather than double, but still affordable)

\$T(33) = 3688972842502560 \$
> 1 0
> 2 1
> 3 0
> 4 0
> 5 0
> 6 0
> 7 0
> 8 0
> 9 2
> 10 0
> 11 8
> 12 12
> 13 0
> 14 72
> 15 0
> 16 0
> 17 0
> 18 0
> 19 0
> 20 0
> 21 185328
> 22 0
> 23 4736520
> 24 21617456
> 25 0
> 26 912370744
> 27 0
> 28 0
> 29 0
> 30 0
> 31 0
> 32 0
> 33 3688972842502560

Process returned 0 (0x0)   execution time : 71.730 s
Press any key to continue.

Code
#include <map>
#include <stdio.h>
#include <algorithm>
const int N = 33;
typedef unsigned long long ulong;

#define long ulong

std::map<ulong, long> A, B;
int i; long base;
template<bool last = false>
void bitfsh(ulong j, ulong d) {
    if (!j) {
        if(!last || d==0) B[d] += base;
        return;
    }
    int p = sizeof(ulong)*8-1-__builtin_clzll(j);
    if (d & 2ULL<<p) {
        bitfsh<last> (j ^ 1ULL<<p, d ^ 3ULL<<p);
    }
    if (p && (j & 1ULL<<p-1)) {
        bitfsh<last> (j ^ 3ULL<<p-1, d ^ 1ULL<<p);
    }
}
template<bool last = false>
long run() {
    B.clear();
    for (auto p=A.begin(); p!=A.end(); ++p) {
        ulong j = (*p).first;
        if (j%65536==0) fprintf(stderr, "%d %lld\r", i, j);
        base = (*p).second;
        if(base) bitfsh<last> (j, (1ULL<<i)-1);
    }
    std::swap (A, B);
    fprintf(stderr, "%60c\r", ' ');
    return A[0];
}
const ulong fs = sizeof(long) << N-1;
int main() {
    A[0] = 1;
    for (i=1; i<N; ++i) {
        //fprintf(stderr, "%d\n", i);
        printf ("> %d %llu\n", i, run ());
    }
    printf ("> %d %llu\n", i, run<true> ());
    exit(0);
}

T(45) = 1.9935928828199593078904655e+31
Ran in 31953.963 s on my computer(including state backups), and use approximately 4.5GB disk.
Use @Anders Kaseorg 's solution but with disk as storage. For each \$k,i\$ amounts of items can be found here. TIO

Sorry, but if it is for Visual Studio (I'm guessing from <windows.h>), I can't run it on my PC. Could you change the code to be gcc(or any other free C++ compiler)-compatible, or share an instruction to run the code as-is?

@Bubbler The windows.h is of historical reason, you can remove it

Score: n=35 at 7 minutes (core dumped shortly after that). Btw, g++ complained that there was already a typedef called ulong, so I inserted #define ulong uulong right before the typedef.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
I hate broccoli!
My mom really wants me to eat broccoli, but I hate it and never want to eat it. Mom wants to trick me so she cuts it into small pieces, puts it in a salad and mixes it. Help me find out if the salad contains broccoli!
Input:
Array of mixed letters of all the ingredients. For a single broccoli ingredient it could be:
[c,o,r,b,l,c,i,o]

Output:
Boolean or other convienient output allowing to distinguish if a salad contains broccoli or not.
Rules:

all possible ingredients are onion, broccoli, celery and beans
input array is always formed of mixing valid ingredients (meaning that it can be always decoded back to the original ingredients array)
input array cannot be decoded into more than one valid ingredient combination
each ingredient can occur 0 or more times in the salad

Sample test cases:
true stands for a salad with broccoli
[c,o,r,b,l,c,i,o] //true
[o,b,n,o,i,i,e,l,n,a,o,r,n,s,b,o,c,c] //true
[l,c,b,r,r,o,r,c,i,i,c,o,c,b,o,c,c,b,i,o,l,o,l,o] //true

[] //false
[o,n,i,o,n] //false
[b,n,s,i,a,o,n,b,a,s,e,e,n,o,n] //false
[b,r,o,c,c,o,l,i,e,y,e,r,l,a,e,e,n,s,y] //false
[e,n,s,o,e,n,i,o,a,o,o,e,n,n,e,l,n,l,e,o,e,r,c,l,o,y,i,r,y,r,y,b,e,l,n,n,c,c,r,c,e,y,i,e] //false

This is code-golf so the shortest code in bytes wins!

Can we take the input as a string instead of array?

@KevinCruijssen yes

Poor broccoli! I haven't heard anyone who wants to eat it.

This challenge would have been much more interesting with soya.

@Wrzlprmft with soya you would still have count(c) > count(l). However I will probably put an adjusted version in the future ;)

@Λ̸̸ Broccoli with ranch :)

@Λ̸̸ Great, now I feel like I'm weird for liking broccoli /:

This problem is a subset of this problem; @RedwolfPrograms I also love broccoli, once I even wrote about broccoli on my math blog

@Λ̸̸ Broccoli is the only green vegetable my kid likes.

Wow, I adore broccoli. It's literally my favourite vegetable. People are strange.

Python 2, 34 32 bytes
-2 bytes thanks to @dingledooper
lambda a:cmp(*map(a.count,'bs'))

Try it online!
Returns 1 for true, 0 for false

J, 14 bytes
[:=/1#.'cy'=/]

Try it online!
Idea of invariant based on letter counts from mathjunkie's clever answer -- be sure to upvote him.

0 for contains broccoli
1 for not

Tests if the number cs is equal to the number of ys.  This will only be true when no broccoli is present.

perl -ple, 14 bytes
$_=y-y---y-c--

Try it online!
Prints 0 if no broccoli is present, something else if there is.

How does this work?

It counts the number of ys in the string, and subtracts the number of cs. If equal, no broccoli is present. Adding spaces to the code, it reads $_ = y-y-- - y-c--. Using more traditional delimiters, and using the usual name for the operator, this becomes $_ = tr/y// - tr/c//. tr/y// replaces any y in $_ by, well, itself, because the replacement part is empty. But it returns the number of ys replaced, hence, counting the number of ys. tr/c// does the same, but for cs.

05AB1E, 7 6 bytes
„bsS¢Ë

-1 byte by reversing the output: will output 0 if it contains broccoli and 1 if not.
Try it online or verify all test cases.
6 bytes alternative which outputs 1 if it contains broccoli and 0 if not:
AS¢üÊн

Try it online or verify all test cases.
Explanation:
„bs     # Push string "bs"
   S    # Convert it to a character-list: ["b","s"]
    ¢   # Count each in the (implicit) input
     Ë  # Check if the counts are the same for both letters (1 if truthy; 0 if falsey)
        # (after which it is output implicitly as result)

A       # Push the lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
 S      # Convert it to a character-list: ["a","b","c",...,"z"]
  ¢     # Count each in the (implicit) input-list
   ü    # For each overlapping pair of counts:
    Ê   #  Check that they are not equal to one another (1 if truthy; 0 if falsey)
     н  # Pop and only leave the first check (for letters 'a' and 'b')
        # (after which it is output implicitly as result)

If the amount of b and s/a are the same, it means the input only contains beans and no broccoli.

Wasn’t an input that includes broccoli, but other invalid salad ingredients supposed to be false? Or did I read that wrong?

@brandonscript You've indeed read that correct, but the challenge also states "Boolean or other convienient output allowing to distinguish if a salad contains broccoli or not." So in my top program I output 0 for truthy and 1 for falsey (which is probably why you're your questions is coming from?), and in my bottom answer I output 1 for truthy and 0 for falsey. So broccolieyerlaeensy for example (which contains broccoli as well as some other ingredients) would output 1 in my top program and 0 in my bottom program as falsey result.

Ah! Got it. Well done.

MATLAB/Octave, 26 bytes
@(b)b&&diff(sum(b'=='cl'))

Try it online!
Credit to @mathjunkie's answer for the idea. Interestingly comparing c and l counts also works because celery has one of each, but broccoli has a different number.
MATLAB likes to expand == into 2D arrays if the inputs are vectors in differing orientations. However this doesn't work with empty arrays. Fortunately empty is false in MATLAB and non-empty with any non-zero elements is true, so we can simply use the input as a logical true-false to capture that case.

Have you tried MATL?

APL (Dyalog Classic), 19 12 bytes
>/+/↑'cl'=⊂⍞

Try it online!
Note that you have to add ⎕← to the beginning for it to output. Originally created with ngn/apl.
>/+/↑'cl'=⊂⍞
            ⍞ ⍝ get input
     'cl'=⊂   ⍝ make two packed vectors: characters equal to c and l
  +/↑         ⍝ turn into two row matrix and add (to get number of 'c's and 'l's
>/            ⍝ Are there more 'c's than 'l's?

returns broccoli: 1, no broccoli: 0

Turning this into a dfn yields the same bytecount...

Can you do something like I am doing in terms of checking l and c equality and only summing once?

@streetster I wish I knew how. APL is similar to K but using what you did would cause a length error. I tried to do it with something like ∊(is ⍺ in ⍵) but that can't find the number of times that ⍺ is in ⍵.

@Λ̸̸ that outputs, but what is it supposed to output? It outputs 1 for ''broccolieyerlaeensy' and 'broccoli'.

@streetster I managed (with the help of APL Orchard). I needed to add ⊂ but it worked and since I only use input once, I don't need to assign L. Saved 7 bytes.

Nice golfing! K is fairly inspired by APL, and I am normally out-golfed by APL solutions!

JavaScript (ES6),  33  32 bytes
Saved 1 byte by not forcing a Boolean value, as suggested by @SteveBennett
Takes a string and returns undefined (falsy) for a broccoli-free salad (yummy!) or a string (truthy) otherwise (yuck!).
s=>s.split`b`[s.split`s`.length]

Try it online!

Surely that succeeds for [l,c,b,r,r,o,r,c,i,i,c,o,c,b,o,c,c,b,i,o,l,o,l,o] by chance that this is a triple broccoli salad, and that wouldn't have worked for a double broccoli salad?

@Neil Yes, I was just (slowly) figuring it out. :-( Now fixed.

Is the ! really required? The problem isn't strict on the output,  so you would just be returning truthy for broccoli, or falsy (undefined) without.

@SteveBennett I guess you're right. Thank you!

Btw I really love this double split solution. So elegant.

JavaScript (SpiderMonkey), 32 bytes
s=>s.map(c=>++this[c],r=y=0)|r>y

Try it online!
JavaScript (Node.js), 37 bytes
s=>s.map(c=>n+=~~{r:1,y:-1}[c],n=0)|n

Try it online!

I think there might be a similar formula that works with < and > instead of ==, but I haven't checked

@mypronounismonicareinstate Yes it saves a byte, but should not be two

For anyone else mystified by this like I was: ++this[foo] is the same as ++foo but doesn't throw if foo isn't defined. r and y are just being set to zero in a convenient location - the fact that they're passed to map is conveniently irrelevant. Overall the code is just counting if there are more rs than ys

Charcoal, 7 bytes
›№θb№θs

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean; - for broccoli, nothing for none. Explanation:
 №θb    Number of `b`s in input
›       Exceeeds
    №θs Number of `s`s in input
        Implicitly print

K (oK), 11 bytes
Solution:
</+/"sb"=/:

Try it online!
Explanation:
Shamelessly stolen "more s' than b's" logic from mathjunkie:
</+/"sb"=/: / the solution
    "sb"=/: / "sb" equal (=) each-right (/:)
  +/        / sum
</          / s less than b? (aka no brocoli?)

You beat me by one because you have each-right. Is that in APL?  Also just realized that my new code is very similar to your code (I didn't try to copy).

Zsh, 22 characters
((${#1//a}==${#1//b}))

Expects the ingredients as a single command line parameter.
Sets the exit code to 1 for broccoli alert and 0 for no broccoli.
(Just to keep the exit code semantics of 0 = Ok / non-0 = error. Using < for comparison would save 1 character but reverse the result's encoding.)
Sample run:
manatwork@manatwork ~ % . ./broccoli-detector.zsh obnoiielnaornsbocc
manatwork@manatwork ~ % echo $?
1
manatwork@manatwork ~ % . ./broccoli-detector.zsh broccolieyerlaeensy
manatwork@manatwork ~ % echo $?
0

Try it online! / Try all test cases online!

Jelly,  7  6 bytes
ċⱮ⁾abE

A monadic Link accepting a list of characters which yields 0 if the salad contains broccoli and 1 if not.
Try it online! Or see the test-suite.
How?
Tests whether the number of 'b's (in both 'broccoli' & 'beans') is equal to the number of 'a's (in only 'beans').
ċⱮ⁾abE - Link: list
 Ɱ     - map across...
  ⁾ab  - ...what: list of characters = ['a', 'b']
ċ      - ...applying: count
     E - all equal?

Retina 0.8.2, 18 bytes
+`[^bs]|bs|sb

1`b

Try it online! Link includes test cases. Explanation:
+`[^bs]|bs|sb

Delete everything that's not a b or an s, plus any remaining bs or sb pairs that result from bean salad.
1`b

Check whether there is any broccoli.

Java (JDK), 41 bytes
s->s.reduce(0,(a,c)->c<98?a-1:c<99?a+1:a)

Try it online!
Uses a chars()-Stream as input, returns any strictly positive value if it contains brocoli.
Credits

-5 bytes thanks to Elgirhath by comparing b to a instead of b to s, and by allowing any positive value instead of a strict boolean.

-3 bytes. Also you probably don't need last >0 if you specify what given output means ;)

asm2bf, 73 bytes
Try it online!
Takes input on stdin as a string; outputs either ASCII(0x00) or ASCII(0x01).
@l
in r1
ceqr1,.b
cadr2,1
ceqr1,.s
cadr3,1
jnzr1,1
gt r2,r3
outr2

Commented code:
; Essentially, our game plan is to compare amount of `b' and `s' occurences.
; Start a new label
@loop
; Read a character from stdin, put it in r1.
  in r1
; If r1 = 'b' (note the way of expressing a character constant), set
; the condition flag.
  ceq r1,.b
; If the condition flag is set, add 1 to r2
  cadd r2,1
; If r1 = 's', set the condition flag. Otherwise, clear it.
  ceq r1,.s
; If the condition flag is set, add 1 to r3
  cadd r3,1
; If r1 is bigger than zero, we didn't hit eof yet, so continue reading.
; Note: The golfed version is based on a certain property beyond explaining.
; It's related to the way how labels work under the hood.
  jnz r1,%l
; The loop finished.
; Compare r2 and r3 (the accumulators).
gt r2,r3
; Display the result
out r2

Japt, 6 bytes
Takes input as a string with reversed output.
èÕ¶Uèc

Try it - includes all test cases, footer negates the output for easier testing

C (gcc), 57 \$\cdots\$ 53 52 bytes
Saved 3 bytes thanks to l4m2!!!
Saved a byte thanks to Arnauld!!!
a;f(char*s){for(a=0;*s;++s)a+=*s-99?*s>120:-1;a=!a;}

Try it online!
Takes a string as input and returns a \$1\$ for edible and a \$0\$ for grossing me out!

You don't need to initalize a and b to zero so long as they are equal

but better is save a variable using ++ and --

@l4m2 Have to init them or they'd be set to however they were left last run. But using one variable is better anyway - thanks! :-)

@l4m2 Ah, could set one to the other! Clever except could overflow to a negative after many runs.

52 bytes by counting c vs y instead. The result is inverted.

@Arnauld Swapping == for a <, nice one - thanks! :D

C# (Visual C# Interactive Compiler), 39 bytes
i=>i.Count(x=>x==98)>i.Count(x=>x=='s')

Try it online!

-2 by comparing b and a Try it online!

29 bytes Try it online!. Outputs 0 for no broccoli and positive integer otherwise

27 bytes

PHP, 44 42 bytes
-2 bytes thanks to @Elgirhath
$b=count_chars($a,1);echo+($b[98]>$b[97]);

Try it online!

great answer! I don't really know PHP but it seems that you can change != to < and 115 ('s') to 97 ('a') for -2 bytes ;)

Google Sheets, 34 33 bytes
Saved 1 byte thanks to Steve Bennett
=CountIf(A:A,"b")>CountIf(A:A,"s"

Input is in column A. When you exit the cell, Sheets will automatically add the trailing parentheses.
There's nothing really clever about this solution besides implementing the concept from others.

You can save a byte by replacing <> with >. It will never be less than.

Javascript, 46 characters
Shortening Yaraslav's answer:
s=>(q=z=>s.filter(e=>e==z).length)('b')>q('s')

Javascript, 62 characters
x=>([,a,b]=/(a*)(b*)/.exec(x.sort().join``),b.length>a.length)

Maybe I missed something? Just counts if there are more b than a.

Cool!!! Nice code!

JavaScript (Node.js), 62 bytes
s=>s.filter(e=>e=='b').map(Date)>s.filter(e=>e=='s').map(Date)

Try it online!
JavaScript (Node.js), 56 bytes
s=>s.filter(e=>e=='b').length>s.filter(e=>e=='s').length

Try it online!

How does this solution work..?

Ah yes, I had the same idea, but yours is shorter.


text:
Analyze the flow
On a toroidal square grid (you can wrap around) where each cell indicates one direction  (^ > v <) if we pick a cell and start to walk following these directions, we will eventually get stuck in a loop.
We may end up in a different loop, depending on our starting cell.
Not all the cells we encounter constitute our terminal loop: these are said to be tributary to that loop.
Task
Given a square grid configuration, count for each loop \$L_i\$:

How many cells is it made up with? \$n_i\$
How many tributary cells does it have? \$t_i\$

Input
You choose the set of 4 printable characters or integers you'll use as directions.

A square matrix having set elements as entries (can be a string)

Output

List of \$(n_i,t_i)\$ for each \$L_i\$

The pairs can be in any order.
Example
input urdrurllruuuulrududllurdu

-vivid color: loop
-pale color: tributary
In this configuration there are 3 loops (orange, blue, green) of lengths (2, 2, 6) with (0, 10, 5) tributary cells.
output 6 5 2 10 2 0
Alternative inputs:
    1232124421111421313441231
    [[^,>,v,>,^],[>,<,<,>,^],[^,^,^,<,>],[^,v,^,v,<],[<,^,>,v,^]]

Valid outputs:
    2 10 2 0 6 5
    (2, 10), (6, 5), (2, 0)

Non valid outputs:
    10 2 2 0 6 5
    (0, 2), (10, 2), (6, 5)

This is code-golf, so the shortest code wins.

I know you've stated "character", but could our inputs be integers? How about allowing pairs (e.g. '^' as (1,0), < as (-1,0), etc.) to? What about complex numbers (probably a useful one here)?

@Jonathan Allan The input would be too exploitable and also detrimental to the "easy-to-use" feature... One character should be sufficent to directly using it in the program. I can think (1,2,3,6) so only 2 test are needed (%2 and %3). Are integers implied in "printable characters"?

Integers are not printable characters, although some languages (or implementations thereof) will implicitly interpret the digits as integers.

@Jonathan Allan Ok, I've added them, thanks!

Nice challenge. What's the explanation of your avatar?

It's a pi visualisation! Just these days I was thinking of changing it cause I set it years ago and now I'd like better a funnier one :D

Java 10, 374 371 364 bytes
import java.util.*;m->{var L=new HashSet<Set>();int l=m.length,R=l*l,r,c,d;for(Set S;R-->0;S.add(r==R/l&c==R%l?-1:-2),L.add(S))for(S=new TreeSet(),r=R/l,c=R%l;S.add(r*l+c);r=(r-(d-d%3*d)/2+l)%l,c=(c-(d<2?1-2*d:0)+l)%l)d=m[r][c];for(Set z:L){if(z.remove(-1)){c=0;for(Set q:L)if(q.remove(-2)){if(q.containsAll(z))c++;q.add(-2);}System.out.println(z.size()+","+c);}}}

-10 bytes thanks to @ceilingcat.
Uses a matrix of integers 0,1,2,3 for <,>,v,^ respectively.
Try it online.
Explanation:
import java.util.*;        // Required import for Set, HashSet, and TreeSet
m->{                       // Method with integer-matrix parameter and no return-type
  var L=new HashSet<Set>();//  Create a Set of Sets `L`, starting empty
  int l=m.length,          //  Set `l` to the dimensions of the input-matrix
      R=l*l,               //  Index integer `R` to loop over the cells
      r,c,                 //  Temp-integers `r,c` for the row and column
      d;                   //  Temp-integer `d` for the direction
  for(Set S;               //  Temp Set `S`, starting uninitialized
      R-->0                //  Loop `R` in the range (`l*l`, 0] over all cells:
      ;                    //     After every iteration:
       S.add(r==R/l&c==R%l?//      If `r,c` is still cell `R`:
              -1           //       Add -1 to Set `S`
             :             //      Else:
              -2),         //       Add -2 instead
       L.add(S))           //      And then add `S` to Set `L`
      for(S=new TreeSet(), //    Set `S` to a new empty sorted-Set
          r=R/l,c=R%l;     //    Set `r,c` to cell `R`
          S.add(r*l+c)     //    Add `r,c` as cell-index to Set `S` every iteration
                           //    and continue looping as long as it wasn't in `S` yet:
          ;                //      After every iteration:
           r=(r-(d-d%3*d)/2//       If `d` is 3:
                           //        Go to the cell above
                           //       Else-if `d` is 2:
                           //        Go to the cell below
              +l)%l        //       Adjust row wraparounds when we're out of bounds
           c=(c-(d<2?1-2*d:0)
                           //       Else-if `d` is 0:
                           //        Go to the cell left
                           //       Else-if `d` is 1:
                           //        Go to the cell right
             +l)%l         //       Adjust column wraparounds when we're out of bounds
        d=m[r][c];         //     Set `d` to the current direction of cell `r,c`
  // After we've determined all paths per cell:
  for(Set z:L){            //  Loop `z` over each path of Set `L`:
    if(z.remove(-1)){      //   Remove a -1 (if present),
                           //   and if it indeed contained a -1 (infinite path):
      c=0;                 //    Use `c` as counter, starting at 0
      for(Set q:L)         //    Inner loop `q` over each path of Set `L`:
        if(q.remove(-2)){  //     Remove a -2 (if present),
                           //     and if it indeed contained a -2 (tributary path):
          if(q.containsAll(z))
                           //      If `q` contains all values of `z`:
            c++;           //       Increase the counter by 1
          q.add(-2);}      //      Add -2 back to `q` for the next iteration of loop `z`
      System.out.println(  //    Print with trailing newline:
        z.size()           //     The size of path `z`
        +","+c);}}}        //     and the counter (comma-separated)

Nice.  Just out of curiosity, why did you decide to do this one in Java?

@Jonah The languages I'm most skilled in are Java, 05AB1E, and Whitespace. And usually when I deem a challenge relatively hard, I will use Java. I'll try it later on in 05AB1E as well, but 05AB1E isn't too great for matrices or checking/going to a certain neighbor in a matrix. But we'll see when I have some time to work on it how well it really does I guess. ;)

K (ngn/k), 99 81 bytes
thanks @bstrat for -18 bytes!
{l,'(#'.c)-l:#'!c:={x@<x:(x?a@*|x)_x}'{?x,a@x}/'a::s/s!'(+(,/-:\=2)@,/x)+!s:2##x}

Try it online!
down,right,up,left in the input are encoded as 0 1 2 3

Sorry, function argument should only be the matrix configuration

@DomenicoModica i assumed dimensions+data is a valid representation of a matrix. i'll fix later.

fixed. it's a single arg now - the matrix split into rows.

Perfect. Awesome answer!

Jelly,  44  41 bytes
-3 as the grid is guaranteed to be square.
ŒṪœịı*ÆiƊ+⁸ʋƬ⁺⁹ɗ€⁸%LḞQ€LÞḢṢƲ€¹ƙ$Ẉ€µḟṂLṭṂ)

A monadic Link accepting a list of lists of integers which yields a list of lists of integers (each being a [loop_size, tributary_count] - i.e. \$(n_i, t_i)\$).
The directions in the input are:
^  2
>  1
V  4
<  3

Try it online!
How?
ŒṪœịı*ÆiƊ+⁸ʋƬ⁺⁹ɗ€⁸%L...  - Link: list, X
ŒṪ                       - truthy multi-dimensional indices -> [[1,1],[1,2],...,[h,w]]
                €        - for each:
               ɗ         -   last three links as a dyadic chain:
              ⁹          -     use chain's right argument as right argument
            Ƭ            -     collect up until no change occurs with:
           ʋ             -       last four links as a dyadic chain:
  œị                     -         multi-dimensional index into X
        Ɗ                -         last three links as a monadic chain:
    ı                    -           square root of -1
     *                   -           exponentiate
      Æi                 -           [real part, imaginary part] -> move deltas
          ⁸              -         chain's left argument -> the current position
         +               -         add together -> the new position
             ⁺           -     repeat the Ƭ-collection, use the entire result
                   L     - length of X
                  %      - modulo -> making all results have the same domain

...ḞQ€LÞḢṢƲ€¹ƙ$Ẉ€µḟṂLṭṂ) - ...continued
   Ḟ                     - floor (we had a mix of ints and floats, but ƙ uses
                                  Python's repr, this makes them all ints again)
    Q€                   - deduplicate each
              $          - last two links as a monadic chain:
            ¹ƙ           - group by:
           €             -   for each
          Ʋ              -     last four links as a monadic chain:
       Þ                 -       sort by...
      L                  -       length
        Ḣ                -       head
         Ṣ               -       sorted
               Ẉ€        - length of each of each
                 µ     ) - for each:
                   Ṃ     -   minimum -> loop length
                  ḟ      -   filter discard (keeping only tributary lengths)
                    L    -   length -> number of tributaries
                      Ṃ  -   minimum -> loop length
                     ṭ   -   tack -> [loop length, number of tributaries]

Python 2, 250 247 235 bytes
Thanks Arnauld for pointing out that the grid is guaranteed to be square, saving 12 bytes!

G=input()
n=len(G)
N={}
T={}
t=0
exec"j=t%n;i=t/n;A=[]\nwhile(i,j)not in A:A=[(i,j)]+A;d=G[i][j];i+=d/3-1;j+=d%3-1;i%=n;j%=n\nk=A.index((i,j))+1;x=min(A[:k]);N[x]=k;T[x]=T.get(x,[])+A[k:];t+=1;"*n*n
for x in N:print N[x],len(set(T[x]))

Try it online!
Takes input as a 2D list from STDIN, where up, right, down, left are encoded as the integers 1, 5, 7, 3 respectively.
For each cell in the grid, the program follows the directions starting from that cell until a loop is found. The loop length is stored in the dictionary N, and the list of tributary cells is stored in the dictionary T. The keys for both dictionaries are the min indices of each loop.

JavaScript (Node.js), 196 bytes if width=height
m=>m[Q='flatMap'](U=(y,I)=>y[Q]((x,j)=>U[T=[...m+0,Y=m.length,i=I][Q](_=>0+[j=(c=m[i][j]-2,j+Y-~c%2)%Y,i=(i+Y+c%2)%Y])[k=0,Q](S=c=>(S[c]=-~S[c])==2&&++k&&c).sort()]?(++U[T][0],[]):[U[T]=[1-k,k]]))

Try it online!
JavaScript (Node.js), 205 bytes
m=>m[Q='flatMap'](U=(y,I)=>y[Q]((x,j)=>U[T=[...m+0,Y=m[W='length'],X=m[W],i=I][Q](_=>0+[j=(c=m[i][j]-2,j+Y-~c%2)%Y,i=(i+Y+c%2)%Y]).sort().filter(S=c=>(S[c]=-~S[c])==2)]?(++U[T][1],[]):[U[T]=[k=T[W],1-k]]))

Try it online!
Ungolfed version
m=>m.flatMap(
  U=(y,I)=>y.flatMap(
    (x,j)=>
      U[
        T=[...m+0,Y=m.length,X=y.length,i=I].map(_=>(
          c=m[i][j],c%2?(i=(i+Y-2+c)%Y):(j=(j+X-1+c)%X),
          i*X+j
        )).sort().filter((c,k,S)=>S[k-1]!=c&S[k+1]==c)
      ]?(++U[T][1],[]):[U[T]=[k=T.length,1-k]]
  )
)

Try it online!

The grid is guaranteed to be square, so you don't need X.

@Arnauld Beat you considering rectangle

J, 78 bytes
[:(#~1<{."1)@((=([,-~)&(+/)0=|)"{~~.)@,](]*.[{"p..0|:((,-)=0 1)|.])^:_ p:@i.@$

Try it online!
How it works
We map each index to the corresponding prime p:@i.@$:
 2  3  5  7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97

Then shift this board by the 4 directions ((,-)=0 1)|.]), and calculate the least common multiple between the tile x and the direction x is heading ]*.[{"p..0|:. We do this until the board does not change anymore (…)^:_:
461677248802 62985        20995    3162172937  3162172937
         221   221         4199 2109169348979 91703015173
        6851  8177       172159       7402837      321997
      363103  4661     10501699    3162172937  3162172937
230838624401  4661 262460353771    3162172937  3162172937

For each unique ~. number we can then count how often it occures and how many other tiles it divides: = …&(1#.,) 0=|. We need the first number and the difference for the result: ([,-~):
…
6  5
2 10
1  5
…
2  0
1  0

We then take only the ones where the first column is greater than 1 (#~1<{."1):
6  5
2 10
2  0

R 435 414 395 390 bytes
Entering the excursion map as a matrix, e.g.
n=3;M=matrix(sample(1:4,n^2,rep=T),n)

where 1,2,3,4 stand for down, up, right, and left, the following heavy-going code produces rows of lengths and tributaries for the different loops
j=cbind;l=sum;a=apply
m=l(!!M);n=m^.5
g=function(A,r=M[A])A+c((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
I=c()
for(i in d<-1:n)I=rbind(I,j(i*d/d,d))
for(t in b<-1:m)I=g(I)
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m)
for(t in b)K[b+m*p(I<-g(I))]=1
s=o=a(u<-unique(K),1,l)
for(k in 1:l(!!s))s[k]=l(!a(!!sweep(K,2,u[k,],'-'),1,l))
j(o,s-o)

Try it online!
Some comments
m=l(!!M);n=m^.5 #m=n^2
#moving all points in the square by the corresponding moves in M
g=function(A,r=M[A])A+cbind((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
#matrix of the (i,j) coordinates for all points in the square
I=c()#NULL
for(i in 1:n)I=rbind(I,cbind(rep(i,n),1:n))
#move long enough to remove transient points
for(t in b<-1:m)I=g(I)
#turns 2D coordinates into a single integer
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m) #matrix of visited coordinates
for(t in b)K[b+m*p(I<-g(I))]=1
#loop length (o) and associated number of transients (s)
s=o=apply(u<-unique(K),1,sum)
#sum over all loops (length(o))
for(k in 1:sum(!!s))s[k]=sum(!a(!!sweep(K,2,u[k,],'-'),1,sum))
cbind(o,s-o)

Now, I spent too much time on this code already but I fear the parts
I=c()
for(i in 1:n)I=rbind(I,cbind(rep(i,n),1:n))

creating the matrix of all starting coordinates and
p=function(i)i[,1]+n*i[,2]-n-1

switching from the coordinates to a single index could be further code-golfed!

Scala, 415 bytes
415 bytes, maybe more. It can be golfed much more.
Port of @Kevin Cruijssen' Java 10 answer in Scala.

Golfed version. Try it online!
val L=new HashSet[Set[Int]]()
val l=m.length
val R=l*l
for(i<-0 until R){var r=i/l
var c=i%l
val S=new TreeSet[Int]()
do{S.add(r*l+c)
val d=m(r)(c)
r=(r-(d-d%3*d)/2+l)%l
c=(c-(if(d<2)1-2*d else 0)+l)%l}while(S.add(r*l+c))
if(r==i/l&&c==i%l)S.add(-1)else S.add(-2)
L.add(S)}
for(z<-L.asScala){if(z.remove(-1)){var c=0
for(q<-L.asScala){if(q.remove(-2)){if(q.containsAll(z))c+=1
q.add(-2)}}
println(s"${z.size},$c")}}

Ungolfed version. Try it online!
import java.util.{HashSet, TreeSet, Set}
import scala.collection.JavaConverters._

object Main {

  trait N {
    def c(m: Array[Array[Int]]): Unit
  }

  val n: N = new N {
    def c(m: Array[Array[Int]]): Unit = {
      val L = new HashSet[Set[Int]]()
      val l = m.length
      val R = l * l

      for (i <- 0 until R) {
        var r = i / l
        var c = i % l
        val S = new TreeSet[Int]()
        do {
          S.add(r * l + c)
          val d = m(r)(c)
          r = (r - (d - d % 3 * d) / 2 + l) % l
          c = (c - (if (d < 2) 1 - 2 * d else 0) + l) % l
        } while (S.add(r * l + c))
        if (r == i / l && c == i % l) S.add(-1) else S.add(-2)
        L.add(S)
      }

      for (z <- L.asScala) {
        if (z.remove(-1)) {
          var c = 0
          for (q <- L.asScala) {
            if (q.remove(-2)) {
              if (q.containsAll(z)) c += 1
              q.add(-2)
            }
          }
          println(s"${z.size},$c")
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
    test(Array(Array(3, 1, 2, 1, 3), Array(1, 0, 0, 1, 3), Array(3, 3, 3, 0, 1), Array(3, 2, 3, 2, 0), Array(0, 3, 1, 2, 3)))
    test(Array(Array(1, 2), Array(3, 0)))
    test(Array(Array(1, 2, 2), Array(3, 0, 0), Array(1, 0, 2)))
  }

  def test(m: Array[Array[Int]]): Unit = {
    println(s"Input: ${m.map(_.mkString(",")).mkString("Array(", ", ", ")")}")
    println("Pretty-printed: ")
    prettyPrint(m)
    println("Output: ")
    n.c(m)
    println()
  }

  def prettyPrint(m: Array[Array[Int]]): Unit = {
    for (r <- m) {
      println(r.map(v => "<>v^".charAt(v)).mkString)
    }
  }
}


text:
Who Took My Toilet Paper?
You step into the restroom, and notice that the toilet paper has missing! It occurs to you that someone had stolen it. Strangely enough, the first thing you would like to know is the amount of toilet paper the thief stole.
Task
You are given three integers \$ I \$, \$ R \$, and \$ G \$, the details of the toilet paper, where \$ I \$ is the radius of the inner ring, \$ R \$ is the number of rotations, and \$ G \$ is the thickness. The task is to return/output out the length of the toilet paper.
The toilet paper can be viewed as an Archimedes' spiral, which starts at coordinate \$ (I, 0) \$, and rotates a total of \$ R \$ times in the counterclockwise direction, with a distance of \$ G \$ between each gap.
More formally, the Archimedes' spiral here is defined as the set of all points whose locations over time move away from the origin counterclockwise at a constant speed and with constant angular velocity.
Due to potential precision issues, your answer will be judged correct if they pass all the sample cases below when rounded to \$ 1 \$ decimal place.
In the diagram below, \$ I = 5 \$, \$ R = 3 \$, \$ G = 4 \$, and the total length is \$ \approx 207.7 \$.

Test Cases
I R G -> answer rounded to 1 decimal place (note that the answer does not have to be rounded)
0 1 1 -> 3.4
5 3 4 -> 207.7
12 9 2 -> 1187.7

This is code-golf, so the shortest code in bytes wins!

You probably want to explicitly mention somewhere that the output should be the length of the spiral

@mathjunkie Added

Are you sure the answer to the last test case (12, 999, 2) is right?  Unless I'm misunderstanding something, the answer should be much larger than 4021.5 (a fast approximation gives a value around 6.35 million).

@MitchellSpector I get 6.35 million as well

@MitchellSpector Thanks for bringing this up, it's fixed now (although I can't guarantee the precision is correct).

Are there any bounds on the input values? I ask because the exact analytic formula can be approximated in various ways including by its Taylor expansion, and whether it's accurate within 0.1 strongly depends on how large the inputs are. As they get larger, the relative precision needed becomes more and more restrictive.

@xnor Good point, I have clarified it in the question now.

Thanks, the bounds are helpful. I'm worried now they are too loose now though. Using the approximation of 2*pi*r*(i+r*g/2) where we estimate the roll as r circles in the middle gives error to the test cases of 0.24, 0.39, and 0.15. While this is more than 0.1, it's only a few times more, so when I test my expressions to approximating for this error on the test cases, I'm not sure if I'm overfitting on them. I think a much larger set of test cases would be good, maybe even something like all values from 1 to 15 for each input, but maybe it's too late because this can affect answers.

All existing answers fail to tell who took your toilet paper... Just saying... :p

Hey, since you could not find an image with integer I,G,R, here's one for your second test case: https://i.imgur.com/rY1Av2Y.png
Generated with this very simple Matlab script (Matlab is not on TIO unfortunately)

@Leo Thank you, I'll take it!

J, 66 bytes
1#.2|@-/\1e3&((-:@[%:_1:)^[:i.1+[*0{])((*{:)+[*(1{])*1e3%~i.@#@[)]

Try it online!
This could be golfed more, but I'm putting it away for now.
Instead of taking an analytic approach I am using complex number arithmetic to break the spiral down into 1000 straight line segments per rotation, and then summing those segments.
I find the 500th root of -1, and keep multiplying it by itself to rotate it and get an approximation to the next spiral point.
Because the spiral also moves outward, we need to take the new vector, normalize it, multiply the normal vector by 1/1000 of the thickness, and then add that little correction to the new vector.
Conceptually, we're doing something similar to approximating a circle's circumference with the short sides of many triangles.

The idea is simple, but the golf part of it boils down to boring bookkeeping and argument parsing which isn't worth going into.  In theory the realization of this method could be a lot shorter.

Python 3, 93 83 76 71 bytes
-9 bytes if we don't explicitly round the results
-1 byte after changing n to 9999
-7 bytes thanks to dingledooper who rearranged the operations
-5 bytes thanks to xnor who changed the square root calculations to taking an absolute value of a complex number
lambda i,r,g:sum(abs(1j+6.283*(t/n+i/g))for t in range(n*r))/n*g
n=9999

Try it online!
This is a straightforward numerical integration of a spiral length, without using any imports. n is chosen so that the results are sufficiently precise.
The length of a spiral is a sum $$L = \sum_{t=1}^n L_t,$$ where Lt is calculated as a hypothenuse in a roughly right triangle with sides $$\frac{2\pi}{n} r_t = \frac{2\pi}{n}\left(i+\frac{gt}{n}\right)$$ and $$r_{t+1}-r_t = \frac{g}{n}$$.

Here's an improvement to 76 bytes by rearranging.

And taking the /n outside cuts a space thanks to Python's lax parsing:Try it online!

Using complex numbers for 71: Try it online!

Python 3, 83 bytes
Thanks @xnor for finding some important approximation, notably h(t)=t*t+log(2*t+.5)
lambda i,r,g:g/2/T*(h(T*(i/g+r))-h(T*i/g))
h=lambda t:t*t+99*(2*t+.5)**.01
T=6.2832

Try it online!
The same solution as below, but uses several approximations:

\$2\pi \approx 6.2832\$
\$ \theta\sqrt{1+\theta^2}+\sinh^{-1}\theta + C \$
\$ \approx \theta^2 + \ln(2\theta+0.5) +C \$
\$ \approx \theta^2 + 99(2\theta+0.5)^{0.01} + C\$

"Exact" solution
Python 3, 104 100 bytes
-3 bytes thanks to @mathjunkie!
-1 byte thanks to @xnor!
lambda i,r,g:g/4/pi*(h(2*pi*(i/g+r))-h(2*pi*i/g))
from math import*
h=lambda t:t*hypot(t,1)+asinh(t)

Try it online!
This uses the exact formula. Maybe a good Taylor series approximation can be shorter.
The formula for the length of the spiral is:
$$ L=\frac{G}{2\pi} \int_{\frac{2\pi I}{G}}^{\frac{2\pi(I+GR)}{G}}\sqrt{1+\theta^2}d\theta $$
and the formula for the integral is:
$$ \int \sqrt{1+\theta^2}d\theta=\frac{1}{2}\left(\theta\sqrt{1+\theta^2}+\sinh^{-1}\theta \right) $$

Which functions here require numpy? Can you not use the math library and the shorter asinh function?

archsinh(x) is ln(x+sqrt(1+x*x)), which makes me wonder if you can approximate ln and pi accurately enough to not need any imports.

@mathjunkie I just googled "Python inverse sinh", and numpy was the first result that popped up. Completely forgot about math :)

Tricks for taking the difference of two parallel expressions might come in useful here.

Since you're using math, there's hypot(t,1) for (1+t*t)**.5.

It looks like h(t)=t*t+log(2*t+.5) is a good enough approximation to get within 0.1 on the test cases, though I might be overfitting a bit here. I'm ignoring the constant term since you're taking the difference of two values of h. Try it online!

And here's a cleaner (ungolfed) form of the above: Try it online! I'd golf my own answer, but I'll be busy from now, so I'll just leave it for you :)

@xnor Thanks a lot for all the suggestions! I finally get rid of the math import, by approximating $ln(x)$ with $ax^{1/a}-a$, where $a$ is a large constant.

Python 3, 60 bytes
lambda I,R,G:6.2831*R*(I+R*G/2)+G*8*((1+R/(I/G+.05))**.01-1)

Try it online!
An approximate method. Approximates log without an import using Surculose Sputum's nifty approximation
This approximation is quite accurate, achieving within 0.02 on all the test cases and within 0.1 on all single-digit inputs. It's possible to use looser approximations that work for all the test cases, but I'm not sure at what point this is overfitting. In the extreme, hardcoding the outputs would be very short. So, I'd like to exclude this answer from my bounty on outgolfing me since I'm not clear what golfs what be valid.
The first summand \$2\pi(I+RG/2)R\$ is what we get if we approximate the toilet paper spiral as instead being concentric circles with the same inner radius, thickness, and number of turns. The average of the circumferences of these \$R\$ circles is \$2\pi(I+RG/2)\$. This is \$2\pi\$ times the average of their radii of \$I+RG/2\$, or equivalently the average of the inner and outer radius.
The above approximation is already pretty good for the test cases, with error within 0.4. The second term approximates the additional circumference due to the spiral moving radially, rather than just tangentially as circles do. I got this from looking at the integral for arc length suggested by svavil. We then get rid of approximate log without an import using Surculose Sputum's approximation The constant of 8 is an approximation for \$100/(4\pi)\$, with 100 being inverse of the exponent 0.01 chosen for the log approximation. The +0.05 fixes an approximation failing near \$I/G=0\$, which would otherwise cause a divide-by-zero. I originally calculated the desired values as \$1/(4\pi)=0.08\$, but heuristically 0.05 does better.

C (gcc) -lm -m32, 129 120 117 114 bytes
#define F float
F i(F u,F g){F s=hypot(u,g/=6.2832);return(u*s/g+g*log(s+u))/2;}
#define f(I,R,G)i(I+G*R,G)-i(I,G)

Try it online!
5 bytes off thanks to ceilingcat (by using the hypot library function).
4 bytes off thanks to dingledooper (who suggested using a typedef to shorten the float declarations -- I ended up using a macro instead to implement the same idea).
3 bytes off by using an approximation to \$2\pi\$ that's sufficient for the accuracy required by the challenge.
3 more bytes thanks to ceilingcat (turning f from a function into a macro).
The auxiliary function i computes the appropriate indefinite integral, and then f computes the desired definite integral by evaluating the indefinite integral at the two endpoints and subtracting.

05AB1E, 23 bytes
4°©*Ý*®/+nŽ›Ñ₄/*²n+tO®/

Port of @svavil's Python answer (their revision without complex number), so make sure to upvote them!
Input-order as r,g,i.
Try it online or verify all test cases.
Explanation:
4°                      # Push 10**4: 10000
  ©                     # Store it in variable `®` (without popping)
   *                    # Multiply it by the first (implicit) input `r`
    Ý                   # Push a list in the range [0, 10000r]
     *                  # Multiply each value by the second (implicit) input `g`
      ®/                # Divide each by `®`
        +               # Add the third (implicit) input `i` to each value
         n              # Take the square of that
          Ž›Ñ           # Push compressed integer 39478
             ₄/         # Divide it by 1000: 39.478
               *        # Multiply it by each value
                ²       # Push the second input `g` again
                 n      # Square it
                  +     # And add it to each value as well
                   t    # Take the square-root of each value
                    O   # Sum everything together
                     ®/ # And divide it by `®`
                        # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž›Ñ is 39478.

Fwiw I have a suspicion my method might be sub 20 bytes in the hands of a skilled 05AB13 programmer

@Jonah Perhaps, but unfortunately I can't read J and couldn't really understand how your explanation would translate into code to be completely honest. I also see you've mentioned complex numbers at the start, which 05AB1E lacks. I understood your approach in general, but I have no idea what it looks like in (pseudo)-code. I can read Python, JavaScript, C, etc. a bit which helps in making ports sometimes, but I can't really read J (just like you probably wouldn't be able to read my 05AB1E answers if I would skip the explanation). I'm also not too skilled in most mathematics in general tbch..

Ah ok Id add a more detailed explanation but without complex numbers it wouldn’t do any good.  I didn’t realize that

@Jonah Yeah, it's unfortunate, but 05AB1E lacks complex/imaginary numbers I'm afraid. I'm sure it's possible to use calculations to mimic them, since I've seen it a few times before (here and here for example). It's one of 05AB1E's weaknesses, in addition to indexing and manipulation of matrices; lack of regex; date-builtins; etc. There are definitely alternatives for it, like what I did here, but it's usually pretty costy. ;)

SageMath, 70 bytes
lambda I,R,G:N(G/2/pi*(sqrt(1+x^2)).integral(x,2*pi*I/G,2*pi*(I/G+R)))

Try it online!
How
Uses the formula for the length of the spiral:
$$ L=\frac{G}{2\pi} \int_{\frac{2\pi I}{G}}^{\frac{2\pi(I+GR)}{G}}\sqrt{1+\theta^2}d\theta $$
from Surculose Sputum's Python answer.