text:
The Missing Number Revised
Background:
I originally posted this question last night, and received backlash on its vagueness. I have since consulted many personnel concerning not only the wording of the problem, but also its complexity (which is not O(1)). This programming problem is an evil spin on an Amazon interview question.
Question:
Given a String of randomly concatenated integers [0, 250), 0 to 250 exclusive, there is ONE number missing in the sequence. Your job is to write a program that will calculate this missing number. There are no other missing numbers in the sequence besides the one, and that is what makes this problem so difficult, and possibly computationally hard.
Doing this problem by hand on smaller Strings, such as examples 1 and 2 below are obviously very easy. Conversely, computing a missing number on incredibly large datasets involving three-digit or four-digit numbers would be incredibly difficult. The idea behind this problem is to construct a program that will do this process FOR you.
Important Information:
One thing that appeared as rather confusing when I posted this problem last night was: what exactly a missing number is defined as. A missing number is the number INSIDE of the range specified above; NOT necessarily the digit. In example 3, you will see that the missing number is 9, even though it appears in the sequence. There are 3 places the DIGIT 9 will appear in a series of [0, 30): “9”, “19”, and “29”. Your objective is to differentiate between these, and discover that 9 is the missing NUMBER (inside of example 3). In other words, the tricky part lies in finding out which sequences of digits are complete and which belong to other numbers.
Input:
The input is a String S, containing integers from 0 to 249 inclusive, or 0 to 250 exclusive (in other words, [0, 250)). These integers, as stated above, are scrambled up to create a random sequence. There are NO delimiters (“42, 31, 23, 44”), or padding 0’s (003076244029002); the problems are exactly as described in the examples. It is guaranteed that there is only 1 solution in the actual problems. Multiple solutions are not permitted for these.
Winning Criteria:
Whoever has the fastest, and lowest memory usage will be the winner. In the miraculous event that a time ties, lower memory will be used for the time breaker. Please list Big O if you can!
Examples:
Examples 1 and 2 have a range of [0, 10)
Examples 3 and 4 have a range of [0, 30)
(Examples 1-4 are just for demonstration. Your program needn't to handle them.)
Examples 5 has a range of [0, 250)
1. 420137659
- Missing number => 8

2. 843216075
- Missing number => 9

3. 2112282526022911192312416102017731561427221884513
- Missing number => 9

4. 229272120623131992528240518810426223161211471711
- Missing number => 15

5. 11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025
- Missing number => 71

Test Data:

Problem 1: 6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102

Problem 2: 14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219

Problem 3: 1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144

Problem 4: 2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851

Clarification: I see you tagged [tag:fastest-algorithm], but it's a bit unclear in the description. is this challenge [tag:fastest-algorithm] (as in, lowest time complexity) or [tag:fastest-code] (as in, taking least amount of time on a particular machine)?

Also, must the program support any values of N, not just 250? / What about the 232 issue? All possibilities or one any? I realize that you knew about that issue, but I find it unclear in the question. / If this is [tag:fastest-code] there must be a way to measure them. Of course running on a supercomputer is different from running on an old computer. / Because no one said that, -- Welcome to PPCG!

Ah, I was wondering what had happened, welcome back! I think the case remains that some problems might have multiple solutions.

Why are the examples have different ranges, but the question specify fixed range (250)? Which one do you want?

250 is what I want; I was using the others to DEMONSTRATE the idea. Nevertheless, the problem has been solved in Java and C++.

And once again, there is only ONE number missing; it's impossible to have multiple solutions.

The program should be capable of solving N = 250.

@JoshuaCrotts Let's continue discussing in the chatroom.

This is a fascinating problem, but (at least according to the answers thus far) is too trivial to get enough computational complexity to be able to meaningfully differentiate between the answers to determine a winner, which is a bummer.

@AdmBorkBork, you are correct... I'm excited to see the solutions though! I do apologize for there not being enough clarity to determine a true WINNER; in all honesty, I just wanted to see if this problem was solvable.

@JoshuaCrotts you could always raise N to, say, 1000 or 10000.

@Ourous But wouldn't that invalidate some answers? Would I need to repost the question?

@JoshuaCrotts as far as I can tell, all the current answers either take N as an argument or have it in a variable, which would require almost no change. None have methods dependent on a certain bound of N.

@Ourous should I just repost the question? Or should I update it? If I want people to get a fair chance/actually SEE the post, would updating it bump it?

I think, I found an instance which is fairly regular, but seems to be difficult to solve for the programs I've tried (clingo + cpp).  Maybe someone can confirm its validity and the results.

@politza My (fixed) clingo program solves it in ≈ 0.03 seconds, and clingo -n0 (compute all models) validates that 231 is the only solution.

@JoshuaCrotts Is there an unstated assumption that no number is repeated (so 23456789100 must parse as 2, …, 9, 10, 0 rather than 2, …, 9, 1, 0, 0)?

@Anders Kaseorg That is correct; none of the numbers are repeated.

@JoshuaCrotts Great (please edit in this clarification though).

Clingo, ≈ 0.03 seconds
This is too fast to be accurately measured—you’ll need to allow larger input cases rather than artificially stopping at 250.
% cat(I) means digits I and I+1 are part of the same number.
{cat(I)} :- digit(I, D), digit(I+1, E).

% prefix(I, X) means some digits ending at I are part of the same
% number prefix X.
prefix(I, D) :- digit(I, D), not cat(I-1), D < n.
prefix(I, 10*X+D) :- prefix(I-1, X), digit(I, D), cat(I-1), X > 0, 10*X+D < n.

% Every digit is part of some prefix.
:- digit(I, D), {prefix(I, X)} = 0.

% If also not cat(I), then this counts as an appearance of the number
% X.
appears(I, X) :- prefix(I, X), not cat(I).

% No number appears more than once.
:- X=0..n-1, {appears(I, X)} > 1.

% missing(X) means X does not appear.
missing(X) :- X=0..n-1, {appears(I, X)} = 0.

% Exactly one number is missing.
:- {missing(X)} != 1.

#show missing/1.

Example input
Input is a list of (k, kth digit) pairs.  Here is problem 1:
#const n = 250.
digit(0,6;1,9;2,6;3,6;4,4;5,1;6,0;7,8;8,1;9,9;10,6;11,1;12,0;13,5;14,2;15,1;16,5;17,3;18,0;19,2;20,9;21,1;22,3;23,6;24,8;25,3;26,4;27,9;28,6;29,8;30,2;31,3;32,0;33,9;34,2;35,1;36,7;37,5;38,9;39,8;40,5;41,7;42,0;43,5;44,9;45,2;46,0;47,1;48,1;49,8;50,7;51,2;52,0;53,2;54,2;55,4;56,8;57,2;58,0;59,1;60,8;61,3;62,1;63,2;64,2;65,2;66,0;67,2;68,4;69,1;70,2;71,4;72,6;73,9;74,1;75,1;76,2;77,9;78,8;79,9;80,1;81,3;82,3;83,1;84,7;85,4;86,1;87,9;88,7;89,2;90,1;91,9;92,2;93,0;94,7;95,1;96,8;97,2;98,1;99,7;100,3;101,1;102,3;103,7;104,1;105,8;106,0;107,8;108,0;109,8;110,5;111,7;112,2;113,3;114,2;115,1;116,7;117,7;118,1;119,3;120,4;121,2;122,3;123,2;124,4;125,8;126,1;127,5;128,5;129,1;130,0;131,2;132,0;133,0;134,1;135,0;136,1;137,1;138,2;139,5;140,1;141,9;142,1;143,7;144,2;145,6;146,5;147,2;148,0;149,3;150,1;151,6;152,3;153,1;154,1;155,1;156,3;157,7;158,9;159,1;160,1;161,0;162,5;163,1;164,2;165,2;166,1;167,1;168,6;169,3;170,1;171,9;172,4;173,5;174,8;175,1;176,5;177,3;178,2;179,4;180,4;181,2;182,6;183,1;184,5;185,8;186,2;187,1;188,3;189,5;190,5;191,1;192,0;193,0;194,9;195,0;196,2;197,3;198,5;199,1;200,1;201,6;202,1;203,3;204,9;205,6;206,1;207,1;208,6;209,4;210,1;211,2;212,6;213,7;214,6;215,9;216,1;217,1;218,4;219,1;220,6;221,7;222,9;223,6;224,1;225,2;226,2;227,1;228,5;229,2;230,2;231,2;232,6;233,6;234,0;235,1;236,1;237,2;238,1;239,2;240,7;241,4;242,2;243,1;244,3;245,2;246,1;247,9;248,0;249,1;250,8;251,6;252,2;253,0;254,4;255,1;256,8;257,2;258,7;259,7;260,4;261,5;262,1;263,0;264,6;265,5;266,2;267,2;268,4;269,3;270,7;271,2;272,0;273,8;274,3;275,6;276,2;277,0;278,6;279,2;280,2;281,7;282,1;283,6;284,8;285,4;286,6;287,4;288,0;289,4;290,3;291,8;292,1;293,7;294,4;295,3;296,1;297,5;298,7;299,3;300,8;301,1;302,3;303,5;304,6;305,4;306,1;307,1;308,7;309,1;310,6;311,9;312,9;313,5;314,1;315,0;316,4;317,2;318,1;319,0;320,1;321,5;322,1;323,9;324,9;325,1;326,2;327,8;328,2;329,3;330,9;331,8;332,8;333,1;334,4;335,4;336,2;337,2;338,4;339,2;340,3;341,8;342,2;343,3;344,6;345,1;346,2;347,1;348,2;349,3;350,1;351,7;352,1;353,6;354,3;355,1;356,4;357,9;358,2;359,3;360,2;361,8;362,3;363,9;364,2;365,3;366,3;367,8;368,2;369,3;370,4;371,1;372,8;373,9;374,1;375,5;376,4;377,4;378,7;379,1;380,4;381,2;382,1;383,6;384,2;385,7;386,7;387,1;388,4;389,1;390,2;391,0;392,9;393,2;394,4;395,9;396,2;397,1;398,4;399,1;400,9;401,8;402,7;403,5;404,2;405,1;406,7;407,1;408,0;409,9;410,1;411,7;412,1;413,2;414,2;415,3;416,5;417,4;418,1;419,5;420,6;421,1;422,3;423,1;424,4;425,6;426,6;427,2;428,1;429,6;430,5;431,1;432,5;433,0;434,6;435,1;436,8;437,1;438,2;439,2;440,7;441,3;442,1;443,4;444,0;445,1;446,3;447,0;448,2;449,4;450,0;451,1;452,7;453,0;454,9;455,7;456,2;457,1;458,8;459,1;460,1;461,7;462,6;463,1;464,7;465,9;466,1;467,6;468,6;469,5;470,3;471,1;472,7;473,8;474,1;475,8;476,5;477,1;478,1;479,5;480,2;481,1;482,7;483,8;484,2;485,2;486,5;487,2;488,4;489,2;490,1;491,9;492,2;493,4;494,4;495,5;496,1;497,4;498,7;499,2;500,2;501,9;502,9;503,9;504,1;505,6;506,1;507,3;508,5;509,1;510,5;511,9;512,1;513,1;514,1;515,2;516,2;517,2;518,2;519,3;520,4;521,1;522,9;523,1;524,8;525,7;526,8;527,6;528,2;529,1;530,6;531,9;532,3;533,1;534,2;535,0;536,1;537,3;538,1;539,2;540,4;541,1;542,5;543,0;544,6;545,7;546,2;547,3;548,7;549,1;550,4;551,3;552,2;553,0;554,5;555,1;556,1;557,9;558,2;559,5;560,1;561,0;562,7;563,2;564,4;565,3;566,5;567,6;568,1;569,7;570,2;571,2;572,8;573,2;574,4;575,7;576,1;577,9;578,5;579,1;580,3;581,8;582,1;583,6;584,0;585,1;586,2;587,4;588,1;589,5;590,1;591,8;592,4;593,1;594,0;595,3;596,1;597,8;598,4;599,1;600,4;601,2;602,1;603,1;604,2;605,1;606,2;607,8;608,7;609,0;610,9;611,4;612,1;613,1;614,1;615,1;616,8;617,3;618,3;619,1;620,9;621,3;622,1;623,4;624,5;625,1;626,2;627,3;628,2;629,4;630,5;631,1;632,8;633,8;634,1;635,0;636,2).

Example output
$ clingo missing.lp problem1.lp
clingo version 5.2.2
Reading from missing.lp ...
Solving...
Answer: 1
missing(148)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.032s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.032s

This solution seems to give a false answer in many cases, e.g. 45879362100 with n = 11 and 1 missing (answers missing(0)).

@politza Fixed. Should I also add the unstated assumption that no number is repeated (else missing(10) is also valid)?

I'm still getting false results, e.g. on this instance.

Would you mind writing one or two sentences about the ideas behind your model ?

@politza Right, it turns out the given tests do rely on the above unstated assumption, so I’ve added it. The revised program gives a unique result on your instance too. (But I would still appreciate if the assumption were stated explicitly in the question.)

I see now what you meant and  would prefer that assumption.  Thanks for the added comments.

C++, 5000 random test cases in 6.1 seconds
This is practically fast, but there may exist some testcases that make it slow. Complexity unknown.
If there are multiple solutions, it will print them all. Example.
Explanation:

Count the occurrences of digits.
List all possible answers.
Check if a candidate is a valid answer:
3-1. Try to split the string(s) by numbers which only occur once and mark it as identified, except the candidate.For example, 2112282526022911192312416102017731561427221884513 has only one 14, so it can be split into 211228252602291119231241610201773156 and 27221884513.
3-2. If any split string has length 1, mark it as identified.If any contradiction is made (identified more than once), the candidate is not valid.If we cannot find the candidate in the string, the candidate is valid.
3-3. If any split is made, repeat step 3-1. Otherwise, do a brute force search to check if the candidate is valid.

#include <cmath>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

const int VAL_MAX = 250;
const int LOG_MAX = log10(VAL_MAX - 1) + 1;
using bools = std::bitset<VAL_MAX>;

std::pair<size_t, size_t> count(const std::string& str, const std::string& target)
{
    size_t ans = 0, offset = 0, pos = std::string::npos;
    for (; (offset = str.find(target, offset)) != std::string::npos; ans++, pos = offset++);
    return std::make_pair(ans, pos);
}

bool dfs(size_t a, size_t b, const std::vector<std::string>& str, bools& cnt, int t)
{ // input: string id, string position, strings, identified, candidate
    if (b == str[a].size()) a++, b = 0;
    if (a == str.size()) return true;   // if no contradiction on all strings, the candidate is valid

    int p = 0;
    for (int i = 0; i < LOG_MAX; i++) { // assume str[a][b...b+i] is a number
        if (str[a].size() == b) break;
        p = p * 10 + (str[a][b++] ^ '0');
        if (p < VAL_MAX && !cnt[p] && p != t) { //if no contradiction
            cnt[p] = true;
            if (dfs(a, b, str, cnt, t)) return true; // recursively check
            cnt[p] = false;
        }
    }
    return false;
}

struct ocr {
    int l, r, G;
    bool operator<(const ocr& i) const { return l > i.l; }
};

int cal(std::vector<std::string> str, bools cnt, int t)
{ // input: a list of strings, whether a number have identified, candidate
  // try to find numbers that only occur once in those strings
    int N = str.size();
    std::vector<ocr> pos;

    for (int i = 0; i < VAL_MAX; i++) {
        if (cnt[i]) continue;             // try every number which haven't identified
        int flag = 0;
        std::string target = std::to_string(i);
        ocr now;
        for (int j = 0; j < N; j++) {     // count occurences
            auto c = count(str[j], target);
            if ((flag += c.first) > 1) break;
            if (c.first) now = {c.second, c.second + target.size(), j};
        }
        if (!flag && t == i) return true; // if cannot find the candidate, then it is valid
        if (i != t && flag == 1) pos.push_back(now), cnt[i] = true;
        // if only occur once, then its position is fixed, mark as identified
    }
    if (!pos.size()) { // if no number is identified, do a brute force search
        std::sort(str.begin(), str.end(), [](const std::string& a, const std::string& b){return a.size() < b.size();});
        return dfs(0, 0, str, cnt, t);
    }

    std::sort(pos.begin(), pos.end());
    std::vector<std::string> lst;
    for (auto& i : pos) {      // split strings by identified numbers
        if ((size_t)i.r > str[i.G].size()) return false;
        std::string tmp = str[i.G].substr(i.r);
        if (tmp.size() == 1) { // if split string has length 1, it is identified
            if (cnt[tmp[0] ^ '0']) return false; // contradiction if it is identified before
            cnt[tmp[0] ^ '0'] = true;
        }
        else if (tmp.size()) lst.push_back(std::move(tmp));
        str[i.G].resize(i.l);
    }
    for (auto& i : str) { // push the remaining strings; same as above
        if (i.size() == 1) {
            if (cnt[i[0] ^ '0']) return false;
            cnt[i[0] ^ '0'] = true;
        }
        else if (i.size()) lst.push_back(std::move(i));
    }
    return cal(lst, cnt, t); // continue the split step with new set of strings
}

int main()
{
    std::string str;
    std::vector<ocr> pos;
    std::vector<int> prob;
    std::cin >> str;

    int p[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    for (int i = 0; i < VAL_MAX; i++)
        for (char j : std::to_string(i)) p[j ^ '0']++;
    for (char i : str) p[i ^ '0']--; // count digit occurrences
    {
        std::string tmp;
        for (int i = 0; i < 10; i++)
            while (p[i]--) tmp.push_back(i ^ '0');
        do {           // list all possible candidates (at most 4)
            int c = std::stoi(tmp);
            if (c < VAL_MAX && tmp[0] != '0') prob.push_back(c);
        } while (std::next_permutation(tmp.begin(), tmp.end()));
    }
    if (prob.size() == 1) { std::cout << prob[0] << '\n'; return 0; }
                       // if only one candidate, output it
    for (int i : prob) // ... or check if each candidate is valid
        if (cal({str}, bools(), i)) std::cout << i << '\n';
}

Try it online!

Clean, ~0.3s
Fixed a huge bug in the algorithm, need to re-optimize it now.
module main
import StdEnv
import StdLib
import System.CommandLine

maxNum = 250
sample = "11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025"
case1 = "6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102"
case2 = "14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219"
case3 = "1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144"
case4 = "2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851"

failing = "0102030405060708090100101102103104105106107108109110120130140150160170180190200201202203204205206207208209210220230240249248247246245244243242241239238237236235234233232229228227226225224223222221219218217216215214213212211199198197196195194193192191189188187186185184183182181179178177176175174173172171169168167166165164163162161159158157156155154153152151149148147146145144143142141139138137136135134133132131129128127126125124123122121119118117116115114113112111999897969594939291898887868584838281797877767574737271696867666564636261595857565554535251494847464544434241393837363534333231292827262524232221191817161514131211987654321"

dupes = "19050151158951391658227781234527110196235731198137214733126868520474181772192213718517314542182652441211742304719519143231236593134207203121171237201705111617211824810013324511511436253946122155201534113626129692410611318356178791080921122151321949681166200188841675156120546124912883216212189712281541382202411041372421642917614416870223753814121124318415710310515010682172099012716167102179894920613516297239186222232225635312262134019719915382229399107111802082341491811011604815220291125247641482401691871755205639495788414314011714616366130175601931092467744819271230159131158714761192105218019822421812423322919341426216523821428232"

:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, [Digits])

numbers :: [[Char]]
numbers = [fromString (toString n) \\ n <- [0..(maxNum-1)]]

candidates :: [Char] -> [[Char]]
candidates chars
    = moreCandidates chars []
where
    moreCandidates :: [Char] [[Char]] -> [[Char]]
    moreCandidates [] nums
        = removeDup (filter (\num = isMember num numbers) nums)
    moreCandidates chars []
        = flatten [moreCandidates (removeAt i chars) [[c]] \\ c <- chars & i <- [0..]]
    moreCandidates chars nums
        = flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num <- nums ]] \\  c <- chars & i <- [0..]]

