title: Too many spies!

text:
# Question
Title: Too many spies!
You are fighting an extensive network of enemy **spies**. You know that each spy has at least one (sometimes multiple) **fake identities** they like to use. You'd really like to know how many spies you're actually dealing with.

Luckily, your counter-intelligence **agents** are doing their job and can *sometimes* figure out when two fake identities are actually controlled by the same enemy spy.

That is to say:

* Your agents don't always know when two fake identies have the same spy behind them, however
* If an agent tells you two fake identities are controlled by the same spy, you trust they are right.

# Agent messages

Agents send you cryptic messages telling you which identities have the same spy behind them. An example:

You have **2 agents** and **5 fake identities** to deal with.

The first agent sends you a message:

```
Red Red Blue Orange Orange

```

This means they think there are 3 spies:

* the first one (Red) controls identities 1 and 2
* the second one (Blue) controls identity 3
* the third one (Orange) controls identities 4 and 5

The second agent sends you a message:

```
cat dog dog bird fly

```

This means they think there are 4 spies:

* the first one (cat) controls identity 1
* the second one (dog) controls identities 2 and 3
* the third one (bird) controls identity 4
* the fourth one (fly) controls identity 5

Compiling the intel we see:

```
Identities:   id1    id2    id3    id4    id5
Agent 1:    |--same-spy--|       |--same-spy--|
Agent 2:           |--same-spy--|
Conclusion: |-----same-spy------||--same-spy--|

```

This means there are at most **2 spies**.

# Notes

Identities owned by the same spy do not have to be consecutive, i.e. a message like:

```
dog cat dog

```

is valid.

Also, the same word might be used by two different agents - that does not mean anything, it's just a coincidence, e.g.:

```
Agent 1: Steam Water Ice
Agent 2: Ice Ice Baby

```

Ice is used by both agents - the `Ice` used by the first agent is unrelated to the two occurences of `Ice` used by the second agent.

# Challenge

Compile all your agents' intel and figure out how many enemy spies there really are. (To be more precise, get the lowest upper bound, given the limited information you have.)

The shortest code in bytes wins.

# Input and Output spec

The input is a list of n lines, which represent n messages from agents. Each line consists of k space-separated tokens, same k for all lines. Tokens are alphanumeric, arbitrary length. Case matters.

The output should be a single number, representing the number of distinct spies, based on your agents' intel.

# Examples

### Example 1

Input:

```
Angel Devil Angel Joker Thief Thief
Ra Ra Ras Pu Ti N
say sea c c see cee

```

Output:

```
2

```

### Example 2

Input:

```
Blossom Bubbles Buttercup
Ed Edd Eddy

```

Output:

```
3

```

### Example 3

Input:

```
Botswana Botswana Botswana
Left Middle Right

```

Output:

```
1

```

### Example 4

Input:

```
Black White
White Black

```

Output:

```
2

```

### Example 5

Input:

```
Foo Bar Foo
Foo Bar Bar

```

Output:

```
1

```

### Example 6

Input:

```
A B C D
A A C D
A B C C
A B B D

```

Output:

```
1

```

### Example 7

Input:

```
A B A C

```

Output:

```
3

```

### Example 8

Input:

```
A
B
C

```

Output:

```
1

```

### Example 9

Input:

```
X

```

Output:

```
1

```

# Answer
# Sledgehammer 0.5.1, ~~16~~ 15 bytes

```
⡡⠥⡀⡾⠥⢢⠍⣽⡷⣩⣅⡷⣡⢒⠅

```

Decompresses into this Wolfram Language function (the final `&` is implicit):

```
Length[ConnectedComponents[RelationGraph[Inner[Equal, ##1, Or] &,
    Transpose[StringSplit @ #1]]]] &

```

Try it online!

`Transpose[StringSplit @ #1]`: Split each string in the input list, and take the columns (spy identities)

`RelationGraph[Inner[Equal, ##1, Or] &, ...]`: Construct the graph where two vertices share an edge if at least one position is equal (if they are classified as the same spy by some friendly agent)

`Length[ConnectedComponents[...]]`: The number of connected components is the upper bound on the possible number of spies.
> 10 votes

# Answer
# JavaScript (Node.js),  ~~155 150 142~~  141 bytes

```
a=>new Set((a=a.map(s=>s.split` `))[0].map((_,x)=>a.flat(m=1<<x).map(o=_=>a.map((b,y)=>b.map((w,i)=>m>>i&1|o[w+=y]?o[w]=m|=1<<i:0)))|m)).size

```

Try it online!

### How?

For each column \\$x\\$, we build a bitmask \\$m\\$ of linked columns (including the \\$x\\$th column). We eventually return the number of distinct bitmasks.

```
+---------+-------+-------+-------+-------+-------+-------+
| x       |   0   |   1   |   2   |   3   |   4   |   5   |
+---------+-------+-------+-------+-------+-------+-------+
| 2**x    |   1   |   2   |   4   |   8   |  16   |  32   |
+---------+-------+-------+-------+-------+-------+-------+
| words   | Angel | Devil | Angel | Joker | Thief | Thief |
|         | Ra    | Ra    | Ras   | Pu    | Ti    | N     |
|         | say   | sea   | c     | c     | see   | cee   |
+---------+-------+-------+-------+-------+-------+-------+
| bitmask |  15   |  15   |  15   |  15   |  48   |  48   |
+---------+-------+-------+-------+-------+-------+-------+

```

### Commented

```
a =>                      // a[] = input
new Set(                  // we eventually convert the generated array into a set
  (a = a.map(s =>         // we first need to convert each line into
    s.split` `            // an array of words (*sigh*)
  ))                      //
  [0].map((_, x) =>       // for each word at position x in the first line:
    a.flat(m = 1 << x)    //   initialize a bitmask m with the x-th bit set and build an
                          //   array containing as many entries (N) as there are words in
                          //   the whole matrix
    .map(o =              //   the object o is used to store words
         _ =>             //   repeat N times to ensure that all relations are found:
      a.map((b, y) =>     //     for each line b[] at position y in a[]:
        b.map((w, i) =>   //       for each word w at position i in b[]:
          m >> i & 1 |    //         if the i-th bit is set in m (the relation already
                          //         exists)
          o[w += y] ?     //         or w + y is set in o (a relation exists in this line):
            o[w] =        //           set o[w + y] (the value doesn't matter as long as
                          //           it's non-zero)
              m |= 1 << i //           set the i-th bit in m
          :               //         else:
            0             //           do nothing
        )                 //       end of map() over the words
      )                   //     end of map() over the lines
    ) | m                 //   end of map() over all flatten entries; yield m
  )                       // end of map() over x
).size                    // return the size of the corresponding set

```
> 9 votes

# Answer
# Jelly, 19 bytes

```
ḲiⱮ`)ZŒc€ẎyⱮ@ƒƊÐLQL

```

Try it online!

Takes input as a list of space-separated lines (the footer accounts for that).

Note: `ḲŒQ)PS` does **not** work.
> 6 votes

# Answer
# Python 3, ~~132~~ ~~162~~ ~~154~~ ~~139~~ 135 bytes

```
def f(a):r=[*zip(*[map(b.index,b)for b in map(str.split,a)])];return sum(i==min(min(u)for u in r if min(w)in u)for i,w in enumerate(r))

```

Try it online!

This is a very compact implementation of a graph algorithm identifying clusters.

1. For each agent, we create a map of profiles and their alias, which is the lowest index of appearance: `[map(b.index,b)for b in map(str.split,a)]`. I.e. `[0,1,2,1,2]` identifies three spies, where the first profile belongs to one, the second and fourth to another one and the third and fifth to the last one. The group index is also the index of the first profile in the group.
2. By transposing this matrix (`[*zip(*m...)]`), we get a group membership for each profile. This forms a directed, acyclic graph, because the group indices are a subset of the profile indices, and all edges go towards lower or equal indices. Profiles corresponding to the same spy now form a cluster with no connections to the other profiles. We still have duplicate paths though, because profile indices are linked to multiple groups indices.
3. With the following loops, we minimize the the graph to a flat forest, where all profiles are linked directly to the lowest index in their tree, i.e. the root: `min(min(u)for u in r if min(w)in u)`
4. Finally, return the number of roots in the forest, i.e. indices linked to themselves: `return sum(i==...)`.
> 6 votes

# Answer
# Charcoal, ~~49~~ 43 bytes

```
≔⪪Ｓ θＷＳ«≔⪪ι ιＦＬιＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»ＩＬΦθ⁼κ⌕θι

```

Try it online! Link is to verbose version of code. Could possibly save a couple of bytes by using a cumbersome input format. Explanation:

```
≔⪪Ｓ θ

```

Input the first agent's list.

```
ＷＳ«

```

Repeat for the remaining agents.

```
≔⪪ι ι

```

Input their list.

```
ＦＬι

```

Loop over each element index.

```
ＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»

```

Find the first element in this agent's list with the same identity and update the first agent's list to show that they are the same identity.

```
ＩＬΦθ⁼κ⌕θι

```

Count the number of unique identities remaining.
> 5 votes

# Answer
# Jelly, ~~25~~ 15 bytes

```
ḲĠ)ẎfƇFQɗⱮQ$ÐLL

```

Try it online!

A monadic link taking a list of space-separates agent claims and returning the lowest upper bound of the number of distinct spies.

## Explanation

```
  )              | For each list:
Ḳ                | - Split at spaces
 Ġ               | - Group indices of equal items
   Ẏ             | Tighten lists, so we have a single list of grouped indices
           $ÐL   | Repeat the following until no change:
        ʋⱮQ      | - Do the following as a dyad, mapping through each element of the uniquified list as the right argument
    fƇ           |   - Keep only those list members with one or more items matching the right argument
      F          |   - Flatten
       Q         |   - Uniquify
              L  | Finally take the length of the resultant list

```

Thanks to @Arnauld and @JonathanAllan for identifying issues with previous versions, and to @JonathanAllan again for saving a byte! If the input spec were relaxed to allow a list of lists, this would save one byte.
> 5 votes

# Answer
# JavaScript (Node.js), 120 bytes

```
a=>a.map(l=>(s=l.split` `).map((w,i)=>r[o(i)]=o(s.indexOf(w)),o=i=>r[i]-i?o(r[i]):i),r=[])|r.map(g=(v,i)=>t+=v==i,t=0)|t

```

Try it online!

```
a=>a.map(l=>(                  // for each line
  (s=l.split` `).map((w,i)=>(  // for each words in line
    r[o(i)]=o(s.indexOf(w)),   // join(current index, first occurrence index)
  )),                          //   without updating nodes in path
  o=i=>r[i]-i?o(r[i]):i,       // a function to find root of some node
  r=[]                         // initial disjoint-set
))|
r.map(g=(v,i)=>t+=v==i,t=0)|   // count roots of tree
t                              // output

```
> 4 votes

# Answer
# Python 3, ~~191~~ 182 bytes

### Thank you recursive

```
e=enumerate
def f(a):
	r=[list(map(b.index,b))for b in map(str.split,a)]
	for z in r:
		for i,v in e(z):
			for x in(i>v)*r:x[(i,x[i])[x[i]<i]]=z[v]
	return sum(i==v for i,v in e(z))

```

Try it online!
> 3 votes

# Answer
# Ruby, ~~123~~ 117 bytes

Uses a similar idea to movatica's Python 3 solution but calculates the lowest spy index for each "tree" in a slightly different way (by keeping track of previous encountered profiles, finding an overlap if it exists, and combining them)

-6 bytes from @GB.

```
->a,*b{a.map{|s|e=s.split;e.map{|i|e.index i}}.transpose.map{|e|b<<(b.find{|i|i-e!=i}||[])+e}
b.map(&:min).uniq.size}

```

Try it online!

### Explanation

```
->a,*b{                                             # Start lambda with input a, b=[]
       x=
         a.map{|s|                             }    # For each agent's report
                  e=s.split;                        # Split the words
                            e.map{|i|e.index i}     # Get spy number for each

   .transpose                                       # Transpose to get group membership
             .map{|e|                            }  # For each profile
                        (b.find{|i|i-e!=i}||[])     # Find a profile in b that overlaps
                                                    #  If one is not found, use []
                                               +e   # Add the profile onto the found one
                     b<<                            # Insert this modified profile into b

b.map(&:min)                                        # Get minimum of each modded profile
            .uniq                                   # Deduplicate
                 .size                              # Size of array
}                                                   # Implicit return

```
> 3 votes

# Answer
# Husk, 12 bytes

```
LωomΣknṁoηkw

```

Try it online!

## Explanation

The idea is to create a list of all groups of spies that are known to be the same person, then progressively merge intersecting groups until a fixed point is reached. The output is the number of remaining groups that couldn't be merged.

```
LωomΣknṁoηkw  Implicit input: list of strings, say ["a bc a","b g g"]
       ṁ      Map and concatenate:
           w   Split at spaces: "a bc a" becomes ["a","bc","a"]
         ηk    Group indices by equality of elements: [[1,3],[2]]
              Result: [[1,3],[2],[1],[2,3]]
 ω            Iterate until result doesn't change:
     k         Group greedily by
      n        (non-emptiness of) intersection: [[[1,3],[1]],[[2],[2,3]]]
   mΣ          Concatenate each part: [[1,3,1],[2,2,3]]
              Result: [[1,3,1,2,2,3]]
L             Length: 1

```
> 3 votes

# Answer
# Python 2, ~~229~~ 221 bytes

```
e=enumerate
def f(s):
 v=[];u=sum([(lambda a:[{i for i,x in e(a)if x==k}for k in set(a)])(a.split())for a in s.split('\n')],v)
 while u:
	x=u.pop()
	for i,y in e(u):
	 if x&y:u.pop(i);u+=[x|y];break
	else:v+=[x]
 return v

