title: One-card Poker for Two

text:
# Question
Title: One-card Poker for Two
This is a challenge to write bots to play the 1st and 2nd players in the following simple poker game.

## Rules of the poker game

There are two players, A and B. Each antes $10 into the pot, and is dealt a card, which is a real number in the range \[0, 1).

Player A goes first, and may pass or bet. If A passes, then there is a showdown; the cards are revealed, and whichever player had the higher card wins the pot.

If A bets, A chooses an amount \\$b\\$ to bet. \\$b\\$ must be an integer multiple of $1, in the range \[$1, $50\], and no greater than the amount of money A has at the time.

**EDIT (19 Aug 2020)**: Moreover, \\$b\\$ must be no greater than the amount of money B has at the time, to enable B to go all-in to call, if B wants to.

A adds \\$b\\$ to the pot.

Then B may fold or call.

If B folds, A wins the pot with no showdown.

If B calls, B adds \\$b\\$ to the pot, and there is a showdown.

**EDIT (19 Aug 2020)** Note that B will always have enough money to call, as A is not allowed to bet so much that B would not have enough.

## Rules of the tournament, matches and sessions

The bots which are the entries to this contest will compete in an all-play-all tournament consisting of matches. Every pair of entries go head to head in a match.

Each match has two contestants (call them X and Y). Each match consists of \\$n\\$ sessions, where \\$n\\$ is a number I will choose, depending on how many entries there are and how much time I feel like devoting to running the engine.

At the start of each session, the tournament controller gives each contestant $100. There then follow a series of games. The games in each match alternate games where X's A-bot plays Y's B-bot, and games where Y's A-bot plays X's B-bot. Each session will continue until either 50 games in the session have been played, or one contestant no longer has enough money to start a further game (specifically, to put a $10 ante into the pot).

Where a session contained \\$g\\$ games, and the winner gained an amount \\$m\\$ of money, that winner is awarded \\$m/\sqrt{g}\\$ points, and the loser loses the same amount of points. (The amount of points is higher, the lower \\$g\\$ is, so as to reward bots that consistently beat their opponents and thus win their opponent's entire stack quickly. However, I don't want very quick sessions to dominate the scoring too much, so I divide only by \\$\sqrt{g}\\$ and not by \\$g\\$.)

The winning bot is the one who won most points over the course of all the matches it played in the tournament (as described in the previous paragraph).

## Interfaces of procedures in an entry

An entry should contain C procedures which have the following prototypes:

```
int a(const Bot *bot);
int b(const Bot *bot, const int aBet);

```

where types are defined as follows:

```
typedef float Card;
typedef long Money;
typedef Money (*AProcType)(const void* bot);
typedef int (*BProcType)(const void* bot, const Money aBet);

typedef struct Bot
{
    AProcType a;
    BProcType b;
    Card    card, opponentsPreviousCard;
    Money   money, opponentsMoney;
    float   f[50]; // scratch area for bots to use as they will
} Bot;

```

Where `bot` points to an entrant's bot, just before `bot->a` or `bot->b` is called, the card dealt to that bot and the amount of money it has are assigned to `bot->card` and `bot->money`.

If a game ended in a showdown, then, afterwards, each bot's card is assigned to the other bot's `bot->opponentsPreviousCard`. By contrast, if the game ended with one player folding, then the controller does not reveal the cards: instead, a negative value is assigned to `bot->opponentsPreviousCard`.

In my sandbox proposal for this KotH, I asked whether or not the controller should *unconditionally* reveal both cards to both bots. It got a comment that in online poker "the winner has the choice whether they show or hide their cards". Seeing as a bot can't possibly do worse by hiding its card than by revealing it, I have opted instead to never reveal the cards dealt in a game where one player folded.

The array `f` is provided to enable a bot to maintain state between games.

In a game where the bot `bot` is the A-player, the controller will call the function `bot->a(bot)`.

`0. <= bot->card < 1.0`. `a` must return the amount (in $) the bot is to bet. If `a` returns 0 or a negative value, that means the bot will pass. Otherwise, the bot will bet the value returned by `a`, $50, or all the player's money, whichever is the smallest.

In a game where the bot `bot` is the B-player, the controller will call the function `bot->b(bot, aBet)` where the A-player has just bet an amount $`aBet`.

`0. <= bot->card < 1.0`. The controller calls `bot->b` only if both the following conditions are true:

* `aBet > 0` because if A had passed, B does not get to act.
* `bot->money >= aBet` because, if A had bet but B could not afford to call, B must fold.

`bot->b` must return 0 if the bot is to fold, and any other value if the bot is to call.

X and Y will never be the same entry. So, even if you think each of your bots would be able to tell if its match-opponent is your other bot... it won't be.

My sandbox proposal for this KotH expressed the game in terms of dealing cards from a pack. In such a game, if cards were not returned to the pack, the value of each card would change depending on how many cards above it and below it had not yet been seen, which would depend on the play. The proposal got a comment that cards are returned to the pack after each round. But in that case the above effect does not occur. So the cards might as well be independent variates from the uniform distribution on the interval \[0, 1).

Each entry's tournament score will be the sum of its match-scores. \[Note that each entry is pitted against every other entry, so all entries play equal numbers of matches.\]

Loopholes are forbidden, as is trying to cheat. No bot may try to read or write or tamper with anything external to it, including the controller or other bots. However, calls to `rand` (in reasonable quantities) are allowed.

**EDIT** Tue 11 Aug 20 to clarify that using `rand` is allowed, and to give direct read-access to the amount of the opponent's money.

The following is a controller, provided just so that entrants can test their bots. My actual controller might contain additional code as required.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

// Return codes from playVonNeumannPokerGame
#define G_FOLD  0
#define G_SHOWDOWN  1
#define G_MAYNOTBOTHPLAY    2

#define ANTE    10
#define BET_LIMIT   50
#define INIT_STACK  100

typedef float Point, Card;
typedef long Index, Money, Stat;
typedef Money (*AProcType)(const void* bot);
typedef int (*BProcType)(const void* bot, const Money aBet);

typedef struct Bot
{
    AProcType a;
    BProcType b;
    Card    card, opponentsPreviousCard;
    Money   money;
    float   f[50]; // scratch area for bots to use as they will
} Bot;

#define GAME_NAME_MAX   31

typedef struct Entrant
{
    Bot *bot;
    char    name[GAME_NAME_MAX+1];
    Point   vp;
    Money   mny;
} Entrant, *PEntrant;

long    nEntrants;
Entrant *plr;

#define NSESSIONSPERMATCH 500
#define MAXNGAMESPERSESSION 50
unsigned long nGamesInTotal, prngSeed;

static void playVonNeumannPokerTournament();
static void playVonNeumannPokerMatch(PEntrant c1, PEntrant c2);
static long playVonNeumannPokerGame(PEntrant a, PEntrant b);
static void initBots();
static void tournament2Init(long nPlayers);
static void tournament2MatchPlayers(long *pi1, long *pi2);
static float fRand();
static int cmpByVP(const Entrant* e1, const Entrant* e2);

// <nEntrants> <seed>
int main(int argc, char** argv)
{
    sscanf_s(argv[1], "%ul", &nEntrants); // for public engine
    sscanf_s(argv[2], "%ul", &prngSeed);
    srand(prngSeed);
    playVonNeumannPokerTournament();
} // main

static void playVonNeumannPokerTournament()
{
    long    pi, pj;
    PEntrant    e;

    nGamesInTotal = 0;
    //nEntrants = sizeof(aProc)/sizeof(aProc[0]); // works only if engine includes bot data
    plr = (PEntrant)calloc(nEntrants, sizeof(Entrant));
    for(pi=0; pi<nEntrants; ++pi) // Initialise the entrants
    {
        e   = &plr[pi];
        e->vp   = 0;
    }
    initBots(); // Connect each entrant to its bot
    for(pj=1; pj<nEntrants; ++pj) // all-play-all tournament
        for(pi=0; pi<pj; ++pi)
            playVonNeumannPokerMatch(&plr[pi], &plr[pj]);
} // playVonNeumannPokerTournament

static void playVonNeumannPokerMatch(PEntrant c1, PEntrant c2)
{
    long    si, mgi=0, sgi, r;
    Point   win1, win2;

    c1->bot->opponentsPreviousCard = -1.0;
    c2->bot->opponentsPreviousCard = -1.0;

    for(si=0; si<NSESSIONSPERMATCH; ++si)
    {
        c1->mny = INIT_STACK;
        c2->mny = INIT_STACK;
        for(sgi=0; sgi<MAXNGAMESPERSESSION; ++sgi)
        {
            if(mgi&1) // c1 & c2 swap roles in the match's every game
                r   = playVonNeumannPokerGame(c2, c1); // c2 is A; c1 is B
            else // even-numbered game
                r   = playVonNeumannPokerGame(c1, c2); // c1 is A; c2 is B
            ++mgi;
            if(r==G_MAYNOTBOTHPLAY)
                break; // one player can't afford to continue the session
            if(r==G_SHOWDOWN)
            {
                c1->bot->opponentsPreviousCard = c2->bot->card;
                c2->bot->opponentsPreviousCard = c1->bot->card;
            }
            else
            {
                c1->bot->opponentsPreviousCard = -1.0;
                c2->bot->opponentsPreviousCard = -1.0;
            }
        }
        win1    = (c1->mny - INIT_STACK +0.0)/sqrt(sgi); // sgi must > 0. Take sqrt so as not to over-reward quick wins
        win2    = (c2->mny - INIT_STACK +0.0)/sqrt(sgi);
        c1->vp += win1;
        c2->vp += win2;
    } // for each session in the match
} // playVonNeumannPokerMatch

static long playVonNeumannPokerGame(PEntrant a, PEntrant b)
{
    _Bool   bCalls;
    Card    ax, bx;
    Money   aBet;
    long    r=G_SHOWDOWN;

    // Unless each of the game's players can afford their ante, they cannot play a game.
    if(a->mny < ANTE || b->mny < ANTE)
        return G_MAYNOTBOTHPLAY; // players may not both play
    a->bot->card = ax = fRand();
    b->bot->card = bx = fRand();
    a->bot->money = b->bot->opponentsMoney = a->mny;
    b->bot->money = a->bot->opponentsMoney = b->mny;
    // Call A's bot to find out how much money A wants to bet.
    aBet    = a->bot->a(a->bot);
    // But A may not bet more money than A has, nor yet more than the bet-limit
    aBet    = aBet < 0 ? 0 : a->mny < aBet ? a->mny : aBet;
    aBet    = aBet > BET_LIMIT ? BET_LIMIT : aBet;
    // EDIT 19 Aug 2020: A may not bet more money than B has.
    aBet    = aBet > b->mny ? b->mny : aBet;
    // [If B cannot afford to call, B must fold; there is no need to call B's bot in such a case. Otherwise,] call B's bot to find B's reply (fold or call)
    // Treat A passing as A betting 0 and B calling
    bCalls  = aBet < 1 ? 1 : b->mny < aBet ? 0 : b->bot->b(b->bot, aBet);
    if(!bCalls) // B folds
    {
        a->mny  += ANTE;
        b->mny  -= ANTE;
        r   = G_FOLD;
    }
    else if(ax>bx) // B calls A's bet; A wins the showdown
    {
        a->mny  += ANTE+aBet;
        b->mny  -= ANTE+aBet;
    }
    else // B calls A's bet; B wins the showdown
    {
        a->mny  -= ANTE+aBet;
        b->mny  += ANTE+aBet;
    }
    return r;
} // playVonNeumannPokerGame

/*#############################################################################
    Bots

    This section is subject to change, and has my copies of user-submitted code for bots' a- and b-procedures
###############################################################################
*/

// This bot is so naive, it never bluffs.
static Money naiveA(const Bot *bot)
{
    Card x=bot->card;

    return 50.*x-25.;
}

static int naiveB(const Bot *bot, const Money aBet)
{
    return bot->card>.5;
}

// This bot treats it like 3-card Kuhn poker
static Money kuhn3A(const Bot *bot)
{
    Card x=bot->card;
    Money m=bot->money;
    Money bet = 10;

    if(m<bet)
        bet = m;
    return 9.*x<1. || 3.*x>2. ? bet : 0;
}

