text:
The Spain license plates game

This question is based on a question I asked in Spanish language. Yes, I asked for an algorithm in Spanish Language. :)

In Spain, current license plates have this pattern:

1234 XYZ

where XYZ are three consonants taken from the full set of Spanish consonants (except the 'Ñ', I think).
Sometimes, when traveling with my wife, we use to play a game. When we see a license plate, we take its three consonants and try to form a word that contains those three consonants, appearing in the same order as in the license plate. Examples (in Spanish):
BCD
    BoCaDo (valid)
    CaBezaDa (not valid)
FTL
    FaTaL (valid)
    FLeTar (not valid)
FTR
    FleTaR (valid, wins)
    caFeTeRa (valid, loses)

The winner is the one who uses the least number of characters, as you can see in the last example.
The challenge
Write the shortest program or function that receives a list of words and a set of three consonants and finds the shortest word in the list that contains the three consonants in the same order. For the purposes of this game, case does not matter.

The input for the word list (first parameter) will be an array of your language string type. The second parameter (the three consonants) will be another string. If it's better for your language, consider the string with the three consonants the last item of the whole list of parameters. The output will be another string.
The words in the word list won't be invented or infinite words, they will word that appear in any standard dictionary. If you need a limit, suppose no word in the word list will be longer than 50 characters.
If there are several words with the same lenght that could be the valid answer, you can return any one of them. Just make sure you return just one word, or an empty string if no words match the pattern of three consonants.
You can repeat consonants in the group, so valid inputs for the three consonants are both FLR and GGG.
The Spanish consonants are exactly the same as English, with the addition of the "Ñ". The vowels are the same with the adition of the stressed vowels: "áéíóúü". There won't be any other kind of marks such as "-" or "'".
You can suppose the case will always be the same in both the word list and the three consonants.

If you want to test your algorithm with a real collection of Spanish words, you can download a file (15.9 MB) from Dropbox with more than a million words.
Test cases
Input: 'psr', {'hola' 'repasar' 'pasarais' 'de' 'caída' 'pequeñísimo' 'agüeros'}
Output: 'repasar'

Input: 'dsd', {'dedos' 'deseado' 'desde' 'sedado'}
Output: 'desde'

Input: 'hst', {'hastío' 'chest'}
Output: 'chest'

This is code-golf, so may the shortest program that helps me to always beat my wife wins! :)

How long are the words in the word list guaranteed to be?

@Neil Just suppose they come from a standard dictionary, there won't be invented, infinite words. I don't know what would be the longest word in English or Spanish. If you need a limit, just consider no word will be longer than 50 characters.

In actual license plates, letter Q  is not allowed either; and W is, although not a proper Spanish letter

@Arnauld yes, you can suppose that words will always be uppercase or lowercase.

You should add some simple test cases in your text, with input and output

Sorry, I meant the length of the words, not the count of them.

May we assume the words in the list and the three letters will be all in one case?

Are we guaranteed to find at least one matching word for the given consonants? If not, what's the expected behavior?

@Arnauld no, you cannot suppose that there will always be a match. If not, just return the empty string (question edited, sorry for that).

@JonathanAllan yes, you can assume that.

A test case like 'psr', {'hola' 'repasar' 'pasarais' 'de' 'caída' 'pequeñísimo' 'agüeros'} may be interesting. My answer failed for that one, because it was only findind the first occurrence of each letter in a word

@LuisMendo W has been a Spanish letter since 1969.

@walen That's why I said "proper" :-) It exists in Spanish, but is feels foreign

05AB1E, 10 8 bytes
Saved 2 bytes thanks to Leo
ʒæså}éR`

Try it online!
Explanation
ʒ         # filter list, keep only members for which the following is true
  så      # input is in the
 æ        # powerset of the current word
    }     # end filter
     é    # sort by length
      R   # reverse
       `  # push separately (shortest on top)

I would have used head at the end saving a byte but that would output an empty list if there isn't a match.

3ù #keep only those of length 3 why do you need this?

@Leo: I don't, that was silly of me. Thanks :)

PHP, 111 bytes
$y=array_map(str_split,preg_grep("#".chunk_split($_GET[1],1,".*")."#",$_GET[0]));sort($y);echo join($y[0]??[]);

Try it online!

The number plate should be a string, not an array. But you don´t need the modifier.

@Titus fixed !!

You can suppose the case will always be the same in both the word list and the three consonants. - no need for the regex modifier. Have you tried wordwrap instead of join(str_split())?

@Titus good idea

MATL, 30 29 bytes
xtog!s2$S"1G!'.*'Yc!@gwXXn?@.

Try it online!
Explanation
x         % Implicitly take first input (string with three letters). Delete.
          % Gets copied into clipboard G, level 1
t         % Implicitly take second input (cell array of strings defining the
          % words). Duplicate
o         % Convert to numeric array of code points. This gives a matrix where
          % each string is on a row, right-padded with zeros
g         % Convert to logical: nonzeros become 1
!s        % Sum of each row. This gives the length of each word
2$S       % Two-input sort: this sorts the array of strings according to their
          % lengths in increasing order
"         % For each word in the sorted array
  1G      %   Push first input, say 'xyz'
  !       %   Transpose into a column vector of chars
  '.*'Yc  %   Concatenate this string on each row
  !       %   Transpose. This gives a char array which, when linearized in
          %   column-major order, corresponds to 'x.*y.*z.*'
  @g      %   Push corrent word
  w       %   Swap
  XX      %   Regexp matching. Gives a cell array with substrings that match
          %   the pattern 'x.*y.*z.*'
  n       %   Number of matchings
  ?       %   If non-zero
    @     %     Push cell array with current word, to be displayed as output
    .     %     Break loop
          %   Implicit end (if)
          % Implicit end (for)
          % Implicitly display stack

Jelly,  12 11  10 bytes
ŒPċðÐfLÞḣ1

A full program that accepts a list of lists of lowercase characters (the words) and a list of lowercase characters (the letters) and prints the first of the shortest words which contain a sub-sequence equal to the letters (or nothing if none exist).
Try it online!
How?
ŒPċðÐfLÞḣ1 - Main link: words; characters
   ðÐf     - filter keep words for which this is truthy:
ŒP         -   the power-set (all sub-sequences of the word in question)
  ċ        -   count (how many times the list of characters appears)
           - ...note 0 is falsey while 1, 2, 3, ... are truthy
       Þ   - sort by:
      L    -  length
        ḣ1 - head to index 1 (would use Ḣ but it yields 0 for empty lists)
           - implicit print (smashes together the list of lists (of length 1))

If I understand your explanation correctly, this would refuse a word like "borracho" for a sequence of consonants of "brc", because "brc" is not a substring of "brrc"

@Leo ah, yes good catch I think that it would fail...

@Leo - well it's fixed (checks "exists in" for the entire power-set of each word) but it may not be fully golfed...

Pyth - 22 21 19 12 11 bytes
h+f/yTQlDEk

-1 Thanks to Maltysen.
Takes 2 lines as input.  1st is the 3-letter string (lowercase), and the 2nd is a lowercase list of words.
Try it here
Explanation:
h+f/yTQlDEk
       lDE   # Sort word list by length
  f          # Filter elements T of the word list...
    yT       # by taking the powerset...
   /  Q      # and checking whether the 3-letter string Q is an element of that.
 +        k  # Add empty string to the list (in case no results found)
h            # And take the first result (the shortest)

Old 19-byte solution:
h+olNf/-T"aeiou"QEk

@JonathanAllan:  Fixed!  Thanks for pointing that out.

@JonathanAllan:  It looks like he edited the question to clarify that it should return an empty string in that case.  I've edited my answer accordingly.

We have a sort-by meta operator in D, so u can replace olN with lD

Brachylog v2, 11 bytes
tlᵒ∋.&h⊆.∨Ẹ

Try it online!
Function submission. (The TIO link has a command-line argument to run a function as though it were a full program.)
Explanation
Just a direct translation of the specification again…
tlᵒ∋.&h⊆.∨Ẹ
t            The last element of {standard input}
   ∋.        contains the return value as an element
     &       and
      h      the first element of {standard input}
       ⊆.    is a subsequence of the return value
         ∨   alternate behaviour if no solution is found:
          Ẹ  return empty string
  ᵒ          tiebreak override: favour answers that have a low
 l           length

You can actually almost answer with h⊆.&t∋ – swapping the evaluation order means that Brachylog will pick the shortest answer by default (as the first constraint it sees is ⊆, which has the rather convenient "shortest" as a default tiebreak) – but in that case, Brachylog's evaluation algorithm would unfortunately go into an infinite loop if the answer is not actually found. So almost half the answer is dedicated to handling the case of there being no appropriate answer. Even then, the lᵒ tiebreak override (which is technically a sort, making use of ∋'s default tiebreak of preferring elements nearer the start of the list) is only two bytes; the other three come from the need to output an empty string specifically when the output is not found, as opposed to Brachylog's default "no solutions" sentinel value (because the final . would be implicit if we didn't have to follow it with ∨).
Interestingly, there's a feature that was previously implemented in Brachylog that would have saved a byte here. At one point, you could extract elements from the input argument using ?₁, ?₂, etc. syntax; that would allow you to rearrange the program to tlᵒ∋.⊇?₁∨Ẹ, which is only 10 bytes. Unfortunately, the implementation that was used didn't actually work (and caused many otherwise working programs to break), so it was reverted. You can think of the program as being "conceptually" 10 bytes long, though.

Haskell 129 125 74 bytes
import Data.List
l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0

CREDIT to @nimi

You can replace the rightmost map and the filter with a list comprehension. As you already have Data.List in scope, you can use sortOn length and pick the head to find the element with minimal length. Finally, make y an infix function. All this makes f and k superfluous: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0.

you're right! I just started golfing! Thanks!

One more: if you switch the import to Data.Lists, you can use argmin instead of sortOnand save the !!0: l#w=argmin length[...]. Data.Lists has many nice functions

JavaScript (ES6), 77 75 72 bytes
Takes the 3 consonants c and the list of words l in currying syntax (c)(l). Both inputs are expected in the same case.
c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

Test cases

let f =

c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

console.log(f('psr')(['hola', 'repasar', 'pasarais', 'de', 'caída', 'pequeñísimo', 'agüeros'])) // 'repasar'
console.log(f('dsd')(['dedos', 'deseado', 'desde', 'sedado'])) // 'desde'

c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`)) for 72, I think

@LarsW Indeed, thanks! However I've chosen another approach to comply with the new rule: or an empty string if no words match the pattern of three consonants.

Perl, 53 bytes
48 bytes code + 5 for -paF.
$"=".*";($_)=sort{$a=~y///c-length$b}grep/@F/,<>

This takes advantage of the fact that lists interpolated into the m// operator utilise the $" variable which changes the initial input string from psr to p.*s.*r which is then matched for each additional word and is sorted on length.
Try it online!

If I insert "adsd" into your list, your program fails to find it. The first character to find does not need to be the first in the word.

@CarlosAlejo The input needs a trailing newline, works ok then: Try it online!. That did catch me off guard though, as the <<< operator adds that in for me at command line!

R, 101 bytes
First time golfing!  I'm sure this can be condensed somehow
Takes the string x and a character vector y of possible inputs
w=pryr::f((b=y[sapply(gsub(paste('[^',x,']'),'',y),function(l)regexpr(x,l))>0])[which.min(nchar(b))])

Try it online!
Edit: My version was 135, thanks Scrooble for the -34!

Welcome to PPCG! This looks like a snippet where the input is in hardcoded variables. Answers need to be either full programs or callable functions. You can have a look at this (or other R answers) for possible I/O methods.

Retina, 58 bytes
O#$^`¶.+
$.&
s`^((.)(.)(.).*¶(?-s:(.*\2.*\3.*\4.*)))?.*
$5

Try it online! Takes the three consonants on one line and then the list of words on all subsequent lines. Explanation: O sorts the list ¶.+ excluding the first line # numerically $ keyed by $.& length. A match is then sought for a line that includes the three consonants in order. If a suitable line exists than the last, i.e. shortest, such line becomes the output, otherwise the output is empty. The ?-s: temporarily turns off the effect of s` so that only one line is matched.