```

Try it online!

8 bytes thx to wilkben.
> 2 votes

# Answer
# Clean, 137 bytes

```
import StdEnv,Text,Data.List
q=length
$l=q(iter(q l)(map flatten o groupBy isAnyMember)(transpose[[(s,n)\\s<-split" "z]\\z<-l&n<-[1..]]))

```

Try it online!

Associates the strings used by the agents with the line-number the appear in to prevent equality across agents, then repeatedly checks if any phrases for any position overlap and counts the number of resulting sets.
> 1 votes

# Answer
# PHP, 271 bytes

This won't work if any of the identities are just numbers as I store the "spy number" in with the identities. I don't think it wouldn't be hard to fix that though.

```
$a=$argv;array_shift($a);if(count($a)==1)array_push($a,...$a);foreach($a as&$b)$b=explode(" ",$b);$c=array_map(null,...$a);foreach($c as&$d)foreach($d as$k=>$e){if(!$d[s])$d[s]=++$s;foreach($c as&$f)if($f[$k]==$e)$f[s]=$d[s];}echo count(array_unique(array_column($c,s)));

```

Try it online!

### Explanation

Sort of confused myself writing this but it works for all the test cases!

```
$a=$argv;					//shorten the arguments variable
array_shift($a);				//removes the script name from the arguments variable
if(count($a)==1)array_push($a,...$a);		//the code needs at least 2 messages to run so if only 1 message duplicate it. "..." passes the stuff in the array rather than the array itself?
foreach($a as&$b)$b=explode(" ",$b);		//turns each string message into an array
$c=array_map(null,...$a);			//if you give array_map "null" for the callabck then it zips the arrays, turning a m by n 2D array into a n by m 2D array. this changes it from the messages being grouped to the identities being grouped
foreach($c as&$d)				//loop over the groups of identities
	foreach($d as$k=>$e)			//loop over the names the agents gave the identity and keep track of the key
	{
		if(!$d[s])$d[s]=++$s;		//if this identity doesn't have a "spy number" give it the next one
		foreach($c as&$f)		//loop over the groups of identities again
			if($f[$k]==$e)		//check if the agents gave any other identities this name
				$f[s]=$d[s];	//if they did then give those the same "spy number"
	}
echo count(array_unique(array_column($c,s)));	//use array_column to get the "spy number" of each identity, remove duplicates using array_unique and then count the size of the array giving the upper limit of spies

```

Try it online!
> 0 votes

---
Tags: code-golf
---


title: Who's that Pokémon?

text:
# Question
Title: Who's that Pokémon?
Input: an integer N between 1 and 151

Output: the Nth Pokemon.

## Rules

* You may use **one** data file.
* You may not use any already made data decompression algorithms. This includes libraries and other programs.
* Your program may not access files other than itself and your data file.

## Scoring

Your score is the sum of the length of your code and data file.

## Helpful Stuff

Here's a list of the first 151 pokemon separated by semicolons to help you generate your data file. Your output should exactly match the Nth entry of this line:

```
Bulbasaur;Ivysaur;Venusaur;Charmander;Charmeleon;Charizard;Squirtle;Wartortle;Blastoise;Caterpie;Metapod;Butterfree;Weedle;Kakuna;Beedrill;Pidgey;Pidgeotto;Pidgeot;Rattata;Raticate;Spearow;Fearow;Ekans;Arbok;Pikachu;Raichu;Sandshrew;Sandslash;Nidoran (f);Nidorina;Nidoqueen;Nidoran (m);Nidorino;Nidoking;Clefairy;Clefable;Vulpix;Ninetales;Jigglypuff;Wigglytuff;Zubat;Golbat;Oddish;Gloom;Vileplume;Paras;Parasect;Venonat;Venomoth;Diglett;Dugtrio;Meowth;Persian;Psyduck;Golduck;Mankey;Primeape;Growlith;Arcanine;Poliwag;Poliwhirl;Poliwrath;Abra;Kadabra;Alakazam;Machop;Machoke;Machamp;Bellsprout;Weepinbell;Victreebell;Tentacool;Tentacruel;Geodude;Graveler;Golem;Ponyta;Rapidash;Slowpoke;Slowbro;Magnemite;Magneton;Farfetch'd;Doduo;Dodrio;Seel;Dewgong;Grimer;Muk;Shellder;Cloyster;Gastly;Haunter;Gengar;Onix;Drowsee;Hypno;Krabby;Kingler;Voltorb;Electrode;Exeggute;Exeggutor;Cubone;Marowak;Hitmonlee;Hitmonchan;Lickitung;Koffing;Weezing;Rhyhorn;Rhydon;Chansey;Tangela;Kangaskhan;Horsea;Seadra;Goldeen;Seaking;Staryu;Starmie;Mr. Mime;Scyther;Jynx;Electabuzz;Magmar;Pinsir;Tauros;Magikarp;Gyarados;Lapras;Ditto;Eevee;Vaporeon;Jolteon;Flareon;Porygon;Omanyte;Omastar;Kabuto;Kabutops;Aerodactyl;Snorlax;Articuno;Zapdos;Moltres;Dratini;Dragonair;Dragonite;Mewtwo;Mew

