title: Crack the bank account's password!

text:
# Question
Title: Crack the bank account's password!
# Introduction

In order to prevent keyloggers from stealing a user's password, a certain bank account system has implemented the following security measure: only certain digits are prompted to be entered each time.

For example, say your target's password is `89097`, the system may prompt them to enter the 2nd, 4th and 5th digit:

`997`

Or it might prompt them to enter the 1st, 3rd and 5th digit:

`807`

All you know is that your target entered the digits in order, *but you don't know which position they belong to in the actual password*. All you know is there are two 9s, which must come before 7; and that 8 comes before 0, and 0 before 7. Therefore, there are six possible passwords:

```
80997
89097
89907
98097
98907
99807

```

The keylogger in your target's computer has been collecting password inputs for months now, so let's hack in!

# Challenge

Given a list of three-digit inputs, output all the possible passwords that are valid for all inputs. In order to reduce computational complexity and to keep the amount of possible results low, the password is guaranteed to be numerical and have a fixed size of 5. The digits in every input are in order: if it's 123, the target typed 1 first, then 2, then 3.

# Input/Output examples

```
|----------------------|--------------------------------------------|
|         Input        |                   Output                   |
|----------------------|--------------------------------------------|
| [320, 723, 730]      | [37230, 72320, 73203, 73230]               |
| [374, 842]           | [37842, 38742, 83742]                      |
| [010, 103, 301]      | [30103]                                    |
| [123, 124, 125, 235] | [12345, 12354, 12435]                      |
| [239, 944]           | [23944]                                    |
| [111, 120]           | [11201, 11120, 11210, 12011, 12110, 12101] |
| [456, 789]           | []                                         |
| [756, 586]           | [07586, 17586, 27586, 37586, 47586, 57586, 57856, 58756, 67586, 70586, 71586, 72586, 73586, 74586, 75086, 75186, 75286, 75386, 75486, 75586, 75686, 75786, 75806, 75816, 75826, 75836, 75846, 75856, 75860, 75861, 75862, 75863, 75864, 75865, 75866, 75867, 75868, 75869, 75876, 75886, 75896, 75986, 76586, 77586, 78586, 79586, 87586, 97586] |
| [123]                | [00123, 01023, 01123, 01203, 01213, 01223, 01230, 01231, 01232, 01233, 01234, 01235, 01236, 01237, 01238, 01239, 01243, 01253, 01263, 01273, 01283, 01293, 01323, 01423, 01523, 01623, 01723, 01823, 01923, 02123, 03123, 04123, 05123, 06123, 07123, 08123, 09123, 10023, 10123, 10203, 10213, 10223, 10230, 10231, 10232, 10233, 10234, 10235, 10236, 10237, 10238, 10239, 10243, 10253, 10263, 10273, 10283, 10293, 10323, 10423, 10523, 10623, 10723, 10823, 10923, 11023, 11123, 11203, 11213, 11223, 11230, 11231, 11232, 11233, 11234, 11235, 11236, 11237, 11238, 11239, 11243, 11253, 11263, 11273, 11283, 11293, 11323, 11423, 11523, 11623, 11723, 11823, 11923, 12003, 12013, 12023, 12030, 12031, 12032, 12033, 12034, 12035, 12036, 12037, 12038, 12039, 12043, 12053, 12063, 12073, 12083, 12093, 12103, 12113, 12123, 12130, 12131, 12132, 12133, 12134, 12135, 12136, 12137, 12138, 12139, 12143, 12153, 12163, 12173, 12183, 12193, 12203, 12213, 12223, 12230, 12231, 12232, 12233, 12234, 12235, 12236, 12237, 12238, 12239, 12243, 12253, 12263, 12273, 12283, 12293, 12300, 12301, 12302, 12303, 12304, 12305, 12306, 12307, 12308, 12309, 12310, 12311, 12312, 12313, 12314, 12315, 12316, 12317, 12318, 12319, 12320, 12321, 12322, 12323, 12324, 12325, 12326, 12327, 12328, 12329, 12330, 12331, 12332, 12333, 12334, 12335, 12336, 12337, 12338, 12339, 12340, 12341, 12342, 12343, 12344, 12345, 12346, 12347, 12348, 12349, 12350, 12351, 12352, 12353, 12354, 12355, 12356, 12357, 12358, 12359, 12360, 12361, 12362, 12363, 12364, 12365, 12366, 12367, 12368, 12369, 12370, 12371, 12372, 12373, 12374, 12375, 12376, 12377, 12378, 12379, 12380, 12381, 12382, 12383, 12384, 12385, 12386, 12387, 12388, 12389, 12390, 12391, 12392, 12393, 12394, 12395, 12396, 12397, 12398, 12399, 12403, 12413, 12423, 12430, 12431, 12432, 12433, 12434, 12435, 12436, 12437, 12438, 12439, 12443, 12453, 12463, 12473, 12483, 12493, 12503, 12513, 12523, 12530, 12531, 12532, 12533, 12534, 12535, 12536, 12537, 12538, 12539, 12543, 12553, 12563, 12573, 12583, 12593, 12603, 12613, 12623, 12630, 12631, 12632, 12633, 12634, 12635, 12636, 12637, 12638, 12639, 12643, 12653, 12663, 12673, 12683, 12693, 12703, 12713, 12723, 12730, 12731, 12732, 12733, 12734, 12735, 12736, 12737, 12738, 12739, 12743, 12753, 12763, 12773, 12783, 12793, 12803, 12813, 12823, 12830, 12831, 12832, 12833, 12834, 12835, 12836, 12837, 12838, 12839, 12843, 12853, 12863, 12873, 12883, 12893, 12903, 12913, 12923, 12930, 12931, 12932, 12933, 12934, 12935, 12936, 12937, 12938, 12939, 12943, 12953, 12963, 12973, 12983, 12993, 13023, 13123, 13203, 13213, 13223, 13230, 13231, 13232, 13233, 13234, 13235, 13236, 13237, 13238, 13239, 13243, 13253, 13263, 13273, 13283, 13293, 13323, 13423, 13523, 13623, 13723, 13823, 13923, 14023, 14123, 14203, 14213, 14223, 14230, 14231, 14232, 14233, 14234, 14235, 14236, 14237, 14238, 14239, 14243, 14253, 14263, 14273, 14283, 14293, 14323, 14423, 14523, 14623, 14723, 14823, 14923, 15023, 15123, 15203, 15213, 15223, 15230, 15231, 15232, 15233, 15234, 15235, 15236, 15237, 15238, 15239, 15243, 15253, 15263, 15273, 15283, 15293, 15323, 15423, 15523, 15623, 15723, 15823, 15923, 16023, 16123, 16203, 16213, 16223, 16230, 16231, 16232, 16233, 16234, 16235, 16236, 16237, 16238, 16239, 16243, 16253, 16263, 16273, 16283, 16293, 16323, 16423, 16523, 16623, 16723, 16823, 16923, 17023, 17123, 17203, 17213, 17223, 17230, 17231, 17232, 17233, 17234, 17235, 17236, 17237, 17238, 17239, 17243, 17253, 17263, 17273, 17283, 17293, 17323, 17423, 17523, 17623, 17723, 17823, 17923, 18023, 18123, 18203, 18213, 18223, 18230, 18231, 18232, 18233, 18234, 18235, 18236, 18237, 18238, 18239, 18243, 18253, 18263, 18273, 18283, 18293, 18323, 18423, 18523, 18623, 18723, 18823, 18923, 19023, 19123, 19203, 19213, 19223, 19230, 19231, 19232, 19233, 19234, 19235, 19236, 19237, 19238, 19239, 19243, 19253, 19263, 19273, 19283, 19293, 19323, 19423, 19523, 19623, 19723, 19823, 19923, 20123, 21023, 21123, 21203, 21213, 21223, 21230, 21231, 21232, 21233, 21234, 21235, 21236, 21237, 21238, 21239, 21243, 21253, 21263, 21273, 21283, 21293, 21323, 21423, 21523, 21623, 21723, 21823, 21923, 22123, 23123, 24123, 25123, 26123, 27123, 28123, 29123, 30123, 31023, 31123, 31203, 31213, 31223, 31230, 31231, 31232, 31233, 31234, 31235, 31236, 31237, 31238, 31239, 31243, 31253, 31263, 31273, 31283, 31293, 31323, 31423, 31523, 31623, 31723, 31823, 31923, 32123, 33123, 34123, 35123, 36123, 37123, 38123, 39123, 40123, 41023, 41123, 41203, 41213, 41223, 41230, 41231, 41232, 41233, 41234, 41235, 41236, 41237, 41238, 41239, 41243, 41253, 41263, 41273, 41283, 41293, 41323, 41423, 41523, 41623, 41723, 41823, 41923, 42123, 43123, 44123, 45123, 46123, 47123, 48123, 49123, 50123, 51023, 51123, 51203, 51213, 51223, 51230, 51231, 51232, 51233, 51234, 51235, 51236, 51237, 51238, 51239, 51243, 51253, 51263, 51273, 51283, 51293, 51323, 51423, 51523, 51623, 51723, 51823, 51923, 52123, 53123, 54123, 55123, 56123, 57123, 58123, 59123, 60123, 61023, 61123, 61203, 61213, 61223, 61230, 61231, 61232, 61233, 61234, 61235, 61236, 61237, 61238, 61239, 61243, 61253, 61263, 61273, 61283, 61293, 61323, 61423, 61523, 61623, 61723, 61823, 61923, 62123, 63123, 64123, 65123, 66123, 67123, 68123, 69123, 70123, 71023, 71123, 71203, 71213, 71223, 71230, 71231, 71232, 71233, 71234, 71235, 71236, 71237, 71238, 71239, 71243, 71253, 71263, 71273, 71283, 71293, 71323, 71423, 71523, 71623, 71723, 71823, 71923, 72123, 73123, 74123, 75123, 76123, 77123, 78123, 79123, 80123, 81023, 81123, 81203, 81213, 81223, 81230, 81231, 81232, 81233, 81234, 81235, 81236, 81237, 81238, 81239, 81243, 81253, 81263, 81273, 81283, 81293, 81323, 81423, 81523, 81623, 81723, 81823, 81923, 82123, 83123, 84123, 85123, 86123, 87123, 88123, 89123, 90123, 91023, 91123, 91203, 91213, 91223, 91230, 91231, 91232, 91233, 91234, 91235, 91236, 91237, 91238, 91239, 91243, 91253, 91263, 91273, 91283, 91293, 91323, 91423, 91523, 91623, 91723, 91823, 91923, 92123, 93123, 94123, 95123, 96123, 97123, 98123, 99123] |
|----------------------|--------------------------------------------|

```

---

# Rules

* Input is guaranteed non-empty.
* Leading and trailing zeros matter: `01234` is different from `12340`, and `1234` doesn't crack either password. Think of how real passwords work!
* Standard I/O rules apply.
* No standard loopholes.
* This is , so the shortest answer in bytes wins. Non-codegolfing languages are welcome!

# Answer
# Python, 100 bytes

```
lambda e,d='%05d':[d%i for i in range(10**5)if all(re.search('.*'.join(x),d%i)for x in e)]
import re

```

Try it online!

Works in Python 2 as well as Python 3.

(**97 bytes** in Python 3.8:)

```
lambda e:[p for i in range(10**5)if all(re.search('.*'.join(x),p:='%05d'%i)for x in e)]
import re

```
> 25 votes

# Answer
# 05AB1E, ~~11~~ 9 bytes

```
žh5ãʒæIåP

```

Try it online!

**Explanation**

```
žh          # push 0123456789
  5ã        # 5 times cartesian product
    ʒ       # filter, keep only values are true under:
     æ      # powerset of value
      Iå    # check if each of the input values are in this list
        P   # product

```
> 23 votes

# Answer
# JavaScript (ES6), 88 bytes

Prints the results with `alert()`.

```
a=>{for(k=n=1e5;n--;)a.every(x=>(s=([k]+n).slice(-5)).match([...x].join`.*`))&&alert(s)}

```

Try it online!

### Commented

```
a => {                    // a[] = input array of 3-character strings
  for(k = n = 1e5; n--;)  // initialize k to 100000; for n = 99999 to 0:
    a.every(x =>          // for each string x = 'XYZ' in a[]:
      ( s =               //   define s as the concatenation of
          ([k] + n)       //   '100000' and n; e.g. '100000' + 1337 -> '1000001337'
          .slice(-5)      //   keep the last 5 digits; e.g. '01337'
      ).match(            //   test whether this string is matching
        [...x].join`.*`   //   the pattern /X.*Y.*Z/
      )                   //
    ) &&                  // end of every(); if all tests were successful:
      alert(s)            //   output s
}                         //

```
> 12 votes

# Answer
## Haskell, ~~81~~ ~~80~~ ~~78~~ 76 bytes

```
f x=[p|p<-mapM(:['1'..'9'])"00000",all(`elem`(concat.words<$>mapM(:" ")p))x]

```

The obvious brute force approach in Haskell: built a list of all possible passwords and keep those where all elements from the input list are in respective list of subsequences.