I can't decide if those are three belly buttons or three breasts.

@CarlosAlejo Are you thinking of Eccentrica Gallumbits by any chance?

I was thinking of the alien from Total Recall, but Eccentrica could be also an option... :)

@CarlosAlejo Apparently Mary is a homage to Eccentrica Gallumbits.

Pip, 17 bytes
@:qJ`.*`N_FI#_SKg

Takes the word list as command-line arguments, and the consonants from stdin.
Try it online!
Explanation
                   g is list of cmdline args (implicit)
              SKg  Sort g using this key function:
            #_      Length of each item (puts shortest words first)
          FI       Filter on this function:
  q                 Line of input
   J`.*`            joined on regex .* (turns "psr" into `p.*s.*r`)
        N_          Count regex matches in item (keeps only words that match)
@:                 Get first element of result (using : meta-operator to lower precedence)
                   If the list is empty, this will give nil, which results in empty output

Java 8, 132 126 bytes
s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}

-6 bytes thanks to @Nevay.
Explanation:
Try it online.
s->a->{              // Method with two String-array parameters and String return-type
  String r="";       //  Result-String, starting empty
  for(String x:a)    //  Loop over the words
    r=(x.length()<r.length()
                     //   If a word is smaller than the current `r`,
      |r.isEmpty())  //   or `r` is still empty
      &x.matches(r.format(".*%s.*%s.*%s.*",s))?
                     //   And if the word is valid
       x             //    Change `r` to the current word
      :              //   Else:
       r;            //    Leave `r` the same
  return r;}         //  Return the result

126 bytes: s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}

Python, 77 bytes
import re
lambda s,a:min([x for x in a if re.search('.*'.join(s),x)],key=len)

Try it online!

MATL, 28 27 26 bytes
x"l1G@g3XNXm/@gn*v]&X<2Gw)

Try it online!
x - Implicitly take first input (string with three letters) and delete it.  Gets copied into clipboard G, level 1 automatically (this part was inspired by @Luis Mendo's answer).
" - Implicitly take second input (cell array of words), iterate through it.
l - Push 1 to be used later
1G - Push first input (say 'psr')
@g - Push the current word as array
3XN - nchoosek - Get all combinations of 3 letters from the word
Xm - See if the license plate code 'psr' is one of these combinations. Returns 0 for false and 1 for true.
/ - Dividing the 1 (that we pushed earlier) by this result. Changes the 0s to Infs
@gn - Get the length of the current word
* - Multiply the length by the division result. Returns the length as it is when word contains the 3 characters, otherwise returns Inf
v - vertically concatenate these results into a single array
] - close loop
&X< - get the index of the minimum value from that array i.e. the index where the word containing the letters and with minimum length was found
2G - Push the second input again
w - Bring the min index back on top of stack
) - Index into array of words with the min index, returning the valid word with minimum length
(Implicit output.)

Older:
x"@g1Gy3XNXm1w/wn*v]&X<2Gw)

x"@g1Gy3XNXm1w/wn*v]2Gw2$S1)


text:
10 Clickbaits you can't resist
Write a program/function/script that takes a natural number i from 1 to 10 as input and outputs the URL of the Question with the i th hottest question on the Code Golf Portal
The ordering should be like in https://codegolf.stackexchange.com/?tab=hot.
For example:
input 1
output https://codegolf.stackexchange.com/questions/127047/the-spain-license-plates-game
(at the point of this edit)
There are no strong restrictions to the output, as long as the url can be reasonably retrieved. Valid outputs include strings, console printing etc.
It's Code Golf, so shortest code in Bytes wins.
Notes
If your program automatically opens a browser with the webpage, it counts as valid output and is totally cool.
If your program does not retrieve the ranking from current information (i.e. hardcoding the links), it is not valid.
The contest ends with the end of June.
As questioned: The indexing must be 1 based, ie: the input 1 must return the the first site of the hottest questions.
Comment
I hope this question is not too clickbaity, as the stack exchange editor program was mocking me for the title. Originally I planned this challenge with Youtube trends, where it would haven been more fitting.