```

# Answer
> 8 votes
## J (93 + 787 = 880)

Edit: other capitalisation method that capitalizes 'Mr. Mime' correctly.

Can probably be shortened, I've almost never written J before. It works on a similar principle as the PHP example.

You need the 'p' file in the same directory as you run this, the file can be downloaded from: http://frankenstein.d-n-s.org.uk/p. It is 787 bytes.

```
u:p-32*96<p*|.!.1[32=p=.(}.p#~(".1!:1[1)=+/\31=p=.#._5>\,#:a.i.1!:1<'p'){(97+i.26),a.i.'.()'' '

```

The file is encoded in a five-bit format, as follows:

```
0-25: A-Z
26: .
27: (
28: )
29: '
30: <space>
31: separator

```

The file also starts with a separator, to make the list 1-based.

The J code works as follows:

* `(97+i.26),a.i.'.()'' '`: a string where the index N is the ASCII character
* `{`: select from this list the values generated by the expression below
* `1!:1<'p'`: read the 'p' file
* `,#:a.i.`: get the file as bits
* `_5>\`: group the bits in groups of five
* `p=.#.`: transform each group of bits into a number and assign to `p`
* `+/\31=p`: a list of the size of `p` where each value N means the value at that position in `p` belongs to the N-th pokemon.
* `(".1!:1[1)=`: read a number from the keyboard and see where in `p` the characters for that pokemon are.
* `}.p#~`: look them up in `p`, and remove the first item (which is the separator).
* `p-32*96<p*_1|.(!.1)32=p=.`: Assign the output to `p` again, and subtract 32 from `p` where `p` is bigger than 96 and to the right of a space. Which is cumbersome. According to the J documentation there should be a `capitalize` function but it's not there on my system.
* `u:`: look them up as unicode.

# Answer
> 24 votes
**Bash** *1182 chars*

```
read n;echo {Bulba,Ivy,Venu}saur Char{mander,meleon,izard} {Squi,Warto}rtle Blastoise Caterpie Metapod Butterfree Weedle Kakuna Beedrill Pidge{y,otto,ot} Rat{tata,icate} {Sp,F}earow Ekans Arbok {Pika,Rai}chu Sands{hrew,lash} Nido{ran%\(f\),rina,queen,ran%\(m\),rino,king} Clefa{iry,ble} Vulpix Ninetales {Jigglyp,Wigglyt}uff {Zu,Gol}bat Oddish Gloom Vileplume Paras{,ect} Veno{nat,moth} Diglett Dugtrio Meowth Persian {Psy,Gol}duck Mankey Primeape Growlith Arcanine Poliw{ag,hirl,rath} {A,Kada}bra Alakazam Mach{op,oke,amp} Bellsprout {Weepin,Victree}bell Tentac{ool,ruel} Geodude Graveler Golem Ponyta Rapidash Slow{poke,bro} Magne{mite,ton} Farfetch\'d Dod{uo,rio} Seel Dewgong Grimer Muk {Shelld,Cloyst}er Gastly Haunter Gengar Onix Drowsee Hypno Krabby Kingler Voltorb Electrode Exeggut{e,or} Cubone Marowak Hitmon{lee,chan} Lickitung {Koff,Weez}ing Rhy{horn,don} Chansey Tangela Kangaskhan Horsea Seadra Goldeen Seaking Star{yu,mie} Mr.%Mime Scyther Jynx Electabuzz Magmar Pinsir Tauros Magikarp Gyarados Lapras Ditto Eevee {Vapore,Jolte,Flare,Poryg}on Oma{nyte,star} Kabuto{,ps} Aerodactyl Snorlax Articuno Zapdos Moltres Dra{tini,gon{air,ite}} Mew{two,}|tr %\  \ \\n|sed $n!d

```

# Answer
> 17 votes
## PHP 919 (925) bytes

As with Peter Taylor's answer, I also cannot post my solution directly, so instead i'll post a program that *generates* it:

```
<?php
$data = <<<EOD
PD9mb3IoJG89J5SWUHYPaY6dSs/pjsJBMS1pRDc1yZ3AUcQkNcnZsYIkJDXtpa4UB4mOMNH8zbDbcDhcKD
VYu89cFyjRlBm8GSjMiFSxCNHitpn8Kdi43B+XUkX2gVjN8LQEmEkF5D2zE9gbTD3z6djUJQAVFXwlXV/o
kVwnsV1rW5J9zpssN3JXdW5LjAS3DYTcBtV/YUdtoAfGC+ztsoc1LxQamD5lmQMaes37flJcGvg7CdkS+s
1bhZLjAQQtmL5tS3rN+2eS7LeROnX9nOCRRWhRQhFkBDSN0igwMUwem4BNYVrkxZuAzUEiRDG+KFODVqV0
KDAvpLM747wC0AwYUVkELsVsBA5vyThUQQtiKFRBK6EYnBC7oMiAkJtYbXOZk9scdPF3hTJEh7hhZ4yDEG
FHzJ1vSfxkDVkd8fz+u6ConHVH7Y3SHFtgq20M22ALpO40xMC9vmictX6lf+2VfqV1EBctRRwZ38RceT3E
G2l5PcTVTFahWEdGGYhjKSwy5lBYAn944VmhWNQRkvXDw5SAkpV/URm0SZPBOPweZUGwDlODERHEwt0VfK
X9WG+kp9tbe+d8oLvu1uw9+6ExyFwZe6LogoTF7oG3RCiUm0GTcJsmcyxJmdRR68Oi7P4NmQ6ZlwxE8djR
DtfANTjRZBOvWE281RLRDtPJY05E4k10BkvfCRwNLKssXh4GHB+SgBFEwsDbHsSxMdhmCBExsfvZKLzEEY
uZ26SXfutBOR1rezc8/XmT6HkcHciTBwTSxD1cJ+XBcmyjis2S7ClZLZJMTG2bngTs7VtCN3VSaQUAcuPQ
VR9yY0+ntSTcnhcdZ4n4JtzDwPHZJEl9pZJsONV96ad1jpV5eVhpldF8r7WcMeRd8hSxMXjVEcZEPZsdLg
SSd+4kNY7L7Bkbdy10VDVuJdtfGOyG7yydwJux2SFcAiz7QSIEa8BxAoQIFUFCRJt+G6KkoZ3d8fzBPZhO
xG2eaIwfvrGb54zZ7mgfGPA0Qp6I5NSund9SSw5MUD8M0wAmzywmSF2N/CZbw8V1JEZF42LIXJmLeIM5uU
wnOzc4OD4kbjspJGY9c3BsaXQonywkeC49Y2hyKDMxJiR2PSsrJGklOCUzPzgqJHZeb3JkKCRvWyRuKytd
KTokdj4+NSleiyk7ZWNob35zdHJ0cigkZlsrZmdldHMoU1RESU4pXXygLICEgYOCLNfY1tHfKTsNCg==
EOD;
print base64_decode($data);
?>

```

Sample I/O:

```
$ php generator.php > out.php

$ echo 12 | php out.php
Butterfree

$ echo 32 | php out.php
Nidoran (m)

$ echo 83 | php out.php
Farfetch'd

$ echo 122 | php out.php
Mr. mime

$ echo 151 | php out.php
Mew

```

How it works (spoiler):

> This code operates on the observation that there are only 32 unique characters, including a separator - if you're not counting capitals. This immediately implies a 5:8 encoding; only 5 bits are needed to represent each byte.
> I accomplish this in the following manner:
> ++$i%8%3
> When this value is non-zero, a new byte is read, and when zero, the next byte is generated from the previously read bytes. The 3rd, 6th, and 8th byte are generated in this manner, and then the process repeats.
> The bit distribution follows accordingly. If for example you wanted to produce the string:
> abcdefgh
> The bits for each are distributed among the 5 source bytes in the following fashion:
> hccaaaaa|cccbbbbb|hffddddd|fffeeeee|hhhggggg
> After generating c, only the top most bit of h remains, after generating f, the top two bits of h remain, and after reading g, h remains in its entirety (I save a few shift operations by using xored values instead, for example the value I load for the second byte is the value I want xor a\<\<3, but that's the gist of it).
> This produces characters on the range of \[0,31\]. By xoring by any character on the range \[96,127\], all characters will be mapped to that range (I chose 116, because it resulted in the least amount of escape sequences). After that, it's a simple matter of translating the 5 characters that don't belong there with their appropriate replacements, and capitalizing the first letter. This code requires three bytes to do so: oring the (previously generated as such) bit inverted string with char 160, and then bit inverting back. A small caveat: the second m in 'Mr. mime' is not capitalized by this method. This could be repaired by replacing the method described above with the ucwords() function, at the cost of 6 bytes, resulting in a code length of 925, instead of 919.

# Answer
> 7 votes
## GolfScript (1040 bytes)

Unfortunately I can't directly post the program, so I'll provide a link and the base64-encoded text:

```
fignACc1Nix7XFsxJF0nJysvXCdCdWxiNzYKSXZ5czY0dXM2CjJtMWQvMm0tZSsyaXozZCpxdSZ0
bCVXMyRydGwlQmw3JGlzJUMjMHBpImUhcB8KQnV0dDBmcmUlHmRsJUtha3VuYQpCZWVkHWxsG3kb
b3QkG290GiN0I2EaI2ljIyVTcGUzGQpGZTMZCkVrMXMYcmJvaxxpa2EXdRphaRd1KjFkc2hyZXcq
MWRzbDdoFWYpFnIUYRZxdWU1FW0pFnIUbxZrExEmeRFibCVWdWxwaXgKThRlIRJzCkoQcHVmZgpX
EHR1ZmYKWnViIw8OYiMKT2RkaXNoD2xvb20KVmkScGx1bSVQMzccMzdlY3Q0LCM0b21vdGgNaWcS
dHQNdWd0HW8MZRl0aBwwc2kxHHN5ZHVjaw8OZHVjawwxa2V5HB1tZQslR3IZbAloGHJjMRQlUAhh
ZxwIaCZsHAgHdGgYYgcGYWRhYgcYbGFrYXphbQUXb3AFF29rImEXYW1wCkItbHNwcm91dAoecBRi
LWwKVmljdHJlZWItbARvDgRydS0PZR91ZCVHB3YtL0cOZW0cLHkhGgtpZDdoKmwZcG9rJVNsGWJy
bwVnbmVtCSJhZ25ldCtGM2ZldBdcJ2QNH3VvDR8dbyplLQ1ld2csZw8dbS9NdWsqaC1sZC9DbG95
c3QvRzd0bHkKSGF1bnQvRzVnMwpPbml4DXIZc2UlSHlwbm8GB2JieQYTbC9WDiRyYgpFEmN0ch8D
dAMkcgpDdWIsIjMZYWsKSAltLBIlSAltLBcxCkxpY2sJdW5nBm9mZhMKHnoTGmh5aAJuGmh5ZCtD
aDFzZXkKVDFnLWEGMWc3a2gxCkgCc2VhKmVhZAcPDmRlNSplYWsTKnQzeXUqdDNtaSJyLiBNaW0l
U2N5dGgvSnlueApFEmMhYnV6egVnbTMcFHMmClQ2b3MFZ2lrM3APeTNhZG9zCkwLB3MNCSQKRWV2
ZSVWCwJlK0oOdGUrRmwzZSwcAnlnK09tMXl0JU9tN3QzAQFwcxgwH2FjdHlsKm4CbGF4GHJ0aWN1
bm8KWgtkb3MMDnRyZXMNB3QUaQ0HZyxhJg0HZywJImV3dHdvDGV3AAZhYnUkAG9yACVFeGVnZ3UA
ClQ1IWMADGEACksAcmEADml3AGl0AAoAYXAACk0ACkQAb2wACkcAaWdnbHkACkMSZmEAbGUAFGcA
aW4AFnIxICgACk5pZG8AY2gACkEAb3cAClIAHGlkZ2UAClAAcmkAV2VlAG9kACAAdGEAJU0AYXQA
dG8AZQoAaXIAXCcAKAApAApTACwKAG9uAGVsAC4AMAoAZXIAYW4AQ2gzAGFyAApWNQBlbgBhdXIA
YXMnJwAnLz0qfS9uLz0=

```

It uses a grammar-based approach with rules separated by NUL characters and a simple expansion approach, followed by splitting on newlines and selecting the desired line. Input is via stdin. No external file is used.

### In more detail

I have written a Java program which applies several grammar-generating strategies and two grammar-to-GolfScript generation strategies and outputs a lot of GS programs to reconstruct a string. In this particular case the winning combination was a greedy grammar builder with a threshold of 2, and the remap engine. The greedy grammar builder starts with a grammar

```
<0> ::= "Bulbasaur\nIvysaur\nVenusaur\n..."

```

and repeatedly looks for the repeated sequence of terminals and non-terminals in the right hand sides which, when pulled out into a rule defining a new non-terminal, produces the greatest decrease in the total number of terminals and non-terminals in the grammar. The threshold is the cutoff point at which the decrease is considered no longer worth it.

The non-terminals are topologically sorted and then numbered from 0 up. If they overlap any character values which are also terminals, the remap engine creates a new rule mapping to that terminal. (E.g. if there are rules 0 to 37 and the space character occurs, it will map 38 to the space character and then update the RHS of all rules to use 38 instead of 32). The right hand sides of the rules are then concatenated, separated by NULs, and a small piece of hand-written GolfScript to expand the grammar is appended.

# Answer
> 3 votes
# brainfuck, 9337 bytes

Pretty sure I will find a shorter solution ^^

```
--->->>>>->>->>>-->->>>>->>>-->->>>>>->>>-->->>->>>->>>>>-->->>->>>>>>>>-->->>->>>>->>>-->->>>>>>>>-->->->>>>>>>>-->->>->>>>>>>-->->->>>>>>>-->->>>->>>>-->->>>>>>>>>>-->->>>>>>-->->->>>>->-->->>>>>>>>-->->>>>>>-->->>>>>>>>>-->->>>>>>>-->->->>>->>->-->->->>>>->>>-->->>>->>>>-->->>->>>>-->->>->>>-->->>>>>-->->>>->>>>-->->->>>>>-->->->>>>>>>>-->->->>>>>->>>-->->>>>>->>-->-->>-->-->->>>>>>>->-->->>>>>>>>>-->->>>>>->>-->-->>-->-->->>>>>>>>-->->>>>>>>>-->->>>>->>>>-->->>>>->>>>-->->>>>>>-->->>>>>->>>>-->->>>>>>>>>>-->->>>>>>>>>>-->->>>->>-->->>>>->>-->->>>>>>-->->>>>>-->->>>>>>>>>-->->->>->>-->->->>->>>>>-->->>>>>->>-->->>>>>>>>-->->>>>>>>-->->>>>>>>-->->>>>>>-->->>>>>->>-->->>>>>>>-->->>>>>>>-->->->>>>>-->->>>>>->>>-->->>>>>>>>-->->>>->>>>>-->->>>>>->>-->->>>>>>>>>-->->>>>>>->>>-->->>>->-->->->>->>>->-->->>->>->>->>-->->->>>>>-->->->>>>>>-->->->>>->>>-->->>>>>>>>>>-->->>>>>>>>>>-->->>>>>>>>>>>-->->>>>->>>>>-->->>>>->>>>>>-->->>>>>>>-->->>->>>>>>-->->>>>>-->->>>>>->-->->->>>>->>>-->->>>>>>>>-->->>>>>>>-->->->>>>>>>>-->->->>>>>>>-->->->>>>>>>-->>-->->>>>>-->->>>>>>-->->>>>-->->>>>>>>-->->>>>>>-->->>>-->->>>>>>>>-->->>>>>>>>-->->->>>>>-->->->>>>>>-->->>>>->>-->->>>>-->->>>>>>>-->->>>>>-->->>->>>>-->->>>>>>>-->->>>>>>>-->->>>>>>>>>-->->>>>>>>>-->->>>>>>>>>-->->>>>>>-->->->>>>->>-->->>>>>>>>>-->->>>>>>>>->>-->->>>>>>>>>-->->>>>>>>-->->>>>>>>-->->>>>>>>-->->>>>>>-->->>->>>>>-->->->>>>>->-->->->>>->>>>->>-->->>>>>->-->->>->>>->-->->>>>>>>-->->>->>>>>-->->>->>>>-->->>->>>>>-->->>-->-->->>>>-->->>>>>>>-->->>>>-->->>>>>->>>>>-->->->>>->>-->->>>>>>-->->->>>>>-->->->>>>->>>-->->>->>->>>>-->->->>>->>-->->>>>>-->->>>>>-->->->>>>>>>-->->>>>>>>-->->>->>>>>-->->>>>>>>-->->>->>>>>-->->>->>>->>-->->->>>>>-->->->>>>>>>-->->>>>>->>>>>-->->>>>>->>-->->>>>>>>>-->->->>>>>-->->>>>>>>-->->>->>>>>-->->>->>>>->>>-->->>->>>>>>>-->->>>>>>-->->>>+[-[>+++++++<-]<+++]>---->->->-->--->+++>->+++>->->--->>->>->+++>->->--->++>--->-->->->+++>->->--->->--->+++>->-->+++>-->--->--->->--->->--->+++>->-->--->-->--->-->-->--->->--->+++>->-->>+++>->--->--->+>->->-->->->-->--->--->++>+++>->->-->->->-->--->--->->-->+++>->->-->-->->--->--->->+++>->--->->->-->--->--->+>--->->+++>->-->--->--->->->->->--->->--->->--->--->--->++>--->--->--->-->--->--->>+++>-->->-->+++>--->->--->--->--->->-->-->-->--->+>-->--->--->--->>--->+>-->--->--->--->-->->->-->--->+>-->--->--->--->-->->--->+>+++>->->+++>->+++>--->+>+++>->-->--->+++>->--->--->+>->--->+++>->-->>--->>--->+++>->-->>--->->-->+++>-->->--->->->--->-->-->--->+>-->-->+++>--->--->->--->+>+++>-->--->--->->--->+>+++>-->--->->--->->--->>--->+>+++>-->--->->-->+++>->--->--->+>-->--->-->->+++>-->+>++>--->++>--->+>-->--->-->->-->-->+++>--->+>-->--->-->->->--->--->-->--->+>-->--->-->->+++>-->+>++>-->++>--->+>-->--->-->->-->-->-->--->+>-->--->-->-->-->-->--->--->->-->--->--->+++>-->->>--->->-->--->--->+++>--->-->--->--->++>->-->->-->>--->+>-->-->--->->+++>-->--->->--->>-->--->--->-->>->->--->--->--->++>-->--->--->-->>->->--->--->--->++>->--->+++>->--->>-->-->--->+++>->--->+>--->--->-->->--->--->>-->-->-->-->--->++>-->-->--->->-->->-->--->--->+>+++>->+++>->--->+>+++>->+++>->--->--->->--->++>--->-->-->-->+++>->--->++>--->-->-->-->-->->--->--->->-->--->-->--->->->--->->->--->->->-->-->--->+>--->-->>->--->--->+>--->->->-->+++>-->--->+>->>--->->--->-->--->>-->-->--->->--->-->--->+>+++>-->-->--->>--->+>->-->-->--->+++>->--->--->>->-->>-->-->->--->--->->->--->+++>-->-->-->--->--->+>-->-->-->>+++>--->--->+>-->-->-->>--->-->->-->--->+>-->-->-->>->+++>->--->--->->--->->+++>--->>+++>--->+++>--->->+++>--->->-->+++>-->+++>>+++>-->--->+>+++>--->--->-->->--->+>+++>--->--->-->-->--->--->+>+++>--->--->+++>-->->--->->--->-->-->->->->-->->->--->++>--->--->->-->-->--->--->-->-->--->++>-->--->->->--->--->--->--->-->-->--->++>--->-->->+++>--->-->-->-->--->++>--->-->->+++>--->->->--->-->--->>--->-->--->->--->--->--->>->+++>->--->-->--->->--->>-->-->--->-->--->+>-->-->>->+++>--->+>+++>->-->--->+++>->--->--->+>-->-->>->-->-->--->--->+>-->-->>--->->-->--->+>+++>--->-->--->-->-->->--->--->+>+++>--->-->--->->-->-->--->>+++>->--->--->->--->--->++>--->--->->-->--->->-->--->->-->--->->-->-->--->+>--->--->-->--->->--->>--->-->-->--->--->>->-->-->--->->--->+>->-->--->+>--->--->-->-->--->--->->--->->-->-->>->->--->->--->>+++>->->-->>--->>+++>->-->->--->->--->>--->-->--->+++>->--->+>-->-->>--->->->-->>->--->--->--->>>->-->-->--->>->+++>--->--->>--->>-->-->--->-->--->->--->++>-->-->->-->->--->--->->-->--->--->->->-->--->--->--->->>--->--->--->->->--->--->->>--->--->--->->->-->->--->->->--->-->-->--->--->+>+++>->-->>+++>-->--->>-->->-->-->-->-->--->--->--->>-->->-->-->-->--->--->+++>-->--->>-->--->-->-->->->-->--->--->>-->--->--->-->-->--->--->++>--->--->>-->-->--->--->+>--->>--->-->->-->--->+>--->>--->-->-->--->->--->+++>-->->--->>--->++>+++>-->--->--->-->+++>--->>+++>-->--->+++>->-->--->+++>-->--->>-->->->--->+++>--->+>--->+++>--->->+++>--->>-->-->--->--->--->-->--->+>--->+++>-->-->-->--->--->+>->+++>->>->--->+>->+++>->-->-->--->--->+>->+++>+>+>-->-->--->--->+>--->>->--->--->->--->>>-->>--->->-->--->--->->+++>--->->>>--->+>+++>--->-->+++>->--->+>-->-->->-->->--->++>+++>->->-->->--->+>+++>--->-->-->+++>->->--->>>+++>->+++>--->-->->--->>+++>->->+++>->--->->-->->->-->--->->--->->--->--->--->++>+++>->-->->--->-->-->--->>-->-->->--->-->-->--->>-->+++>->--->-->-->--->+>-->->>--->-->-->--->+>-->+++>-->>->--->--->+>-->+++>->->+++>->--->>+++>--->->->-->--->>+++>--->->->-->->->--->->--->->-->--->+++>--->->>-->--->+>-->-->->-->+++>>--->->->->-->--->->-->-->--->++>+++>->--->-->->--->+>-->-->->->--->->--->->->+++>->-->-->-->--->->->+++>--->-->-->+++>-->->--->->->+++>--->-->-->-->->--->--->+>--->>->>-->--->+>--->>+[-[>+++++++<-]<++++]>---->>++>>--->+++>>+++>++>->--->>+++>->>+++>++>->--->->>++>++>>+++>++>->--->+>+++>+++>->+>+++>++>->>->--->+>+++>+++>->+>>>>+++>++>--->+>+++>+++>->--->>+++>->->--->+++>-->++>--->->+>>>--->>+++>->+>+++>->+>>>--->>>+++>>+>+++>--->>>--->+>+++>+>>->--->--->>--->--->>+>+++>--->+++>->--->>++>+>+>>->+>->>>--->>>>->>>--->++>+++>->++>++>+++>--->>>>->->--->>>--->>--->->++>>->--->>--->->++>>+++>+>+>+++>--->>--->->++>>+++>+>--->++>+++>+>+>+++>+>+++>--->++>+++>+>--->-->+++>+>>--->+++>--->>+++>->+++>--->--->--->>+++>->+++>--->--->+++>->+++>++>>--->->->--->+++>->--->>--->->+++>-->+++>++>--->++>+++>--->-->+++>++>--->+++>+++>++>->>+++>->>--->--->+++>+++>++>->>>+++>>+++>--->-->--->->+++>->+++>++>+>++>+>+++>--->-->--->->+++>->--->++>+++>--->-->--->->+++>-->++>>>++>--->-->--->->+++>->+++>++>+>++>+>+++>--->-->--->->+++>->--->++>+++>--->-->--->->+++>->--->++>++>--->+>>>+>+++>--->->->--->+>>>+>+++>--->>>--->->++>>--->--->-->--->-->--->++>>+>+++>>>>--->+>--->++>++>>->--->++>+>+>--->>--->++>++>>->+>++>+>+>--->+++>++>--->+++>+>--->-->+++>>--->+++>+>--->->->->--->>+++>--->-->>+++>+++>+>--->->--->>>--->>++>+>>--->>+++>->+++>>--->>+++>->+++>>>-->+>--->->>++>+++>++>+++>+>--->->>++>+++>+>+++>+>+++>--->++>--->++>>>+>+>--->++>++>++>+>->--->+++>--->--->>+++>--->+>+++>--->>>->>--->+++>++>--->>>->->++>-->->--->-->+++>>->++>-->->--->--->+++>++>->>->--->>->--->+>>+++>--->>--->-->->+++>--->>--->+>+++>--->->->-->+++>++>--->++>>--->>+++>>--->--->+++>++>--->>+++>>--->--->+++>--->->>--->>+++>>--->--->->+++>+>+++>--->->--->->+++>--->++>+++>->+++>--->->+++>--->->>+++>->+++>>+++>+>--->--->+++>-->+++>+++>--->--->--->+++>-->+++>+++>->>--->--->+++>-->+++>+++>+>--->--->>>>>>--->->+++>++>+>--->>>>--->--->++>--->>>>--->->--->-->+>->>>--->>>>--->--->>++>+>+++>-->+++>+++>>--->--->>++>+>+++>-->->++>>>--->-->>+++>->++>->>--->-->->+++>+++>>>>->--->-->+++>>>+>--->>+++>++>->+>+++>--->++>+++>--->--->->+++>>+++>--->+++>>+++>--->--->+++>->>--->+++>>+++>--->--->->+++>--->--->+++>++>++>>+>--->+>>--->--->+++>++>++>>+>+++>++>--->--->+++>->+>>+>-->+++>+>->--->++>+++>->++>+++>--->++>+++>->->--->+++>--->+++>>>>--->++>>--->++>+++>++>++>--->-->->--->+>>->--->--->++>->--->+++>+++>>>>->>->--->+>>+++>->>+>>->--->-->+++>>+>>->--->->+++>++>++>+>>->--->-->>++>++>+++>->--->->++>--->-->--->++>->+++>--->>>>--->->->--->++>+++>--->++>->+++>--->--->->--->++>--->++>++>>>->--->->+++>>+>+++>->--->--->+++>>>-->+>->+++>->>--->+++>-->>++>++>++>+>>--->+++>-->>++>++>++>+>+++>->--->+>++>--->+++>++>>--->--->+++>->+++>--->+++>->--->->--->+>+>+++>++>>>>--->->--->+>+>+++>++>-->+++>+++>++>--->+++>--->-->->--->+>++>++>++>--->++>+++>+>+>--->++>++>--->>>>>--->++>++>--->++>+++>->+++>+++>->++>--->++>+++>->->+++>++>--->+>+++>+++>++>>>->--->--->+++>++>++>>>+++>--->++>+++>++>++>+++>>->+++>+++>++>--->->+++>->>>+++>--->+++>>+++>->->+++>--->-->+++>>->>>++>--->+++>>+++>->--->++>++>--->+++>+>+++>->->++>--->+++>+>+++>->+>--->>--->--->->+>+>--->--->+>>--->+++>-->->+>+++>>->--->+>->++>-->--->+++>>>-->+>+++>--->++>>>--->--->+++>++>+>+++>->--->>--->++>>--->->--->--->+++>++>->+++>>--->--->+++>++>--->->+++>->--->--->-->->+++>->+++>->+++>>--->+++>+++>--->->+++>>--->++>--->+>+>+++>--->+++>>+++>>>--->->+++>--->+++>->>+++>++>--->+>+++>>+>>+++>++>--->--->>+++>->>+++>++>--->>+++>->->++>+++>++>--->->+>+++>++>->+>>--->->+>+++>>+>+++>->--->++>+++>--->++>+>+++>--->++>+++>--->++>+>+++>--->>--->->>->+++>->+++>-->+>->>--->+++>++>+++>->>+++>-->--->->->+>--->-->++>++>+++>--->+++>+++>--->->+++>>--->--->+++>>+>->>>--->++>->+++>+>--->++>--->--->++>->+++>++>+++>++>+++>--->->--->++>->+++>++>+++>++>--->+>>--->--->>--->+>--->+++>--->--->>--->+[-<++++]<<<,[>[>+<-]>[<++++++++++>-]<<<++++++++[>------<-]>[>+<-],]>-[>>[>]+[<]<-]>>[>]>[.>]

```

Try it online!

# Answer
> 2 votes
# q/kdb, 789+77 = 866 bytes

**Solution:**

```
/ encoding pokemon.txt into 'q' text file (not added to byte count, not golfed)
`:q 0:enlist "c"$2 sv'8 cut (raze 3_'0b vs'4h$(asc distinct p)?p:lower first read0`:pokemon.txt),000000b

/ checking length of q file (note: file is written with trailing newline \r\n, so could/should be 787 bytes)
hcount `:q
789

/ decoding q and look-up of value
@[;0;upper](";"vs(" '().;",.Q.a)2 sv'5 cut -6_(,/)0b vs'4h$"\n"sv(0:)`:q)@-1+

```

**Examples:**

```
q)@[;0;upper](";"vs(" '().;",.Q.a)2 sv'5 cut -6_(,/)0b vs'4h$"\n"sv(0:)`:q)@-1+45
"Vileplume"
q)@[;0;upper](";"vs(" '().;",.Q.a)2 sv'5 cut -6_(,/)0b vs'4h$"\n"sv(0:)`:q)@-1+151
"Mew"
q)@[;0;upper](";"vs(" '().;",.Q.a)2 sv'5 cut -6_(,/)0b vs'4h$"\n"sv(0:)`:q)@-1+1
"Bulbasaur"

```

**Explanation:**

The strategy (like other solutions) is to encode each 8 bit character in 5 bits, this is done by creating a smaller alphabet of 32 characters, finding the indices of each letter in the input list (0..31) and then encoding these as 5-bit numbers (which need to be joined and converted to 8-bit chars to be written down in Q).

The decoding is just doing the opposite of this, the alphabet is known to be `" '().;abcdefghijklmnopqrstuvwxyz"`, so split the input into batches of 5 bits and convert back into integers, index into the alphabet. Split this on `;` and then index into it with user input (subtract 1 due to 0-indexing), and (re)capitalise the first letter.

```
@[;0;upper] (";" vs " '().;abcdefghijklmnopqrstuvwxyz"2 sv'5 cut -6_raze 0b vs'4h$ "\n" sv read0 `:q)@-1+ / ungolfed decoder
                                                                                -1+ / same as doing 'x-1', subtract 1 from input
                                                                                @    / index in to item on the left
            (                                                                                )     / do all this together
                                                                                read0 `:q      / read text file 'q'
                                                                                "\n" sv                / join back newlines (as q breaks text files on newlines)
                                                                               4h$                        / cast char array to bytes
                                                                         0b vs'                           / convert each byte to binary (boolean list)
                                                                    raze                                  / flatten list
                                                                 -6_                                      / drop the 6 padding bits added to align 5/8-bits
                                                           5 cut                                          / chop into lists of 5-bit lengths
                                                      2 sv'                                               / convert each boolean list back to an integer
                    " '().;abcdefghijklmnopqrstuvwxyz"                                                    / index into our lookup table at each index
             ";" vs                                                                                / break this string up at semicolons
 @[;0;upper]                                                                                / apply 'upper' to each first character in the result

```

