title: Create a pyramidal matrix

text:
# Question
Title: Create a pyramidal matrix
A pyramidal matrix is a square matrix where all numbers increase or decrease from the center point, like the two matrices below:

```
1  1  1  1  1
1  2  2  2  1
1  2  3  2  1
1  2  2  2  1
1  1  1  1  1

```

Or:

```
3  3  3  3  3
3  2  2  2  3
3  2  1  2  3
3  2  2  2  3
3  3  3  3  3

```

Given a non-zero integer `n`, create a pyramidal matrix where the numbers goes from `1` to `n` either in increasing order (if n\<0), or decreasing order (if n\>0) from the center. **If `n` is even, then there will be 4 center numbers** (see the examples).

**As always:**

* Optional input and output format
    + Number of spaces, delimiter etc. is optional

**Test cases:**

```
1
1

-1
1

5
1  1  1  1  1  1  1  1  1
1  2  2  2  2  2  2  2  1
1  2  3  3  3  3  3  2  1
1  2  3  4  4  4  3  2  1
1  2  3  4  5  4  3  2  1
1  2  3  4  4  4  3  2  1
1  2  3  3  3  3  3  2  1
1  2  2  2  2  2  2  2  1
1  1  1  1  1  1  1  1  1

-5
5  5  5  5  5  5  5  5  5
5  4  4  4  4  4  4  4  5
5  4  3  3  3  3  3  4  5
5  4  3  2  2  2  3  4  5
5  4  3  2  1  2  3  4  5
5  4  3  2  2  2  3  4  5
5  4  3  3  3  3  3  4  5
5  4  4  4  4  4  4  4  5
5  5  5  5  5  5  5  5  5

```

```
2
1  1  1  1
1  2  2  1
1  2  2  1
1  1  1  1

-2
2  2  2  2
2  1  1  2
2  1  1  2
2  2  2  2

-4
4  4  4  4  4  4  4  4
4  3  3  3  3  3  3  4
4  3  2  2  2  2  3  4
4  3  2  1  1  2  3  4
4  3  2  1  1  2  3  4
4  3  2  2  2  2  3  4
4  3  3  3  3  3  3  4
4  4  4  4  4  4  4  4

```

# Answer
# Jelly, ~~18~~ 17 bytes

```
|1ŒḄfR«þ`
AÇạẋ¡CG

```

Try it online! or verify all test cases.

### How it works

```
|1ŒḄfR«þ`  Helper link. Argument: k (positive integer)

|1         Take the bitwise OR with 1. This increments k if it is even.
  ŒḄ       Bounce; yield [1, 2, ..., k | 1, ..., 2, 1].
    fR     Filter range; remove elements not in [1, ..., k] from the array.
           This results in [1, 2, ..., k, ..., 2, 1] if k is odd and in
           [1, 2, ..., k, k, ..., 2, 1] if k is even.
        `  Pass the last return value as left and right argument to:
      «þ     Minimum table; take the minimum of each pair of elements in the
             generated array, returning a 2D array.

AÇạẋ¡CG      Main link. Argument: n

A            Take the absolute value of n.
 Ç           Call the helper link on the result.
     C       Complement; yield 1 - n.
    ¡        Conditional application:
   ẋ           If repeating the return value of Ç 1 - n times results in a non-
               empty array, i.e., if n < 1:
  ạ              Take the absolute differences of the generated integers and 1 - n.
      G      Grid; join columns by spaces, rows by linefeeds.

```
> 5 votes

# Answer
# MATL, ~~26~~ 24 bytes

```
oXyG|to-:"TTYaQ]G0<?G+q|

```

**Try it online!** Or **verify all test cases** (slightly modified code to serve as test suite).

### Explanation

The code first builds the output array assuming positive input `n`. The array is initiallized as `1` for odd input or as the empty array for even input (this is created as an identity matrix with size equal to the parity of the input). Then the following is repeated `n` times for even input, and `n-1` times for odd input: extend the array with a frame containing `0`, and add `1` to all elements.

For example, the steps for input `n` are:

* Initial array:

```
1

```
* Extend with frame:

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

```
* Add `1`:

```
1 1 1
1 2 1
1 1 1

```
* Extend with frame:

```
0 0 0 0 0
0 1 1 1 0
0 1 2 1 0
0 1 1 1 0
0 0 0 0 0

```
* Add `1`:

```
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

```

This gives the correct output for positive input. If the input is negative, the array needs to be modified by adding the input minus `1` and taking the absolute value:

```
    3 3 3 3 3
    3 2 2 2 3
    3 2 1 2 3
    3 2 2 2 3
    3 3 3 3 3

```

You can watch the array growing (modified code to show intermediate steps) at **MATL Online!** The interpreter is still a beta. If it doesn't work press "Run" again or reload the page.

### Commented code

```
o        % Take input implicitly and push 0 if even or 1 if odd
Xy       % Identity matrix of that size. Gives either 1 or empty array
G|       % Absolute value of input
to-      % Subtract 1 if odd
:"       % For loop: repeat that many times
  TTYa   %   Add a frame of zeros in the two dimensions
  Q      %   Add 1 to all elements
]        % End for
G        % Push input again
0>       % is it negative?
?        % If so
  G      %   Push input again
  +      %   Add
  q      %   Subtract 1
  |      %   Absolute value
         % End if implicitly
         % Display implicitly

```
> 7 votes

# Answer
## Python 2, 109 99 98

```
n=input()
r=range(1,abs(n)+1)
l=r+r[~n|-2::-1]
for j in l:print[abs((n<0)*~-n+min(i,j))for i in l]

```

Create list

```
l = [1,2,3,4,5,4,3,2,1]

```

and play with it a little.

---

edit: new way of creating list + thx Lynn for two bytes
> 7 votes

# Answer
# EXCEL: 126 bytes

`=MAX(MIN(MIN(CELL("row",RC)-1,CELL("col",RC)-1),MIN(((ABS(R1C1)-1)*2+3)-CELL("row",RC),((ABS(R1C1)-1)*2+3)-CELL("col",RC))),0)`

Try it online*

Note: this answer uses R1C1 Notation. If you're going to try this yourself. you need to turn that on in Excel options.

the formula given needs to be in every cell present beyond (2,2). Put your desired pyramid size into (1,1).

quick screen-cap of the formula in action:

Here is an Additional picture of some fun with conditional formatting!

\*It takes a very long time to update, currently.
> 7 votes

# Answer
# Python 2.7: ~~123~~ ~~122~~ 120 Bytes

probs can still save a few bytes...

```
from numpy import*
n=input()
N=abs(n)
e=N*2-N%2
a=ones([e,e])
for i in range(N):a[i:e-i,i:e-i]=(i+1)*(n>0)or-n-i
print a
```

edit1: `N=abs(n)` to save 1 byte

edit2: `(i+1)*(n>0)or-n-i` to save 2 bytes
> 3 votes

# Answer
## Haskell, ~~119~~ ~~113~~ ~~110~~ ~~104~~ ~~102~~ 101 bytes

```
f x|(h,t)<-splitAt(mod x 2)$[x,x-1..1]++[1.. -x]=foldl(\m n->(n#)<$>(n<$m)#m)[[y]|y<-h]t
x#y=x:y++[x]

```

Returns the matrix as a list of lists of integers, for example: `f 2` -\> `[[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]`.

How it works:

```
            [x,x-1..1]++[1.. -x]      -- make list from x down to 1 followed by
                                      -- 1 to (-x). One of the sublists will be
                                      -- empty. The resulting list contains the
                                      -- numbers of the pyramid from inside to out.
   (h,t)<-splitAt(mod x 2)            -- bind h to the first element if x is odd
                                      -- or to the empty list if x is even
                                      -- bind t to the rest (tail or full list)

foldl (     ) [[y]|y<-h] t            -- fold the following function into t with a
                                      -- starting value of [] if x is even or
                                      -- [[h]] if x is odd

   \m n ->                            -- the current matrix m with the next number
                                      -- n is transformed into a new matrix:

               (n#)<$>(n<$m)#m        -- prepend and append a n to
                                      -- m prepended and append by a line of n's

x#y=x:y++[x]                          -- helper function to prepend and append an
                                      -- element x to a list y

```
> 3 votes

# Answer
## Perl, 175 bytes

Includes 1 bytes for `-p`.

```
($t,$v,$w)=($_,(abs)x2);$k=$_.$k for 1..$v;map{$r.=$_ for(@v=1..$_-1),$_ x(2*$v---$w%2),reverse@v;$r.=$/}1..$v;$_=$r.~~reverse$r;eval"y/1-$w/$k/"if$t<0;$w%2&&s/

.*//||s;

;

```