Re: Stack Exchange mocking you for the question title, it's just triggering on the word you specifically. The assumption made by the software is that if you're asking people what they specifically think about something, then the question is probably going to be closed as primarily opinion-based (as if the question were factually-based, it wouldn't matter who you asked). Of course, this simple heuristic has a lot of false positives.

I'm surprised the answers aren't using URL shorteners: v.ht/b6QI

@EngineerToast They're not usually allowed.

@Challenger5 Indeed. I should probably re-read that list...

Can we output a JSON object containing the URL under the link key or must we output just the URL?

PowerShell v5, 83 Bytes
(irm api.stackexchange.com/questions?sort=hot`&site=codegolf).Items["$args"-1].Link

irm is short for Invoke-RestMethod which auto-parses the Json, makes life quite easy.
add four bytes (saps for start-process) for version which opens in browser.
saps(irm api.stackexchange.com/questions?sort=hot`&site=codegolf).Items["$args"-1].Link

Python + requests, 128 bytes
from requests import*
lambda n:get('http://api.stackexchange.com/questions?sort=hot&site=codegolf').json()['items'][n-1]['link']

Mathematica, 125 bytes
b="http://codegolf.stackexchange.com";b<>"/q/"<>StringCases[Import[b<>"?tab=hot","Text"],"ns/"~~a:DigitCharacter..:>a][[3#]]&

Anonymous function. Takes no input and returns a string as output. Was going to use the XML feed, but it seems to follow a different ordering than on the page.

Python 3, 221 bytes
from urllib.request import*
import zlib, json
lambda n:json.loads(zlib.decompress(urlopen('http://api.stackexchange.com/questions?sort=hot&site=codegolf').read(),16+zlib.MAX_WBITS),encoding='utf-8')['items'][n-1]['link']

Based off of ovs answer. Also, thanks to Oluwafemi Sule for helping me with an issue I had.

Can you edit your answer and mention that it is Python 3? Thanks! :-)

@MauroBaraldi Edited. Sorry about that.

16+zlib.MAX_WBITS can be 31, the space between zlib and json in import zlib, json can be removed, and Python 3.9 lets you get rid of ,encoding='utf-8'.

Python 2.7, 195 bytes
from urllib import*
import zlib, json
lambda n:json.loads(zlib.decompress(urlopen('http://api.stackexchange.com/questions?sort=hot&site=codegolf').read(),16+zlib.MAX_WBITS))['items'][n-1]['link']

This is same answer by Dair, but using Python 2

Welcome to PPCG!

Stratos, 28 bytes
"-1"+
f"¹⁵s²&sort=hot"r"⁷s"@

Explanation:
"-1"+                    Decrement the input, and store it.
f"¹⁵s²&sort=hot"         Fetch the contents of the URL api.stackexchange.com/questions?site=codegolf&sort=hot.
                r"⁷s"    Get the array named "items"
                     @   Get the nth element, where n is retrieved from storage.

Try it!

I'm really questioning the validity of this, considering you made this language less than a month before posting this, and, coincidentally, there are one-byte builtins for api.stackexchange.com/, question, ?site=codegolf, and item. Oh yeah, and a builtin for parsing JSON and getting an array from it in 3+ bytes.

More to the point, this returns a JSON object, not a URL like OP asked. Therefore, this is invalid.

Try re-reading the challenge, it is valid. This language was specifically designed to be able to look up the stackexchange API and this challenge just happened to be posted

Try re-reading my second comment, it is invalid.

Quoting the challenge: "There are no strong restrictions to the output, as long as the url can be reasonably retrieved. Valid outputs include strings, console printing etc." @Makonede

Yes, and this doesn't output a string of the URL or write it to a file or etc. It prints a JSON object which is not allowed.

As the URL can be reasonably be retrived from the JSON, as the challenge states, it is valid.

JavaScript (ES6), 106 bytes
Returns a Promise containing the JSON object for the desired question, which includes the link.
n=>fetch`//api.stackexchange.com/questions?sort=hot&site=codegolf`.then(r=>r.json()).then(j=>j.items[--n])

Sacrificed 2 bytes allowing for 1-indexing.

Try it

f=
n=>fetch`//api.stackexchange.com/questions?sort=hot&site=codegolf`.then(r=>r.json()).then(j=>j.items[--n])
oninput=_=>f(+i.value).then(console.log)
f(i.value=1).then(console.log)
<input id=i type=number>

hm Im not sure at the moment how to handle 0 based indexing, but as the other answers appear to use 1 based indexing and it was specified that way, your answer is counted as 106 bytes (still current top score)

@Moartem: "Im not sure at the moment how to handle 0 based indexing" - Let me know when you've figured it out and I'll update my answer accordingly. I would suggest allowing for either 1-indexing or 0-indexing.

I will fix it to 1-indexing, so all have the same prequesites, please update your answer. Anyway thanks for pointing this out.

@Moartem: Answer updated. For future reference, unless there's good reason not too, the norm is to allow solutions to use their language's default indexing.

05AB1E + json, 85 bytes
<’¸¸.Â‚‹º.ŒŒ/…é?€¼=ƒËŠˆ&Šœ=…ß’.w„\"D„\\s‚‡’(EnÆá.€› (JSON.deƒË!"ÿ")["‚Õ"],ÿ)["ƒÚ"]’.E

source: Stack Exchange

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

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

sort: votes


text:
Find the missing integer (i) , The duplicated integer (j), the length or random integers (n). But only if "i" = "j", just tell me "Huh!?"
The task
Your program will be given the following inputs: a number n, and an array of n positive integers. Your program only has to work when n=1000.
The program must do the following:

If the input array is a permutation of the range [1, 2, …, n], output Huh!?
Otherwise, return a three-element array [i, j, n], where i is a number from 1 to n inclusive that does not appear in the input array, and j is a number that appears more than once in the input array.

Clarifications

Because n will always have the same value, your program may get at it three different ways: hardcoding it as 1000, checking the length of the input array, or taking it from input.
Per PPCG rules, you don't have to read an input at all if you don't need it to solve the question.
The input will always be chosen so that there's a unique answer (in other words, the input array will contain no more than one duplicated element).

Test case generator
The following test case generator, in the statistical programming language R, will generate an appropriate test case for this challenge. It takes the following inputs:

The value of n. In order to create an appropriate test case, this should be 1000.
The value of i.
The value of j.

Here's the generator itself:
#!/usr/bin/env Rscript
#Random_number_generator_1.R
getwd()

printf <- function(...) cat(sprintf(...))
print("Please set the range of random numbers from 1 to n \n")

this_range = scan(file = 'stdin', what = integer(), nmax = 1)

numbers = 1:this_range

#print("How many random numbers in this range")
# random_numbers = scan(file = "", what = integer(), n = 1)

#if(random_numbers > this_range)
#{
#  remove(random_numbers)
#  print("Sorry. When Replace = FALSE. It's not possible to have more unique random numbers than the given range")
#}

random_numbers = sample(numbers)
random_numbers = sample(random_numbers)

print("Now remove any random number in the available range")
number_taken = scan(file = 'stdin' , what = integer(), nmax = 1)
random_numbers = random_numbers[random_numbers != number_taken]

print("Now insert any random number within the range")
number_inserted = scan(file = 'stdin', what = integer(), nmax = 1)

random_numbers = append(random_numbers, number_inserted)

print(random_numbers)

write(random_numbers, file = "my_random_numbers.txt", sep = " ")

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

I almost solved this problem completely with 580 bytes of an R-script.

Please explain the dislike? I provided all details that you need to solve this problem including the desired output, and that the problem is truly solvable.

The question is too long. Delete the unrelated part, and move the most important part to the top, while keeping the rest as appendix, and outsource long programs to pastebin.

So it's a good question. You just don't like how it's formatted? What do you consider unrelated exactly? The last time my question was put on hold for being too vague, and now it's too exact? How does that work?

Does the "space separated input" add anything to the challenge or could we just take a list?

when would i = j not be the same as j = i?

It would always be the same. I was just trying to be extra clear about it.

@xyz123 the balance between concision and precision is not always an easy one.

If you can read space separated input into a list, then it's fine.

What's up with the strict output formatting?

It's for human readability.

"If you can read space separated input into a list, then it's fine." does not really answer my question - I wanted to know if I may take input as a list? Also do we need to output a space separated string or is my current [j, i, n] OK? Note that usually IO is kept loose in code-golf to allow us to concentrate on the core of the challenge unless a tight I/O adds to the challenge in some way.

[i, j, n] is fine since everyone understand my question. You can change the format of my question to a way that makes sense to you, so long as you don't dislike my thoughtful question in the process.

@xyz123, next time you post, you may want to use the sandbox first.

I actually got suggestions form sandbox to modify my question, and I modified it appropriately, and then I got all this hate from you guys, and you put my question on hold again, so yeah, I don't know what you want from me!

I don't think it should have been put on hold (especially after I improved the formatting), but at that point it already had 4 votes to place it on hold, so only 1 more was needed. I've started a vote to reopen it again. In general, Stack Exchange's close and reopen system is problematic because if someone thinks a post shouldn't be placed on hold, they have no way to express that opinion until after it already is.

Do we really have to output n given that it's always 1000? Also, outputting "Huh?" as an alternative to a list of numbers is not possible in strongly-typed languages and IMO a needless complication. I think this would be a good challenge if not for the extra stuff.

Jelly,  27 26  21 18 bytes
-8 bytes by applying a suggestion from Leaky Nun (use multi-set difference to J and a dequeue to replace a length-1 test)
ḲµVœ^J;LµḊȧȯ“Huh!?

A full program.
Try it online!
How?
ḲµVœ^J;LµḊȧȯ“Huh!? - Main link: list of characters
Ḳ                  - split at spaces, call this x
 µ                 - start a new monadic chain with the result of that on the left
  V                - evaluate as Jelly code (vectorises) -> list of integers
     J             - range(length(x)) -> [1,2,3,...,n]
   œ^              - multi-set difference -> one of: []; [i,j]; or [j,i]
       L           - length of x -> n
      ;            - concatenate -> one of: [n]; or [i, j, n]; or [j, i, n]
        µ          - new monadic chain, call that r
         Ḋ         - dequeue r -> one of: []; [j, n]; or [i, n]
          ȧ        - logical and with r -> []; [i, j, n]; or [j, i, n]
            “Huh!? - list of characters "Huh!?" (end of a program so no close quote needed)
           ȯ       - logical or -> one of "Huh!?"; [i, j, n]; or [j, i, n]
                   - implicit print

Mathematica, 70 bytes
{(a=(Range@1000~Complement~#)[[1]])+Tr@#-500500,a,1000}~Check~"Huh!?"&

Anonymous function. Takes a list of numbers as input and returns a list of numbers or a string as output. Ignore any messages generated. Works by finding j and then computing i.

That's pretty neat.

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


text:
Am I a Cullen Number?
A Cullen Number is any number that is contained in the sequence generated using the formula:
C(n) = (n*2^n)+1.
Your Task:
Write a program or function that receives an input and outputs a truthy/falsy value based on whether the input is a Cullen Number.
Input:
A non-negative integer between 0 and 10^9 (inclusive).
Output:
A truthy/falsy value that indicates whether the input is a Cullen Number.
Test Cases:
Input:    Output:
1   --->  truthy
3   --->  truthy
5   --->  falsy
9   --->  truthy
12  --->  falsy
25  --->  truthy

Scoring:
This is code-golf, so the lowest score in bytes wins.

What's the range of n? In particular, is 1 a Cullen Number?

@ais523 according to OEIS, it is. n seems to be 0-based.

Fair enough. Just needed to know whether my Jelly answer should have an Ḷ or R in it :-)

Related

Umm, what's with the downvote?

Pyth, 6 5 bytes
/mh.<

try it online

x86_64 machine code (System V ABI), 28 27 bytes
-1 byte thanks to @Cody Gray, thanks!
A constant-time algorithm!
_cullen:
   0:   0f bd cf    bsrl    %edi, %ecx
   3:   0f bd c1    bsrl    %ecx, %eax
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx
   a:   0f bd c2    bsrl    %edx, %eax
   d:   29 c1       subl    %eax, %ecx
   f:   d3 e1       shll    %cl, %ecx
  11:   ff c1       incl    %ecx
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq

Explanation:
Let y an integer and x=y*2^y + 1.
Taking logs, we have y + log2(y) = log2(x-1), thus y=log2(x-1)-log2(y). Plugging back the value of y, we get y=log2(x-1)-log2(log2(x-1)-log2(y)). Doing this one more time, we obtain: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].
Let us remove the last terms (of the order of log2(log2(log2(log2(x)))), this should be safe!), and assume that x-1≈x, we obtain:
y≈log2(x)-log2[log2(x)-log2(log2(x))]
Now, letting f(n) = floor(log2(n)), it can be verified manually that y can be exactly retrieved by:
y=f(x)-f[f(x)-f(f(x))],
for y < 26, and thus x ⩽ 10^9, as specified by the challenge(1).
The algorithm then simply consists of computing y given x, and verify that x == y*2^y + 1.
The trick is that f(n) can simply be implemented as the bsr instruction (bit-scan reverse), which returns the index of the first 1-bit in n, and y*2^y as y << y.
Detailed code:
_cullen:                                 ; int cullen(int x) {
   0:   0f bd cf    bsrl    %edi, %ecx   ;  int fx = f(x);
   3:   0f bd c1    bsrl    %ecx, %eax   ;  int ffx = f(f(x));
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx   ;  int a = fx - ffx;
   a:   0f bd c2    bsrl    %edx, %eax   ;  int ffxffx = f(a);
   d:   29 c1       subl    %eax, %ecx   ;  int y = fx - ffxffx;
   f:   d3 e1       shll    %cl, %ecx    ;  int x_ = y<<y;
  11:   ff c1       incl    %ecx         ;  x_++;
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq                 ;  return (x_ == x);
                                         ; }

(1)In fact, this equality seems to hold for values of y up to 50000.

Well, I'm pretty sure this qualifies as the most interesting code for this challenge so far.  +1

Pre-XORing eax would allow you to eliminate the movzbl, saving 1 byte. You'd need to do the XOR before the cmpl so it doesn't clobber the flags, of course, but that's totally fine because nothing after that depends on eax. Or, you could just decide that the method returns a Boolean in only the lower 8 bits, saving all 3 bytes!

@CodyGray Indeed, thanks a lot :)

Jelly, 7 6 bytes
Ḷæ«`i’

Try it online!
Takes input as a command-line argument. If given a Cullen number C(n), outputs n+1 (which is truthy in Jelly, being an nonzero integer; note that we have n≥0 because the input is an integer, and Cullen numbers with negative n are never integers). If given a non-Cullen number, returns 0, which is falsey in Jelly.
Explanation
Ḷæ«`i’
Ḷ        Form a range from 0 to (the input minus 1)
 æ«      Left-shift each element in the range by
   `       itself
    i’   Look for (the input minus 1) in the resulting array

Basically, form an array of Cullen numbers minus one, then look for the input minus one in it. If the input is a Cullen number, we'll find it, otherwise we won't. Note that the array is necessarily long enough to reach to the input, because C(n) is always greater than n.

JavaScript (ES6), 37 35 bytes
Saved 2 bytes thanks to Neil
f=(n,k,x=k<<k^1)=>x<n?f(n,-~k):x==n

Demo

f=(n,k,x=k<<k^1)=>x<n?f(n,-~k):x==n

console.log(JSON.stringify([...Array(1000).keys()].filter(n => f(n))))

Does x<n?f(n,k+1):x==n work?

@Neil It sure does. :-)

Why does `~k work, while k+1 overloads the callstack?

@trlkly Basically, undefined+1===NaN but -~undefined===1. You can read more about this here.

Haskell, 28 bytes
f n=or[x*2^x+1==n|x<-[0..n]]

Try it online!

R, 53 51 46 bytes
pryr::f(x%in%lapply(0:x,function(y)(y*2^y+1)))

Anonymous function. Checks if x is generated in the sequence C(n) for n in [0,x].
3 bytes golfed by Giuseppe.
Try it online!

use x%in%... instead of any(x==...); that'll drop you 4 bytes

So if I golf this by changing the lapply to simply checking the vector, and use scan instead of taking function arguments - I get @giuseppe 's answer. Thanks for posting it separately so I can see what I'm missing - I learn more by trying something on my own, even though I usually lose.

Ohm, 8 bytes
@Dº*≥Dlε

Try it online!
           Implicit input
@          Range [1,...,Input]
 D         Duplicate
  º        2^n each element
   *       Multiply those two array
    ≥      Increment everything (now I have an array of all Cullen Numbers)
     Dl    Push array length (= get input again, can't get again implicitly or using a function because it would be a string so I'd waste a byte again)
       ε   Is input in array?

PHP, 43 bytes
for(;$argn>$c=1+2**$n*$n++;);echo$argn==$c;

Try it online!

Is $argn a special variable? Changing it to $a would save 6 bytes: https://tio.run/##K8go@G9jX5BRwKWSaKtkaGaoZP0/Lb9Iw1ol0U4l2dZQ20hLSyUPiLS1rTWtU5Mz8oHqbFWSrf//BwA

@topher Yes  $argn is available if you run PHP from the command line with the -R option

05AB1E, 7 bytes
ÝDo*¹<å

Try it online!
Explanation:
ÝDo*¹<å Example input: 9. Stack: [9]
Ý       Range 0-input. Stack: [[0,1,2,3,4,5,6,7,8,9]]
 D      Duplicate. Stack: [[0,1,2,3,4,5,6,7,8,9],[0,1,2,3,4,5,6,7,8,9]]
  o     2** each item in the list. Stack: [[0,1,2,3,4,5,6,7,8,9], [1,2,4,8,16,32,64,128,256,512]]
   *    Multiply the two lists. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608]]
    ¹   Push input again. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608],9]
     <  Decrement. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608],8]
      å Is the first item of the stack in the second item? Stack: [1]
        Implicit print.

C, C++, Java, C#, D : 70 bytes
Due to the similarities between all these languages, this code works for each
int c(int n){for(int i=0;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}

I'll post the optimized D version this time, some pretty D-specific tricks can be used.

Suggest i=30;i--;)if(i<<i==n-1) instead of i=0;i<30;++i)if((1<<i)*i+1==n)

Python 2, 36 bytes
f=lambda n,i=0:i<<i!=n-1and f(n,i+1)