singletonSieve :: Complete -> Complete
singletonSieve (list, sequence)
    | (list_, sequence_) == (list, sequence)
        = reverseSieve (list, sequence)
    = (list_, sequence_)
where
    singles :: Numbers
    singles
        = filter (\(_, i) = length i == 1) list
    list_ :: Numbers
    list_
        = [(a, filter (\n = not (isAnyMember n (flatten [flatten b_ \\ (a_, b_) <- singles | a_ <> a]))) b) \\ (a, b) <- list]
    sequence_ :: [Digits]
    sequence_
        = foldr splitSequence sequence (flatten (snd (unzip singles)))

reverseSieve :: Complete -> Complete
reverseSieve (list, sequence)
    # sequence
        = foldr splitSequence sequence (flatten (snd (unzip singles)))
    # list
        = [(a, filter (\n = not (isAnyMember n (flatten [flatten b_ \\ (a_, b_) <- singles | a_ <> a]))) b) \\ (a, b) <- list]
    # list
        = [(a, filter (\n = or [any (isPrefixOf n) (tails subSeq) \\ subSeq <- map (snd o unzip) sequence]) b) \\ (a, b) <- list]
    = (list, sequence)
where
    singles :: Numbers
    singles
        = [(a, i) \\ (a, b) <- list, i <- [[subSeq \\ subSeq <- map (snd o unzip) sequence | isMember subSeq b]] | length i == 1]

splitSequence :: Position [Digits] -> [Digits]
splitSequence split sequence
    = flatten [if(isEmpty b) [a] [a, drop (length split) b] \\ (a, b) <- [span (\(_, i) = not (isMember i split)) subSeq \\ subSeq <- sequence] | [] < max a b]

indexSubSeq :: [Char] Digits -> Positions
indexSubSeq _ []
    = []
indexSubSeq a b
    # remainder
        = indexSubSeq a (tl b)
    | startsWith a b
        = [[i \\ (_, i) <- take (length a) b] : remainder]
    = remainder
where
    startsWith :: [Char] Digits -> Bool
    startsWith _ []
        = False
    startsWith [] _
        = False
    startsWith [a] [(b,_):_]
        = a == b
    startsWith [a:a_] [(b,_):b_]
        | a == b
            = startsWith a_ b_
        = False

missingNumber :: String -> [[Char]]
missingNumber string
    # string
        = [(c, i) \\ c <-: string & i <- [0..]]
    # locations
        = [(number, indexSubSeq number string) \\ number <- numbers]
    # digits
        = [length (indexSubSeq [number] [(c, i) \\ c <- (flatten numbers) & i <- [0..]]) \\ number <-: "0123456789"]
    # missing
        = (flatten o flatten) [repeatn (y - length b) a \\ y <- digits & (a, b) <- locations]
    # (answers, _)
        = hd [e \\ e <- iterate singletonSieve (locations, [string]) | length (filter (\(a, b) = (length b == 0) && (isMember a (candidates missing))) (fst e)) > 0]
    # answers
        = filter (\(_, i) = length i == 0) answers
    = filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)