(There is a trailing newline that I don't know how to show with the markdown, but you need it).

Needs `-p` as well as `-M5.010` or `-E` to run :

```
perl -pE '($t,$v,$w)=($_,(abs)x2);$k=$_.$k for 1..$v;map{$r.=$_ for(@v=1..$_-1),$_ x(2*$v---$w%2),reverse@v;$r.=$/}1..$v;$_=$r.~~reverse$r;eval"y/1-$w/$k/"if$t<0;$w%2&&s/

.*//||s;

;
' <<< 5

```

Damn, this is too long... I'll try some other approaches when I have some time.
> 2 votes

# Answer
# Python 2, 109 bytes

```
n=input()
a=abs(n)
s=a*2-a%2
r=range(s)
for y in r:print[(min,max)[n<0](x+1,s-x,y+1,s-y)-(n<0)*s/2for x in r]

```
> 2 votes

# Answer
# J, ~~29~~ 26 bytes

```
1+**[:<./~**i.,2&|1&}.i.@-

```

## Usage

```
   f =: 1+**[:<./~**i.,2&|1&}.i.@-
   f 1
1
   f _1
1
   f 2
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
   f _2
2 2 2 2
2 1 1 2
2 1 1 2
2 2 2 2
   f 3
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
   f _3
3 3 3 3 3
3 2 2 2 3
3 2 1 2 3
3 2 2 2 3
3 3 3 3 3

```

## Explanation

The range `i.` verb outputs `[0, 1, ..., n-1]` for positive `n` and `[n-1, n-2, ..., 0]` for negative `n` which is useful here.

```
1+**[:<./~**i.,2&|1&}.i.@-  Input: integer n
                         -  Negate n
                      i.@   Creates range for -n
               2&|          Take n modulo 2, returns 0 or 1
                  1&}.      If n is odd, drop the first value from the range for -n
                            Else do nothing and pass it unmodified
              ,             Append it to
            i.              The range for n
          *                 Get the sign of n
           *                Multiply elementwise with the joined ranges
    [:<./~                  Form a table of the minimum values of the range
  *                         Get the sign of n
   *                        Multiply elementwise with the joined ranges
1+                          Add 1 to each and return

```
> 2 votes

# Answer
# Mathematica, 78 bytes

```
Abs[Fold[ArrayPad[#,1,#2]&,Table[0,#,#]&@Mod[#,2,1],Range[Abs@#-1]]+1~Min~-#]&

```

# Explanation

```
Table[0,#,#]&@Mod[#,2,1]

```

Make initial matrix: 1x1 if odd, 2x2 if even.

```
Range[Abs@#-1]

```

Generate a list from 1 to abs(input) - 1.

```
Fold[ArrayPad[#,1,#2]&, ..., ...]

```

Pad the initial array using the aforementioned list.

```
... +1~Min~-#

```

Add 1 or -input, whichever is smaller.

```
Abs

```

Apply absolute value to the entire matrix.
> 2 votes

# Answer
# PHP, ~~177~~ 157 bytes

```
for($y=-$n=abs($z=$argv[1])+1;++$y<$n;)if($y&&($n&1||$y-1)){for($x=-$n;++$x<$n;)if($x&&($n&1||$x-1)){$v=max(abs($x),abs($y));echo$z<0?$v:$n-$v," ";}echo"
";}

```

run with `php -r '<code>`

loops through rows and columns, prints the values depending on their distance to the center.

* `$n=abs($z)+1`: The `+1` saves a couple of `+1` and `-1` in later expressions
* loops go from `-$n+1` (pre-increment in the condition!) to `$n-1` (`-abs($z)` to `abs($z)`)
* line/column 0 (and for odd `$n`: 1) are skipped
(`$n&1` is true for even columns here! Remember the `+1`?)
* The printing for positive $z also benefits from the `+1`.
> 1 votes

# Answer
# Haskell, ~~191~~ ~~183~~ ~~173~~ ~~169~~ 168 bytes

```
r=reverse;m=map
x!y=(((++)<*>(x.r)).).zipWith(++).m y
g n|n<0=m(m$abs.((n-1)+)).g$abs n|1<2=[id!id,tail!init]!!mod n 2=<<m r$r$m(\x->(x<$[1..x])++[x+1..n])[1..n]
g.(0-)

```

Usage:

```
mapM_ print $ (g.(0-)) 3

[1,1,1,1,1]
[1,2,2,2,1]
[1,2,3,2,1]
[1,2,2,2,1]
[1,1,1,1,1]

```

Thanks to nimi for ~~2~~ ~~10~~ ~~20~~ 24 bytes!
> 1 votes

# Answer
## JavaScript (ES6), 107 bytes

```
(n,l=Math.abs(n+n-n%2))=>[...Array(l--)].map((_,i,a)=>a.map((_,j)=>(j=Math.min(i,l-i,j,l-j),n<0?-n-j:j+1)))

```

`l` is the size of the array. The `n<0?-n-j:j+1` seems awkward but I can't find anything better.
> 1 votes

# Answer
# Vim, ~~152~~ 143 bytes

I'm sure this could be golfed more, especially those last two lines, but my brain is fried.

```
D:let@z=@-/abs(@-)
a"nywYp:s/\d/x/g<C-v>
YggP:%s/.*/x \0 x<C-v>
:%s/x\+/\=@n-@z/g<C-v>
<Esc>v0"qda<C-r>=@z<0?1:@-*@z
<Esc>@=@-%2?"":"YPJYp"
@=@-*@z-1.(@-*@z>1?"@q":"")

```

Try it online!

Here it is in xxd format with unprintable characters:

```
0000000: 443a 6c65 7440 7a3d 402d 2f61 6273 2840  D:let@z=@-/abs(@
0000010: 2d29 0a61 226e 7977 5970 3a73 2f5c 642f  -).a"nywYp:s/\d/
0000020: 782f 6716 0a59 6767 503a 2573 2f2e 2a2f  x/g..YggP:%s/.*/
0000030: 7820 5c30 2078 160a 3a25 732f 785c 2b2f  x \0 x..:%s/x\+/
0000040: 5c3d 406e 2d40 7a2f 6716 0a1b 7630 2271  \=@n-@z/g...v0"q
0000050: 6461 123d 407a 3c30 3f31 3a40 2d2a 407a  da.=@z<0?1:@-*@z
0000060: 0a1b 403d 402d 2532 3f22 223a 2259 504a  ..@=@-%2?"":"YPJ
0000070: 5970 220a 403d 402d 2a40 7a2d 312e 2840  Yp".@=@-*@z-1.(@
0000080: 2d2a 407a 3e31 3f22 4071 223a 2222 29    -*@z>1?"@q":"")

```

## Explanation

It builds the pyramid from the center out, surrounding the center number with `x`es:

```
x x x
x 5 x
x x x

```

Then it replaces the `x`es with the next number and surrounds it with `x`es again:

```
x x x x x
x 4 4 4 x
x 4 5 4 x
x 4 4 4 x
x x x x x

```

...and so on. For even numbers it does the same thing but starts with a 2x2 base.

Here's the code "ungolfed." It's somewhat unconventional in that I "record" a macro by typing it into a buffer (hence all the `<C-v>`s) and then deleting it into a register, which is the best way I found to compose a macro without actually executing the keystrokes.

```
D:let@z=@-/abs(@-)<CR>       " Delete the input (into @-) and set @z to -1 if @- is negative; otherwise 1
a                            " Enter insert mode to compose the macro
  "nyw                         " Copy the number under the cursor to @n
  Yp                           " Copy this line and paste it below
  :s/\d/x/g<C-v><CR>           " Replace digits in the copy with 'x'
  YggP                         " Copy this line and paste it at the top of the buffer
  :%s/.*/x \0 x<C-v><CR>       " Add an 'x' before and after each line
  :%s/x\+/\=@n-@z/g<C-v><CR>   " Replace all 'x'es (and 'xx'es etc.) with the next number
<Esc>v0"qd                   " Done composing macro; delete it into @q (buffer is now empty)
a<C-r>=@z<0?1:@-*@z          " Append the center number (1 or abs(@-)) to the buffer
<Esc>@=@-%2?"":"YPJYp"       " If the input is even, make a 2x2 square
@=@-*@z-1.(@-*@z>1?"@q":"")  " Execute the macro abs(@-)-1 times if it's > 1

```
> 1 votes

# Answer
# PHP, 215 Bytes

```
for($i=0;$i<$m=($r=($s=abs($n=$argv[1]))*2-$s%2)**2;){$i%$r?:print"\n";$l=min(($x=$i%$r+1)<$s?$x:$x=$r-$x+1,($z=1+floor($i++/$r))<$s?$z:$z=$r-$z+1);$o=($n>0)?$l:$s+1-$l;echo str_pad(" ",1+strlen($s)-strlen($o)).$o;}

```
> 0 votes

# Answer
# R, 112 bytes

```
k=abs(n);l=2*k;m=diag(l);for(i in 1:k){m[i:(l+1-i),i:(l+1-i)]=i};if(n%%2==1){m=m[-k,-k]};if(n<0){m=abs(m-1+n)};m

```

Needs integer `n` in workspace, otherwise run `n=scan()` for an extra 8 bytes.

```
k=abs(n)
l=2*k
m=diag(l)                    # Initialize quadratic 2*|n| matrix
for(i in 1:k){
    m[i:(l+1-i),i:(l+1-i)]=i # Assign values to matrix elements according
                             # to their index
}
if(n%%2==1){
   m=m[-k,-k]                # If n is odd, delete middle row and column
}
if(n<0){
    m=abs(m-1+n)             # If n < 0, flip values
}
m                            # Print matrix

```
> 0 votes

---
Tags: code-golf, number, matrix
---


title: Tips for golfing in Emotinomicon

text:
# Question
Title: Tips for golfing in Emotinomicon
What general tips do you have for golfing in Emotinomicon? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Emotinomicon (e.g. "remove comments" is not an answer).

Please post one tip per answer.

# Answer
Should be answers to respective challenges (if they exist). Note that some of these code samples might alerady be answers somewhere else.

If you just want to print `undefined`, use this 4-byte, 1-char program.

```

```

Infinite loop (6 bytes, 2 chars).

```
ℹ⏩

```

Cat (owned by Conor O'Brien) (15 bytes, 5 chars).

```
⏫⏪⏬⏫⏩

```

This program should output the 8 phases of the moon, but it doesn't seem to work (61 bytes, 16 chars).

```
⏪⏬⏩

```

Hypothenuse (27 bytes, 7 chars).
> 2 votes

# Answer
If you just want a truthy value (or even just a value), without using it, use . It's 3 bytes, while the others are 4 bytes.
> 1 votes

# Answer
If you want to output 2 chars or less, do not use `⏪⏬⏩`, use the number of s needed.
> 1 votes

# Answer
# Make use of built-ins.

Some cases are:

* `⁉❕` -\>
* The numbers `0`-`10`, `100` and `i` are , respectively.
* Multiplication with `2`-`4` is done with `☺`, respectively.
* Division with `2`-`4` is done with , respectively.
* Exponentiation with `2`-`4` is done with , respectively.
* Rooting:
    + n-Rooting with `n` being `2`-`4` is done with , respectively.
    + For other `n`, use `n➗`. `n` is not a literal `n`, but the power of rooting.
> 1 votes

# Answer
# Infinite Looping

If you want to loop a program infinitely, from index `n`, you can use `n` to jump behind the `n`th character. For example, this 34-byte, 12-char program for `yes`:

```
⏪sey⏪⏬⏩⏩

```

Becomes this 32-byte, 11-char program:

```
sey⏪⏬⏩

```
> 1 votes

# Answer
Because of a bug in the interpreter, if you want to append `1` to a number (e.g. `10` -\> `101`), use . As it is right now, you have to use  for the *true* function of .
> 0 votes

---
Tags: code-golf, tips
---


title: Counterfeit Coins on a Pointer Scale

text:
# Question
Title: Counterfeit Coins on a Pointer Scale
You sell gold coins. Each gold coin you sell is supposed to be 1 ounce. However, you find out that one of your coin suppliers is cheating you. By alloying the gold material with something else, their coins weigh only 0.9 ounces. With a help of a **pointer** scale (one that shows the exact weight of a quantity of matter set on it), you want to determine which of your coin suppliers is selling you the counterfeit coins.

Apparently, you are not the only one to have this problem - lots of gold sellers buy coins from this supplier, and the supplier knows that it is being dodgy and is changing their branding accordingly. All of these sellers have the same problem - 1 ounce coins that end up being 0.9 ounces from this supplier - and need to solve it, fast! How can you determine, out of `n` suppliers, which one is the cheating supplier with the **minimum** number of weighings on the pointer scale?

---

Your task is to write a program function that can solve this problem automatically for `n` suppliers. It's **input** includes:

* an integer number of suppliers, `n`,
* an oracle function that represents weighing a set of coins on the balance scale

It must take this information, calling this function a minimum number of times and returning, as **output**, the index number of the cheating supplier.

The oracle function has the following specifications:

* It takes as input an `int->int` mapping (as an array or dictionary, whichever your language prefers) mapping each supplier index (from `0` to `n-1`) to a number of gold coins that you want to try weighing on the scale.
* The returned output is the total weight, in ounces, of the coins put on the scale.
* The function is in whatever format your language prefers for passing procedures as data. For instance, functional languages will pass lambdas, C will take a function pointer, Java 7 and earlier will take a functional interface. Languages that support none of these, but do support string execution, will take these as strings.
* In those cases when the oracle can be stringified or otherwise inspected as data, you may assume that it is sufficiently obfuscated such that you cannot tell which supplier is cheating without executing it.

This is also code-golf: among the solutions that call the function the minimum number of times, the smallest solution in bytes is the winner!

---

NOTE: If your language does not support functions at all, but does support string execution, write your program as a standalone program - assume that the number of suppliers, followed by the oracle, will be passed into standard input. If your language does not support string execution, assume that a file path to a binary oracle will be provided instead.

# Answer
> 6 votes
## Python, 33 bytes

```
lambda n,f:n*~-n*5-f(range(n))*10

```

Puts 0 coins from supplier 0, 1 coin from supplier 1, ... n-1 coins from supplier n-1. The deficit is then 0.1 for each coin sent to the cheating supplier, so `i/10`. We therefore subtract the oracle value from the fair sum `n*(n-1)/2` and multiply by 10. Distributing the `*10` saved on parens for a shorter expression.

# Answer
> 3 votes
# Python 2, ~~56 48~~ 44 bytes

**Uses 1 weighing**

-8 bytes thanks to @feersum (use `range(0,10*n,10)`)

```
def f(n,o):x=range(n);return(sum(x)-o(x))*10

```

Example runs at **ideone**

Places `i` coins from each of the suppliers `i` in `[0,n-1]` on the scale, subtracts the weighing from the total number of coins weighed and multiplies by 10.

(Python 3 will return float values that start to differ)

# Answer
> 1 votes
# Mathematica, 23 Byte

```
5#(#+1)-1-10#2@Range@#&

```

Same approach as xnor. In Mathematica `Range` starts with `1`, which is equivalent to using `n+1` coins from the `n`th supplier. Hence, the formula for the fair sum is `n(n+1)/2` and we have to subtract `1` from the result to restore zero-based indexing.

```
5#(#+1)-1-10#2@Range@#&[5,oracle]

```

> 149 - 10 oracle\[{1, 2, 3, 4, 5}\]

# Answer
> 1 votes
# Pyth, 9 bytes

```
-FsMlBm*T

```

As `o` cannot be used for the oracle in Pyth (it takes in a lambda itself), I instead defined the oracle as `l`. Any one-input function other than `s` should work as the oracle. Returns 0-indexed input.

Explanation (assuming the 3rd vendor is the faulty one):

```
      m*T        Map d*10 over all d in range(input): [0, 10, 20, 30] for input = 4
    lB           Bifurcate over the oracle function: [[0,10,20,30],58.0]
  sM             Map sum (for arrays, floors numbers): [60,58]
-F               Fold over subtraction: 2
                 Implicitly print

```

Try it online! (first line sets up the oracle function)

Try changing the faulty vendor! (The faulty vendor is 0-indexed: from `0` to `first input - 1`. Any other value will cast the blame on the 0th vendor.)

---
Tags: code-golf, puzzle-solver
---


title: Solve Grid-Tangram

text:
# Question
Title: Solve Grid-Tangram
The *Tangram* is a dissection puzzle made from seven shapes: Five differently sized triangles, a parallelogram and a square. Given a shape, the goal is recreating the shape using all the pieces and without overlapping. There are obviously infinitely many ways to arrange this set of pieces in the plane. An interesting subset are the

### Grid Tangrams

We can draw the "standard" Tangram square into a bigger square which is subdivided by a *grid* into 16 smaller squares. Grid tangrams are just shapes made up of the tangram pieces, such that all vertices of the pieces are on the grid points.

These are the kinds of Tangram puzzles we want to consider in this challenge, as they are probably easier to handle than the more general ones.

As a side note: The Chinese mathematicians Chuan-Chin Hsiung and Fu Traing Wang proved in 1942 that there are only 13 convex tangrams. They first showed that the problem can be reduced to grid tangrams, and then used some combinatorial and geometric arguments. These are all of those 13:

### Challenge

Given a solvable grid tangram, output a dissection of the grid tangram into the seven tangram pieces.

### IO

A tangram is given as a black and white image (the shape is in black, background in white), with both sides multiples of 50px. The grid has a width of exactly 50px. The grid lines are parallel to the sides of the image.

**EDIT: The image can be accepted as input and returned as output in any convenient raster image format like PNG,TIFF,PBM etc. but a representation as a binary 2d array or string or matrix is acceptable.**

The output should again have the same size and should have again the same shape, but with each piece a different colour, or alternatively with white lines separating all the pieces. It is worth noting that the non rectangular quadrangle can be flipped.

The pixels on the border of the pieces do not exactly have to match the one on the shape, also if there are aliasing effects or other fuzz this is still ok.

Example Input and Output:

Examples:

Possible solutions:

# Answer
> 34 votes
# BBC BASIC, ~~570 514~~ 490 bytes ASCII

Download interpreter at http://www.bbcbasic.co.uk/bbcwin/download.html

**435 bytes tokenised**

Full program displays an input from `L.bmp` on the screen, then modifies it to find a solution.

```
*DISPLAY L
t=PI/8q=FNa(1)
DEFFNa(n)IFn=7END
LOCALz,j,p,i,c,s,x,y,m,u,v
F.z=0TO99u=z MOD10*100v=z DIV10*100ORIGINu,v
F.j=0TO12S.4p=0F.i=j+3TOj+9S.2c=9*COS(i*t)s=9*SIN(i*t)p=p*4-(POINT(c,s)<>0)*2-(POINT(9*c,9*s)<>0)N.
m=n:IFn=5A.(43A.p)=0p=0m=7
IF(ASCM."??O|(C",n)-64A.p)=0THEN
F.i=-1TO0GCOL0,-i*n:c=99*COS(j*t)s=99*SIN(j*t)y=402/3^m MOD3-1MOVE-c-s*y,c*y-s:x=n<3MOVEc*x-s*x,s*x+c*x:x=2778/3^m MOD3-1y=5775/3^m MOD3-1PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y:IFi q=FNa(n+1)ORIGINu,v
N.
ENDIF
N.N.=0

```

**Explanation**

Note that in BBC basic a distance of 1 pixel = 2 units, so the 50x50 pixel grid becomes a 100x100 grid.

We use a recursive function to place the 2 large triangles, medium triangle, square and parallelogram into the shape. The earlier shape in the list is drawn before the next recursive call is made. if a recursive call returns without finding a solution, the earlier shape is overdrawn in black and a new position of the earlier shape is tried.

Once these five shapes are drawn, placing the two small triangles is just a formality. It is necessary to draw one of them though, in order to distiguish them if they share a common edge. We only colour one of the two small triangles. The other is left in natural black.

Placing of each shape is attempted at different x,y coordinates and in 4 different rotations. To test if there is free space to draw a shape we use the template below, with 45 degree angles. The rotations are made about the `*` and the 8 pixels tested are in 2 semicircles of radius 9 and 81 units and fall on radiating lines at odd multiples of 22.5 degrees to the x and y axes.

For a large triangle all 8 spaces are required to be clear. For other shapes only some of the cells must be clear so a mask is applied.

```
+----+----   Shape             Mask HGFEDCBA Mask decimal
|\ E/|\G /
| \/F|H\/    1,2. Large triangle    11111111    -1
|C/\ | /     3. Med triangle        00001111    15
|/ D\|/      4. Square              00111100    60
+----*       5. Parallelogram       11101000   -24
|\ B/        6. Small triangle      00000011     3
|A\/         7. Parallogr reversed  00101011    43
| /          Note: reversed parallelogram is checked/drawn at recursion depth n=5
|/           with a special check, but the coordinates are encoded as m=7.

```

Once it is established that a shape will fit, it must be drawn. If it is a triangle it is plotted with `PLOT 85`, if it is a parallelogram, the number is 32 higher (note that for `PLOT` purposes we consider a square a special parallelogram). In either case 3 consecutive vertices must be given. The second vertex is the origin of the shape (marked `*` in the above table) except in the case of the large triangle, where (prior to rotation) it is `-1,-1.` The other 2 vertices can have x and y coordinates of `-1,0 or 1` which are extracted from base 3 encoded numbers, then scaled by 99 and rotated as necessary by transformation with `c` and `s`.

**Ungolfed code**

```
  *DISPLAY L
  t=PI/8                                          :REM Constant 22.5 degrees.
  q=FNa(1)                                        :REM Call function, return dummy value to q
  END                                             :REM End the program gracefully if no solution. Absent in golfed version.

  DEFFNa(n)                                       :REM Recursive function to place shapes.
  IFn=7END                                        :REM If n=7 solution found, end program.
  LOCALk,z,j,p,i,c,s,x,y,m,u,v                    :REM declare local variables for function.
  k=ASCMID$("??O|(C",n)-64                        :REM Bitmasks for big tri, big tri, med tri, sq, normal paralellogram, small tri.
  FORz=0TO99                                      :REM For each point on the grid
    u=z MOD10*100:v=z DIV10*100                   :REM calculate its x and y coordinates relative to bottom left of screen
    ORIGINu,v                                     :REM and set the origin to this point.
    FORj=0TO12STEP4                               :REM For each rotation 0,90,180,270deg
      p=0                                         :REM assume no non-black pixels found
      FORi=j+3TOj+9STEP2                          :REM test angles of 3,5,7,9 times 22.5 deg anticlockwise from right x axis.
        c=9*COS(i*t)                             :REM Coords of test points at radius ll
        s=9*SIN(i*t)
        p*=4                                      :REM Leftshift any existing data in p
        p-=(POINT(c,s)<>0)*2+(POINT(9*c,9*s)<>0)  :REM and check pixels at radius 11 and 99.
      NEXT
      m=n                                         :REM The index of the shape to plot normally corresponds with recursion depth n.
      IF n=5 AND (43ANDp)=0 p=0:m=7               :REM If n=5 check if a reverse parallelogram is possible (mask 43). If so, clear p and change m to 7.
      REM                                         :REM Check p against mask k, if the shape fits then...
      IF (k ANDp)=0 THEN
        FOR i=-1 TO 0                               :REM draw the shape in colour, and if deeper recursions prove unsuccesful, redraw it in black.
          GCOL0,-i*n                                :REM Colour is equal to n.
          c=99*COS(j*t)                             :REM Set parameters c and s for scaling by 99
          s=99*SIN(j*t)                             :REM and rotation by 0,90,180 or 270 as appropriate.
          x=-1                                      :REM For vertex 1, x=-1 always.
          y=402/3^m MOD3-1                          :REM Lookup y value for vertex 1.
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=n<3                                     :REM For vertex 2, coords are 0,0 except for large triangle where they are -1,-1
          y=x                                       :REM in BBC BASIC, TRUE=-1
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=2778/3^m MOD3-1                         :REM Lookup x and y value for vertex 3.
          y=5775/3^m MOD3-1                         :REM PLOT85 uses last 2 points + specified point to make triangle, PLOT85+32 makes paralelogram (or square.)
          PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y      :REM Use c and s to transform the vertex and draw shape.
          IFi q=FNa(n+1):ORIGINu,v                  :REM If i=-1 recurse to next level. If it fails, reset the origin before replotting this level's shape in black.
        NEXT
      ENDIF
    NEXT
  NEXT
  =0                                                :REM Dummy value to return from function

```

**Output**

This is a montage of the solutions found by the program for the test cases. Use of 99 instead of 100 for golfing reasons leaves some small black gaps. As the shapes are redrawn during the searches, it can take a few seconds to run for some cases, and is quite fascinating to watch.

---
Tags: code-golf, geometry, grid, puzzle-solver, set-partitions
---


# Question
Title: Program that outputs a program that outputs a program ... that outputs "Hello!"
## Challenge

Write the shortest program P such that

* P takes any positive integer n as input, and outputs a program string P1
* executing P1 (with no input) outputs a program string P2,
* executing P2 (with no input) outputs a program string P3,
* ...
* executing Pn (with no input) outputs exactly "Hello!" (without the quotes).

Schematically:

**P(n) → P1 → P2 → ... → Pn → Hello!**

## Criteria

* I/O is via stdin/stdout.
* Program length is measured in bytes.
* Programs consist only of ASCII printable characters.
* There must be no duplicates among the programs P, P1,...,Pn.

EDIT: Programs P, P1,...,Pn are meant to be source code, and "executing the program" refers to whatever processing produces the output (i.e., interpretation, compilation & execution, etc.).

# Answer
> 10 votes
### Golfscript ~~39~~ 14

```
~'Hello!'{`}@*

```

**Example:**

Assuming that **n=4** and our program is **P**, these are the steps:

1. Run **P** with parameter **4**. The output is `"\"\\\"\\\\\\\"Hello!\\\\\\\"\\\"\""` (**P1**)
2. Running **P1** outputs `"\"\\\"Hello!\\\"\""` (**P2**)
3. Running **P2** outputs `"\"Hello!\""` (**P3**)
4. Running **P3** outputs `"Hello!"`(**P4**)
5. Running **P4** outputs `Hello!`. If you don't trust me, follow this link ☺.

# Answer
> 4 votes
## Perl (~~45~~ 36)

```
say"say q("x($m=<>),"Hello!",")"x$m

```

Run with `perl -M5.010` to use `say`.

For `n=1`, outputs `say q(Hello!)`
For `n=2`, outputs `say q(say q(Hello!))`
For `n=3`, outputs `say q(say q(say q(Hello!)))`
and so on.

# Answer
> 4 votes
## JavaScript, 58 chars

```
function $(_){alert(_?$+'$('+--_+')':'Hello!')}$(prompt())

```

# Answer
> 2 votes
### Python3, 66

```
r="print(%r)";e=eval;n=e(input())+1;e(e("(r%"*n+"'Hello!'"+")"*n))

```

# Answer
> 2 votes
### Common Lisp, 68 characters

```
(do((n(read)(1- n))(s'(princ"Hello!")`(print',s)))((= 0 n)(eval s)))