Try it online!

Edit: -1 byte thanks to @xnor, ~~-2~~ -4 bytes thanks to @H.PWiz
> 8 votes

# Answer
# Python 2, 96 bytes

```
l=input()
n=1e5
while n:
 n-=1;s='%05d'%n;t={''}
 for c in s:t|={x+c for x in t}
 if l<t:print s

```

Try it online!

Takes input as a set of strings.

---

# Python 3, 98 bytes

```
f=lambda l,s='':any(l)or print(s)if s[4:]else[f([x[x[:1]==c:]for x in l],s+c)for c in'0123456789']

```

Try it online!

Recursively tries building every five-digit number string in `s`, tracking the subsequences in `l` still remaining to be hit. If all are empty by the end, prints the result.
> 7 votes

# Answer
# Ruby, 54 bytes

```
->a{(?0*5..?9*5).select{|x|a.all?{|y|x=~/#{y*'.*'}/}}}

```

Try it online!

Takes input as an arrray of character arrays.
> 6 votes

# Answer
# Pyth, 11 bytes

```
f<QyT^s`MT5

```

Takes input as a set of strings.
Try it here

### Explanation

```
f<QyT^s`MT5
      s`MT      Take the digits as a string.
     ^    5     Take the Cartesian product with itself 5 times.
f   T           Filter the ones...
 <Qy            ... where the input is a subset of the power set.

```
> 5 votes

# Answer
# , ~~80~~ 81 bytes

```
Reduce(intersect,lapply(gsub("",".*",scan(,"")),grep,substr(1e6:199999,2,6),v=T))

```

Try it online!

Here’s a base R solution using regex. Writing this nested series of functions made me realise how much I’ve learned to appreciate the magrittr package!

Initially hadn’t read rules on input, so now reads from stdin (thanks @KirillL).

Thanks to @RobinRyder for saving a byte!

Try it online!
> 5 votes

# Answer
# Jelly, 11 bytes

```
9Żṗ5ŒPiⱮẠɗƇ