**Notes:**

An extra 13 bytes (879) if we need to capitalise the second `M` of `Mr. Mime`:

```
{@[x;0,1+x ss" ";upper]}(";"vs(" '().;",.Q.a)2 sv'5 cut -6_(,/)0b vs'4h$"\n"sv(0:)`:q)@-1+

```

# Answer
> 2 votes
# Pure Bash (no coreutils), 1173 bytes

```
read n;set {Bulba,Ivy,Venu}saur Char{mander,meleon,izard} {Squi,Warto}rtle Blastoise Caterpie Metapod Butterfree Weedle Kakuna Beedrill Pidge{y,otto,ot} Rat{tata,icate} {Sp,F}earow Ekans Arbok {Pika,Rai}chu Sands{hrew,lash} Nido{ran\ \(f\),rina,queen,ran\ \(m\),rino,king} Clefa{iry,ble} Vulpix Ninetales {Jigglyp,Wigglyt}uff {Zu,Gol}bat Oddish Gloom Vileplume Paras{,ect} Veno{nat,moth} Diglett Dugtrio Meowth Persian {Psy,Gol}duck Mankey Primeape Growlith Arcanine Poliw{ag,hirl,rath} {A,Kada}bra Alakazam Mach{op,oke,amp} Bellsprout {Weepin,Victree}bell Tentac{ool,ruel} Geodude Graveler Golem Ponyta Rapidash Slow{poke,bro} Magne{mite,ton} Farfetch\'d Dod{uo,rio} Seel Dewgong Grimer Muk {Shelld,Cloyst}er Gastly Haunter Gengar Onix Drowsee Hypno Krabby Kingler Voltorb Electrode Exeggut{e,or} Cubone Marowak Hitmon{lee,chan} Lickitung {Koff,Weez}ing Rhy{horn,don} Chansey Tangela Kangaskhan Horsea Seadra Goldeen Seaking Star{yu,mie} Mr.\ Mime Scyther Jynx Electabuzz Magmar Pinsir Tauros Magikarp Gyarados Lapras Ditto Eevee {Vapore,Jolte,Flare,Poryg}on Oma{nyte,star} Kabuto{,ps} Aerodactyl Snorlax Articuno Zapdos Moltres Dra{tini,gon{air,ite}} Mew{two,};echo ${!n}

```

Try it online!

Uses brace expansion like this answer, but uses only bash builtins `read`, `set`, and `echo`. `set` sets the command line arguments to those given, so that, for instance, `$1` is `Bulbasaur`. `${!n}` is an indirect expansion, which expands into the variable of the variable with the name of `$n`.

# Answer
> 2 votes
# Python 3, 178+1253=1431 bytes

```
import re
def f(l,N,p='',n=0,w=''):
 for s in open(l,'r',1,'utf-8').read().split('\0'):t=re.match('\d*',s)[0];n=int(t or n);w=w[:n]+s[len(t):];p+=w[:-1]*(ord(w[-1])==N)
 return p