Start world
    # (args, world)
        = getCommandLine world
    | length args < 2
        = abort "too few arguments\n"
    = flatlines [foldr (\num -> \str = if(isEmpty str) num (num ++ [',' : str]) ) [] (missingNumber arg) \\ arg <- tl args]

Compile with clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
This works by taking every number the string has to contain, and counting the number of places the required digit sequence is present in the string. It then repeatedly does these steps:

If number has no possible positions, that's the answer
Remove every number with one possible position (call these singles)
Remove every position from all remaining numbers which overlaps with any positions from the previously removed numbers (the singles)

Running a program with the input hard-coded may be a questionable way to benchmark this: what if the compiler optimizes away the entire computation and writes a binary that merely prints a precomputed result? (I don’t know whether the Clean compiler is quite that smart, but I’ve heard good things about it.)

You... have a very good point. I've checked and it is doing exactly that. I'll amend the answer.

Do you know if it’s possible to get this working on TIO? (My attempt)

@AndersKaseorg Not currently, I'm still working with Dennis on getting all the libraries working with TIO. You can find the context starting about here. Basically, at the moment, if it needs more than StdEnv + Dynamics, it won't work.

Running it locally, I get “multiple solutions” on the given problem 2. (Also, 2 microseconds is a suspicious running time—are you sure you didn’t mean milliseconds? I get about 4 milliseconds per case on my laptop when providing many cases as arguments to a single execution.)

@AndersKaseorg fixed

@Ourous What happens if the set of singles in step 2 of your algorithm is empty ?

@politza It breaks. I didn't run into a case where that happened in about 1000 test runs so I suspect it won't. However, if you find one, tell me what it is so I can fix it.

It does, e.g. in this instance.  Alternatively, raise the limit and it should become obvious fairly quickly.

@politza Thanks, I'll get right on that :)

I'm curious whether there exists a better algorithm compared to brute-forcing all alternative assignments (of non-singles).

@politza There is. I was stuck on it until you found a test case that failed this one, but once I fix it I'll be able to finish the performant one and post it to the other question.

@politza Fixed it now.

@Οurous So, how'd you solve it ?

Rust
Port of @Colera Su's C++ answer in Rust.
\$   \color{red} {\text{But I made some mistakes, the result of the rust code is not correct.}}  \$
\$   \color{red} {\text{variable `prob` seems to be consistent, the logic that produces `prob` seems to be consistent.
}}  \$
Any help would be appreciated.
Try it online!
use std::collections::HashMap;
use std::cmp::Ordering;

// const VAL_MAX: usize = 250;
// const LOG_MAX: f64 = (VAL_MAX as f64 - 1.0).log10() + 1.0;
const VAL_MAX: usize = 250;
const LOG_MAX: usize = 3;

struct Ocr {
    l: usize,
    r: usize,
    g: usize,
}

impl PartialEq for Ocr {
    fn eq(&self, other: &Self) -> bool {
        self.l == other.l
    }
}

impl Eq for Ocr {}

impl PartialOrd for Ocr {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Ocr {
    fn cmp(&self, other: &Self) -> Ordering {
        other.l.cmp(&self.l)
    }
}

fn count(s: &str, target: &str) -> (usize, usize) {
    let mut count = 0;
    let mut last_index = 0;
    let mut offset = 0;

    while let Some(index) = s[offset..].find(target) {
        count += 1;
        offset += index + target.len();
        last_index = offset;
    }

    (count, last_index)
}

fn dfs(a: usize, mut b: usize, strs: &Vec<String>, cnt: &mut HashMap<usize, bool>, t: usize) -> bool {
    if b == strs[a].len() {
        b = 0;
        if a + 1 == strs.len() {
            return true;
        }
    }

    let mut p = 0;
    for _ in 0..LOG_MAX as usize {
        if strs[a].len() == b {
            break;
        }
        p = p * 10 + (strs[a].as_bytes()[b] as usize - b'0' as usize);
        b += 1;
        if p < VAL_MAX && !*cnt.entry(p).or_insert(false) && p != t {
            cnt.insert(p, true);
            if dfs(a, b, strs, cnt, t) {
                return true;
            }
            cnt.insert(p, false);
        }
    }
    false
}

fn cal(str: Vec<String>, mut cnt: HashMap<usize, bool>, t: usize) -> bool {
    let mut pos = Vec::new();

    for i in 0..VAL_MAX {
        if cnt.get(&i).unwrap_or(&false).clone() {
            continue;
        }
        let target = i.to_string();
        let mut flag = 0;
        let mut now = Ocr { l: 0, r: 0, g: 0 };
        for (j, str) in str.iter().enumerate() {
            let c = count(str, &target);
            flag += c.0;
            if flag > 1 {
                break;
            }
            if c.0 > 0 {
                now = Ocr { l: c.1, r: c.1 + target.len(), g: j };
            }
        }
        if flag == 0 && t == i {
            return true;
        }
        if i != t && flag == 1 {
            pos.push(now);
            cnt.insert(i, true);
        }
    }

    if pos.is_empty() {
        let mut str = str.clone();
        str.sort_by(|a, b| a.len().cmp(&b.len()));
        return dfs(0, 0, &str, &mut cnt, t);
    }

    pos.sort();
    let mut lst = Vec::new();
    let mut str = str.clone();
    for i in pos {
        if i.r > str[i.g].len() {
            return false;
        }
        let tmp = str[i.g][i.r..].to_string();
        if tmp.len() == 1 {
            let value = tmp.as_bytes()[0] as usize - b'0' as usize;
            if *cnt.get(&value).unwrap_or(&false) {
                return false;
            }
            cnt.insert(value, true);
        } else if !tmp.is_empty() {
            lst.push(tmp);
        }
        str[i.g].truncate(i.l);
    }
    for i in str {
        if i.len() == 1 {
            let value = i.as_bytes()[0] as usize - b'0' as usize;
            if *cnt.get(&value).unwrap_or(&false) {
                return false;
            }
            cnt.insert(value, true);
        } else if !i.is_empty() {
            lst.push(i);
        }
    }
    cal(lst, cnt, t)
}

fn main() {
    let mut str = String::new();
    std::io::stdin().read_line(&mut str).unwrap();
    let str = str.trim().to_string();

    let mut p = vec![0; 10];
    for i in 0..VAL_MAX {
        for j in i.to_string().chars() {
            p[j as usize - '0' as usize] += 1;
        }
    }
    for i in str.chars() {
        p[i as usize - '0' as usize] -= 1;
    }

    let mut tmp = String::new();
    for i in 0..10 {
        for _ in 0..p[i] {
            tmp.push((i as u8 + b'0') as char);
        }
    }
    let mut prob = Vec::new();
    loop {
        let c = tmp.parse::<usize>().unwrap();
        if c < VAL_MAX && tmp.chars().next().unwrap() != '0' {
            prob.push(c);
        }
        let mut tmp_bytes = tmp.into_bytes();
        if !tmp_bytes.next_permutation() {
            break;
        }
        tmp = String::from_utf8(tmp_bytes).unwrap();
    }

    println!("{:?}",prob);

    if prob.len() == 1 {
        println!("\n the result is: {:?}", prob[0]);
        return;
    }
    for i in prob {
        if cal(vec![str.clone()], HashMap::new(), i) {
            println!("\n the result is: {:?}", i);
        }
    }
}

pub trait NextPermutation {
    fn next_permutation(&mut self) -> bool;
}

impl<T> NextPermutation for [T]
where
    T: Ord,
{
    fn next_permutation(&mut self) -> bool {
        if self.len() < 2 {
            return false;
        }

        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] >= self[i] {
            i -= 1;
        }

        if i == 0 {
            return false;
        }

        let mut j = self.len() - 1;
        while j >= i && self[j] <= self[i - 1] {
            j -= 1;
        }

        self.swap(j, i - 1);
        self[i..].reverse();

        true
    }
}


text:
Enumerate all possible grids of integers with constraints
Problem
Consider a square 3 by 3 grid of non-negative integers.  For each row i the sum of the integers is set to be r_i.  Similarly for each column j the sum of integers in that column is set to be c_j.
The task is to write code to enumerate all possible different assignments of integers to the grid given the row and column sum constraints. Your code should output one assignment at a time.
Input
Your code should take 3 non-negative integers specifying the row constraints and 3 non-negative integers specifying the column constraints. You can assume that these are valid, i.e. that the sum or row constraints equals the sum of column constraints. Your code can do this in any way that is convenient.
Output
Your code should output the different 2d grids it computes in any human readable format of your choice. The prettier the better of course. The output must not contain duplicate grids.
Example
If all the row and column constraints are exactly 1 then there are only 6 different possibilities. For the first row you can put a 1 in any of the first three columns, for the second row there are now 2 alternatives and the last row is now completely determined by the previous two.  Everything else in the grid should be set to 0.
Say the input is 2 1 0 for the rows and 1 1 1 for the columns. Using APL's lovely output format, the possible integers grids are:
┌─────┬─────┬─────┐
│0 1 1│1 0 1│1 1 0│
│1 0 0│0 1 0│0 0 1│
│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┘

Now say the input is 1 2 3 for the rows and 3 2 1 for the columns. The possible integer grids are:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 1│0 0 1│0 0 1│0 1 0│0 1 0│0 1 0│0 1 0│1 0 0│1 0 0│1 0 0│1 0 0│1 0 0│
│0 2 0│1 1 0│2 0 0│0 1 1│1 0 1│1 1 0│2 0 0│0 1 1│0 2 0│1 0 1│1 1 0│2 0 0│
│3 0 0│2 1 0│1 2 0│3 0 0│2 1 0│2 0 1│1 1 1│2 1 0│2 0 1│1 2 0│1 1 1│0 2 1│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

APL (Dyalog), 42 bytes
{o/⍨(⍵≡+/,+⌿)¨o←3 3∘⍴¨(,o∘.,⊢)⍣8⊢o←⍳1+⌈/⍵}

Try it online!
Uses ⎕IO←0 which is default on many systems. The other stuff in the header is just pretty printing for the matrices (boxed display).
Input is list of six values, rows sums first, then column sums.
How?
o←⍳1+⌈/⍵ - o gets the range 0 to the maximum (⌈/) of input
,o∘.,⊢ - cartesian product with o and flatten (,)
⍣8 - repeated for eight times
3 3∘⍴¨ - shape every 9-items list into a 3×3 matrix
¨o← - save these matrices to o, and for each
+/,+⌿ - check if the rows sums (+/) concatenated to the column sums (+⌿)
⍵≡ - correspond with the input
o/⍨ - filter o (the matrices array) by truthy values

This very nice looking answer needs an explanation (please).

@Lembik added explanation

Thanks. So you enumerate all possible matrices and check those that fit the constraints it seems.  Not the most efficient, but it works.

@Lembik yup, that's the shortest. I could manage a bit more efficient one by getting all 3-items lists that can match the sums, then choose the ones that fits the first row sum then choose the ones (for each of the previous combinations) that matches the first columns sum, and so on back and forth. That would be the non-brute-force general algorithm.

@EriktheOutgolfer thanks, I always forget to update my byte count

@Uriel (,o∘.,⊢)⍣8⊢o←⍳ ... -> ⍳9⍴ ...

Husk, 20 17 bytes
fȯ=⁰mΣS+Tπ3π3Θḣ▲⁰