Try it online!
Outputs by not crashing / crashing, as currently allowed by this meta concensus.

Python 2, 42 bytes
i=0
n=input()-1
while i<<i<n:i+=1
i<<i>n<c

Try it online!
Outputs via exit code

Python, 40 bytes
lambda n:any(x<<x==n-1for x in range(n))

Try it online!

R, 26 bytes
a=0:26;scan()%in%(1+a*2^a)

Try it online!
A slightly different approach than the other R answer; reads from stdin and since the input is guaranteed to be between 0 and 10^9, we just have to check n between 0 and 26.

I never remember scan(). Good work.

APL (Dyalog), 9 bytes
To cover the case of n = 1, it requires ⎕IO←0 which is default on many systems.
⊢∊1+⍳×2*⍳

Try it online!
⊢ [is] n (the argument)
∊ a member of
1 one
+ plus
⍳ the integers 0 … (n-1)
× times
2 two
* to the power of
⍳ the integers 0 … (n-1)

So, "default on many systems" means that it just exists?

@Zacharý Yes, it would be wrong to call ⎕IO←0 non-standard, as many indeed always have it set like that, with no specification necessary each time.

Well. I'm going to use that trick in MY for sure (and MY can have non-0 and non-1 Index Origins) if I ever get the chance to.

@Zacharý Wouldn't that require an actual install base/versions where those values are default? E.g. in SAX and ngn, ⎕IO←0.

Yeah, I guess it would. And MY does have three iotas, so I think that wouldn't be used anyways.

Python 2, 32 bytes
[n<<n|1for n in range(26)].count

Try it online!
Creates the list of Cullen numbers up to 10^9, then counts how many times the input appears in it. Thanks to Vincent for pointing out n<<n|1 instead of (n<<n)+1, saving 2 bytes.

You can save two bytes using n<<n|1 (n<<n being even) ;)

This fails for 838860801. You need range(26), because the range isn't inclusive.

@mbomb007 Thanks. I've done this for a while and still sometimes forget ranges are right-exclusive.

D, 65 bytes