static int kuhn3B(const Bot *bot, const Money aBet)
{
    return bot->money>=aBet && 9.*bot->card>5.;
}
typedef char *String;
static String botName[] = {"naive", "Kuhn3"};
static AProcType aProc[] = {naiveA, kuhn3A};
static BProcType bProc[] = {naiveB, kuhn3B};

static void initBots()
{
    Bot *pBot;
    long    i, j;

    for(i=0; i<nEntrants; ++i)
    {
        pBot = (Bot*)calloc(1, sizeof(Bot));
        pBot->a = aProc[i];
        pBot->b = bProc[i];
        for(j=0; j<50; ++j)
            pBot->f[j] = 0.0;
        plr[i].bot  = pBot;
        strncpy_s(plr[i].name, GAME_NAME_MAX+1, botName[i], GAME_NAME_MAX);
    }
} // initBots

static float fRand()
{
    float   r = rand();
    return r / RAND_MAX;
}

static int cmpByVP(const Entrant* e1, const Entrant* e2)
{
    return e2->vp > e1->vp ? 1 : -1; // map from floats to int +-1
}

```

# Answer
# LikeMe Bot

Here's a simple bot. It mostly just assumes that the other bot bets roughly like it does.

```
int likemea(const Bot *bot){
    // Always go big if we can't play again if we lose.
    if (bot->money < 10) return bot->money;
    // Force an all-in if there's a decent change we win.
    if (bot->card > 0.5 && bot->opponentsMoney <= 50) return bot->opponentsMoney;
    float max_pass = 0.5;
    float min_max_bet = 0.9;
    // Increase risk tolerance when in the lead.
    float lead = bot->money / (bot->opponentsMoney + 20);
    if (lead > 1){
        // Don't go crazy.
        lead = lead / 2 + 1;
        if (lead > 1.5) lead = 1.5;
        max_pass /= lead;
        min_max_bet /= lead;
    }
    if (bot->card < max_pass) return 0;
    if (bot->card > min_max_bet) return 50;
    return (int)((bot->card - max_pass) / (min_max_bet - max_pass) * 50);
}

int likemeb(const Bot *bot, const int aBet){
    // Get what I would have bet if I was a.
    int my_bet = likemea(bot);
    if (bot->money < 50){
        // If I'm being pushed all-in, assume the other bot is playing riskier.
        my_bet = (int)(my_bet * 1.2);
    }
    if (my_bet >= aBet) return aBet;
    return 0;
}

```

Please have mercy on my C. It's been a while, and I've never done much C anyway.
> 3 votes

# Answer
# Con-stats Bot

Uses the power of probabilities and brute-force to choose better numbers than just '50%' or '50 money', the right constant stats to con you.

```
static Money constatsA(const Bot* bot)
{
    Card x = bot->card;
    Money money = bot->money - ANTE; // ANTE is not taken out before call
    Money oppMoney = bot->opponentsMoney - ANTE; // same as above

    // Going all in is a bad strat normally?
    // Just put a minimum card, that'll fix it
    if (x > 0.72 && money < ANTE) return money;

    // If my card is over 0.71, I have an optimial chance of winning
    // make sure not to bet all _my_ money
    // BET_LIMIT + ANTE means that I can bet even harder, as they
    // don't need to go to 0, just low enough they can't ANTE anymore.
    if (x > 0.71 && oppMoney <= BET_LIMIT + ANTE && oppMoney < money)
        return oppMoney;

    // yep, 1.
    // Turns out, most bots self-destruct under their own weight?
    // Or they just get confused by the quite low bet.
    return 1;
}

static int constatsB(const Bot* bot, const Money aBet)
{
    Card x = bot->card;
    Money money = bot->money - ANTE;

    if (x > 0.90) return true;

    // if it has enough for two more rounds
    // and a 55% of winning, go for it
    return x > 0.55 && money >= aBet + 2 * ANTE;
}

```

Well, it was this, or making a neural network and exporting it to C. Never actually used C before, but C++ is close enough to know all this.

Also, the controller's `Bot` struct is missing it's `opponentsMoney`.
> 1 votes

---
Tags: king-of-the-hill, card-games
---


# Question
Title: Implement the Method of Finite Differences
The Method of Finite Differences is a technique used to find the next term in a sequence of numbers, given that the sequence is governed by consecutive values of a certain polynomial. Given a list of `n` terms, the Method will be able to determine the degree of the polynomial, which is a maximum of `n+1`.

The Method works by arranging the numbers in order, like so.

```
4 8 15 16 23 42

```

Then the difference between any number and its neighbor to the right (given that it has a neighbor to the right) is written in the row below. Note that entries must be written one space (ASCII 20) to the right of the longest entry in the previous column.

```
4 8 15 16 23 42
4 7 1  7  19

```

The process is repeated until there is one entry left in the bottom row.

```
4   8  15 16 23 42
4   7  1  7  19
3   -6 6  12
-9  12 6
21  -6
-27

```

Then the bottom row's entry is duplicated.

```
4   8   15 16 23 42
4   7   1  7  19
3   -6  6  12
-9  12  6
21  -6
-27 -27

```

Then the above process for finding differences is reversed until there is a new entry in the first row, which is separated from the other entries by  `|`

```
4   8   15  16  23  42 | 46
4   7   1   7   19  4
3   -6  6   12  -15
-9  12  6   -27
21  -6  -33
-27 -27

```

The Method moves down rows until all of the entries in a row are equal. Take the starting numbers `2 5 10 17 26`. This is the finished table.

```
2 5 10 17 26 | 37
3 5 7  9  11
2 2 2  2

```

The degree of the polynomial is the number of rows minus 1. As you might tell from the previous example, the polynomial is `x^2+1`.

---

Your program will take as its input a list of integers separated by whitespace. You may assume that the list contains only integers and has at least 2 elements (they need not be distinct; the resulting chart would have only 1 row). The program will output the entire table generated by the Method of Finite Differences, as defined above.

---

This is code golf. Standard rules apply. Shortest code in bytes wins.

# Answer
# CJam, ~~74~~ ~~73~~ ~~71~~ 68 bytes

```
q~]{_2ew::-Wf*_)-}g0]W%{_W=@W=++_}*;)"|"\++]W%z{:s_:,$W=)f{Se]}}%zN*

```

Try it online

The latest version uses the middle section of @MartinBüttner's proposed solution, which is 3 bytes shorter than what I had. The first part for calculating the difference rows was identical. The part for the final formatting was the same length, so I kept my original version. Martin's savings came from making the sum part of the list while the new values are calculated, and using a `*` instead of a `%` loop. That also simplified the insertion of the "|".

Explanation:

```
l       Get one line of input.
~]      Interpret input and wrap in list.
{       While loop to construct additional lines.
  _2ew    Copy and build pairs of subsequent numbers.
  ::-     Reduce all number pairs by subtraction.
  Wf*     Multiply all of them by -1, since the reduction calculated 1st minus 2nd,
          but we need 2nd minus 1st.
  _)-     Check if all numbers in list are equal by popping off last and removing
          value from the list. This is truthy if all numbers are not equal.
}g      End of while loop to construct additional lines.
0       Add a 0 at the end, which will be the starting point of the sum for
        calculating the new values.
]       Wrap all lines in a list.
W%      Revert order of list, since adding the additional numbers in each row
        goes in bottom-up order.
{       Start of loop over rows.
  _W=     Get last value of row.
  @       Rotate previous row to top.
  W=      Extract last value as new increment. For the 0 that was added as an
          additional row, this is a comparison with -1, which gives the desired
          value of 0.
  +       Add increment to last value.
  +       Append value to list.
  _       Copy row for use in next loop iteration.
}*      End of loop over rows.
;       Remove extra copy of last row.
)       Pop off last value of last row.
"|"     Push the vertical bar.
\       Swap vertical bar and last value.
++      Concatenate the 3 parts.
W%      Revert order of list, to get the rows back in original order.
z       Transpose list for handling column alignment.
{       Loop over columns.
  :s      Convert values to strings.
  _:,     Copy and calculate the length of all values.
  $W=     Get maximum length by sorting and getting last value.
  )       Increment to add space between columns.
  f{      Apply to all values.
    Se]     Right pad to column width with spaces.
  }       End apply to all values.
}%      End loop over columns.
z       Transpose back to row order.
N*      Join rows with newlines.

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 93 bytes

```
{↑⍕¨¨{(⊂1⌽'|',⍨¯1⌽⊃⍵),(¯1↓1↓⍵),⊂(⊢,⊢/)⊃⌽⍵}⊃{(⊂⍺,(⊃⌽⍺)+⊃⌽⊃⍵),⍵}/⌽⊂@1⌽{⍵,⊂-2-/⊃⌽⍵}⍣{1≥≢∪⊃⌽⍺}⊂⍵}

```

Try it online!

The output format is a bit annoying, and takes up most of the space here.
> 0 votes

---
Tags: code-golf, math, number
---


title: Random Password Generator

text:
# Question
Title: Random Password Generator
The domain server requires that all employees have a strong, random password conforming to the following rules:

* Exactly 15 characters long.
* Keyboard-typeable characters only (as shown in code-type below). Teaching the sales to use ALT+NUMPAD codes is not permitted.
* At least 1 lower case letter: `abcdefghijklmnopqrstuvwxyz`
* At least 1 upper case letter: `ABCDEFGHIJKLMNOPQRSTUVWXYZ`
* At least 1 numeric digit: `0123456789`
* At least 1 symbol: ``~!@#$%^&*()_+-={}|[]\:";'<>?,./`

For this purpose IT have commissioned and will be distributing a Random Password Generator to all employees. All employees will be required to use the Random Password Generator. The requirements for the Random Password Generator are, in addition to the password restrictions above:

* It must be able to generate all permutations of all allowable characters.
* It must display the generated password on the screen.
* The code is required to be as small as possible (in bytes).

Please submit your proposed solution within the next week.

# Answer
> 29 votes
# Mathematica (18)

Let me a little cheat

```
= 15char ASCII pwd

```

> ```
> &(^F7yP8k:*1P<t
>
> ```

P.S. not safety :)

# Answer
> 13 votes
# Ruby, 74 69 bytes

Just randomly sample from the ascii range 33 - 126 until all classes of characters are present:

```
$_=[*?!..?~].sample(15)*''until~/\d/&&~/[a-z]/&&~/[A-Z]/&&~/\W|_/
p$_

```

# Ruby, 39 bytes

Using moose's clever discovery:

```
p"0123abcdABCD-+/<".chars.sample(15)*''

```

---

Edit to satisfy the mob:

Note that the rules changed *after* I first posted this. At the time *both* the previous entries applied to the rules. I would also like to point out that the rules are still not too well defined:

> (..) all permutations of all allowable characters

"Permutations". There are ***no*** permutations of the allowable characters that complies with the rest of the rules, because any permutation of the set of allowable characters is as long as the set of allowable characters itself (while the password is supposed to be 15 characters long). *And there are no repetitions in a permutation.* However my first entry is still more "random" than many of the other well upvoted answers here.

Nevertheless, here you have it. Allows repetitions of characters and underscore:

# Ruby, 77 bytes

```
$_=([*?!..?~]*15).sample(15)*''until~/\d/&&~/[a-z]/&&~/[A-Z]/&&~/\W|_/
puts$_

```

I also used `puts` instead of `p` in this one because `p` prints out the string enclosed in "quotation marks" and some characters escaped with a backslash.

# Ruby, 70 bytes

As Ventero points out, `~` can be skipped in front of the regexes, and `print` can replace `puts$_`. But with the ugly output this causes you might as well print all the rejected passwords too, squeezing it into a one-liner:

```
puts$_=([*?!..?~]*15).sample(15)*''until/\d/&&/[a-z]/&&/[A-Z]/&&/\W|_/

```

### Explanation

As requested. `$_` is a semi-magical variable that contains the last line read from input - so you don't always need to store it, like this. Here however we use it because of another property, namely that the `~` operator applies a regex directly to it, a trick I first learned by chron. I replaced the usage of `all`, but it should be quite easy to understand if you get the rest (see the docs).

# Answer
> 13 votes
# Java 8 - 354 329 319 275 267 characters