-3 bytes thanks to @H.PWiz
Takes input as a list xs encoding the constraints [r_1,r_2,r_3,c_1,c_2,c_3], try it online!
Explanation
Brute force approach :P Generate all 3x3 grids with entries [0..max xs]:
f(=⁰mΣS+T)π3π3Θḣ▲⁰  -- input ⁰, for example: [1,1,1,1,1,1]
                ▲⁰  -- max of all constraints: 1
               ḣ    -- range [1..max]: [1]
              Θ     -- prepend 0: [0,1]
            π3      -- 3d cartesian power: [[0,0,0],...,[1,1,1]]
          π3        -- 3d cartesian power: list of all 3x3 matrices with entries [0..max] (too many)
f(       )          -- filter by the following predicate (eg. on [[0,0,1],[1,0,0],[0,1,0]]):
      S+            --   append to itself, itself..: [[0,0,1],[1,0,0],[0,1,0],..
        T           --   .. transposed:             ..[0,1,0],[0,0,1],[1,0,0]]
      mΣ            --   map sum: [1,1,1,1,1,1]
    =⁰              --   is it equal to the input: 1

Brachylog, 17 bytes
{~⟨ṁ₃{ℕᵐ+}ᵐ²\⟩≜}ᶠ

Try it online!
WARNING: UGLY OUTPUT! Don't frick out, it's still human-readable, I'm not required to account for how much. ;)
For some reason it has to be much longer than what I'd expect to make sense (13 bytes):
⟨ṁ₃{ℕᵐ+}ᵐ²\⟩ᶠ

This latter version, if it worked, would have taken input from the output (i.e. command-line argument) instead.

@Riker Read the "Output" section of the OP. Sure, it still has brackets separating the grids, it could've stripped them as well and the output would still have not lost any data...

Python 2, 149 145 142 141 138 136 bytes
lambda s:[i for i in product(range(max(sum(s,[]))+1),repeat=9)if[map(sum,(i[j:j+3],i[j/3::3]))for j in 0,3,6]==s]
from itertools import*

Try it online!
Takes input as a list of lists: [[r1, c1], [r2, c2], [r3, c3]]

Haskell, 94 88 84 79 bytes
q=mapM id.(<$"abc")
f r=[k|k<-q$q$[0..sum r],(sum<$>k)++foldr1(zipWith(+))k==r]

Takes the sums of the rows and columns as a single flat 6-element list [r1,r2,r3,c1,c2,c3].
Try it online!
q=mapM id.(<$"abc")         -- helper function

f r =                       --
  [k | k <-   ,    ]        -- keep all k
    q$q$[0..sum r]          --   from the list of all possible matrices with
                            --   elements from 0 to the sum of r
                            -- where
    (sum<$>k) ++            --   the list of sums of the rows followed by
    foldr1(zipWith(+))k     --   the list of sums of the columns
    == r                    -- equals the input r

As the elements of the matrices to test go up to the sum of r, the code does not finish in reasonable time for large row/column sums. Here's a version that goes up to the maximum of r which is faster, but 4 bytes longer: Try it online!

