title: Factory workers

text:
# Question
Title: Factory workers
# Challenge

Factory workers are usually very hard-working. However, their work is now being commonly replaced with machines.

You have to write a program that takes a number as input. It will print out a factory of 10 workers 10 times. Every time, each worker has a `1/input` chance of being 'fired' and replaced by a machine.

## Input

An integer, coming from STDIN or a function call.

## Output

10 cases of the factory, each one with usually more workers fired.

# Output format - how to print a factory

A factory looks like this:

`|0000000000|` or `|0000011001|`

A pipe represents the walls, a 0 represents a worker, and a 1 represents a machine, so the first print of the factory will always be `|0000000000|`.

# Example

### Input: 10

### Output:

```
|0000000000| //always start off with this
|0000000010| //a 1/10 chance means that this worker lost his job
|0000010010|
|0010010010|
|1010010010|
|1010110010|
|1010110011|
|1010111011|
|1010111111|
|1110111111|

```

---

### Input: 5

### Output:

```
|0000000000| //always start here
|0000001001| //a 1/5 chance means that 2 workers got fired
|1000101001|
|1000101111|
|1101101111|
|1111111111| //after achieving all machinery, the machines continue to be printed
|1111111111|
|1111111111|
|1111111111|
|1111111111|

```

# NOTE

The number of workers fired is RANDOM - in my examples for `1/5 chance` there would always be 2 workers fired but your program has to do this randomly - sometimes 1 and sometimes 3 - they just have 1/5 chance of being fired.

# Answer
> 7 votes
# Japt `-R`, ~~22~~ ~~21~~ ~~20~~ ~~19~~ 18 bytes

```
AÆP=®|!UöÃªAçTÃû|C

```

Try it

---

## Explanation

```
AÆP=®|!UöÃªAçTÃû|C     :Implicit input of integer U
A                      :10
 Æ                     :Map the range [0,A)
  P=                   :  Assign to P (initially the empty string)
    ®                  :    Map P
     |                 :      Bitwise OR with
      !                :      The negation of
       Uö              :      A random integer in the range [0,U)
         Ã             :    End Map
          ª            :    OR, for the first element when the above will still be an empty string (falsey)
           Aç          :    Ten times repeat
             T         :      Zero
              Ã        :End Map
               û|      :Centre pad each element with "|"
                 C     :  To length 12
                       :Implicitly join with newlines and output

```

# Answer
> 7 votes
# , ~~92~~ 89 bytes

```
cat(t(cbind("|",apply("[<-"(matrix(runif(100)<1/scan(),10),1,,0),2,cummax),"|
")),sep="")

```

Try it online!

Ungolfed:

```
m <- matrix(runif(100)<1/n,10,10)   #10x10 matrix of TRUE with probability 1/n
                                    #and FALSE with probability 1-1/n
m[1,] <- 0                          #set first row to 0
m <- apply(m,2,cummax)              #take the column cumulative maxima
m <- cbind("|",m,"|\n")             #put "|" as the first and last columns
m <- t(m)                           #transpose m for the write function
cat(m,sep="")                       #print m to stdout, separated by ""

```

# Answer
> 6 votes
# JavaScript (ES6), 84 bytes

```
n=>[...s=2e9+''].map(j=>`|${s=s.replace(/./g,i=>i&1|Math.random()*n<!+j)}|`).join`
`

```

Try it online!

---

# Recursive version, 88 bytes

```
n=>(g=k=>k?`|${s=s.replace(/./g,i=>i%5|Math.random()*n<(s!=k))}|
`+g(k>>3):'')(s=5e9+'')

```

Try it online!

### How?

We start with **k = s = '5000000000'**.

At each iteration:

* We coerce each character **i** of **s** to a number, compute **i modulo 5** -- so that the leading **5** is treated like a **0** -- and randomly perform a bitwise OR with **1** with the expected probability **1/n**, except on the first iteration.
* The counter **k** is right-shifted by 3 bits. We stop the recursion as soon as **k = 0**, which gives 10 iterations.

It is important to note that **5000000000** is slightly larger than a 32-bit integer, so it is implicitly converted to **5000000000 & 0xFFFFFFFF = 705032704** just before the first bitwise shift occurs. Hence the following steps:

```
 step | k
------+-----------
   0  | 705032704
   1  | 88129088
   2  | 11016136
   3  | 1377017
   4  | 172127
   5  | 21515
   6  | 2689
   7  | 336
   8  | 42
   9  | 5
  10  | 0

```

# Answer
> 4 votes
# APL (Dyalog), 37 bytes

```
⎕{⎕←' '~⍨⍕'|'⍵'|'⋄×⍵+⍺=?10⍴⍺}⍣10⊢10⍴0

```

Try it online!

**How?**

`10⍴0` \- start with 10 zeros.

`⎕←' '~⍨⍕'|'⍵'|'` \- every time print the formatted array,

`?10⍴⍺` \- generate a random array with values ranging `1` to input,

`⍺=` \- element-wise comparison with the input. should mark `1` / input of the elements, giving each a `1` / input every time,

`⍵+` \- add to the array,

`×` \- signum. zero stays zero, anything greater than one comes back to one.

`⍣10` \- repeat 10 times.

# Answer
> 3 votes
# PowerShell, ~~82~~ ~~80~~ 69 bytes

```
param($x)($a=,0*10)|%{"|$(-join$a)|";$a=$a|%{$_-bor!(Random -ma $x)}}

```

Try it online!

Takes input `$x`. Creates an array of all zeros, saves that into `$a` and then loops that many times. Conveniently, the factory is just as wide as it is iterations worth. Each iteration, we output our current factory with `"|$(-join$a)|"`, then loop through each element of `$a`.

Inside we're selecting the current element `$_` that has been `-b`inary-`or`ed with either `1` based on the `Random` chance based on input `$x`. For example, for input `10`, `Get-Random -max 10` will range between `0` and `9` and be `0` approximately 1/10th of the time. Thus with a `!(...)` wrapping the `Random`, we'll get a `1` approximately `1/input` amount of the time, and the other `1-1/input` amount of the time we'll get `$_`. Yes, this sometimes means that we're overwriting a `1` with another `1`, but that's fine.

That resulting array is then stored back into `$a` for the next go-round. All of the resulting strings are left on the pipeline, and the implicit `Write-Output` at program completion gives us newlines for free.

*-2 bytes thanks to Veskah.*
*-11 bytes thanks to ASCII-only.*

# Answer
> 3 votes
# Retina, 30 bytes

```
.+
|¶10*$(*0¶
.-10+0\%0<@`\d
1

```

Try it online!

I'm having lots of fun with randomness in Retina^^

### Explanation

The first stage sets up the string we will be working with:

```
.+
|¶10*$(*0¶

```

It replaces the whole input with `|`, a newline, and then 10 lines containing as many `0`s as the input says. The first character on each line will represent a worker of the factory.

The following stage means:

```
.                     Disable automatic printing at the end of the program
 -10+                 Do the following exactly 10 times:
       %                For each line:
        0<                Print the first character, then
          @`\d            Pick a random digit and
1 (on the next line)      replace it with a 1
     0\                 Then print the first character of the whole string
                        followed by a newline

```

The first line of the working string contains only a `|`, which will be the first character printed by every iteration of the loop (being the first character of the first line), and will be also printed at the end of every iteration (being the first character of the whole string). The replacement will never have any effect on this line because it doesn't contain any digit.

Each other line contains `n` digits, so there is a 1 in `n` chance to turn the first character of the line (which is the only meaningful one) into a `1`.

# Answer
> 2 votes
# Python 2, ~~104~~ 103 bytes

```
from random import*
x='0'*10;i=input()
exec"print'|%s|'%''.join(x);x=[choice('1'+n*~-i)for n in x];"*10

```

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), 105 93 90 bytes

```
x=>w.map(a=>(`|${w=w.map(j=>j|Math.random()<1/x),w.join``}|
`)).join``,w=Array(10).fill(0)

```

Try it online!

+2 bytes for putting the array inside the function, thanks to @Shaggy for pointing that out

```
(x,w=Array(10).fill(0))=>w.map(a=>(`|${w=w.map(j=>j|Math.random()<1/x),w.join``}|
`)).join``

```

Try it online!

# Answer
> 2 votes
# Jelly, 22 bytes

```
ẋ⁵ẋ€⁵¬1¦X€€=1o\j@€⁾||Y

```

A full program accepting the integer as a command line input and printing the output to STDOUT.
(As a monadic link it returns a list of characters and integers.)

**Try it online!**

### How?

Effectively decides at each stage if each worker (including any machines) lose their job (with a one in N chance), however machines are replaced by machines (using logical-OR).

```
ẋ⁵ẋ€⁵¬1¦X€€=1o\j@€⁾||Y - Main link: integer, N
 ⁵                     - literal ten
ẋ                      - repeat -> [N,N,N,N,N,N,N,N,N,N]
    ⁵                  - literal ten
  ẋ€                   - repeat €ach -> [[N,N,N,N,N,N,N,N,N,N],...,[N,N,N,N,N,N,N,N,N,N]]
       ¦               - sparse application...
      1                - ...to indices: [1]
     ¬                 - ...do: logical-NOT -> [[0,0,0,0,0,0,0,0,0,0],[N,N,...],...]
        X€€            - random integer for €ach for €ach
                       -   (0s stay as 0s; Ns become random integers in [1,N])
           =1          - equals one? (vectorises)
             o\        - cumulative reduce with logical-OR
                  ⁾||  - literal list of characters = ['|','|']
               j@€     - join with sw@pped arguments for €ach
                     Y - join with line feeds
                       - implicit print

```

# Answer
> 2 votes
# Perl 6, 58 bytes

```
{say "|$_|" for 0 x 10,|[\~|] ([~] +(1>$_*rand)xx 10)xx 9}

```

Try it online!

`+(1 > $_ * rand)` generates a single bit with the required frequency of `1`s. `xx 10` replicates that expression ten times to produce a single factory instance as a list of bits, and `[~]` joins that list into a single string. `xx 9` replicates that factory-string-generating expression nine times, and then `[\~|]` does a triangular reduction (which some other languages call a "scan") with the stringwise or operator `~|`, so that a worker fired in an earlier iteration remains fired in later ones.

# Answer
> 2 votes
# C (gcc), 110 106 bytes

-4 bytes from @ceilingcat

```
char l[]="|0000000000|",i,j;f(n){for(srand(time(i=0));i++<10;)for(j=!puts(l);j++<10;)rand()%n||(l[j]=49);}

```

Try it online!

Iterates through a list of characters for each round of replacements.

Ungolfed:

```
f(n)
{
    //start with a fresh factory
    char l[]="|0000000000|";

    //init rng
    srand(time(0));

    //print 11 lines
    for(int i = 0; i < 11; i++)
    {
        //print current factory
        puts(l);

        //iterate through the workers. start at index 1 to skip the '|'
        for(int j = 1; j < 11; j++)
        {
            //the expression (rand()%n) has n possible values in the range [0,n-1],
            //so the value 0 has 1/n chance of being the result and thus the worker
            //has 1/n chance of being replaced
            if(rand()%n == 0)
            {
                l[j] = '1';
            }
        }
    }
}

```

# Answer
> 2 votes
# MATL, 26 bytes

```
'|'it10th&Yr=0lY(Y>48+y&Yc

```

Try it online!

### (Long) explanation

Example stack contents are shown along the way. At each step, stack contents are shown bottom to top.