Just for fun, using lambdas with Java 8 - each possible output has the same probability of being found.

It uses the fact that the allowed characters have consecutive ascii codes, from 33 to 126.

```
class A {
    //flags for, respectively, small caps, large caps, digits, punctuation
    static int a, A, d, p;

    public static void main(String[] x) {
        String s;
        do {
            //Using special String constructor that takes an int[]
            s = new String(new java.util.Random().ints(15, 33, 127)
                                .toArray(),
                           0, 15);
            a = A = d = p = 0;
            s.chars()
                .map(c ->
                      c > 96 & c < 123 ? a = 1
                    : c > 64 & c < 90  ? A = 1
                    : c > 47 & c < 58  ? d = 1
                    : (p = 1))
                .min();
        } while (a + A + d + p < 4);
        System.out.println(s);
    }
}

```

Sample output:

```
.*;Tm?svthiEK`3
o.dzMgtW5|Q?ATo
FUmVsu<4JF4eB]1

```

Compressed program:

`class A{static int a,A,d,p;public static void main(String[]x){String s;do{s=new String(new java.util.Random().ints(15,33,127).toArray(),0,15);a=A=d=p=0;s.chars().map(c->c>96&c<123?a=1:c>64&c<90?A=1:c>47&c<58?d=1:(p=1)).min();}while(a+A+d+p<4);System.out.println(s);}}`

# Answer
> 8 votes
# Python 2.X + 3.X (229 characters): Generate and replace

## Idea

1. First make a list with 15 allowed symbols
2. Replace a random position `r` by a random digit
3. Replace a random position `s`, with `s != r`, by an upper case letter
4. The same for lower case letter and symbol as in 2 and 3.

## Code

```
from random import randint as r, shuffle as s
a=list(range(15))
p=a[:]
for i in range(15):
    a[i]=chr(r(32,126))
s(p)
a[p.pop()]=chr(r(48,57))
a[p.pop()]=chr(r(65,90))
a[p.pop()]=chr(r(97,122))
a[p.pop()]=chr(r(33,47))
print(a)

```

# Python 2.X + 3.X (194 characters): Generate and check

```
import random
from re import search as s
p=''
while not all([s("\d",p),s("[a-z]",p),s("[A-Z]",p),s("[\W_]",p)]):
 p=str(map(chr,[random.choice(list(range(33,127))) for i in range(15)]))
print(p)

```
* Thanks to MvG who told me that `\u` and `\l` does not exist in Python regex.
* Thanks to grc who told me that `random.sample` is without replacement, be to get every possible allowed password we need sampling with replacement.

# Using flaw in the problem description

Currently, the problem description does not demand that every symbol / digit appears with the same probability. With the following solution, you cannot make any assumption about a single symbol and/or position. But you can do it with multiple ones.

## Python 2.X+ 3.X (62 characters)

```
from random import sample
print(sample("0123abcdABCD-+/<",15))

```

Thanks to daniero for the idea to use sample.

# Answer
> 8 votes
# Bash on \*nix (109)

```
while ! grep -Pq [A-Z].*[a-z].*[0-9].*[\\W_]<<<$a$a$a$a
do a=`tr -dc !-~</dev/urandom|head -c15`
done
echo $a

```

To work correctly, `$a` must not be set to a valid but non-random password up front. If you want to include `a=` and a line break up front, that's three more characters but it allows you to run the thing repeatedly. You can obviously also replace all newlines with `;` so you have a one-liner which you can execute as often as you whish.

Furthermore, you should have set `LC_ALL=C` or not set any locale-specific environment variables (`LANG` and `LC_CTYPE` in particular), since the character ranges depend on collation order being equal to ascii order.

`/dev/urandom` is the a source of random bytes. `!-~` is the range of all permissible characters, as specified in the question. `tr -dc` removes all characters *not* listed in its next argument. `head` takes 15 of the remaining characters. `grep` checks whether each of the required kinds does occur at least once. Its input consists of four copies of the candidate, so order of the symbols does not matter, hence all possible passwords stand a chance of getting selected. The `-q` to grep suppresses output.

For reasons unknown, `/dev/random` instead of `/dev/urandom` takes ages. It seems like entropy got exhausted pretty quickly. If you `cd` into `/dev`, you can avoid some more bytes, but that feels a bit like cheating.

# Python 2 (138)

```
import re,random
a=''
while not re.search('[A-Z].*[a-z].*[0-9].*[\W_]',a*4):
 a=''.join(random.sample(map(chr,range(33,127))*15,15))
print a

```

To make the code readable I added a newline and indentation after the loop which is not neccessary and which I did not count.

This is essentially the same idea as in the bash version. The random source here is `random.sample`, which will not repeat elements. To counter this fact, we use 15 copies of the list of permissible letters. That way, every combination can still occur, although those with repeated letters will occur less often. But I decide to consider this a feature, not a bug, since the question did not require equal probability for all permutations, only the possibility.

# Python 3 (145)

```
import re,random
a=''
while not re.search('[A-Z].*[a-z].*[0-9].*[\W_]',a*4):
 a=''.join(random.sample(list(map(chr,range(33,127)))*15,15))
print(a)

```

One newline and one indent again not counted. Apart from some Python-3-specific syntax overhead this is the same solution as for Python 2.

# JavaScript (161)

```
a=[];for(i=33;i<127;)a.push(s=String.fromCharCode(i++));
while(!/[A-Z].*[a-z].*[0-9].*[\W_]/.test(s+s+s+s))
for(i=0,s="";i<15;++i)s+=a[Math.random()*94|0];alert(s)

```

I added the newlines for readability, but did not count them.

# R (114)

```
s<-""
while(!grepl("[A-Z].*[a-z].*[0-9].*(\\W|_)",paste(rep(s,4),collapse="")))
 s<-intToUtf8(sample(33:126,15,T))
s

```

Linebreak and indentation inside loop added but not counted. If you feel like it, you can again move this to a single `;`-separated line.

# Answer
> 7 votes
# C# (123 - 139 103 - 127 characters compacted):

Using a perfectly adequate framework method in `System.Web.dll`:

```
class P
{
    static void Main()
    {
        Console.WriteLine(System.Web.Security.Membership.GeneratePassword(15, 1));
    }
}

```

Compacted:

```
class P{static void Main()
{Console.WriteLine(System.Web.Security.Membership.GeneratePassword(15,1));}}