```

```
(do ((n (read) (1- n))
     (s '(princ "Hello!") `(print ',s)))
    ((= 0 n) (eval s)))

```

The only non-straightforward thing: it generates one more level of program than needed and evaluates it, because `eval` is one character shorter than `print`.

# Answer
> 2 votes
# Common Lisp: 65

```
#1=(SETF N(READ)(CADDR'#1#)(1- N)W(PRINT(IF(= N 0)"Hello!"'#1#)))

```

This version is smaller than the existing CL-answer. In case your Lisp croaks with a stackoverflow, then you have to use this, 81 bytes:

```
#1=(SETF N(READ)*PRINT-CIRCLE* T(CADDR'#1#)(1- N)W(PRINT(IF(= N 0)"Hello!"'#1#)))

```

I know I'm late to the party, and I'm sure this could still be optimized.

Demonstration (careful, some online REPLs don't work correctly):

```
* #1=(SETF N(READ)*PRINT-CIRCLE* T(CADDR'#1#)(1- N)W(PRINT(IF(= N 0)"Hello!"'#1#)))
2
#1=(SETF N 1
         *PRINT-CIRCLE* T
         (CADDR '#1#) (1- N)
         W
           (PRINT
            (IF (= N 0)
                "Hello!"
                '#1#)))
#1=(SETF N 1
         *PRINT-CIRCLE* T
         (CADDR '#1#) (1- N)
         W
           (PRINT
            (IF (= N 0)
                "Hello!"
                '#1#)))
* (eval *)

#1=(SETF N 0
         *PRINT-CIRCLE* T
         (CADDR '#1#) (1- N)
         W
           (PRINT
            (IF (= N 0)
                "Hello!"
                '#1#)))
#1=(SETF N 0
         *PRINT-CIRCLE* T
         (CADDR '#1#) (1- N)
         W
           (PRINT
            (IF (= N 0)
                "Hello!"
                '#1#)))
* (eval *)
"Hello!"
"Hello!"
*

```

Note that:

* Tested using SBCL 1.2.11.debian
* There are lots of warnings because I'm doing things that are seriously not supposed to be done. Thankfully, all warnings are printed with a semi-colon, so they would be treated as comments anyway.
* Duplication is because one is the return value and one actual output. If the return value would also count, then it simplifies to 58 bytes: `#1=(SETF N(READ)(CADDR'#1#)(1- N)W(IF(= N 0)"Hello!"'#1#))`
* I still know I'm late to the party

# Answer
> 1 votes
### Python 2.7, 57

```
print reduce(lambda x,y:y+`x`,input()*["print"],"Hello!")

```

# Answer
> 1 votes
## Haskell, 62

```
main=interact$(iterate(("main=putStr"++).show)"Hello!"!!).read

```

# Answer
> 1 votes
Bash, 47 or 12 (if I use golfbash)

Code:

```
read x;for((;x>=0;x--)){ O+=" echo";};$O Hello!

```

golfbash code:

```
R;n e Hello!

```

Previous code (49):

```
read x;E=echo;eval \"\${E[0]\"{0..$x}\"}\" Hello!

```

Use:

Make program P

```
$ echo '<paste code here>' > P

$ chmod +x P

```

Example

Make P1:

```
$> echo 4 | ./P >
echo echo echo echo Hello!

```

Make P2:

```
$> echo 4 | ./P | bash
echo echo echo Hello!

```

Make P3:

```
$ echo 4 | ./P | bash | bash
echo echo Hello!

```

Make P4:

```
$ echo 4 | ./P | bash | bash | bash
echo Hello!

```

Run P4:

```
$ echo 4 |./P | bash | bash | bash | bash
Hello!

```

Say that I make a new general purpose language called golfbash - at bit like golfscript - that has some useful commands like these:

```
R which reads stdin and places result into variable $REPLY.
n $1 $2 which echo's $1 $REPLY times followed by $2.
e which echo's all parameters to stdout.

```

Then I could write this:

```
R;n e Hello!

```

This would be legal, would't it?

# Answer
> 0 votes
**F#, 182**

```
let say msg = sprintf "%s" msg
let gen num =
    let rec g n a =
        match n with
        | i when i > 0 -> g (i-1) ("say \"" + a + "\"")
        | _ -> say a
    g num "Hello!"

```

# Answer
> 0 votes
# J - 31 char

Keep in mind that J uses Pascal-style strings: `'It''s too easy!'`

```
'Hello!'(],,)''''#~<:2^".1!:1]1

```

Explained:

* `".1!:1]1` \- Read in a line from stdin and convert it to a number.
* `<:2^` \- Take 2 to the power of this number, and decrement.
* `''''#~` \- Make a string with that many copies of the single quote character.
* `'Hello!'(],,)` \- Append these quotes to the front and back of `Hello!`.

Usage:

```
   'Hello!'(],,)''''#~<:2^".1!:1]1   NB. let's try 3
3
'''''''Hello!'''''''
   '''''''Hello!'''''''  NB. P1
'''Hello!'''
   '''Hello!'''          NB. P2
'Hello!'
   'Hello!'              NB. and P3 prints Hello!
Hello!

```

# Answer
> 0 votes
## Python 2.7: 75

```
def h(n):
 return "Hello"if n<1 else'print %s' % `h(n-1)`
print h(input())

```

First time golfing, not sure if I'm doing it right ;p

# Answer
> 0 votes
# Clojure, 36 bytes

```
(str(apply str(repeat 5\'))"Hello!")

```

Symbol

```
'something

```

evaluates to

```
something

```

Build up a symbol with 5 single quotes and run the result until no quotes left.

---
Tags: code-golf
---


title: String and ASCII

text:
# Question
Title: String and ASCII
**The Challenge**

Given a non-empty string containing only lowercase or uppercase letters and no spaces:

* Sum up the ASCII values for each character instance in the input string.
* The sum will be converted to binary.
* And, the result will be the number of ones in the binary value.

**Input example:**

```
abcDeFAaB

```
1. Sum up the ASCII values for each character instance, so for this example: `97+98+99+68+101+70+65+97+66 = 761`.
2. Convert the sum (`761`) to binary. This will give `1011111001`.
3. The final result will be the number of ones (`7`).

So the output for this example is `7`.

**Winning Criterion**

This is , so shortest answer in bytes wins!

# Answer
> 9 votes
# Jelly, 4 bytes

```
OSBS

```

**TryItOnline**

How?

```
OSBS - Main link: s     e.g. "abcDeFAaB"
O    - ordinal (vectorises)  [97, 98, 99, 68, 101, 70, 65, 97, 66]
 S   - sum                   761
  B  - binary                [1, 0, 1, 1, 1, 1, 1, 0, 0, 1]
   S - sum                   7

```

# Answer
> 5 votes
# Python3, ~~46~~ 40 bytes

```
lambda s:bin(sum(map(ord,s))).count("1")

```

# Answer
> 4 votes
# R, ~~65~~ ~~53~~ ~~43~~ 42 bytes

Counting the number of 1s in a binary representation is calculating the Hamming weight of a number, a common procedure in cryptanalysis. There's an R package `boolfun`, described in this journal article, which handily has a function `weight` which computes the Hamming weight of any (base 10) integer. That makes our job a lot easier! The rest of the code just sums over the integer representation of STDIN, before sending that to `weight`.

```
boolfun::weight(sum(utf8ToInt(scan(,'')))

```

As an added bonus, this code works for UTF-8 as well as ASCII. There are 7 ones in the binary representation of the sum of 高尔夫 (that's *golf* in Mandarin).

A note for those playing along at home: unfortunately, `boolfun` is no longer hosted on CRAN, so if you don't already have it installed you'll have to do it manually with `install.packages("https://cran.r-project.org/src/contrib/Archive/boolfun/boolfun_0.2.8.tar.gz", repos = NULL, type = "source")`, rather than `install.packages(boolfun)`.

If you really don't want to use `boolfun`, you can achieve the same result with only two more bytes:

```
sum(intToBits(sum(utf8ToInt(scan(,''))))==1)

```

# Answer
> 4 votes
# MATL, 3 bytes

```
sBs

```

Try it online!

Shortest language for this challenge, I think: `s`um, `B`inary, `s`um.

# Answer
> 3 votes
# 05AB1E, ~~6~~ 5 bytes

```
ÇObSO

```

**Explanation**

```
 Ç      # convert to list of ascii values
  O     # sum
   b    # convert to binary
    SO  # sum as a list

```

Try it online!

# Answer
> 3 votes
# Bash + coreutils, ~~43~~ 49 bytes

**Edit:** corrected version based on manatwork's comments.

```
od -vAn -tuC|tr '\n ' +|dc -e?2op|grep -o 1|wc -l

```

**Explanation:**

The result is printed on STDOUT, with some warnings given on STDERR which can be ignored.

```
od -vAn -tuC       # get the ASCII value for each string character
|tr '\n ' +        # replace each whitespace with a plus (in dc, a warning will be
                   #raised for each consecutive plus)
|dc -e?2op         # execute input, calculating the sum, then convert to binary
|grep -o 1|wc -l   # count how many ones exist

```

**Run:**

```
echo -n "abcDeFAaB" | ./script.sh 2> /dev/null

```

**Output:**

```
7

```

A similar solution is presented below (51 bytes), that had the potential to be shorter, but with *xxd* I can't concatenate multiple flags and also *dc* only understands upper case hex letters.

```
xxd -c1 -u -p|tr \\n +|dc -e16i?2op|grep -o 1|wc -l

```

# Answer
> 2 votes
# Java 7,~~80~~,76 bytes

*Thanks to kevin for saving **4 bytes***

```
int f(char[]a){int s=0,c=0;for(char i:a)s+=i;for(;s>0;s&=s-1,c++);return c;}

```

# Ungolfed

```
int f(char[]a){
    int s=0,c=0;
    for(char i:a)
        s+=i;
    for(;s>0;s&=s-1,c++);
        return c;
}

```

# Answer
> 2 votes
# PHP, ~~79~~ 76 bytes

```
foreach(str_split($argv[1])as$c)$s+=ord($c);echo substr_count(decbin($s),1);

```

Test online

Ungolfed testing code:

```
$argv[1] = 'abcDeFAaB';

foreach(str_split($argv[1]) as $c){
    $s += ord($c);
}
echo substr_count(decbin($s),1);

```

Test online

# Answer
> 1 votes
## R, 98 bytes

Was interested in how difficult this would be in R. Turns out you have to do a lot of conversions back and forth (in this solution at least) but I'm sure there should be a shortcut, especially if using packages (can't access any here at work).

```
sum(as.integer(rev(intToBits(sum(strtoi(sapply(strsplit(readline(),"")[[1]],charToRaw),16L)))))^2)

```

Could add an explanation if someone is interested.

# Answer
> 1 votes
# \>\<\>, 34 bytes

```
01\
(?\i:@+$0
?!\:2%:}-2,r+$:
n;\~

```

Try it online!

# Answer
> 1 votes
# Haskell, 47 bytes

```
g 0=0;g n=mod n 2+g(div n 2)
g.sum.map fromEnum

```

# Answer
> 1 votes
# Perl, 36 bytes

Includes +1 for `-p`

Run with input string ***without newline*** on STDIN:

```
echo -n abcDeFAaB | strsum.pl; echo

```

`strsum.pl`:

```
#!/usr/bin/perl -p
$_=unpack"%b*",pack N,unpack"%32W*"

```

If the sum of the ASCII values fits in a 16-bit integer you can leave out the `32` and gain 2 more bytes.

# Answer
> 1 votes
## Julia, 56 Bytes

```
f(s)=length(filter(i->i=='1',bin(sum(map(Int,[s...])))))

```

Convert to ascii value, sum up, filter for 1s, take length of result

# Answer
> 1 votes
## JavaScript ES6, ~~80~~ ~~78~~ 71 Bytes

```
g=
    s=>[...s].map(c=>r+=c.charCodeAt(),r=0)|r.toString(2).split`1`.length-1
;

console.log(g.toString().length);    // 71
console.log(g('abcDeFAaB'))          // 7
```

Saved 7 Bytes thanks to @BassdropCumberwubwubwub

### Breakdown

```
 [...s]                              // Split string into array of chars
 .map(c=>r+=c.charCodeAt(),r=0)      // Sum up ASCII values
 |
 r.toString(2)                       // Convert to binary (represented as string)
 .split`1`.length-1                  // Count occurences of 1

```

# Answer
> 1 votes
## Common Lisp, 53

```
(lambda(s)(logcount(reduce'+(map'list'char-code s))))

```

# Answer
> 1 votes
# PHP, 73 bytes

```
<?=substr_count(decbin(array_sum(array_map(ord,str_split($_GET[s])))),1);

```

save to file, call in browser with `<scriptpath>?s=<string>`

or

```
<?=substr_count(decbin(array_sum(array_map(ord,str_split($argv[1])))),1);

```

save to file, run with `php <scriptpath> <string>`

---

To run without a file, replace `<?=` with `echo<space>` in the second version
and run with `php -r '<code>' <string>`.

# Answer
> 1 votes
## Javascript (ES6), ~~72~~ 70 bytes

Saved 2 bytes thanks to ETHproductions:

```
f=
  (s,p=([c,...d])=>c?c.charCodeAt()+p(d):0,q=n=>n&&n%2+q(n>>1))=>q(p(s))
;
console.log(f('abcDeFAaB'));
```

**Explanation:**

```
(s,                                        //Input string
    p=([c,...d])=>c?c.charCodeAt()+p(d):0, //Recursive method to sum up the ASCII values
    q=n=>n&&n%2+q(n>>1)                    //Recursive method to count 1s in the binary form
)=>q(p(s))

```

---

**Previous solution (72 bytes):**

```
(s,p=([c,...d])=>c?c.charCodeAt()+p(d):0,q=n=>n&&(n&1)+q(n>>1))=>q(p(s))

```

# Answer
> 1 votes
# C#, 51 50 bytes

```
s=>Convert.ToString(s.Sum(x=>x),2).Count(x=>x>48);

```

can be used like this:

```
Func<string, int> f=s=>Convert.ToString(s.Sum(x=>x),2).Count(x=>x>48);
f("abcDeFAaB") // == 7

```

would be so much shorter if Int32.ToString() had a to binary flag.

Edit: saved one byte by converting '0' to int

# Answer
> 0 votes
# Pyth, 8 bytes

```
ssM.BsCM

```

Try it online!

Explanation:

```
      CM  (M)ap ordinals(C) over input
     s    (s)um
   .B     Binary string
 sM       map cast to integer
s         sum

```

# Answer
> 0 votes
## Mathematica, ~~53~~ 37 bytes

not the best solution but hey...built-in's ftw

Shortened. Thanks to Martin Ender

```
DigitCount[Tr@ToCharacterCode@#,2,1]&

```

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


title: Outputting x to y

text:
# Question
Title: Outputting x to y
## Challenge

You must choose one number `x` (`y = x + 9`) and create ten unique programs which each print out one of the numbers in the range `x` to `y` inclusive. However, there are three twists:

* Each program's score is the difference between length of your program in bytes and `n` (where `n` is the number that the program outputs). i.e. If a program is 12 bytes long and it outputs the number 15, its score is 3 (`|15-12| = 3`).
    + You must not use comments to achieve this byte count.
* Your program must not contain any number which is contained within the number which the program outputs. i.e. If a program outputs `1659`, the program cannot contain 1, 6, 5 or 9
* Your program must not contain any of the characters which are the first letters of the number which the program outpts. i.e. If the program outputs `1659`, the program cannot contain o, s, f or n (**o**ne, **s**ix, **f**ive and **n**ine)

## Rules

If any number is impossible, this is counted as a DNP. You should declare all DNPs in your range.

The following is a list of numbers and their spellings. The disallowed characters for each are highlighted in bold:

* 0: **Z**ero
* 1: **O**ne
* 2: **T**wo
* 3: **T**hree
* 4: **F**our
* 5: **F**ive
* 6: **S**ix
* 7: **S**even
* 8: **E**ight
* 9: **N**ine

## Scoring

Your overall score is the sum of all your programs' scores.

## Winning

The person with the lowest score with the fewest DNPs wins.

In the event of a tie, the person whose last edit was earliest wins.

# Answer
# 05AB1E, score = 0

Chosen **x = 1**

**Programs**

**1**: Variable initialized as 1

```
X

```

**2**: zeroth prime number

**3**: first digit of 2^15

```
žG¬

```

**4**: integer root of 16

```
žvtï

```

**5**: first digit of pi + 2

```
žqS¬Ì

```

**6**: first digit of 2nd to last set from the powerset of 256

```
žzœ¨¤¬

```

**7**: the (e // e)th primeth prime

```
žržr÷ØØ

```

**8**: the first 2 digits of the sum of the 10 first multiples of 3, divided by 2

```
TLx+O¨Y÷

```

**9**: ceil(sqrt(sum(range\[1..10\])))+2 XOR 1st prime

```
TLOtîÌXØ^

```

**10**: int(prod(\[1..9\])/2^15)-1

```
žmS¨PžG/ï<

```
> 8 votes

# Answer
# brainfuck, score = 0

Chosen **x = 15**

**15**

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

```

**16**

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

```

**17**

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

```

**18**

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

```

**19**

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

```

**20**

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

```

**21**

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

```

**22**

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

```

**23**

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

```

**24**

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

```

Output is in byte values.
> 5 votes

# Answer
# Jelly, score 0

**x=3**, using ten completely different methods

```
2ÆN          -  3: second prime
6ḃ2S         -  4: sum of digits of 6 in bijective-base 2
2*4BL        -  5: number of bits in 16
2+1R+/       -  6: third triangle number
⁵×ØeḞDṪ      -  7: 1st decimal place of Euler's number
12,6_/+2     -  8: Number of vertices on a cube
ȷ*4×ØPḞDṪ    -  9: the 12th decimal place of pi
9999b9999Ḍ   - 10: decimal of 9999 base 9999
45683g38654  - 11: greatest common divisor of 45683 and its reverse
6RLRL×7RLÆfS - 12: sum of the prime factors of 42 (6*7 is the ultimate question)

```

Run all ten at **TryItOnline**

---

Previous (just another boring answer)

**x=2**

```
1‘          - 1 incremented            1+1 =  2
1‘‘         - 1 incremented twice    1+1+1 =  3
1‘‘‘        - 1 incremented thrice 1+1+1+1 =  4
1‘‘‘‘       -                ... 1+1+1+1+1 =  5
1‘‘‘‘‘      -              ... 1+1+1+1+1+1 =  6
1‘‘‘‘‘‘     -            ... 1+1+1+1+1+1+1 =  7
1‘‘‘‘‘‘‘    -          ... 1+1+1+1+1+1+1+1 =  8
1‘‘‘‘‘‘‘    -        ... 1+1+1+1+1+1+1+1+1 =  9
3‘‘‘‘‘‘‘‘’  - 3 incremented eight times then decremented
                       3+1+1+1+1+1+1+1+1-1 = 10
3‘‘‘‘‘‘‘‘‘’ - 3 incremented nine times then decremented
                     3+1+1+1+1+1+1+1+1+1-1 = 11

```

---

If tie-break is on lowest **x** then for **x=0**

```
          - 0: empty program returns zero
¬         - 1: logical not
¬‘        - 2: logical not then increment
¬‘‘       - 3: logical not then increment twice
¬‘‘‘      - 4: logical not then increment thrice
¬‘‘‘‘     - 5: logical not then increment four times
¬‘‘‘‘‘    - 6: logical not then increment five times
¬‘‘‘‘‘‘   - 7: logical not then increment six times
¬‘‘‘‘‘‘‘  - 8: logical not then increment seven times
¬‘‘‘‘‘‘‘‘ - 9: logical not then increment eight times

```

Run all ten at **TryItOnline**
> 4 votes

# Answer
# Python 2, score 0

x = 14

```
print +2*3+3+5
print 6+2*3+3+0
print 7+2*3+3+00
print 6+2*3+5+0+0
print-~6+2*3+5+0+0
exec"pri\x6et 22-3"
exec"prin\164 9+8+3"
exec"prin\x74 9+9+03"
exec"prin\164-~9+8+04"
exec"prin\164-~9-~8+04"

```
> 2 votes

# Answer
# Emotinomicon, 205 bytes

x = 16

```

71 ⏬⏬
81 ⏬ ⏬
91⏪⏬⏩
02⏬⏬ ℹ
 12⏬⏬ ℹ
22⏪⏬⏬⏩
32 ⏪⏬⏬⏩
42⏬⏬
ℹℹ➕

```

Pro tip: Prepend a  before each snippet to clean the output.
> 1 votes

# Answer
### Pyke, x=2, score 0

```
1h
1hh
1hhh
1hhhh
1hhhhh
1hhhhhh
1hhhhhhh
1hhhhhhhh
ZOhhhhhhhh
ZOhhhhhhhhh

```
> 0 votes

# Answer
### Pyth, x=2, score 0

```
h1
hh1
hhh1
hhhh1
hhhhh1
hhhhhh1
hhhhhhh1
hhhhhhhh1
hhhhhhyyld
hhhhhhhyyld

```
> 0 votes

# Answer
# Mathematica, *x* = 4, score 0

```
3+1&
4+01&
5+001&
6+0001&
7+00001&
8+000001&
8+2+22-22&
9+00000002&
9+000000003&
9+0000000004&

```

Anonymous functions. Take no input and return numbers as output.
> 0 votes

# Answer
# PHP 7 , x=4,score=0

```
2+2;
11-6;
18-12;
3+2**2;
2+2+2+2;
3+2**2+2;
2+2+2+2+2;
3+2**2+2+2;
3*3+3+6-3-3;
4**2-5+2+0*2;

```
> 0 votes

# Answer
## Ru, score = 0

`x = 2`

```
’1
’’1
’’’1
’’’’1
’’’’’1
’’’’’’1
’’’’’’’1
’’’’’’’’1
→’’’’’’’’2
→’’’’’’’’’2

```
> 0 votes

# Answer
## dc, x = 5, score 0

```
# Note: in dc all numbers typed in use the input radix. By default it is 10, which
#means that a number like CF is not 207, but 12*10^1 + 15*10^0 = 135.

CCDap              # 5   print character with the ASCII code  (1333 % 256 =) 53
CCEadp             # 6   print character with the ASCII code  (1334 % 256 =) 54
CCFaddp            # 7   print character with the ASCII code  (1335 % 256 =) 55
ACBAaddp           # 8   print character with the ASCII code (11320 % 256 =) 56
ACBBadddp          # 9   print character with the ASCII code (11321 % 256 =) 57
Addddddddp         #10   print 10 (A)
Bdddddddddp        #11   print 11 (B)
Cddddddddddp       #12   print 12 (C)
Ddddddddddddp      #13   print 13 (D)
Eddddddddddddp     #14   print 14 (E)

```

Comments were added for a better understanding. All the above 10 programs are standalone, but you could have a bonus program that prints all the numbers from 5 to 14, by copy-pasting each code into one single file.
> 0 votes

---
Tags: code-challenge, restricted-source
---


title: Cheating a multiple choice test, part 2

text:
# Question
Title: Cheating a multiple choice test, part 2
This is sequel to this challenge by Adnan. If you like this challenge, chances are you'll like the other one too. Check it out!

---

A multiple choice test with 8 questions each with 4 choices might have the answers: `BCADBADA`. Converted to four different arrays, with true and false if the current letter is the answer, it will look like this

```
Q#: 1  2  3  4  5  6  7  8
    B  C  A  D  B  A  D  A
A: [0, 0, 1, 0, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 0, 0]
C: [0, 1, 0, 0, 0, 0, 0, 0]
D: [0, 0, 0, 1, 0, 0, 1, 0]

```

This can be compressed using a bit of logic. Each of the choices `A`, `B`, `C` and `D` can be represented by two true/false values shown below:

```
A: 1 0
B: 0 1
C: 0 0
D: 1 1

```

Using this logic, we can compress the four vectors above to just two:

```
 1  2  3  4  5  6  7  8
 B  C  A  D  B  A  D  A
[0, 0, 1, 1, 0, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 1, 0]

```

That is, the solution to your test is simply: `00110111`, `10011010`. By concatenating these, we get the binary number `0011011110011010`, or `14234` in decimal. Use this decimal value to cheat on your test!

**Challenge**

Take a number `N` in the (inclusive) range `[0, 65535]`, and output a string with the answer to the multiple choice test.

**Test cases:**

```
14234
BCADBADA

38513
ABBDCAAB

0
CCCCCCCC

120
CBBBBCCC

65535
DDDDDDDD

39253
ABCDABCD

```

The output may be in upper or lower case letters, but you can not use other symbols.

# Answer
# Jelly, 14 bytes

```
d⁹+⁹BZḄḊị“BADC

```

Try it online! or verify all test cases.

### How it works

```
d⁹+⁹BZḄḊị“BADC  Main link. Argument: n

d⁹              Divmod 256; yield [n : 256, n % 256].
  +⁹            Add 256; yield [n : 256 + 256, n % 256 + 256].
    B           Binary; convert both integers to base 2.
     Z          Zip; group the quotient bits with corresponding remainder bits.
      Ḅ         Unbinary; convert from base 2 to integer.
       Ḋ        Dequeue; discard the first integer, which corresponds to the
                dummy value introduced by adding 256 to quotient and remainder.
        ị“BADC  Index into that string, mapping [1, 2, 3, 0] to "BADC".

```
> 3 votes

# Answer
# 05AB1E, ~~19~~ ~~18~~ 16 bytes

### Code:

```
žH+b¦2äøC’c‰±’sè

```

Uses the **CP-1252** encoding. Try it online!

### Explanation:

First, we add `65536` to the number (`žH` is a constant defined to `65536`), which is also `10000000000000000` in binary. This is to pad the number with zeroes. Let's take the number `14234` as an example. `14234 + 65536` is equal to `79770`. Which in binary is:

```
10011011110011010

```

We remove the first character, resulting in:

```
0011011110011010

```

We split the string into two pieces using :

```
00110111, 10011010

```

After that, we zip the array with `ø`:

```
01, 00, 10, 11, 01, 10, 11, 10

```

Converting them back into decimal (using `C`) results in:

```
1, 0, 2, 3, 1, 2, 3, 2

```

Now, we only need to index it with the string `cbad`. The compressed version for this string is `’c‰±’`, which can also be tested here. Finally, we get the characters at the index of the above array. For the above example, this results in:

```
1, 0, 2, 3, 1, 2, 3, 2
b  c  a  d  b  a  d  a

```
> 10 votes

# Answer
## JavaScript (ES6), ~~55~~ 48 bytes

```
f=(n,i=8)=>i--?"CBAD"[n>>i&1|n>>i+7&2]+f(n,i):''

console.log(f(14234)); // BCADBADA
console.log(f(38513)); // ABBDCAAB
console.log(f(0));     // CCCCCCCC
console.log(f(120));   // CBBBBCCC
console.log(f(65535)); // DDDDDDDD
console.log(f(39253)); // ABCDABCD
```

### Non-recursive version (55 bytes)

Using a regular expression, we can do:

```
n=>"76543210".replace(/./g,i=>"CBAD"[n>>i&1|n>>+i+7&2])

```
> 6 votes

# Answer
# Python 2, 53 bytes

```
f=lambda n,k=8:k*'_'and f(n/2,k-1)+'CBAD'[n>>7&2|n&1]

```

Test it on Ideone.
> 4 votes

# Answer
## CP-1610 assembly, 24 DECLEs (30 bytes)

This code is intended to be run on an Intellivision. (1)

A CP-1610 opcode is encoded with a 10-bit value, known as a 'DECLE'. The actual function is 24 DECLEs long, starting at `$4809` and ending at `$4820`.

The CPU registers are however 16-bit wide, so it will support any input value in `0x0000` .. `0xFFFF`.

```
                            ROMW  10            ; use 10-bit ROM
                            ORG   $4800         ; start program at address $4800
4800 0002                   EIS                 ; enable interrupts (to enable display)

                    ;; ---- usage example
4801 0001                   SDBD                ; load parameter in R0
4802 02B8 009A 0037         MVII  #14234, R0    ;
4805 0004 0148 0009         CALL  cheat         ; call function
4808 0017                   DECR  PC            ; infinite loop

                    ;; ---- 'Cheat Your Test' function
                    cheat   PROC

4809 0082                   MOVR  R0,     R2    ; copy R0 to R2
480A 0040                   SWAP  R0            ; swap LSB/MSB in R0
480B 02BC 0214              MVII  #$214,  R4    ; R4 = pointer to 2nd row of screen memory

480D 01DB           @@loop  CLRR  R3            ; clear R3
480E 0052                   RLC   R2            ; extract highest bit of R2 to carry
480F 0053                   RLC   R3            ; inject carry into R3
4810 0050                   RLC   R0            ; extract highest bit of R0 to carry
4811 0053                   RLC   R3            ; inject carry into R3
4812 0001                   SDBD                ; add pointer to lookup table to R3
4813 02FB 001D 0048         ADDI  #@@tbl, R3    ;
4816 029B                   MVI@  R3,     R3    ; read character value
4817 0263                   MVO@  R3,     R4    ; write it to screen memory (also does R4++)
4818 037C 021C              CMPI  #$21C,  R4    ; 8 characters written? ...
481A 0225 000E              BLT   @@loop        ; ... if not, jump to @@loop

481C 00AF                   JR    R5            ; return

481D 011F 0117      @@tbl   DECLE $11F, $117    ; characters 'B', 'C', 'A' and 'D'
481F 010F 0127              DECLE $10F, $127    ; in white, using the built-in font

                            ENDP

```

### Output

---

(1) Granted that at least one compiler, several emulators and copyright-free replacement ROM files are freely available, I think that it doesn't infringe any PPCG submission rule. But please let me know if I'm wrong.
> 4 votes

# Answer
# PHP, 57 Bytes

```
for($i=8;$i--;)echo CBAD[($n=$argv[1])>>$i+7&2|$n>>$i&1];

```

Version without Bitwise operators 70 Bytes

```
for(;$i<8;)echo CABD[($s=sprintf("%016b",$argv[1]))[$i]+$s[8+$i++]*2];

```
> 3 votes

# Answer
# Mathematica, ~~75~~ ~~73~~ ~~68~~ 66 bytes

```
StringPart["CBAD",#+##+1]&@@IntegerDigits[#,2,16]~Partition~8<>""&

```

Thanks to @MartinEnder for saving 2 bytes.
> 3 votes

# Answer
# JavaScript, ~~113~~ ~~93~~ ~~90~~ 88 bytes

*A big thanks to @Neil for helping me save 20 bytes!
-3 bytes thanks to @Cyoce*

~~```
n=>{r="";b=("0".repeat(15)+n.toString(2)).slice(-16);for(i=0;i<8;i++)r+="CBAD"[parseInt(b[i]+b[i+8],2)];return r}

```~~ ~~```
n=>{r="";b=(65536+n).toString(2).slice(1);for(i=0;i<8;i++)r+="CBAD"[+b[i+8]+2*b[i]];return r}

```~~ ~~```
n=>eval('r="";b=(65536+n).toString(2).slice(1);for(i=0;i<8;i++)r+="CBAD"[+b[i+8]+2*b[i]]')

```~~
```
n=>eval('r="";b=n.toString(2).padStart(16,0);for(i=0;i<8;i++)r+="CBAD"[+b[i+8]+2*b[i]]')

```

Sadly, JavaScript lacks functions like `decbin`, `bindec`, and `str_pad` that PHP has.
> 3 votes

# Answer
## CJam, 22 bytes

```
ri2bG0e[8/:.{1$=)^'A+}

```

Try it online!

### Explanation

Powered by magic...

The mapping of bit pairs to letters in this challenge is a bit arbitrary. If we represent `ABCD` by `0, 1, 2, 3` (so we can just add them to the character `A`) then we want the following mapping:

```
i1   i2   o
0    0    2
0    1    1
1    0    0
1    1    3

```

This mapping can be computed with a magical little formula: `((i1 == i2) + 1) ^ i1`, where the equality check returns `0` or `1`. Check out the following table, where each column corresponds to one input, each row corresponds to one operation, and each cell will show the stack at that point:

```
[i1, i2]:  [0, 0]     [0, 1]     [1, 0]     [1, 1]
copy i1:   [0, 0, 0]  [0, 1, 0]  [1, 0, 1]  [1, 1, 1]
equals:    [0, 1]     [0, 0]     [1, 0]     [1, 1]
inc:       [0, 2]     [0, 1]     [1, 1]     [1, 2]
xor:       [2]        [1]        [0]        [3]

```

With that in mind here is the full breakdown of the source code:

```
ri     e# Read input, convert to integer.
2b     e# Get binary representation.
G0e[   e# Pad to 16 bits with zeros.
8/     e# Split into two halves of 8 bits each.
:.{    e# For each pair of bits, i1 and i2...
  1$   e#   Copy i1.
  =    e#   Check equality with i2.
  )    e#   Increment.
  ^    e#   Bitwise XOR.
  'A+  e#   Add to 'A'
}

```

An alternative solution with the same byte count which is decidedly less magical:

```
ri2bG0e[8/z2fb"CBAD"f=

```

And in case it's useful to anyone, if you turn the `i1` and `i2` bits back into a single number (i.e. when you want the mapping `0 -> 2, 1 -> 1, 2 -> 0, 3 -> 3`) this can be computed even more easily as `(~n - 1) & 3` or `(~n - 1) % 4` if your language gets modulo on negative values right. I think this can be written concisely as `3&~-~n` in many languages. In CJam this turns out to be a byte longer, because of the additional conversion back from base 2.
> 3 votes

# Answer
# Perl, 42 bytes

Includes +1 for `-n`

Give input on STDIN:

```
perl -nE 'say+(A..D)[2-($`>>8-$_&257)%127]for/$/..8' <<< 39253

```

Just the code:

```
say+(A..D)[2-($`>>8-$_&257)%127]for/$/..8

```
> 3 votes

# Answer
# MATL, 16 bytes

```
16&B8eXB'BADC'w)

```

**Try it Online!**

or Verify all test cases

**Explanation**

```
        % Implicitly grab input
16&B    % Convert to binary string with at least 16 bits
8e      % Reshape the resulting string to have 8 rows and 2 columns
XB      % Convert each row from binary to decimal
'BADC'  % Push this string literal
w)      % Use the decimal numbers to index into this string (modular indexing)
        % Implicitly display the resulting string

```
> 1 votes

# Answer
# Julia, 73 Bytes

Gives a function f taking N as input and returning the answer as string.

```
f(N)=(b=bin(N,16);join(["CBAD"[parse("0b$(b[i])$(b[i+8])")+1]for i=1:8]))

```

Try it

Depending if a char array counts as string, one can omit the join (**67 Bytes**)

```
f(N)=(b=bin(N,16);["CBAD"[parse("0b$(b[i])$(b[i+8])")+1]for i=1:8])

```

Try it
> 1 votes

# Answer
## R, 110 bytes

Came up with a vectorized solution in R. This should probably by golfable by coming up with a smarter conversion int to binary conversion.

```
x=as.integer(intToBits(scan()));cat(LETTERS[1:4][match(paste0(x[16:9],x[8:1]),c("10","01","00","11"))],sep="")

```
> 0 votes

---
Tags: code-golf, string, base-conversion
---


title: How many electrons are in each shell?

text:
# Question
Title: How many electrons are in each shell?
Given a atomic number, print how many electrons are in each shell of the element that the atomic number corresponds to.

## Expected input/output:

```
Input -> Output
1 -> 1
2 -> 2
3 -> 2, 1
4 -> 2, 2
5 -> 2, 3
6 -> 2, 4
7 -> 2, 5
8 -> 2, 6
9 -> 2, 7
10 -> 2, 8
11 -> 2, 8, 1
12 -> 2, 8, 2
13 -> 2, 8, 3
14 -> 2, 8, 4
15 -> 2, 8, 5
16 -> 2, 8, 6
17 -> 2, 8, 7
18 -> 2, 8, 8
19 -> 2, 8, 8, 1
20 -> 2, 8, 8, 2
21 -> 2, 8, 9, 2
22 -> 2, 8, 10, 2
23 -> 2, 8, 11, 2
24 -> 2, 8, 13, 1
25 -> 2, 8, 13, 2
26 -> 2, 8, 14, 2
27 -> 2, 8, 15, 2
28 -> 2, 8, 16, 2
29 -> 2, 8, 18, 1
30 -> 2, 8, 18, 2
31 -> 2, 8, 18, 3
32 -> 2, 8, 18, 4
33 -> 2, 8, 18, 5
34 -> 2, 8, 18, 6
35 -> 2, 8, 18, 7
36 -> 2, 8, 18, 8
37 -> 2, 8, 18, 8, 1
38 -> 2, 8, 18, 8, 2
39 -> 2, 8, 18, 9, 2
40 -> 2, 8, 18, 10, 2
41 -> 2, 8, 18, 12, 1
42 -> 2, 8, 18, 13, 1
43 -> 2, 8, 18, 13, 2
44 -> 2, 8, 18, 15, 1
45 -> 2, 8, 18, 16, 1
46 -> 2, 8, 18, 18
47 -> 2, 8, 18, 18, 1
48 -> 2, 8, 18, 18, 2
49 -> 2, 8, 18, 18, 3
50 -> 2, 8, 18, 18, 4
51 -> 2, 8, 18, 18, 5
52 -> 2, 8, 18, 18, 6
53 -> 2, 8, 18, 18, 7
54 -> 2, 8, 18, 18, 8
55 -> 2, 8, 18, 18, 8, 1
56 -> 2, 8, 18, 18, 8, 2
57 -> 2, 8, 18, 18, 9, 2
58 -> 2, 8, 18, 19, 9, 2
59 -> 2, 8, 18, 21, 8, 2
60 -> 2, 8, 18, 22, 8, 2
61 -> 2, 8, 18, 23, 8, 2
62 -> 2, 8, 18, 24, 8, 2
63 -> 2, 8, 18, 25, 8, 2
64 -> 2, 8, 18, 25, 9, 2
65 -> 2, 8, 18, 27, 8, 2
66 -> 2, 8, 18, 28, 8, 2
67 -> 2, 8, 18, 29, 8, 2
68 -> 2, 8, 18, 30, 8, 2
69 -> 2, 8, 18, 31, 8, 2
70 -> 2, 8, 18, 32, 8, 2
71 -> 2, 8, 18, 32, 9, 2
72 -> 2, 8, 18, 32, 10, 2
73 -> 2, 8, 18, 32, 11, 2
74 -> 2, 8, 18, 32, 12, 2
75 -> 2, 8, 18, 32, 13, 2
76 -> 2, 8, 18, 32, 14, 2
77 -> 2, 8, 18, 32, 15, 2
78 -> 2, 8, 18, 32, 17, 1
79 -> 2, 8, 18, 32, 18, 1
80 -> 2, 8, 18, 32, 18, 2
81 -> 2, 8, 18, 32, 18, 3
82 -> 2, 8, 18, 32, 18, 4
83 -> 2, 8, 18, 32, 18, 5
84 -> 2, 8, 18, 32, 18, 6
85 -> 2, 8, 18, 32, 18, 7
86 -> 2, 8, 18, 32, 18, 8
87 -> 2, 8, 18, 32, 18, 8, 1
88 -> 2, 8, 18, 32, 18, 8, 2
89 -> 2, 8, 18, 32, 18, 9, 2
90 -> 2, 8, 18, 32, 18, 10, 2
91 -> 2, 8, 18, 32, 20, 9, 2
92 -> 2, 8, 18, 32, 21, 9, 2
93 -> 2, 8, 18, 32, 22, 9, 2
94 -> 2, 8, 18, 32, 24, 8, 2
95 -> 2, 8, 18, 32, 25, 8, 2
96 -> 2, 8, 18, 32, 25, 9, 2
97 -> 2, 8, 18, 32, 27, 8, 2
98 -> 2, 8, 18, 32, 28, 8, 2
99 -> 2, 8, 18, 32, 29, 8, 2
100 -> 2, 8, 18, 32, 30, 8, 2
101 -> 2, 8, 18, 32, 31, 8, 2
102 -> 2, 8, 18, 32, 32, 8, 2
103 -> 2, 8, 18, 32, 32, 8, 3
104 -> 2, 8, 18, 32, 32, 10, 2
105 -> 2, 8, 18, 32, 32, 11, 2
106 -> 2, 8, 18, 32, 32, 12, 2
107 -> 2, 8, 18, 32, 32, 13, 2
108 -> 2, 8, 18, 32, 32, 14, 2
109 -> 2, 8, 18, 32, 32, 15, 2
110 -> 2, 8, 18, 32, 32, 16, 3
111 -> 2, 8, 18, 32, 32, 17, 2
112 -> 2, 8, 18, 32, 32, 18, 2
113 -> 2, 8, 18, 32, 32, 18, 3
114 -> 2, 8, 18, 32, 32, 18, 4
115 -> 2, 8, 18, 32, 32, 18, 5
116 -> 2, 8, 18, 32, 32, 18, 6
117 -> 2, 8, 18, 32, 32, 18, 7
118 -> 2, 8, 18, 32, 32, 18, 8

```

Psst... take a closer look at the output, it's not always the last shell incrementing.

Remember, this is , so the code with the smallest number of bytes wins.

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=94753,OVERRIDE_USER=12537;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# Mathematica, 42 bytes

```
Tr/@#~ElementData~"ElectronConfiguration"&

```
> 0 votes

---
Tags: code-golf
---


title: Mutilating the Query

text:
# Question
Title: Mutilating the Query
I know you've always thought about the trials and tribulations of experiencing the joys of life as a web proxy. Honestly, who hasn't? Today you're tasked with realizing this goal (at least a part of it). Website X gets a lot of traffic on the daily and is looking for a PaaS (clearly this refers to Proxy as a Service) because of the large number of users who insist on passing sensitive information via query parameters (users are silly). Your task is to remove any and all sensitive query parameters from the request before forwarding the request through to its original destination.

## Input

* A well-formed absolute HTTP URL that follows the URI grammar in RFC3986 Section 3.
    + You can assume there is no fragment
    + Brief format example where anything in square brackets denotes optional: `http[s]://[user:pass@]host.name.com[:port]/[?param1=value1&param2=value2...]`
* A list of query parameters to be removed.

## Output

The modified HTTP URL without the parameters defined in the input list.

## Examples

```
http://example.com/ [foo]
> http://example.com/

http://example.com/?foo=bar []
> http://example.com/?foo=bar

http://example.com/ []
> http://example.com/

http://example.com/?foo=1&bar=2&baz=3 [foo,baz]
> http://example.com/?bar=2

http://example.com/?foo=1&bar=2&baz=3 [foo,bar,baz]
> http://example.com/

http://example.com/?foo&bar=2&baz= [foo,baz]
> http://example.com/?bar=2

http://example.com/?abc=1&def=2&baz=foo [foo,bar]
> http://example.com/?abc=1&def=2&baz=foo

http://example.com/?foobar=baz [foo]
> http://example.com/?foobar=baz

http://foo:foo@foo.com:8080/?foo=1&bar=foo [foo]
> http://foo:foo@foo.com:8080/?bar=foo

```

## Scoring

This is , so the shortest answer (in bytes) wins.

# Answer
# GNU sed 98 96 88 80 77 74 69 59 54 (48 + 1 for -r) 49

```
:;s,(.+)(=[^&]*[& ]|&)(.*)\1,\3 ,
t;s,[?&]? .*,,

```

The list of parameters to remove are separated by spaces.

```
$ echo 'http://example.com/?foo=1&bar=2&baz=3 foo bar baz' | sed -rf sed.txt
http://example.com/

$ echo 'http://example.com/?foo&bar=2&baz= foo baz' | sed -rf sed.txt
http://example.com/?bar=2

$ echo 'http://example.com/' | sed -rf sed.txt
http://example.com/

```
> 6 votes

# Answer
## JavaScript (ES6), ~~62~~ 60 bytes

```
f=
(s,a,u=new URL(s))=>a.map(e=>u.searchParams.delete(e))&&''+u
;
s.value=document.URL;
```

```
<div oninput=o.textContent=f(s.value,a.value.split`\n`)><input id=s><br><textarea id=a></textarea><pre id=o>
```

Edit: Saved 2 bytes thanks to @Shaggy.
> 5 votes

# Answer
# PHP, 90 Bytes

```
<?=trim(preg_replace("#(?<=\?|&)(".join("|",$_GET[r]).")(=.*)?(&|$)#U","",$_GET[u]),"?&");

```

-11 Bytes if ? or & is allowed at the end

Previous Version 140 Bytes

```
<?=substr($u=$_GET[u],0,strpos($u,"?")+!!$j=join("&",preg_grep("#^(".join("|",$_GET[r]).")(=|$)#",explode("&",parse_url($u)[query]),1))).$j;

```
> 3 votes

# Answer
# C#, ~~377~~ ~~336~~ ~~330~~ 328 bytes (173 alt)

```
string n(string u,string[]r){var s=u.Split('?');if(s.Length<2)return u;var a=s[1].Contains("&")?s[1].Split('&'):new string[]{s[1]};int B=a.Length,i=0,C=i,c=B;for(;i<B;i++)foreach(var R in r)if(R==a[i].Split('=')[0]){a[i]="";c--;}var t=s[0];t+=c>0?"?":"";for(i=0;i<a.Length;i++)if(a[i]!=""){t+=a[i];C++;if(C!=c)t+="&";}return t;}

```

Ungolfed full program:

```
using System;
class a
{
    static void Main()
    {
        string input = Console.ReadLine();
        string url = input.Split(' ')[0];
        string r = input.Split(' ')[1];
        r = r.Replace("[", "").Replace("]","");
        string[] remove = r.Split(',');
        a b = new a();
        Console.WriteLine(b.n(url, remove));
    }
    string n(string u,string[]r)
    {
        var s=u.Split('?');
        if(s.Length<2)return u;
        var a=s[1].Contains("&")?s[1].Split('&'):new string[]{s[1]};
        int B=a.Length,i=0,C=i,c=B;
        for(;i<B;i++)
            foreach(var R in r)
                if(R==a[i].Split('=')[0])
                {
                    a[i]="";
                    c--;
                }
        var t=s[0];
        t+=c>0?"?":"";
        for(i=0;i<a.Length;i++)
            if(a[i]!="")
            {
                t+=a[i];
                C++;
                if (C!=c)t+="&";
            }
        return t;
    }
}

```

Probably not very efficient, but it works I think.

Alternatively, there is a 173 byte solution using @Poke's method from Java. Requires an import for Regex though, so probably can't be shorter.

```
using System.Text.RegularExpressions;string m(string a,string[]b){foreach(var c in b)a=Regex.Replace(a,$"(?<=[?&]){c}(=[^&]*)?(&|$)","");return Regex.Replace(a,"[?&]$","");}

```
> 2 votes

# Answer
# Java 7, 127 bytes

```
String a(String a,String[]b){for(String c:b)a=a.replaceAll("(?<=[?&])"+c+"(=[^&]*)?(&|$)","");return a.replaceAll("[?&]$","");}

```

## Explanation

```
String sanitize(String url, String[] params) {
    for (String param : params) {
        // please don't modify function parameters in real code
        url=url.replaceAll("(?<=[?&])" // Look for a leading ? or & but don't consume it
            + param                    // Consume the key of the query param (assuming key=value syntax)
            + "(=[^&]*)?"              // Consume the value of the query param if it exists
            + "(&|$)","");             // Consume the trailing & unless we're at the end of the url and replace with nothing
    }
    url = url.replaceAll("[?&]$",""); // If we remove all of the params then we'll have a trailing ? which needs to be removed
                                      // If we remove the last param only then we could have a trailing & which also needs to be removed
                                      // We will only run into one of these scenarios
    return url;
}

```

Ideone
> 2 votes

# Answer
# PHP, ~~120~~ 110 bytes

with preg\_replace and array functions: (inspired by Jörg)

```
<?=preg_replace(array_map(function($s){return"#(\\?|&)$s(=.*)?(&|$)#U";},array_slice($argv,2)),"\1",$argv[1]);

```

save to file, call with `php <scriptname> <uri> <parametername> <parametername> ...`

with parse\_str and http\_build\_query (120 bytes):

```
parse_str(end($u=explode('?',$argv[1])),$a);for($i=$argc;$i-->1;)unset($a[$argv[$i]]);echo"$u[0]?".http_build_query($a);

```

run with `php -r <code> <uri> <parametername> <parametername> ...`
> 2 votes

# Answer
# Ruby, ~~146 140 127 119 116~~ 113 bytes

edit 2: saved 6 bytes by using `$1`, `$2`, and `$*`, and 7 by changing `x.split("=")[0]` to `x[/\w+/]`
edit 3: saved 6 bytes by using `*` instead of `.join`, saved 2 bytes from unnecessary spaces
edit 4: saved 3 bytes by reformulating inline (changed regex to equivalent `$*[1][/([^?]*)\??(.*)/,1]` and put as assigned to `a`)
edit 5: saved 3 bytes by using `($*[2].scan(r=/\w+/)&[x[r]])[0]` instead of `$*[2].scan(r=/\w+/).include?(x[r])`

Assuming input to the program when running it:

```
a,b=$*[1][/([^?]*)\??(.*)/,1],$2.split("&").reject{|x|($*[2].scan(r=/\w+/)&[x[r]])[0]}*"&"
puts(b[0] ?a+"?"+b: a)

```

## Explanation

```
a,b=$*[1][/([^?]*)\??(.*)/,1],$2.split("&")

```

This parses the URL given on the command line, and stores the matches into `$1` and `$2`. `$*[1][/([^?]*)\??(.*)/,1]` also returns the first match to store inside `a`, while the second match is referred to as `$2` let a point to $1, and parse `b` into an array of arrays...

```
.reject { |x|

```

...rejecting all that...

```
    ($*[2].scan(r=/\w+/)&[x[r]])[0]

```

...have a string before the '=' that is included in the list of names given by the second parameter... This works because we scan for words (to get the list) then get the word before the `=`, and see if that word is in the list with `&`. Since `&` returns an empty array on "not found" (the null set), we use the trick explained below to get `nil` if there are no elements in the array. otherwise we return a string, which counts as truthy, which rejects that string.

```
}*"&"

```

...and join the remaining strings together with '&'

At this point, `b` is the GET query string for the URL. Thus, we just need to print it.

```
puts(b[0] ?a+"?"+b: a)

```

This uses a trick in ruby. `b[0]` will be `nil` if b is an empty array or string. So if its *truthy*, (not `nil` or `false`), then there's at least one element in the array, so we need to puts `a+"?"+b` for the correct URL. otherwise, we just puts `a`, because there are no parameters to show

Note: this answer assumes that `?` *cannot* appear anywhere except to delimit the URL from the query. (according to what I read from the linked RFC)

Also, this is my first golf answer :D
> 2 votes

# Answer
## PowerShell v3+, ~~115~~ 90 bytes

```
param($n,$z)$a,$b=$n-split'\?';($z|%{$b=$b-replace"(^|&)$_(=[^&]*)?(&|$)"});$a+"?"*!!$b+$b

```

Takes input `$n` as the URL and `$z` as a literal array of strings as the parameters to remove. `-split`s the input URL on `?`, stores the first half into `$a` and the second into `$b`.

Next, `$b` is re-formulated by taking a loop through `$z`, performing a regex `-replace` on each banned query word to remove them. Then, outputs `$a` (unmodified), plus a `/` depending upon whether `$b` exists, plus a `?` depending upon whether `$x` exists, plus \`$x.
> 1 votes

# Answer
## Pip, 46 bytes

Takes the URL from stdin and the query parameters for removal from command-line args.

```
YgqR`\?.+`{s:J_@`^[^=]+`NIyFI@>a^'&[s&'?sJ'&]}

```

Try it online!

Explanation:

```
 g               Local variable containing list of cmdline args
Y                Yank into global variable y so it's available inside the function
  q              Grab a line of stdin
   R`\?.+`{...}  Do a regex replace of everything from ? on, using a callback function:

s:J_@`^[^=]+`NIyFI@>a^'&[s&'?sJ'&]
                  @>a^'&            All but 1st char of match, split on &
                FI                  Filter on this function:
   _@`^[^=]+`                         Regex match: run of non = from beginning of string
                                      @ returns a list (here, of one item), so...
  J                                   Join to get a scalar
             NIy                      True if match not in y; false if in y
s:                                  Assign the filtered list to s
                        [        ]  Return a list containing:
                         s&'?       ? if s is nonempty, [] otherwise
                             sJ'&   s joined on &
                                    When used as a replacement, a list is first stringified
                                    (which, in the absence of flags, means concatenated)

```
> 1 votes

# Answer
# Pyth - 27 bytes

Kenny was right when he talked about the builtin to transform and then invert, it'll be very hard to right, though.

```
.sjK\?mj\&f!}hcT\=Qcd\&czKK

```

Test Suite.
> 1 votes

# Answer
## Retina, ~~44~~ 48 bytes

<sub>*Crossed-out 44 is still 44. Thanks to Martin for the fix.*</sub>

```
[?&](?>([^ =&]+))[^ &]*(?=.* \1( |$))| .*

/&
/?

```

Takes input like `uri param1 param2`. Try it online!

### Explanation

The first replacement deletes the appropriate parameters from the query string. `[?&](?>([^ =&+))[^ &]*` matches a `?` or `&`, a full parameter name, and (optionally) `=` and a value, storing the parameter name in capture group 1. Then `(?=.* \1( |$))` is a lookahead that checks whether that parameter name appears in the list of parameters to delete. If a parameter matches these conditions, it is removed (substituted with an empty replacement).

Substitutions are non-overlapping (thanks to the lookahead) and proceed from left to right. On reaching the end of the URL, the  `.*` branch matches the list of parameters to delete and removes it as well.

The second replacement just makes sure the new query string starts with `?` if the first parameter was deleted.
> 1 votes

# Answer
# Java 7, 203 bytes

```
String f(String u,List p)throws Exception{String[]g=u.split("\\?",2);String s="";if(g.length>1)for(String q:g[1].split("&")){if(p.indexOf(q.split("=")[0])<0){s+=s.isEmpty()?"?":"&";s+=q;}}return g[0]+s;}

```

Ungolfed:

```
  String f(String u, List p) throws Exception {
    String[] g = u.split("\\?", 2);
    String s = "";
    if (g.length > 1) for (String q : g[1].split("&")) {
      if (p.indexOf(q.split("=")[0]) < 0) {
        s += s.isEmpty() ? "?" : "&";
        s += q;
      }
    }
    return g[0] + s;
  }

```

This function passes all of the tests.
> 0 votes

# Answer
# Python, ~~75~~ ~~81~~ 112 bytes:

```
def Z(A,S):import re;F=A.rindex('/');print A[:F]+re.sub('|'.join(i+'(=\d?|&)&?'for i in S),'',A[F:]).strip('&?')

```

A named function. Takes input in the format

```
D(<String>,<Array>)

```

and outputs a string.

Repl.it With All Test Cases!
> 0 votes

# Answer
# PHP, not competing

Heck, PHP was made for this; why not use the actual URL?

```
<?foreach($_GET[x]as$w)unset($_GET[$w]);
echo http,s[$_SERVER[SERVER_PORT]-443],"://",
$u=$_SERVER[PHP_AUTH_USER],($p=$_SERVER[PHP_AUTH_PW])?":$p":"","@"[!$u&!$p],
"$_SERVER[HTTP_HOST]$_SERVER[SCRIPT_NAME]?",http_build_query($_GET);

```

Save to file, call with your wanted query string plus `&x[]=x&x[]=<exclude1>&x[]=<exclude2>&...`.

May fail on username and password (depending on wether your browser removes them or not).
*Will* fail if password is `0`.
> 0 votes

---
Tags: code-golf
---


title: Perform Dempster's Rule of Combination

text:
# Question
Title: Perform Dempster's Rule of Combination
## Crash Course on DST

Dempster–Shafer theory (DST) provides a method to combine various sources of evidence to form a belief. Given a list of possible statement (one of which is the true answer), each possible *combination* of statements is assigned a "mass" indicating the degree of supporting evidence. The total mass of all combinations is always equal to 1.

From these mass assignments, we can create a reasonable lower bound (belief) and upper bound (plausibility) on the truth of that combination. The belief `bel(X)` of any set X is the sum of the masses of all of X's subsets (including itself). The plausibility `pl(X)` of any set X is "1 - the sum of the masses of all sets disjoint to X". The diagram below illustrates how belief and plausibility are related to uncertainty.

For example, let's say that there is a traffic light that could be one of either `G`reen, `Y`ellow, or `R`ed. The list of options and a possible mass assignment is shown below:

```
binary    interpretation    m(X)    bel(X)  pl(x)
000       null              0       0       0
001       R                 0.2     0.2     0.7
010       Y                 0.1     0.1     0.3
011       Y||R              0.05    0.35    0.8
100       G                 0.2     0.2     0.65
101       G||R              0.3     0.7     0.9
110       G||Y              0       0.3     0.8
111       G||Y||R           0.15    1       1

```

These masses can be notated by an array `[0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15]`.

Now the question is, how do we decide what the masses are? Let's say that we had a sensor looking at the light, and this sensor indicates that the light *not green*; however, we know that there's a 20% chance that the sensor sent a random, spurious signal. This piece of evidence can be described by the mass distribution `[0, 0, 0, 0.8, 0, 0, 0, 0.2]` where {Y,R} has a mass of 0.8 and {G,Y,R} has a mass of 0.2.

Similarly, let's say that some second sensor indicates that the light is *not red*, but we also know that there's a 30% chance the sensor is wrong and the light is actually red. This piece of evidence can be describe by `[0, 0.3, 0, 0, 0, 0, 0.7, 0]` where {G,Y} has a mass of 0.7 and {R} has a mass of 0.3.

To assimilate these two pieces of evidence to form a single mass distribution, we can use Dempster's Rule of Combination.

## Dempster's Rule of Combination

Two mass assignment `m1` and `m2` can be combined to form `m1,2` using the following formulas, where `A`, `B` and `C` represent possible combinations (rows of the table above).

where K is a measure of "conflict," used for renormalization, and is calculated by:

It is also possible to describe this process geometrically, as in the image below. If `A = 011` (Yellow or Red) and `B = 101` (Green or Red), then the value of `m1(A) * m2(B)` *contributes to* (is added to) the value of `m1,2(001)` (Red). This process is repeated for all possible combinations of A and B where `A&B != 0`. Finally, the array is renormalized so that the values add up to a total of 1.

Here is a simple Java method that combines two arrays following Dempster's rule:

```
public static double[] combine(double[] a, double[] b) {
  double[] res = new double[a.length];
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      res[i & j] += a[i] * b[j];
    }
  }
  for (int i = 1; i < res.length; i++) {
    res[i] /= 1 - res[0];
  }
  res[0] = 0;
  return res;
}

```

To see how this works in practice, consider the traffic light sensors above, which independently give the masses `[0, 0, 0, 0.8, 0, 0, 0, 0.2]` and `[0, 0.3, 0, 0, 0, 0, 0.7, 0]`. After performing Dempster's rule, the resulting *joint mass* is `[0, 0.3, 0.56, 0, 0, 0, 0.14, 0]`. The majority of mass is assigned to "Yellow", which makes intuitive sense given that the two sensors returned "not green" and "not red" respectively. The other two masses (0.3 for "Red" and 0.14 for "Green or Yellow") are due to the uncertainty of the measurements.

## The Challenge

Write a program that takes two lists of real numbers and outputs the result of applying Dempster's rule to the two input lists. The lengths of the two input lists will equal, and that length will be a power of 2, and will be at least 4. For each list, the first value will always be 0 and the remaining values will all be non-negative and add up to 1.

Output should be a list with the same length as the input lists. You can assume that a solution exists (it is possible for a solution to not exist when there is total conflict between evidence and thus K=1). To place a minimum requirement on precision, your program must be able to produce results that are accurate when rounded to four decimal places.

## Example I/O

```
in:
[0, 0, 0, 0.8, 0, 0, 0, 0.2]
[0, 0.3, 0, 0, 0, 0, 0.7, 0]
out:
[0.0, 0.3, 0.56, 0.0, 0.0, 0.0, 0.14, 0.0]

in:
[0.0, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.4]
[0.0, 0.2, 0.0, 0.2, 0.0, 0.2, 0.0, 0.4]
out:
[0.0, 0.2889, 0.0889, 0.1556, 0.0889, 0.1556, 0.0444, 0.1778]

in:
[0.0, 0.0, 0.5, 0.5]
[0.0, 0.7, 0.1, 0.2]
out:
[0.0, 0.53846, 0.30769, 0.15385]

in:
[0.0, 0.055, 0.042, 0.098, 0.0, 0.152, 0.0, 0.038, 0.031, 0.13, 0.027, 0.172, 0.016, 0.114, 0.058, 0.067]
[0.0, 0.125, 0.013, 0.001, 0.012, 0.004, 0.161, 0.037, 0.009, 0.15, 0.016, 0.047, 0.096, 0.016, 0.227, 0.086]
out: (doesn't have to be this precise)
[0.0, 0.20448589713416732, 0.11767361551134202, 0.028496524069011694, 0.11809792349331062, 0.0310457664246791, 0.041882026540181416, 0.008093533320057205, 0.12095719354780314, 0.11306959103499466, 0.06412594818690368, 0.02944697394862137, 0.06398564368086611, 0.014369896989336852, 0.03774983253978312, 0.006519633578941643]

in:
[0.0, 0.0, 0.1, 0.1, 0.0, 0.0, 0.0, 0.1, 0.1, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.1, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.1, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.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.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.1, 0.0]
out:
[0.0, 0.09090909090909094, 0.23376623376623382, 0.0, 0.07792207792207795, 0.025974025974026, 0.03896103896103895, 0.0, 0.10389610389610393, 0.05194805194805199, 0.02597402597402597, 0.0, 0.012987012987012984, 0.012987012987012993, 0.012987012987012984, 0.0, 0.09090909090909094, 0.038961038961038995, 0.06493506493506492, 0.0, 0.07792207792207796, 0.0, 0.0, 0.0, 0.012987012987012984, 0.012987012987013, 0.012987012987012984, 0.0, 0.0, 0.0, 0.0, 0.0]

```

# Answer
> 2 votes
# Perl, 68 bytes

Includes +2 for `-an`

Give the first set as row and the second as a column on STDIN

```
perl -M5.010 dempster.pl
0.0  0.0  0.5  0.5
0.0
0.7
0.1
0.2
^D
^D

```

`dempster.pl`:

```
#!/usr/bin/perl -an
/$/,map$H[$m%@F&$m++/@F]+=$_*$`,@F for<>;say$%++&&$_/(1-"@H")for@H

```

A pretty standard golf solution. Doesn't work if I replace `@H` by `@;`

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