```

<sub>Credit to wizzwizz4 for their Bookworm decompression function: Parse the Bookworm dictionary format</sub>

Must pass the filename and the desired Pokemon number to the function. Returns a string containing the Pokemon.

Ex.: `f('pokemans', 1')` returns 'Bulbasaur'.

The file uses BookWorm compression, but since the Pokemon must be in alphabetical order for this to work, they all end with a character whose ordinal matches their number (Ex. Nidorino appears as "7o!", "7o" being the compressed string "Nidorino" and "!" being \33). Items are delineated by the null byte \0, since Pokemon chars start at \1.

Due to the complexity of decompressing BookWorm, this is actually worse than taking the basic hard-coded list, then splitting and indexing it. But it's a novel answer, so I thought I'd post it anyway.

**Hex dump of 'pokemans' file:**

> 41 62 72 61 3f 00 31 65 72 6f 64 61 63 74 79 6c c2 8e 00 6c 61 6b 61 7a 61 6d 41 00 72 62 6f 6b 18 00 32 63 61 6e 69 6e 65 3b 00 74 69 63 75 6e 6f c2 90 00 30 42 65 65 64 72 69 6c 6c 0f 00 32 6c 6c 73 70 72 6f 75 74 45 00 31 6c 61 73 74 6f 69 73 65 09 00 75 6c 62 61 73 61 75 72 01 00 32 74 74 65 72 66 72 65 65 0c 00 30 43 61 74 65 72 70 69 65 0a 00 31 68 61 6e 73 65 79 71 00 33 72 69 7a 61 72 64 06 00 34 6d 61 6e 64 65 72 04 00 35 65 6c 65 6f 6e 05 00 31 6c 65 66 61 62 6c 65 24 00 35 69 72 79 23 00 32 6f 79 73 74 65 72 5b 00 31 75 62 6f 6e 65 68 00 30 44 65 77 67 6f 6e 67 57 00 44 69 67 6c 65 74 74 32 00 32 74 74 6f c2 84 00 30 44 6f 64 72 69 6f 55 00 33 75 6f 54 00 31 72 61 67 6f 6e 61 69 72 c2 94 00 36 69 74 65 c2 95 00 33 74 69 6e 69 c2 93 00 32 6f 77 73 65 65 60 00 31 75 67 74 72 69 6f 33 00 30 45 65 76 65 65 c2 85 00 31 6b 61 6e 73 17 00 6c 65 63 74 61 62 75 7a 7a 7d 00 35 72 6f 64 65 65 00 31 78 65 67 67 75 74 65 66 00 37 6f 72 67 00 30 46 61 72 66 65 74 63 68 27 64 53 00 31 65 61 72 6f 77 16 00 6c 61 72 65 6f 6e c2 88 00 30 47 61 73 74 6c 79 5c 00 31 65 6e 67 61 72 5e 00 32 6f 64 75 64 65 4a 00 31 6c 6f 6f 6d 2c 00 6f 6c 62 61 74 2a 00 33 64 65 65 6e 76 00 34 75 63 6b 37 00 33 65 6d 4c 00 31 72 61 76 65 6c 65 72 4b 00 32 69 6d 65 72 58 00 32 6f 77 6c 69 74 68 3a 00 31 79 61 72 61 64 6f 73 c2 82 00 30 48 61 75 6e 74 65 72 5d 00 31 69 74 6d 6f 6e 63 68 61 6e 6b 00 36 6c 65 65 6a 00 31 6f 72 73 65 61 74 00 79 70 6e 6f 61 00 30 49 76 79 73 61 75 72 02 00 4a 69 67 67 6c 79 70 75 66 66 27 00 31 6f 6c 74 65 6f 6e c2 87 00 79 6e 78 7c 00 30 4b 61 62 75 74 6f c2 8c 00 36 70 73 c2 8d 00 32 64 61 62 72 61 40 00 32 6b 75 6e 61 0e 00 32 6e 67 61 73 6b 68 61 6e 73 00 31 69 6e 67 6c 65 72 63 00 6f 66 66 69 6e 67 6d 00 72 61 62 62 79 62 00 30 4c 61 70 72 61 73 c2 83 00 4c 69 63 6b 69 74 75 6e 67 6c 00 4d 61 63 68 61 6d 70 44 00 34 6f 6b 65 43 00 35 70 42 00 32 67 69 6b 61 72 70 c2 81 00 33 6d 61 72 7e 00 6e 65 6d 69 74 65 51 00 35 74 6f 6e 52 00 32 6e 6b 65 79 38 00 72 6f 77 61 6b 69 00 31 65 6f 77 74 68 34 00 32 74 61 70 6f 64 0b 00 77 c2 97 00 33 74 77 6f c2 96 00 31 6f 6c 74 72 65 73 c2 92 00 72 2e 20 4d 69 6d 65 7a 00 75 6b 59 00 30 4e 69 64 6f 6b 69 6e 67 22 00 34 71 75 65 65 6e 1f 00 72 61 6e 20 28 66 29 1d 00 39 6d 29 20 00 35 69 6e 61 1e 00 37 6f 21 00 32 6e 65 74 61 6c 65 73 26 00 30 4f 64 64 69 73 68 2b 00 31 6d 61 6e 79 74 65 c2 8a 00 33 73 74 61 72 c2 8b 00 31 6e 69 78 5f 00 30 50 61 72 61 73 2e 00 35 65 63 74 2f 00 31 65 72 73 69 61 6e 35 00 69 64 67 65 6f 74 12 00 35 6f 74 74 6f 11 00 79 10 00 32 6b 61 63 68 75 19 00 6e 73 69 72 7f 00 31 6f 6c 69 77 61 67 3c 00 35 68 69 72 6c 3d 00 72 61 74 68 3e 00 32 6e 79 74 61 4d 00 72 79 67 6f 6e c2 89 00 31 72 69 6d 65 61 70 65 39 00 73 79 64 75 63 6b 36 00 30 52 61 69 63 68 75 1a 00 32 70 69 64 61 73 68 4e 00 74 69 63 61 74 65 14 00 33 74 61 74 61 13 00 31 68 79 64 6f 6e 70 00 33 68 6f 72 6e 6f 00 30 53 61 6e 64 73 68 72 65 77 1b 00 35 6c 61 73 68 1c 00 31 63 79 74 68 65 72 7b 00 65 61 64 72 61 75 00 33 6b 69 6e 67 77 00 32 65 6c 56 00 31 68 65 6c 6c 64 65 72 5a 00 6c 6f 77 62 72 6f 50 00 34 70 6f 6b 65 4f 00 31 6e 6f 72 6c 61 78 c2 8f 00 70 65 61 72 6f 77 15 00 71 75 69 72 74 6c 65 07 00 74 61 72 6d 69 65 79 00 34 79 75 78 00 30 54 61 6e 67 65 6c 61 72 00 32 75 72 6f 73 c2 80 00 31 65 6e 74 61 63 6f 6f 6c 48 00 36 72 75 65 6c 49 00 30 56 61 70 6f 72 65 6f 6e c2 86 00 31 65 6e 6f 6d 6f 74 68 31 00 34 6e 61 74 30 00 33 75 73 61 75 72 03 00 31 69 63 74 72 65 65 62 65 6c 6c 47 00 32 6c 65 70 6c 75 6d 65 2d 00 31 6f 6c 74 6f 72 62 64 00 75 6c 70 69 78 25 00 30 57 61 72 74 6f 72 74 6c 65 08 00 31 65 65 64 6c 65 0d 00 33 70 69 6e 62 65 6c 6c 46 00 7a 69 6e 67 6e 00 31 69 67 67 6c 79 74 75 66 66 28 00 30 5a 61 70 64 6f 73 c2 91 00 31 75 62 61 74 29 00

# Answer
> 0 votes
# JavaScript, ~~1277~~ 1276 bytes

```
n=>";Bulbasaur;Ivysaur;Venusaur;Charmander;Charmeleon;Charizard;Squirtle;Wartortle;Blastoise;Caterpie;Metapod;Butterfree;Weedle;Kakuna;Beedrill;Pidgey;Pidgeotto;Pidgeot;Rattata;Raticate;Spearow;Fearow;Ekans;Arbok;Pikachu;Raichu;Sandshrew;Sandslash;Nidoran (f);Nidorina;Nidoqueen;Nidoran (m);Nidorino;Nidoking;Clefairy;Clefable;Vulpix;Ninetales;Jigglypuff;Wigglytuff;Zubat;Golbat;Oddish;Gloom;Vileplume;Paras;Parasect;Venonat;Venomoth;Diglett;Dugtrio;Meowth;Persian;Psyduck;Golduck;Mankey;Primeape;Growlith;Arcanine;Poliwag;Poliwhirl;Poliwrath;Abra;Kadabra;Alakazam;Machop;Machoke;Machamp;Bellsprout;Weepinbell;Victreebell;Tentacool;Tentacruel;Geodude;Graveler;Golem;Ponyta;Rapidash;Slowpoke;Slowbro;Magnemite;Magneton;Farfetch'd;Doduo;Dodrio;Seel;Dewgong;Grimer;Muk;Shellder;Cloyster;Gastly;Haunter;Gengar;Onix;Drowsee;Hypno;Krabby;Kingler;Voltorb;Electrode;Exeggute;Exeggutor;Cubone;Marowak;Hitmonlee;Hitmonchan;Lickitung;Koffing;Weezing;Rhyhorn;Rhydon;Chansey;Tangela;Kangaskhan;Horsea;Seadra;Goldeen;Seaking;Staryu;Starmie;Mr. Mime;Scyther;Jynx;Electabuzz;Magmar;Pinsir;Tauros;Magikarp;Gyarados;Lapras;Ditto;Eevee;Vaporeon;Jolteon;Flareon;Porygon;Omanyte;Omastar;Kabuto;Kabutops;Aerodactyl;Snorlax;Articuno;Zapdos;Moltres;Dratini;Dragonair;Dragonite;Mewtwo;Mew".split`;`[n]

```

Try it online! <sub>Node.Js because there's no plain JS</sub>

---
Tags: code-golf, kolmogorov-complexity
---


title: Random numbers with fixed sum

text:
# Question
Title: Random numbers with fixed sum
Your task is to write a program or a function that outputs `n` random numbers from interval \[0,1\] with fixed sum `s`.

# Input

`n, n≥1`, number of random numbers to generate

`s, s>=0, s<=n`, sum of numbers to be generated

# Output

A random `n`-tuple of floating point numbers with all elements **from the interval \[0,1\]** and sum of all elements equal to `s`, output in any convenient unambiguous way. All valid `n`-tuples have to be equally likely within the limitations of floating point numbers.

This is equal to uniformly sampling from the intersection of the points inside the `n`-dimensional unit cube and the `n-1`-dimensional hyperplane that goes through `(s/n, s/n, …, s/n)` and is perpendicular to the vector `(1, 1, …, 1)` (see red area in Figure 1 for three examples).

Figure 1: The plane of valid outputs with n=3 and sums 0.75, 1.75 and 2.75

# Examples

```
n=1, s=0.8 → [0.8]
n=3, s=3.0 → [1.0, 1.0, 1.0]
n=2, s=0.0 → [0.0, 0.0]
n=4, s=2.0 → [0.2509075946818119, 0.14887693388076845, 0.9449661625992032, 0.6552493088382167]
n=10, s=9.999999999999 → [0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999]

```

# Rules

* Your program should finish under a second on your machine at least with `n≤10` and any valid s.
* If you so wish, your program can be exclusive on the upper end, i.e. `s<n` and the output numbers from the half-open interval \[0,1) (breaking the second example)
* If your language doesn't support floating point numbers, you can fake the output with at least ten decimal digits after the decimal point.
* Standard loopholes are disallowed and standard input/output methods are allowed.
* This is , so the shortest entry, measured in bytes, wins.

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~92~~ 90 bytes

```
If[2#2>#,1-#0[#,#-#2],While[Max[v=Differences@Sort@Join[{0,#2},RandomReal[#2,#-1]]]>1];v]&

```

Try it online!

Un-golfed code:

```
R[n_, s_] := Module[{v},
  If[s <= n/2,             (* rejection sampling for s <= n/2:                        *)
    While[
      v = Differences[Sort[
            Join[{0},RandomReal[s,n-1],{s}]]];         (* trial randoms that sum to s *)
      Max[v] > 1           (* loop until good solution found                          *)
    ];
    v,                     (* return the good solution                                *)
    1 - R[n, n - s]]]      (* for s > n/2, invert the cube and rejection-sample       *)

```

---

Here is a solution that works in **55 bytes** but for now (Mathematica version 12) is restricted to `n=1,2,3` because `RandomPoint` refuses to draw points from higher-dimensional hyperplanes (in TIO's version 11.3 it also fails for `n=1`). It may work for higher `n` in the future though:

```
RandomPoint[1&~Array~#~Hyperplane~#2,1,{0,1}&~Array~#]&

```

Try it online!

Un-golfed code:

```
R[n_, s_] :=
  RandomPoint[                           (* draw a random point from *)
    Hyperplane[ConstantArray[1, n], s],  (* the hyperplane where the sum of coordinates is s *)
    1,                                   (* draw only one point *)
    ConstantArray[{0, 1}, n]]            (* restrict each coordinate to [0,1] *)

```

# Answer
> 8 votes
# JavaScript (Node.js), ~~122~~ 115 bytes

```
N=>W=S=>2*S>N?W(N-S).map(t=>1-t):(t=(Q=s=>n?[r=s-s*Math.random()**(1/--n),...r>1?[++Q]:Q(s-r)]:[])(S,n=N),Q?t:W(S))

```

Try it online!

# Answer
> 6 votes
# Python 2, ~~144~~ ~~128~~ 119 bytes

```
from random import*
def f(n,s):
 r=min(s,1);x=uniform(max(0,r-(r-s/n)*2),r);return n<2and[s]or sample([x]+f(n-1,s-x),n)

```

Try it online!

---

* -20 bytes, thanks to Kevin Cruijssen

# Answer
> 4 votes
# Java 8, ~~194~~ ~~188~~ ~~196~~ ~~237~~ 236 bytes

```
n->s->{double r[]=new double[n+1],d[]=new double[n],t;int f=0,i=n,x=2*s>n?1:0;for(r[n]=s=x>0?n-s:s;f<1;){for(f=1;i-->1;)r[i]=Math.random()*s;for(java.util.Arrays.sort(r);i<n;d[i++]=x>0?1-t:t)f=(t=Math.abs(r[i]-r[i+1]))>1?0:f;}return d;}

```

+49 bytes (188 → 196 and 196 → 237) to fix the speed of test cases nearing 1, as well as fix the algorithm in general.

Try it online

**Explanation:**

Uses the approach in this StackoverFlow answer, inside a loop as long as one of the items is still larger than 1.
Also, if `2*s>n`, `s` will be changed into `n-s`, and a flag is set to indicate we should use `1-diff` instead of `diff` in the result-array (thanks for the tip *@soktinpk* and *@l4m2*).

```
n->s->{              // Method with integer & double parameters and Object return-type
  double r[]=new double[n+1]
                     //  Double-array of random values of size `n+1`
         d[]=new double[n],
                     //  Resulting double-array of size `n`
         t;          //  Temp double
  int f=0,           //  Integer-flag (every item below 1), starting at 0
      i=n,           //  Index-integer, starting at `n`
      x=             //  Integer-flag (average below 0.5), starting at:
        2*s>n?       //   If two times `s` is larger than `n`:
         1           //    Set this flag to 1
        :            //   Else:
         0;          //    Set this flag to 0
  for(r[n]=s=        //  Set both the last item of `r` and `s` to:
       x>0?          //   If the flag `x` is 1:
        n-s          //    Set both to `n-s`
       :             //   Else:
        s;           //    Set both to `s`
      f<1;){         //  Loop as long as flag `f` is still 0
    for(f=1;         //   Reset the flag `f` to 1
        i-->1;)      //   Inner loop `i` in range (n,1] (skipping the first item)
      r[i]=Math.random()*s;
                     //    Set the i'th item in `r` to a random value in the range [0,s)
    for(java.util.Arrays.sort(r);
                     //   Sort the array `r` from lowest to highest
        i<n;         //   Inner loop `i` in the range [1,n)
        ;d[i++]=     //     After every iteration: Set the i'th item in `d` to:
          x>0?       //      If the flag `x` is 1:
           1-t       //       Set it to `1-t`
          :          //      Else:
           t)        //       Set it to `t`
      f=(t=Math.abs( //    Set `t` to the absolute difference of:
            r[i]-r[i+1]))
                     //     The i'th & (i+1)'th items in `r`
        >1?          //    And if `t` is larger than 1 (out of the [0,1] boundary)
         0           //     Set the flag `f` to 0
        :            //    Else:
         f;}         //     Leave the flag `f` unchanged
  return d;}         //  Return the array `d` as result

```

# Answer
> 3 votes
# JavaScript (Node.js), 153 bytes

```
(n,s)=>s+s>n?g(n,n-s).map(r=>1-r):g(n,s)
g=(n,s)=>{do(a=[...Array(n-1)].map(_=>Math.random()*(s<1?s:1))).map(r=>t-=r,t=s);while(t<0|t>=1);return[...a,t]}

```

Try it online!

# Answer
> 3 votes
## C++11, ~~284~~ 267 bytes

-17 bytes thanks to Zacharý
Uses C++ random library, output on the standard output

```
#include<iostream>
#include<random>
typedef float z;template<int N>void g(z s){z a[N],d=s/N;int i=N;for(;i;)a[--i]=d;std::uniform_real_distribution<z>u(.0,d<.5?d:1-d);std::default_random_engine e;for(;i<N;){z c=u(e);a[i]+=c;a[++i]-=c;}for(;i;)std::cout<<a[--i]<<' ';}

```

To call, you just need to do that :

```
g<2>(0.0);

```

Where the template parameter ( here, 2 ) is N, and the actual parameter ( here, 0.0 ) is S

# Answer
> 3 votes
# C, ~~132~~ ~~127~~ ~~125~~ ~~118~~ ~~110~~ 107 bytes

*-2 bytes thanks to @ceilingcat*

```
i;f(s,n,o,d)float*o,s,d;{for(i=n;i;o[--i]=d=s/n);for(;i<n;o[++i%n]-=s)o[i]+=s=(d<.5?d:1-d)*rand()/(1<<31);}

```

Try it online!

# Answer
> 2 votes
# Clean, ~~221~~ 201 bytes

*Clean, code-golf, or random numbers. Pick two.*

```
import StdEnv,Math.Random,System._Unsafe,System.Time
g l n s#k=toReal n
|s/k>0.5=[s/k-e\\e<-g l n(k-s)]
#r=take n l
#r=[e*s/sum r\\e<-r]
|all((>)1.0)r=r=g(tl l)n s

```

#

```
g(genRandReal(toInt(accUnsafe time)))

```

Try it online!

Partial function literal `:: (Int Real -> [Real])`. Will only produce new results once per second.
Accurate up to at least 10 decimal places.

# Answer
> 2 votes
# , 99 bytes (with `gtools` package)

```
f=function(n,s){if(s>n/2)return(1-f(n,n-s))
while(any(T>=1)){T=gtools::rdirichlet(1,rep(1,n))*s}
T}

```

Try it online!

We wish to sample uniformly from the set \\$\tilde{\mathcal A}=\\{w\_1,\ldots,w\_n: \forall i, 0\<w\_i\<1; \sum w\_i=s\\}\\$. I'll divide all the \\$w\_i\\$ by \\$s\\$ and instead sample from \\$\mathcal A=\\{w\_1,\ldots,w\_n: \forall i, 0\<w\_i\<\frac1s; \sum w\_i=1\\}\\$.

If \\$s=1\\$, this is easy: it corresponds to sampling from the \\$Dirichlet(1, 1, \ldots, 1)\\$ distribution (which is the uniform over the simplex). For the general case \\$s\neq 1\\$, we use rejection sampling: sample from the Dirichlet distribution until all entries are \\$\<1/s\\$, then multiply by \\$s\\$.

The trick to mirror when \\$s\>n/2\\$ (which I think l4m2 was the first to figure out) is essential. Before I saw that, the number of iterations in the rejection sampler exploded for the last test case, so I spent a *lot* of time trying to sample efficiently from well-chosen truncated Beta distributions, but it is not necessary in the end.

# Answer
> 1 votes
# Haskell, ~~122~~ ~~217~~ 208 bytes

```
import System.Random
r p=randomR p
(n#s)g|n<1=[]|(x,q)<-r(max 0$s-n+1,min 1 s)g=x:((n-1)#(s-x)$q)
g![]=[]
g!a|(i,q)<-r(0,length a-1)g=a!!i:q![x|(j,x)<-zip[0..]a,i/=j]
n%s=uncurry(!).(n#s<$>).split<$>newStdGen

```

Try it online!

Sometimes the answers are slightly off due, I assume, to floating point error. If it's an issue I can fix it at a cost of 1 byte. I'm also not sure how uniform this is (pretty sure it's fine but I'm not all that good at this kind of thing), so I'll describe my algorithm.

Basic idea is to generate a number `x` then subtract it from `s` and recur until we have `n` elements then shuffle them. I generate `x` with an upper bound of either 1 or `s` (whichever is smaller) and a lower bound of `s-n+1` or 0 (whichever is greater). That lower bound is there so that on the next iteration `s` will still be less than or equal to `n` (derivation: `s-x<=n-1` -\> `s<=n-1+x` -\> `s-(n-1)<=x` -\> `s-n+1<=x`).

EDIT: Thanks to @michi7x7 for pointing out a flaw in my uniformity. I think I've fixed it with shuffling but let me know if there's another problem

EDIT2: Improved byte count plus fixed type restriction

# Answer
> 1 votes
# Haskell, 188 bytes

```
import System.Random
import Data.List
n!s|s>n/2=map(1-)<$>n!(n-s)|1>0=(zipWith(-)=<<tail).sort.map(*s).(++[0,1::Double])<$>mapM(\a->randomIO)[2..n]>>= \a->if all(<=1)a then pure a else n!s

```

Ungolfed:

```
n!s
 |s>n/2       = map (1-) <$> n!(n-s)       --If total more than half the # of numbers, mirror calculation
 |otherwise   = (zipWith(-)=<<tail)        --Calculate interval lengths between consecutive numbers
              . sort                       --Sort
              . map(*s)                    --Scale
              . (++[0,1::Double])          --Add endpoints
              <$> mapM(\a->randomIO)[2..n] --Calculate n-1 random numbers
              >>= \a->if all(<=1)a then pure a else n!s   --Retry if a number was too large

```

Try it online!

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


title: Generate a Baseball Pitch String

text:
# Question
Title: Generate a Baseball Pitch String
# Goal

Write a program or function that takes a positive integer `n` and randomly generate a legal series of pitches (henceforth called a Pitch string) of length `n`.

# Input

A non-zero, positive integer `n` \<= 100

# Output

Return a random string, or list of characters, that represent a possible, valid pitch string of length `n`. The characters used will be:

* **B** \- Ball. If you accumulate 4 of these, the batter is walked and finished batting.
* **S** \- Strike. If you accumulate 3 of these, the batter is out and finished batting.
* **F** \- Foul. Will also increase the Strike count but cannot get the batter out. I.e., you cannot have a Foul be the last pitch in a valid string. Any fouls past two strikes/fouls will not increase the Strike count (the batter already has 2 strikes at that point and a 3rd would get him out).
* **H** \- Hit. The batter has hit a ball into play and is finished batting.

(This is simplified slightly but don't you worry about that)

Valid pitch strings are those that end in a strike-out, a walk, or a hit.

I.e., an **invalid** pitch string has either

* additional pitches after the 4th Ball, 3rd Strike, or Hit
* terminated before generating a 4th ball, 3rd strike, or Hit.

# Rules

* Your program must be able to produce all possible results for a given input.
* Your program does not have to be uniformly random but still must follow the previous rule.
* This is .

# Examples

```
Input => Possible Outputs
1 => [H] #Can only end with a hit
2 => [S,H], [B,H], [F,H] #Can only end with a hit
3 => [S,S,S], [F,F,S], [B,B,H], ... #Can now strike-out, otherwise must end with a hit
4 => [B,B,B,B], [S,B,S,S], [B,F,S,S], [B,B,B,H], ... #Can now be walked, struck-out, or get a hit
6 => [S,B,S,B,B,H], [F,F,F,F,F,S], ... #Can now have a full-count (3 balls, 2 strikes) before finishing

Input => Invalid Outputs
1 => [S], [B]    #Not enough for a strike-out/walk
2 => [S,S]       #Not enough for a strike-out/walk
2 => [H,H]       #Batter has already scored a hit
3 => [S,S,F]     #Fouls will not cause a strike-out
4 => [S,S,S,H]   #Batter has already struck out
5 => [B,B,B,B,B] #Batter has already walked

```

# Answer
> 4 votes
# Python 2, 128 bytes

```
from random import*
def g(n):
 x=i=S=0;r=''
 while(S>2)+x<3>=i-S:x=randint(0,3);r+='BFSH'[x];S+=x>0;i+=1
 return(i==n)*r or g(n)

```

Try it online!

Randomly generate the pitch string until the batter is done, output it if it turns out the right length, and otherwise try again from scratch.

---

**Python 2, 136 bytes**

```
from random import*
def g(n):
 B=H=F=S=0;r=''
 while(F+S<3or'S'>x)>B/4+H:x=choice('BHFS');r+=x;exec x+"+=1"
 return(len(r)==n)*r or g(n)

```

Try it online!

# Answer
> 4 votes
# 05AB1E,  ~~44~~  ~~50~~ 44 bytes

*Crossed out ` 44 ` is no longer 44 :)*

```
[õ0U.µ["BFSH"3ÝΩ©è«®ĀX+U¼X2›®+3@¾X-3›~#}I¾Q#

```

Port of *@xnor*'s Python 2 answer, so make sure to upvote him as well if you like this answer!
+6 bytes due to a bug-fix, and after that -6 bytes again thanks to *@xnor* by porting his way more efficient fix in comparison to my temporary work-around, as I was expecting. ;)

Try it online or verify some more random outputs.

**Explanation:**

```
[                # Start an infinite loop:
 õ               #  (Re)set the result-string to an empty string ""
 0U              #  (Re)set variable `X` to 0
 .µ              #  Reset the counter_variable to 0
   [             #  Start an inner infinite loop:
    "BFSH"       #   Push string "BFSH"
          3ÝΩ    #   Push a random integer in the range [0,3]
             ©   #   Store this random integer in variable `r` (without popping)
              è  #   Index it into the string "BFSH"
               « #   Append it to the result-string
    ®Ā           #   If `r` is NOT 0:
      X+U        #    Increase `X` by 1
    ¼            #   Increase the counter_variable by 1
    X2›®+        #   Calculate `X`>2 (1 if truthy; 0 if falsey) + `r`
         3@      #   Check if this is larger than or equal to 3
    ¾X-          #   Calculate counter_variable - `X`
       3›        #   Check if this is larger than 3
    ~            #   If either of the two checks above is truhy:
     #           #    Stop the inner infinite loop
   }             #  After the inner infinite loop:
    I¾Q          #  If the input and counter_variable are equal:
       #         #   Stop the outer infinite loop
                 # (and output the result-string at the top of the stack implicitly)

```

# Answer
> 3 votes
# , 148 bytes

```
function(n){`~`=paste0
`*`=sample
o=""
while(nchar(o)<n-1){a=c("B"[T<4],"F","S"[F<2])*1
F=F+(a>"E")
T=T+(a<"F")
o=o~a}
o~c("B"[T>3],"H","S"[F>1])*1}

```

Try it online!

Generates the string, using conditional inclusion in the sampling datasets to ensure that the result is a possible pitch sequence.

Possibly doing rejection sampling (as xnor's python answer does) is shorter.

```
function(n){`~`=paste0		# alias
`*`=sample			# alias
o=""				# empty string for output
while(nchar(o)<n-1){		# do n-1 times:
a=c("B"[T<4],"F","S"[F<2])*1	# sample 1 from the string "BFS", conditionally including B or S if the ball/strike count is 3/2
F=F+(a>"E")			# increment F (strike count) if sampled character is F or S
T=T+(a<"F")			# increment T (ball count) if sampled character is B
o=o~a}				# append a to output

o~c("B"[T>3],"H","S"[F>1])*1}	# append the sampled "BHS", conditionally including B or S if the ball/strike count is 3/2.

```

Random "F and S" reference that kept playing in my head every time I typed one of those letters...

# Answer
> 2 votes
# JavaScript (SpiderMonkey), 137 bytes

```
f=(n,o='',i=Math.random()*4|0,r=/^(?!.*((B.*){4}|([SF].*){2}S|H).)/)=>r.test(o)?n?f(n-1,o+'BSFH'[i%4])||i<8&&f(n,o,i+1):!r.test(o+1)&&o:0

```

Try it online!

# Answer
> 2 votes
# Pyth, 53 bytes

```
u+GO?H+W<K/G\B3+W<Jl@"SF"G2\F\S\B+WqK3+WgJ2\H\S\B_UQ[

```

Try it online here.

This feels way too long, I think another approach may be required.

```
u+GO?H+W<K/G\B3+W<Jl@"SF"G2\F\S\B+WqK3+WgJ2\H\S\B_UQ[   Implicit: Q=eval(input())
                                                 _UQ    Reversed range from Q-1 to 0
u                                                   [   Reduce the above, with initial value G=[], next value as H:
                    @"SF"G                                Keep elements of G which are in "SF"
                   l                                      Length of the above
                  J                                       Store in J - this is the number of strikes and fouls so far
          /G\B                                            Count number of "B"s in G
         K                                                Store in K - this is the number of balls so far
    ?H                                                    If H is not 0 (i.e. not final pitch):
                           \F                               Start with "F" (foul is always available in non-final pitch)
                W<J       2                                 If J<2...
               +             \S                             ... append "S"
       W<K    3                                             If K<3...
      +                        \B                           ... append "B"
                                                          Else:
                                           \H               Start with "H" (hit is always available in final pitch)
                                       WgJ2                 If J >= 2...
                                      +      \S             ... append "S"
                                  WqK3                      If K == 3...
                                 +             \B           ... append "B"
   O                                                      Choose one element at random from the available options
 +G                                                       Append the above to G
                                                        Implicit print the result of the reduce operation

```

# Answer
> 2 votes
# JavaScript (ES6),  ~~107 106~~  99 bytes

```
f=(n,k=p=s=0,o='')=>p&&p>2|k-s>3|s>2&p<2?k-n?f(n):o:f(n,k+1,o+'FSBH'[p=Math.random()*4|0,s+=p<2,p])

```

Try it online!

### Commented

```
f = (                       // f = recursive function taking:
  n,                        //   n = requested length
  k =                       //   k = pitch counter, initialized to 0
  p =                       //   p = last pitch
  s = 0,                    //   s = sum of strikes and fouls
  o = ''                    //   o = output string
) =>                        //
  p &&                      // if the last pitch was not a foul
  p > 2 |                   // AND the last pitch was a hit
  k - s > 3 |               //     OR we have 4 balls (or 3 balls + 1 hit)
  s > 2 & p < 2 ?           //     OR more than 2 strikes or fouls, ending with a strike:
    k - n ?                 //   if k is not equal to n:
      f(n)                  //     valid series but bad timing: try again from scratch
    :                       //   else:
      o                     //     success: return o
  :                         // else:
    f(                      //   do a recursive call:
      n,                    //     n is unchanged
      k + 1,                //     increment k
      o + 'FSBH'            //     append the pitch letter to o
        [ p = Math.random() //     pick a new random pitch
              * 4 | 0,      //     in [0..3]
          s += p < 2,       //     increment s if the pitch is a foul or a strike
          p ]               //     actual index in 'FSBH'
    )                       //   end of recursive call

```

# Answer
> 2 votes
# Ink, ~~120~~ ~~119~~ ~~116~~ 117 bytes

```
=f(n)
->g(n,3,2)
=g(n,b,s)
~n--
{n:{~{b:b->g(n,b-1,s)}|{s:s->g(n,b,s-1)}|}f->g(n,b,s-(s>0))|{~{b:h|b}|{s:h|s}|h}}->->

```

Try it online!

Probably still golfable.

# Ungolfed (mildly reformatted)

```
=f(length) // Define a stitch f, with one parameter which specifies the length of the created string. This is the intended entry point.
->g(length,3,2) // Instantly divert to g, defined below, with some extra parameters

=g(length,balls_left,strikes_left) // Define a stitch g, with three parameters.
~ length--                         // Decrement remaining length
{
    - length: // If this is not to be the last character in the string
              // randomly do one of the following:
              // 1. If balls_left is nonzero, print a b and recurse
              // 2. If strikes_left is nonzero, print an s and recurse
              // 3. Do nothing
              // If we did not divert earlier, print an f and recurse.
        {~{balls_left:b->g(length,balls_left-1,strikes_left)}|{strikes_left:s->g(length,balls_left,strikes_left-1)}|}f->g(length,balls_left,strikes_left-(strikes_left>0))
    - else: // Randomly do one of the following
            // 1. If a ball would result in a walk, print a b, otherwise an h.
            // 2. If a strike would result in a strikeout, print an s, otherwise an h.
            // 3. Just print an h.
            // And finally, halt.
        {~{balls_left:h|b}|{strikes_left:h|s}|h}}->->

```

**Edits**

1. Saved a byte by finishing with `->->` instead of `->END`.
2. Saved three bytes by decrementing `n` earlier.
3. Fixed a bug that caused strikeouts in incorrect places, thanks to @veskah for spotting it (+1 byte)

# Answer
> 1 votes
# APL (Dyalog Unicode), 77 bytesSBCS

```
{'HBSF'[{⍺←⍬⋄∨/((⊃⌽⍺)=⍳3)∧1,4 3≤(⊃s),+/1↓s←⍺∘(+/=)¨1+⍳3:⍺⋄∇⍨⍺,?4}⍣{i=≢⍺}i←⍵]}

```

Try it online!

# Answer
> 1 votes
# Charcoal, 57 bytes

```
≔⁰η≔⁰ζＦ⊖Ｎ«≔‽⁺²‹ζ³ι¿›ι¹≦⊕ζ≦⊕η§SFB∨ι›η²»⊞υHＦ›η¹⊞υSＦ›ζ²⊞υB‽υ

```

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

```
≔⁰η≔⁰ζ

```

Start with 0 balls and 0 strikes.

```
Ｆ⊖Ｎ«

```

Loop over all of the deliveries except the last.

```
≔‽⁺²‹ζ³ι

```

If the have been fewer than three balls, then generate a random number from 0 to 2, otherwise just coinflip between 0 and 1.

```
¿›ι¹≦⊕ζ≦⊕η

```

A random value of 2 is a ball otherwise it increases the strike count.

```
§SFB∨ι›η²»

```

The values 0 to 2 map to strike, foul and ball, except that if there would be three strikes then foul is printed instead. (Four balls are excluded above.)

```
⊞υHＦ›η¹⊞υSＦ›ζ²⊞υB‽υ

```

Determine whether a strike or ball would get the batter out and choose from those or a hit as appropriate.

# Answer
> 1 votes
# C (GCC) ~~164~~ ~~145~~ 142 bytes

-3 bytes ceilingcat

```
#define A(a)!i&&!r--?puts(#a),++a,--n:0;
b,s,f,h,i,r;p(n){srand(time(0));for(i=n;i--;){for(n=1;n;){r=rand()&3;b>2^!A(b)s+f>1^!A(s)!A(f)A(h)}}}

```

Try it online

# Answer
> 1 votes
# Perl 5, 122 bytes

```
map{$B=$S=$H=0;while($B<4&&$S<3&&!$H&&/./g){${$&}++;$S+=$&eq F&&$S<2}y///c>pos||push@a,$_}glob"{B,F,H,S}"x<>;say$a[rand@a]

```

Try it online!

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


# Question
Title: Fully-justify & hyphenate a block of text
```
Given  a width  and  a block  of
text containing possible hyphen-
ation points,  format it  fully-
justified (in monospace).

```

Fully justified means it is aligned on the left *and* the right, and is achieved by increasing the spacing between words until each line fits.

Related:

## Input

You can take input in any format you like. You will be given:

* A target width (in characters), in the range 5-100 (inclusive);
* A block of text containing possibly hyphenated words. This could be a space-separated string, an array of words, or an array of arrays of word fragments (or any other data representation you desire).

A typical input might be:

```
Width: 25
Text:  There's no bu-si-ne-ss lik-e s-h-o-w busine-ss, n-o bus-iness I know.

```

Where the hyphens denote possible hyphenation points, and the spaces denote word boundaries. A possible alternative representation of the text:

```
[["There's"], ["no"], ["bu", "si", "ne", "ss"], ["lik", "e"], (etc.)]

```

## Output

The input text with spaces added between words, newlines at the column width, and hyphenation points chosen to fully-justify it to the column width. For functions, an array of strings (one for each line) can be returned instead of using newline separation.

A possible output for the above input might be:

```
There's no  business like
show  business,  no  bus-
iness I know.

```

Note that all hyphens have been removed except the one in the final "bus-iness", which is kept to show that the word wraps to the next line, and was chosen to ensure the second line contains as much text as possible.

## Rules

* Within each line, the number of spaces between words cannot vary by more than 1, but where you insert the extra spaces is otherwise up to you:

```
hello hi foo     bar    <-- not permitted (1,1,5)
hello  hi foo    bar    <-- not permitted (2,1,4)
hello  hi  foo   bar    <-- OK (2,2,3)
hello  hi   foo  bar    <-- OK (2,3,2)
hello   hi  foo  bar    <-- OK (3,2,2)

```
* No line can begin or end with spaces (except the last line, which can end with spaces).
* The last line should be left justified, containing single spaces between each word. It can be followed by arbitrary whitespace / a newline if desired, but this is not required.
* Words will consist of A-Z, a-z, 0-9 and simple punctuation (`.,'()&`)
* You can assume that no word fragment will be longer than the target width, and it will always be possible to fill lines according to the rules (i.e. there will be at least 2 word fragments on each line, or 1 word fragment which fills the line perfectly)
* You must choose hyphenation points which maximise the number of word characters on earlier lines (i.e. words must be consumed greedily by lines), for example:

```
This is an input stri-ng with hyph-en-at-ion poi-nts.

This     is     an     input    stri-      <-- not permitted
ng with hyphenation points.

This  is an  input string  with hyph-      <-- not permitted
enation points.

This is an input  string with hyphen-      <-- OK
ation points.

```
* Shortest code in bytes wins

## Examples

```
Width: 20
Text:  The q-uick brown fox ju-mp-s ove-r t-h-e lazy dog.

The quick  brown fox
jumps over the  lazy
dog.

```

---

```
Width: 32
Text: Given a width and a block of text cont-ain-ing pos-sible hyphen-ation points, for-mat it ful-ly-just-ified (in mono-space).

Given  a width  and  a block  of
text containing possible hyphen-
ation points,  format it  fully-
justified (in monospace).

```

---

```
Width: 80
Text:  Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.

Programming Puzzles &  Code Golf  is a question and answer  site for programming
puzzle enthusiasts  and code golfers.  It's built and run  by you as part of the
Stack Exchange network  of Q&A sites. With your help,  we're working together to
build a library of programming puzzles and their solutions.

```

---

```
Width: 20
Text:  Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.

Programming  Puzzles
&  Code  Golf  is  a
question and  answer
site for programming
puzzle   enthusiasts
and  code   golfers.
It's  built  and run
by  you  as  part of
the  Stack  Exchange
network    of    Q&A
sites.   With   your
help,  we're working
together to  build a
library of  program-
ming   puzzles   and
their solutions.

```

---

```
Width: 5
Text:  a b c d e f g h i j k l mm nn oo p-p qq rr ss t u vv ww x yy z

a b c
d e f
g h i
j k l
mm nn
oo pp
qq rr
ss  t
u  vv
ww  x
yy z

```

---

```
Width: 10
Text:  It's the bl-ack be-ast of Araghhhhh-hhh-h-hhh-h-h-h-hh!

It's   the
black  be-
ast     of
Araghhhhh-
hhhhhhhhh-
hhh!

```

# Answer
# JavaScript (ES6), 218 bytes

```
w=>s=>s.map((c,i)=>c.map((p,j)=>(k+p)[l="length"]-w-(b=!i|j>0)+(j<c[l]-1)<0?k+=b?p:" "+p:(Array(w-k[l]-b).fill(h=k.split` `).map((_,i)=>h[i%(h[l]-1)]+=" "),o.push(h.join` `+(b?"-":"")),k=p)),o=[],k="")&&o.join`
`+`
`+k

```

Takes arguments in currying syntax (`f(width)(text)`) and the text input is in the double array format described in the challenge. Strings are converted to that format via `.split` `.map(a=>a.split`-`))`. Also, the newlines are literal newlines inside template strings.

## Un-golfed and rearranged

```
width=>string=> {
    out=[];
    line="";
    string.map((word,i)=> {
        word.map((part,j)=> {

            noSpaceBefore = i==0 || j>0;
            if ((line+part).length - width - noSpaceBefore + (j<word.length-1) < 0) {
                line += noSpaceBefore ? part : " "+part;
            }
            else {
                words=line.split` `;
                Array(width - line.length - noSpaceBefore).fill()
                    .map((_,i) => words[i % (words.length-1)] += " ");
                out.push(words.join(" ") + (noSpaceBefore? "-" : ""));
                line=part;
            }
        });
    });
    return out.join("\n") + "\n"+line
}

```

The idea here was to step through each part of the entire string and build up each line one part at a time. Once a line was complete, it increases the word spacing from left to right until all extra spaces are placed.

## Test Snippet

```
f=
w=>s=>s.map((c,i)=>c.map((p,j)=>(k+p)[l="length"]-w-(b=!i|j>0)+(j<c[l]-1)<0?k+=b?p:" "+p:(Array(w-k[l]-b).fill(h=k.split` `).map((_,i)=>h[i%(h[l]-1)]+=" "),o.push(h.join` `+(b?"-":"")),k=p)),o=[],k="")&&o.join`
`+`
`+k
```

```
<style>*{font-family:Consolas,monospace;}</style>
<div oninput="O.innerHTML=f(+W.value)(S.value.split` `.map(a=>a.split`-`))">
Width: <input type="number" size="3" min="5" max="100" id="W">
Tests: <select id="T" style="width:20em" oninput="let x=T.value.indexOf(','),s=T.value;W.value=s.slice(0,x);S.value=s.slice(x+2)"><option></option><option>20, The q-uick brown fox ju-mp-s ove-r t-h-e lazy dog.</option><option>32, Given a width and a block of text cont-ain-ing pos-sible hyphen-ation points, for-mat it ful-ly-just-ified (in mono-space).</option><option>80, Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.</option><option>20, Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.</option><option>5, a b c d e f g h i j k l mm nn oo p-p qq rr ss t u vv ww x yy z</option><option>10, It's the bl-ack be-ast of Araghhhhh-hhh-h-hhh-h-h-h-hh</option></select><br>
Text:  <textarea id="S" cols="55" rows="4"></textarea>
</div>
<pre id="O" style="border: 1px solid black;display:inline-block;"></pre>
```
> 8 votes

# Answer
# GNU sed `-r`, 621 bytes

Takes input as two lines: The width as a unary number first and the string second.

I'm certain this could be golfed much more but I've already dumped way too much time into it.

```
x;N
G
s/\n/!@/
:
/@\n/bZ
s/-!(.*)@ /\1 !@/
s/!(.*[- ])(@.*1)$/\1!\2/
s/@(.)(.*)1$/\1@\2/
s/-!(.*-)(@.*)\n$/\1!\2\n1/
s/(\n!@) /\1/
s/-!(.* )(@.*)\n$/\1!\2\n1/
s/-!(.*-)(@.*1)$/\1!\21/
s/!(.*)-@([^ ]) /\1\2!@ /
t
s/ !@(.*)\n$/\n!@\1#/
s/!(.*-)@(.*)\n$/\1\n!@\2#/
s/!(.*)(@ | @)(.*)\n$/\1\n!@\3#/
s/-!(.*[^-])@([^ ]) (.*)\n$/\1\2\n!@\3#/
s/!(.+)@([^ ].*)\n$/\n!@\1\2#/
/#|!@.*\n$/{s/#|\n$//;G;b}
:Z
s/-?!|@.*//g
s/ \n/\n/g
s/^/%/
:B
G
/%.*\n.+\n/!bQ
:C
s/%([^\n])(.*)1$/\1%\2/
tC
s/([^\n]+)%\n/%\1\n/
:D
s/%([^ \n]* )(.*)1$/\1 %\2/
tD
s/(^|\n)([^\n]+)%(.*1)$/\1%\2\3/
tD
s/%([^\n]*)\n(.*)\n$/\1\n%\2/
tB
:Q
s/%(.*)\n1*$/\1/

```

Try it online!

## Explanation

The program works in two phases: 1. Split, and 2. Justify. For the below, suppose our input is:

> ```
> 111111111111
> I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.
>
> ```

### Setup

First we read the input, moving the first line (the width as a unary number) to the hold space (`x`), then appending the next line (`N`) and then a copy of the width from the hold space (`G`) to the pattern space. Since `N` left us with a leading `\n` we replace it with `!@`, which we'll use as cursors in Phase 1.

```
x;N
G
s/\n/!@/

```

Now the content of the hold space is `1111111111111` (and won't change henceforth) and the pattern space is (in the format of sed's "print unambiguously" `l` command):

> ```
> !@I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$
>
> ```

### Phase 1

In Phase 1, the main `@` cursor advances one character at a time, and for each character a `1` is removed from the "counter" at the end of the pattern space. In other words, `@foo\n111$`, `f@oo\n11$`, `fo@o\n1$`, etc.

The `!` cursor trails behind the `@` cursor, marking places we could break if the counter reaches 0 in the middle of the line. A couple rounds would look like this:

> ```
> !@I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$
> !I@ re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n11111111111$
> !I @re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111111$
>
> ```

Here there's a pattern we recognize: a space immediately followed by the `@` cursor. Since the counter is greater than 0, we advance the break marker, then keep advancing the main cursor:

> ```
> I !@re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111111$
> I !r@e-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111$
> I !re@-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n11111111$
> I !re-@mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111$
>
> ```

Here's another pattern: `-@`, and we still have 7 in the counter, so we advance the break cursor again and keep advancing:

> ```
> I re-!mem-@ber a time of cha-os, ru-ined dreams, this was-ted land.\n111$
>
> ```

Here's a different pattern: A hyphen immediately preceding the break cursor and another preceding the main cursor. We remove the first hyphen, advance the break cursor, and, since we removed a character, add 1 to the counter.

> ```
> I remem-!@ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111$
>
> ```

We keep advancing the main cursor:

> ```
> I remem-!ber@ a time of cha-os, ru-ined dreams, this was-ted land.\n1$
>
> ```

Similar to before, but this time the main cursor precedes a space rather than following a hyphen. We remove the hyphen, but since we're also advancing the main cursor we neither increment no decrement the counter.

> ```
> I remember !@a time of cha-os, ru-ined dreams, this was-ted land.\n1$
> I remember !a@ time of cha-os, ru-ined dreams, this was-ted land.\n$
>
> ```

Finally, our counter has reached zero. Since the character after the main cursor is a space, we insert a newline and put both cursors immediately after it. Then we replenish the counter (`G`) and start again.

> ```
> I remember a\n!@ time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$
>
> ```

Phase 1 continues, advancing the cursors and matching various patterns, until the `@` cursor reaches the end of the string.

```
# Phase 1
:
  # End of string; branch to :Z (end of phase 1)
  /@\n/bZ

  # Match -!.*@_
  s/-!(.*)@ /\1 !@/

  # Match [-_]@ and >0
  s/!(.*[- ])(@.*1)$/\1!\2/

  # Advance cursor
  s/@(.)(.*)1$/\1@\2/

  # Match -!.*-@ and 0; add 1
  s/-!(.*-)(@.*)\n$/\1!\2\n1/

  # Match \n!@_
  s/(\n!@) /\1/

  # Match -!.*_@ and 0; add 1
  s/-!(.* )(@.*)\n$/\1!\2\n1/

  # Match -!.*-@ and >0; add 1
  s/-!(.*-)(@.*1)$/\1!\21/

  # Match -@[^_]_
  s/!(.*)-@([^ ]) /\1\2!@ /

  # If there were any matches, branch to `:`
  t

  # Match _!@ and 0
  s/ !@(.*)\n$/\n!@\1#/

  # Match -@ and 0
  s/!(.*-)@(.*)\n$/\1\n!@\2#/

  # Match @_|_@ and 0
  s/!(.*)(@ | @)(.*)\n$/\1\n!@\3#/

  # Match -!.*[^-]@[^_]_ and 0
  s/-!(.*[^-])@([^ ]) (.*)\n$/\1\2\n!@\3#/

  # Match !.+@[^_] and 0
  s/!(.+)@([^ ].*)\n$/\n!@\1\2#/

  # Match marked line (#) or !@ and 0
  /#|!@.*\n$/{
    # Remove mark; append width and branch to `:`
    s/#|\n$//
    G
    b
  }

:Z

# Cleanup
s/-?!|@.*//g
s/ \n/\n/g

```

At the end of Phase 1, our pattern space looks like this:

> ```
> I remember a\ntime of cha-\nos, ruined\ndreams, this\nwasted land.
>
> ```

Or:

> ```
> I remember a
> time of cha-
> os, ruined
> dreams, this
> wasted land.
>
> ```

### Phase 2

In Phase 2 we use `%` as a cursor and use the counter in a similar way, beginning like this:

> ```
> %I remember a\ntime of cha-\nos, ruined\ndreams, this\nwasted land.\n111111111111$
>
> ```

First, we count the characters on the first line by advancing the cursor and removing 1s from the counter, after which we have;

> ```
> I remember a%\ntime of cha-\nos, ruined\ndreams, this\nwasted land.\n$
>
> ```

Since the counter is 0, we don't do anything else on this line. The second line also has the same number of characters as the counter, so let's skip to the third line:

> ```
> I remember a\ntime of cha-\nos, ruined%\ndreams, this\nwasted land.\n11$
>
> ```

The counter is greater than 0, so we move the cursor back to the beginning of the line. Then we find the first run of spaces and add a space, decrementing the counter.

> ```
> I remember a\ntime of cha-\nos, % ruined\ndreams, this\nwasted land.\n1$
>
> ```

The counter is greater than 0; since the cursor is already in the last (only) run of spaces on the line, we move it back to the beginning of the line and do it again:

> ```
> I remember a\ntime of cha-\nos,  % ruined\ndreams, this\nwasted land.\n$
>
> ```

Now the counter is 0, so we move the cursor to the beginning of the next line. We repeat this for every line except the last. That's the end of phase 2 and the end of the program! The final result is:

> ```
> I remember a
> time of cha-
> os,   ruined
> dreams, this
> wasted land.
>
> ```

```
# Phase 2
# Insert cursor
s/^/%/
:B
  # Append counter from hold space
  G
  # This is the last line; branch to :Q (end of phase 1)
  /%.*\n.+\n/!bQ

  :C
    # Count characters
    s/%([^\n])(.*)1$/\1%\2/
    tC

  # Move cursor to beginning of line
  s/([^\n]+)%\n/%\1\n/

  :D
    # Add one to each space on the line as long as counter is >0
    s/%([^ \n]* )(.*)1$/\1 %\2/
    tD

    # Counter is still >0; go back to beginning of line
    s/(^|\n)([^\n]+)%(.*1)$/\1%\2\3/
    tD

    # Counter is 0; move cursor to next line and branch to :B
    s/%([^\n]*)\n(.*)\n$/\1\n%\2/
    tB

:Q

# Remove cursor, any remaining 1s
s/%(.*)\n1*$/\1/

```
> 8 votes

# Answer
# JavaScript (ES6), 147 bytes

Takes input as `(width)(text)`.

```
w=>F=(s,p=S=' ')=>(g=([c,...b],o='',h=c=='-')=>c?o[w-1]?c==S&&o+`
`+F(b):o[w+~h]?o+c+`
`+F(b):c>S?g(b,h?o:o+c):g(b,o+p)||g(b,o+p+c):o)(s)||F(s,p+S)

```

Try it online!

### Commented

```
w =>                              // w = requested width
  F = (                           // F is a recursive function taking:
    s,                            //   s = either the input string (first iteration) or an
                                  //       array of remaining characters (next iterations)
    p =                           //   p = current space padding
    S = ' '                       //   S = space character
  ) => (                          //
    g = (                         // g is a recursive function taking:
      [c,                         //   c   = next character
          ...b],                  //   b[] = array of remaining characters
      o = '',                     //   o   = output for the current line
      h = c == '-'                //   h   = flag set if c is a hyphen
    ) =>                          //
      c ?                         // if c is defined:
        o[w - 1] ?                //   if the line is full:
          c == S &&               //     fail if c is not a space
          o + `\n` + F(b)         //     otherwise, append o + a linefeed and process the
                                  //     next line
        :                         //   else:
          o[w + ~h] ?             //     if this is the last character and c is a hyphen:
            o + c + `\n` + F(b)   //       append o + c + a linefeed and process the next
                                  //       line
          :                       //     else, we process the next character:
            c > S ?               //       if c is not a space:
              g(b, h ? o : o + c) //         append c if it's not a hyphen
            :                     //       else:
              g(b, o + p) ||      //         append either the current space padding
              g(b, o + p + c)     //         or the current padding and one extra space
      :                           // else:
        o                         //   success: return o
  )(s)                            // initial call to g() with s
  || F(s, p + S)                  // in case of failure, try again with a larger padding

```
> 8 votes

# Answer
# APL (Dyalog Unicode), ~~129 123 121 118 111 109 107 104 100~~ 95 bytesSBCS

```
{⊃⌽m←⍺≥-⌿c⍪+\⊢⌿c←' -'∘.≠⍵:⊂⍵/⍨⊢⌿c⋄(⊂∊l⊣l[(⍺-≢l)⍴⍸' '=l],←⊃0⍴l←⍵/⍨n×⊣⌿c⊖⍨1⌽n),⍺∇⍵/⍨~n←⌽∨\⌽m>×⌿c}

```

Try it online!
> 4 votes

# Answer
# Stax, ~~51~~ 50 bytes

```
éS┴k╖♀╡¶┐'▼jÆD╨◙♠ß╒└╧rî{♀EÜ╢a┌ùLiƒ7ÉøΩS╜╪åⁿM◙┴,○9H

```

Run and debug it
> 1 votes

# Answer
# Python 2, 343 bytes

```
W,T=input()
T+=' '
L,l=[],len
while T:
 p,r=0,''
 for i in range(l(T)):
  s=T[:i].replace('-','')
  if'-'==T[i]:s+='-'
  if T[i]in' -'and W-l(s)>=0:p,r=i,s
 R=r.split()
 if R:
  d,k=W-l(''.join(R)),0
  for j in range(d):
   R[k]+=' '
   k+=1
   if k==l(R)-1:k=0
  L+=[''.join(R)]
  T=T[p+1:]
print'\n'.join(L[:-1])
print' '.join(L[-1].split())

```

Try it online!

```
The  input  is a block of text
containing possibly hyphenated
words.  For  each space/hyphen
position  p  the code computes
l(p)  the  length  of the line
induced  by  slipping the text
to this space/hyphen. Then the
code choses the position p for
which  the  length l(p) is the
closest  to  the given width W
(and  l(p)<=W).  If l(p)<W the
code  adds spaces  fairly  in-
between  the  words to achieve
the length W.

```
> 1 votes

---
Tags: code-golf, typography
---