```

Example:

```
b+m2ae0K:{dz7:A

```

Alternatively, take the value of the second parameter (`int numberOfNonAlphanumericCharacters`) from the command line:

```
class P
{
    static void Main(string[] a)
    {
        Console.WriteLine(System.Web.Security.Membership.GeneratePassword(15, int.Parse(a[0])));
    }
}

```

# Answer
> 5 votes
# R (~~301~~ 322 characters)

**Correction** forgot to check for digits.

```
a='abcdefghijklmnopqrstuvwxyz';
f=as.factor(strsplit(paste(a,toupper(a),
    sep="0123456789`~!@#$%^&*()_+-={}|[]\\:\";'<>?,./"),"")[[1]]);
g=gsub("(.):","\\1",levels(q:q:q:q:q:q:q:q:q:q:q:q:q:q:q));
repeat{p=g[runif(1)*length(g)];
    if(grepl("[A-Z]",p)&&grepl("[a-z]",p)&&grepl("[0-9]",p)&&grepl("[^A-Za-z0-9]",p))break;};
print(p);

```

(whitespace added for clarity only).

Generates all possible 15-character permutations of the 94 characters. Then randomly selects one until it matches the criteria.

The magic is in the `q:q` operation, which generates a new factor data type that is the interaction of all the factors in the first `q` list with all the factors in the second list, with every possible combination of those two lists being included in the list of "levels" of that factor. Interact 15 copies of the list of allowed characters, and you get (94^15) possible levels.

Please do not try this at home. The code takes a couple seconds to figure out all the three-character permutations, I really can't imagine how long it would take to figure out all the 15-character permutations, if your computer didn't just run out of memory in the meantime. When I ran the finished (three-character password) script to check it, the first password it spit out was "oO=", which I think about sums up the reaction you should have to this code.

# Answer
> 4 votes
## Python 2.7 (182)

```
import random as r,string as s
z=r.sample
j=list(z(s.ascii_lowercase,12)+z(s.ascii_uppercase,1)+z(s.digits,1)+z('`~!@#$%^&*()_+-={}|[]\\:";\'<>?,./',1))
r.shuffle(j)
print ''.join(j)

```

# Answer
> 4 votes
# Mathematica 170

```
r=RandomSample;f[i_]:=(FromCharacterCode/@Range@@i);
{t,A,a,n}=f/@{{33,126},{65,90},{97,122},{48,57}};
s=Complement[t,A,a,n];
""<>r[Join[RandomChoice/@{A,a,n,s},r[t,11]],15]

```

**Examples**

"\<\]}Pg3/e?3+Z~Oz"
"X/8jWe@f(\_x5P:="
"2wz2VQhtJC?\*R7^"

# Answer
> 4 votes
**Golfscript (60)**

Since the obl. golfscript is missing and as a noob I need the practice anyway :)

```
[48 10{rand}:r~+65 26r+97 26r+33 15r+11,{;32 96r+}%~]{r}$''+

```

It just builds an array with the 4 required + 11 random characters and sorts in random order.

# Answer
> 3 votes
# JavaScript 258 240 233 225

```
R=Math.random;a=b=>b[b.length*R()|0];for(x=[a(l="abcdefghijklmnopqrstuvwxyz"),a(u=l.toUpperCase()),a(n="0123456789"),a(s="`~!@#$%^&*()_+-={}|[]\\:\";'<>?,./")];15>x.length;x.push(a(l+u+n+s)));alert(x.sort(y=>.5-R()).join(""))

```

Using a rule where:

`function(x){return x*x}` can be re-written as `function(x)x*x`. Only seems to work for functions returning a value.

Next iteration, reduced `x.sort(function().5-R())` to `x.sort(y=>.5-R())`

Next iteration, reduced further with fat arrow notation, which sadly only works for Firefox 22 and above.

# Answer
> 2 votes
## JavaScript (269 characters compacted)

For clarity, this is the code *before* I compacted it down JS-Fiddle of it:

```
var lowerLetters = "abcdefghijklmnopqrstuvwxyz";
var upperLetters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
var numbers = "0123456789";
var symbols = "`~!@#$%^&*()_+-={}|[]\\:\";'<>?,./";
var allCharacters = lowerLetters + upperLetters + numbers + symbols;

String.prototype.randomChar = function() {
    return this[Math.floor(this.length * Math.random())];
}

var minLength = 15;
var result = [];

// Start off by picking one random character from each group
result.push(lowerLetters.randomChar());
result.push(upperLetters.randomChar());
result.push(numbers.randomChar());
result.push(symbols.randomChar());
// Next, pick a random character from all groups until the desired length is met
while(result.length < minLength) {
    result.push(allCharacters.randomChar());
}
result.shuffle(); // Finally, shuffle the items (custom function; doesn't actually exist in JavaScript, but is very easy to add) -> http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
result.join("");

```

Here it is compacted down to 269 characters (JS-Fiddle of it):

```
l="abcdefghijklmnopqrstuvwxyz";
u=l.toUpperCase();
n="0123456789";
s="`~!@#$%^&*()_+-={}|[]\\:\";'<>?,./";
R=Math.random;

function r(t){
    return t[~~(t.length*R())]
}

for(x=[r(l),r(u),r(n),r(s)];x.length<15;x.push(r(l+u+n+s)));
x.sort(function(){return .5-R()});
alert(x.join(""));

```

# Answer
> 2 votes
# Clojure (63):

```
(->> (map char (range 33 127)) (shuffle) (take 15) (apply str))

```

But need to be improved to ensure that containing at least 1 character of each category (Upper, Lower, Digit, Symbol).

# Answer
> 2 votes
# In sql-server

```
declare @a nvarchar(28)
set @a='abcdefghijklmnopqrstuvwxyz'
declare @b nvarchar(max)
set @b='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
declare @c nvarchar(max)
set @c='0123456789'
declare @d nvarchar(max)
set @d='~!@#$%^&*()_+-={}|[]\:";<>?,./'

select left(substring(@a,cast(rand()*10 as int),3)+substring(@b,cast(rand()*10 as int),6)+substring(@c,cast(rand()*10 as int),3)+substring(@d,cast(rand()*10 as int),5),15)

```

# See it in action--1

# see it in Action--2

# Answer
> 2 votes
## SAS (191)

```
%macro c(p);compress(p,,"&p")ne''%mend;data x;length p$15;do x=1by 1;do t=1to 15;substr(p,t,1)=byte(ranuni(7)*94+33);end;if %c(kd)and %c(kl)and %c(ku)and %c(ad)then do;put p;stop;end;end;run;

```

`*TQP,(f=h10*)S=`

Commented/indented:

```
%macro c(p); /*compress removes or keeps certain classes of characters*/
  compress(p,,"&p")ne''
%mend;
data x;
length p$15;
do x=1by 1;
    do t=1to 15;
        substr(p,t,1)=byte(ranuni(7)*94+33); /*give it a 33-126, byte discards the noninteger portion rounding down*/
    end;
    if %c(kd)and %c(kl)and %c(ku)and %c(ad)then do; /*k=keep d=digit l/u=lower/upper ad=remove digits and alphas*/
        put p;
        stop;  /*met our requirement, head home*/
    end;
end;
run;

```

# Answer
> 2 votes
# PowerShell: 119

**Gofled Code**

```
for(;!($x-cmatch'.*(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[!-/:-@[-`{-~]).*')){$x='';1..15|%{$x+=[char](33..126|random)}}$x

```

**Un-golfed and Commented**

```
# Start for loop definition.
for(
    # Skip variable initialization, start definition of run condition.
    ;
    # Loop runs if $x does not meet complexity requirements.
    # Length requirement is not tested here because it is enforced by the generator later.
    # Much thanks to @VasiliSyrakis for the RegEx help.
    !($x-cmatch'.*(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[!-/:-@[-`{-~]).*')
)
{
    # Reset $x in case the script block has already run.
    $x='';
    # Use ForEach-Object, via the % alias, to run a loop 15 times.
    1..15|%{
        # Append a random ASCII character from 33-126 to $x.
        # Note: Use get-random instead of random for faster performance.
        $x+=[char](33..126|random)
    }
}
# Display $x.
$x
# Variable cleanup - not included in golfed code.
rv x

```

# Answer
> 1 votes
## PHP, 235 225

This script shuffles characters around and then is checked via RegEx to make sure the password is strong (or it is regenerated).

```
<?php
while(!preg_match('/^(?=.*[A-Z])(?=.*[^A-Za-z])(?=.*[0-9])(?=.*[a-z]).{15}$/',$p)){ $p = substr(str_shuffle('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789`~!@#$%^&*()_+-={}|[]\:";\'<>?,./'),0,15); }
echo $p;

```

# Answer
> 1 votes
# Powershell

---

## One Liner version (143 bytes)

```
sal g random;1..11|%{$P+=[char](33..126|g)};(65..90|g),(97..122|g),(48..57|g),(33..47+58..64+123..126|g)|%{$P=$P.insert((1..11|g),[char]$_)};$P

```

## Mini version (146 bytes)

```
sal g random
1..11|%{$P+=[char](33..126|g)}
(65..90|g),(97..122|g),(48..57|g),(33..47+58..64+123..126|g)|%{$P=$P.insert((1..11|g),[char]$_)}
$P

```

## Readable version (860 bytes)

```
function pwgen {

    # Fulfill Upper,Lower,Digit,Symbol requirement by predefining ASCII ranges for each
    # These will be added into the string beginning at line 24

    [array[]]$symbolrange = (33..47),(58..64),(123..126)

    [char]$upper = (get-random (65..90))
    [char]$lower = (get-random (97..122))
    [char]$digit = (get-random (48..57))
    [char]$symbol = $symbolrange | get-random

    [char[]]$requirement = $upper + $lower + $digit + $symbol

    # Create the first 11 characters using any ASCII character between 32 - 126

    foreach ($number in (1..11)) {
        [string]$pass += [char](get-random (33..126))
    }

    # Insert each requirement character at a random position in the string

    foreach ($char in $requirement) {
        [string]$pass = $pass.insert((Get-Random (1..11)),$char)
    }

    return $pass
}

```

> Credit to Iszi for various tips to shorten the code.

# Answer
> 1 votes
**Python 2.7 (149)**

```
from random import*
''.join(map(lambda x:chr(randint(*(x[1]or(32,126)))),sorted(map(None,sample(range(15),15),((48,57),(65,90),(97,122),(33,47))))))

```

Written out in a more readable (and not executable) way;

```
from random import *
''.join(                                          # Concatenate characters to string
  map(                                            # Map all characters using below lambda
    lambda x:chr(randint(*(x[1] or (32, 126)))),  # Map a single range to a random character
                                                  # within a specific range if supplied,
                                                  # otherwise the default "all" range.
    sorted(                                       # After distributing ranges, sort
      map(None,                                   # zip_longest alternative, distributes the
                                                  # required ranges over 4 random positions
        sample(range(15), 15),                    # 0-14 in random order
        ((48, 57), (65, 90), (97, 122), (33, 47)) # The 4 required ranges
      )
    )
  )
)

```

Fairly straight forward and surprisingly not much longer than a "generate, retry on match fail" version.

# Answer
> 1 votes
**PSQL (189)**

Feels like PSQL is a bit verbose... :)

```
SELECT ARRAY_TO_STRING(ARRAY_AGG(CHR((TRUNC((b-a)*RANDOM()+a))::int)ORDER BY RANDOM()),'')FROM(SELECT 32 a,127 b FROM generate_series(1,11)UNION ALL VALUES(48,58),(65,91),(97,123),(33,48))a

```

SQLfiddle demo.

# Answer
> 1 votes
## Perl, 92

Not as concise as the Ruby answer, but I'm sure a Perl wizard could make this even shorter... I'm not too happy with all the `m//`s at the end, but seems to work and should satisfy the conditions to eventually generate all permutations.

```
do{$_=join"",map{(map{chr}33..127)[rand 94]}0..14}while!(/[A-Z]/&/[a-z]/&/\d/&/[\W_]/);print

```

Sample usage:

```
perl -e 'do{$_=join"",map{(map{chr}33..127)[rand 94]}0..14}while!(/[A-Z]/&/[a-z]/&/\d/&/[\W_]/);print'

```

Edited to fix validation and change `[[:punct:]]` to `[\W_]` after MvGs comments.

# Answer
> 1 votes
**Javascript (209)**

```
r=Math.random;function t(x,y){return String.fromCharCode(Math.floor(y*r()+x))};x=[t(33,14),t(48,10),t(65,26),t(97,26)];for(i=0;i<11;i++)x.push(t(32,95));console.log(x.sort(function(){return r()-0.5}).join(''))

```

Semi-ungolfed;

```
// Return a character in the range [x,x+y)
function t(x,y) { return String.fromCharCode(Math.floor(y*Math.random()+x)) }
// Prefill required ranges
x=[ t(33,14), t(48,10), t(65,26), t(97,26)]
// Push 11 totally random (valid) characters
for(i=0; i<11; i++)
  x.push(t(32,95))
// Shuffle and output as string
console.log(x.sort(function(){return Math.random()-0.5})
             .join(''))

```

# Answer
> 1 votes
## Java 7 (~~270~~ 234 characters)

The premise is the same used by @assylias with java 8 (generate random passwords until valid password). However, instead of using lambdas, the password is generated by iterating a char array and validated by matching a regex.

```
class A {
  public static void main(String [] a) {
    byte[] b = new byte[15];
    String s;
    do {
      new java.util.Random().nextBytes(b);
      s = new String(b);
    } while(!s.matches("(?=.*?[a-z])(?=.*?[A-Z])(?=.*?\\d)(?=.*?[!-/:-@\\[-`]).*"));
    System.out.println(s);
  }
}

```

Minified Code:

```
class A {public static void main(String[] a){byte[] b=new byte[15];String s;do{new java.util.Random().nextBytes(b);s=new String(b);}while(!s.matches("(?=.*?[a-z])(?=.*?[A-Z])(?=.*?\\d)(?=.*?[!-/:-@\\[-`]).*"));System.out.println(s);}}

```

# Answer
> 1 votes
# Factor, 196 characters

Same algorithm as MvG and moose's. It is not the shortest but should satisfy all the (current) criteria in the question:

```
USING: io kernel math pcre random sequences sequences.repeating ;
[ 15 94 random-integers [ 33 + ] "" map-as dup 60 cycle
"[A-Z].*[a-z].*[0-9].*[\\W_]" findall { } = not ] [ drop ] until print

```

# Answer
> 1 votes
# C - 154 characters

```
char p[16],c,f,w;main(){srand(time());while(f^15){c=p[15]=f=0;while(c^15){w=33+rand()%94;f|=w
>96&&w<123?1:w>47&&w<59?2:w>64&&w<91?4:8;p[c++]=w;}}puts(p);}

```

How do I hate `srand()`? Let me count the ways.

# Answer
> 1 votes
# Haskell, 192

```
import System.Random
main=getStdGen>>= \g->(print.(take 15))$until((\x->all(any(`elem`x))[['a'..'z'],['A'..'Z'],['0'..'9'],['!'..'/']++":;<=>?@[\\]^_`{|}~"]).(take 15))tail$randomRs('"','~')g

```

The printed string has quotes around it and escapes the backslash and quote characters; if that's unacceptable, `print` can be replaced with `putStrLn` for 3 more bytes. Here's a more readable version:

```
import System.Random

main = do
    g <- getStdGen
    let chars = randomRs ('"', '~') g
    let password = take 15 $ until (hasChars.(take 15)) tail chars
    print password

hasChars :: String -> Bool
hasChars x = all (any (`elem` x)) $
    [ ['a'..'z']
    , ['A'..'Z']
    , ['0'..'9']
    , "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"
    ]

```

It's quite straightforward, it just creates an infinite/lazy list of random ASCII characters in the range `'!'` to `'~'`, then tosses out the first element until the first 15 characters have at least one character from each string of required characters.

# Answer
> 1 votes
### Excel VBA, 209 bytes

```
For i = 1 To 15
x = x + Chr(Int(90 * Rnd + 33))
Next
p = "^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*(_|[^\w])).+$"
With New RegExp
.Pattern = p
Set m = .Execute(x)
If m.Count = 0 Then
MsgBox "redo"
Else
MsgBox x
End If
End With

```

Randomly generates 15 ASCII characters so all possible combinations are possible. Then uses a regular expression pattern to check if it contains at least one of each criteria.

If it does then the password is displayed, if not "redo" is displayed.

Credit to Bart Kiers for the Regular Expression pattern: https://stackoverflow.com/questions/1559751/regex-to-make-sure-that-the-string-contains-at-least-one-lower-case-char-upper

# Answer
> 1 votes
# Python 3 \+ passgen, 64 bytes

```
import passgen as p
print(p.passgen(length=15,punctuation=True))

```

**If you have any suggestions for improvement, let me now in the comments!**

Try it online! (or rather don't, as the `passgen` module isn't on TIO)

Github: https://github.com/EacyCoding/Password\_Generator

or in one line:

```
import passgen as p;print(p.passgen(length=15,punctuation=True))