```
'|'    % Push this character
       % STACK: '|'
it     % Take input. Duplicate
       % STACK: '|'
                5
                5
10th   % Push [10 10]
       % STACK: '|'
                5
                5
                [10 10]
&Yr    % Random 10×10 matrix of integers from 1 to input number
       % STACK: '|'
                 5
                 [4 5 4 4 5 5 2 1 2 3
                  3 4 3 3 1 4 4 3 1 5
                  5 1 4 5 4 4 5 2 3 2
                  3 4 5 2 1 3 2 5 3 4
                  4 1 2 2 4 1 1 5 1 1
                  4 5 3 1 5 3 5 2 4 1
                  2 1 4 3 3 1 3 5 3 5
                  1 2 2 1 2 2 4 3 5 3
                  4 5 4 1 2 2 5 3 2 4
                  4 1 2 5 5 5 4 3 5 1]
=      % Is equal? Element-wise
       % STACK: '|'
                [0 1 0 0 1 1 0 0 0 0
                 0 0 0 0 0 0 0 0 0 1
                 1 0 0 1 0 0 1 0 0 0
                 0 0 1 0 0 0 0 1 0 0
                 0 0 0 0 0 0 0 1 0 0
                 0 1 0 0 1 0 1 0 0 0
                 0 0 0 0 0 0 0 1 0 1
                 0 0 0 0 0 0 0 0 1 0
                 0 1 0 0 0 0 1 0 0 0
                 0 0 0 1 1 1 0 0 1 0]
0lY(   % Write 0 in the first row
       % STACK: '|'
                [0 0 0 0 0 0 0 0 0 0
                 0 0 0 0 0 0 0 0 0 1
                 1 0 0 1 0 0 1 0 0 0
                 0 0 1 0 0 0 0 1 0 0
                 0 0 0 0 0 0 0 1 0 0
                 0 1 0 0 1 0 1 0 0 0
                 0 0 0 0 0 0 0 1 0 1
                 0 0 0 0 0 0 0 0 1 0
                 0 1 0 0 0 0 1 0 0 0
                 0 0 0 1 1 1 0 0 1 0]
Y>     % Cumulative maximum down each column
       % STACK: '|'
                [0 0 0 0 0 0 0 0 0 0
                 0 0 0 0 0 0 0 0 0 1
                 1 0 0 1 0 0 1 0 0 1
                 1 0 1 1 0 0 1 1 0 1
                 1 0 1 1 0 0 1 1 0 1
                 1 1 1 1 1 0 1 1 0 1
                 1 1 1 1 1 0 1 1 0 1
                 1 1 1 1 1 0 1 1 1 1
                 1 1 1 1 1 0 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1]
48+    % Add 48, element-wise. This transforms each number into the
       % ASCII code of its character representation
       % STACK: '|'
                [48 48 48 48 48 48 48 48 48 48
                 48 48 48 48 48 48 48 48 48 49
                 49 48 48 49 48 48 49 48 48 49
                 49 48 49 49 48 48 49 49 48 49
                 49 48 49 49 48 48 49 49 48 49
                 49 49 49 49 49 48 49 49 48 49
                 49 49 49 49 49 48 49 49 48 49
                 49 49 49 49 49 48 49 49 49 49
                 49 49 49 49 49 48 49 49 49 49
                 49 49 49 49 49 49 49 49 49 49]
y      % Duplicate from below
       % STACK: '|'
                [48 48 48 48 48 48 48 48 48 48
                 48 48 48 48 48 48 48 48 48 49
                 49 48 48 49 48 48 49 48 48 49
                 49 48 49 49 48 48 49 49 48 49
                 49 48 49 49 48 48 49 49 48 49
                 49 49 49 49 49 48 49 49 48 49
                 49 49 49 49 49 48 49 49 48 49
                 49 49 49 49 49 48 49 49 49 49
                 49 49 49 49 49 48 49 49 49 49
                 49 49 49 49 49 49 49 49 49 49]
                 '|'
&Yc    % Horizontally concatenate all stack contents as char arrays.
       % 1-row arrays are implicitly replicated along first dimension
       % STACK: ['|0000000000|'
                 '|0000000001|'
                 '|1001001001|'
                 '|1011001101|'
                 '|1011001101|'
                 '|1111101101|'
                 '|1111101101|'
                 '|1111101111|'
                 '|1111101111|'
                 '|1111111111|']
       % Implicitly display

```

# Answer
> 1 votes
# SmileBASIC, 75 bytes

```
INPUT N
FOR J=0TO 9?"|";BIN$(F,10);"|
FOR I=0TO 9F=F OR!RND(N)<<I
NEXT
NEXT

```

# Answer
> 1 votes
# Perl 5, 44 bytes

```
#!/usr/bin/perl -a
say"|$_|",s/0/rand"@F"<1|0/eg<0for(0 x10)x10

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 22 bytes

```
TÅ0TFDJ'|.ø=sITи€L€ΩΘ~

```

Try it online!

There should be some more room for golfing.

* `TÅ0` — Push a list of 10 zeroes.
* `TF...` — Do this 10 times:
    + `DJ` — Duplicate the current item and join it.
    + `'|.ø=` — Surround it with two `|`s and print to STDOUT.
    + `ITи` — Repeat the input 10 times.
    + `€L€Ω` — And for each occurrence, get a random element of **\[1 ... N\]**. (There might be a built-in for this which I haven’t seen yet)
    + `Θ` — Push 05AB1E truthified™. For each, check if it equals **1**.
    + `s...~` — Logical OR the result by the current item.

# Answer
> 1 votes
# Charcoal, ~~30~~ ~~29~~ 27 bytes

```
⊞υ×χ0Ｆχ⊞υ⭆§υ±¹‽⁺1×κ⊖θＥυ⪫||ι

```

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

```
⊞υ×χ0

```

Push an string of 10 `0`s to the empty list `u`.

```
Ｆχ

```

Repeat the next command 10 times.

```
⊞υ⭆§υ±¹‽⁺1×κ⊖θ

```

For each character of the last string, repeat it `n-1` times, add a `1`, and pick a random character from the string. This gives a `1/n` chance of changing the character to a `1`. The result is pushed to `u`.

```
Ｅυ⪫||ι

```

Map over the list of strings, surrounding each with `|`, then implicitly print each on its own line.

# Answer
> 1 votes
# JavaScript, 83 bytes

```
f=(n,t=9,s=`|0000000000|
`)=>t?s+f(n,t-1,s.replace(/0/g,v=>+(Math.random()<1/n))):s

```

```
f=(n,t=9,s=`|0000000000|
`)=>t?s+f(n,t-1,s.replace(/0/g,v=>+(Math.random()<1/n))):s
```

```
<p><input id=i value=10 /><button id=t onclick="o.textContent=f(+i.value)">Run</button><p><pre id=o></pre>
```

# Answer
> 1 votes
# Java 10, ~~153~~ ~~152~~ 131 bytes

```
n->{for(int j=10,a[]=new int[j],i;j-->0;){var s="|";for(i=0;i<10;a[i++]|=Math.random()*n<1?1:0)s+=a[i];System.out.println(s+"|");}}

```

-18 bytes thanks to *@OlivierGrégoire*, and -3 more bytes by converting Java 8 to Java 10.

**Explanation:**

Try it online.

```
n->{                             // Method with integer parameter and no return-type
  for(int j=10,a[]=new int[j],i; //  Create the array with 10 workers (0s)
      j-->0;){                   //  Loop 10 times

    var s="|";                   //  Start a String with a wall
    for(i=0;i<10;                //  Loop `i` from 0 to 10 (exclusive)
        a[i++]                   //    After every iteration, change the current item to:
         |=                      //     If it's a 0:
           Math.random()*n<1?    //      If the random value [0:1) is below 1/n
            1                    //       Change the worker to a machine
           :                     //      Else:
            0;                   //       It remains a worker
                                 //     Else (it already is a machine)
                                 //      It remains a machine
      s+=a[i];                   //   Append the current item to the String
    System.out.println(s+"|");}} //   Print the String, with a trailing wall and new-line

```

# Answer
> 0 votes
# APL+WIN, ~~30 40~~  35 bytes