```

Try it online!
> 4 votes

# Answer
# Perl 5 `-MList::Util=all -a`, 70 bytes

```
map{$t=sprintf'%05d',$_;(all{$t=~/$_/}map s//.*/gr,@F)&&say$t}0..99999

```

Try it online!

### Old Approach: Perl 5 `-a`, ~~80~~ 77 bytes

*Credit to @NahuelFouilleul for -2 bytes*

```
map{s||($t=0)x(5-y///c)|e;for$b(map s//.*/gr,@F){$t+=/$b/}$t-@F||say}0..99999

```

Try it online!
> 4 votes

# Answer
# Retina, 53 bytes

```
~(`
.$*
m`^
G`
^
K`¶5+%`$$¶0"1"2"3"4"5"6"7"8"9¶
"
$$"

```

Try it online! Explanation:

```
~(`

```

After executing the script, take the result as a new script, and execute that, too.

```
.$*

```

Insert `.*` everywhere. This results in `.*3.*2.*0.*` although we only need `3.*2.*0`, not that it matters.

```
m`^
G`

```

Insert a `G`` at the start of each line. This turns it into a Retina Grep command.

```
^
K`¶5+%`$$¶0"1"2"3"4"5"6"7"8"9¶
"
$$"

```

Prefix two more Retina commands. The resulting script will therefore look something like this:

```
K`

```

Clear the buffer (which contains the original input).

```
5+

```

Repeat 5 times...

```
%`$

```

... append to each line...

```
0$"1$"2$"3$"4$"5$"6$"7$"8$"9

```

... the digit `0`, then a copy of the line, then the digit `1`, etc. until `9`. This means that after `n` loops you will have all `n`-digit numbers.

```
G`.*3.*2.*0.*
G`.*7.*2.*3.*
G`.*7.*3.*0.*

```

Filter out the possible numbers based on the input.
> 4 votes

# Answer
# Ruby, ~~79~~ 77 bytes

```
->x{(0...1e5).map{|i|'%05d'%i}.select{|i|x.all?{|c|i=~/#{c.gsub('','.*')}/}}}

```

Try it online!

Input is an array of strings.

Here's a more readable version of the same code:

```
def f(codes)
  (0...10**5).map{|i| '%05d'%i}.select do |i|
    codes.all? do |code|
      i =~ Regexp.new(code.chars.join('.*'))
    end
  end
end

```
> 2 votes

# Answer
# , 52 bytes

```
(>,{;^:4~i.10)([#~]*/@e."2((#~3=+/"1)#:i.32)#"_ 1[)]

```

Try it online!
> 2 votes

# Answer
# PHP 128 bytes

```
for(;$i++<1e5;$k>$argc||print$s)for($k=0;$n=$argv[++$k];)preg_match("/$n[0].*$n[1].*$n[2]/",$s=sprintf("%05d
",$i-1))||$k=$argc;

```

or

```
for(;$i<1e5;$i+=$k<$argc||print$s)for($k=0;$n=$argv[++$k];)if(!preg_match("/$n[0].*$n[1].*$n[2]/",$s=sprintf("%05d
",$i)))break;

```

take input from command line arguments. Run with `-nr` or try them online.
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 116 bytes

```
x=>{for(int i=0;i<1e5;){var s=$"{i++:D5}";if(x.All(t=>t.Aggregate(-6,(a,c)=>s.IndexOf(c,a<0?a+6:a+1))>0))Print(s);}}

```

Try it online!

```
// x: input list of strings
x=>{
  // generate all numbers under 100k
  for(int i=0;i<1e5;){
    // convert the current number to
    // a 5 digit string padded with 0's
    var s=$"{i++:D5}";
    // test all inputs against the 5 digit
    // string using an aggregate.
    // each step of the aggregate gets
    // the index of the next occurrence
    // of the current character starting
    // at the previously found character.
    // a negative index indicates error.
    if(x.All(t=>t
             .Aggregate(-6,(a,c)=>
               s.IndexOf(c,a<0?a+6:a+1)
             )>0))
      // output to STDOUT
      Print(s);
  }
}

```

**EDIT:** fixed a bug where the same character was counted more than once. For example, if `000` was logged, the function used to return all passwords containing a single `0`.
> 2 votes

# Answer
# Japt, 21 bytes

```
1e5o ù'0 f@e_XèZË+".*

```

Try it!

```
1e5o ù'0 f@e_XèZË+".*    # full program

1e5o                     # generate numbers under 100k
     ù'0                 # left pad with 0's
         f@              # filter array
           e_            # check every element of input array
             Xè          # X is the number to be tested.
                         # test it against a regex.
               ZË+".*    # the regex is an element from the input array
                         # with wildcards injected between each character

```

-2 bytes thanks to @Shaggy!
> 2 votes

# Answer
# Clean, 113 bytes

```
import StdEnv,Data.List
$l=[s\\s<-iter 5(\p=[[c:e]\\e<-p,c<-['0'..'9']])[[]]|all(flip any(subsequences s)o(==))l]

```

Try it online!
> 1 votes

# Answer
## K 67 bytes

```
{n@&{&/y in\:x@/:&:'a@&3=+/'a:(5#2)\:'!32}[;x]'n:{"0"^-5$$x}'!_1e5}

```

K has a (very) primitive regex capability, so i tried a different approach.

{...} defines a lambda. Use example: `{...}("320";"723";"730")`

returns `("37230";"72320";"73203";"73230")`

* `n` is the list of integers in range 0..9999 as 0-padded strings

+ `_1e5` applies floor to float 1e5 (scientific notation) -\> generates integer 100000
    + `!_1e5` generates integer-list 0..99999
    + `{..}'!_1e5` applies lambda to each value in 0..99999
    + `$x` transform argument x (implicit arg) to string
    + `-5$$x` right adjust string $x to a field of size 5 (ex. `-5$$12` generates `" 12"`
    + `"0"^string` replaces blanks with "0" char, so `"0"^-5$$12` generates `"00012"`
* `a` is the list of integers in the range 0..31 as 5-bit values

+ `!32` generate values 0..31
    + `(5#2)` repeat 2 five times (list 2 2 2 2 2)
    + `(5#2)\:'!32` generates 5-bit values (2-base five-times) for each value in range 0..31
* we filter the values of a with exactly 3 ones. That values are all the combinations (places) where pattern can be located: `11100 11010 11001 10110 10101 10011 01110 01101 01011 00111`. Ex. for "abc" pattern we have equivalence with regexs `abc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?`

+ `+\'a` calculates sum of each binary representation (number of ones)
    + `3=+\'a` generates list of booleans (if each value in a has exactly 3 ones)
    + `a@&3=+\'a` reads as "a at where 3=+\\'a is true"
* generate list of indexes for previous places: `(0 1 2; 0 1 3; 0 1 4; 0 2 3; 0 2 4; 0 3 4; 1 2 3; 1 2 4; 1 3 4; 2 3 4)` and the possible entered-values for a password (x)

+ `&:'` reads as "where each", applies to list of binary-coded integers, and calculates indexes of each 1-bit
    + `x@/:` applies password x to each elem of the list of indexes (generates all possible entered values)
* Determines if all patterns are located in the list of all possible entered values

+ `y` is the arg that represent list of patterns
    + `y in\:` reads as each value of y in the list at the right
    + `&/` is "and over". `&/y in\:..` returns true iff all patterns in y are locates at the list ..
* finally, return each string in n at every index that makes lambda true

+ `n@&{..}` reads as "n at where lambda {..} returns true"
> 1 votes

# Answer
# Bash \+ GNU utilities, ~~54~~ ~~53~~ 51 bytes

```
sed 's/./&.*/g;s/ \|^/|grep /g;s//seq -w 0 99999/e'

```

Try it online!

*Thanks to @user41805 for 1 byte off, and now an additional 2 bytes off.*

Input: Space-separated integers on stdin.

Output: On stdout, one possible password per line.
> 1 votes

# Answer
# Python 3.8 (pre-release), ~~119~~ 102 bytes

```
lambda l:['%05d'%n for n in range(10**5)if all(map(lambda x:''in[x:=x[x[:1]==c:]for c in'%05d'%n],l))]

```

Try it online!

This was based off of xnor's Python answer and @Bubbler helped me golf it by 17 bytes ;)
> 1 votes

# Answer
# Python 3.8, <sup>~~97~~</sup> 96 bytes

```
lambda l:[s for n in range(10**5)if(s:='%05d'%n,t:={''},[t:=t|{x+c for x in t}for c in s])!=t>l]

```

Try it online!

-1 byte thanks to @xnor.

# Python 2, 96 bytes

```
lambda l,d='%05d':[d%n for n in range(10**5)if reduce(lambda t,c:t|{x+c for x in t},d%n,{''})>l]

```

Try it online!

Alternative forms of xnor's Python 2 answer.
> 1 votes

# Answer
# C(GCC) ~~222~~ 214 bytes

-8 bytes ceilingcat

```
#define C(p)*f-p||++f;
#define I(x,y)x>9&&++y,x%=10;
a,b,c,d,e,g,**h,*f;z(int**H){for(a=0;g=a<10;){for(h=H;*h;g&=f>*h+++2){f=*h;C(a)C(b)C(c)C(d)C(e)}g&&printf("%d%d%d%d%d,",a,b,c,d,e);e++;I(e,d)I(d,c)I(c,b)I(b,a)}}

```

Try it online!

Calling code

```
int main() {
  int hint1[5] = {9,9,7,-1,-1};
  int hint2[5] = {8,0,7,-1,-1};
  int* hints[3] = {hint1,hint2,0};
  z(hints);
}

```

Output

```
80997,89097,89907,98097,98907,99807,

```
> 0 votes

# Answer
The function takes an array of strings as input and prints each possible code on separate lines.

# PHP, 122 bytes

```
function a($n){for(;$x++<1e5;){foreach($n as$a)if(!preg_match("/$a[0].*$a[1].*$a[2]/",$x))continue 2;printf("%05d
",$x);}}

```

Try it online!
> 0 votes

# Answer
# sed -E, ~~46~~ 44 bytes

```
s/./&.*/g;s/ |^/|grep /g;s//seq -w 0 99999/e

```

Try it online!

Input: Space-separated integers on stdin.

Output: On stdout, one possible password per line.

This is from my bash answer, which had 3 bytes off thanks to @user41805.
> 0 votes

---
Tags: code-golf
---


title: Cook me a character meal

text:
# Question
Title: Cook me a character meal
Chef Avillez is about to cook us some really nice meal. He is just waiting for us to give him some ingredients and to request a meal.

# Task

Given a list of ingredients (strings matching `/[a-z]+/`) and a requested meal (string matching `/[a-z][a-z ]*/`) output the integer amount of meals Chef Avillez can make.

## Algorithm

Each letter (`[a-z]`) in the ingredient list contributes with one character for the soon-to-be-cooked meals. Each portion of our requested meal costs as many of each character as there are in the request string, excluding spaces.

For example, if our requested meal is `"bacon"` and the ingredients are `"banana"` and `"coconut"`, the output is `1` because in `"bananacoconut"` there is only one `b`, and for each portion of `"bacon"` we need one `"b"`.

# Input

A list of ingredients in any reasonable format, like

* a list of strings
* a list of lists of characters
* a (whatever-you-please)-separated list of ingredients, in a single string

and a requested meal in any reasonable format, like

* a string
* a list of characters

# Output

A non-negative integer representing the amount of meals that can be cooked.

# Test cases

A Python reference implementation is available.

```
['spam', 'spam', 'spam', 'spam', 'bacon', 'eggs', 'eggs', 'bacon', 'spam'], 'beans' -> 2
['bacon', 'bacon', 'bacon', 'bacon', 'bacon'], 'bacon' -> 5
['banana', 'coconut'], 'bacon' -> 1
['acon', 'bcon', 'baon', 'bacn', 'baco'], 'bacon' -> 4
['tomato', 'oregano', 'pizza', 'chocolate'], 'bacon' -> 0
['strawberries', 'figs', 'chocolate', 'sardines'], 'cod fish' -> 1
['these', 'are', 'some', 'random', 'words', 'wow'], 'or' -> 3
['some', 'more', 'delicious', 'ingredients', 'here'], 'bolognese' -> 0
['some', 'delicious', 'ingredients', 'here', 'are', 'bliss'], 'bolognese' -> 1
['some', 'bountiful', 'bagful', 'of', 'ingredients', 'here', 'are', 'bliss'], 'bolognese' -> 1

```

# Answer
# Python 2, ~~95~~ ~~71~~ ~~70~~ 55 bytes

```
lambda i,m:min(i.count(c)/m.count(c)for c in m if" "<c)

```

Try it online!

**Input**: Ingredients `i` as a comma-separated string, and a meal `m` as a string.
**Output**: Max number of meals that can be made.

**How**: Divides the frequency of each character in the ingredient by its corresponding character in the meal, then takes the minimum.
> 10 votes

# Answer
# Ruby, ~~55~~ 50 bytes

Meal (m) is a list of characters, and Ingredients (i) is a single string with ingredients separated by spaces.

-5 bytes from Dingus.

```
->m,i{(m-[' ']).map{|c|i.count(c)/m.count(c)}.min}

```

Try it online!
> 8 votes

# Answer
# , 29 27 26 bytes

```
<./@(=/<.@%&(+/)]=/]);@cut

```

Try it online!

*-2 bytes thanks to Bubbler*

*-1 byte thanks to FrownyFrog*

Inspired by ValueInk's ruby answer -- be sure to upvote him.

Both args are strings. Meal is right arg. Ingredients are left arg and taken as space separated string.

Consider the example:

```
'banana coconut' f 'ba con'

```

`-.&' '` removes the spaces from the right arg:

```
'banana coconut' <./@(=/<.@%&(+/)]=/]) 'bacon'

```

Now the main verb is a fork whose tines are `=/` and `]=/]`. `]` is the right arg so that the right tine runs as `'bacon' =/ 'bacon'`:

```
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

```

And the left tine becomes `'banana coconut' =/ 'bacon'`:

```
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

```

Now take the rowwise sum `&(+/)` of each, which results in:

```
1 1 1 1 1  NB. right tine
1 3 2 2 3  NB. left tine

```

In the right tine (meal), the number at index `i` is the count of meal letter `i` within meal (all 1 in this example because the letters are unique).

In the left tine (ingredients), the number at index `i` is the count of meal letter `i` within ingredients.

We divide those elementwise `1 3 2 2 3 % 1 1 1 1 1` = `1 3 2 2 3`, rounding down `<.@` each element to handle fractional amounts (not relevant in this example).

Finally we take the min `<./@` of the whole result, which in this case is `1`. This reflects the constraint of having a single `b` in our ingredients, limiting the number of meals we can make to 1.
> 7 votes

# Answer
# JavaScript (ES6),  ~~59 ... 51~~  50 bytes

Takes input as `(ingredients)(meal)`, where *ingredients* is the list of ingredients as a comma-separated string and *meal* is a list of characters. All names are expected in upper case.

Returns *false* instead of 0.

```
s=>g=m=>m.every(c=>s<(s=s.replace(c))|++c)&&1+g(m)

```

Try it online!

### Commented

```
s =>                   // s = list of ingredients
  g = m =>             // g is a recursive function taking m[] = meal,
                       // as a list of characters
    m.every(c =>       // for each character c in m[]:
      s < (            //   test whether s is less than ...
        s =            //     ... the updated value of s where ...
          s.replace(c) //       ... the 1st occurrence of c is replaced with 'undefined'
      )                //   end of comparison (falsy if c was not found)
      | ++c            //   force a truthy result if c is a space
    ) &&               // end of every(); if successful:
      1 + g(m)         //   increment the final result and do a recursive call

```
> 5 votes

# Answer
# Java (JDK), 94 bytes

```
a->s->{var z=new int[91];for(var c:a)z[c]++;for(;;z[0]++)for(var c:s)if(z[c]--<1)return z[0];}

```

Try it online!

Both inputs are uppercase letters to save a byte. If not allowed, please tell me, I'll fix it and add the byte.

## Credits

* Kevin Cruijssen for tidying up the inputs
> 5 votes

# Answer
# 05AB1E, ~~10~~ 9 bytes

*-1 byte thanks to Kevin Cruijssen*

```
Jsθáδ¢`÷ß

```

Try it online! or validate all test cases.

Takes the ingredients as a list of strings, and the meal as a list of characters.

```
J                  # join each input
 sθ                # get the last input (meal)
   á               # keep only letters
    δ¢             # double-vectorized count occurences
      `            # dump to the stack
       ÷           # integer division
        ß          # minimum

```
> 3 votes

# Answer
# APL (Dyalog Extended), 15 bytes

```
⌊⌂dab⍛(⌊/⍧÷⊣⍧⊣)

```

Try it online!

A dyadic train which takes the meal as its left arg and space-separated ingredients as right arg. (Comma-separated ingredients should work equally well.)

### How it works

```
⌊⌂dab⍛(⌊/⍧÷⊣⍧⊣)  ⍝ Left: meal, Right: ingredients
 ⌂dab⍛(       )  ⍝ Remove all spaces from the meal
         ⍧       ⍝ Counts of each char of meal in the ingredients
          ÷      ⍝ Divided by
           ⊣⍧⊣   ⍝ Counts of each char of meal in the meal
       ⌊/        ⍝ Minimum
⌊                ⍝ Floor (the result of division might be fractional)

```

Without the space-handling requirement, the code would be **9 bytes**:

```
⌊/⍤⌊⍧÷⊣⍧⊣

```

Try it online!
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~54~~ ~~63~~ 60 bytes

```
s=>t=>t.Min(x=>x>32?s?.Count(c=>c==x)/t.Count(c=>c==x):null)

```

`Min` can calculate the minimum selectively if `int?` objects are used. To obtain such objects, I use the `?.` operator: `s` will never be `null`, but it casts `int` to `int?` for 1 byte anyway.

Try it online!
> 2 votes

# Answer
# Perl 5 `-nlF`, ~~54~~ ~~47~~ 39 bytes

*Shoutout to @Grimmy for helping me fix an issue with no net gain of bytes*

```
$_=<>;$j++while s/$F[$j%@F]//x;say$j/@F

```

Try it online!

First line of input is the recipe; second line contains the ingredients (doesn't matter how or if they're separated).
> 2 votes

# Answer
# Retina, 48 bytes

```

%O`.
L$`\G((.)\2*)(?=.*¶.*?(\1)+)?
$#3
N`
1G`

```

Try it online! Link includes test suite. Takes input as dish on the first line and space-separated ingredients on the second line but the test suite uses a more convenient comma separator. Explanation:

```

```

Delete spaces in the dish and ingredients.

```
%O`.

```

Separately sort the letters in the dish and ingredients.

```
L$`\G((.)\2*)(?=.*¶.*?(\1)+)?
$#3

```

For each distinct letter in the dish, count the number of times its appearance in the dish divides into its appearance in the ingredients.

```
N`

```

Sort the counts.

```
1G`

```

Take the minimum.
> 2 votes

# Answer
# Pyth, 16 bytes

```
hSmL//hQd/eQdsce

```

Try it online!

### Explanation

```
hSmL//hQd/eQdsce(Q)
                (Q)  : Implicit evaluated input
               e     : Get last element of input
              c      : Split string at spaces
             s       : Concatenate split strings
   L                 : Lambda with argument named d
       Q             : Evaluated input
      h              : Get first element of input
     /  d            : Count occurrences of d in first element of input
           Q         : Evaluated input
          e          : Get last element of input
         /  d        : Count occurrences of d in last element of input
    /                : Divided occurrences of d in first element of input by occurrences of d in last element of input
  m                  : Map the lambda over last element of input
 S                   : Sort the result of the map
h                    : Get the first element from result of sort

```
> 2 votes

# Answer
# C (gcc), ~~135~~ 133 bytes

Expects ingredients and request as command line arguments (the last one is the request). The return value of the program is the result.

```
l[128],n;char*a;main(c,v)char**v;{for(++v;c---2;)for(a=*v++;*a;++l[*a++]);for(a=*v,n=l[*a];*a;++a)n=*a-32&&l[*a]<n?l[*a]:n;return n;}

```
> 2 votes

# Answer
# Python 3, ~~117~~ \\$\cdots\\$ ~~103~~ 70 bytes

Saved a whopping 33 bytes thanks to Surculose Sputum!!!

```
f=lambda l,m:all(e in l and[l.remove(e)]for e in m if' '<e)and-~f(l,m)

```

Try it online!
> 1 votes

# Answer
# Japt, 17 bytes

```
kS £V¬èX zU¬èXÃrm

```

Try it
> 1 votes

# Answer
# Erlang (escript), 81 bytes

To fix the bug I had to switch to filtering.

```
f(I,M)->lists:min([length([X||X<-I,X==C])div length([X||X<-M,X==C])||C<-M,32<C]).

```

Try it online!

## Explanation

```
f(I,M)->       % Function with operands I and M
lists:min(     % Find the minimum of this list.
[length(       % Find the length of:
[X||X<-I,X==C] % I items only containing C
)div           % Integer-divided by
length(        % the length of
[X||X<-M,X==C] % M items only containing C
)||C<-M,       %Ｗｈｅｒｅ　ｔｈｅ　ｉｔｅｍ　ｉｓ　ｔａｋｅｎ　ｆｒｏｍ　Ｍ
32<C]          % and the current item is larger than the space
).

```
> 1 votes

# Answer
# JavaScript (V8), 136 bytes

```
(a,b)=>{b=b.filter(a=>" "!==a),c=-1,d=!1;do c++,d=!0,b.forEach(b=>-1==(i=a.indexOf(b))?d=!1:a.splice(i,1)),c=d?c:c--;while(d);return c};

```

## Input:

* Ingredients: array of characters
* Meal: array of characters

Original commented code (`a=ingredients, b=meal, c=meals, d=yes`):

```
f = (ingredients, meal) => { // es6 arrow function syntax
    meal = meal.filter(i => i !== ' '); // delete all the spaces
    meals = -1 // set number of meals to -1, since we'll be adding one later on
    yes = false // yes is whether there are any meals left to make
    do { // do...while instead of while so it runs at least once
        meals++; // increment meals
        yes = true; // yes there is a meal to make
        meal.forEach(v => { // es6 arrow function for each character of the meal
            return (i = ingredients.indexOf(v)) == -1 ? // ternary operator, set i to index of character in ingredients, then check if its -1
                yes = false // if it is we can't find the character, so we can't make a meal
                    : ingredients.splice(i, 1) // we take out the letter from the ingredients list
        });
        meals = // assign to meals
            yes ? // ternary operator, check if we made a meal
                meals : meals-- // if we didn't make a meal then decrement meals
    } while (yes) // repeat if we made a meal
    return meals; // return the number of meals
}

```

Methods mentioned:

Try it online!
> 1 votes

# Answer
# MS SQL Server 2017, 300 bytes

```
CREATE FUNCTION F(@ NVARCHAR(MAX),@R NVARCHAR(MAX))RETURNS
TABLE RETURN WITH A AS(SELECT LEFT(@R,1)C,STUFF(@R,1,1,'')R
UNION ALL SELECT LEFT(R,1),STUFF(R,1,1,'')FROM A
WHERE R!=''),B AS(SELECT(LEN(@)-LEN(REPLACE(@,C,'')))/COUNT(*)OVER(PARTITION BY C)R
FROM A WHERE C LIKE'[A-Z]')SELECT MIN(R)R FROM B;

```

Try it on db\<\>fiddle.
> 1 votes

# Answer
# Charcoal, 15 bytes

```
Ｉ⌊ＥΦη№βι÷№θι№ηι

```

Try it online! Link is to verbose version of code. Takes input as a space-separated list of ingredients on the first line and the dish on the second line. Explanation:

```
    η           Second input (dish)
   Φ            Filter over characters
     №          Count of
       ι        Current character
      β         In lowercase alphabet
  Ｅ             Map over characters
         №      Count of
           ι    Current character
          θ     In ingredients
        ÷       Integer divide by
            №   Count of
              ι Current character
             η  In dish
 ⌊              Take the minimum
Ｉ               Cast to string
                Implicitly print

```
> 0 votes

---
Tags: code-golf, string
---


# Question
Title: Triangular domino tiling of an almost regular hexagon
## Background

An **almost regular hexagon** is a hexagon where

* all of its internal angles are 120 degrees, and
* pairs of the opposite sides are parallel and have equal lengths (i.e. a zonogon).

The following is an example of an almost regular hexagon, with side lengths 2 (red), 4 (blue), and 3 (yellow).

A **triangular domino** is a domino made of two unit triangles. A **triangular domino tiling** is a tiling on a shape using triangular dominoes. The following is a possible triangular domino tiling of the above shape (each color represents an *orientation* of each triangular domino):

## Challenge

Given the lengths of the three sides of an almost regular hexagon, find the number of distinct triangular domino tilings. The three sides will be always positive integers.

## Alternative description

The second image shows that such a tiling can be viewed as an isometric view of stacked unit cubes. Now let's assign three directions to three axes in 3D:

* `x` = down-right / southeast / SE (blue edges in the first image)
* `y` = down-left / southwest / SW (red edges)
* `z` = up / north / N (yellow edges)

Then the stacked unit cubes can be represented as an `x`-by-`y` 2D array, whose items represent the height of the stack at that position. So the above challenge is equivalent to the following:

> Given three positive integers `x`, `y`, and `z`, find the number of `x`-by-`y` arrays whose elements are between 0 and `z` inclusive and all rows and columns are in decreasing order.

It happens that this is one definition of plane partition in the form of \\$ PL(x,y,z) \\$, and it has a closed-form formula:

$$ PL(x,y,z) = \prod\_{i=1}^x \prod\_{j=1}^y \prod\_{k=1}^z \frac{i+j+k-1}{i+j+k-2} $$

## Scoring and winning criterion

Standard rules apply. The shortest code in bytes wins.

Note that a submission is valid even if it suffers from integer overflows or floating-point inaccuracies, as long as the underlying algorithm is correct.

## Test cases

```
x,y,z => output
---------------
1,1,1 => 2
1,1,2 => 3
1,2,3 => 10
2,3,1 => 10 (the order of inputs doesn't matter, since it's the same hexagon)
2,3,4 => 490
3,4,2 => 490
3,3,5 => 14112

```

# Answer
> 14 votes
# APL (Dyalog Classic), 14 bytes

```
×/1+1÷1+∘,1⊥¨⍳

```

Try it online!

Uses 0 indexing with `⎕IO←0`.

### Explanation:

```
             ⍳     ⍝ Cartesian product of the ranges from 0 to n-1
          1⊥¨      ⍝ Sum of each element (using base 1)
         ,         ⍝ Flattened
        ∘          ⍝ Composed with
  1+1÷1+           ⍝ 1 + 1/(n+1)
×/                 ⍝ And reduced by multiplication

```

# Answer
> 8 votes
# Perl 6, ~~38~~ 30 bytes

```
{[*] map 1+1/(*+1),[X+] ^<<@_}

```

Try it online!

Based on the formula given in the question

### Explanation:

```
{                            }    # Anonymous code block
                        ^<<@_     # Map each input to the range 0 to n-1
                   [X+]           # Get the cross product of sums
     map          ,               # Map these to
         1+1/(*+1)                # 1+1/(n+1) = (n+2/n+1)
                                  # Which is the formula compensating for the 0 based range
 [*]                              # And reduce by multiplication

```

# Answer
> 5 votes
# Jelly, ~~9~~ 8 bytes

```
Œp§_2İ‘P

```

Try it online!

Uses the altered form of the closed form expression. Takes input as a list `[x,y,z]`.

```
Œp          Cartesian product of the list.
            (Each element, being an integer, is implicitly converted to a range.)
  §         Sum the items of each triplet,
   _2       subtract 2 from each sum,
     İ      take the reciprocal of each lowered sum,
      ‘     increment each reciprocal,
       P    and return the product of the increments reciprocals.

```

# Answer
> 5 votes
# K (ngn/k), ~~17~~ 15 bytes

```
%/*/'2 1+\:+/!:

```

Try it online!

last test fails because of an overflow

uses a 0-indexed version of the formula:

\\$PL(x,y,z)=\prod\_{i=0}^{x-1}\prod\_{j=0}^{y-1}\prod\_{k=0}^{z-1}\frac{i+j+k+2}{i+j+k+1}\\$

# Answer
> 5 votes
# Wolfram Language (Mathematica), 28 bytes

```
Array[1+1/(##-2)&,#,1,1##&]&

```

Try it online!

# Answer
> 5 votes
# Haskell, 44 bytes

```
foldr(\r k->k+k/(sum r-2))1.mapM(\n->[1..n])

```

Try it online!

Outputs floats. Thanks to @H.PWiz for 4 bytes using a fold.

# Answer
> 5 votes
# 05AB1E, ~~13~~ 11 bytes

```
L.«â€˜OÍz>P

```

Try it online or verify all test cases.

**Explanation:**

Uses the derived formula (inspired by *@JoKing*'s answers): $$PL(x,y,z) = \prod\_{i=1}^x \prod\_{j=1}^y \prod\_{k=1}^z \frac{1}{i+j+k-2}+1$$

```
L            # Map each value in the (implicit) input-list to an inner [1,v]-ranged list
 .«          # (Right-)reduce these lists by:
   â         #  Taking the cartesian product between two lists
    €˜       # Then flatten each inner list
      O      # Sum each inner list
       Í     # Decrease all by 2
        z    # Take 1/v for each value
         >   # Increase all by 1
          P  # And take the product of that
             # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Bash, 75

Inputs are passed as a comma-separated list.

```
e={1..${1//,/\}+\{1..}}
eval eval echo \\$\[1 *\\\($e-1\\\) /\\\($e-2\\\) ]

```

Try it online! The last test fails due to integer overflow.

# Answer
> 2 votes
# JavaScript (ES6),  ~~73 65~~  64 bytes

```
(x,y,z)=>(g=n=>!n||g(n-1)/(s=n%z-~(n/z%y)+n/z/y%x|0)*-~s)(x*y*z)

```

Try it online!

### Commented

```
(x, y, z) => (              // (x, y, z) = input
  g = n =>                  // g is a recursive function taking a counter n
    !n ||                   //   if n = 0, stop recursion and return 1
    g(n - 1) / (            //   otherwise, divide the result of a recursive call by:
      s =                   //     s defined as the sum of:
        n % z               //       k, 0-indexed: n mod z
        - ~(n / z % y)      //       j, 1-indexed: floor((n / z) mod y) + 1
        + n / z / y % x | 0 //       i, 0-indexed: floor((n / z / y) mod x)
    )                       //
    * -~s                   //   and multiply by s + 1
)(x * y * z)                // initial call to g with n = x * y * z

```

# Answer
> 2 votes
# , 25 bytes

-4 bytes thanks to Bubbler!

```
[:*/1+1%1+1#.&>[:,@{i.&.>

```

Try it online!

# , 29 bytes

```
[:*/[:(1+1%1++/)@>[:,@{<@i."0

```

Try it online!

A  port of @JoKing's APL answer (don't forget to upvote it), but twice as long. I'll try to golf it...

# Answer
> 2 votes
# , 18 bytes

```
*/@,@(1+%)1++/&i./

```

Try it online!

Takes `z` on its left and `x y` on the right.

Uses modified formula by Peter Taylor:

$$ \begin{align} \prod\_{i=1}^x \prod\_{j=1}^y \frac{i+j+z-1}{i+j-1} &= \prod\_{i=1}^x \prod\_{j=1}^y \left(1 + \frac{z}{i+j-1}\right) \\ &= \prod\_{i=0}^{x-1} \prod\_{j=0}^{y-1} \left(1 + \frac{z}{i+j+1}\right) \end{align} $$

### How it works

```
*/@,@(1+%)1++/&i./  NB. Left =: z, Right =: x y
                 /  NB. Reduce over x y...
              &i.   NB.   Apply range (n -> 0..n-1) to each item and
            +/      NB.   Outer product by addition
          1+        NB. Increment each, so that each cell has i+j+1
    @(1+%)          NB. Compute 1+z/(i+j+1) for each i and j
*/@,                NB. Flatten the matrix and compute the product

```

# Answer
> 1 votes
# Ruby, ~~85~~ 75 bytes

```
->x,y,z{w=->t{(0...x*y*z).map{|r|r%x+(r/=x)%y+r/y+t}.reduce &:*};w[2]/w[1]}

```

Try it online!

# Answer
> 1 votes
# Icon, ~~81, 78~~ 70 bytes

-8 bytes thanks to Peter Taylor

```
procedure f(x,y,z)
p:=1&p*:=(1+z/(seq()\x+seq()\y-1.))&\u
return p
end

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), ~~79~~ 62 bytes

Based on @galen-ivanov's answer.

-17 bytes thanks to Jo King and xnor.

```
lambda x,y,z,t=1:[t:=t+t*z/(i%x-~i//x)for i in range(x*y)][-1]

```

Try it online!

# Answer
> 0 votes
# Charcoal, 25 bytes

```
ＮθＮηＦＮＦηＦθ⊞υ⊕⁺λ⁺κιＩ÷Π⊕υΠυ

```

Try it online! Link is to verbose version of code. Explanation: Uses the 0-indexed version of the given formula.

```
ＮθＮηＦＮＦηＦθ

```

Input the three dimensions and loop over the implicit ranges.

```
⊞υ⊕⁺λ⁺κι

```

Take each incremented sum and save it in a list, thus flattening the Cartesian product.

```
Ｉ÷Π⊕υΠυ

```

Divide the product of the incremented list by the product of the list and cast to string for implicit print.

# Answer
> 0 votes
# Japt, 18 bytes

```
mo rï Ëc rÄ pJ ÄÃ×

```

Try it

input as array

```
mo rï               // cartesian product [0,n)
      Ëc            // flatten each triplet
         rÄ         // reduce with initial value of 1 ( -2 +3=>triplets 0 to 1
            pJ      // raised -1
               Ä    // +1
                Ã×  // reduce by multiplication

Implicit output, -m flag to run the program for each input

```

---
Tags: code-golf, combinatorics, tiling, dominoes
---


# Question
Title: Generating generating expressions for sequences
*(yes, "generating generating" in the title is correct :) )*

# Context

In middle (?) school we are taught about sequences and, in particular, we are taught about linear sequences where the `n`th term is generated with an expression of the form `an + b`, where `a` and `b` are some coefficients. In this challenge, we will deal with sequences generated by polynomials of arbitrary degree.

# Task

Given the first `m` terms of a sequence, find the coefficients of the polynomial of ***lowest*** degree that could have generated such a sequence.

A polynomial, and thus the generating expression you are looking for, is to be seen as a function \\$p(n)\\$ that takes `n` as an argument and returns

$$a\_0 + a\_1 n + a\_2 n^2 + a\_3 n^3 + \cdots + a\_k n^k$$

where \\$k \geq 0\\$ and \\$a\_i, 0 \leq i \leq k\\$ have to be found by you.

You will assume that the `m` terms you were given correspond to taking `n = 0`, `n = 1`, ..., `n = m-1` in the generating polynomial above.

## Examples

If I am given the sequence `[2, 2, 2]` then I realize this is a constant sequence and can be generated by a polynomial of degree `0`: `p(n) = 2`.

If I am given the sequence `[1, 2, 3]` then I realize this cannot come from a constant polynomial but it could come from a linear polynomial `p(n) = n + 1`, so that is what my output should be. Notice how

```
p(0) = 1
p(1) = 2
p(2) = 3    # and NOT p(1) = 1, p(2) = 2, p(3) = 3

```

# Input

Your input will be the first terms of a sequence, which you can take in any reasonable format/data type. A standard list is the most obvious choice.

You may assume the input sequence is composed of integers (positive, 0 and negative).

# Output

The coefficients of the polynomial of ***lowest*** degree that could have generated the input sequence. The output format can be in any sensible way, as long as the coefficients can be retrieved unambiguously from the output. For this, both the value of each coefficient and the degree of each coefficient are important. (e.g. if using a list, `[1, 0, 2]` is different from `[0, 1, 2]`).

You can assume the polynomial you are looking for has integer coefficients.

# Test cases

For these test cases, the input is a list with the first terms; the output is a list of coefficients where (0-based) indices represent the coefficients, so `[1, 2, 3]` represents `1 + 2x + 3x^2`.

```
[-2] -> [-2]
[0, 0] -> [0]
[2, 2, 2] -> [2]
[4, 4] -> [4]
[-3, 0] -> [-3, 3]
[0, 2, 4, 6] -> [0, 2]
[2, 6] -> [2, 4]
[3, 7] -> [3, 4]
[4, 8, 12, 16] -> [4, 4]
[-3, -1, 5, 15, 29] -> [-3, 0, 2]
[0, 1, 4, 9] -> [0, 0, 1]
[3, 2, 3, 6, 11] -> [3, -2, 1]
[3, 4, 13, 30, 55] -> [3, -3, 4]
[4, 12, 28, 52, 84] -> [4, 4, 4]
[2, 4, 12, 32, 70] -> [2, 1, 0, 1]
[3, 6, 21, 54] -> [3, -1, 3, 1]
[4, 2, 12, 52, 140] -> [4, -2, -3, 3]
[10, 20, 90, 280] -> [10, 0, 0, 10]
[-2, 8, 82, 352, 1022, 2368, 4738] -> [-2, 4, -1, 4, 3]
[4, 5, 32, 133, 380] -> [4, -2, 0, 2, 1]
[1, 0, 71, 646, 2877, 8996, 22675] -> [1, -1, 0, -3, 0, 3]
[4, 2, 60, 556, 2540, 8094, 20692] -> [4, -2, -1, 0, -2, 3]
[1, 2, -17, 100, 1517, 7966, 28027, 78128, 186265] -> [1, 3, -2, 4, -3, -2, 1]
[4, 5, 62, 733, 4160, 15869, 47290, 118997] -> [4, 3, -1, -3, 1, 0, 1]

```

Test cases generated with this code

---

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

# Answer
# JavaScript (ES7),  ~~193 ... 154~~  145 bytes

*Saved 9 bytes thanks to @Bubbler*

Returns \\$(a\_0,a\_1,...,a\_k)\\$ with some possible trailing zeros.

```
v=>v.map((_,i)=>(g=(i,m=v.map((n,y)=>v.map((_,x)=>x==i?n:y**x)))=>+m||m.reduce((s,[v],i)=>v*g(0,m.map(([,...r])=>r).filter(_=>i--))-s,0))(i)/g())

```

Try it online!

(removed the penultimate test case, which requires more precision than IEEE-754 provides)

### How?

We use Cramer's rule to solve a system of linear equations based on a square Vandermonde matrix:

1. Given an input vector of length \\$n\\$, we build a Vandermonde matrix \\$V\_n\\$ of size \\$n\times n\\$ with coefficients \\$\alpha\_i=i,0\le i \<n\\$:

$$Vn=\begin{pmatrix} 1&0&0&...&0\\ 1&1&1&...&1\\ 1&2&4&...&2^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&n-1&(n-1)^2&...&(n-1)^{n-1} \end{pmatrix}$$
2. Using Cramer's rule, the coefficient \\$a\_i\\$ of the polynomial is computed by taking the determinant of the matrix obtained by replacing the \\$i\\$-th column of \\$V\_n\\$ with the input vector, and dividing by the determinant of \\$V\_n\\$.

### Example for \\$(4,2,12,52,140)\\$

The constant coefficient \\$a\_0\\$ is given by:

$$a\_0=\begin{vmatrix} \color{blue}4&0&0&0&0\\ \color{blue}2&1&1&1&1\\ \color{blue}{12}&2&4&8&16\\ \color{blue}{52}&3&9&27&81\\ \color{blue}{140}&4&16&64&256 \end{vmatrix}/|V\_5|=\frac{1152}{288}=4$$

The coefficient \\$a\_1\\$ is given by:

$$a\_1=\begin{vmatrix} 1&\color{blue}4&0&0&0\\ 1&\color{blue}2&1&1&1\\ 1&\color{blue}{12}&4&8&16\\ 1&\color{blue}{52}&9&27&81\\ 1&\color{blue}{140}&16&64&256 \end{vmatrix}/|V\_5|=\frac{-576}{288}=-2$$

And so on.
> 8 votes

# Answer
# , ~~55~~ 52 bytes

-3 bytes thanks to Giuseppe.

```
round(solve(outer(n<-seq(a=u<-scan())-1,n,"^"))%*%u)

```

Try it online!

Outputs \\$(a\_0, a\_1,\ldots,)\\$ with possible trailing zeros.

Let \\$u\\$ be the output sequence, and \\$X\\$ be the \\$m\times m\\$ matrix such that \\$X\_{i,j}=i^j\\$ (0-indexed), i.e.

\\$ X=\begin{pmatrix} 1&0&0&\ldots&0\\ 1&1&1&\ldots&1\\ 1&2&4&\ldots&2^{m-1}\\ 1&3&9&\ldots&3^{m-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&m-1&(m-1)^2&\ldots&(m-1)^{m-1} \end{pmatrix}. \\$

Then in matrix notation, \\$u=Xa\\$, hence \\$a=X^{-1}u\\$.

The code implements this: `n` is the vector `(0, 1, ..., m-1)` where `m` is the length of `u`; this is used to construct `X = outer(n, n, "^")`. The function `solve` performs matrix inversion, and the `round` is there to avoid numerical errors.
> 6 votes

# Answer
# APL+WIN, 16 bytes

Index origin = 0

Prompts for input as a vector and outputs coefficients from a0 to an-1 where n is the length of the vector. The order of the polynomial can be obtained by summing the number of coefficients up to the last none zero coefficient:

```
0⍕n⌹m∘.*m←⍳⍴n←,⎕

```

Try it online! Courtesy of Dyalog Classic
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~50~~ ~~49~~ 37 bytes

Returns a polynomial.

Mathematica is so awesome `x+1` can be used as a variable in this context. `Apart` is a weird built-in that, quoting from the docs, seems to attempt to rewrite an expression as a sum of terms with minimal denominators, and also happens to expand polynomials (that are returned in a weird collapsed form by default) into something more sane.

```
Apart@InterpolatingPolynomial[#,x+1]&

```

Try it online!

# Sledgehammer, 8 bytes

(it will try to deceive you into thinking it's actually 7.5, but it's actually not)

```
⣕⢤⣏⠛⡪⣊⠵⢼

```

Explanation: It's `Apart@InterpolatingPolynomial[Input[], x+1]`, but compressed via an awesome Mathematica compressor (it is so awesome that, as far as I understand, it translates Mathematica to an intermediate stack-based language).

Unfortunately, running this is fairly painful.
> 4 votes

# Answer
# , 10 bytes

```
%.^/~@i.@#

```

Try it online!

Obligatory J answer on a matrix-related challenge. Takes input as a vector of extended integers (otherwise the answer may have small floating-point errors), and gives the polynomial's coefficients in lowest-first order, possibly with some extra zeroes at the end.

### How it works

```
%.^/~@i.@#  NB. Input: a vector V of extended integers.
         #  NB. Length of V
      i.@   NB. Generate 0..(len(V)-1)
  ^/~@      NB. Self outer product by ^(exponentiation)
%.          NB. Matrix-divide V by the matrix above,
            NB.   i.e. solve a linear system of equations

```
> 3 votes

# Answer
# Pari/GP, 38 bytes

```
a->Vecrev(polinterpolate([0..#a-1],a))

```

Try it online!
> 2 votes

# Answer
# Python 3 \+ Numpy, 69 bytes

```
lambda x:polyfit(range(len(x)),x,len(x)-1).round()
from numpy import*

```

Try it online!

May have leading zeros.
> 2 votes

# Answer
# Charcoal, ~~68~~ 62 bytes

```
≔⟦¹⟧ηＦＬθ«⊞υ⁰≔÷⁻§θιΣＥυ×κＸιλ∨ΠＥι⊕κ¹ζＵＭυ⁺κ×ζ§ηλ⊞η⁰≔Ｅη⁻§η⊖λ×κιη»Ｉυ

```

Try it online! Link is to verbose version of previous version of code that excludes trailing zeros, but apparently it isn't necessary to do that, thus saving 6 bytes. Outputs the terms in power order i.e. the constant term is printed first. Explanation:

```
≔⟦¹⟧η

```

Start by creating a helper polynomial \\$ h(x) = 1 \\$.

```
ＦＬθ«

```

Loop over the \\$ m \\$ terms.

```
⊞υ⁰

```

Add a \\$ 0x^i \\$ term to the result polynomial \\$ u(x) \\$.

```
≔÷⁻§θιΣＥυ×κＸιλ∨ΠＥι⊕κ¹ζ

```

Subtract the value of \\$ u(i) \\$ from the input term and divide that by \\$ i! \\$.

```
ＵＭυ⁺κ×ζ§ηλ

```

Multiply \\$ h \\$ by that value and add the result to \\$ u \\$. This doesn't change the values of \\$ u(0) ... u(i-1) \\$ but the value of \\$ u(i) \\$ is now the input term.

```
⊞η⁰≔Ｅη⁻§η⊖λ×κιη

```

Multiply \\$ h \\$ by \\$ x - i \\$.

```
»Ｉυ

```

Print the coefficients of \\$ u \\$, which may include trailing zeros.
> 2 votes

# Answer
# Haskell, 77 bytes

```
h%(a:t)=h-a:a%t
h%_=[h]
f(h:t)=h:foldr(%)[](f$zipWith((/).(-h+))t[1..])
f e=e

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), 10 bytesSBCS

```
⊢⌹∘.*⍨∘⍳∘≢

```

Try it online!

A port of Graham's APL+WIN solution into a modern APL, which happens to work exactly the same (and have the same byte count) as my own J solution.

### How it works

```
⊢⌹∘.*⍨∘⍳∘≢  ⍝ Input: V, result of a polynomial evaluated at 0..m-1
       ⍳∘≢  ⍝ Generate 0..m-1
  ∘.*⍨∘     ⍝ Self outer product by * (exponentiation)
⊢⌹          ⍝ Matrix divide V by above (solve linear system of equations)

```
> 2 votes

# Answer
# 05AB1E, ~~48~~ 47 bytes

```
g≠iā<DδmUεXøINǝ}Xšεā<sUœε©2.ÆíÆ.±Xε®Nèè}«P}O}ć÷

```

Sometimes 05AB1E's lack of almost all matrix builtins is pretty annoying.. ;)
Inspired by @Arnauld's JavaScript answer.

Try it online or verify almost all test cases (removed the last two largest ones, since they time out on TIO).

**Explanation:**

First handle the edge case of a single-element input-list (would cause issues with the `«` later on in the code):

```
g                # Get the length of the (implicit) input-list
 ≠i              # And if it is NOT 1, continue with:
                 #  ... (see below)
                 # (implicit else:)
                 #  (output the implicit input-list as implicit output)

```

Next we'll get the exponentiation matrix of the list `[0, input-length)`:

```
ā                #  Push a list in the range [1, (implicit) input-length] (without popping)
 <               #  Decrease each value by 1 to make the range [0, input-length)
  Dδ             #  Apply double-vectorized on itself by first duplicating:
    m            #   Take the power of the two values
     U           #  Pop and store this exponentiation matrix in variable `X`

```

Next we'll create a list of this matrix, with every column one by one replaced with the input-list:

```
ε     }          #  Map over the input-list that was still on the stack
 X               #   Push the exponentiation matrix from variable `X`
  ø              #   Zip/transpose it; swapping rows/columns
     ǝ           #   Replace the transposed row of the exponentiation matrix
    N            #   at the current map-index
   I             #   with the input-list

```

We'll prepend the original exponentiation matrix to this list:

```
Xš               #  Prepend the matrix `X` in front of this list

```

And we'll calculate the determinant of each inner matrix in this list:

```
ε              } #  Map over the list of matrices:
 ā               #   Push a list in the range [1, matrix-length] (without popping)
  <              #   Decrease it by 1 to make the range [0, matrix-length)
   sU            #   Swap to get the matrix again, and pop and store it in variable `X`
     œ           #   Get all permutations of the [0, matrix-length) list
      ε          #   Inner map over each permutation:
       ©         #    Store the current permutation in variable `®` (without popping)
        2.Æ      #    Get all 2-element combinations of this permutation
           í     #    Reverse each inner pair
            Æ    #    Reduce it by subtracting
             .±  #    And get it's signum (-1 if a<0; 0 if a==0; 1 if a>0)
       X         #    Push the matrix from variable `X`
        ε        #    Map over each of its rows:
         ®       #     Push the current permutation of variable `®`
          Nè     #     Get the value in the permutation at the current map-index
            è    #     And use that to index into the current matrix-row
        }«       #    After the map of rows: merge it together with the signum list
          P      #    And take the product of this entire list
      }O         #   After the map of permutations: sum all values

```

Now that we have all determinants of the matrices, we get the default one again to divide all others by it:

```
ć                #  Extract head: pop and push remainder-list and first item separated
 ÷               #  Integer-divide each value in the remainder-list by this head
                 #  (after which the result is output implicitly)

```
> 2 votes

# Answer
# SageMath, ~~63~~ 48 bytes

```
lambda v:QQ[x].lagrange_polynomial(enumerate(v))

```

Try it online!

Outputs the polynomial as

$$a\_k n^k + \cdots + a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0 $$
> 1 votes

# Answer
# MATL, 12 bytes

```
n:qGyz3$ZQYo

```

The result is given with higher-order coefficients first, and may contain leading zeros.

Try it online! Or verify all test cases

### Explanation

Consider input `[-3, -1, 5, 15, 29]` as an example.

```
n:q    % Implicit input. Number of elements. Range. Subtract 1, element-wise
       % STACK: [0, 1, 2, 3, 4]
G      % Push input again
       % STACK: [0, 1, 2, 3, 4], [-3, -1, 5, 15, 29]
yz     % Duplicate from below. Number of non-zero elements
       % STACK: [0, 1, 2, 3, 4], [-3, -1, 5, 15, 29], 4
3$ZQ   % Fit polynomial with inputs x, y, degree
       % STACK: [3.7536e-16, -3.1637e-15, 2.0000, -8.8363e-15, -3]
Yo     % Round, element-wise. Implicit display
       % STACK: [0, 0, 2, 0, -3]

```
> 1 votes

# Answer
# Jelly, 14 bytes

```
J’*þ`æ*-⁸æ×ær0

```

A monadic Link accepting a list of integers which yields a list of the exponents (floats and/or integers) with the lowest degree on the left of the same length as the input (with trailing zeros if need be).

**Try it online!**

### How?

```
J’*þ`æ*-⁸æ×ær0 - Link: list of integers, V
J              - range of length (V)
 ’             - decrement (vectorises)
    `          - use as both arguments of:
   þ           -   outer-product using:
  *            -     exponentiation
       -       - minus one
     æ*        - matrix-exponentiation (i.e. inverse)
        ⁸      - chain's left argument, V
         æ×    - matrix-multiplication
           ær0 - round to zero decimal places (vectorises)

```
> 0 votes

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


title: Convert Planck unit to SI metric

text:
# Question
Title: Convert Planck unit to SI metric
# Objective

Given a dimension of an SI unit, convert the Lorentz-Heaviside version of a Planck unit \\$1\\$ into SI metric.

# What is a Planck unit?

Planck units are a set of units of measurement. It defines five fundamental constants of the universe as dimensionless \\$1\\$.

# What is a dimension?

There are five types of fundamental dimension: `L`, `M`, `T`, `Q`, and `Θ` (U+0398; Greek Capital Letter Theta).

`L` stands for length and corresponds to SI unit m (meter).

`M` stands for mass and corresponds to SI unit kg (kilogram).

`T` stands for time and corresponds to SI unit s (second).

`Q` stands for electric charge and corresponds to SI unit C (Coulomb).

`Θ` stands for temperature and corresponds to SI unit K (Kelvin).

A dimension is a multiplicative combination of these. For example, SI unit V (volt) is same as kg·m²·C/s⁴ and thus corresponds to dimension `L²MQ/T⁴`.

# Planck to SI

\\$1\\$ as Planck unit can be converted to SI metric as follows:

$$ 1 = 5.72938×10^{−35} \space \[\text{m}\] = 6.13971×10^{−9} \space \[\text{kg}\] = 1.91112×10^{−43} \space \[\text{s}\] = 5.29082×10^{−19} \space \[\text{C}\] = 3.99674×10^{31} \space \[\text{K}\] $$

# Input and Output

A dimension is given as the input. Its type and format doesn't matter. In particular, it can be an size-5 array of signed integers, each integer representing the exponent of a fundamental dimension.

The Planck unit \\$1\\$ is to be converted to the SI unit that corresponds to the inputted dimension, and then outputted. The output type and format doesn't matter.

# Examples

Let's say the input format is a tuple of five integers, representing `L`, `M`, `T`, `Q`, and `Θ`, respectively.

For example, If the input is \\$(2,1,-1,-2,0)\\$, it corresponds to SI unit Ohm, and thus:

$$ 1 = \frac{(5.72938×10^{−35})^2 × (6.13971×10^{−9})}{(1.91112×10^{−43})×(5.29082×10^{−19})^2} \space \[\text{Ω}\] $$

So the output is approximately \\$376.730\\$.

For another example, if the input is \\$(-2,-1,3,0,1)\\$, it corresponds to SI unit K/W, and thus:

$$ 1 = \frac{(1.91112×10^{−43})^3 × (3.99674×10^{31})}{(5.72938×10^{−35})^2 × (6.13971×10^{−9})} \space \[\text{K/W}\] $$

So the output is approximately \\$1.38424×10^{−20}\\$.

Note that, if the input is \\$(0,0,0,0,0)\\$, the output must be \\$1\\$.

# Answer
> 3 votes
# 05AB1E, ~~31~~ 29 bytes

```
•¿NkˆSSÀ¯j5ÄΣDt₁ñµ•8ô6°/₃-*O°

```

Try it online!

-2 thanks to @Kevin Cruijssen

inspired by @xnor.

explanation:

```
•¿NkˆSSÀ¯j5ÄΣDt₁ñµ•8ô6°/₃- compressed list [-34.241893, -8.211853000000005, -42.718713, -18.276477999999997, -82.33983, -94.999995]
* multiply by the implicit input (e.g. [-68.48378600000001, -8.211852999999998, 42.718713, 36.552955999999995, 0.0])
O sum (e.g. 2.576029999999996)
° raise 10 to the power of that (e.g. 376.729821659)

```

# Old Solution, ~~36~~ ~~35~~ 34 bytes

```
"7Q/Gy"Ç₃-*O°•7“µ$₁$´*h$Ć²E•6ôImP*

```

-1 thanks to @Expired Data

Try it online!

explanation:

```
"7Q/Gy"Ç₃- compressed list [-40,-14,-48,-24,26]
* multiply (vectorize) with the implicit input - [-80, -14, 48, 48, 0]
O sum - 2
° 10^ - 100
•7“µ$₁$´*h$Ć²E• compressed number 572938613971191112529082399674
6ô split into groups of length 6 - [572938,613971,191112,529082,399674]
I push input to the stack, to get [2, 1, -1, -2, 0] [572938,613971,191112,529082,399674] 100
m power (vectorize) - [328257951844, 613971, 5.232533802168362e-6, 3.5723502030270884e-12, 1]
P product - 3.7672911312918473
* multiply - 376.72911312918473, and then implicitly output

```

# Answer
> 7 votes
# Python 3, <sup>~~118~~ \\$\cdots\\$ ~~85~~</sup> 80 bytes

Saved a whopping 29 bytes thanks to Surculose Sputum!!!
Saved 4 bytes thanks to Arnauld!!!
Saved 5 bytes thanks to xnor!!!

```
lambda a,b,c,d,e:399674e26**e/174539e29**a/162874e3**b/523253e37**c/189007e13**d

```

Try it online!

# Answer
> 5 votes
# Jelly,  ~~35~~  34 bytes

```
“~VHð¡ȷ‘I⁵*×“®ƬØʋ¥4ẋİ8nCaḌ’bȷ6¤*⁸P

```

A monadic Link accepting a list of the five exponents, `[L, M, T, Q, Θ]`, which yields a floating-point number.

**Try it online!**

### How?

```
“~VHð¡ȷ‘I⁵*×“®ƬØʋ¥4ẋİ8nCaḌ’bȷ6¤*⁸P - Link: list of numbers       [L, M, T, Q, Θ]
“~VHð¡ȷ‘                           - list of code-page indices   [126, 86, 72, 24, 0, 26]
        I                          - differences                 [-40,-14,-48,-24,26]
         ⁵                         - ten                         10
          *                        - exponentiate                [1e-40, 1e-14, 1e-48, 1e-24, 1e26]
                              ¤    - nilad followed by link(s) as a nilad:
            “®ƬØʋ¥4ẋİ8nCaḌ’        -   base 250 number           572938613971191112529082399674
                            ȷ6     -   10^6                      1000000
                           b       -   convert from base         [572938,613971,191112,529082,399674]
           ×                       - multiply (vectorises)       [5.72938e-35,6.13971e-09,1.91112e-43,5.29082e-19,3.99674e31]
                                ⁸  - chain's left argument       [L, M, T, Q, Θ]
                               *   - exponentiate                [5.72938e-35^L,6.13971e-09^M,1.91112e-43^T,5.29082e-19^Q,3.99674e31^Θ]
                                 P - product                     5.72938e-35^L×6.13971e-09^M×1.91112e-43^T×5.29082e-19^Q×3.99674e31^Θ

```

# Answer
> 5 votes
# Fortran (2008), 133 bytes

At least for this challenge there should be a Fortran solution.

Takes input as integer array.

```
real(real64)function h(I)
use iso_fortran_env
integer I(5)
h=product([572938d-40,613971d-14,191112d-48,529082d-24,399674d26]**I)
end

```

A slightly longer and less accurate function uses the logarithm (stolen from @xnor):

```
real(real64)function f(I)
use iso_fortran_env
integer I(5)
f=exp(sum([-7884487d-5,-1890850d-5,-9836347d-5,-42083140d-5,7276562d-5]*I))
end

```

# Answer
> 5 votes
## Frink, 76 bytes

```
f[a,b,z,d,e]:=l_P^a m_P^b(4π)^((a-b+z-e)/2)t_P^z(ℏ c epsilon0)^(d/2)T_P^e

```

Example usage:

```
f[2,1,-1,-2,0]
376.73031366686987155 m^2 s^-3 kg A^-2 (electric_resistance)
f[-2,-1,3,0,1]
1.3842382138391631282e-20 m^-2 s^3 kg^-1 K (thermal_resistance)

```

(As a bonus, it outputs a description of the unit of the result!)

Frink has the constants `plancklength`, `planckmass`, `plancktime`, and `plancktemperature` built in, with abbreviations `l_P`, `m_P`, `t_P`, and `T_P` respectively. Unfortunately, these are the Gaussian versions of the units, and the challenge specifies that we must use the Lorentz-Heaviside versions. This is a factor of \\$\sqrt{4\pi}\\$ conversion for each unit, which is consolidated into the `(4π)^((a-b+z-e)/2)` expression in the solution. (This expression is placed in the middle of the code to save a byte by letting us remove the space between `m_P^b` and `t_P^z`.)

Incidentally,  is exactly as long as `4pi` in UTF-8, so it doesn't actually save any bytes -- it just looks fancier. :P

Finally, Frink inexplicably lacks the built-in unit `planckcharge`, so we calculate the Lorentz-Heaviside version directly ourselves as `(ℏ c epsilon0)^(1/2)` (this time,  actually saves a byte over `hbar`!).

# Answer
> 3 votes
# Perl 5 `-pa`, ~~84~~ 80 bytes

*@Arnauld and I both realized that you can save bytes by removing the decimal points.*

```
$\=1;map$\*=$_**$F[$i++],572938E-40,6.13971E-9,191112E-48,529082E-24,399674E26}{

```

Try it online!

# Answer
> 3 votes
# dc, ~~85~~ ~~81~~ ~~78~~ ~~75~~ 70 bytes

```
16iFFk1F875AI15^*?^35C8BI18^*?^/9B5431E?^/3C1109I1E^*?^/1A3ADDIA^*?^/p

```

Try it online!

Or try a test suite that shows the sample cases listed in the challenge. (This is a bash script that runs the dc program on each test data set in turn.)

---

*Saved 4 bytes by removing the decimal points, thanks to @Arnauld.*

*Had to add 1 byte also though, because I had inadvertently omitted a digit in one of the constants.*

*Saved 3 more bytes by changing constants to hexadecimal.*

*Thanks to @Noodle9 for pointing out that using division instead of multiplication can shorten this. That, plus careful attention to how many significant digits were needed throughout, yielded a savings of 5 additional bytes.*

---

**Input on stdin, one number per line, in base 16, in the following order:**

```
Θ
L
M
T
Q

```

This is the OP's order except the last one there is moved to the first position instead.

(The challenge says, "A dimension is given as the input. Its type and format doesn't matter." Also, hexadecimal input won't make a difference in practice given the problem domain, because we're not going to have a dimensional exponent outside the range -9 to 9. And this is allowed anyway by "Yes, I/O in unary, binary, octal, decimal or hexadecimal should be acceptable by default", which got the required support of at least 5 net votes, and at least twice as many upvotes as downvotes -- in this case, 20 upvotes, 8 downvotes, and 12 net votes.)

**Output on stdout, in base 10 as usual, with *lots* of decimal places :) .**

---

**If you try this out,** note that when you enter negative numbers in dc, they're written with an initial `_` character instead of `-`, since `-` is reserved for the binary subtraction operator. And don't forget to put `Θ` first, and to enter them all in hexadecimal! (Output is still in decimal.)

# Answer
> 3 votes
# JavaScript (ES7),  ~~81~~  76 bytes

*Saved 5 bytes thanks to @Noodle9*

Seems like the direct formula is the shortest way... ¯\\\_(ツ)\_/¯

Takes input as 5 distinct arguments.

```
(a,b,c,d,e)=>399674e26**e/174539e29**a/162874e3**b/523253e37**c/189007e13**d

```

Try it online!

---

# JavaScript (ES7), 86 bytes

Using `reduce()` adds  ~~5~~  10 bytes.

Takes input as an array.

```
a=>a.reduce((p,c,i)=>p*([572938e8,613971e34,191112,529082e24,399674e74][i]/1e48)**c,1)

```

Try it online!

# Answer
> 2 votes
# Mathematica, 260 bytes

Using a different method than the OP's. In particular, Table 2 at https://en.wikipedia.org/wiki/Planck\_units#Definition

Many opportunities for cleanup (e.g., shrink name to `c`, saving 6 bytes), but seems pointless. Newlines and indenting are inessential and are only present for presentation. Two spaces are required, at the end of the `BoltzmannConstant` line and at the end of the `ElectricConstant` line.

```
convert=Function[{L,M,T,Q,t},
  N[UnitConvert[
    Quantity["BoltzmannConstant"]^-t
      Sqrt[
        (4Pi)^(L-M+T-t)
        Quantity["SpeedOfLight"]^(-3L+M-5T+Q+5t)
        Quantity["ElectricConstant"]^Q
        Quantity["GravitationalConstant"]^(L-M+T-t)
        Quantity["ReducedPlanckConstant"]^(L+M+T+Q+t)
      ]
  ],6]
]

```

Checking:

```
convert[2, 1, -1, -2, 0]
(*  376.730 kg m^2/(s^3A^2)  *)
(*  FullForm: Quantity[376.730, ("Kilograms" ("Meters")^2)/(("Amperes")^2 ("Seconds")^3)]  *)

convert[-2, -1, 3, 0, 1]
(*  1.3842\[Times]10^-20 s^3K/(kg m^2)  *)
(*  FullForm: Quantity[1.3842\[Times]10^-20, ("Kelvins"*"Seconds"^3)/("Kilograms"*"Meters"^2)]  *)

convert[0, 0, 0, 0, 0]
(*  1.00000  *)

```

Notice that this code uses a curated source of consensus scientific values of the constants, and the output will change as those values change. Of relevance to the Challenge (and exemplified in the above samples), the gravitational constant is only 6.674 30(15) \*10^(-11) m^3 /(kg s^2), so is only known to four significant digits. This impacts the precision of length, mass, and time (except in combinations where this term cancels) in the Challenge, although the Challenge does not acknowledge this limitation of precision in those constants.

# Answer
> 2 votes
# PowerShell, ~~124~~ 101 bytes

*-23 bytes thanks to mazzy*

```
$t=1
$args|%{$t/=[math]::pow((174539e29,162874e3,523253e37,189007e13, 2502039161917e-44)[$i++],$_)}
$t

```

Try it online.

# Answer
> 1 votes
# Fortran (GFortran), ~~95~~ 90 bytes

```
READ*,I,J,K,L,M
PRINT*,399674D26**M/174539D29**I/162874D3**J/523253D37**K/189007D13**L
END

```

Try it online!

Input on stdin, output on stdout.

*Thanks to @Noodle9 for saving 5 bytes by pointing out that using division instead of multiplication can shorten this.*

# Answer
> 1 votes
# Java 8, 118 bytes

```
Math M=null;(a,b,c,d,e)->M.pow(399674e26,e)/M.pow(174539e29,a)/M.pow(162874e3,b)/M.pow(523253e37,c)/M.pow(189007e13,d)

```

Port of *@Noodle9*'s Python answer, so make sure to upvote him!!

Try it online.

# Answer
> 1 votes
# TI-83 Basic, 62 tokens

Using list operations:

```
prod({5.72938ᴇ−35,6.13971ᴇ−9,1.91112ᴇ−43,5.29082ᴇ−19,3.99674ᴇ31}^Ans

```

where

```
prod(                 Multiply all list elements together (1 token)
     { ... }          Constants in list (59 tokens)
            ^         Power using 2 lists as arguments (1 token)
             Ans      Input list stored in answer variable (1 token)

```

Example:

```
| {2,1,-1,-2,0}    | Give input
|    {2 1 -1 -2 0} |
| prgmPLANCK       | Run program
|      376.7291131 | Result

```

Second example unfortunately returns 0, because of insufficient precision on calculator.

---
Tags: code-golf, physics, floating-point
---


title: Counting Cunningham chains

text:
# Question
Title: Counting Cunningham chains
Prime numbers have always fascinated people. 2300 years ago Euclid wrote in his "Elements"

> A prime number is that which is measured by a unit alone.

which means that a prime is only divisible by `1` (or by itself).

People have always looked for relations between prime numbers, and have come up with some pretty weird (as in "interesting") stuff.

For example a **Sophie Germain prime** is a prime `p` for which `2*p+1` is also prime.

A **safe prime** is a prime `p` for which `(p-1)/2` is also prime, which is exactly the backwards condition of a Sophie Germain prime.

These are related to what we are looking for in this challenge.

A **Cunningham chain of type I** is a series of primes, where every element except the last one is a **Sophie Germain prime**, and every element except the first one is a **safe prime**. The number of elements in this *chain* is called it's **length**.

This means that we start with a prime `p` and calculate `q=2*p+1`. If `q` is prime too, we have a Cunnigham chain of type **I** of length 2. Then we test `2*q+1` and so on, until the next generated number is composite.

Cunningham chains of type **II** are constructed following almost the same principle, the only difference being that we check `2*p-1` at each stage.

Cunningham chains can have a *length of 1*, which means that neither 2\*p+1 nor 2\*p-1 are prime. **We're not interested in these**.

## Some examples of Cunningham chains

`2` starts a chain of type **I** of length 5.

`2, 5, 11, 23, 47`

The next constructed number would be `95` which isn't prime.
This also tells us, that `5`, `11`, `23` and `47` don't start any chain of type **I**, because it would have preceeding elements.

`2` also starts a chain of type **II** of length 3.

`2, 3, 5`

Next would be `9`, which isn't prime.

Let's try `11` for type **II** (we excluded it from *type I* earlier).
Well, `21` would be next, which isn't prime, so we would have length 1 for that "chain", which we don't count in this challenge.

## Challenge

> Write a program or function that, given a number `n` as input, writes/returns the starting number of the **nth** Cunningham chain of **type I or II** of **at least length 2**, followed by a space, followed by the type of chain it starts (**I** or **II**), followed by a colon, followed by the length of that type of chain. In case a prime starts both types of chains (type I *and* type II) the chain of type I is counted first.
>
> Example: `2 I:5`

Bear in mind, that `n` might be part of a previously started chain of any type, in which case it shouldn't be considered a *starting number* of a chain of that type.

## Let's look into how this begins

We start with `2`. Since it is the first prime at all we can be sure that there is no chain starting with a lower prime that contains `2`.
The next number in a chain of type I would be `2*2+1 == 5`. `5` is prime, so we have a chain of at least length 2 already.
We count that as the first chain. What about type II? Next number would be `2*2-1 == 3`. `3` is prime, so a chain of at least length 2 for type II too.
We count that as the second chain. And we're done for `2`.

Next prime is `3`. Here we should check if it is in a chain that a lower prime started.
Check for type I: `(3-1)/2 == 1`. `1` isn't prime, so 3 could be a starting point for a chain of type I.
Let's check that. Next would be `3*2+1 == 7`. `7` is prime, so we have a chain of type I of at least length 2. We count that as the third chain.
Now we check if `3` appears in a type II chain that a lower prime started. `(3+1)/2 == 2`. `2` is prime, so 3 can't be considered as a *starting number* for a chain of type II. So this is not counted, even if the next number after `3` in this chain, which would be `5`, is prime. (Of course we already knew that, and you can and should of course think about your own method how to do these checks.)

And so we check on for `5`, `7`, `11` and so on, counting until we find the nth Cunningham chain of at least length 2.

Then (or maybe some time earlier `;)` ) we need to determine the complete length of the chain we found and print the result in the previously mentioned format.

By the way: in my tests I haven't found any prime besides `2` that started both types of chains with a length greater than `1`.

## Input/Output examples

> ### Input
>
> `1`
>
> ### Output
>
> `2 I:5`

> ### Input
>
> `10`
>
> ### Output
>
> `79 II:3`

> ### Input
>
> `99`
>
> ### Output
>
> `2129 I:2`

### The outputs for the inputs 1..20

```
2 I:5
2 II:3
3 I:2
7 II:2
19 II:3
29 I:2
31 II:2
41 I:3
53 I:2
79 II:3
89 I:6
97 II:2
113 I:2
131 I:2
139 II:2
173 I:2
191 I:2
199 II:2
211 II:2
229 II:2

```

A list of the first 5000 outputs can be found here.

This is code golf. Arbitrary whitespace is allowed in the output, but the type and numbers should be seperated by a single space and a colon as seen in the examples. Using any loopholes is not allowed, especially getting the results from the web is **not** allowed.

Good luck `:)`

# Answer
> 2 votes
# Javascript, ~~236~~ 208 bytes

Saved 28 bytes:

```
p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

```

Saved 9 bytes on `p` function with: `p=(n,i=n)=>n%--i?p(n,i):i==1`
The `t` function was replaced by the `eval(...)` statement directly in the `f` function.

---

**Previous solution:**

```
p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

```

Example: `f(6)`

Output: `29 I:2`

**Explanation**
I'm using 3 functions

**1** *p*: to know if *n* is prime : `p=n=>{for(i=n;n%--i&&i;);return 1==i}`

**2** *t*: to know the length of the Cunningham chain starting with *n* of type I or II depending on the *m* parameter which will be 1 or -1 : `t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}`

**3** *f*: counts the chains (*for loop*) then display the result

```
f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

```

*for loop*: for each number the Cunningham chain (I then II if needed) is valid if

* the number is prime
* the predecessor is not prime
* the successor is prime

# Answer
> 0 votes
# Wolfram Language (Mathematica), 182 bytes

```
Union[Flatten[DeleteCases[Table[c@x_:=Module[{t=0,p=Prime@k},If[PrimeQ[(p-x)/2],1,While[PrimeQ@p,p=2p+x;t++];t]];{Prime@k,If[#==1,"I","II"],c@#},{k,7!}],{a_,b_,1}]&/@{1,-1},1]][[#]]&

```

Try it online!

---
Tags: code-golf, primes
---


title: Multiply with restricted operations

text:
# Question
Title: Multiply with restricted operations
> There's a 500 rep unofficial bounty for beating the current best answer.

**Goal**

Your goal is to multiply two numbers using only a very limited set of arithmetic operations and variable assignment.

1. Addition `x,y -> x+y`
2. Reciprocal `x -> 1/x` (*not* division `x,y -> x/y`)
3. Negation `x -> -x` (*not* subtraction `x,y -> x-y`, though you can do it as two operations `x + (-y)`)
4. The constant `1` (no other constants allowed, except as produced by operations from `1`)
5. Variable assignment `[variable] = [expression]`

**Scoring:** The values start in variables `a` and `b`. Your goal is to save their product `a*b` into the variable `c` using as few operations as possible. Each operation and assignment `+, -, /, =` costs a point (equivalently, each use of (1), (2), (3), or (4)). Constants `1` are free. The fewest-point solution wins. Tiebreak is earliest post.

**Allowance:** Your expression has to be arithmetically correct for "random" reals `a` and `b`. It can fail on a measure-zero subset of **R**2, i.e. a set that has no area if plotted in the `a`-`b` Cartesian plane. (This is likely to be needed due to reciprocals of expressions that might be `0` like `1/a`.)

**Grammar:**

This is an . No other operations may be used. In particular, this means no functions, conditionals, loops, or non-numerical data types. Here's a grammar for the allowed operations (possibilities are separated by `|`). A program is a sequence of `<statement>`s, where a `<statement>` is given as following.

```
<statement>: <variable> = <expr>
<variable>: a | b | c | [string of letters of your choice]
<expr>: <arith_expr> | <variable> | <constant>
<arith_expr>: <addition_expr> | <reciprocal_expr> | <negation_expr>
<addition_expr>: <expr> + <expr>
<reciprocal_expr>: 1/(<expr>)
<negation_expr>: -<expr>
<constant>: 1

```

You don't actually have to post code in this exact grammar, as long as it's clear what you're doing and your operation count is right. For example, you can write `a-b` for `a+(-b)` and count it as two operations, or define macros for brevity.

(There was a previous question Multiply without Multiply, but it allowed a much looser set of operations.)

# Answer
> 37 votes
## 22 operations

```
itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(itx + itx + 1/(1+nx)) + 1/(1/(a+nx) + 1/(b+nx)) ) #14

```

Try it online!

The ops are 10 additions, 7 inverses, 2 negations, and 3 assignments.

So, how did I get this? I started with the promising-looking template of the sum of two double-decker fractions, a motif that had appeared in many previous attempts.

```
c = 1/(1/x + 1/y)  +  1/(1/z + 1/w)

```

When we restrict the sum to `x+y+z+w=0`, a beautiful cancellations occur, giving:

```
c = (x+z)*(y+z)/(x+y)

```

which contains a product. (It's often easier to get `t*u/v` rather than `t*u` because the first has degree 1.)

There's a more symmetric way to think about this expression. With the restriction `x+y+z+w=0`, their values are specified by three parameters `p,q,r` of their pairwise sums.

```
 p = x+y
-p = z+w
 q = x+z
-q = y+w
 r = x+w
-r = y+z

```

and we have `c=-q*r/p`. The sum `p` is distinguished as being in the denominator by corresponding to the pairs `(x,y)` and `(z,w)` of variables that are in the same fraction.

This is a nice expression for `c` in `p,q,r`, but the double-decker fraction is in `x,y,z,w` so we must express the former in terms of the latter:

```
x = ( p + q + r)/2
y = ( p - q - r)/2
z = (-p + q - r)/2
w = (-p - q + r)/2

```

Now, we want to choose `p,q,r` so that `c=-q*r/p` equals `a*b`. One choice is:

```
p = -4
q = 2*a
r = 2*b

```

Then, the doubled values for `q` and `r` are conveniently halved in:

```
x = -2 + a + b
y = -2 - a - b
z =  2 + a - b
w =  2 - a + b

```

Saving `2` as a variable `t` and plugging these into the equation for `c` gives a 24-op solution.

```
#24 ops
t = 1+1   #2
c = 1/(1/(-t+a+b) + 1/-(t+a+b))  +  1/(1/(-b+t+a) + 1/(-a+b+t)) #1, 10, 1, 10

```

There's 12 additions, 6 inverses, 4 negations, and 2 assignments.

A lot of ops are spent expressing `x,y,z,w` in terms of `1,a,b`. To save ops, instead express `x` in `p,q,r` (and thus `a,b,1`) and then write `y,z,w` in terms of `x`.

```
y = -x + p
z = -x + q
w = -x + r

```

Choosing

```
p = 1
q = a
r = b

```

and expressing `c` with a negation as `c=-q*r/p`, we get

```
x = (1+a+b)/2
y = -x + 1
z = -x + a
w = -x + b

```

Unfortunately, halving in `x` is costly. It needs to be done by inverting, adding the result to itself, and inverting again. We also negate to produce `nx` for `-x`, since that's what `y,z,w` use. This gives us the 23-op solution:

```
#23 ops
itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(1/(-nx) + 1/(1+nx))  +  1/(1/(a+nx) + 1/(b+nx)) ) #15

```

`itx` is `1/(2*x)` and `nx` is `-x`. A final optimization of expressing `1/x` as `itx+itx` instead of the templated`1/(-nx)` cuts a character and brings the solution down to 22 ops.

# Answer
> 27 votes
# 23 operations

```
z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
res = z+z

```

proof by explosion:

```
z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
             1/(a+1)+1/(b+1)                            == (a+b+2) / (ab+a+b+1)
          1/(1/(a+1)+1/(b+1))                           == (ab+a+b+1) / (a+b+2)
          1/(1/(a+1)+1/(b+1))-1                         == (ab - 1) / (a+b+2)
          1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1)             == ab / (a+b+2)
       1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))            == (a+b+2) / ab
                                              1/a+1/b   == (a+b) / ab
       1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)  == 2 / ab
    1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)) == ab / 2

z = ab / 2 and therefore z+z = ab

```

I abused wolfram alpha to get this beautiful image (wolfram alpha tried to get me to subscribe to pro to save it, but then ctrl-c ctrl-v ;-)):

score (with added `+` on subtraction):

```
z = ////++/++-+/++++-/+/
res = +

```

# Answer
> 14 votes
# 29 operations

Does not work for the set \\$\\{(a,b) \in \mathbb{R}^2 : a\pm b=0 \text{ or } a\pm b = -1\\}\\$. That's probably measure zero?

```
sum = a+b
nb = -b
diff = a+nb
rfc = 1/(1/(1/sum + -1/(sum+1)) + -1/(1/diff + -1/(diff+1)) + nb + nb)  # rfc = 1/4c
c = 1/(rfc + rfc + rfc + rfc)

# sum  is  2: =+
# nb   is  2: =-
# diff is  2: =+
# rfc  is 18: =///+-/++-//+-/+++
# c    is  5: =/+++
# total = 29 operations

```

The structure of `rfc` (Reciprocal-Four-C) is more evident if we define a macro:

```
s(x) = 1/(1/x + -1/(x+1))              # //+-/+ (no = in count, macros don't exist)
rfc = 1/(s(sum) + - s(diff) + nb + nb) # =/s+-s++ (6+2*s = 18)

```

Let's do the math:

* `s(x)`, mathematically, is `1/(1/x - 1/(x+1))` which is after a bit of algebra is `x*(x+1)` or `x*x + x`.
* When you sub everything into `rfc`, it's really `1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))` which is just `1/((a+b)^2 - (a-b)^2)`.
* After difference of squares, or just plain expansion, you get that `rfc` is `1/(4*a*b)`.
* Finally, `c` is the reciprocal of 4 times `rfc`, so `1/(4/(4*a*b))` becomes `a*b`.

# Answer
> 10 votes
# 27 operations

```
tmp = 1/(1/(1+(-1/(1/(1+(-a))+1/(1+b))))+1/(1/(1/b+(-1/a))+1/(a+(-b))))
res = tmp+tmp+(-1)

# tmp is 23: =//+-//+-+/++///+-/+/+-
# res is 4: =++-

```

There is no theory behind this. I just tried to get `(const1+a*b)/const2` and started with `(1/(1-a)+1/(1+b))` and `(-1/a+1/b)`.

# Answer
> 4 votes
# 25 operations

```
two = 1+1
c = 1/(1/(a+b) + -1/(a+b+two)) + 1/(-1/a + 1/(a+two)) + 1/(-1/b + 1/(b+two))

```

Definitely not optimal, but probably optimal when restricted to only two levels of nested inversions (i.e. not using `1/(1/(1/...`). There *might* be ways to optimize this...

Uses the property

$$ \frac{1}{\frac{1}{x}-\frac{1}{x+2}} = \frac{x(x+2)}{2} = \frac{x^2}{2}+x $$

If we substitute \\$x\\$ with \\$a+b, a, b\\$ respectively:

$$ \begin{align} \frac{1}{\frac{1}{a+b}-\frac{1}{a+b+2}} &= \frac{(a+b)^2}{2}+(a+b) = \frac{a^2}{2} + ab + \frac{b^2}{2} + a + b \tag1 \\ \frac{1}{\frac{1}{a}-\frac{1}{a+2}} &= \frac{a^2}{2}+a \tag2 \\ \frac{1}{\frac{1}{b}-\frac{1}{b+2}} &= \frac{b^2}{2}+b \tag3 \\ \end{align} $$

We can easily see that \\$(1)-(2)-(3)\\$ conveniently gives \\$ab\\$.

Proof by Wolfram|Alpha:

```
> simplify c = 1/(1/(a+b) + -1/(a+b+2)) + 1/(-1/a + 1/(a+2)) + 1/(-1/b + 1/(b+2))
c = ab

```

---
Tags: math, restricted-source, arithmetic, atomic-code-golf
---


title: Multiplayer Rock-Paper-Scissors

text:
# Question
Title: Multiplayer Rock-Paper-Scissors
# Objective

Given a nonempty multiset of `Rock`, `Paper`, and `Scissors`, output the winning figure according to the special rule.

# Background

For a multiplayer RPS, if all three figures come out, usually it's considered a draw. But by that rule, the probability to draw would dramatically increase when there are many and many players.

Let's resolve that by a special rule.

# Input

Though defined as a multiset, the input type and format doesn't matter. Valid formats of the input include:

* A multiset
* A sequential container with or without guarantee of order
* An size-3 array of integers representing the count of each of RPS

Also, `Rock`, `Paper`, and `Scissors` may be encoded by an arbitrary type.

# The Special Rule and Output

Let's say \\$r\\$ `Rock`s, \\$p\\$ `Paper`s, and \\$s\\$ `Scissors`-es(?) are given.

* If one of them is zero, output the winning figure of the other two.
* If none of them is zero, allot them a score by multiplicating the number of themselves and the number of the figure they win to. That is, `Rock` gets score \\$r×s\\$, `Paper` gets score \\$p×r\\$, and `Scissors` get score \\$s×p\\$.

+ If the scores don't tie, output the figure with the maximum score.
    + If the scores tie by two figures, output the winning figure amongst the two figures.
    + Otherwise, output a fourth value indicating draw.
* Otherwise, output either the only figure or the fourth value.

The output type and format doesn't matter.

# Rule about code golf

Invalid inputs (Empty container, contains a fourth value, etc) fall into *don't care* situation.

# Example

Given the following input:

```
[Rock, Rock, Rock, Paper, Paper, Scissors, Scissors]

```

`Rock` gets score 3×2=6, `Paper` gets score 2×3=6, and `Scissors` get score 2×2=4. Since `Paper` wins to `Rock`, the output is `Paper`.

# Answer
> 3 votes
# 05AB1E, ~~14~~ 13 bytes

```
Ćü*ZÊ2βD3*7%M

```

Input as a list of integers in the order \\$\[r,s,p\]\\$.
Output as one of the following four:

```
Rock wins:      3
Scissors wins:  5
Paper wins:     6
Tie:            0

```

-1 byte thanks to *@xnor*.

Try it online or verify some more test cases.

**Explanation:**

```
Ć              # Enclose the (implicit) input-list, appending its own head
               #  i.e. input=[3,2,2] → STACK: [[3,2,2,3]
 ü             # For each overlapping pair: [a,b,c,d] → [[a,b],[b,c],[c,d]]
  *            #  Multiply them together
               #   STACK: [[6,4,6]]
   Z           # Get the maximum (without popping)
               #   STACK: [[6,4,6],6]
    Ê          # Check which of the values in the list are NOT equals to this maximum
               #  STACK: [[0,1,0]]
     2β        # Convert this list of 0s and 1s from a binary list to integer
               #  STACK: [2]
       D       # Duplicate it
               #  STACK: [2,2]
        3*     # Multiply it by 3
               #  STACK: [2,6]
          7%   # Take modulo-7:
               #  STACK: [2,6]
            M  # Push the largest value on the stack
               #  STACK: [2,6,6]
               # (after which the top of the stack is output implicitly as result)

```

After the `Ćü*ZÊ` we can have the following values:

```
                One of:
Rock wins:      [[0,1,1], [0,0,1]]
Scissors wins:  [[1,0,1], [1,0,0]]
Paper wins:     [[1,1,0], [0,1,0]]
Ties:           [[0,0,0]]

```

Converting those from binary-lists to integers:

```
                One of:
Rock wins:      [3, 1]
Scissors wins:  [5, 4]
Paper wins:     [6, 2]
Ties:           [0]

```

The `3*7%` (thanks to *@xnor*!) will map the lower values to the higher values in the pair, and will also unsure the lower values won't increase.

> This works because the pairs `[1,3], [2,6], [4,5]` are constructed from bits where the second number has two bits set: that of the first number, and the bit position to its right, wrapping around in 3 bits. This comes from the binary-list of the RPS game. We can do the set-next-bit with `*3` and enforce 3-bit wrapping with `%7`.

```
                One of:
Rock wins:      [3→2, 1→3]
Scissors wins:  [5→1, 4→5]
Paper wins:     [6→4, 2→6]
Ties:           [0]

```

After which we can use `M` to only keep the largest value on the stack for our result:

```
                One of:
Rock wins:      [3, 3]
Scissors wins:  [5, 5]
Paper wins:     [6, 6]
Ties:           [0]

```

# Answer
> 5 votes
# Python, 41 bytes

```
lambda r,s,p:[s>p<=r>0,p>r<=s>0,r>s<=p>0]

```

Try it online!

Takes counts as `(r,s,p)`. Outputs a three-element list with `True` at the position of the winner, or all `False`'s if there's a tie or only a single figure appearing.

```
Rock:     [True, False, False]
Scissors: [False, True, False]
Paper:    [False, False, True]
Tie:      [False, False, False]

```

We use an alternate characterization without multiplication (except when only one figure is present). Below is the condition for Rock winning, with Scissors and Paper having similar conditions.

> Rock wins if: Paper has the fewest, strictly fewer than Scissors but possibly the same as Rock.

We can write this in Python as `s>p<=r` using inequality chaining.

Unfortunately, this doesn't correctly handle the special case when `r=p=0`, saying that Rock wins even though only Scissors is present. To fix this, we strengthen the condition for Rock to win to include `r>0` via `s>p<=r>0`, which makes the only-Scissors case give all `False` for every condition, matching a tie.

---

**44 bytes**

```
lambda r,s,p:r*s==s*p==p*r or[s>p<=r,p>r<=s]

```

Try it online!

Takes counts as `(r,s,p)`. Outputs as:

```
Rock:     [True, False]
Scissors: [False, True]
Paper:    [False, False]
Tie:      True

```

The "Tie" case also includes where there's only a single figure present.

# Answer
> 2 votes
# C (gcc), <sup>~~61~~ \\$\cdots\\$ ~~53~~</sup> 52 bytes

Saved 3 bytes thanks to Kevin Cruijssen!!!
Saved 3 bytes thanks to Arnauld!!!
Saved a byte thanks to ceilingcat!!!

Uses xnor's formula converted to \\$3\\$ for Rock, \\$2\\$ for Scissors, \\$1\\$ for Paper, and \\$0\\$ for a tie or only a single figure appearing.

```
f(r,s,p){r=s>p&p<=r&&r?3:p>r&r<=s&&s?2:r>s&s<=p&&p;}

```

Try it online!

---
Tags: code-golf
---