```

Sample Outputs:

```
;dLjI3pr7541(CW
3ptRCt%OK^8+iW;
dDZk7^1!53rG$3M

```

# Answer
> 0 votes
## AutoHotkey 352

```
global o:={}
loop 4
o[c()]:=o(A_index-1)
loop 11
o[c()]:=o(m(r(),4))
loop 15
s.=o[A_index-1]
msgbox % s
r(){
Random,z
return z
}
m(z,r){
return mod(z,r)
}
c(){
while o[t:=m(r(),15)]!=""
j++
return t
}
o(f){
r0:=48,l0:=10,r1:=97,l1:=l2:=26,r2:=65
r := chr(r%f%+m(r(),l%f%))
if f=3
r:=Substr("``~!@#$%^&*()_+-={}|[]\:"";'<>?,./",m(r(),32)+1,1)
return r
}

```

**Using** \- Just run the script

# Answer
> 0 votes
## Python (121 characters)

Makes use of the fact that you can multiply lists in Python \[1,2,3\] * 2 gives \[1,2,3,1,2,3\]. Imports random. Numbers in a list multiplied by three are borders between ranges in ascii table for needed characters, e.g. \[65, 90\] maps to uppercase letters.

```
print "".join([random.choice([chr(i) for i in range(z[0],z[1])]) for z in [[33,48],[48,58],[58,65],[65,90],[90,123]]* 3])

```

# Answer
> 0 votes
**Perl (134 characters)**

Perl one-liner::

```
perl -e 'push @a,map{(33..47,58..64,91..96,123..126)[rand (32)]}1;push @a,map{(65..90)[rand(26)]}1;push @a,map{(97..122)[rand(26)]}1;push @a,map{(48..57)[rand(10)]}1;push @a,map{(33..126)[rand(10)]} 1..11;foreach (@a){print chr($_);}'

```

**The Output:**

```
_Gj2()%%&)$#"%&
$Vn7"#"'#%*&$%(
]Tj2*'%)&"#"#(%

```

**Update:**

```
perl -MList::Util=shuffle -e 'push @a,map{(33..47,58..64,91..96,123..126)[rand (32)]}1;push @a,map{(65..90)[rand(26)]}1;push @a,map{(97..122)[rand(26)]}1;push @a,map{(48..57)[rand(10)]}1;push @a,map{(33..126)[rand(10)]} 1..11; @a=shuffle @a;foreach (@a){print chr($_);}'

```

# Answer
> 0 votes
**Python 3.3 (360 characters)**

First generate a random character from each list, to ensure the first rule.
Them add a random sample from the whole group of allowed characters to complete the rest of the password.
Now we have a random sequence of 15 chars (a seed), with at least one of each, but the first 4 are always, in order, a lower, an upper, a numeric and a symbol. So we shuffle the seed, thus allowing all possible and valid passwords to be generated.

```
from random import sample

lower = 'abcdefghijklmnopqrstuvwxyz'
upper = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
numeric = '0123456789'
symbol = '''`~!@#$%^&*()_+-={}|[]\:";'<>?,./'''

seed = sample(lower, 1) + sample(upper, 1) + sample(numeric, 1) + sample(symbol, 1) +\
   sample(lower + upper + numeric + symbol, 11)
pwd = ''.join(sample(seed, 15))
print(pwd)

```

# Answer
> 0 votes
**PHP 5.5 (230 bytes)**

```
echo preg_replace_callback('/./', function ($a)
{
  return chr([rand(33, 126), rand(48, 57), rand(65, 90), rand(97, 122), ord(str_shuffle('`~!@#$%^&*()_+-={}|[]\:";\'<>?,./')[0])][$a[0]]);
}
, str_shuffle(str_pad('1234', 15, 0)));

```

Or on one line (211 bytes)

```
echo preg_replace_callback('/./',function($a){return chr([rand(33,126),rand(48,57),rand(65,90),rand(97,122),ord(str_shuffle('`~!@#$%^&*()_+-={}|[]\:";\'<>?,./')[0])][$a[0]]);},str_shuffle(str_pad('1234',15,0)));

```

# Answer
> 0 votes
# F#, 67 66 59 characters

Using the same framework method as the C# solution, but obviously F# is shorter:

```
Web.Security.Membership.GeneratePassword(15,1)|>printf "%s"

```

I don't need to specify `System`, apparently.

# Answer
> 0 votes
**C++11 (489 characters)**

```
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
using namespace std;random_device r;uniform_int_distribution<> d4(0,3),d10(0,9),d26(0,25);
char rc(int t){int i=0;switch(t){case 0:i=48+d10(r);break;case 1:i=32;case 2:i+=65+d26(r);break;case 3:i=33+[](unsigned j){return j<15?j:j<22?j+10:j+68;}(d26(r));}return char(i);}
int main(){string s(15,0);int i=0;for(;i<4;i++){s[i]=rc(i);}for(;i<15;i++){s[i]=rc(d4(r));}random_shuffle(s.begin(),s.end());cout<<s<<endl;}

```

Update: stripped down from 673 to 489 characters

# Answer
> 0 votes
## Bash (111 bytes)

```
a=`strings /dev/urandom | head -c 512 | iconv -f utf-8 -t us-ascii//TRANSLIT | tr -d '\n' | head -c 15`
echo $a

```

Example outputs:

```
bw?<{qqH$lh}VC2
M)2@(nH9IdkOwYh
x;&_IR)NM7bCNd~

```

# Answer
> -1 votes
# Perl (73 characters)

```
sub x{@x=map{chr rand6+6*$_+27%122}1..15;print splice@x,rand@x,1 while@x}

```

Maybe someone can minify it more..

---
Tags: code-golf, random
---


title: Help Stack Exchange transpose tables

text:
# Question
Title: Help Stack Exchange transpose tables
Stack Exchange doesn't know how to transpose tables. Let's help.

**Given a markdown table, transpose it.**

Input assumptions:

* There will be at least two rows (including header) and two columns
* Either all cells have no leading space or all cells have exactly one leading space (you must handle both)
* If the cells have a leading space, then the widest cell in every column has exactly one trailing space, otherwise, the widest cell in every column has no trailing spaces
* All pipes line up
* The header-body separator lines of dashes extend the full width of their column, except a leading and tailing space if the table uses this
* Cell alignment (`-:`, `:-:`, etc.) is not used
* No other extraneous spaces appear (this includes between words)
* Either all rows have a trailing pipe or no rows have a trailing pipe (you must handle both)
* Cells contain only printable ASCII, but no pipes (`|`), dashes (`-`) or any characters that need special treatment (`\`, `**`, etc.)
* All cells will have at least *some* non-space content

Output requirements:

* Trailing pipe on every row or no trailing pipes (must be consist for any one result)
* Either no leading spaces, or exactly one leading space in every cell (must be consist for any one result)
* If you produce leading spaces, then the widest cell in each column must have exactly one trailing space
* All pipes must line up
* The header-body separator must extend to the full width of the column, save for leading and trailing spaces, if used in that result
* Trailing spaces (and up to one trailing line break) are acceptable

# Test cases

## A

### Test inputs (you must handle every one of these)

```
| A header | Another header |
| -------- | -------------- |
| First    | row            |
| Second   | row            |

```

```
| A header | Another header
| -------- | --------------
| First    | row
| Second   | row

```

```
|A header|Another header|
|--------|--------------|
|First   |row           |
|Second  |row           |

```

```
|A header|Another header
|--------|--------------
|First   |row
|Second  |row

```

### For any of the above inputs, output must be any one of the below
(not necessarily corresponding 1:1)

```
| A header       | First | Second |
| -------------- | ----- | ------ |
| Another header | row   | row    |

```

```
| A header       | First | Second
| -------------- | ----- | ------
| Another header | row   | row

```

```
|A header      |First|Second|
|--------------|-----|------|
|Another header|row  |row   |

```

```
|A header      |First|Second
|--------------|-----|------
|Another header|row  |row

```

## B

### Test inputs (you must handle every one of these)

```
| A header | Another header | Last column here  |
| -------- | -------------- | ----------------- |
| First    | 0              | more content here |
| Second   | row            | that's it!        |

```

```
| A header | Another header | Last column here
| -------- | -------------- | -----------------
| First    | 0              | more content here
| Second   | row            | that's it!

```

```
|A header|Another header|Last column here |
|--------|--------------|-----------------|
|First   |0             |more content here|
|Second  |row           |that's it!       |

```

```
|A header|Another header|Last column here
|--------|--------------|-----------------
|First   |0             |more content here
|Second  |row           |that's it!

```

### For any of the above inputs, output must be any one of the below
(not necessarily corresponding 1:1)

```
| A header         | First             | Second     |
| ---------------- | ----------------- | ---------- |
| Another header   | 0                 | row        |
| Last column here | more content here | that's it! |

```

```
| A header         | First             | Second
| ---------------- | ----------------- | ----------
| Another header   | 0                 | row
| Last column here | more content here | that's it!

```

```
|A header        |First            |Second    |
|----------------|-----------------|----------|
|Another header  |0                |row       |
|Last column here|more content here|that's it!|

```

```
|A header        |First            |Second
|----------------|-----------------|----------
|Another header  |0                |row
|Last column here|more content here|that's it!

```

# Answer
# Python 3.8 (pre-release), 218 bytes

```
n=[(t:=[x for s in l.split('|')if(x:=s.strip())],max(map(len,t)))for l in open(0)]
del n[1]
j=''.join
f=lambda c:j(f'|{l[c]:{w}}'for l,w in n)
print(f(0),j('|'+w*'-'for _,w in n),*map(f,range(1,len(n[0][0]))),sep='\n')