Mathematica, 81 bytes
Select[0~Range~Max[s=#,t=#2]~g~3~(g=Tuples)~3,(T=Total)@#==s&&T@Transpose@#==t&]&

finds all 3x3 matrices with elements 0..Max and selects the right ones
this means that (Max+1)^9 matrices have to be checked
Try it online!

Could you add an explanation please.

@Lembik I will, after you add some test cases and make this challenge "clear" for all the people here.I voted to reopen but you don't seem to try to make this any better for all those who need help

Added to the question now.

What is still unclear? / Grid also work with TIO, using ToString. Try it online!

@user202729 nothing to me, but test cases were missing

R, 115 110 bytes
function(S)for(m in unique(combn(rep(0:max(S),9),9,matrix,F,3,3)))if(all(c(rowSums(m),colSums(m))==S))print(m)

Try it online!
Takes input as c(r1,r2,r3,c1,c2,c3), a single vector, and prints the matrices to stdout.
It's quite similar to Uriel's APL answer, but it generates the 3x3 grids somewhat differently.
Letting M=max(S), it generates the vector 0:M, then repeats it 9 times, i.e., [0..M, 0...M, ..., 0...M] nine times. Then it selects all combinations of that new vector taken 9 at a time, using matrix, 3, 3 to convert each 9-combination into a 3x3 matrix, and forcing simplify=F to return a list rather than an array. It then uniquifies this list and saves it as m.
Then it filters m for those where row/column sums are identical to the input, printing those that are and doing nothing for those that aren't.
Since it computes choose(9*(M+1),9) different possible grids (more than the (M+1)^9 possibilities), it'll run out of memory/time faster than the more efficient (but less golfy) answer below:
R, 159 bytes
function(S,K=t(t(expand.grid(rep(list(0:max(S)),9)))))(m=lapply(1:nrow(K),function(x)matrix(K[x,],3,3)))[sapply(m,function(x)all(c(rowSums(x),colSums(x))==S))]

Try it online!

R is very welcome!

MATL, 35 22 bytes
-13 bytes thanks to Luis Mendo
X>Q:q9Z^!"@3et!hsG=?4M

Try it online!
Link is to a version of the code that prints a little more nicely; this version will just print all the matrices with a single newline between them.
Takes input as [c1 c2 c3 r1 r2 r3].
Obviously, this computes the cartesian power X^ of 0...max(input) with exponent 9, and transposing !. It then loops " over the columns, reshaping each @ as a 3x3 matrix 3e, duplicating t, transposing !, and horizontally concatenating them h. Then it computes the column sums s, which will result in the vector [c1 c2 c3 r1 r2 r3]. We do elementwise equality to the input G=, and if ? all are nonzero, we recover the correct matrix by selecting the input to the function ! by using 4M.

Batch, 367 bytes
@echo off
for /l %%i in (0,1,%1)do for /l %%j in (%%i,1,%1)do for /l %%k in (%%i,1,%4)do call:c %* %%i %%j %%k
exit/b
:c
set/a"a=%1-%8,c=%4-%9,f=%8-%7,g=%9-%7,l=%5-f,m=%2-g,l^=m-l>>31&(m^l),m=%5+c-%3-f,m&=~m>>31
for /l %%l in (%m%,1,%l%)do set/a"b=%2-g-%%l,d=%5-f-%%l,e=%6-a-b"&call:l %7 %%l
exit/b
:l
echo %1 %f% %a%
echo %g% %2 %b%
echo %c% %d% %e%
echo(

The top left 2×2 square forces the result, so the best approach is to generate all values for the top left integer, all valid values for the sum of the top left and top middle integer, all valid values for the sum of the top left and middle left integer, and calculate the range of valid values for the middle integer, then, having looped through all the appropriate ranges, calculate the remaining values from the constraints.

Python 2, 118 bytes
def f(v,l=[],i=0):n=len(l);V=v*1;V[~n/3]-=i;V[n%3]-=i;return[l][any(V):]if n>8else V*-~min(V)and f(V,l+[i])+f(v,l,i+1)

Try it online!

Python 2, 123 bytes
V=input()
n=max(V)+1
for k in range(n**9):
 m=[];exec"m+=[k%n,k/n%n,k/n/n%n],;k/=n**3;"*3
 if map(sum,m+zip(*m))==V:print m

Try it online!

source: Stack Exchange

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

sort: votes


text:
Pour me a drink, will you?
The Challenge
I am thirsty and need a drink, but I don't know what to order. Your task is to provide me with either a drink or options for one.
I/O
Input will be either a base or a drink name.
If given a base, your program should output one random drink from a list of drinks with that base.
If given a drink name, your program should output the base that drink is made from.
Below is a list of drink names, ordered by their bases:
Absinthe:
    Death in the Afternoon
    Earthquake
    Green Russians
    Green Vesper
    Moloko Plus

Beer:
    Black and Tan
    Black Velvet
    Boilermaker
    Michelada
    Irish Car Bomb

Brandy:
    B&B
    Brandy Alexander
    French Connection
    Horse's Neck
    Sidecar

Cachaça:
    Caipirinha
    Leite de Onça
    Quentão
    Rabo-de-Galo
    Royce

Gin:
    Bramble
    Casino
    Clover Club Cocktail
    Gin Fizz
    Martini

Rum:
    Bacardi
    Cuba Libre
    Daiquiri
    El Presidente
    Piña Colada

Tequila:
    El Toro Loco
    Margarita
    Matador
    Paloma
    Tequila Sunrise

Vodka:
    Black Russian
    Bloody Mary
    Cosmopolitan
    Kamikaze
    Screwdriver

Whiskey:
    Bourbon Lancer
    Irish Coffee
    Manhattan
    Rusty Nail
    Whiskey Sour

Rules:

Standard Loopholes are forbidden.
If given a base, the program's output should be non-deterministic, meaning that multiple runs should result in different outputs.
Accordingly, when given a drink name, the program's output should be deterministic, yielding the same result for drinks with the same base.
You may assume the input will always be one of the bases or drink names in the list compiled above.
You may choose to print characters such as ç, ñ and ã as c, n and a, respectively.
You may accept I/O in any reasonable format.
This is a code-golf challenge, so the shortest answer (in bytes) wins.

Test Cases:
Input:                    Output (Any one of the following):
Absinthe                  Death in the Afternoon
                          Earthquake
                          Green Russians
                          Green Vesper
                          Moloko Plus

Beer                      Black and Tan
                          Black Velvet
                          Boilermaker
                          Michelada
                          Irish Car Bomb

Brandy                    B&B
                          Brandy Alexander
                          French Connection
                          Horse's Neck
                          Sidecar

Cachaça                   Caipirinha
                          Leite de Onça
                          Quentão
                          Rabo-de-Galo
                          Royce

Gin                       Bramble
                          Casino
                          Clover Club Cocktail
                          Gin Fizz
                          Martini

Rum                       Bacardi
                          Cuba Libre
                          Daiquiri
                          El Presidente
                          Piña Colada

Tequila                   El Toro Loco
                          Margarita
                          Matador
                          Paloma
                          Tequila Sunrise

Vodka                     Black Russian
                          Bloody Mary
                          Cosmopolitan
                          Kamikaze
                          Screwdriver

Whiskey                   Bourbon Lancer
                          Irish Coffee
                          Manhattan
                          Rusty Nail
                          Whiskey Sour

Likewise, the input can be any of the drink names in the output column. If so, the output should be the corresponding base.

From the Sandbox

@HyperNeutrino sure, no problem. Those are common in my language, so I think I just put them there automatically hahahah. I'll update the rules to account for that.

@HyperNeutrino, kinda weird that a language that consists almost exclusively of Unicode characters can't handle Unicode characters...

Damn now I want a drink at it's only 10am

Python 3, 693 690 686 687 bytes
Yeah, naive approach. I tried some compression methods, and this one seems to be the shortest.
-2 bytes thanks to HyperNeutrino.
EDIT: Bug fixed.
import random
v="Absinthe$Death in the Afternoon$Earthquake$Green Russians$Green Vesper$Moloko Plus$Beer$Black and Tan$Black Velvet$Boilermaker$Michelada$Irish Car Bomb$Brandy$B&B$Brandy Alexander$French Connection$Horse's Neck$Sidecar$Cachaca$Caipirinha$Leite de Onca$Quentao$Rabo-de-Galo$Royce$Gin$Bramble$Casino$Clover Club Cocktail$Gin Fizz$Martini$Rum$Bacardi$Cuba Libre$Daiquiri$El Presidente$Pina Colada$Tequila$El Toro Loco$Margarita$Matador$Paloma$Tequila Sunrise$Vodka$Black Russian$Bloody Mary$Cosmopolitan$Kamikaze$Screwdriver$Whiskey$Bourbon Lancer$Irish Coffee$Manhattan$Rusty Nail$Whiskey Sour".split('$');a=v.index(input());print(v[a-a%6if a%6else random.randint(1,5)+a])

Try it online!

Thanks to the new rules you can save some bytes by getting rid of the accents.

637 bytes using Python 2 and string compression

Jelly, 356 bytes
“%³“¥;ġŀṭṢDṡỌµ“Ñçḥ“)ụ_ƥÐ¬“(OE⁼Ọ“"³Ḟ'×ɱA8“tẊ“ßDæj|t³G“z⁸ƈƲe“¦¿¶“ßṆÑẆṇ8“©ŒẓġṾɠ×“¢(°“⁶oI“¬ĿḤẈX“ṫ°^iɱ“ıịṣXṆẠL“3!ṁ“©VṢ“¦ƈœƘNd]¶mḄœ“Ðv4WṁḌạYÐġȯḣɼ“¢ḅuɼḶŒß“AṠḍ*ɦ)!Ḷ¿µʋ“¡pK“¡ȯL“¦uż“¬5;“¥I¢q9ḅḋĖ“µ>Ƥøŀ“ ØÐ“¤^(“¡Il“£Ḅ#ṫ$⁽ø“€Uy“"ƭ/4¢ṫ“ƬƒN⁼A6+EẈṆ“8ɠ¹“½oŒLụ}ɗ“µṡ⁴“½Çj“€g©“ÆḄ²zị'“¥¹j“þk¥ÆṢ“C⁼ṭ¬'“¿®ı“÷Ụ;“1ṂY“?]ʂ“¢ȥ4Ɗh⁺“Œ\ẒƘḳ“µċ$“¦ʋȷ[Ɱ“¡?ƓṚĠk»
¢i³
¢_¢’¤%6¤¤¢+5X¤¤¢%6¤’¤?ị1£

Try it online!
Formula stolen from Colera Su but I think I can get it shorter in Jelly using a Jelly-mindset approach.
¢_¢

PHP, 681 680 676 661 646+1 bytes
gz version:
<?=($x=explode)(_,$x(X,strstr($d=gzinflate(base64_decode("RZHBbtswDIZfhaft1IeI3TYblnRZEmS6CbTM1IRlMqXkbs7Tj9lS7CCQBH6Sn36uusJSBwqPhHUAFvACVudKJqoSn9Dq8DbjSHFtRAL7uRRGKffyROVCFreadVTY5bmEhsjCltNAGXuMTcY0AkoPR5R7daL8TjU2ypls8uEWvxqXAVo0aHTqQmPesYTmUxP/pbDK9NsTlz4bSXKtilCq7JRf1Ap9LvBCaYwH7imhhRbTgAk98oWNZcC4Ia4EPcF3SRh/zCQVNe6x04eeHtaYvdAlUViz3B488/Uat+4BC99Api5TbNE909hmfSeDNs+ds6SxIuewn6fQ+FbrObZzh7Dhzig+Ir/NDhF3LOjqv848ZdgZFceVSuFIrsj4EeEwi1tCN9VRTWGjSW8or2hc0bOKvVrcOfSE4aT9iKHJqm6Vq5a70/dzxVbLpBfN3irxkIx+9caOH7/hxCNeKfwcuIy0fEQ46Gx+odk6FdigpP9H0vOZyAnc0nqb50vqAi/+/z8")),$argn.X))[1])[rand()%5]?:array_slice($x(X,strstr($d,$argn,1)),-2)[0];

strtr version, 676 661+1 bytes
<?=($x=explode)(_,$x(X,strstr($d=strtr("Abs4theXDeath 4 the Aft2noon_E5thquake_Green Russi0s_Green Vesp2_Moloko PlusXBe2XMiche7da1 0d T01 Velvet_Boil2mak2_I8sh C5 BombXBr0dyXB&B_Br0dy Alex0d2_French Connection_Horse's Neck_Sidec5XCachacaXCaipi8nha_Leite de Onca_Quentao_Rabo-de-Galo_RoyceXG4XG4 Fizz9rt4i_Bramble_Cas4o_Clov2 Club CocktailXRumXBac5di_Cuba Libre_Daiqui8_P4a Co7da_El Presidente66 Sun8se_El Toro Loco9rg5ita9tador_PalomaXVodkaXBloody M5y1 Russi0_Cosmopolit0_Screwd8v2_Kamikaze33 Sour_Bourbon L0c2_I8sh Coffee9nhatt0_Rusty Nail",[an,_Black,er,XWhiskey,in,ar,XTequila,la,ri,_Ma]),$argn.X))[1])[rand()%5]?:array_slice($x(X,strstr($d,$argn,1)),-2)[0];

Run as pipe with -nF or try it online. Requires PHP 7.

Python 2, 640 bytes
import random as r
def f(s):d="eJw9Ucty2zAM/BWc2lPwD5by6tRJXNvjniEKjjCiAAek0tpfXyij6UlYanexXG66IloHxnumOoAoBIDNubKrmeIDeR0+ZhoZn5xZYT+XIqRlhScuF3Z8sWyjwS7PBRuOgyZTGoG0hyPpik6cP7liY5LZp7AMnaSBM/WEP1zKAC05NDZ12Hhor9h8a9YRNpn/xhCiR2dNwTVVTlUi5bN54e8FXjmNeJCeEzm2lAZKFF+5iIsOhFuWytAzvGn8+DWzVjLcU2d3Pd89UQ5g1xR3FV32Tl3m0EdFhm22T3Zo89zF6jRWkrzw4FFuN3yJnkQF9/OETWz1XrCdO4KtdB7tknzMEQIfMuycS0TUyrgTpTD7KuDIwci0MI7mBltLtti+k0ulmCr15riLkNN/NhxmjeIYT9aPtPa8PlEgsyguPK7YWpnsYjmsFH/SJCPdGA/J+U/vEhfD34OUkaNym70zhS1piuP1Xex8Zo4Q0WJdLGJHvcLr0sEqhEMI/wHq6dVM".decode('base64').decode('zip').split('.');i=d.index(s);print d[[i+r.randint(1,5),i/6*6][i%6>0]]

Try it online!

Use from random import* instead of import random as r, and omit the r. from r.randint, so it will save you 1 byte

PHP, 628 bytes
Stealing the best ideas from others... thanks for the inflate trick
<?$d=explode("|",gzinflate(base64_decode("PVHLctswDPwVnHrLR1hqHp06iWt73DNEwRVGFOCAVBp78Lc99Nw/KNTR9CQstbtYLjddYakD+WfCOgALBIDNuZKJqvg9Wh3eZhzJH41IYD+XwihlhScqFzJ/1qyjwi7PxRuKgyZjGgGlhyPKik6U36l6o5zJprAMHaeBMvboX4zLAC0aNDp13lhor958atYRNpk+YgjRg5Gk4KoIpcqR8kmtEBR4oTT6gXtKaN5iGvA3xpcvbCwD+pa4EvQErxI/vs0k9Zf6Hju96+nuEXMAvaa4K8uyd+oyhT4qUm+zvpNBm+cuVqexIueFBw98u/lz9MTCvp8nbzDW9+zt3CFsubNoF/ltjhB+n2FnVCKiVPId/8Ew+1fAkYKRcWEc1RS2mnSx/YHGFWOq2Kv5LkJO/9lwmCWKIz9pP+La8/pEgVSjuPC4eqtl0ovmsBL/ihOPeCM/JKOfvXFczL8PXEaKynW2TgW2KCmO13fR85koQkSLdbGIHfUKL0sHqxAOIfwL")));$i=array_search($argv[1],$d);echo($i%6)?$d[$i-$i%6]:$d[$i+rand(1,5)];

You are wasting 22-1 bytes. But nice idea. Try <?=($d=explode(_,gzinflate(...)))[($i=array_flip($d)[$argn])-($i%6?:-rand(1,5)]; with -nF and _ as separator instead of |.

Charcoal, 381 375 bytes
≔⪪”}⊞J'%↓B+K…↙ZＱαyε↘¶⎚\`⟲≧↑lⅉ＆⬤↖ΦüY⁹←‖⧴p×OＣ∧⊗F]±⊗✳Ｎ″ⅈ✳c∕lü,Π438↖⍘✳⍘⁷N⪪ςz↨Ｄ″≦«p¶↧⟦¬²◨▶↗⪫/_"b8n↨À⊙ρ≡1#▶UD⸿no,7φ²↘↑r‴m⪪pＷ⭆mC↥#pP″νr↧″h[κznβd6qυ:*…KC⪫⌈⸿＆DΣεＸMω⊙⟧↔Ｌ↓;?ü↶σ⁵%Ｆ⊙⪫:ＱD*)⊞↥$Ｘ4.⎆V\`″Ｎb5βς｜…5¤⁴↘⊗｜%À⭆)⬤,⁻f»Ｄh…{“ [ＷＦ⸿⊗$ς«8RbγＺ5gv⮌⟲Π\`XcρO≦3；2{§³Ｑψt‹ＳY⪫ς⦃Ｄ⪫⎚TO⁼Ｎ⊗Ｅ⁺ζt≕·´H|›gＰＯＷkＫ⁶³⧴\`⁶Ａ⊟ⅈ✂&)ξ↧εβ%ιSΦＹ\`»ＸＷV⁸｜∧Ａ▷RE⍘Zα#÷Þ~↙{﹪ÞqＳＫ[μO\`It›▷≕ρ≔⊘Jc◨;Ｚm�～8″⟲Ｐ↶S⎆2×”#δ≔⌕δθπ§δ⁻π∨﹪π⁶±⊕‽⁵

Try it online!
A port to Charcoal of Colera Su's answer. Link is to the verbose version of the code. I could not test some of the cases because Charcoal considers French Connection as two different inputs...

6 bytes saved thanks to Neil!

Print(AtIndex(d,-(p,Or(Modulo(p,6),Negate(++(Random(5)))))); saves you a few bytes. Also, to stop Charcoal splitting on spaces, either a) append a trailing newline b) wrap the input in a list i.e. ["French Connection"].

@Neil if you omit the last ; of your Print statement, the deverbosifier omits a ¦ at the end of the code and you can save one more byte.

I guess that works... I always hate having to remove commas and semicolons though. (I need to remember to ask @ASCII-only to allow a ; before else...)

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


text:
Advent Challenge 6: Transport Dock Relabeling!
<< Prev Next >>
Thanks to the PPCG community, Santa managed to sort his presents into the correct order for moving into the transportation dock. Unfortunately, the transportation dock signs are broken so he doesn't know where to put all the presents! The presents are all grouped together and not by their ranges, which Santa admits would have been a better idea.
Now, given the presents in the sorted order, determine all possible minimal range configurations that would result in the present being in the correct order. That is, find all minimal range configurations such that sorting the presents according to the algorithm in Challenge #5 would not change the order.
Challenge
A minimal range configuration is a list of ranges such that the ranges are each as small as possible. That is, if a range is designated to cover a specific subset of presents, then the minimum and maximum of the range must be the same as that of the subset. In other words, shrinking any range in the cover would cause it to no longer be a cover.
The challenge is to find all possible minimal range configurations that would apply to the present sizes. Let's take an example: [3, 1, 2, 5, 4, 7, 6]
There is a trivial case, which is to take the range of the entire present configuration. In this case, [[1, 7]] would be a solution.
For examples with unique elements, another trivial case would be [[3], [1], [2], [5], [4], [7], [6]] (because the ranges don't need to be ordered).
For this example, we also see that [[1, 3], [4, 7]] and [[1, 3], [4, 5], [6, 7]] would work, as well as [[1, 3], [5], [4], [6, 7]] and [[1, 3], [4, 5], [7], [6]].
The final answer for [3, 1, 2, 5, 4, 7, 6] would be [[[3], [1], [2], [5], [4], [7], [6]], [[3], [1], [2], [5], [4], [6, 7]], [[3], [1], [2], [4, 5], [7], [6]], [[3], [1], [2], [4, 5], [6, 7]], [[3], [1], [2], [4, 7]], [[3], [1, 2], [5], [4], [7], [6]], [[3], [1, 2], [5], [4], [6, 7]], [[3], [1, 2], [4, 5], [7], [6]], [[3], [1, 2], [4, 5], [6, 7]], [[3], [1, 2], [4, 7]], [[1, 3], [5], [4], [7], [6]], [[1, 3], [5], [4], [6, 7]], [[1, 3], [4, 5], [7], [6]], [[1, 3], [4, 5], [6, 7]], [[1, 3], [4, 7]], [[1, 5], [7], [6]], [[1, 5], [6, 7]], [[1, 7]]].
Formatting Specifications
The input will be given as a flat list of positive integers within your language's reasonable supported number range in any reasonable format. The input may contain duplicate elements. The output should be given as a 3D list of positive integers in any reasonable format.
Each range in your output (which is at the second layer) can be represented either as [min, max], [num] if it's a single-value range, or as the entire range itself, but your output format must be consistent. Please specify if you wish to use a slightly different reasonable output format.
Duplicate values must be covered by a single range in the output; that is, no two ranges in the output may have any overlap.
Your solution may return the ranges in any order and this does not have to be deterministic.
Rules

Standard Loopholes Apply
This is code-golf so the shortest answer in bytes wins
No answer will be accepted

Test Case for a list with duplicate elements:
2 3 2 4 -> [[[2, 3], [4]], [[2, 4]]]

Reference Implementation
The header is the link.
Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site
You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.
Happy golfing!

Mathematica, 106 bytes
sSelect[MinMax/@s~TakeList~#&/@Join@@Permutations/@IntegerPartitions@Tr[1^s],Unequal@@Join@@Range@@@#&]

Try it online!
Martin saved 16 bytes

Brachylog, 17 16 bytes
{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ

Works on lists with duplicates as well.
Ranges are represented by the lists of elements they contain.
Try it online!
Explanation
The idea is to break the list into blocks and transform the blocks into ranges, then verify that they don't overlap.
{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ  Input is a list.
{             }ᶠ  Compute all possible outputs for this predicate:
 ~c                Break the list into contiguous blocks.
   ⟨    ⟩ᵐ         For each block,
    ⌋  ⌉           take its minimum and maximum,
     ⟦₂            and create the range between them.
          .        This is the output.
           c       Also, if you concatenate the output,
            ≠      its elements are distinct.
             ∧     Prevent the interpreter from thinking this is also the output.

JavaScript (ES6), 166 164 bytes
Edit: updated version that now supports duplicates
Prints the results directly to the console in [min, max] format.
f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

Test cases

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

consoleLog = console.log;
console.log = s => consoleLog(JSON.stringify(s))

consoleLog('Test case: [3, 1, 2, 5, 4, 7, 6]')
f([3, 1, 2, 5, 4, 7, 6])
consoleLog('Test case: [2, 3, 2, 4]')
f([2, 3, 2, 4])

Pyth, 17 bytes
f{IsTmm}hSkeSkd./

Try it here!
Now that's much better. Outputs the whole ranges. See the revision history for the previous version (at a staggering 31 bytes).
How it works

f{IsTmm}hSkeSkd./  ~> Full program.

               ./  ~> List partition.
     m             ~> Map using a variable d.
      m       d    ~> Map over d using a variable k.
        hSk        ~> The minimum of k.
           eSk     ~> The maximum of k.
       }           ~> Inclusive integer range.
f                  ~> Filter those...
   sT              ~> Which, when flattened,
 {I                ~> Are invariant over deduplication.

Python 2, 179 bytes
lambda l:[l for l in[[range(min(x),max(x)+1)for x in P]for P in p(l)]if len(sum(l,[]))==len(set(sum(l,[])))]
p=lambda l:[[l[:i]]+a for i in range(1,len(l))for a in p(l[i:])]+[[l]]

Try it online!
Outputs a list of full ranges.
Heavily inspired by the reference implementation.
Builds all partitions, then ranges of min/max for each partition. A list of ranges is valid if no value appears more than once in the list.

sum(l,[]) flattens a list of lists, and allows me to check for duplicates:
l=[[1, 2], [2, 3]]
sum(l,[]) = [1,2,2,3]
len([1,2,2,3] == len(set([1,2,2,3]))  -> False (duplicates)


text:
Happiness is Mandatory
If you're sad, that's wrong. We need to scrub out ALL sadness.
This is a sad face, for reference:
  ......
  .S..S.
 ........
 ...SS...
..SS..SS..
.S......S.
 ........

Where S is a consistent pixel, . is any pixel other than S, and   is any pixel. Note that the sad face is not a perfect square, only the . should be considered. Theoretical sad face overlap in the corners is possible, but overwriting one sad face has a chance to eliminate the other, e.g. if it was in a . character and is overwritten with an S.
Input
An image, in any acceptable format. I would recommend a color matrix.
Output
The same image, but take all those treasonous sad faces and replace their S characters with randomized data. The data should be either random RGB values, or values taken from the palette of the image. You just need to have a nonzero probability of all outputs; you do not need to make it uniform.
Rules

S can be any pixel, as long as it's the same pixel throughout the formation.
Remove ALL sad faces. If the removal makes a new sad face, then remove that too.
You should only modify S pixels. Unauthorized modification of pixels is insubordination, punishable by disqualification.
The shortest answer in bytes wins.

Test Cases
These have one sad face each:

This has 2 sad faces, on the left and right:

This has 2 sad faces overlapping:

This has 2 sad faces, in the top-left and bottom-right; the bottom-left and top-right have S characters in the place of . characters:

Why not replace all pixels with white pixels?

@anatolyg because then it won't be replacing it with randomized data. also, if i make a sad face that's black-on-white and then run it through this program, it will still look like a sad face as long as enough of the randomized data is dark enough :p

@StephenLeppik doesn't this work? https://pastebin.com/T8mYQx8B To clarify: I meant overlap the square boundary, not the happy face itself

@Riker oh, yeah that would be acceptable.

@Riker it's open now; you can post your solution.

C (gcc), 339 337 331  323 bytes

Saved two eight fifteen sixteen bytes thanks to ceilingcat.

C,a,l,A,m,i,t,o,u,s;n(e,z,Z)int*e;{for(C=1;C;C+=i)for(C=s=0;s<Z;s++)for(u=0;u<z;u++)if(u>8&s>5)for(m=e[~-u+~-s*z],A=i=1;++A<4;)for(o=0;o<7;o++)for(t=0;t<10;t++)a=e[l=u+t-9+(s+o-6)*z],(o-1||t-3&&t-6)*(o-3||t<4|5<t)*(o-4||t<2|3<t&t<6|7<t)*(o-5||t-1&&t-8)?o>1|t>1&t<8&o<2|o>3&o<6|t&&t<9&&(i*=a-m):A<3?i*=a==m:i?e[l]=rand():e;}

Try it online!

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


text:
Half-Exponential Function
A half-exponential function is one which when composed with itself gives an exponential function. For instance, if f(f(x)) = 2^x, then f would be a half-exponential function. In this challenge, you will compute a specific half-exponential function.
Specifically, you will compute the function from the non-negative integers to the non-negative integers with the following properties:

Monotonically increasing: if x < y, then f(x) < f(y)
At least half-exponential: For all x, f(f(x)) >= 2^x
Lexicographically smallest: Among all functions with the above properties, output the one which minimizes f(0), which given that choice minimizes f(1), then f(2), and so on.

The initial values of this function, for inputs 0, 1, 2, ... are:
[1, 2, 3, 4, 8, 9, 10, 11, 16, 32, 64, 128, 129, 130, 131, 132, 256, 257, ...]
You may output this function via any of the following methods, either as a function or as a full program:

Take x as input, output f(x).
Take x as input, output the first x values of f.
Infinitely output all of f.

If you want to take x and output f(x), x must be zero indexed.
Reference implementation
This is code golf - shortest code in bytes wins. Standard loopholes are banned, as always.

seems definition is not verified for 0 : f(f(0)) = f(1) = 2 but 2^0 = 1

and for 1 :  f(f(1)) = f(2) = 3 but 2^1 = 2

@NahuelFouilleul the requirement is f(f(x)) >= 2^x.

Should we submit to OEIS?

JavaScript (ES7), 51 48 bytes
Saved 3 bytes thanks to @Arnauld
f=i=>i?f[f[q=f(i-1),r=f[i]||q+1]=(i>1)<<i,i]=r:1

Takes in n and outputs the n'th item in the sequence.

JavaScript (ES7), 70 68 64 bytes
f=(n,a=[],q=1)=>n?f(n-1,a,(n=2**a.indexOf(a.push(q)))<++q?q:n):a

A recursive function that takes in x and returns the first x items of the sequence as an array.
How it works
The array a is procedurally generated, one item at a time, until it reaches the desired length. (A port of the infinite technique used in xnor's excellent Python answer would likely be shorter.)
We can make the following observation for each index i (0-indexed):

If i exists as an item in a at index j (a[j] = i), then a[i] needs to be at least 2j.

This is true because f(f(j)) needs to be at least 2j, and f(f(j)) is equivalent to a[a[j]], which is in turn equivalent to a[i].
Normally the correct option is exactly 2j. However, for the singular case i = 2, 2 exists in the array at index j = 1, which means that 2j would be 2—but this means that we would have 2 at both a[1] and a[2]. To get around this, we take the maximum of 2j and a[i-1] + 1 (one more than the previous item), which gives 3 for i = 2.
This technique also happens to take care of deciding whether or not j exists—if it doesn't, JS's .indexOf() method returns -1, which leads to taking the max of a[i-1] + 1 and 2-1 = 0.5. Since
all items in the sequence are at least 1, this will always return the previous item plus one.
(I'm writing this explanation late at night, so please let me know if something is confusing or I missed anything)

Note that inputs 272 and up give incorrect answers due to integer overflow issues. This is fine, as it works up to the limit of the datatype.

Use 2** instead of 1<< hopefully fix the problem.

Now the .99 kills the solution. But why using +.99 and not just +.9? What's the difference?

@user202729 I feel like an idiot--that was left in there from a previous version where I was using Math.log2(...) and had to calculate the ceiling. Now it's not needed at all. Thanks! I'll look into the 2** thing--I was using 2**...+.99|0 originally, but 1<< was shorter because I didn't need the |0. Now I think there's no difference...

Python 2, 60 bytes
d={};a=n=1
while 1:print a;a=d.get(n,a+1);d[1%n*a]=2**n;n+=1

Try it online!
Prints forever.

Python, 61 bytes
f=lambda n,i=2:n<1or(i>=n)*-~f(n-1)or(f(i)==n)<<i or f(n,i+1)

Try it online!
A function. Outputs True in place of 1.

Perl 5, 53 + 1 (-p) = 54 bytes
$\=$_>0;map$a[$\=$a[$_]?2**$a[$_]:$\+1]=$_,++$\..$_}{

Try it online

Bash, 66 bytes
for((r=$1?2:1,i=2;i<=$1;i++));{ a[r=a[i]?2**a[i]:r+1]=$i;};echo $r

Try it online

Jelly, 14 bytes
iL’2*»Ṁ‘$ṭ
⁸Ç¡

Try it online!
How it works
⁸Ç¡         Main link. No arguments.

⁸           Set the left argument and the return value to [].
 Ç¡         Read an integer n from STDIN and call the helper link n times, first on
            [], then on the previous result. Return the last result.

iL’2*»Ṁ‘$ṭ  Helper link. Argument: A (array)

 L          Take the length of A. This is the 0-based index of the next element.
i           Find its 1-based index in A (0 if not present).
  ’         Decrement to a 0-based index (-1 if not present).
   2*       Elevate 2 to the 0-based index.
      Ṁ‘$   Take the maximum of A and increment it by 1.
            Note that Ṁ returns 0 for an empty list.
     »      Take the maximum of the results to both sides.
         ṭ  Tack (append) the result to A.

Python 2, 111 bytes
def f(x):
 a=range(1,2**x)
 for i in range(1,x):a[i]=max(a[i],a[i-1]+1);a[a[i]]=max(a[a[i]],2**i)
 return a[:x]

Try it online!
This is a significant modification of user202729's answer. I would have posted this improvement as a comment, but the answer is deleted and so comments are disabled.

This fails with a "list index out of range" exception on the input 258. I think the problem is that x**2 is too small.

Well... Python 2 is different (often less bytes) from Python 3.

As expected, half-exponential is way larger than quadratic. The solution get "list index out of range" at x=1000. You may want to try 2**x - terribly large, but codegolf is codegolf.

@user202729 Ah, this is true. Unfortunately it now encounters an entirely different problem with larger inputs in that 2**x creates far too large of a range for Python to continue.

Swift, 137 bytes
func f(n:Int){var l=Array(1...n).map{$0>3 ?0:$0},p=8;if n>3{for i in 3..<n{if l[i]<1{l[i]=l[i-1]+1};if l[i]<n{l[l[i]]=p};p*=2}};print(l)}

Takes input as Int (integer) and prints as [Int] (integer array).
Ungolfed version
func f(n:Int){
    var l = Array(1...n).map{$0 > 3 ? 0 : $0} // Create the range from 1 to n and set all
    var p = 8                                 // values greater than 3 to 0
    if n > 3 {
        for i in 3 ..< n {
            if l[i] < 1 {
                l[i] = l[i - 1] + 1
            }
            if l[i] < n {
                l[l[i]] = p
            }
            p *= 2
        }
    }
    print(l)
}

I'm curious, what will happen if you remove the space before the ??

@ETHproductions That leads to a compiler error, since integers can't be optional chained.


text:
Days and months make years
Today's date is quite an interesting one. Let's take a look at why. The date 07/12/2017 (in DD/MM/YYYY date format) can be split into the year (2017) and the rest (07/12). You may notice that the digits in the year can be rearranged to match the digits in the rest of the date, which is the basis of this challenge.
The task
Given an valid integer (e.g. no leading zeros) representing a year, consisting of exactly four digits, output all unique possible valid dates that can be made from those digits. You may take the number as a list of digits, or a string representing the input if you want. Each number in the input must be used exactly once in each of the final outputs. As leading 0s aren't used in integers, the input will be in the range 1000 <= input <= 9999.
A valid date is one in which the date exists on the Gregorian Calendar, such as 17/05/2000. The only corner case is February 29th, which is only a valid date when the year is a leap year. You can (but don't have to) assume that leap years are years that are divisible by 4.
You have to output a separator between the day and the month (e.g. /) and a different separator between different dates. You may optionally output the year with each date, but this must be consistent between dates.
Finally, you may choose between the date format order, i.e. you can output as any of DD/MM/YYYY, MM/DD/YYYY etc. but leading 0s are required when the input contains at least one 0.
Essentially, you may output in any obviously understandable format, such as an array of strings, one concatenated string etc.
This is a code-golf so shortest code wins!
Test cases
input
outputs

2017
07/12, 12/07, 17/02, 21/07, 27/01, 27/10

2092
22/09, 29/02

2029
22/09

1000
Nothing

8502
25/08, 28/05

Reference Implementation

Not all years divisible by 4 are leap. Should we consider that this is the case nonetheless?

@Arnauld Yes, you can assume that all leap years are divisible by 4

Should we output in a specific format {N1}{SEP1}{M1}{SEP2}{N2}{SEP1}{M2}{SEP2}... or can we output as arrays too? It looks like this is a bit of a chameleon or maybe multi-part challenge currently...

@EriktheOutgolfer Essentially, you may output in any reasonable format you wish, whether than be array, string or whatever

Can there be an input like 0000? If so, then that's not an integer (Given an integer consisting of exactly four digits).

@EriktheOutgolfer I think you answered your own question. No, 0000 won't be inputted because it's not an integer.

Are duplicated dates a problem?

@Uriel output all unique possible valid dates

Does the "etc" in the possible output formats include YYYY-MM-DD?

@Shaggy Yes, that’s no problem

I tried making a pip solution, but there are too many conditions for a golfy answer. Maybe someday when pip has date functionality. Nice question.

@Razetime If you have a solution, post it! A long answer is better than no answer

sure, I'll take some time and figure the conditions out.

I think I may have interpreted the spec too strictly! Can we output a 2D-array as Kevin did for his solution?

@Shaggy Yes, that’s no problem

I'm pushing it now, but I assume an array of dates formatted as "MMDD", without a separator is a "no-no"? https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=4SDiIGbIpKXQTmNY8rlm&input=IjIwMTciCi1R

@Shaggy Like the interpreter, but unfortunately that’s a no-no cause there’s no separator, sorry

No worries; I figured it'd be a step too far.

Japt, 31 30 26 24 23 22 17 bytes
Locale dependent. Outputs a 2D-array of the format [["MM","DD"],...].
á â mò fÈÎ-ÐNcX)Î

Try it or Try It Online! (to avoid the locale dependency)
Explanation
If it wasn't for JavaScript's Date object wrapping invalid dates, I'd be able to get this down to about 20 18 16 bytes. Even when providing its argument as a single string, which the spec says shouldn't lead to wrapping, dates up to 31 still do for months that don't have 31 days. However, as the month's can only wrap over by one, we can take advantage of the fact that string arguments use 1-based months to simply filter by subtraction - if the month rolls over then the result of that subtraction will be 0.
á â mò fÈÎ-ÐNcX)Î     :Implicit input of N=[U="YYYY"]
á                     :Permutations of U
  â                   :Deduplicate
    m                 :Map
     ò                :  Partitions of length 2 (=[["MM","DD"],...])
       f              :Filter
        È             :By passing each X through the following function
         Î            :  First element of X
          -           :  Subtract
           Ð          :  Create new Date from
            NcX       :    N concatenated with X (=["YYYY","MM","DD"], which gets coerced to "YYYY-MM-DD", with MM being 1-based)
               )      :  End date creation
                Î     :  0-based month (=NaN for invalid dates, n-NaN=NaN)

Original, 22 bytes
Preserving this, 'cause I really liked the setwise union trick.
á
â¡ÐNcXòÃfÈÎ-2îUvÃms7

Try it (footer formats the output to match the examples in the challenge)Or Try it online! to somewhat mitigate the locale dependency - TIO's locale doesn't include leading 0s for dates & months, so they're added back in in the footer.
Explanation
á\nâ¡ÐNcXòÃfÈÎ-2îUvÃms7     :Implicit input of N=[U="YYYY"]
á                           :Permutations of U
 \n                         :Reassign to U, leaving the value in N unchanged
   â                        :Setwise union with
    ¡                       :Map each X in U
     Ð                      :  New Date from
      Nc                    :  N concatenated with
        Xò                  :  Partitions of X of length 2 (=["YYYY","MM","DD"], which gets coerced to "YYYY-MM-DD", with MM being 1-based)
          Ã                 :End map
           f                :Filter by
            È               :Passing each through the following function
             Î              :  Get 0-based month (=NaN for invalid date)
              -             :  Subtract (NaN-n=NaN)
               2î           :  First 2 characters of
                 Uv         :  Remove and return first element of U
                   Ã        :End filter
                    m       :Map
                     s7     :  To locale date string (="DD/MM/YYYY")

The reason the setwise union doesn't include any elements from the first array is because v modifies that array so the filter ends up removing all elements from it.
In the 16 byte version, which assumes a way to avoid dates wrapping over, we don't need to reassign the array of possible dates to U and instead filter by using Í to try to subtract the timestamp from 2, which will result in NaN if the date is invalid. We can't use the setwise union trick, though, so â get tacked on the end to deduplicate the final array.

Man, this must be the only time I've gone 1000+ days between asking a question and it being answered :P

Only noticed that once you said it, @cairdcoinheringaahing! :o

Of course being deleted for 1000 days might help :P

@cairdcoinheringaahing, I do admit that I was confused as to why you thought it was 2017!

@Dingus, I think the footer might be the cause of the problem there. Do you get the expected output when you remove it?

Yup, looks like it is, @Dingus. I get no results from the 17-byte version for an input of "2000", as expected. I'll add a note that it's locale dependent with an alternative link to TIO.

05AB1E, 36 35 bytes
œÙ2δôʒ`ÐU13‹rD•ü¯B•5°I4Ö*+ºS₂+Xè‹PĀ

05AB1E doesn't have any date builtins, so manual calculations it is. Therefore all years divisible by 4 are counted as leap years (which is allowed in the challenge description), since that's shorter than actual leap year calculations.
Output as a list of [dd,MM]-pairs.
Try it online or verify all test cases.
Explanation:
œ                # Get all permutations of the (implicit) input-integer
 Ù               # Uniquify this list
   δ             # For each permutation:
  2 ô            #  Split it into parts of size 2
ʒ                # Filter this list of [dd,MM]-pairs by:
 `               #  Pop and push both values separated to the stack
  Ð              #  Triplicate the top value MM
   U             #  Pop and store one MM in variable `X`
    13‹          #  Check whether MM is smaller than 13
  r              #  Reverse the values on the stack, so the order is MM<13,MM,dd
   D             #  Duplicate the top value dd
    •ü¯B•        #  Push compressed integer 16365656
     5°          #  Push 10⁵: 100000
       I         #  Push the input-year
        4Ö       #  Check if it's divisible by 4 (1 if truthy; 0 if falsey)
          *      #  Multiply that by the 100000 (100000 if it's a 'leap year'; 0 if not)
           +     #  Add it to the 16365656 (16465656 if it's a 'leap year'; 16365656 if not)
            º    #  Mirror it: 1636565665656461 / 1646565665656461
             S   #  Convert it to a list of digits: [1,6,3/4,6,5,6,5,6,6,5,6,5,6,3/4,6,1]
              ₂+ #  Add 26 to each: [27,32,29/30,32,31,32,31,32,32,31,32,31,32,29/30,32,27]
    X            #  Push MM from variable `X`
     è           #  Index it into this list (0-based modulair, hence the leading dummy 27)
    ‹            #  Check if dd is smaller than the indexed value
  P              #  Take the product of all values on the stack: (MM<13)*MM*dd*(dd<...)
   Ā             #  Check that this is NOT 0
                 # (after which the filtered list of [dd,MM]-pairs is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •ü¯B• is 16365656.

R, 231 216 189 186 bytes
Edit: -42 bytes by keeping numbers as numbers (no conversion to text) and using sprintf to fix the leading zeros
function(y){e=unique(gtools::permutations(4,4,y%/%10^(0:3)%%10,F))
m=e[,1]*10+e[,2];n=e[,3]*10+e[,4]
sprintf("%02d/%02d",m,n)[which(m&n&(m<(31-rep(-1:0,l=13)[-8])[n]-(n==2)*(2-!y%%4)))]}

Try it online!
This challenge seemed quite innocuous when I read it, but turned-out to be much, much more complicated than I thought to implement!
The actual checking for possible day/month combinations is less than one-third of the code!
Finds all unique permutations of the digits of the year, combines them in pairs as numbers text (to keep leading zeros), then finds the indices that are possible after converting back to numbers, and sprintfs the output to keep the leading zeros.
Calculates days in months as (31-rep(-1:0,l=13)[-8]) which gives all correct except Feb, then adjusts with -(month==2)*(2-!y%%4)) to fix Feb for leap-years.
Original commented code (before quite a lot of golfing):
possible_dates=
function(y,                     # y = year (number)
 `+`=as.double,                 # `+` = alias to as.double() function, to easily
                                #       convert text to numbers
  a=apply,                      # a = alias to apply() function (runs helper function over all elements of matrix)
  p=paste0){                    # p = alias to paste0 function (joins text together)
  d=a(                          # d (digits) =
   unique(                      # get the unique combinations of...
    gtools::permutations(4,4,   # all permutations of...
     y%/%10^(0:3)%%10,F))       # the digits of the year...
   ,1,function(i)               # and, for each combination...
    p(i[1:2],i[3:4]))           # paste-together the first & second two digits as text
 a(d,2,p,collapse="/")          # now, paste these together with '/' as separator,
  [which(                       # but only output those that satisfy...
   (m=+d[1,])&                  # first element (days) non-zero, and...
   (n=+d[2,])&                  # second element (months) non-zero, and...
   (m<(31-rep(-1:0,l=13)[-8])[n]  # days less than days in the month...
   -(m==2)*(2-!y%%4))           # with correction for leap-years
  )]
}

I have to say, I'm also quite surprised at how difficult this turns out to be. I'm not familiar enough with R to have a benchmark expectation, but I was fully expecting Shaggy's Japt answer to be around half the length. Interesting how that happens.

@cairdcoinheringaahing Well, I'd like to encourage you to try your hand at R while it's the 'language of the month', but...   ...I can't really recommend you use this challenge as a first attempt!  It was fun, though (in the end), so thanks for posting it 3 years ago!

Ruby, 94 91 90 88 bytes
-3 bytes thanks to @Shaggy and another -2 bytes thanks to @vrintle
->y{[]|y.permutation.map{|d|("#{Time.gm y*'',(d*'')[/../],$'}"rescue$/)[/\S+-#$'/]}-[p]}

Try it online!
Takes input as an array of digits and returns an array of date strings in yyyy-mm-dd format. Leap years are handled correctly, i.e. it is not assumed that all years that are divisible by 4 are leap years. A gotcha with the Time library is that it sets an upper limit of 31 days for all months, silently wrapping to the next real calendar date, so a sanity check is required. Invalid months are automatically rejected.
->y{
  []|                                   # combine with empty array
  y.permutation                         # form all permutations of the year digits
   .map{|d|                             # loop over permutations
     ("#{Time.gm y*'',(d*'')[/../],$'}" # (attempt to) create a time string using the first two digits of the permutation as the month and the last two digits as the day
       rescue$/)                        # if the time is invalid, rescue the exception and return a dummy string ($/) instead
     [/\S+-#$'/]                        # check that the day is the same as expected (to prevent date wrapping) and extract the full date if so
   }
  -[p]                                  # remove nil elements
}

y.permutation() seems to work without the 4.

@Shaggy Thanks. I didn't know you could do that.

Neither did I - I don't know Ruby at all!

@vrintle Nice one - it was bound to happen. :) (d*'')[/../],$' splits the four-digit string d*'' (i.e. the joined array d) into two parts. The first part, (d*'')[/../], returns the first two digits (the month). The second part, the predefined variable $', returns everything to the right of the previous regex match, which in this case is the last two digits. $/ is the input record separator ("\n" by default), but I'm just using it so that rescue returns a string. Any other string would do but you'd need a space in between.

Python 3.8, 149 140 bytes
Uses the simplified definition of leap years.
lambda y:{i+o+'/'+z+u for z,u,i,o in permutations(str(y))if((m:=int(z+u))==2)*~(y%4>0)+(m//8^m%2)+31>int(i+o)>0<m<13}
from itertools import*

Try it online!

"leading 0s are required when the input contains at least one 0"

@DominicvanEssen thanks for pointing it out, should be fixed now.

Yes, and I've just copied your 'output the digits' approach, which has saved me 15 bytes, too!  Thanks!

Python 3, 186 197 bytes
import itertools;import datetime;y=input();s=set()
for p in itertools.permutations(list(y)):
 try:f=datetime.date(int(y),int(p[2]+p[3]),int(p[0]+p[1]));s.add(f)
 except:pass
for d in s:print(d)

"leading 0s are required when the input contains at least one 0"

@DominicvanEssen: should be fixed

k4, 55 bytes
{?,/(@[.:;;()]x,"."/:0 0 2_)'(,"")(,/{(1_x),*x}\',')/x}

Not the most elegant, but it outputs a list of valid dates (accounting for e.g. leap years). Takes a string as input, e.g. "2017".

(,"")(,/{(1_x),*x}\',')/x builds a list of the permutations of the input
x,"."/:0 0 2_ takes each permutation, prepends the input year, and inserts "."s to format it as a date. E.g., for an input of "0127", the output is "2017.01.27".
@[.:;;()] is error trap; it attempts to eval the generated date string, returning an empty list if the value is an invalid date.
?,/ returns the distinct valid dates

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


text:
ASCII Hexagon Chain
Problem
Draw a hexagon chain x long, each with side of y length
Input
x - the length of the chain <= 50
y - the length of each side <= 50
Examples
x=1,y=1
 _
/ \
\_/

x=4,y=1
 _   _
/ \_/ \_
\_/ \_/ \
  \_/ \_/

x=3,y=2
  __      __
 /  \    /  \
/    \__/    \
\    /  \    /
 \__/    \__/
    \    /
     \__/

Rules

The shortest valid answer in bytes wins.
Leading and trailing newlines allowed.
Trailing white space allowed.

Related

Waiting for obligatory Hexagony answer...

@LLlAMnYP Any minute now...

@user202729 If you write one now, we never have to find out what happens.

First line in Hexagony. Obviously need to increase edge size for the rest.

Charcoal, 34 bytes
ＮθＦＮ«Ｍ∧﹪ι²⊗θ↓Ｐ×_θ←↖θ→↗θ×_θ↓↘θ←Ｐ↙θ↗

Try it online! Link is to verbose version of code. Takes the parameters in the order size, count. Explanation:
Ｎθ

Input the hexagon size.
ＦＮ«

Loop over the input number of hexagons.
Ｍ∧﹪ι²⊗θ↓

On alternate hexagons, move down a whole hexagon, so that the next hexagon is drawn to the lower right rather than the upper right.
Ｐ×_θ

Draw the bottom.
←↖θ

Draw the lower left side.
→↗θ

Draw the upper left side.
×_θ

Draw the top.
↓↘θ

Draw the upper right side.
←Ｐ↙θ

Draw the lower right side.
↗

Assume the next hexagon is to the upper right.

Python 2, 254 224 bytes
def f(n,w):
 a=w*2
 for j in range(1+w*3):print''.join([[[' ',[' /'[i%w==-j%w],' \\'[i%w==~-j%w]][i/a+~-j/w&1]][(j>0)*(i/w>=(j>a))*((i/w/n<2)or(n%-2<~-j/w<3-n%2))],' _'[(j+i/w%4/2*w)%a<(i<n*a)]][i/w%2]for i in range(-~n*a)])

Try it online!

Python 2, 264 229 bytes
def f(n,w):
 c=2*w;r=[[' ']*(-~n*c)for _ in' '*(1+w*3)]
 for i in range(w):
  for j in range(n):a=i+j*2*w;b=j%2*w;r[b][w+a],r[c+b][w+i+j*c],r[b+w-i][a],r[b+c-i][a+c],r[b+w-~i][a],r[b-~i][a+c]=r'__//\\'
 for l in r:print''.join(l)

Try it online!

@ovs Thanks a lot :)

222 bytes

SOGL V0.12, 32 31 bytes
ā.{e╚øΚe╔*ο⁴↔±┼┼╬±fe«*If2%e*I╬5

Try it Here!
Explanation:
ā                              push an empty array - the canvas
 .{                            repeat input times
   e╚                            push a diagonal the length of the variable E (by default: next input)
     øΚ                          prepend a line to it
       e╔*ο                      push ["_"*E]
           ⁴                     copy that diagonal
            ↔±                   and reverse it horizontally
              ┼┼                 add the 3 parts together
                ╬±               and palindromize vertically - one hexagon is finished
                  fe«*I          push counter*E*2 + 1 (the counter is 0-based)
                       f2%e*I    push counter%2 * E + 1
                             ╬5  at [counter*E*2+1; counter%2*E+1] insert the hexagon in the canvas

Befunge, 230 228 225 bytes
+&#92#<*:0< vp93*p92+1*3:p91:&+1p
>1+:29g-!#@_>:1-19g+:19g/1-:2*49p2%!2*:1+59p19g*\19g%+69p01v
,>*19g3*79g-1-69g-!2*49g1+0g2%*79g69g-!49g0g2%*++4g,1+:39g-v
^^3*!-*g95g91+1g96!-g95%4p04p01:`\g90p05`0::/g91:p97%*4g91:_$55+
 \/_

Try it online!

JavaScript (ES6), 215 bytes
Takes input in currying syntax (y)(x).
y=>(F=(x,c=!(p=y-1,w=x*y*2+y,a=[...(' '.repeat(w++)+`
`).repeat(3*y+1)],g=(d,k)=>k!=y?g(d,-~k,a[p+=d]='_\\/'[c%3]):c++))=>x--?F(x,g(1),g(w+1),p++,g(w-1),g(-1),p+=w,g(~w),p--,g(1-w),p+=(c/6&1?w:-w)*y-w+y*2):a.join``)

Demo

let f =

y=>(F=(x,c=!(p=y-1,w=x*y*2+y,a=[...(' '.repeat(w++)+`
`).repeat(3*y+1)],g=(d,k)=>k!=y?g(d,-~k,a[p+=d]='_\\/'[c%3]):c++))=>x--?F(x,g(1),g(w+1),p++,g(w-1),g(-1),p+=w,g(~w),p--,g(1-w),p+=(c/6&1?w:-w)*y-w+y*2):a.join``)

O.innerText = f(3)(7)

Canvas, 25 bytes
ø╶｛╷⁷«×¹２％⁷×╵⁷⇵_× ⁷／∔×╬│╋

Try it here!
Explanation (some characters have been changed to look monospace):
ø╶{╷⁷«×¹2%⁷×╵⁷⇵_× ⁷/∔×╬│╋
ø                          push an empty canvas
 ╶{                        for 1..input
   ╷                         decrease (so this starts with 0)
    ⁷«×                      multiply by X*2; X coordinate of new hexagon done
       ¹2%                   push 0-indexed counter%2
          ⁷×                 multiply by X
            ╵                and increment; Y coordinate done
             ⁷⇵              push ceil(X/2), saving the remainder
               _×            repeat "_" that many times
                  ⁷/         push " " and an ASCII diagonal with size X
                    ∔        prepend verticall the space before the diagonal
                              done so there's space for the underscores
                     ×       and append the underscores horizontally to the diagonal
                      ╬│     quad-palindromize with Y overlap of 1
                              and X overlap of the remainder taken before
                        ╋    and at the before defined coords ((I-1)*X*2; (i%2)*X + 1)
                              insert the hexagon in the canvas