Missed the bit about no spaces ;( - fixed & thanks to Uriel for -3 bytes

Prompts for screen input of number

```
'|',(⍕0⍪×+⍀n=?9 10⍴n←⎕)[;2×⍳10],'|'

```

Explanation similar to that of Uriel:

```
?9 10⍴n create a 9x10 matrix of numbers selected at random between 1 and number

×+⍀n= compare elements of matrix to number, cumulatively sum columns and signum

[;2×⍳10] take non-space columns

'|',(⍕0⍪.......,'|' concatenate a row of zeros and front and back columns of |

```

# Answer
> 0 votes
# Python 3, 132 bytes

```
from random import*
w,p,c=[0]*10,'|',1/int(input())
for _ in w:print(p+''.join(map(str,w))+p);w=list(map(lambda x:x|(random()<c),w))

```

Try it online!

# Answer
> 0 votes
## VBA, 144 bytes

```
Sub f(i)
Dim w(9) As Long
For x = 0 To 9
s = "|"
For y = 0 To 9
s = s & w(y)
If i * Rnd() < 1 Then w(y) = 1
Next
Debug.Print s; "|"
Next
End Sub

```

Indented for easier reading:

```
Sub f(i)
    Dim w(9) As Long
    For x = 0 To 9
        s = "|"
        For y = 0 To 9
            s = s & w(y)
            If i * Rnd() < 1 Then w(y) = 1
        Next
        Debug.Print s; "|"
    Next
End Sub

```

Takes advantage of 2 points: VBA Arrays will default to Base 0 (so `w(9)` is the same as `w(0 to 9)`) and creating the Array as a Long will automatically initialise it to 0.

(Annoyingly, **20** bytes are auto-formatting that VBA adds in but not actually required - 19 spaces and one semi-colon)

# Answer
> 0 votes
I don't see answer for Ruby yet, so:

# Ruby, 92 bytes

```
n=gets.to_i
z='0'*x=10
x.times do
puts'|'+z+'|'
x.times do|s|
z[s]='1' if rand(n)==0
end
end

```

Try it online!

# Answer
> 0 votes
# Ruby, 67 bytes

```
->n{f=[0]*10;10.times{p"|#{f.join}|";f.map!{|l|rand>(1.0/n)?l:?1}}}

```

I think I've cheated a few things here. First of all, this function prints the output with quotes around each line, e.g.:

```
pry(main)> ->n{f=[0]*10;10.times{p"|#{f.join}|";f.map!{|l|rand>(1.0/n)?l:?1}}}[5]
"|0000000000|"
"|0100100000|"
"|0100100000|"
"|0100100000|"
"|0100100100|"
"|0100110100|"
"|0101110100|"
"|0111110100|"
"|1111110110|"
"|1111110110|"
=> 10

```

If this is unacceptable (given that this is , that is probably the case), here is a solution that prints without quotes for **70 bytes**:

```
->n{f=[0]*10;10.times{puts"|#{f.join}|";f.map!{|l|rand>(1.0/n)?l:?1}}}

```

### Explanation:

```
->n{                                                              } # defines anonymous lambda
    f=[0]*10;                                                       # initializes f to [0,0,0,...] (10)
             10.times{                                           }  # main loop
                      p"|#{f.join}|";                               # joins f and prints | before and after
                                     f.map!{|l|                 }   # maps each element of f
                                               rand>(1.0/n)? :      # if rand is greater than 1.0/n
                                                            l ?1    # keep current element or replace with '1'

```

# Answer
> 0 votes
# PHP, ~~71~~ 70 bytes

merging loops saved 5 bytes (again):

```
for(;$k<91;$v|=!rand(0,$argn-1)<<$k++%10)$k%10||printf("|%010b|
",$v);

```

Run as pipe with `-nR` or try it online.

---

edit 1: fixed format and first output (no change in byte count thanks to additional golfing)
edit 2: Golfed one more byte: After the last printing, there´s no more need for firing anyone.

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 131 bytes

```
n=>{var r=new Random();var a=new int[10];for(int i=0;i<100;a[i%10]|=r.Next(n)<1?1:0)if(i++%10<1)Write("|"+string.Concat(a)+"|\n");}

```

Hey, at least I tied with Java.

Try it online!

---
Tags: code-golf, ascii-art, random
---


title: The Great Pyramid of Quine

text:
# Question
Title: The Great Pyramid of Quine
The task is a rather simple quine challenge with a twist, you must output your source code in the shape of a pyramid. The shape of a pyramid is defined below:

```
       1
      234
     56789
    ABCDEFG
   HIJKLMNOP
  QRSTUVWXYZa
 bcdefghijklmn
......etc......

```

The main limitation of this challenge is that your quine must contain exactly enough bytes as to not obstruct the pattern of the pyramid. For instance, the following program lengths would work:

```
1-byter: 1st layer of the pyramid (not allowed by definition of a quine).
4-byter: 1st and 2nd layers of the pyramid.
9-byter: 1st, 2nd and 3rd layers of the pyramid.
etc...

```

So, if your program was:

```
QWERTY

```

It would not be valid, because it would arrange like:

```
  Q
 WER
TY

```

However, if your program was QWERTYUIO, it would be fine:

```
  Q
 WER
TYUIO

```

---

# Rules

* Standard loopholes are obviously disallowed, no reading your own source.
* The pyramid must be centered, trailing characters are allowed, but not required.
    + Also, any character may be used to center the pyramid, doesn't have to be `(char)32`.
* Your quine must be able to be shaped into a pyramid.
    + It must retain the original ordering of your sourcecode.
    + **Your source-code may *NOT* contain the character being used to format the pyramid.**
    + E.G. if your sourcecode contains a space, you'll need another char for the format.
* You may use comments in your quine to "pad" to the correct size.
    + Obviously, these must be output as part of the quine.
* If the program contains newlines/tabs, they aren't part of the quine and should be omitted in the output.
* The shape is counted in characters, not bytes; if the shape is malformed you're not doing it right.

**The lowest possible score here should be 4.**

# Answer
> 4 votes
# 05AB1E, 36 bytes

```
"34çs«DJā·<£õK.cJ?"34çs«DJā·<£õK.cJ?

```

Try it online!

If `trailing characters are allowed` also means at the end of the output, `0"D34çýā·<£.c"D34çýā·<£.c` is a layer shorter at 25 bytes.

# Answer
> 4 votes
# Java 11, ~~324~~ ~~256~~ 227 bytes

```
v->{var s="v->{vars=%c%s%1$c;for(inti=0;;)System.out.printf(%1$c%%%1$c+(15+i)+%1$cs%%n%1$c,s.format(s,34,s).substring(i*i,++i*i));}///";for(int i=0;;)System.out.printf("%"+(15+i)+"s%n",s.format(s,34,s).substring(i*i,++i*i));}//

```

-29 bytes thanks to *@JoKing*.

Outputs with leading spaces to make the triangle. (Note that the whitespace between `var s` and `int i` are tabs, not spaces.)

Try it online.

**Explanation:**

**-part:**

* `var s` contains the unformatted source code String
* `%s` is used to put this String into itself with `s.format(...)`
* `%c`, `%1$c` and `34` are used to format the double-quotes (`"`)
* `%%` is used to format the `%`
* `s.format(s,34,s)` puts it all together

**Challenge part:**

```
for(int i=0;;)         // Loop `i` indefinitely upwards from 0
  System.out.printf(   //  Print with format:
    "%"+(15+i)+"s      //   Add leading spaces to make the line length size 15+`i`
                 %n",  //   And include a trailing newline
    s.format(s,34,s).substring(
                       //   And append a substring of the source code-String
       i*i,            //    From index `i` squared
       ++i*i));}       //    To index `i+1` squared

```

Which stops with an `java.lang.StringIndexOutOfBoundsException: begin 225, end 256, length 226` error for the `String#substring(int,int)` method, the iteration after it has printed the result (which is fine according to the meta).

# Answer
> 4 votes
# Python 2, 81 bytes

```
s='n=0;\nprint(8-n)*chr(32)+("s=%r;exec(s*9)"%s)[n*n:][:n-~n];n+=1;#JK';exec(s*9)

```

Try it online!

An eval quine that uses spaces as the filler character.

# Answer
> 3 votes
# Python 2, 169 bytes

Uses `0` for formatting the pyramid.

```
s='s=%r;k=s%%s;print"\\n".join(`1-1`*(12-n)+k[n*n:][:n-~n]for n in range(13))#######################';k=s%s;print"\n".join(`1-1`*(12-n)+k[n*n:][:n-~n]for n in range(13))

```

Try it online!

---

# Python 2, 147 bytes

This uses the rule *If the program contains newlines/tabs, they aren't part of the quine and should be omitted in the output.*

```
s='s=%r;k=s%%s;print"\\n".join(`1-1`*(12-n)+k[n*n:][:n-~n]forninrange(13))##';k=s%s;print"\n".join(`1-1`*(12-n)+k[n*n:][:n-~n]for	n	in	range(13))##

```

Try it online!

# Answer
> 3 votes
# Perl 6, 67 bytes

```
<say("<$_>~~.EVAL".substr($!++²,$!*2-1).indent(8-$!))xx⁸>~~.EVAL

```

Try it online!

I used a couple of unicode characters in order to squeeze out that extra layer. Outputs using spaces:

```
       <
      say
     ("<$_
    >~~.EVA
   L".substr
  ($!++²,$!*2
 -1).indent(8-
$!))xx⁸>~~.EVAL

```

### Explanation:

```
<say("<$_>~~.EVAL"                                  )   >~~.EVAL   # Normal quine
                  .substr($!++²,$!*2-1)              xx⁸  # Split into layered substrings
                                       .indent(8-$!)      # And indent each one

```

# Answer
> 2 votes
# Gol\>\<\>, 36 bytes

```
":P}r6&56F:M}F0ss|&:P&Roao{|;Nooooo!

```

Try it online!

**an even younger version, 36 bytes**

```
":P}r6&56F:M}R` &:P&Fo|ao{|;Noooooo!

```

I feel so close to getting it one line shorter, grrrr....

Try it online!

**even younger version, 36 bytes**

```
"r2ss6&56F:M}R` &:P&Fo|ao{|;what????

```

This one's code is smaller, but it still comes out to the same amount sadly, the comment takes up the remainder of the space.

Try it online!

**slightly younger version, 36 bytes**

```
"r2ss156F:M}F` o|:PP}Fo|ao{{|;Wowza!

```

Wowza! Heh, I just used that to fill some space, but the program works, to golf down, I used a few prepushed values rather than using variables!

Try it online!

**Older version, 42 bytes**

```
"r2ss0V_~6:&F&:M&F` o|_PPV_Fo|ao|;empty...

```

This has a trailing newline, and has more chars than i would like...

I'm going to be golfing this severely...

Try it online!

# Answer
> 2 votes
# Clean, 256 bytes

```
module QQ;import StdEnv,Text;q=dec'#';$n#k=(s<+q<+s<+q)%(n^2,n^2+n*2)=lpad k(16+n)(dec q);Start=join{toChar 10}(map$[0..15]);s="module QQ;import StdEnv,Text;q=dec'#';$n#k=(s<+q<+s<+q)%(n^2,n^2+n*2)=lpad k(16+n)(dec q);Start=join{toChar 10}(map$[0..15]);s="

```

Try it online!

Pretty much the standard quine, conveniently also a template quine, with the formatting function added.

# Answer
> 2 votes
# , ~~169~~ 144 bytes

```
s='`!`=intToUtf8;cat(sprintf("%*s",11+(i=1:12),substring(paste0("s=",q<-!39,s,q,";eval(parse(t=s))"),(i-1)^2+1,i^2)),sep=!010)';eval(parse(t=s))

```

Try it online!

```
           s
          ='`
         !`=in
        tToUtf8
       ;cat(spri
      ntf("%*s",1
     1+(i=1:12),su
    bstring(paste0(
   "s=",q<-!39,s,q,"
  ;eval(parse(t=s))")
 ,(i-1)^2+1,i^2)),sep=
!010)';eval(parse(t=s))

```

Managed to shorten it by moving to a string that’s parsed rather than an expression that’s departed. Had to use a redefinition of a unary operator to get it under the 144 though.

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 225 bytes

```
var s="var s={0}{1}{0};for(int i=0;;)WriteLine(string.Format(s,(char)34,s).Substring(i*i++,2*i-1).PadLeft(i+14,(char)2));//";for(int i=0;;)WriteLine(string.Format(s,(char)34,s).Substring(i*i++,2*i-1).PadLeft(i+14,(char)2));//

```

Uses a `STX` char as padding. Did not realize Kevin Cruijssen already submitted an exact copy in java before posting until I was done, but I decided to post this anyways.

Try it online!

---
Tags: code-golf, ascii-art, restricted-source, quine
---


title: Drawing a tree from an array

text:
# Question
Title: Drawing a tree from an array
Given a possibly nested, non-empty array of single-digit positive integers (not guaranteed unique), output the ASCII-art representation as a tree, using the box-drawing characters `┌ ┴ ┐ ─ │ ┬ ┼`. (These were copied from Code Page 437, but you can use any equivalent representation).

Every integer of the array should be a leaf of the tree. Elements the same level deep in the array should be present at the same level of the tree. All elements should be separated by enough whitespace to be distinct (up to you to determine how wide, minimum of one space between).

For example, given array `[[1, [2]], [3, [4, 5]]]`, output the following tree

```
 ┌─┴─┐
┌┴┐ ┌┴─┐
1 │ 3 ┌┴┐
  2   4 5

```

For array `[1, 2, 3]` the tree could look like

```
┌─┼─┐
1 2 3

```

But the array `[[1, 2, 3]]` would look like

```
  │
┌─┼─┐
1 2 3

```

While the array `[1, [1, [1, [1]]]]` could look like

```
 ┌─┴┐
 1 ┌┴─┐
   1 ┌┴┐
     1 │
       1

```

As a more complicated example, `[1, [[[2, 3], 4], 5]]` could be

```
┌┴───┐
1  ┌─┴┐
 ┌─┴┐ 5
┌┴┐ 4
2 3

```

or several other variations.

---

* Input and output can be given by any convenient method.
* You can print it to STDOUT or return it as a function result.
* Either a full program or a function are acceptable.
* Any amount of extraneous whitespace is acceptable, so long as the characters line up appropriately.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# Python 3, 400 393 390 bytes

```
L=len
S,*K=' ┴┼│123456789'
def T(x):
 try:return[str(x+0)]
 except:
  z=[*map(T,x)];q=max(map(L,z))
  for p in z:p+=[S*L(p[0])]*(q-L(p))
  b=[S.join(a)for a in zip(*z)];t=b[0];l=L(t);s=0;e=L(z);r=[S]*l
  if e<2:return['│'.center(l),*b]
  for i in range(l):
   if t[i]in K:s+=1;r[i]='┬┌┐'[(s<e)-(s>1)]
   elif 0<s<e:r[i]='─'
  c=l//2;r[c]=K[r[c]=='┬'];return[''.join(r),*b]

```

Returns a list of strings from top to bottom.

EDIT 1: Trimmed 7 bytes by avoiding duplication of `┴┼` (net save of 2 bytes), cutting out 0 from the one string, changing how drawing characters are selected from `┬┌┐` (use `<` instead of `==`), and replacing a `L(z)` I missed with `e`

EDIT 2: -2 bytes thanks to ovs and -1 byte thanks to Kevin Cruijssen

Try it online!

### Ungolfed

```
def layer(item):
    if isinstance(item, int):
        return [str(item)]
    else:
        subs = [layer(sub) for sub in item]
        longest = max(map(len, subs))
        for sub in subs:
            sub += [' ' * len(sub[0])] * (longest - len(sub))
        below = [' '.join(l) for l in zip(*subs)]
        top = below[0]
        l = len(top)
        if len(subs) == 1:
            return ['│'.center(l), *below]
        seen = 0
        expected = len(subs)
        builder = [' '] * l
        for i in range(l):
            c = top[i]
            if c in '┴┼│123456789':
                seen += 1
                if seen == 1:
                    builder[i] = '┌'
                elif seen == expected:
                    builder[i] = '┐'
                else:
                    builder[i] = '┬'
            elif 0 < seen < expected:
                builder[i] = '─'
        center = l // 2
        if builder[center] == '┬':
            builder[center] = '┼'
        else:
            builder[center] = '┴'
        return [''.join(builder), *below]

```

Builds a tree from the leaves up, one layer at a time.
> 12 votes

# Answer
# Clean, ~~544~~ 506 bytes

*Escapes are used to avoid invalid UTF-8 on SE/TIO but counted as one byte as they're valid literals*

```
import StdEnv,Data.List;::T=I Int|L[T];$l#m= @l#k=map maxList(transpose m)=flatlines[[last[' ':[(\_|v<0|w<[j]|q>hd w|q<last w|any((==)q)w|q==j='\305'='\302'|q==j='\301'='\304'='\277'='\332'='\263'=toChar v+'0')0\\[v,r,j:w]<-m|r/2==p&&q>=hd w&&q<=last w]]\\q<-[0..k!!3]]\\p<-[0..k!!1]];@(L l)#p=twice(\p=[[v,r+1:[e+sum([2\\[v:_]<-i|0<=v]++zipWith(\c j=j!!2-c!!3)t(takeWhile(\[z:_]=v+z< -1)(tl t)))-x!!1\\e<-x]]\\i<-inits p&t<-tails p&[v,r:x]<-p])(concatMap@l)#g=[g\\[_,2,g:_]<-p]=[[-1,0,(hd g+last g)/2:g]:p];@(I i)=[[i,0,0,0]];

```

Try it online!

Takes input in the format `L[I 3, L[I 4, I 5], I 2]..`

Connects the trees from the bottom up, left to right, then adjusts the distances from right to left.

Prettified, sort-of:

```
import StdEnv, Data.List;
:: T = I Int | L [T];
$ l
    #m = @l
    #k = map maxList (transpose m)
    = flatlines [
        [
            last[
                ' ':
                [
                    if(v < 0)
                        if(w < [j])
                            if(q > hd w)
                                if(q < last w)
                                    if(any ((==) q) w)
                                        (
                                            if(q == j)
                                                '\305'
                                                '\302'
                                        )(
                                            if(q == j)
                                                '\301'
                                                '\304'
                                        )
                                    '\277'
                                '\332'
                            '\263'
                        (toChar v + '0')
                    \\ [v, r, j: w] <- m
                    | r/2 == p && q >= hd w && q <= last w
                ]
            ]
            \\ q <- [0..k!!3]
        ]
        \\p<-[0..k!!1]
    ];
@ (L l)
    #p = twice
        ( \p
            = [
                [
                    v, r + 1:
                    map
                        (
                            (+)
                            (
                                sum [2 \\ [v: _] <- i| 0 <= v]
                                + sum (
                                    zipWith
                                        (
                                            \[_, _, _, c: _] [_, _, j: _] = j - c
                                        )
                                        t
                                        (
                                            takeWhile (\[v: _] = v < 0) (tl t)
                                        )
                                ) * (1 - sign (v + 1))
                                - x!!1
                            )
                        )
                        x
                ]
            \\ i <- inits p
            &  t <- tails p
            &  [v, r: x] <- p
            ]
        )
        (concatMap @ l)
    #g = [g \\ [_, 2, g: _] <- p]
    =[[-1, 0, (hd g + last g)/2: g]: p];
@ (I i) = [[i, 0, 0, 0]];

```
> 3 votes

# Answer
# Charcoal, ~~127~~ 123 bytes

```
↶≔⟦⟦θ⟧⟧ηＦη«≔⊟ιζ¿⁼Ｉζ⪫⟦ζ⟧ω⊞υ⊞ＯιζＦＬζ⊞η⁺ι⟦⊖Ｌζκ§ζκ⟧»Ｗυ«≔⌊υι≔Φυ¬⁼κιυＪ±⊗Ｌυ⊘⊖ＬιＩ⊟ιＷι«≔⊟ιζ¿ζ«←§┐┬‹ζ⊟ιＷ⁼ＫＫψ←─≔⁰ι»¿⊟ι┌¶┴¦│

```

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

Change the default drawing direction to up since we don't draw anything to the right.

```
≔⟦⟦θ⟧⟧η

```

The first step is to convert the nested array representation into an index representation which is a list of all the entries together with the indices of the subarrays, e.g. for the input `q=[1, [[[2, 3]], [4], 5]]` the `5` is `q[1][2]` and therefore the list we want is `1, 2`. We start with a single entry to process which is a list containing a list of the current indices (i.e. none so far) and the original input.

```
Ｆη«

```

Loop over the arrays as we process them. (Conveniently Charcoal will continue to iterate over a list if you push to it during iteration.)

```
≔⊟ιζ

```

Get the next array to process.

```
¿⁼Ｉζ⪫⟦ζ⟧ω

```

Is this actually a scalar rather than an array?

```
⊞υ⊞Ｏιζ

```

If so, then the list we had actually belongs on the final list of lists of indices.

```
ＦＬζ

```

Otherwise, loop over each element in this array...

```
⊞η⁺ι⟦⊖Ｌζκ§ζκ⟧»

```

... and save it with its new index list so far for further processing. The maximum index of the array is also saved which is used to special-case the last element of the array.

```
Ｗυ«

```

We are now ready to loop over the list of index lists. However, the list is not in lexicographical order, so we can't iterate it directly.

```
≔⌊υι

```

Find the next element in lexicographical order.

```
≔Φυ¬⁼κιυ

```

Remove it from the list.

```
Ｊ±⊗Ｌυ⊘⊖Ｌι

```

Jump to the position of the scalar in the output. We can calculate this given that we can keep count of the number of scalars we output and we also know the number of entries in its index list.

```
Ｉ⊟ι

```

Actually print the scalar.

```
Ｗι«

```

Loop over the entries in the index list. Again, this isn't simple iteration, because the entries come in pairs, and we also need to be able to break out of the loop.

```
≔⊟ιζ

```

Extract the next index from the list.

```
¿ζ«

```

If this is not the first element in the list...

```
←§┐┬‹ζ⊟ι

```

... then print  or  depending on whether this is the last element in the list...

```
Ｗ⁼ＫＫψ←─

```

... and print enough s to fill up to the previous entry at this level...

```
≔⁰ι»

```

... and clear the variable to break out of the loop since we're done here.

```
¿⊟ι┌¶┴

```

Otherwise if this is (the first element of) a multiple-element list then print the `┌┴`, leaving the cursor above the  to deal with this level's parent.

```
¦│

```

Otherwise if this is a 1-element list then just print a  and move up a line to deal with this level's parent.
> 3 votes

---
Tags: code-golf, ascii-art, data-structures
---


# Question
Title: Can this container hold this much liquid?
# Can this container hold this much liquid?

### Challenge Synopsis

As you most likely know, liquids have an indefinite shape and a definite volume. As such, they always take the shape of their container. They cannot, however, expand to fill their container.

Your job today is to determine whether or not a certain amount of liquid (represented by a certain number of `L` characters or numbers representing the volume of the part, as per suggestion) can fit into a container of a certain size (represented by a matrix of `C` characters) with some amount of empty space (represented by space characters) within it. The container will always have `C` characters all the way around the perimeter.

Your program will return a truthy/falsey value based on whether the liquid will fit into the container. It will only fit if there is an area of connected empty space (made up of spaces adjacent to one another horizontally, diagonally, or vertically) within the container for each part of the liquid that is separated from the rest (either by a space or by two newline characters).

### Test Cases

```
LLL
L
-----    True
CCCCC
C  CC
C  CC
CCCCC

LLL
 LL
------   True
CCCCCC
C C  C
C  CCC
CCCCCC

L L
LLL
-----    False (Not enough space)
CCCCC
CCCCC
C  CC
CCCCC

LL
------   False (Spaces are not connected but liquid is)
CCCCCC
CCCC C
C CCCC
CCCCCC

L L
------   True
CCCCCC
CCCC C
C CCCC
CCCCCC

L L
------   True (There is a pocket of empty space which holds both parts of the liquid)
CCCCCC
CCC  C
CCCCCC
CCCCCC

L

L
------   True (There is a pocket of empty space for each part of the liquid)
CCCCCC
CCCC C
C CCCC
CCCCCC

L L L LL
------   True
CCCCCCCCC
CCCC  C C
C CCCCCCC
CCCCCC CC
CCCCCCCCC

L
L
-----    True
CCCCC
CCCCC
C  CC
CCCCC

```

*Feel free to suggest test cases!*

### Rules

* This is , so the shortest answer in bytes wins.
* Standard loopholes are disallowed.

# Answer
> 4 votes
# Snails, 58 bytes

Input is taken exactly as in the examples.

```
t\ t\L{t\L?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

```

A 4 bytes longer version is fast enough to instantly complete the test cases (Try this version online):

```
?^
t\ t\L{t\L`?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

```

An indented formatting of the latter:

```
?^
    t\
    t\L
    {
        t\L`?
        t\
        z!.
        o=(\ ,\C
    },
    !(tz(
         \L!.!~
         |
         \ !.o=(\ ,\C
},
!(t\L

```

# Answer
> 1 votes
# Clean, 313 bytes

```
import StdEnv,Data.List
?v=nub[v:[[sum s:k]\\s<-subsequences v|s>[],k<- ?(difference v s)]]
$v m#p=[[(x,y)]\\x<-[0..]&l<-m,y<-[0..]&' '<-l]
=or[and(zipWith(>=)(s++[0,0..])r)\\r<- ?v,s<-permutations(map length(foldl(\p _=nub[sort(nub(e++[(x,y)\\(u,v)<-e,x<-[u-1,u,u+1],y<-[v-1,v,v+1]|(m!!x)!!y<'C']))\\e<-p])p p))]

```

Try it online!

Defines the function `$ :: [Int] [[Char]] -> Bool`. TIO link includes a wrapper around STDIN.

`? :: [Int] -> [[Int]]` is a helper to generate the different ways the volumes can be combined.

Expanded:

```
$ v m // in function $ of v and m
    # p // define p as
        = [ // a list of
            [(x, y)]    // lists of pairs (x, y)
        \\              // for each
            x <- [0..]  // index x
            & l <- m    // at list l in m
        ,               // for each
            y <- [0..]  // index y
            & ' ' <- l  // at spaces in l
        ]
    = or [ // true if any of the list of
        and (               // true if all of
            zipWith         // element-wise application of
                (>=)            // greater than or equal to
                (s ++ [0, 0..]) // permutation s padded with zeroes
                v               // list v of volumes
        )
    \\                      // for each
        s <- permutations ( // permutation s of
            map length (    // the lengths of
                foldl       // a left-fold of
                    (\p _   // function on p discarding second argument
                        = nub [ // the unique elements of the list of
                            sort (          // sorted versions of
                                nub (       // unique lists composed of
                                    e       // list e of points in a region
                                    ++ [    // prepended to the list of
                                        (x, y)      // pairs (x, y)
                                    \\              // for each
                                        (u, v) <- e // pair (u, v) in list e
                                    ,               // for each
                                        x <- [u-1, u, u+1] // x-coordinate adjacent to u
                                    ,               // for each
                                        y <- [v-1, v, v+1] // y-coordinate adjacent to v
                                    |               // where
                                        (m!!x)!!y < 'C' // the character in m at (x, y) is a space
                                    ]
                                )
                            )
                        \\          // for each
                            e <- p  // region e in p
                        ]
                    )
                    p // applied to a starting argument of p
                    p // recursively, for each element in p
            )
        )
    ]

```

---
Tags: code-golf, geometry, matrix
---


title: Minimum-cost flow problem

text:
# Question
Title: Minimum-cost flow problem
A flow network is a directed graph `G = (V, E)` with a source vertex `s ϵ V` and a sink vertex `t ϵ V`, and where every edge `(u, v) ϵ E` on the graph (connecting nodes `u ϵ V` and `v ϵ V`) has 2 quantities associated with it:

1. `c(u, v) >= 0`, the capacity of the edge
2. `a(u, v) >= 0`, the cost of sending one unit through the edge

We define a function `0 <= f(u, v) <= c(u, v)` to be the number of units being passed through a given edge `(u, v)`. Thus, the cost for a given edge `(u, v)` is `a(u, v) * f(u, v)`. The minimum-cost flow problem is defined as minimizing the total cost over all edges for a given flow amount `d`, given by the following quantity:

The following constraints apply to the problem:

1. **Capacity requirements**: the flow through a given edge may not exceed the capacity of that edge (`f(u, v) <= c(u, v)`).
2. **Skew symmetry**: the flow though a given edge must be antisymmetric when the direction is reversed (`f(u, v) = -f(v, u)`).
3. **Flow conservation**: the net flow into any non-sink non-source node must be 0 (for each `u ∉ {s, t}`, summing over all `w`, `sum f(u, w) = 0`).
4. **Required flow**: the net flow out of the source and the net flow into the sink must both equal the required flow through the network (summing over all `u`, `sum f(s, u) = sum f(u, t) = d`).

Given a flow network `G` and a required flow `d`, output the minimum cost for sending `d` units through the network. You may assume that a solution exists. `d` and all capacities and costs will be non-negative integers. For a network with `N` vertices labeled with `[0, N-1]`, the source vertex will be `0` and the sink vertex will be `N-1`.

This is , so the shortest answer (in bytes) wins. Remember that this is a competition within languages as well as between languages, so don't be afraid to post a solution in a verbose language.

Built-ins are allowed, but you are encouraged to include solutions without builtins, either as an additional solution in the same answer, or as an independent answer.

Input may be in any reasonable manner that includes the capacities and costs of each edge and the demand.

## Test Cases

Test cases are provided in the following format:

`c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>`

```
c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213

```

These test cases were computed with the NetworkX Python library.

# Answer
> 3 votes
# \[R + lpSolve\], ~~201~~ ~~186~~ ~~149~~ 144 bytes

```
function(c,a,d,`^`=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))$objv

```

Try it online!

The code constructs the following Linear Problem and solve it using `lpSolve` package :

$$ \begin{align} min & \sum\_{\forall x \in V}\ \sum\_{\forall y \in V} A\_{x,y} \cdot f\_{x,y} \\ subject\ to : & \\ & \sum\_{x \in V} f\_{v,x} - f\_{x,v} = 0 & \forall v \in V : v \neq \\{s,t\\} \\ & \sum\_{x \in V} f\_{s,x} - f\_{x,s} = d \\ & \sum\_{x \in V} f\_{t,x} - f\_{x,t} = -d \\ & f\_{x,b} \leq C\_{x,b} & \forall x \in V,\forall y \in V \end{align} $$ where :

* \\$V\\$ is the set of vertices
* \\$s\\$ s is the source vertex
* \\$t\\$ s is the target (or sink) vertex
* \\$A\_{x,y}\\$ is the flow cost for edge `x -> y`
* \\$f\_{x,y}\\$ is the flow of edge `x -> y` in the optimal solution
* \\$d\\$ is the required flow at sink (i.e. the demand at \\$t\\$ and the production at \\$s\\$)
* \\$C\_{x,y}\\$ is the maximum capacity of edge `x -> y`

# Answer
> 1 votes
# Wolfram Language, 42 bytes

```
FindMinimumCostFlow[#,1,VertexCount@#,#2]&

```

Trivial builtin. Non-builtin solution coming soon.

# Answer
> 1 votes
# Python 3 + NetworkX, 137 bytes

```
from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)

```

No TryItOnline link because TIO doesn't have the NetworkX library installed

Takes graph input as an edge list with capacity and weight attributes, like this:

```
[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]

```

This is a golfed version of the code that I used to verify the test cases.

---
Tags: code-golf, graph-theory, optimization
---


title: Finding Gaps in Date Ranges

text:
# Question
Title: Finding Gaps in Date Ranges
Given a list of date ranges `r` as input, output or return any ranges not found in `r`.

For the sake of this example, input will be in `YYYY-MM-DD` format.

Let's say you have three date ranges:

```
[2019-01-01, 2019-02-01]
[2019-02-02, 2019-04-05]
[2019-06-01, 2019-07-01]

```

You can see that there is a gap in between `2019-04-05` and `2019-06-01`.

The output will be that gap: `[2019-04-06, 2019-05-31]`

## Rules

* Input and output can be in any reasonable date or collection format, as long as it is consistent.
* Assume the input is not ordered.
* Your date range does not have to be `[latest, earliest]`, but it does have to follow rule 2.
* Assume there are no overlapping dates in the input

## Test Cases:

Input: `[[2019-01-01, 2019-02-01],[2019-02-02, 2019-04-05],[2019-06-01, 2019-07-01]]`

Output: `[[2019-04-06, 2019-05-31]]`

---

Input: `[[2019-01-01, 2019-02-01],[2018-02-02, 2018-04-05],[2019-06-01, 2019-07-01]]`

Output: `[[2018-04-06, 2018-12-31], [2019-02-02, 2019-05-31]]`

---

Input: `[[2019-01-01, 2019-02-01],[2019-02-02, 2019-03-02],[2019-03-03, 2019-07-01]]`

Output: `[]`

---

Input: `[[2019-01-01, 2019-02-01], [2019-11-02, 2019-11-20]]`

Output: `[[2019-02-02, 2019-11-01]]`

---

Input: `[[2019-01-01, 2019-02-01],[2019-02-03, 2019-04-05]]`

Output: `[[2019-02-02, 2019-02-02]]` or `[[2019-02-02]]`

# Answer
# APL (Dyalog Extended), ~~28~~ ~~25~~ 24 bytes

Anonymous tacit prefix function. Argument and result are 2-column matrices of day numbers since an epoch, each row representing a range.

```
1 ¯1+⍤1∘{⍵⌿⍨1<-⍨/⍵}1⌽⍢,∧

```

Try it online! The `In` pre-processor function converts from a list of pairs of 3-element lists (dates in ISO order) to a 2-column matrix of IDNs, International Day Numbers (days since 1899-12-31). The `Out` post-processor function converts from a matrix of IDNs to a matrix of 3-element lists.

sort rows ascending

`1⌽` cyclically rotate the dates one step left
`⍢,` while ravelled (flattened) — afterwards, reshape back to original shape

`1 ¯1+` add one and negative one
`⍤1` using that list for each row
of the result of
`{``}` the following lambda:
the argument
`-⍨/` subtract left-hand date from right-hand date, row-wise
`1<` mask where differences exceed one (i.e. where ranges are not adjacent)
`⍵⌿⍨` filter the rows by that mask
> 4 votes

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

```
n=>{n.Sort();for(int i=0;;)Write(n[i].b.AddDays(1)==n[++i].a?"":n[i-1].b.AddDays(1)+""+n[i].a.AddDays(-1));}

```

Outputs by printing in the format `DD/MM/YYYY 12:00:00 AMDD/MM/YYYY 12:00:00 AM`. Will cause an IndexOutOfRange exception, which is fine per meta consensus.

Try it online!

If we take input in the form of days since the unix epoch, we can get this down to...

# 83 bytes

```
n=>{n.Sort();for(int i=0;;)Print(n[i].b+1==n[++i].a?"":n[i-1].b+1+" "+(n[i].a-1));}

```

Try it online!

We can golf this down even further with the `/u:System.Array` flag, for...

# 78 bytes

```
n=>{Sort(n);for(int i=0;;)Print(++n[i].b==n[++i].a--?"":n[i-1].b+" "+n[i].a);}

```

Try it online!
> 3 votes

# Answer
# PHP, ~~208 197 190~~ 177 bytes

hunky chunky sat on a wall ... though the new approach had quite some golfing potential.

```
function($a){sort($a);for($m=$x=$a[0][0];$f=$m<=$x;$f^$g&&print($g=$f)?"$m/":"$n
",$m=date("Y-m-d",strtotime($n=$m)+9e4))foreach($a as$d)$x=max($x,$d[1|$f&=$m<$d[0]|$m>$d[1]]);}

```

function takes array of ranges \[start,end\] in ISO format, prints gap intervals. Try it online.

---

## breakdown

```
function($a){
    sort($a);                           # sort ranges (for easy access to min date)
    for($m=$x=$a[0][0];$f=$m<=$x;       # loop from min date to max date, 1. set flag
        $f^$g&&print($g=$f)?"$m/":"$n\n",       # 4. flag changed: backup flag, print date
        $m=date("Y-m-d",strtotime($n=$m)+9e4)   # 5. backup and increment date
    )foreach($a as$d)
        $x=max($x,$d[1                          # 2. find max date
            |$f&=$m<$d[0]|$m>$d[1]              # 3. date found in ranges: clear flag
        ]);
}

```
> 2 votes

# Answer
# Perl 5, 130 bytes

```
/-(\d+)-/,$_=strftime"%Y-%m-%d",0,0,0,$'+($|--||-1),$1-1,$`-1900 for@F=sort@F;$,lt$;&&say"$, $;"while($,,$;)=@F[++$i,$i+1],++$i<@F

```

TIO
> 2 votes

# Answer
# Bash, 125 bytes

```
set `sort<<<$1`;shift;for a;{ s=$[x++%2?-1:1]day;c=`date -d$a\ $s +%Y-%m-%d`;[ $p ]&&{ [[ $p < $c ]]&&echo $p $c;p=;}||p=$c;}

```

TIO
> 2 votes

# Answer
# Jelly, 13 bytes

```
FṢṖḊs2+Ø+>/Ðḟ

```

Jelly (currently) has no built-in dates, so this uses days-since-epoch.
The input list of ranges (pairs of integers) may be in mixed order and mixed directions.
The result is a list of ascending ranges in ascending order.

**Try it online!** (footer formats in order to show an empty list as `[]`)

### How?

Note: This relies on the assurance that "there are no overlapping dates in the input" as stated in the rules.

```
FṢṖḊs2+Ø+>/Ðḟ - Link: list of pairs of integers
F             - flatten
 Ṣ            - sort
  Ṗ           - pop (remove tail)
   Ḋ          - dequeue (remove head)
    s2        - split into twos
       Ø+     - literal [1,-1]
      +       - add (vectorises)
           Ðḟ - filter discard those for which:
          /   -   reduce by:
         >    -     greater than?

```
> 2 votes

# Answer
# Perl 6, 46 bytes

```
{@_.sort[1..*-2].map:{$^a+1,$^b-1 if $b>$a+1}}

```

Try it online!

Takes a list of `Date` pairs.
> 2 votes

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

```
x=>{var(a,_)=x[0];foreach(var(b,c)in x.OrderBy(y=>y)){if(a<b)Print((a,b.AddDays(-1)));a=c.AddDays(1);}}

```

Try it online!

Input is a list of start/end date tuples. Outputs each missing range to STDOUT.

```
// x: input list of start/end date tuples
x=>{
  // variable definitions...
  // a: 1 day after the end date of the previous range
  // b: start of the current range
  // c: end of the current range

  // start by deconstructing the start date of the first tuple
  // into a. a will then be a DateTime and will contain a value
  // at least a large as the smallest start date.
  var(a,_)=x[0];
  // iterate over sorted ranges
  foreach(var(b,c)in x.OrderBy(y=>y)){
    // if the day after the end of the previous range is less
    // than the start of the current range, then print the
    // missing days.
    if(a<b)
      Print((a,b.AddDays(-1)));
    // save the day after the current range to a for next iteration
    a=c.AddDays(1);
  }
}

```
> 1 votes

# Answer
# , 88 bytes

```
function(a,b=a[order(a$x),],d=c(b$x[-1]-b$y[-nrow(b)],0))data.frame(b$y+1,b$y+d-1)[d>1,]

```

Try it online!

This takes a data frame of date ranges as input and outputs a data frame with the ranges that are missing. I’m fairly sure this could be golfed more, but I ran into issues with `c`, `cbind` and others stripping the date class.
> 1 votes

---
Tags: code-golf, date
---


title: How lit is this room?  pt. 1

text:
# Question
Title: How lit is this room?  pt. 1
Related to this question.

A *room* is defined to be a (not necessarily convex) non-intersecting polygon, expressed as an ordered list of 2-dimensional coordinates. A sufficiently bright lightbulb is placed at a specific point inside the room, and emits light in every direction. Your task is to find the total illuminated area of the room. You may take in input in any reasonable format. The points on the polygon/room as well as the coordinates of the light source are rational numbers. They can be taken in clockwise or counterclockwise, either format is fine. The test case in the problem is given counterclockwise.

The following picture shows two example rooms, where the purplish dot represents the light source, and the shaded region represents the illuminated area.

Test case:

```
(1/2, 18)
(1,3)
(5,1/2)
(7,5)
(12,7)
(16,3)
(15,11)
(8,19)
(3,7)
Light source located at (5,8)
Answer: 815523/6710 ≈ 121.538

```

Here is a graphical depiction of the solution to that test case. The two points that define the solution that are not on the original polygon are (55/61, 363/61) and (856/55, 357/55).

This formula may be helpful in calculating the area.

Since this is , the shortest code in bytes wins.

# Answer
> 12 votes
# Python 3, 388 ~~398~~ ~~408~~ ~~409~~ ~~415~~ ~~417~~ ~~493~~ bytes

---

To make it more accurate, increase `n`

```
from random import*
u=uniform
c=lambda A,B,C:(C[1]-A[1])*(B[0]-A[0])>(B[1]-A[1])*(C[0]-A[0])
I=lambda A,B,C,D:c(A,C,D)!=c(B,C,D)and c(A,B,C)!=c(A,B,D)
def a(l,v,n=9**6,s=0):
 g=lambda i:(min(x[i]for x in v),max(x[i]for x in v))
 for _ in'x'*n:
  h=((u(*g(0)),u(*g(1))),l);s+=any([I(*f,*h)for f in list(zip(v,v[1:]+[v[0]]))])^1
 return(abs(g(0)[0]-g(0)[1])*abs(g(1)[0]-g(1)[1]))*float(s/n)

```

Basic Monte-Carlo approach. Steps listed below.

1. Find x and y ranges that the shape occupies.
2. Create a list of edges created by the vertices
3. Iterate a large number of times (the more the better)
4. Create a random point (j,k) inside the x,y range.
5. Check if any of the edges intercept with the line-segment created by the light and the random point. If any of the edges intercept, increment the variable `s`
6. Divide `s` by the total numbers, then multiply by the total range area.

## Ungolfed version:

```
import random

def ccw(A,B,C):
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def lit_area(light, vertices):
    # points: list of points
    # i     : x => i=0
    #       : y => i=1
    get_range = lambda i: (min(x[i] for x in vertices), max(x[i] for x in vertices))
    xr = abs(get_range(0)[0] - get_range(0)[1])
    yr = abs(get_range(1)[0] - get_range(1)[1])

    edges = list(zip(vertices, vertices[1:] + [vertices[0]]))

    num_sims = 1000000

    num_successes = 0
    for _ in range(num_sims):
        guess_x = random.uniform(*get_range(0))
        guess_y = random.uniform(*get_range(1))

        light_guess_line = ((guess_x, guess_y), light)

        if not any([intersect(*e, *light_guess_line) for e in edges]):
            num_successes += 1
    return float(num_successes / num_sims) * (xr * yr)

if __name__ == "__main__":
    points = [
    (1/2, 18),
    (1,3),
    (5,1/2),
    (7,5),
    (12,7),
    (16,3),
    (15,11),
    (8,19),
    (3,7)
    ]
    light_source = (5,8)
    print("Area lit by light: %f"% lit_area(light_source, points))

```

Try it online!

Credit for line intersection algorithm

Also, credit to all the helpful commenters on how to golf this even further.

# Answer
> 5 votes
# Haskell, 559 ~~618~~ ~~632~~ bytes

```
r(a:b)=b++[a]
s=zip<*>r
(?)a=sum.zipWith(*)a
o(a,b)=r a?b-a?r b
(a,b)!(c,d)=(c-a,d-b)
(a,b)#(c,d)=a*d-b*c
x i a@(e,f)b j c d|let k@(g,h)=a!b;l=c!d;m=c!a;n=l#k;o=m#l/n;p=m#k/n;q|i>0=o<0||o>1|let=o<=0||o>=1;r|n==0||q||p<0||p*j>1=[]|let=[(e+o*g,f+o*h)]=r
(a&b)(c:e@(d:_))|let(f,g)=span(/=d)b;h=zip f$r$f++[d]=concat[[k,l]|(i,j)<-h,[[k],[l]]<-[x 1 i j 0 a<$>[c,d]],and[x 0 m n 1 a o==[]|o<-[k,l],(m,n)<-h,(m,n)/=(i,j)]]++(a&g)e
(_&_)_=[]
z a b=sum[o$unzip[c,a,d]|e@(f:_)<-[[c|c<-b,and[all(==c)$x 1 d e 1 a c|(d,e)<-s b]]],(c,d)<-s$a&until((f==).head)r b$e++[f]]/2

```

Exact solution (barring bugs). Haskell has built-in exact rational arithmetic. Try it online!

Note that this gives `815523/6710`, not `814643/6710`, for the example room, and the first wall intersection is calculated as `(55/61, 363/61)`. I'm fairly sure this is correct because the Monte Carlo entry (slowly) converges to the same result.

Legend:

```
z light roomPoints
    -- Main function, returns lit area.
    -- Compute list of visible corners in the room, then calls (&).
(&) light roomPoints' visibleCorners
    -- Compute visibility polygon. visibleCorners is the subset of points
    -- that are visible from the light. The first point of roomPoints'
    -- must coincide with the first visibleCorner.
x pEndpoints p1 p2 qSegment q1 q2
    -- Intersect line segments (p1, p2) and (q1, q2).
    -- If pEndpoints, exclude endpoints p1, p2.
    -- If not qSegment, allow intersection to extend past q2 (i.e. raycast).
r   -- Rotate list by one, used to construct closed loops etc.
s   -- Construct closed loop
(!) -- Vector between two points
(?) -- Dot product
(#) -- Cross product
o   -- Polygon area

```

Bonus: Gloss GUI for testing. Click next to points to move them.

```
import qualified Graphics.Gloss as G
import qualified Graphics.Gloss.Interface.IO.Interact as GI

solnPoly a b|let c@(d:_)=[c|c<-b,and[all(==c)$x 1 d e 1 a c|(d,e)<-s b]]=a&until((d==).head)r b$c++[d]
solnArea = z

main =
  let fromRatP (x, y) = (fromRational x, fromRational y)
      displayScale = 10
      scalePoints = G.scale (fromInteger displayScale) (fromInteger displayScale)
      displayMode = G.InWindow "" (512, 512) (0, 0)
      drawBasePoly pointSz ps =
          mconcat $ G.lineLoop ps :
                    [G.translate x y (G.circleSolid pointSz) | (x, y) <- ps]
      drawVisPolyOf light ps =
          G.color G.blue $ drawBasePoly 0.2 $ map fromRatP $ solnPoly light ps
      drawLight (x, y) =
          G.translate x y $
          G.color G.yellow (G.circleSolid 0.5) <> G.circle 0.5
      draw (light, ps) =
          mconcat [
              scalePoints $ drawLight (fromRatP light),
              scalePoints $ drawBasePoly 0.4 (map fromRatP ps),
              scalePoints $ drawVisPolyOf light ps,
              G.translate (-200) (-50) $ G.scale 0.2 0.2 $
                G.color G.blue $ G.text $ "Lit area: " ++ show (solnArea light ps)
          ]
      event (GI.EventKey (GI.MouseButton GI.LeftButton) GI.Down _ (curx_, cury_)) (light, ps) =
          let dist (x,y) (x',y') = (x'-x)^2 + (y'-y)^2
              curx = curx_ / fromInteger displayScale
              cury = cury_ / fromInteger displayScale
              cursorR = (fromInteger$round curx, fromInteger$round cury)
              maxDist = 3
              snapAmount = 1
              (d, i) = minimum [(dist p cursorR, i) | (p, i) <- zip (light : ps) [0..]]
              snapTo n a = fromInteger$n*round(a/fromInteger n)
              snapCursor = (snapTo snapAmount curx, snapTo snapAmount cury)
              light' | i == 0 && d < maxDist^2 = snapCursor
                     | otherwise = light
              ps' | i > 0 && d < maxDist^2 = take (i-1) ps ++ [snapCursor] ++ drop i ps
                  | otherwise = ps
          in (light', ps')
      event _ state = state
      state0 =
        ((2, 2), [(0, 0), (10, 0), (10, 5), (20, 0), (20, 20), (15, 5),
                  (10, 10), (6, 10), (10, 12), (0, 12), (4, 10), (0, 10)])
  in G.play displayMode G.white 60
            state0
            draw
            event
            (\_ -> id)

```

# Answer
> 1 votes
# APL+WIN

This is an ungolfed version of this interesting challenge which I offer to demonstrate my logic. My ancient version of APL+WIN is not well suited to golfing nested control structures. More modern APLs could well do better - challenge?

If readers validate the logic I will have a go at golfing this solution. If the logic is wrong I will simply delete.

```
r←b Room v

⍝Separate x and y coordinates of vertices
x←v[;1] ⋄ y←v[;2]

⍝Intercept and slope of each line segment and ray through each vertex
s←(y,¨1⌽y)⌹¨(1E¯9+1,[1.1]¨x,¨1⌽1E¯9+x)
l←(y,¨b[2])⌹¨(1E¯9+1,[1.1]¨x,¨b[1]+1E¯9)

⍝Coordinates of vertices
x←x,¨1⌽x ⋄ y←y,¨1⌽y

⍝Initialise intersection matrix
r←((⍴s),0)⍴0

⍝Evaluate intersection matrix
:for i :in ⍳⍴l
    t←0⍴0
    :for j :in ⍳⍴s
        t←t,⍎1⍕∊((↑∊l[i])-↑∊s[j])÷((1↓∊s[j])-1↓∊l[i])
    :endfor
    z←r←r,t
:endfor

⍝Identify x coordinates of valid intersections in the direction of the ray
:for i :in ⍳⍴l
    t←(r[i;i])
    :for j :in ⍳⍴s
        :if t<b[1]
            r[j;i]←r[j;i]×(r[j;i]<t)^r[j;i]>⌊/∊x[i]
        :else
            r[j;i]←r[j;i]×(r[j;i]>t)^r[j;i]<⌈/∊x[i]
        :endif
    :endfor
 :endfor

⍝Identify the edges intersected
e←(+/r≠0)/⍳⍴l

⍝Intersection x coordinates
cx←(+/r)[e]

⍝Intersection y coordinates
cy←⍎1⍕+/¨(s[e])× 1,¨(+/r)[e]

⍝Replace original coordinates that are in shadow
x[e]←(1↓¨x[e]),¨cx
y[e]←(1↓¨y[e]),¨cy

⍝Calculate lit area
r←+/.5×(|-/¨x)×|-/¨y

```

# Answer
> 0 votes
# , ~~296~~ 255 bytes

```
function(s,l,u=cbind(s,s[,1]),d=t(diff(t(u))),q=l-u,r=apply(s,1,range),g=c(diff(r)))mean(replicate(1e6,!any((q[i<-1:ncol(s)*2]*(p=runif(2)*g+r[1,]-u)[j<-i-1]>p[i]*q[j])!=(q[i+2]*p[i+1]>q[i+1]*p[i+2])&(p[i]*d[j]>p[j]*d[i])!=(q[i]*d[j]>q[j]*d[i]))))*prod(g)

```

Try it online!

This is a further reduced version of the Python answer. The core Monte Carlo method is the same, but I rearranged some of the functions to make them shorter. In my first iteration, I'd been over-aggressive in rearrangement, and I then realised I could optimise both length and speed by returning to a version of the intersection algorithm closer to the python.

Here's an ungolfed version that also plots the results:

```
find_lit_ungolf <- function(shape, light, plot = TRUE) {
  lines <- cbind(shape ,shape[,1])
  diffs <- t(diff(t(lines)))
  light_minus_lines <- light - lines
  shape_range <- apply(s,1,range)
  shape_range_diff <- c(diff(shape_range))
  successes <- t(replicate(
    n = 1e5,
    {
      random_point <- runif(2) * shape_range_diff + shape_range[1, ]
      random_minus_lines <- random_point - lines
      q <- light_minus_lines
      p <- random_minus_lines
      d <- diffs
      i <- 1:ncol(s)*2
      success <-
        !any((q[i]*p[i-1]>p[i]*q[i-1])!=(q[i+2]*p[i+1]>q[i+1]*p[i+2])&(p[i]*d[i-1]>p[i-1]*d[i])!=(q[i]*d[i-1]>q[i-1]*d[i]))
      c(random_point, success)
    }))
  colnames(successes) <- c("x", "y", "success")
  if (plot) {
    shape <- t(shape)
    colnames(shape) <- c("x", "y")
    print(ggplot(as_tibble(successes), aes(x, y)) +
      geom_point(aes(colour = factor(success)), alpha = 0.3) +
      geom_polygon(data = as_tibble(shape), alpha = 0.2) +
      annotate("point", light[1], light[2], col = "yellow"))
  }
  mean(successes[, 3]) * prod(shape_range_diff)
}
find_lit_ungolf(s, l)

```

---
Tags: code-golf, geometry
---


title: Removing unique elements from string

text:
# Question
Title: Removing unique elements from string
I came upon this question, because it seems to be very common use-case to find unique characters in string. But what if we want to get rid of them?

Input contains only lower case alphabets. Only letters from a to z are used. Input length may be from 1 to 1000 characters.

Example:
input: helloworld
output: llool

Objective: Shortest code wins
Language: Any of the top 20 of TIOBE languages

# Answer
> 7 votes
## Perl, 28 24 characters (includes 1 for 'p' option)

```
s/./$&x(s!$&!$&!g>1)/eg

```

Usage:

```
> perl -pe 's/./$&x(s!$&!$&!g>1)/eg'
helloworld
llool

```

At first I thought I could do this with negative look-ahead and negative look-behind, but it turns out that negative look-behinds must have a fixed length. So I went for nested regexes instead. With thanks to mob for the `$&` tip.

# Answer
> 12 votes
### (GolfScript, 15 13 characters)

```
:;{.;?);>?)},

```

GolfScript is not one of the top 20, but a codegolf without GolfScript... (run it yourself)

*Previous Version: (run script)*

```
1/:;{;\-,;,(<},

```

# Answer
> 7 votes
## J, 12 characters

Having entered a valid Perl answer, here's an invalid (language not in the TIOBE top 20) answer.

```
a=:#~1<+/@e.

```

Usage:

```
   a 'helloworld'
llool

```

Declares a verb `a` which outputs only non unique items.

# Answer
> 5 votes
## GolfScript (14 chars)

```
:x{{=}+x\,,(},

```

Online demo

Might not qualify to win, but it's useful to have a yardstick.

# Answer
> 4 votes
# Ruby 46 40 36

```
gets.chars{|c|$><<c if$_.count(c)>1}

```

# Answer
> 3 votes
# Japt, ~~6~~ 5 bytes

```
ÆèX É

```

*-1 byte thanks to @Oliver*

Try it online!

# Answer
> 2 votes
# Mathematica 72 63

Ok, Mathematica isn't among the top 20 languages, but I decided to join the party anyway.

`x` is the input string.

```
"" <> Select[y = Characters@x, ! MemberQ[Cases[Tally@y, {a_, 1} :> a], #] &]

```

# Answer
> 2 votes
## Python 2.7 (~~52~~ 51), ~~Python 3 (52)~~

I didn't expect it to be so short.

2.7: `a=raw_input();print filter(lambda x:a.count(x)>1,a)`

~~3.0: `a=input();print''.join(i for i in a if a.count(x)>1)`~~

`raw_input()`: store input as a string (`input()` = `eval(raw_input())`)
(Python 3.0: `input()` has been turned into `raw_input()`)

`filter(lambda x:a.count(x)>1,a)`: Filter through all characters within `a` if they are found in `a` more than once (`a.count(x)>1`).

# Answer
> 2 votes
## Perl 44

```
$l=$_;print join"",grep{$l=~/$_.*$_/}split""

```

Execution:

```
perl -lane '$l=$_;print join"",grep{$l=~/$_.*$_/}split""' <<< helloworld
llool

```

# Answer
> 2 votes
# K, 18

```
{x@&x in&~1=#:'=x}

```

# Answer
> 2 votes
## sed and coreutils (128)

Granted this is not part of the TIOBE list, but it's fun (-:

```
<<<$s sed 's/./&\n/g'|head -c -1|sort|uniq -c|sed -n 's/^ *1 (.*)/\1/p'|tr -d '\n'|sed 's:^:s/[:; s:$:]//g\n:'|sed -f - <(<<<$s)

```

De-golfed version:

```
s=helloworld
<<< $s sed 's/./&\n/g'        \
| head -c -1                  \
| sort                        \
| uniq -c                     \
| sed -n 's/^ *1 (.*)/\1/p'   \
| tr -d '\n'                  \
| sed 's:^:s/[:; s:$:]//g\n:' \
| sed -f - <(<<< $s)

```

### Explanation

The first sed converts input into one character per line. The second sed finds characters that only occur once. Third sed writes a sed script that deletes unique characters. The last sed executes the generated script.

# Answer
> 2 votes
# Brachylog (v2), 8 bytes

```
⊇.oḅlⁿ1∧

```

Try it online!

Function submission. Technically noncompeting because the question has a limitation on what langauges are allowed to compete (however, several other answers have already ignored the restriction).

## Explanation

```
⊇.oḅlⁿ1∧
⊇         Find {the longest possible} subset of the input
  o       {for which after} sorting it,
   ḅ        and dividing the sorted input into blocks of identical elements,
    lⁿ1     the length of a resulting block is never 1
 .     ∧  Output the subset in question.

```

# Answer
> 1 votes
## Python (56)

Here's another (few chars longer) alternative in Python:

```
a=raw_input();print''.join(c for c in a if a.count(c)>1)

```

---

If you accept output as a list (e.g. `['l', 'l', 'o', 'o', 'l']`), then we could boil it down to **49** characters:

```
a=raw_input();print[c for c in a if a.count(c)>1]

```

# Answer
> 1 votes
## Perl (55)

```
@x=split//,<>;$s{$_}++for@x;for(@x){print if($s{$_}>1)}

```

Reads from stdin.

# Answer
> 1 votes
# Ocaml, ~~139~~ 133

Uses ExtLib's ExtString.String

```
open ExtString.String
let f s=let g c=fold_left(fun a d->a+Obj.magic(d=c))0 s in replace_chars(fun c->if g c=1 then""else of_char c)s

```

Non-golfed version

```
open ExtString.String
let f s =
  let g c =
    fold_left
      (fun a c' -> a + Obj.magic (c' = c))
      0
      s
  in replace_chars
  (fun c ->
    if g c = 1
    then ""
    else of_char c)
  s

```

The function `g` returns the number of occurences of c in the string s. The function `f` replaces all chars either by the empty string or the string containing the char depending on the number of occurences. Edit: I shortened the code by 6 characters by abusing the internal representation of bools :-)

Oh, and ocaml is 0 on the TIOBE index ;-)

# Answer
> 1 votes
## C# – 77 characters

```
Func<string,string>F=s=>new string(s.Where(c=>s.Count(d=>c==d)>1).ToArray());

```

If you accept the output as an array, it boils down to **65** characters:

```
Func<string,char[]>F=s=>s.Where(c=>s.Count(d=>c==d)>1).ToArray();

```

# Answer
> 1 votes
# PHP - 70

```
while($x<strlen($s)){$c=$s[$x];echo substr_count($s,$c)>1?$c:'';$x++;}

```

with asumption $s = 'helloworld'.

# Answer
> 1 votes
# Java 8, 90 bytes

```
s->{for(char c=96;++c<123;s=s.matches(".*"+c+".*"+c+".*")?s:s.replace(c+"",""));return s;}

```

**Explanation:**

Try it online.

```
s->{                         // Method with String as both parameter and return-type
  for(char c=96;++c<123;     //  Loop over the lowercase alphabet
    s=s.matches(".*"+c+".*"+c+".*")?
                             //   If the String contains the character more than once
       s                     //    Keep the String as is
      :                      //   Else (only contains it once):
       s.replace(c+"",""));  //    Remove this character from the String
  return s;}                 //  Return the modified String

```

# Answer
> 1 votes
# PowerShell, 59 bytes

```
"$args"-replace"[^$($args|% t*y|group|?{$_.Count-1}|% n*)]"

```

Try it online!

Less golfed:

```
$repeatedСhars=$args|% toCharArray|group|?{$_.Count-1}|% name
"$args"-replace"[^$repeatedСhars]"

```

Note: `$repeatedChars` is an array. By default, a Powershell joins array elements by space char while convert the array to string. So, the regexp contains spaces (In this example, `[^l o]`). Spaces do not affect the result because the input string contains letters only.

# Answer
> 1 votes
# APL (Dyalog Extended), 8 bytesSBCS

Anonymous tacit prefix function.

```
∊⊢⊆⍨1<⍧⍨

```

Try it online!

`⍧⍨` count-in selfie (count occurrences of argument elements in the argument itself)

`1<` Boolean mask where one is less than that

`⊢⊆⍨` partition the argument by that mask (beginning a new partition on 1s and removing on 0s)

**ϵ**nlist (flatten)

# Answer
> 1 votes
# JavaScript, 45 bytes

```
s=>[...s].filter(c=>s.match(c+'.*'+c)).join``

```

# Answer
> 1 votes
# , 70 bytes

```
a=utf8ToInt(scan(,''));intToUtf8(a[!a%in%names(table(a)[table(a)<2])])

```

Try it online!

A poor attempt, even from a TIOBE top 20 language. I know something can be done about the second half, but at the moment, any golfs escape me.

# Answer
> 1 votes
# JavaScript (Node.js), 82 bytes

```
p=>[...p].map((v,i,a)=>a.filter(f=>f==v).length).reduce((a,c,i)=>c>1?a+=p[i]:a,[])

```

Try it online!

# Answer
> 1 votes
# JavaScript, 34 bytes

Input as a string, output as a character array.

```
s=>[...s].filter(x=>s.split(x)[2])

```

Try It Online!

# Answer
> 1 votes
# C++, 139 bytes

```
string s;cin>>s;string w{s}; auto l=remove_if(begin(s),end(s),[&w](auto&s){return count(begin(w),end(w),s)==1;});s.erase(l,end(s));cout<<s;

```

ungolfed:

```
#include <algorithm>
#include <string>
#include <iostream>

int main() {
  using namespace std;
  string s;
  cin >> s;
  const string w{s};
  auto l = remove_if(begin(s), end(s), [&w](auto& s) {
                                         return count(begin(w), end(w), s) == 1;
                                       });
  s.erase(l, end(s));
  cout << s;
  return 0;
}

```

# Answer
> 0 votes
## PHP - 137

**Code**

```
implode('',array_intersect(str_split($text),array_flip(array_filter(array_count_values(str_split($text)),function($x){return $x>=2;}))));

```

**Normal Code**

```
$text   = 'helloworld';
$filter = array_filter(array_count_values(str_split($text)), function($x){return $x>=2;});
$output = implode('',array_intersect(str_split($text),array_flip($filter)));

echo $output;

```

# Answer
> 0 votes
**PHP - 83 78**

```
<?for($a=$argv[1];$i<strlen($a);$r[$a[$i++]]++)foreach($ras$k=>$c)if($c>1)echo$k

```

Improved version:

```
<?for($s=$argv[1];$x<strlen($s);$c=$s[$x++]) echo substr_count($s,$c)>1?$c:'';

```

Of course this needs notices to be turned off

**Edit:** Improvement inspired by @hengky mulyono

I am so bad at codegolf :)

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


title: How many Lynch-Bell numbers are there?

text:
# Question
Title: How many Lynch-Bell numbers are there?
## Challenge

Given an integer, `n`, as input where `36 >= n >= 2`, output how many Lynch-Bell numbers there are in base `n`.

The output must be in base 10.

## Lynch-Bell Numbers

A number is a Lynch-Bell numbers if:

* All of its digits are unique (no repetition of digits)
* The number is divisible by each of its digits
* It doesn't contain zero as one of its digits

Since, all of the digits have to be unique, and you have a finite set of single digit numbers in each base, there is a finite number of Lynch-Bell numbers.

For example, in base 2 there is only one Lynch-Bell number, `1`, since all other numbers either repeat digits or contain a 0.

## Examples

```
Input > Output
2 > 1
3 > 2
4 > 6
5 > 10
6 > 10
7 > 75
8 > 144
9 > 487
10 > 548

```

*Mathematica Online ran out of memory above base 10. You can use the following code to generate your own:*

```
Do[Print[i," > ",Count[Join@@Permutations/@Rest@Subsets@Range[#-1],x_/;And@@(x\[Divides]FromDigits[x,#])]&[i]],{i,10,36,1}]

```

## Winning

Shortest code in bytes wins.

# Answer
# Jelly, 13 bytes

```
Q⁼g
*`Ṗ©bç"®S

```

Try it online!

Another *O(nn)* solution.

## Explanation

```
Q⁼g  Helper link. Input: digits (LHS), integer (RHS)
Q    Unique (digits)
 ⁼   Match
  g  GCD between each digit and the integer

*`Ṗ©bç"®S  Main link. Input: integer n
*`         Compute n^n
  Ṗ        Pop, forms the range [1, n^n-1]
   ©       Store previous result in register
    b      Convert each integer to base n
     ç"    Call the helper link, vectorized, with
       ®   The register's value
        S  Sum

```
> 8 votes

# Answer
# Jelly, 15 bytes

```
*ḃ€’Q€Qḍḅ¥€⁸Ạ€S

```

Try it online!

Complexity `O(n<sup>n</sup>)`.
> 5 votes

# Answer
# Java, ~~222~~ ~~212~~ 190 bytes

-10 bytes thanks to Herman

-22 bytes thanks to Kevin

```
import java.util.*;a->{int c=0,i=1;A:for(;i<Math.pow(a,a);i++){Set g=new HashSet();for(char b:a.toString(i).toCharArray())if(!g.add(b)|b<49||i%a.parseInt(b+"",a)>0)continue A;c++;}return c;}

```

Ungolfed:

```
a -> {
    int count = 0;
    OUTER:
    for (int i = 1; i < Math.pow(a, a); i++) {
        Set<Character> found = new HashSet<>();
        for (char b : Integer.toString(i, a).toCharArray()) {
            if (!found.add(b) || b == 48 || i % Integer.parseInt(b + "", a) != 0) {
                continue OUTER;
            }
        }
        count++;
    }
    return count;
}

```

Try it online!

Gets very slow for large numbers.
> 3 votes

# Answer
# Perl 6, ~~86~~ ~~84~~ 77 bytes

*-2 bytes thanks to Ramillies*

```
->\n{n-1+grep {.Set==$_&&.reduce(* *n+*)%%.all},map {|[X] (1..^n)xx$_},2..^n}

```

Try it online!

Works for n=8 on TIO.
> 3 votes

# Answer
# Mathematica, ~~82~~ ~~79~~ 76 bytes

```
Count[Join@@Permutations/@Subsets@Range[#-1],x_/;x==x~FromDigits~#~GCD~x]-1&

```
> 2 votes

# Answer
# Actually, 24 bytes

```
;╗DR⌠╜DR╨i⌡M⌠;╜@¿♀%ΣY⌡MΣ

```

Try it online!

## Explanation

This program consists of two main parts: the permutation generation, and the Lynch-Bell test. So, this explanation will look at each part separately, for greater clarity.

### Generating Permutations

Input: `n` (an integer in `[2, 36]`)

Output: all partial and total permutations of `[1, n-1]` (sequences containing values from `[1, n-1]` without repetition whose length is in `[1, n-1]`)

```
;╗DR⌠╜DR╨i⌡M
;╗            store a copy of n in register 0
  DR          range(1, n)
    ⌠╜DR╨i⌡M  do the following for each element k in range:
     ╜DR        range(1, n)
        ╨       k-permutations of [1, n-1]
         i      flatten

```

### Lynch-Bell Test

Input: a list of base-`n` integers, represented as lists of base-`n` digits

Output: the number of Lynch-Bell numbers in base `n`

```
⌠;╜@¿♀%ΣY⌡MΣ
⌠;╜@¿♀%ΣY⌡M   for each base-n digit list a:
 ;╜             duplicate a, push n
   @¿           convert a from base-n to decimal
     ♀%         modulo a with each of its base-n digits
       Σ        sum
        Y       boolean negation (1 if all modulo results are 0, else 0)
           Σ  sum (count the 1s in the resultant list)

```
> 2 votes

# Answer
# 05AB1E, 22 bytes

```
mLIBε0KÙ}ÙvyIöySIö%O_O

```

Try it online!

`O_O` was also my face when this finally worked.

`<ÝIBJ0Kæ¦Ù€œ˜` is faster than the way I use to generate the numbers in the actual answer but randomly stops working for anything bigger than 7 (for no apparent reason?)

### Explanation

```
mLIBε0KÙ}ÙvyIöySIö%O_O # (input = i)
m                      # Push i^i
 L                     # ...and get a range from one to this value
  IB                   # Map every element to their base i representation
    ε   }              # Map every element to ...
     0K                 # Itself without 0s
       Ù                # ...and only unique digits
         Ù             # Uniquify the resulting list
          v            # For each element...
           yIö          # Push it converted to base 10
              ySIö      # Push every digit of it converted to base 10 in a list
                  %     # Calculate the modulo for each digit
                   O    # Sum all results together
                    _   # Negate: Returns 0 for every positive number and 1 for 0
                     O  # Sum with the rest of the stack (Basically counting all Lynch-Bell-Numbers)
                       # Implicit print

```
> 1 votes

# Answer
## Perl 5, 80 76 bytes (75 + `-p`)

```
$\+=!grep$_?$;%$_|$|{0,$_}++:1,@@until($@[$}++]+=1)%=$_ and++$;,$}=$}==$_}{

```

Abusing `$;` for fun and profit. Times out on inputs \> 8.

EDIT: -4 bytes by merging the two loops.
> 1 votes

# Answer
# Ruby, ~~80~~ 65 bytes

```
->n{(1..n**n).count{|i|(d=i.digits n)-[0]==d|d&&d.sum{|j|i%j}<1}}

```

Try it online!

Thanks to G B for -15 bytes.
> 1 votes

# Answer
# Japt `-x`, ~~25~~ 19 bytes

-6 bytes thanks to Shaggy

```
pU õìU ËeDâ f myDìU

```

Try it online!
> 1 votes

# Answer
# Python 3, 204 174 bytes

```
lambda x,r=range,i=chain:sum(0**any(int(''.join(map(str,y)),x)%z for z in y)for y in i(*map(permutations,i(*[combinations(r(1,x),e)for e in r(x)]))))-1
from itertools import*

```

Try it online!

For each permutation of each element of powerset of range(1,n) (no zeros, unique), convert to numerical string to base n. Sum all that are divisible by each digit, subtract 1 due to powerset generating the empty set.

-30 bytes thanks to @ovs!
> 0 votes

# Answer
# Haskell, 117 bytes

```
f n=sum[1|x<-id=<<[mapM(\_->[1..n-1])[0..m]|m<-[0..n]],all(\y->[mod(sum(zipWith((*).(n^))[0..]x))y|c<-x,c==y]==[0])x]

```

Try it online! Works on TIO up to `n=7` before timing out.
> 0 votes

# Answer
# Perl 5, 108 + 1 (`-p`) = 109 bytes

```
while(@a<$_){$r=%k=@a=();for($t=++$i;$t;$t=int$t/$_){push@a,$t%$_}$r||=!$_||$i%$_||$k{$_}++for@a;$r||$\++}}{

```

Try it online!

It's a pig. Not sure if it will do more than base 8 on TIO without timing out.
> 0 votes

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

```
n=>{int j,i,p;for(j=i=0;i++<~0UL;){p=i;var a=new List<int>();for(;p>0;p/=n)a.Add(p%n);j+=a.All(c=>c>0&&i%c<1&a.Count(x=>x==c)<2)?1:0;}return j;}

```

Goes through all the numbers from 0 to `ulong.MaxValue`, and selects those that are Lynch-Bell numbers in the specified base. Takes forever to run, even for 2, though if you set the `~0UL` part in the for loop to something smaller, you can get output for input up to 7 within a minute on TIO.

Try it online!
> 0 votes

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