```

Try it online!

-12 bytes thanks to basic code golfing advice by @cairdcoinheringaahing :)

-25 bytes thanks to @ovs by using `open(0)` instead of `sys.stdin`!
> 16 votes

# Answer
# K (ngn/k), ~~84~~ ~~73~~ ~~67~~ 59 bytes

-6 bytes from @rak1507's trim implementation (`2(|(&\^:)_)/`)

-19 bytes from golfing

```
{,'/("|",'++?[;1;"-"]{(|/#'x)$x^,""}2(|(&\^:)_)/'"|"\)'x_1}

```

Try it online!

Takes a list of strings, one for each row. Returns a list of strings, without leading/trailing spaces, and without trailing pipes.

* `x_1` drop the row at index 1 (i.e., the one with all the `-`'s)
* `(...)'` run the code in parenthesis on each row of the input
    + `"|"\` split each row on pipes (i.e. get the cells)
    + `2(|(&\^:)_)/'` strip leading and trailing whitespace from each cell's contents
    + `{...x^,""}` remove empty cells
    + `{(|/#'x)$x...}` pad the cells (of each row) with spaces so they are all the same length
    + `?[;1;"-"]` insert a cell containing the character `"-"` in the proper place
    + `++` transpose each row to generate the correct number of `"-"`s, then transpose back
    + `"|",'` prepend a `"|"` to each cell
* `,'/` concatenate the result by column
> 9 votes

# Answer
# Ruby 2.7, 144 bytes

```
->a{(a=(a.map{_1.scan /\| ?\K[^|
]*[^|
-]/}-[[]]).map{|l|l.map{_1.ljust l.map(&:size).max}}.transpose.map{?|+_1*?|}).insert 1,a[0].tr("^|",?-)}

```

Try it online!

Takes in an array of lines, and outputs array of lines through the last output format. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves *six* bytes!
> 7 votes

# Answer
# JavaScript (ES8), 204 bytes

Expects and returns an array of lines. Uses the last output format.

```
s=>(m=[,0]).map((r,y)=>m[r&&y].map((s,x)=>(r?s:"").padEnd(w[x],"-"[r])).join`|`,s.map(w=(s,y)=>s.replace(/\| *(.+?) *(?=\||$)/g,(_,s)=>((v=s.length)<w[y]?0:w[y]=v,m[x+=x==1]=m[x++]||[])[y]=s,y+=y<2,x=0)))

```

Try it online!

## Commented

### Step 1

Extracting the content of all cells and saving them into the matrix `m[]`.

```
s.map(w =                   // w is an object used to store the max. width in each row
  (s, y) =>                 // for each string s at position y in the input array:
  s.replace(                //   match in s all occurrences of:
    /\| *(.+?) *(?=\||$)/g, //     "\|"       a pipe
                            //     " *"       followed by optional whitespace
                            //     "(.+?)"    followed by a non-greedy string
                            //                (this is the payload)
                            //     " *"       followed by optional whitespace
                            //     "(?=\||$)" followed by either a pipe or the end of
                            //                the line (not captured)
    (_, s) =>               //     for each payload string s found in there:
      ( (v = s.length)      //       define v as the length of this string
        < w[y] ?            //       if it's smaller than w[y]:
          0                 //         do nothing
        :                   //       else:
          w[y] = v,         //         update w[y] to v
        m[x += x == 1] =    //       increment x if x = 1
          m[x++] || []      //       if undefined, initialize m[x] to an empty array
                            //       increment x afterwards
      )[y] = s,             //       save s in m[x][y]
                            //     initialization:
    y += y < 2,             //       increment y if y = 0 or y = 1
    x = 0                   //       start with x = 0
  )                         //   end of replace()
)                           // end of map()

```

### Step 2

Building the output.

```
(m = [, 0])      // initialize m[] with m[1] = 0 (reserved for the separator lines)
                 // (this is actually done before step 1)
.map((r, y) =>   // for each row r[] at position y in m[]:
  m[r && y]      //   use m[0] if r = 0, or m[y] otherwise
  .map((s, x) => //   for each string s at position x in this row:
    (r ? s : "") //     use an empty string if r = 0, or s otherwise
    .padEnd(     //     pad it with:
      w[x],      //       w[x] characters
      "-"[r]     //       using hyphens if r = 0, or spaces otherwise
    )            //     end of padEnd()
  ).join`|`      //   end of inner map(); join with pipes
)                // end of outer map()

```
> 6 votes

# Answer
# PHP, ~~429~~ 420 bytes

```
$a=preg_split("/
(\W*
)?/",$argv[1]);foreach($a as&$v)$v=array_values(array_filter(explode('|',$v)));for($i=-1;++$i<max(count($a),count($a[0]));)for($j=-1;++$j<=$i;){$t=trim($a[$i][$j]);$u=$a[$i][$j]=trim($a[$j][$i]);$a[$j][$i]=$t;$m[$i]=max(strlen($t),$m[$i]);$m[$j]=max(strlen($u),$m[$j]);}for($k=-1;$b=$a[++$k];print$k?"
":"
$s
")for($l=-1;$b[++$l]!=null;){printf("|%-$m[$l]s",$b[$l]);$s.='|'.str_repeat('-',$m[$l]);}

```

Try it online!

I'm pretty sure it could be golfed a bit more, when I have time I'll try to max it

EDIT: saved 9 bytes by using an alias for `$a[$k]` and using double quotes for the `printf`. Still work to do but 420 is a good number ;)

ungolfed explanation (the outputted newlines also replaced by `\n` for readability):

```
$a=preg_split("/\n(\W*\n)?/",$argv[1]); //split input by line removing the dashes under the headers
foreach($a as&$v)$v=array_values(array_filter(explode('|',$v))); //split each line at the pipes, remove empty cells and rearrange indexes if needed
for($i=-1;++$i<max(count($a),count($a[0]));) //looping on largest array dimension
  for($j=-1;++$j<=$i;){ //swapping array values, trimming strings and we keep the largest length for each column
    $t=trim($a[$i][$j]);
    $u=$a[$i][$j]=trim($a[$j][$i]);
    $a[$j][$i]=$t;
    $m[$i]=max(strlen($t),$m[$i]);
    $m[$j]=max(strlen($u),$m[$j]);
  }
for($k=-1;$b=$a[++$k];print$k?"\n":"\n$s\n") //output of the result with the line
  for($l=-1;$b[++$l]!=null;){
    printf("|%-$m[$l]s",$b[$l]);
    $s.='|'.str_repeat('-',$m[$l]);
  }

```
> 4 votes

# Answer
# Charcoal, ~~79~~ ~~71~~ 61 bytes

```
ＷＳ¿¬⁼ιη«≔⟦⟧υＦΦ⪪ι|κ«≔⁻Ｅκμ⌕Ａκ ζ≔✂κ⌊ζ⊕⌈ζ¹κＰ⁺|κＭ⊕¬υ↓⊞υＬκ»ＭＬυ↑|⌈υ↑

```

Try it online! Link is to verbose version of code. Explanation:

```
ＷＳ¿¬⁼ιη«

```

Loop over the input rows, skipping the separator row.

```
≔⟦⟧υ

```

Start collecting the output column cell widths.

```
ＦΦ⪪ι|κ«

```

Split the row on `|`s and loop over the non-empty cells.

```
≔⁻Ｅκμ⌕Ａκ ζ

```

Remove the positions of the spaces from the list of all character indices.

```
≔✂κ⌊ζ⊕⌈ζ¹κ

```

Get the trimmed cell text.

```
Ｐ⁺|κ

```

Print the vertical line and text without moving the cursor.

```
Ｍ⊕¬υ↓

```

Move down one or two lines depending on whether this is the first cell.

```
⊞υＬκ

```

Push the width of the trimmed text to the list.

```
»ＭＬυ↑

```

Move up to the separator row.

```
|⌈υ

```

Print the separator with its vertical line.

Move to the first row.
> 3 votes

# Answer
# Perl 5, ~~269~~ 228 bytes

```
sub f{@t=map[split/\s*\|\s*/],pop()=~/^.\s?(.*?)\s*$/mg;@T=map{$c=$_-1;[map$$_[$c],@t]}1..@{splice@t,1,1};@w=map{max map y///c,@$_}@t;splice@T,1,0,[map'-'x$_,@w];join'',map{(map{sprintf'|%*s',-$w[$_],$$r[$_]}0..$#{$r=$_}),$/}@T}

```

Try it online!

```
sub f{
  @t=map[split/\s*\|\s*/],       #split at |, trim away spaces before and after
     pop()=~/^.\s?(.*?)\s*$/mg;  #pick part of each line that matter from input
  @T=map{$c=$_-1;[map$$_[$c],@t]}#transpose input table @t
     1..@{splice@t,1,1};         #cols
  @w=map{max map y|||c,@$_}@t;   #find max width of cols in transposed table
  splice@T,1,0,[map'-'x$_,@w];   #insert second line with --- of each width
  join'',                        #join pieces of output into single string
  map{                           #for each line in transposed table @T
    (
      map {
        sprintf '|%*s',          #string right padded...
          -$w[$_],               #...to width of this column
          $$r[$_]                #info in column number $_
      }
      0..$#{$r=$_}               #0..last index of current line in @T
    ),
    $/                           #newline \n (default)
  }
  @T                             #for each line in transposed table @T
}

```
> 3 votes

# Answer
# APL (Dyalog Extended), 40 bytes

```
⊃1(,/↑,2↓⊢){'|','-'⍪⍢(1∘⊖)↑⌂deb⍵⊆⍨⍵≠⊃⍵}¨

```

Try it online!

Adám's method.

**64 bytes(old)**

```
{↑,/⍉↑{'|',¨¯1⌽(m∘↑¨1⌽⍵),⍨⊂'-'/⍨m←⌈/≢¨⍵}¨¯1⌽1↓1⌽⌂deb¨'|'(≠⊆⊢)¨⍵}

```

Try it online!

Takes the input as a list of lines, outputs a character matrix.

-9 bytes using `dfns.deb`.

## Explanation

`'|'(≠⊆⊢)¨⍵` split each line on pipes(`|`)

`⌂deb¨` trim whitespace from both sides of each cell

`¯1⌽1↓1⌽` drop the row with hyphens

`{'|',¨¯1⌽(m∘↑¨1⌽⍵),⍨⊂'-'/⍨m←⌈/≢¨⍵}¨` do the following for each row:

`m←⌈/≢¨⍵` set m to the maximum cell length

`⊂'-'/⍨` create a cell of hyphens that long

`,⍨` join with

`m∘↑¨1⌽⍵` input shifted by 1, with each cell padded to length m.

`¯1⌽` shift back to original position

`'|',¨` prepend a pipe to each cell

Finally,

`⍉↑` convert to matrix, and transpose

`↑,/` join each row's cells, and convert to matrix again
> 2 votes

# Answer
# Julia 1.0, ~~146~~ 144 bytes

```
x->["|"*join(rpad.(i,l),"|") for i=zip(insert!.((n=[strip.(split(i,"|";keepempty=0>1)) for i=x[[1;3:end]]];),2,"-".^(l=maximum.(length,n)))...)]

```

input and output are arrays of strings

Try it online!
All tests!

Edit: -2 bytes by replacing `false` by `0>1`
> 2 votes

# Answer
# 05AB1E, 45 bytes

```
ā2ÊÏε'|¡õÚðδÚ}©øćU®ε€gà}©'-×šXšεεR®NèjR„| ì]»

```

Input as a list of lines. Outputs with spaces, and without trailing `|`.

Try it online (the header `|` is to convert the input into a list of lines).

**Explanation:**

```
ā            # Push a list in the range [1, (implicit) input-length]
 2Ê          # Check for each that they're NOT equal to 2
   Ï         # And only leave the lines in the input at truthy indices
             # (so we've removed the second line with the dashes)
ε            # Map each remaining line to:
 '|¡        '#  Split it on "|"
    õÚ       #  Remove leading/trailing empty strings, if the line started and/or ended
             #  with a "|"
       δ     #  Map over each part:
      ð Ú    #   Remove leading/trailing spaces
}©           # After the map: store the result in variable `®` (without popping)
  ø          # Zip/transpose, swapping rows/columns
   ć         # Pop and push remainder-list and first item separated to the stack
    U        # Pop this first item, and store it in variable `X`
 ®           # Push the list of variable `®` again
  ε          # Map over each list:
   €         #  Map over each part:
    g        #   Pop and get the length of the part
   à         #  Pop and only leave the maximum length
  }©         # After the map: store this as new value `®` (without popping)
    '-×     '# Transform each integer in the list into that many "-" as string
       š     # Prepend this list to the remainder-list
        Xš   # And then prepend the extracted head `X` back as well
ε            # Map over each list:
 ε           #  Map over each part inside the list:
  R          #   Reverse the current part
   ®         #   Push the list of integers `®`
    Nè       #   Pop and index the map-index into it
      j      #   Pad leading spaces up to that many characters to the reversed part
       R     #   Then reverse it back so the spaces are trailing
        „| ì #   And prepend "| " to the part
]            # Close the nested maps
 »           # Join each inner list by spaces, and then each string by newlines
             # (after which the result is output implicitly)

```
> 2 votes

---
Tags: code-golf, matrix, parsing, code-generation, generation
---


title: Polynomial extrapolation

text:
# Question
Title: Polynomial extrapolation
## Task

> Given a list of integers *a1, a2, …, ak* (*k* ≥ 2) and a positive integer *m*, write a function or a complete program that calculates the next *m* numbers of the list. Assume that *ai = P(i)* where
>
> *P(x) = bk-1 xk-1 \+ bk-2 xk-2 \+ … + b0*
>
> is the unique polynomial of minimum order which fits the points.

## Description

### Input

If the code is a function, input is given by an integer *k*, an array *a1, a2, …, ak* and an integer *m*.

If the code is a program, input (through stdin) is given by space-separated *k a1 a2 … ak m*.

You can assume that *k* ≥ 2 and *m* \> 0.

### Calculation

(Of course, the code can calculate the result in different way, but the result should be same.)

Find the polynomial *P(x)* which satisfies *ai = P(i)* for all 1 ≤ *i* ≤ k and has a degree of (no more than) *k* \- 1. For example, if a list is `1,2,3,4,5`, then *P(x) = x*. If a list is `1,4,9,16,25`, then *P(x) = x2*.

Then, calculate *ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m)*. These are the results.

### Output

If the code is a function, return an array \[*ak+1, ak+2, …, ak+m*\].

If the code is a full program, print those numbers to stdout, separated by an any character you want.

# Answer
## Golfscript, 46 42 40 38 chars

```
~])\({[{.@-\}*])\}*;]-1%){0\{+.}/p]}*;

```

This uses a simple difference table approach, which is described in more detail on my GolfScript blog.
> 9 votes

# Answer
## Maple, 41 chars

```
c:=(k,a,m)->interp([$1-k..0],a,x)$x=1..m;

```

For example, `c(3, [1, 2, 4], 4)` returns `7, 11, 16, 22`.

This function interprets the spec literally, taking both `k` and `a` as separate arguments. If the list `a` does not have exactly `k` elements, an error occurs. For convenience, here's a 45-char version that omits `k` from the argument list:

```
c:=(a,m)->interp([$1-nops(a)..0],a,x)$x=1..m;

```

I was first thinking of trying this in Perl, but hell, let's use the right tool for the job.
> 4 votes

# Answer
# Jelly, 18 bytes, language postdates challenge

```
Iß;@Ḣ+\øṁ⁹µL?
çUḣU

```

Try it online!

Jelly's functions only support up to two arguments, so I don't take in *k* (which is redundant) as an argument. I hope that's acceptable. The program defines a function  that obeys the specification in the question.

## Explanation

**Helper function**  (takes input λ, ρ, and expands λ by ρ elements):

```
Iß;@Ḣ+\øṁ⁹µL?
       ø  µ ? If
           L    {λ} is nonempty,
              then:
I               take differences of consecutive elements of {λ};
 ß              call 1ŀ recursively on this value and {ρ};
  ;@            prepend
    Ḣ           the first element of {λ};
     +\         and take the cumulative sum {and return it}.
              Otherwise:
        ṁ⁹      {return} {0} repeated ρ times.

```

This is fairly magical in the way in which Jelly happens to pick out the exactly values I need it to operate on at every stage. Some of it is the result of me manipulating things; in particular, the unusual choice `ø` for the separator (rather than the more usual `µ`) means that all implicit arguments are set to 0, which is fairly handy in this case. However, I have no idea why `;@Ḣ` parses the way it does, but it seems to work…

**Main function**  (takes input λ, ρ, and returns the next ρ elements of λ):

```
çUḣU
ç             Call 1ŀ on {λ} and {ρ};
 U            reverse it;
  ḣ           take the first {ρ} elements;
   U          and reverse it {and return that value}.

```

This is just massaging the output into the form requested (if we were allowed to return the terms we were already given, that would remove a whole 5 bytes). Jelly doesn't have a "last n elements" function; of the various ways to synthesize it out of other functions, `UḣU` is convenient here because it happens to pick up ρ as a default argument.
> 3 votes

# Answer
### Golfscript, 51 characters

Similar approach to Peter's one.

```
~])\-1%[{(.@{.@\-}%\;.,}do;]-1%\[0]\*\{\{+.}%\;}%;p

```

When run on input

```
2 3 12 35 78
4

```

it yields the result

```
[147 248 387 570]

```

There are still possible places where the solution might be golfable further.
> 1 votes

# Answer
# Scala, 128 bytes

```
m=>Stream.iterate(_)(a=>a.tail.lazyZip(a)map(_-_)).takeWhile(Nil!=).:\(Seq.fill(m)(0))((a,b)=>b.scanLeft(a(0))(_+_))takeRight(m)

```

Try it online!
> 0 votes

---
Tags: code-golf, math, array
---


title: Linear integer function generator

text:
# Question
Title: Linear integer function generator
Inspired by a recent challenge involving Fibonacci numbers in which OEIS was mentioned, I would like to present a challenge of creating a function that generates a wide array of different linear integer sequences, depending on user input.

Specifically, the user should provide three inputs:

1. the kernel (a representation of the recurrence relation). More about this below.
2. the starting value of every 'seed' needed for the sequence, and
3. the number of integers to generate and display.

For example, the Fibonacci sequence has two members in the kernel and needs two starting seeds (0, 1). Then \\$F(n) = F(n-1) + F(n-2)\\$.

The Padovan sequence has *three* members in its kernel and needs three seeds, (1,0,0). Then \\$F(n) = F(n-2) + F(n-3)\\$.

I am not going to mandate the format of the 'kernel' input, though the natural form would be, I think, a list of the same length of the list of seeds, composed of integers corresponding to the weight to give to each of integers in the previous row.

This means that the kernel of the Fibonacci sequence, which adds together the previous two numbers, can be represented as (1,1). By contrast, the kernel of the Padovan sequence, which ignores the first member of the previous row and adds the second and third terms, can be represented as (0,1,1).

Your code should be able to handle an arbitrary number of seeds and lists of arbitrary length. For each sequence, the number of members of the kernel and the length of the seed list should be the same positive integer. For the sake of this challenge, assume all members of the kernel and all seed values are integers (though I suspect that most of the responses to this challenge will work for all real numbers). Similarly assume the required sequence length will be a positive integer.

My examples below use (parentheses) to encapsulate lists, but use whatever notation is most natural to your programming language.

**Examples!**

For the Fibonacci sequence, your function should take three inputs like

```
(1, 1), (0, 1), 10

```

(that's kernel, seed, and sequence length), and generate

```
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

```

For the Padovan sequence, input like

```
(0, 1, 1), (1, 0, 0), 20

```

should generate

```
(1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37)

```

The Perrin Sequence takes input like

```
(0, 1, 1), (3, 0, 2), 10

```

to produce

```
(3, 0, 2, 3, 2, 5, 5, 7, 10, 12)

```

For edge cases,

```
(1, 1), (0, 0), 5

```

should produce

```
(0,0,0,0,0)

```

and

```
(-1, 0, 1, 0), (0, -1, 0, 1), 20

```

should produce

```
(0, -1, 0, 1, -2, 2, -1, -1, 3, -4, 3, 0, -4, 7, -7, 3, 4, -11, 14, -10).

```

I suspect there are going to be some extremely concise responses to this.

# Answer
> 4 votes
# 05AB1E, ~~9~~ 7 bytes

Inputs are the seed, then the kernel and the number of integers last.

Thanks to Kevin Cruijssen for -2 bytes!

```
λ£³ā₆*O

```

Try it online! or Try all cases!

The challenge reads like it's made for the recursive list generation builtin `λ` ;)

`λ£` takes the seed and the number as input and generates the first terms of the sequence starting with the values from the seed. `²ā₆*O` is executed to generate each `a(n)`:
`²` pushes the second input, the kernel.
`ā` pushes the range `[1,2,...,len(kernel)]`.
For each `k` in this range  gets the previous value `a(n-k)` to get the new list `[a(n-1), a(n-2), ..., a(n-len(kernel))]`.
`*` multiplies this element-wise with the kernel.
`O` sums up all values to generate `a(n)`.

---

# 05AB1E, 10 bytes

First input is the number of integers, then the the seed and the kernel last.

```
FDŠR*Oª}¹£

```

Try it online! 1 byte longer without `λ`.

```
F      }    # iterate input times
 D          # duplicate the current sequence (initially: seed)
  Š         # triple swap -> stack: [sequence, kernel, sequence]
   R        # reverse the current sequence
    *       # multiply element-wise with the kernel
     O      # take the sum
      ª     # append the new value to the sequence
        ¹£  # take as many numbers as required

```

# Answer
> 8 votes
# Wolfram Language (Mathematica), 16 bytes

```
LinearRecurrence

```

Try it online!

Given the OP's background, I suppose this isn't too much of a surprise.

# Answer
> 7 votes
# Kakoune, 62 keystrokes

```
<a-l>"ndd<a-l>S
"hddQxy<a-p><a-p>_S
a*<c-r>h+<a-;> <backspace><esc><a-h>|bc
k<a-i>ndd<a-j>Q:ex<tab> <c-r>nq
K<a-x>d%<a-s><a-h>w<a-l>d<a-j>

```

(note the trailing spaces on line 1 and 2)

Assumes the input in the following format, with the cursor at the start of the buffer:

```
number of items
kernel separated with spaces in reverse
seed separated by spaces

```

Gives the output as the numbers space separated.

Here is a video of the solution in action, with a few minor human errors :)

# Answer
> 6 votes
# Factor, 38 bytes

```
[ [ 2dup v. prefix dup pop . ] times ]

```

Try it online!

Takes the inputs in the order of `kernel seed(reversed) length`, and prints out the desired sequence to STDOUT, one item per line. The seed must be of a sequence type that supports `pop` method, e.g. a `vector`.

```
[               ! ( kernel seed length -- kernel seed' )
  [             ! inner quotation ( kernel seed -- kernel seed' )
    2dup v.     !   evaluate next item using vector dot product
    prefix      !   prepend to seed
    dup pop .   !   remove the last item from seed and print
  ] times       ! run the above `length` times
]

```

---

# Factor, 45 bytes

```
[ [ 2dup reverse v. suffix unclip . ] times ]

```

Try it online!

Taking the seed in the given order costs 8 bytes for `reverse<space>` which is needed for dot product, but 1 byte can be saved by replacing `dup pop` with `unclip`.

# Answer
> 6 votes
# Haskell, ~~54~~ 49 bytes

```
g k(x:r)n=take n$x:g k(r++[sum$zipWith(*)k$x:r])n

```

Try it online! Use as `g kernel seed n`.

Previously, the function `g` only took the seed and the kernel as input and recursively build the sequence as an infinite list, with a second function truncating this infinite sequence to the given length with `take n`. However, it turns out we can just incorporate this truncation into `g` because of lazy evaluation, saving 5 bytes.

# Answer
> 4 votes
# APL (Dyalog Extended), 23 (SBCS)

Full program. Prompts for seed (reversed of OP's), then required length, then kernel (OP's).

```
⎕(⌽⊣≢⍛↓(⊢,⍨⊣+.×≢⍛↑)⍣⎕)⎕

```

Try it online!

`⎕(``)⎕` apply the following tacit function with kernel and seed as left and right arguments:

`(``)⍣⎕` prompt for required length, and apply the following tacit function that many times:

`≢⍛↑` take length-of-kernel elements from the (reversed) seed/list

…`+.×` dot product with:

the kernel

`,⍨` append:

the seed/list

…`≢⍛↓` drop as many elements as there are elements in:

the kernel

reverse

---

Old solution using a function kernel:

## APL (Dyalog Unicode), 12 bytes (SBCS)

Anonymous infix lambda, taking seed as right argument and required sequence length as left argument. Prompts for kernel as a prefix function that takes a list as argument and computes the next term.

```
{⍺↑,∘⎕⍨⍣⍺⊢⍵}

```

Try it online! (with helper operator to make kernel input easy)

`{``}` "dfn"; left and right arguments are  and :

`⊢⍵` on the seed

…`⍣⍺` apply the following function as many times as terms required:

`,∘` catenate self with result of applying the following function:

get kernel function from console

`⍺↑` take as many terms as required

# Answer
> 4 votes
# , 28 bytes

```
0{"1(}.@],1#.]*1>@{[)^:(0{[)

```

Try it online!

There are a lot of ugly mechanics in this solution, even though the underlying "power of" verb `^:` solves the problem nicely.

The issue is that we have only two arguments in J, and have to get 3 pieces of information into the verb, so have to make one of the arguments do double duty, and then waste a lot of bytes de-structuring.

J902 has the `F:` conjunction which expresses recurrences naturally, but you have use the awkward and verbose "terminate fold" `Z:` to express "n iterations".

The other approach I tried was to create the powers of the appropriate matrix (the recurrence as the top row, stacked on the identity matrix with the last row cut off), and multiply those by the seed. Also a nice solution, but requires enough mechanics that I couldn't get the byte count down.

## , another approach, 29 bytes

```
0{"1(}.@],1#.*)/@|.\@(0}#&>/)

```

Try it online!

# Answer
> 4 votes
# Python 3, ~~72~~ ~~67~~ 64 bytes

Takes as input \\$k\\$, \\$s\\$ and \\$n\\$, which are the kernel, seed, and number of integers to display, respectively.

```
lambda k,s,n:s[exec("s+=sum(map(int.__mul__,s[::-1],k)),;"*n):n]

```

Try it online!

### Python 3, 72 bytes

```
f=lambda k,s,n:len(s)//n*s or f(k,s+[sum(map(int.__mul__,s[::-1],k))],n)

```

Try it online!

# Answer
> 4 votes
# ARM Thumb-2, strict ruleset, 34 bytes

Machine code:

```
4563 d90d 4664 2700 000a 3c01 5705 f912
6b01 fb06 7705 d8f8 7017 3101 3b01 e7ef
4770

```

Overcommented assembly with C-callable wrapper (not part of score, just for testing with C)

```
        // Now with C-style comments because no ARM syntax highlighting
        .syntax unified
        .arch armv6t2
        .thumb
        // Params (note kernel_length is r12, not r2)
        // int8_t *kernel:         kernel (test case order)
        ker_p   .req r0
        // int8_t *seed_out_ptr:   seed/output array
        out_p   .req r1
        // uint32_t kernel_length: Kernel length in elements
        ker_len .req r12
        // uint32_t seq_length:    Sequence length in elements
        seq_len .req r3

        // Local temps
        // Clobbers r4-r7.
        i       .req r4 // Loop counter
        j       .req r2 // seq_p copy for loop
        k_co    .req r5 // Kernel coefficient
        f_i     .req r6 // F(n - i)
        dot_p   .req r7 // Dot product

        // Custom calling convention, hence the dot. See below for a C wrapper.
        .globl .linear_gen
        .type .linear_gen, %function
        .thumb_func
.linear_gen:
.Lmain_loop:
        // Loop while seq_len > ker_len
        cmp     seq_len, ker_len
        bls     .Lmain_loop.end
        // Loop backwards from kernel_length to 0.
        mov     i, ker_len
        // Initialize dot product at 0
        movs    dot_p, #0
        // Make a copy of the pointer
        movs    j, out_p
.Ldot_product_loop:
        // Decrement loop counter
        subs    i, #1
        // Load kernel coefficient
        ldrsb   k_co, [ker_p, i]
        // Load F(n - i), incrementing the pointer as we go. (wide insn)
        ldrsb   f_i, [j], #1
        // dot_p += f_i * k_co (wide insn)
        mla     dot_p, f_i, k_co, dot_p
        // loop while i is > 0 (mla doesn't affect flags)
        bhi     .Ldot_product_loop
.Ldot_product_loop.end:
        // Store the dot product into out_p[kernel_length].
        // We can just reuse j because the loop will leave it at
        // this point.
        strb    dot_p, [j]
        // Increment out_p
        adds    out_p, #1
        // Decrement seq_len
        subs    seq_len, #1
        // loop
        b       .Lmain_loop
.Lmain_loop.end:
        // return
        bx      lr

#ifdef C_WRAPPER
        // C wrapper
        .global linear_gen
        .type linear_gen, %function
        .thumb_func
        // void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_len, uint32_t sequence_len);
linear_gen:
        // save callee saved registers
        push    {r4-r7, lr}
        // fix parameters
        mov     ker_len, r2
        // call the function
        bl      .linear_gen
        // restore registers and return
        pop     {r4-r7, pc}
#endif // C_WRAPPER

```

C signature (for wrapped version)

```
void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_len, uint32_t sequence_len);

```

The arrays are `int8_t *` as it is the easiest type to work with due to how offsetting works, but the algorithm would work with any integer type.

This version is VERY awkward from an implementation standpoint.

Specifically, these are the issues:

* The kernel is in the opposite order of the seed, requiring one pointer to index forwards and the other to index backwards. Thumb doesn't have negative register indexing.
    + This extra pointer pushes us to use a high register which is very restrictive in what you can do with narrow instructions.
* The sequence length is always greater **or equal** to the kernel length. This requires the comparison to be *before* the loop.

Now, let's bend the rules a tiny bit to make things **significantly** less awkward.

* The kernel order is **reversed** from the test cases.
    + This simplifies indexing, saving 4 bytes.
        - We only need one counter, removing a `movs`
        - This also allows us to keep everything in low registers, meaning we can still index the `strb`, with `ker_len` instead of `j`.
        - We can use the narrow form of `ldrb` in the loop.
* The sequence length is always **greater than, never equal** to the kernel length.
    + This means we can move the branch to the bottom, saving 2 bytes.
    + Don't know why this isn't the case...running zero times is a little silly, and none of the test cases show the length being equal to the sequence length.

Under this altered ruleset, we save 6 bytes and can be a lot more orthodox in the parameters, storing them in the traditional `r0, r1, r2, r3` instead of `r0, r1, r12, r3`.

## ARM Thumb-2, altered ruleset (non-competing?), 28 bytes

Machine code:

```
1a9b 0014 2700 3c01 5705 570e fb06 7705
d8f9 548f 3101 3b01 d8f3 4770

```

Commented assembly (Differing lines marked with `// <`)

```
        // Now with C-style comments because no ARM syntax highlighting
        .syntax unified
        .arch armv6t2
        .thumb
        // Params
        // int8_t *kernel:         kernel (reversed from test case order)
        ker_p   .req r0
        // int8_t *seed_out_ptr:   seed/output array
        out_p   .req r1
        // uint32_t kernel_length: Kernel length in elements
        ker_len .req r2 // <- not r12
        // uint32_t seq_length:    Sequence length in elements (> kernel_length)
        seq_len .req r3
        // Local temps
        // Clobbers r4-r7.
        i       .req r4 // Loop counter
        k_co    .req r5 // Kernel coefficient
        f_i     .req r6 // F(n - i)
        dot_p   .req r7 // Dot product

        // custom calling convention. See linear_gen for a C wrapper.
        .globl .linear_gen
        .type .linear_gen, %function
        .thumb_func
.linear_gen:
        // Subtract kernel_length from sequence_length to get
        // the iteration count.
        subs    seq_len, ker_len // <- since ker_len is a low reg now, we can subtract
.Lmain_loop:
        // Loop while seq_len > ker_len
        // cmp     seq_len, ker_len // <- we no longer need the branch at the top,
        // bls     .Lmain_loop.end // <- because we know it is never equal
        // Loop backwards from kernel_length to 0.
        movs    i, ker_len
        // Initialize dot product at 0
        movs    dot_p, #0
.Ldot_product_loop:
        // Decrement loop counter
        subs    i, #1
        // Load kernel coefficient
        ldrsb   k_co, [ker_p, i]
        // Load F(n - i)
        ldrsb   f_i, [out_p, i] // <- not wide insn, just register+register
        // dot_p += f_i * k_co (wide insn)
        mla     dot_p, f_i, k_co, dot_p
        // loop while i is > 0 (mla doesn't affect flags)
        bhi     .Ldot_product_loop
.Ldot_product_loop.end:
        // Store the dot product into out_p[kernel_length]
        strb    dot_p, [out_p, ker_len] // <- Instead of j, we can use ker_len. Same size.
        // Increment out_p
        adds    out_p, #1
        // Decrement seq_len
        subs    seq_len, #1
        // Loop while not zero
        bhi     .Lmain_loop // <- Use flags from subs for loop
.Lmain_loop.end:
        // return
        bx      lr

#if 1
        // C wrapper
        .global linear_gen
        .type linear_gen, %function
        .thumb_func
        // void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_length, uint32_t sequence_length);
linear_gen:
        // save callee saved registers
        push    {r4-r7, lr}
        // fix parameters
        // mov     ker_len, r2 // <- kernel_len is already r2
        // call the function
        bl      .linear_gen
        // restore registers and return
        pop     {r4-r7, pc}
#endif

```

***Technically***, we could go further and say that the sequence\_length should not include kernel\_length for another 2 bytes, but that is DEFINITELY pushing it.

# Answer
> 3 votes
# Zsh, ~~87~~ 81 bytes

*-6 bytes thanks to @pxeger*. *-6 bytes for a score of **75 bytes** by taking the kernel in reverse*.

```
K=(${(Oa)=1})    # Use "K=($=1)" if kernel is reversed
S=($=2)
repeat $3-$#S S+=$[`printf +%s\*%s ${S[-$#K,-1]:^K}`]
<<<$S

```

~~Try it online!~~  Try it online! (81 bytes/original input) Try it online! (75 bytes/reversed kernel)

Takes the lists as space-delimited.

```
kern=(${(Oa)=1})                   # = split on $IFS, (Oa) reverse order
seed=($=2)                         # = split on $IFS
repeat $3-$#seed;{                 # repeat's argument is interpreted arithmetically
    tmp=(${seed[-$#kern,-1]:^kern} # zip the last len(kern) arguments of seed with $kern
    printf -v next +%s\*%s $tmp    # next='+s_(n-1)*k_1+s_(n-2)*k_2 ...'
    seed+=$[next]                  # interpret $next arithmetically, append to $seed
}
<<< $seed                          # output seed array

```

# Answer
> 3 votes
# Haskell, ~~70~~ 65 bytes

```
f k s n=take n$foldl(\a t->a++[sum$zipWith(*)(drop t a)k])s[0..n]

```

Try it online!

* saved 5 thanks to @Laikoni

```
take n$     - return n elements
foldl(...)s - fold adding to seed
[0..n]      - index of first seed to use(had to add n because infinite list didn't worked)
(\a t->a++  - again, add to seed
[sum[x*y|(x,y) - sum of terms
zip(drop t a)k]- make pairs dropping t elements from list

```

# Answer
> 3 votes
# Scala, ~~75~~ 71 bytes

*-4 bytes thanks to user!*

```
k=>n=>1.to(n-k.size)./:(_)((x,_)=>x:+(x.reverse,k).zipped.map(_*_).sum)

```

Try it online!

# Answer
> 2 votes
# Raku, 50 bytes

```
{@^k;(|@^s,{sum @k Z*@_[@_-1…@_-@k]}…*)[^$^z]}

```

Try it online!

* `@^k` (the kernel), `@^s` (the seed), and `$^z` (the count of elements to return) are the parameters to the function.
* `(|@^s, { ... } … *)` is an infinite sequence starting with the flattened seed array. The brace expression is a function which generates successive elements; it takes the entire list of previous elements in the `@_` variable.
* `@_[@_-1 … @_-@k]` is the last N elements of the sequence so far, in reverse order, where N is the size of the kernel list.
* `sum @k Z* @_[...]` computes the sum of the kernel zip-multiplied with the previous N elements of the sequence.

# Answer
> 2 votes
# PowerShell, 90 67 bytes

-Thanks to mazzy yet again for putting me to shame with a 23 byte save!!

```
$r,$s,$l=$args;for(;$l-$s.Count){$s+=&{$r|%{$a+=$_*$s[--$i]};$a}}$s

```

Try it online!

# Answer
> 2 votes
# Jelly, 9 8 bytes

```
Ṛḋ⁵ṭƲ⁴¡ḣ

```

Try it online!

Takes three arguments in this order: seed, number of repetitions, kernel.

## Explanation

```
Ṛḋ⁵ṭƲ⁴¡ḣ   Main dyadic link (third argument can't be accessed tacitly)
      ¡    Repeat [on the first argument, the seed]
     ⁴     (second argument) times
    Ʋ      (
Ṛ            Reverse
 ḋ           Dot product
  ⁵          with the third argument, the kernel
   ṭ         Append that to the first argument
    Ʋ      )
       ḣ   Take the first (second argument) items [because we produced too many terms]

```

# Answer
> 2 votes
# , 62 bytes

```
function(k,s,n)for(i in 1:n){show(s[1]);s=c(s[-1],rev(k)%*%s)}

```

Try it online!

# Answer
> 2 votes
# C (tcc), ~~99~~ 98 bytes

```
t,i;f(k,s,n,z)int*k,*s;{for(;n--;s[z-1]=t)for(t=i=!printf("%d ",*s);i<z;s[i]=s[++i])t+=s[i]*k[i];}

```

Try it online!

* saved 1 thanks to @ceilingcat.
* essentially moves the seed array along the sequence, printing the first element, n times.

f(k,s,n,z) - input: kernel, seed, number, length of k,s
{for(;n--;s\[z-1\]=t) - repeat n times, updating last seed with next term
for(.. i\<z;s\[i\]=s\[++i\]) - loop trough k,s swapping s back
printf("%d ",\*s) - and printing first seed
t+=s\[i\]\*k\[i\] : accumulate next term

# Answer
> 1 votes
# Charcoal, 17 bytes

```
Ｆζ⊞ηΣＥθ×κ§⮌ηλＩ…ηζ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｆζ

```

Generate `l` more terms:

```
⊞η

```

Push to the seed...

```
ΣＥθ×κ§⮌ηλ

```

... the dot product of the kernel and the reversed seed.

```
Ｉ…ηζ

```

Print the first `l` terms of the seed (it's slightly golfier to generate extra unwanted terms).

# Answer
> 1 votes
# Husk, 10 bytes

```
↑⁴¡ȯΣz*²↔⁰

```

Try it online!

```
↑⁴              # first n=arg3 elements of
  ¡ȯ     ⁰      # list created from repeatedly applying to arg1 and appending results:
    Σ           # sum of
     z*         # elementwise products of
       ²        # arg2, and
        ↔       # reverse of arg1

```

# Answer
> 1 votes
# Julia, 46 bytes

```
g(k,s,n)=try s[1:n]catch;g([0;k],[s;s'k],n)end

```

Try it online!

---
Tags: code-golf, math, sequence
---