This is a port of @HatsuPointerKun's algorithm to D (the original was already D code, but this is with D-specific tricks)
T c(T)(T n){for(T i;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}

How? (D specific tricks)
D's template system is shorter than C++'s, and can infer types. And D also initializes its variables to the default upon declaration.

TI-BASIC, 17 bytes
max(Ans=seq(X2^X+1,X,0,25

Explanation
seq(X2^X+1,X,0,25 Generate a list of Cullen numbers in the range
Ans=              Compare the input to each element in the list, returning a list of 0 or 1
max(              Take the maximum of the list, which is 1 if any element matched

You might want to add an explanation to this.

Done, thanks for the tip.

That works, but a command-by-command explanation usually helps garner most upvotes.  I would reccomend doing something like the explanation on this answer.  I don't know why somebody downvoted your post though.  It's usually common courtesy to leave a comment when you do so, although that idea is often ignored.

Your welcome.  I remember when I first joined the site, people told these types of things to me.  Just passing on the favour.

Nibbles, 5.5 bytes (11 nibbles)
?.`,$+~*^2

Returns 1-based index in list of Cullen numbers (truthy), or zero (falsy) if not a Cullen number.
?.`,$+~*^2      # full function
?.`,$+~*^2$$$   # (with implicit arguments shown):
 .              # map over
  `,$           # 0..input-1
                # with function:
     +          #   add
      ~         #   1 (default)
                #   to
        ^2      #   2 to the power of
          $     #   input
       *   $    #   multiplied by input
?           $   # and get the index of the input in this
                # (or zero if not found)

Julia 1.0, 23 bytes
~n=n∈0:n.|>x->x*2^x+1

Try it online!

Mathematica, 30 bytes
MemberQ[(r=Range@#-1)2^r+1,#]&

Pure function taking a nonnegative integer as input and returning True or False. If the input is n, then (r=Range@#-1) sets the variable r to be {0, 1, ..., n-1}, and then r2^r+1 vectorially computes the first n Cullen numbers. MemberQ[...,#] then checks whether n is an element of the list.

Mathematica, 32 bytes
!Table[x*2^x+1,{x,0,#}]~FreeQ~#&

Excel VBA, 45 Bytes
Anonymous VBE immediate window function that takes input from cell [A1] and ouputs to the VBE immediate window
Must be run in a clean module or have values for i,j be reset to default value of 0 between runs
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]

Input / Output
I/O as seen in VBE immediate window
[A1]=25
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
True

[A1]=1: i=0:j=0 ''# clearing module values
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
True

[A1]=5: i=0:j=0 ''# clearing module values
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
False

Swi-Prolog, 69 bytes
f(X) succeeds if it can find a value I where X = I*2^I+1. The range hint stops it running out of stack space, but it's enough for the range of Cullen numbers up to 10^9 in the question spec.
:-use_module(library(clpfd)).
f(X):-I in 0..30,X#=I*2^I+1,label([I]).

e.g.
f(838860801).
true

cQuents, 9 bytes
$0?1+$2^$

Try it online!
Explanation
$0           n is 0-indexed
  ?          Mode query. Given input n, output true/false for if n is in the sequence.
   1+$2^$    Each item in the sequence equals `1+index*2^index`

Arturo, 29 bytes
$=>[in?&map 0..25'n->1+n*2^n]

Try it

Japt -d, 7 bytes
ÑpU ¶NÉ

Try it
ÑpU ¶NÉ     :Implicit map of each U in the range [0,input)
Ñ           :Multiply by 2
 pU         :Raised to the power of U
    ¶       :Is equal to
     N      :Array of all inputs
      É     :Minus 1
            :Implicit output of whether or not any U returns true

Raku, 30 bytes
{$_∈({1+$++*2**$++}...*>$_)}

Try it online!
The parenthesized expression is a list of generated Cullen numbers, taken up to the point where a number is greater than the input argument (* > $_).  Then we just check that the input argument is a member of that list (∈).

Vyxal, 6 bytes
ʀ:E*›c

Try it Online!
Explained
ʀ:E*›c
ʀ:     # push 2 copies of the range [0, input]
  E    # 2 ** x for x in ^
   *   # vectorised multiply with the other copy
    ›  # + 1
     c # contains the input?

Thunno D, \$ 11 \log_{256}(96) \approx \$ 9.05 bytes
RD2@z*s1-Aq

Attempt This Online!
Explanation
RD2@z*s1-Aq  # Implicit input
RD           # Push range(input) and duplicate
  2@         # Pop one copy and push 2 ** each
    z*       # Multiply elementwise
      s1-    # Push the input decremented
         Aq  # Is this in the list?

Pyt, 8 bytes
Đ0⇹ŘĐ«⁺∈

Try it online!
Đ             implicit input; Đuplicate
 0⇹Ř          Řangify from 0 to n
    Đ         Đuplicate
     «        bitshift left
      ⁺       increment
       ∈      is input in list of Cullen numbers?; implicit print

QBIC, 24 bytes
[0,:|~a*(2^a)+1=b|_Xq}?0

Explanation
[0,:|           FOR a = 0 to b (input from cmd line)
~a*(2^a)+1=b    IF calculating this a results in b
|_Xq            THEN quit, printing 1
}               NEXT a
?0              We haven't quit early, so print 0 and end.

k, 19 bytes
{&1=x-{x**/x#2}'!x}

Try it online. Truthy is an array with a number in it: ,3 or ,0 et cetera. Falsey is an empty array: () or !0 depending on your interpreter.

Java (OpenJDK 8), 56 bytes
i->{int n,c;for(n=0;(c=n*(2<<n++-1)+1)<i;);return c==i;}

Try it online!

Pari/GP, 25 bytes
n->!prod(i=0,n,n-i*2^i-1)

Try it online!

Thunno 2 -c, 5 bytes
ĖıỴ;Ƈ

Try it online!
Port of user62131's Jelly answer.
Thunno 2, 6 bytes
ĖDO×⁺Ƈ

Try it online!
Explanation
ĖıỴ;Ƈ  # Implicit input
       # Decrement the input
Ė      # Push [0..input-1]
  Ỵ    # Left bit-shift each
 ı ;   # number by itself
    Ƈ  # Is (input - 1)
       # in this list?
       # Implicit output

ĖDO×⁺Ƈ  # Implicit input
Ė       # Push [0..input]
 D      # Duplicate it
  O     # Push 2 ** that
   ×    # Multiply together
    ⁺   # Increment each
     Ƈ  # Is the input
        # in this list?
        # Implicit output


text:
LCM of Rational Numbers
The least common multiple (LCM) of a set of numbers A is the smallest integer b such that b/a is an integer for all integers a in A. This definition can be extended to rational numbers!
Task
Find the smallest positive rational b such that b/a is an integer for all rationals a in the input.
Rules

Standard loopholes are forbidden.
You may take numerators and denominators separately in the input, but may not take doubles, floats, etc.
The input may not be fully reduced.
You may take integer inputs as rationals with denominator of 1.
Submissions that would feed rational numbers to an LCM/GCD builtin are allowed, but non-competing.

Test Cases
In:  3
Out: 3

In:  1/17
Out: 1/17

In:  1/2, 3/4
Out: 3/2

In:  1/3, 2/8
Out: 1

In:  1/4, 3
Out: 3

In:  2/5, 3
Out: 6

In:  1/2, 3/4, 5/6, 7/8
Out: 105/2

This is code-golf, so submissions using the fewest bytes win!

Note: computing LCM[numerators]/GCD[denominators] may not work when the input contains a non-reduced rational number. e.g. 1/3, 2/8.

So if I reduce it, it will work?

@LeakyNun Yes, it will.

To encourage people to submit non-builtin answers, I've edited the question, making builtin answers non-competing (still allowed). If this is a problem, I will rollback my edit.

What about an LCM built-in being used but only with integers - competing or not?

@JonathanAllan They are competing as long as the inputs of the LCM builtin  are only integers.

I wondered at "non-competing but still allowed" but it seems we don't have a rule about that yet, so I've raised it on meta for discussion.

Maybe include a test case with negative input?

Can we take input as a list of numerators and a list of denominators?

Jelly, 19 bytes
g/:@$€Z©Ḣæl/;®Ḣg/$¤

Try it online!

tfw Jelly sucks with fractions

g/:@$€ -> :g/$€

Save another two bytes with: :g/$€ZµḢæl/,Ḣg/$

@JonathanAllan That's a nice piece of code...

J, 3 bytes
*./

Given a list of rational inputs, this folds LCM through it.

Jelly, 12 bytes
:g/æl/;g/}ɗ/

Try it online!
Takes input as [[list of numerators], [list of denominators]]. +2 bytes to take input as a list of [numerator, denominator] pairs
How it works
:g/æl/;g/}ɗ/ - Main link. Takes a pair of lists [N, D] on the left
  /          - Columnwise reduce by:
 g           -   GCD
:            - Divide, reducing the fractions to their simplest form
          ɗ  - Group the previous 3 links into a dyad f(N, D):
   æl/       -   LCM of N
         }   -   To D:
       g/    -     GCD
      ;      -   Concatenate
           / - Reduce; Yield f(N, D) where N is the first list and D the second

The 14 byte version transposes the input with Z to get it into the [N, D] format, then uses $ as a "grouping" construct the make the :g/ act on that

Python 2, 65 bytes
lambda x:reduce(lambda x,y:x*y/gcd(x,y),x)
from fractions import*

Try it online!

sed, 374 (373+1) bytes
sed's -E flag counts as one byte. Note: I haven't tried to golf this yet, and probably won't for quite some time.
Input is taken in unary, and output is in unary. Spaces must surround every fraction. Example: echo " 1/111 111/11111 111111/111 ".
:d;s, (1*)/\1(1*), \1/\22,;s,(1*)(1*)/\2 ,2\1/\2 ,;td;s,1*(1/22*),\1,g;s,(22*/1)1*,\1,g;:r;s,((1*)/1*)2,\1\2,;s,2(1*/(1*)),\2\1,;tr;h;s,1*/,,g;:g;s/^(1*) 1(1*) 1(1*)/1\1 \2 \3/;tg;s/  */ /g;s/^/ /;/1 1/bg;x;s,/1*,,g;s/^( 1*)( 1*)/\1\2\2/;:l;s/^(1*) (1*) \2(1*)/\1\2 \2 \3/;tl;/  $/be;/  /{s/^(1*) 1*  1*( 1*)/ \1\2\2/;bl};s/^(1* 1* )(1*) (1*)/\1\2\3 \3/;bl;:e;G;s, *\n *,/,

Try it online!

Pari/GP, 30 bytes
This only apply the lcm built-in on integers.
a->d=denominator(a);lcm(a*d)/d

Try it online!

Pari/GP, 3 bytes
This feeds rational numbers to the lcm built-in, so it is non-competing.
lcm

Try it online!

@JungHwanMin Does it mean that a GCD built-in is allowed?

Good point. Yes, as long as its inputs are only integers.

JavaScript (ES6), 85 bytes
a=>a.reduce(([b,c],[d,e,g=(b,c)=>c?g(c,b%c):b,h=g(b*e,c*d),i=g(b*d,h)])=>[b*d/i,h/i])

Look no builtins! No doubt someone will beat this using a recursive approach or something.

Common Lisp, 154 bytes
(defun f(l &aux(s(pairlis l l)))(loop(and(eval`(=,@(mapcar'car s)))(return(caar s)))(let((x(assoc(reduce'min s :key'car)s)))(rplaca x(+(car x)(cdr x))))))

Algorithm used (specified for integers, but works also for rationals).
First make an associative list of the input data with itself, to get track of the initial values of the elements, so the operating sequence is given by the “car”s of the list.
(defun f(l &aux (s (pairlis l l)))        ; make the associative list
  (loop
     (when (eval `(= ,@(mapcar 'car s))) ; when the car are all equal
       (return (caar s)))                 ; exit with the first one
     (let ((x (assoc (reduce 'min s :key 'car) s))) ; find the (first) least element
       (rplaca x (+ (car x) (cdr x))))))  ; replace its car adding the original value (cdr)

Test cases:
CL-USER> (f '(3))
3
CL-USER> (f '(1/17))
1/17
CL-USER> (f '(1/2 3/4))
3/2
CL-USER> (f '(1/3 2/8))
1
CL-USER> (f '(1/4 3))
3
CL-USER> (f '(2/5 3))
6
CL-USER> (f '(1/2 3/4 5/6 7/8))
105/2

Note: The solution is without the use of the builting lcm and gcd, that accept integers.

W00t? Try this at your REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).

@Kaz, since, as it said in problem, “Submissions that would feed rational numbers to an LCM/GCD builtin are allowed, but non-competing”.

In Lisp terms, strictly speaking, we are in fact feeding rationals when we call (lcm 1 3 5 7), since integers are a subtype of rationals, but I think the rule is supposed to exclude use of a lcm or gcd which allows rational inputs.

@Kaz, ops... I misinterpreted the rules! Should I remove the post? (maybe it is not good marketing for Common Lisp :)

I'd just put in a note that this is a solution without using the built-in integer lcm and gcd.

Perl 6,  46  42 bytes
{[lcm](@_».numerator)/[gcd] @_».denominator}

test it
{[lcm](($/=@_».nude)[*;0])/[gcd] $/[*;1]}

test it
Input is a list of Rational numbers.
Expanded:
{ # bare block lambda with implicit parameter list ｢@_｣

  [lcm](            # reduce using &infix:<lcm>
    (
      $/ = @_».nude # store in ｢$/｣ a list of the NUmerators and DEnominiators
                    # ((1,2), (3,4))

    )[
      *;            # from all of the first level ｢*｣,
      0             # but only the 0th of the second level (numerators)
    ]
  )
  /
  [gcd] $/[ *; 1 ]  # gcd of the denominators
}

Retina, 117 bytes
\d+
$*
\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*
{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3
}`\G1(?=1* (1+))|\G 1+
$1
1+
$.&

Try it online! Takes input as a space-separated series of improper fractions (no integers or mixed numbers). Explanation:
\d+
$*

Converts decimal to unary.
\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*

This reduces each fraction to its lowest terms. Capture group 1 represents the GCD of the numerator and denominator, so we count the number of captures before and after the /. \b(1+)+/(\1)+\b doesn't seem to count the number of captures correctly for some reason, so I use an extra capturing group and add 1 to the result.
{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3

This does a number of things. Capture group 2 represents the GCD of the numerators of the first two fractions, while capture group 3 represents the GCD of the denominators. $#4 is therefore the second numerator divided by their GCD. (Again, I couldn't could the number of captures of the first numerator, but I only need to divide one numerator by their GCD, so it doesn't cost me quite so much.)
}`\G1(?=1* (1+))|\G 1+
$1

Now that the second numerator has been divided by their GCD, we just use this expression from the unary arithmetic tutorial to multiply the two together, resulting in the LCM. We then repeat the exercise for any remaining fractions.
1+
$.&

Converts unary back to decimal.

Mathematica, 3 bytes
LCM

Mathematica's built-in LCM function is capable of handling rational number inputs.

While answering your own question is fine, I don't think it's very sporting to answer it with a solution that has a very real chance of winning :P

@BetaDecay Yep... So it's non-competing now.

PHP, 194 bytes
<?for(list($n,$d)=$_GET,$p=array_product($d);$x=$n[+$k];)$r[]=$x*$p/$d[+$k++];for($l=1;$l&&++$i;$l=!$l)foreach($r as$v)$l*=$i%$v<1;for($t=1+$i;$p%--$t||$i%$t;);echo$p/$t>1?$i/$t."/".$p/$t:$i/$t;

-4 Bytes with PHP>=7.1 [$n,$d]=$_GET instead of list($n,$d)=$_GET
Try it online!

Common Lisp, 87 78 bytes
Using lcm and gcd, which have integer inputs:
(defun l(a)(/(apply #'lcm(mapcar #'numerator a))(apply #'gcd(mapcar #'denominator a))))

More golfed:
(defun l(a)(eval`(/(lcm,@(mapcar'numerator a))(gcd,@(mapcar'denominator a))))


text:
Fastest algorithm to take the product of all subsets
Given n numbers in an array (you can't assume they are integers), I would like to compute the product of all subsets of size n-1.
You can do this by  multiplying all the numbers together and then dividing by each one in turn, as long as none of the numbers is zero.  However, how quickly can you do this with no division?

If you don't allow division, what is the minimum number of
  arithmetic operations (e.g. multiplication and addition) needed to compute the product of all subsets of size
  n-1?

Clearly you can do it in (n-1)*n multiplications.
To clarify, the output is n different products and the only operations apart from reading and writing to memory allowed are multiplication, addition and subtraction.
Example
If the input has three numbers 2,3,5, then the output is three numbers 15 = 3*5, 10 = 2*5 and 6 = 2*3.
Winning criterion
Answers should give an exact formula for the number of arithmetic operations their code will use in terms of n.  To make life simple, I will just plug n = 1000 into your formula to judge its score. The lower the better.
If it's too hard to produce an exact formula for your code, you can just run it for n = 1000 and count the arithmetic operations in  the code.  An exact formula would be best however.
You should add your score for n=1000 to your answer for easy comparison.

Welcome to PPCG! Nice first question!

@EriktheOutgolfer Thank you!

Do the products have to be listed in any particular order?

@xnor No. Any order will do.

May we count multiplying by 1 as free? Otherwise I'd define a custom-multiplication function that does this.

For simplicity, all multiplications should be counted in the score, even by 1.

Would it be against the rules to do a whole bunch of multiplications in parallel by concatenating numbers together with sufficiently many spacer 0 digits?

@xnor Yes it would!

Are operations like >= or max also banned? You might want to make this an atomic code golf so people don't try to use language features to get around your restrictions.

@xnor I basically don't want to allow any operations that are going to substitute for the arithmetic operations via some trickery.  I really want to know how you can do it using a small number of multiplications, subtractions and additions.

Do the operations such as + on indices count? If this is the case, does array indexing count as well? (since it is after all syntactic sugar for addition and dereferencing).

I removed the restricted-code tag since my understanding is that atomic-code-golf supersedes it.

@nore You can look up/access/read the input elements for free.  All the arithmetic operations in your code should be counted however.

@Arthur does this mean a loop has a cost of the number of operations for the counter?

Are architecture-specific tricks allowed in our answers?

@nore OK I give in :)   Just count arithmetic operations that involve the input in some way.

Clearly you can do it in (n-1)*n multiplications You mean (n-2)*n, right?

Does a SIMD operation count as a single operation?

@Veedrac Not for this challenge, sorry.

Maybe I'm being thick, but what does it mean to multiply two or more sets?  No definition of set that I know has a multiply operation.  Perhaps you could give a worked example for what the result would be for a small input array?

@TobySpeight If the input has three number 1,2,3, then  the output is three numbers 6 = 2*3,3 = 1*3 and 2 = 1*2. Does that help?

Oh, so you're asking for a set of outputs - no wonder I was confused.  The way it's worded in the question suggests you are looking for (2,3) * (1,3) * (1,2) - perhaps it could be edited to include your helpful example?

If this was a simple code golf, I would submit this Perl 6 one {.combinations(.end).map: *.reduce: &prefix:<[*]>}

Python, 3(n-2) operations, score = 2994
l = list(map(float, input().split()))
n = len(l)

left = [0] * len(l)
right = [0] * len(l)
left[0] = l[0]
right[-1] = l[-1]
for i in range(1,len(l)-1):
  left[i] = l[i] * left[i - 1]
  right[-i-1] = l[-i-1] * right[-i]

result = [0] * len(l)
result[-1] = left[-2]
result[0] = right[1]
for i in range(1, len(l) - 1):
  result[i] = left[i - 1] * right[i+1]

print(result)

The arrays left and right contain the cumulated products of the array from the left and from the right, respectively.
EDIT: Proof that 3(n-2) is the optimal number of operations needed for n >= 2, if we only use multiplication.
We will do that by induction; by the above algorithm, we just have to prove that for n >= 2, 3(n-2) is a lower bound on the number of multiplications needed.
For n = 2, we need at least 0 = 3(2-2) multiplications, so the result is trivial.
Let n > 2, and suppose for n - 1 elements, we need at least 3(n-3) multiplications. Consider a solution for n elements with k multiplications.
Now, we remove the last of these elements as if it was 1, and simplify all multiplications directly by it. We also remove the multiplication leading to the product of all the other elements, since that one is not needed as it can never be used as an intermediate value to get the product of n-2 of the other elements, since division is not allowed. This leaves us with l multiplications, and a solution for n - 1 elements.
By induction hypothesis, we have l >= 3(n-3).
Now, let's have a look at how many multiplications were removed. One of them was the one leading to the product of all elements except the last. Moreover, the last element was used directly in at least two multiplications: if it was used in only one, then it was used when multiplying by an intermediate result consisting in some product of the other elements; let's say, without loss of generality, this this intermediate result included the first element in the product. Then, there is no way to get the product of all the elements but the first, since every product that contains the last element is either the last element, or contains the first element.
We thus have k >= l+3 >= 3(n-2), proving the claimed theorem.

This turns out very clean in Haskell: f l = zipWith (*) (scanl (*) 1 l) (scanr (*) 1 $ tail  l).

Comments are not for extended discussion; this conversation has been moved to chat.

Haskell, score 2994
group :: Num a => [a] -> [[a]]
group (a:b:t) = [a,b] : group t
group [a] = [[a]]
group [] = []

(%) :: (Num a, Eq a) => a -> a -> a
a % 1 = a
1 % b = b
a % b = a * b

prod_one_or_two :: (Num a, Eq a) => [a] -> a
prod_one_or_two [a, b] = a % b
prod_one_or_two [x] = x

insert_new_value :: (Num a, Eq a) => ([a], a) -> [a]
insert_new_value ([a, b], c) = [c % b, c % a]
insert_new_value ([x], c) = [c]

products_but_one :: (Num a, Eq a) => [a] -> [a]
products_but_one [a] = [1]
products_but_one l =
    do combination <- combinations ; insert_new_value combination
    where
        pairs = group l
        subresults = products_but_one $ map prod_one_or_two pairs
        combinations = zip pairs subresults

Try it online!
Say we're given the list [a,b,c,d,e,f,g,h]. We first group it into pairs [[a,b],[c,d],[e,f],[g,h]]. Then, we recurse on the half-size list pairs of their products to get subresults
[a*b, c*d, e*f, g*h] -> [(c*d)*(e*f)*(g*h), (a*b)*(e*f)*(g*h), (a*b)*(c*d)*(g*h), (a*b)*(c*d)*(e*f)]

If we take the first element (c*d)*(e*f)*(g*h), and multiply it by b and a respectively, we get the product of all but a and all but b. Doing this for every pair and recursive result with that pair missing, we get out final result. The odd-length case is specially handled by having the odd element passed unpaired to the recursive step, and the product of the remaining elements returned is the product without it.
The number of multiplications t(n) is n/2 for the pairing product, t(n/2) for the recursive call, and another n for the products with individual elements. This gives t(n) = 1.5 * n + t(n/2) for odd n. Using a more precise counts for odd n and ignoring multiplying with 1 for the base case gives score 2997 for n=1000.

This is very nice.

I think the reason why the score is 2995 and not 2994 as in my answer is that it computes the product of all numbers as well in the non-power of two case, which is later truncated. Maybe a careful handling in products_but_one' could avoid that by returning something of the correct length.

@nore I found I had an extra multiplication in my count because I forgot the base case has a 1 that is free to multiply. I think the padding 1 didn't affect things, but I cleaned up my algorithm to not use them.

Does this code assume the input is integers?

@Lembik It does, but only in the optional type annotations. I'll change them all to float.

Surely you mean Num a => a, or at least Double.

@ØrjanJohansen Is this right?

Looks good, I forgot about the need for Eq. Although group doesn't need either constraint.

@ØrjanJohansen I was surprised Num doesn't imply Eq. Do you know why that is?

@xnor It used to, but was removed in GHC 7.4 because it rules out (or makes awkward) useful new instances. See libraries list thread.

Haskell, score 9974
partition :: [Float] -> ([Float], [Float])
partition = foldr (\a (l1,l2) -> (l2, a:l1)) ([],[])

(%) :: Float -> Float -> Float
a % 1 = a
1 % b = b
a % b = a*b

merge :: (Float, [Float]) -> (Float, [Float]) -> (Float, [Float])
merge (p1,r1) (p2, r2) = (p1%p2, map(%p1)r2 ++ map(%p2)r1)

missing_products' :: [Float] -> (Float, [Float])
missing_products' [a] = (a,[1])
missing_products' l = merge res1 res2
    where
        (l1, l2) = partition l
        res1 = missing_products' l1
        res2 = missing_products' l2

missing_products :: [Float] -> [Float]
missing_products = snd . missing_products'

Try it online!
A divide-and-conquer strategy, very reminiscent of merge sort. Doesn't do any indexing.
The function partition splits the list into as-equal-as-possible halves by putting alternating elements on opposite sides of the partition. We recursively merge the results (p,r) for each of the halves, with r the list of products-with-one-missing, and p the overall product.
For the output for the full list, the missing element must be in one of the halves. The product with that element missing is a one-missing-product for the half it's in, multiplied by the full product for the other half. So, we multiply each product-with-one-missing by the full product of the other half and make a list of the results, as map(*p1)r2 ++ map(*p2)r1). This takes n multiplications, where n is the length. We also need to make a new full-product p1*p2 for future use, costing 1 more multiplication.
This gives the general recursion for for the number of operations t(n) with n even: t(n) = n + 1 + 2 * t(n/2). The odd one is similar, but one of the sublists is 1 larger. Doing out the recursion, we get n*(log_2(n) + 1) multiplications, though the odd/even distinction affects that exact value. The values up to t(3) are improved by not multiplying by 1 by defining a variant (%) of (*) that shortcuts the _*1 or 1*_ cases.
This gives 9975 multiplications  for n=1000. I believe Haskell's laziness means the unused overall product in the outer layer is not computed for 9974; if I'm mistaken, I could omit it explicitly.

You beat me by the timestamp one minute earlier.

If it's hard to work out the formula  exactly, feel free to just run it for n = 1000 and count the arithmetic operations in  the code.

Since our code is basically the same, I don't understand how you got to 9974 and not 9975 multiplications for n = 1000 (in the case of computing the overall product in the outer layer). Did you include a 1 in the input you used to test it?

@nore You're right, I was off by one. I wrote code to do the recursion for the number of multiplication function calls. Counting calls directly would be more reliable -- does anyone know how I'd do that in Haskell?

@xnor From my very limited Haskell experience, I know no easy way to do that except by using unsafePerformIO. Maybe someone has a better idea for that than me, however.

@xnor you can use trace from Debug.Trace with a catch-all | trace "call!" False = undefined guard, I think. But this uses unsafePerformIO under the hood, so it's not really that much of an improvement.

O(n log n) operations, score = 9974
Works with a binary tree.
Python
l = list(map(int, input().split()))
n = len(l)

p = [0] * n + l
for i in range(n - 1, 1, -1):
  p[i] = p[i + i] * p[i + i+1]

def mul(x, y):
  if y == None:
    return x
  return x * y

r = [None] * n + [[None]] * n
for i in range(n - 1, 0, -1):
  r[i] = [mul(p[i + i + 1], x) for x in r[i + i]] + [mul(p[i + i], x) for x in r[i + i + 1]]

u = r[1]
j = 1
while j <= n:
  j += j
print(u[n+n-j:] + u[:n+n-j])

This also requires list addition operations, and some arithmetic on numbers that are not the input values; not sure if that counts. The mul function is there to save n operations for the base case, to avoid wasting them by multiplying by 1.
In any case, this is O(n log n) operations. The exact formula is, if only counting arithmetic operations on input numbers, with j = floor(log_2(n)):
j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2.
Thanks to @xnor for saving one operation with the idea of not computing the outer product!
The last part is to output the products in order of the missing term.

If it's hard to work out the formula  exactly, feel free to just run it for n = 1000 and count the arithmetic operations in  the code.

I counted 10975 operations...?

p[i] = p[i + i] * p[i + i+1] isn't counted

This is about n log2 n + n operations (which is O(nlogn) btw

@HyperNeutrino the operations in p[i] = p[i + i] * p[i + i + 1] should be saved by the multiplication optimization. I might have counted one too many, however.

Can't you assign a variable to i + i in the second for loop so you save on operations?

@ZacharyT I could, but I didn't include the operations on indices (to oppose to input numbers) in the count. I could do that of course, but I don't think this is the spirit of the challenge.

Did you count the n-1 in the range calls?

@ZacharyT same, I didn't count this operation as it is only an operation on indices; I am going to wait for an explicit answer on this point.

Haskell, score 2994
group :: [a] -> Either [(a, a)] (a, [(a, a)])
group [] = Left []
group (a : l) = case group l of
  Left pairs -> Right (a, pairs)
  Right (b, pairs) -> Left ((a, b) : pairs)

products_but_one :: Num a => [a] -> [a]
products_but_one [_] = [1]
products_but_one [a, b] = [b, a]
products_but_one l = case group l of
  Left pairs ->
    let subresults =
          products_but_one [a * b | (a, b) <- pairs]
    in do ((a, b), c) <- zip pairs subresults; [c * b, c * a]
  Right (extra, pairs) ->
    let subresult : subresults =
          products_but_one (extra : [a * b | (a, b) <- pairs])
    in subresult : do ((a, b), c) <- zip pairs subresults; [c * b, c * a]

Try it online!
How it works
This is a cleaned up version of xnor’s algorithm that deals with the odd case in a more straightforward way (edit: it looks like xnor has cleaned it up the same way):
[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc)(de)(fg), a(de)(fg), a(bc)(fg), a(bc)(de)] by recursion ↦
[(bc)(de)(fg), a(de)(fg)c, a(de)(fg)b, a(bc)(fg)e, a(bc)(fg)d, a(bc)(de)g, a(bc)(de)f]
[a, b, c, d, e, f, g, h] ↦
[ab, cd, ef, gh] ↦
[(cd)(ef)(gh), (ab)(ef)(gh), (ab)(cd)(gh), (ab)(cd)(ef)] by recursion ↦
[(cd)(ef)(gh)b, (cd)(ef)(gh)a, (ab)(ef)(gh)d, (ab)(ef)(gh)c, (ab)(cd)(gh)f, (ab)(cd)(gh)e, (ab)(cd)(ef)h, (ab)(cd)(ef)g].

"Given n numbers in an array (you can't assume they are integers), " We can't assume they are integers

O((n-2)*n) = O(n2): Trivial Solution
This is just the trivial solution that multiplies together each of the subsets:
Python
def product(array): # Requires len(array) - 1 multiplication operations
    if not array: return 1
    result = array[0]
    for value in array[1:]:
        result *= value
    return result

def getSubsetProducts(array):
    products = []
    for index in range(len(array)): # calls product len(array) times, each time calling on an array of size len(array) - 1, which means len(array) - 2 multiplication operations called len(array) times
        products.append(product(array[:index] + array[index + 1:]))
    return products

Note that this also requires n list-addition operations; not sure if that counts. If that is not allowed, then product(array[:index] + array[index + 1:]) can be replaced to product(array[:index]) * product(array[index + 1:]), which changes the formula to O((n-1)*n).

You can  add your own score to the answer.  998*1000 in this case.

Doesn't need your product function O(n) operations? one for each element in the array (althought this can easily be changed to O(n-1))

@RomanGräf True. I'll change it to O(n-1) but thanks for pointing that out.

This has been changed to [tag:atomic-code-golf]...

@EriktheOutgolfer What does that make my score now? Unless I am being blatantly stupid, don't the tag and the specs contradict each other now?

Python, 7540
A tripartite merge strategy. I think I can do even better than this, with a yet large merge. It's O(n log n).
EDIT: Fixed a miscount.
count = 0
def prod(a, b):
    if a == 1: return b
    if b == 1: return a
    global count
    count += 1
    return a * b

def tri_merge(subs1, subs2, subs3):
    total1, missing1 = subs1
    total2, missing2 = subs2
    total3, missing3 = subs3

    prod12 = prod(total1, total2)
    prod13 = prod(total1, total3)
    prod23 = prod(total2, total3)

    new_missing1 = [prod(m1, prod23) for m1 in missing1]
    new_missing2 = [prod(m2, prod13) for m2 in missing2]
    new_missing3 = [prod(m3, prod12) for m3 in missing3]

    return prod(prod12, total3), new_missing1 + new_missing2 + new_missing3

def tri_partition(nums):
    split_size = len(nums) // 3
    a = nums[:split_size]
    second_split_length = split_size + (len(nums) % 3 == 2)
    b = nums[split_size:split_size + second_split_length]
    c = nums[split_size + second_split_length:]
    return a, b, c

def missing_products(nums):
    if len(nums) == 1: return nums[0], [1]
    if len(nums) == 0: return 1, []
    subs = [missing_products(part) for part in tri_partition(nums)]
    return tri_merge(*subs)

def verify(nums, res):
    actual_product = 1
    for num in nums:
        actual_product *= num
    actual_missing = [actual_product // num for num in nums]
    return actual_missing == res[1] and actual_product == res[0]

nums = range(2, int(input()) + 2)
res = missing_products(nums)

print("Verified?", verify(nums, res))
if max(res[1]) <= 10**10: print(res[1])

print(len(nums), count)

The relevant function is missing_products, which gives the overall product and all of the ones with a missing element.

did you count the multiplications in tri_merge? Also you can replace the 2 * split_size + ... in tri_partition with split_size + split_size + ....

@RomanGräf I restructured it as per your suggestion.

C++, score: 5990, O([2NlogN]/3)
This implementation uses a binary tree look up table.  My first implementation was O(NlogN), but a last minute optimization, which looks up the product of all array elements minus a pair, + 2 multiplications saved the day. I think this could still be optimized a bit further, maybe another 16%...
I've left some debugging traces in, only because it's easier to delete them than to rewrite them :)
[Edit] the actual complexity is measured at O([2NlogN]/3) for 100.  It is actually a bit worse than O(NlogN) for small sets, but tends towards O([NlogN]/2) as the array grows very large O(0.57.NlogN) for a a set of 1 million elements.
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <random>
#include <cstdlib>

using DataType = long double;

using DataVector = std::vector<DataType>;

struct ProductTree
{
    std::vector<DataVector> tree_;
    size_t ops_{ 0 };

    ProductTree(const DataVector& v) : ProductTree(v.begin(), v.end()) {}
    ProductTree(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        Build(first, last);
    }

    void Build(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        tree_.emplace_back(DataVector(first, last));

        auto size = std::distance(first, last);
        for (auto n = size; n >= 2; n >>= 1)
        {
            first = tree_.back().begin();
            last = tree_.back().end();

            DataVector v;
            v.reserve(n);
            while (first != last) // steps in pairs
            {
                auto x = *(first++);
                if (first != last)
                {
                    ++ops_;
                    x *= *(first++); // could optimize this out,small gain
                }
                v.push_back(x);
            }
            tree_.emplace_back(v);
        }
    }

    // O(NlogN) implementation...
    DataVector Prod()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            result[i] = ProductAtDepth(i, depth);
        }
        return result;
    }

    DataType ProductAtDepth(size_t index, size_t depth)
    {
        if (depth == 0)
        {
            return ((index ^ 1) < tree_[depth].size())
                ? tree_[depth][index ^ 1]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth(index, depth - 1);
        }
        return ProductAtDepth(index, depth - 1);
    }

    // O([3NlogN]/2) implementation...
    DataVector Prod2()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)    // steps in pairs
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            auto x = ProductAtDepth2(i, depth);
            if (i + 1 < tree_[0].size())
            {
                ops_ += 2;
                result[i + 1] = tree_[0][i] * x;
                result[i] = tree_[0][i + 1] * x;
                ++i;
            }
            else
            {
                result[i] = x;
            }
        }
        return result;
    }

    DataType ProductAtDepth2(size_t index, size_t depth)
    {
        if (depth == 1)
        {
            index = (index >> 1) ^ 1;
            return (index < tree_[depth].size())
                ? tree_[depth][index]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth2(index, depth - 1);
        }
        return ProductAtDepth2(index, depth - 1);
    }

};

int main()
{
    //srand(time());

    DataVector data;
    for (int i = 0; i < 1000; ++i)
    {
        auto x = rand() & 0x3;          // avoiding overflow and zero vaolues for testing
        data.push_back((x) ? x : 1);
    }

    //for (int i = 0; i < 6; ++i)
    //{
    //  data.push_back(i + 1);
    //}

    //std::cout << "data:[";
    //for (auto val : data)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    ProductTree pt(data);
    DataVector result = pt.Prod2();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";
    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    pt.ops_ = 0;
    result = pt.Prod();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    return 0;
}

I'm adding @nore's algorithm, for completeness.  It's really nice, and is the fastest.
class ProductFlat
{
private:
    size_t ops_{ 0 };

    void InitTables(const DataVector& v, DataVector& left, DataVector& right)
    {
        if (v.size() < 2)
        {
            return;
        }

        left.resize(v.size() - 1);
        right.resize(v.size() - 1);

        auto l = left.begin();
        auto r = right.rbegin();
        auto ol = v.begin();
        auto or = v.rbegin();

        *l = *ol++;
        *r = *or++;
        if (ol == v.end())
        {
            return;
        }

        while (ol + 1 != v.end())
        {
            ops_ += 2;
            *l = *l++ * *ol++;
            *r = *r++ * *or++;
        }
    }

public:
    DataVector Prod(const DataVector& v)
    {
        if (v.size() < 2)
        {
            return v;
        }

        DataVector result, left, right;
        InitTables(v, left, right);

        auto l = left.begin();
        auto r = right.begin();
        result.push_back(*r++);
        while (r != right.end())
        {
            ++ops_;
            result.push_back(*l++ * *r++);
        }
        result.push_back(*l++);
        return result;
    }

    auto Ops() const
    {
        return ops_;
    }
};

dc, score 2994
#!/usr/bin/dc -f

# How it works:
# The required products are
#
#   (b × c × d × e × ... × x × y × z)
# (a) × (c × d × e × ... × x × y × z)
# (a × b) × (d × e × ... × x × y × z)
# ...
# (a × b × c × d × e × ... × x) × (z)
# (a × b × c × d × e × ... × x × y)
#
# We calculate each parenthesised term by
# multiplying the one above (on the left) or below
# (on the right), for 2(n-2) calculations, followed
# by the n-2 non-parenthesised multiplications
# giving a total of 3(n-2) operations.

# Read input from stdin
?

# We will store input values into stack 'a' and
# accumulated product into stack 'b'.  Initialise
# stack b with the last value read.
sb

# Turnaround function at limit of recursion: print
# accumulated 'b' value (containing b..z above).
[Lbn[ ]nq]sG

# Recursive function - on the way in, we stack up
# 'a' values and multiply up the 'b' values.  On
# the way out, we multiply up the 'a' values and
# multiply each by the corresponding 'b' value.
[dSalb*Sb
z1=G
lFx
dLb*n[ ]n
La*]dsFx

# Do the last a*b multiplication
dLb*n[ ]n

# And we have one final 'a' value that doesn't have a
# corresponding 'b':
La*n

I'm assuming that the integer comparison z1= (which terminates the recursion when we reach the last value) is free.  This is equivalent to the likes of foreach in other languages.
Demonstrations
for i in '2 3 5' '2 3 5 7' '0 2 3 5' '0 0 1 2 3 4'
do printf '%s => ' "$i"; ./127147.dc <<<"$i"; echo
done
2 3 5 => 15 10 6
2 3 5 7 => 105 70 42 30
0 2 3 5 => 30 0 0 0
0 0 1 2 3 4 => 0 0 0 0 0 0

A demo with large and small inputs:
./127147.dc <<<'.0000000000000000000542101086242752217003726400434970855712890625 1 18446744073709551616'
18446744073709551616 1.0000000000000000000000000000000000000000000000000000000000000000 .0000000000000000000542101086242752217003726400434970855712890625


text:
Help me sort out my desktop windows!
It's really frustrating when I'm working and I have a ton of windows open that are completely or partially hidden behind other windows. To make things worse, I'm still using two 1024x768 monitors.
Your task is to take a list of coordinates that designate the area, in pixels, on a screen, that a list of windows occupy and output a truthy value if, for a 2 monitor set-up with 1024x768 resolution, all the following conditions are met:

None of the windows would overlap,
None of the windows would be partly off screen
None of the windows would straddle a boundary between the two monitors (so the order in which you visualize monitors 1 and 2 is irrelevant)

And a falsey value if any of these criteria are not met.
You may assume that all windows are rectangular, and that no coordinates are negative in the input, which is in a file, in stdin, or in a list of tuples, is in the following format:
monitor-number left-x bottom-y right-x top-y
monitor-number left-x bottom-y right-x top-y
monitor-number left-x bottom-y right-x top-y

Where each line contains the ID of the monitor (which can either be in [1, 2] or [0, 1] depending on which is easier for your language), and the dimensions of a window.
For example, the following input will result in a truthy output because none of the windows overlap:
1 10 10 100 200
1 210 300 600 600
2 10 10 100 200

The following input will result in a falsey value because lines 1 and 3 result in an overlap:
1 10 10 50 50
2 5 5 600 200
1 20 20 80 80

The following input will result in a falsey value because it would partially off-screen on one of the monitors:
1 1000 400 1400 300

This is code-golf so the shortest solution wins.

Can I also take input as a list of tuples which is passed to my function?

@ThreeFx sure, let me update my post.

I suppose we are assuming that the monitor with minimum ID has its right edge aligned exactly with the left edge of the other? (My 1 and 2 are in fact the other way around :))

@JonathanAllan Sure, but either way, the criteria for truthy output is that it can't partially be on either monitor

wait - if they straddle that should yield a falsey value, even if they are not off screen?

@JonathanAllan Yes, but reading my OP again I didn't make that as explicitly clear as I should have. I'll edit my post again.

I think that could do with a test case or two too.

@JonathanAllan The final example I include would fail because it straddles the 1024x768 boundary of monitor 1, even if monitor 2 is directly to its right

I have assumed 0s are off screen, is that correct?

@JonathanAllan Since I forgot to address that when asking the question, let's say it's permissible to include or exclude 0 as a valid coordinate

Jelly, 33 bytes
<⁽¡ð,769FẠ
Ḋs2Zr/€p/;€Ḣµ€ẎµQL⁼LȧÇ

A monadic link taking a list of lists of the window-data and returning 0 if any windows exceed their monitor's space or overlap, or 1 otherwise.
Uses 1-indexed monitor IDs; 1,1 to 1024,768 inclusive are considered on-screen.
Try it online! (Too slow for the first two test cases! Typical golf :))
How?
The reason this is so slow is because it creates all the pixels for all the windows, each with its monitor ID and checks for overlap using de-duplication (which is implemented using lists not sets). It also checks each pixel is on-screen rather than checking just the input corners. All in all very inefficient...
Test-case 1 succeeded (1) locally in only eleven minutes! Test-case 2 succeeded (0) in less.
<⁽¡ð,769FẠ - Link 1 check pixels are on-screen: list of lists, each being [x,y,ID]
 ⁽¡ð       - literal base-250 integer = 1025
    ,769   - pair with literal 769
<          - less than (vectorises) -> [[x<1025, y<769, ID],...]
        F  - flatten into a single list
         Ạ - all truthy?

Ḋs2Zr/€p/;€Ḣµ€ẎµQL⁼LȧÇ - Main link: list of lists, each being [ID,Lx,By,Rx,Ty]
            µ€         - for €ach window:
Ḋ                      -   dequeue -> [Lx,By,Rx,Ty]
 s2                    -   split into twos -> [[Lx,By],[Rx,Ty]]
   Z                   -   transpose -> [[Lx,Rx],[By,Ty]]
     /€                -   reduce €ach with:
    r                  -     inclusive range -> [[Lx,...,Rx],[By,...,Ty]]
        /              -   reduce with:
       p               -     Cartesian product -> all pixels, [[Lx,By],[Lx,By+1],...[Lx,Ty],[Lx+1,By],... ...[Rx,Ty]]
           Ḣ           -   head -> ID
         ;€            -   concatenate each pixel with the monitor ID
              Ẏ        - tighten -> one list of all window's [x,y,ID] values
               µ       - monadic chain separation, call that w
                Q      - deduplicate (unique [x,y,ID] values)
                 L     - length
                   L   - length of w
                  ⁼    - equal?
                     Ç - call last link (1) as a monad (all on-screen?)
                    ȧ  - logical and

That is... equal parts horrific and amazing. I love the solution of generating each pixel and testing, but it also makes me cringe inwardly.

Yep, welcome to the golf course :p

Haskell, 103 88 bytes
f l=[]==[a|z@(m,a,b,c,d)<-l,y@(n,e,f,g,h)<-l,y/=z&&m==n&&e<c&&(b<h||f<d)||1024<c||768<d]

Forgot the bounds checking initially.
Takes input as a list of 5-tuples representing the windows.
How does it work?
We pair all windows with each other and then look at all pairs (a, b) with a /= b. Since the relation is symmetric, we only have to check whether the right end of the first and left end of the second window overlap. If they do, then for them to overlap one's lower has to be higher than the other one's top or vice versa. Lastly, we do bounds checking.
If any of the conditions are true, the list will contain more than one element, so all there is left to do is to check whether the list is empty.

You use the variable name d twice, so it fails for example for f [(2,10,10,200,2000)]. Just rename the variables inside the 5-tuple y and adjust the conditions.

@nimi Whoops, how did I not see that? Thanks, it should be fixed now!

Hmm, the first test case returns False: f [(1,10,10,100,200),(1,210,300,600,600),(2,10,10,100,200)].

@nimi I'll fix that in the morning then, it's late here. If you want to correct it, feel free to!

null is better style than []== and just as long (or short)

JavaScript (ES6), 100 bytes
a=>!a.some(([m,l,b,r,t],i)=>l<0|b<0|r>1024|t>768|a.some(([n,k,c,s,u],j)=>i!=j&m==n&l<s&b<u&r>k&t>c))

Takes input as an array of arrays. Assumes window coordinates are monitor-relative. I could save 8 bytes by assuming windows never overlap to the left of the monitor but 100 is a nice round number ;-)


text:
efficient farming
Introduction
A farmer needs help calculating the least time it will take him to pick his fruit each day.
Challenge

This farmer has X orchards.
Each orchard has Y fruits in it. If the orchard has no fruits, then it will contain the string "none".
The farmer has a list, this list contains the fruit he must pick.
The farmer will only go down the list in order
You must calculate how long it will take the farmer to pick his fruit on each day.

More on the orchards

All of the orchards are in a line.
Each orchard is exactly 1 unit away from the next and previous one.
The farmer can go up and down the line, but may not jump from one orchard to another

Input and Output
You will receive an input in the following format:
X
*string*
*string*
*string* *string* *string* *string*
*string*
//ect.
Y
*string* *string*
*string* *string*
*string* *string*
*string* *string*
//ect.

X is the number of orchards

Everything after X and before Y is an orchard containing a/some string(s), each string is a different fruit in that orchard.

Y is the number of days that the farmer must gather fruit.

Each day consists of two strings that are different fruits.
You must find what orchard these strings are in and calculate the difference.

Input Rules:

Each fruit name string will be one word with no spaces

Real Example
Still confused? Maybe this will clear it up:
Input
6

none

apple

orange pear pear

none

orange lemon pumpkin

pumpkin lettuce flowers peas

4

peas lettuce

apple orange

apple pumpkin

flowers orange

output: [ 0, 1, 3, 1 ]
Explanation
Input:

6 the number of orchards
A set of 6 orchards containing fruit, each orchard on a new line.
4 the number of days on the farmers list.
A set of 4 fruits to compare, each pair of fruits is on a new line.

Output:

Output an array of the differences between each set of fruits.
The difference between peas and lettuce is 0, because they are in the same orchard.
The difference between apples and oranges is 1 because they are one orchard apart.
The difference between apples and pumpkins is 3 Because they are three orchards apart.
The difference between flowers and oranges is 1 because they are one orchard apart.

Annotated input/output
6 orchards

a none

b apple

c orange pear pear

d none

e orange lemon pumpkin

f pumpkin lettuce flowers peas

--

4 fruits

peas lettuce 0

apple orange 1

apple pumpkin 3

flower orange 1

--

output: [ 0, 1, 3, 1 ]

How To Win
Shortest code in bytes wins.
Rules

code-golf so shortest solution in bytes wins
Standard Loopholes Apply
The meta definition of randomness applies
You may use functions as well as programs

Disclamer
I submitted this question to the sandbox, but I did not get any feedback on it, so feel free to edit as you see needed.

-1 No objective winning criteria

Good thing this went through the sandbox so this user could be informed about this before they lost rep for it. /S

You should ad the code-gold tag if this is a code-golf challenge

Create a script/function that completes the challenge. The community will decide what script/function is best. Does this mean it's a [tag:popularity-contest]?

its not code-golf. sorry my bad, I added a how to win part

Then you need to say that it's code golf. The way the challenge reads now, I think most people would assume popularity-contest

popularity contest sounds right. I just added that

Be warned that popularity contests are often closed, as they rarely have objective winning criteria.

That's a terrible use of popularity contest, tbh. Popularity Contest should only be used when another victory criterion is impossible to apply.

I highly advise making this code golf.

ok, I will make it code-golf then if that seems to be what most people think is best

Sorry about the confusion. This is now code-golf

If I was to go the function approach, would the input be one big string which has lines separated by newlines? or would the input be the lines as a string array/list?
Also, can a fruit name contain numbers? or just letters?

Yes, the input would be one big string with newlines.

Your explanation of the challenge is really confusing.  I was able to piece together what was being asked by the example test case, but users should be clear on the challenge just from the spec.  I would recommend rewriting the task.  I think one of the more confusing parts is the use of X and Y to refer to multiple different things,  however I'm not entirely sure if this is even the case.

176 bytes, Python 3
def p(a):l=[b.split()for b in a.split('\n')];X=int(l[0][0]);return[min(y-x for y in range(X)for x in range(y+1)if z[0]in l[x+1]+l[y+1]and z[1]in l[x+1]+l[y+1])for z in l[X+2:]]

This can be called by passing in the entire content as a string
p("""6
none
apple
orange pear pear
none
orange lemon pumpkin
pumpkin lettuce flowers peas
4
peas lettuce
apple orange
apple pumpkin
flowers orange""")

Ungolfed solution
def problem(a):
    # this will split on new line, and split each individual line into it's own list
    lines=[b.split()for b in a.split('\n')]
    # get the number of orchards
    X=int(lines[0][0])
    return[
        # get the minimum of all possible differences
        min(y-x # subtract y and x to get the difference
            for y in range(X) # for each orchard, y
                for x in range(y+1) # and each orchard up to y inclusive, x
                    if z[0] in lines[x+1]+lines[y+1] and z[1] in lines[x+1]+lines[y+1]) # if both fruits exist the x and y orchards
        # for every day (z is a list containing 2 fruits as string)
        for z in lines[X+2:]
    ]

153 bytes: def p(a):l=[*map(str.split,a.split('\n'))];X=int(l[0][0]);return[min(y-x for y in range(X)for x in range(y+1)if{*z}<=set(l[x+1]+l[y+1]))for z in l[X+2:]]

Java 10, 307 298 288 280 273 271 bytes
s->{String[]a=s.split("\\d"),o=a[1].split("\n"),f=a[2].split("\n");int r[]=new int[f.length-1],q=-2,d,i,j,z;for(var p:f)if(++q>=0)for(z=d=o.length,i=0;++i<d;)for(j=0;o[i].contains((f=p.split(" "))[0])&++j<z;)r[q]=d=o[j].contains(f[1])?Math.min(i>j?i-j:j-i,d):d;return r;}

-19 bytes thanks to @ceilingcat.
Explanation:
Try it here.
s->{                           // Method with String parameter & integer-array return
  String[]a=s.split("\\d"),    //  Split the input on numbers
          o=a[1].split("\n"),  //  List of orchards
          f=a[2].split("\n");  //  List of pairs (later on reused for individual pair of fruits)
  int r[]=new int[f.length-1], //  Result integer-array
      q=-2,d,i,j,z;            //  Some temp integers
  for(var p:f)                 //  Loop `p` over the pairs:
    if(++q>=0){                //   If this isn't the first iteration of the pair-loop
                               //   (the first item is always empty after `.split("\\d")`)
      for(z=d=o.length,i=0;++i<d;)
                               //    Inner loop `i` over the orchards:
        for(j=0;o[i].contains((f=p.split(" "))[0])
                               //     If the current orchard contains the first fruit of the pair:
                &++j<z;)       //      Inner loop `j` over the orchards again:
          r[q]=                //       Add the following to the resulting array:
               d=o[j].contains(f[1])?
                               //       If the current orchard contains the second fruit of the pair:
                 Math.min(     //        Take the minimum of:
                   i>j?i-j:j-i,//         The absolute difference between `i` and `j`
                   d)          //         And the current integer of the array
               :               //       Else:
                d;             //        Leave the current integer unchanged
  return r;}                   //  Return the result array

@ceilingcat Thanks. Sometimes I'm surprised simple golfs like that are still in my answers. XD Then again, this is an answer from 2017.

JavaScript (ES6), 224 bytes
a=>(d=a.split('\n')).slice(e=+d[0]+2).map(f=>{p=e;for(g=(q=(t,s=0)=>d.slice(1,e-1).map(b=c=>c.split(' ')).findIndex((x,y)=>y>=t&x.includes(b(f)[s])))(0);++g;g=q(g))for(l=q(0,1);++l;l=q(l,1))p=p<(u=g>l?g-l:l-g)?p:u;return p})

Call with "6\nnone\napple\norange pear pear\nnone\norange lemon pumpkin\npumpkin lettuce flowers peas\n4\npeas lettuce\napple orange\napple pumpkin\nflowers orange"

Röda, 118 bytes
{A=[head(parseInteger(pull()))|splitMany|enum]pull n;split|{f={|x|A|[_2]if[x in _1]}f a|{|i|f b|abs i-_}_|min}for a,b}

Explanation:
{
    A=[
        /* Pull line, convert to integer, and read that many lines */
        head(parseInteger(pull()))|
        /* Split all lines to arrays */
        splitMany|
        /* Enumerate, ie. give each line a number */
        enum
    ]
    /* Discard one line */
    pull n;
    /* Split each following line and push words to the stream */
    split|
    /* For each word a, b in the stream: */
    {
        /* Helper function to find lines that contain x */
        f={|x|A|[_2]if[x in _1]}
        /* Push numbers of lines that contain the first word to the stream */
        f a|
        /* For each line number i */
        {|i|
            /* Push numbers of lines that contain the second word to the stream */
            f b|
            /* Push the difference of two line numbers to the stream */
            abs i-_
        }_|
        /* Push the smallest difference to the stream */
        min
    }for a,b
}

No TIO link yet, as the TIO version of Röda is outdated.