title: Parallel accounts (Day 2)

text:
# Question
Title: Parallel accounts (Day 2)
Challenge Taken with permission from my University Code Challenge Contest

---

After finishing her studies a couple of months ago, Marie opened a bank account to start receiving the payment of her first job in town. Since then she has been performing a few transactions with it. Her first payment was $1000 dollars. With that money she paid for a dinner in which she invited her parents (The dinner cost $150 dollars), then, she did a purchase in a well-known supermarket ($80 dollars) and a hotel reservation for her vacations ($200). At the end of the month she received her payment again (1040 dollars, a little more than the previous month) and the day after she spent another $70 dollars at the supermarket.

Today, she realized that if after paying the first $80 dollars in the supermarket a second account had been created and the first one frozen, both accounts would have exactly the same balance:

$$ \underbrace{1000\quad -150\quad -80}\_{Total=770}\quad \underbrace{-200\quad 1040\quad -70}\_{Total=770} $$

The event was so rare to her that she wants to continue ascertaining if the movements of her account and those of her friends have also this feature or not.

**Challenge**

Given a list of transactions, output the number of instants of time in which the owner of the bank account could have created a second account so that both had the same final balance.

**Example:** `[1000, -150, -80, -200, 1040, -70]` $$ \color{red}{1)\quad\underbrace{}\_{Total=0}\quad \underbrace{1000\quad -150\quad -80\quad -200\quad 1040\quad -70}\_{Total=1540}} $$ $$ \color{red}{2)\quad\underbrace{1000}\_{Total=1000}\quad \underbrace{-150\quad -80\quad -200\quad 1040\quad -70}\_{Total=540}} $$ $$ \color{red}{3)\quad\underbrace{1000\quad -150}\_{Total=850}\quad \underbrace{-80\quad -200\quad 1040\quad -70}\_{Total=690}} $$ $$ \color{green}{4)\quad\underbrace{1000\quad -150\quad -80}\_{Total=770}\quad \underbrace{-200\quad 1040\quad -70}\_{Total=770}} $$ $$ \color{red}{5)\quad\underbrace{1000\quad -150\quad -80\quad-200}\_{Total=570}\quad \underbrace{ 1040\quad -70}\_{Total=970}} $$ $$ \color{red}{6)\quad\underbrace{1000\quad -150\quad -80\quad -200\quad 1040}\_{Total=1610}\quad \underbrace{-70}\_{Total=-70}} $$ $$ \color{red}{7)\quad\underbrace{1000\quad -150\quad -80\quad-200\quad 1040\quad -70}\_{Total=1540}\quad \underbrace{}\_{Total=0}} $$

**Test Case**

* Input: `1000 -150 -80 -200 1040 -70` Output: `1`
* Input: `100 -100` Output: `2`
* Input: `1 2 3` Output: `1`
* Input: `10 -20 15` Output: `0`
* Input: `15 -15 15 -15` Output: `3`
* Input: `1` Output: `0`

**Notes**

* You can assume there wont be any transaction of $0 dollars
* You can take input in any reasonable way

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

```
n=>n.Append(0).Where((a,b)=>n.Take(b).Sum()*2==n.Sum()).Count()

```

Saved 6 bytes thanks to dana

Try it online!
> 5 votes

# Answer
# Perl 6, 25 bytes

```
{+grep .sum/2,[\+] 0,|$_}

```

Try it online!

# Explanation

We just prepend a zero to the given list (`0,|$_`), make a sequence of partial sums with `[\+]` (i. e. the sequence formed by the first element, the sum of first two, the sum of first three etc.), and look (`grep`) for any elements that are exactly equal to the half of the final account state (sum of the given list). Finally, we count them with a `+`.
> 4 votes

# Answer
# 05AB1E, 11 bytes

```
0.ø.œ2ùO€ËO

```

Try it online or verify all test cases.

**Explanation:**

```
0.ø          # Surround the (implicit) input list with a leading and trailing 0
             #  i.e. [100,-100] → [0,100,-100,0]
   .œ        # Get all possible partitions to divide the list
             #  → [[[0],[100],[-100],[0]],[[0],[100],[-100,0]],[[0],[100,-100],[0]],[[0],[100,-100,0]],[[0,100],[-100],[0]],[[0,100],[-100,0]],[[0,100,-100],[0]],[[0,100,-100,0]]]
     2ù      # Only leave partitions consisting of 2 items
             #  → [[[0],[100,-100,0]],[[0,100],[-100,0]],[[0,100,-100],[0]]]
       O     # Take the sum of each
             #  → [[0,0],[100,-100],[0,0]]
        €Ë   # Check of each inner list if both sums are equal (1 if truthy; 0 if falsey)
             #  → [1,0,1]
          O  # Take the sum of that (and output as result)
             #  → 2

```
> 3 votes

# Answer
# Jelly, ~~11~~ 6 bytes

```
ŻÄḤ=SS

```

Try it online!
> 3 votes

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

```
a=>!a.map(v=>o[s+=v]=-~o[s],s=0,o=[1])|o[s/2]

```

Try it online!

Save 4 bytes by using `-~o[s]`. Thanks to Shaggy.
> 3 votes

# Answer
# JavaScript (ES6), 52 bytes

```
a=>a.map(x=>n+=(s+=x)==eval(a.join`+`)-s,n=s=0)|n+!s

```

Try it online!

### Commented

```
a =>                        // a[] = input array
  a.map(x =>                // for each element x in a[]:
    n +=                    //   increment n if the following test is truthy:
      (s += x)              //     update the left sum
      ==                    //     and test whether it's equal to
      eval(a.join`+`) - s,  //     the right sum
    n = s =0                //   start with n = s = 0
  )                         // end of map()
  | n                       // yield n; if the final sum is 0, it means that we could have
  +                         // created a balanced account at the beginning of the process;
  !s                        // so, we increment n if it is

```

---

# Recursive version,  ~~54~~  53 bytes

```
f=(a,s=0)=>a+a?(s==eval(a.join`+`))+f(a,s+a.pop()):!s

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), 21 bytesSBCS

Anonymous tacit prefix function

```
+/⊂((+/↑)=1⊥↓)¨⍨0,⍳∘≢

```

Try it online!

**ɩ**ndices
of
the tally of transactions

`0,` prepend zero

`⊂(``)¨⍨` apply the following tacit function with each of those as left argument and the entire list of transactions as right argument ( swaps argument

the entire list of transactions
`(``)` as left argument to the below function
`¨` applied to each of the indices
with swapped arguments (i.e. list on right, indices on left:

drop that many from the left

`1⊥` sum (lit. evaluate in base-1)

`(``)=` is it (0/1) equal to…

take that many transactions from the left

`+/` sum them

`+/` sum that Boolean list to get the count of truths
> 2 votes

# Answer
# Japt `-x`, ~~14~~ 11 bytes

```
iT å+ ®¥nUx

```

Try it

```
iT å+ ®¥nUx     :Implicit input of array U
i               :Prepend
 T              :  Zero
   å+           :Cumulatively reduce by addition
      ®         :Map each Z
       ¥        :  Test for equality with
        n       :  Z subtracted from
         Ux     :  U reduced by addition
                :Implicitly reduce by addition and output

```
> 2 votes

# Answer
# Python 3, ~~67~~ 58 bytes

```
lambda l:sum(sum(l[:x])*2==sum(l)for x in range(len(l)+1))

```

Try it online!

*-9 bytes thanks to @Don't be a x-triple dot*
> 2 votes

# Answer
# , ~~50~~ 37 bytes

```
sum(c(0,cumsum(x<-scan()))==sum(x)/2)

```

Try it online!
> 2 votes

# Answer
# Perl 5 `-p`, ~~42~~ 41 bytes

*@NahuelFouilleul saves a byte*

```
y/ /+/;$\+=eval$'==eval$`while/^|$|\+/g}{

```

Try it online!
> 2 votes

# Answer
## Batch, 84 bytes

```
@set s=%*
@set/as=%s: =+%,c=0
@for %%n in (0 %*)do @set/as-=%%n*2,c+=!s
@echo %c%

```

Takes input as command-line arguments. Explanation:

```
@set s=%*

```

Join the arguments with spaces.

```
@set/as=%s: =+%,c=0

```

Replace the spaces with `+`s and evaluate the result. Also clear the count.

```
@for %%n in (0 %*)do @set/as-=%%n*2,c+=!s

```

For each amount, subtract double that from the sum. If the result is zero, then this is a valid match, so increment the count. The extra zero at the beginning allows for a match before any amounts.

```
@echo %c%

```

Print the result.
> 2 votes

# Answer
# Charcoal, 15 bytes

```
⊞θ⁰ＩΣＥθ⁼Σθ⊗Σ✂θκ

```

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

```
 θ              Input list
  ⁰             Literal 0
⊞               Push to list
      θ         Augmented list
     Ｅ          Mapped to
             θ  Augmented list
            ✂   Sliced from
              κ Current index
           Σ    Summed
          ⊗     Doubled
       ⁼        Equals
         θ      (Augmented) list
        Σ       Summed
    Σ           Sum of booleans
   Ｉ            Cast to string
                Implicitly print

```

Unfortunately in Charcoal `Sum([])` is not `0` so I have to ensure that there is always at least one element to sum.
> 2 votes

# Answer
# PowerShell, ~~88~~ 82 bytes

-6 Bytes thanks to mazzy

```
param($n)0..($x=$n.length)|%{$i+=+$z-eq($n[$_..$x]|measure -Su).sum;$z+=$n[$_]};$i

```

Try it online!

This seems like a very clumsy method but it got the job done. I'll try and revamp it in the future.
> 2 votes

# Answer
# MATL, 9 bytes

```
s0GhYsE=s

```

Try it online!

Same approach as some other answers: prepend a zero, and check how often half the cumulative sum is equal to the total sum.

```
s   % Total sum of (implicit) input
0Gh % Prepend 0 to another copy of the input
Ys  % Cumulative sum
E=  % Check element-wise equality of 2*cumulative sum with total sum
s   % Sum number of `true` values

```
> 2 votes

# Answer
# PowerShell, ~~49~~ ~~45~~ 36 bytes

```
(($args+0|%{2*($s+=$_)})-eq$s).count

```

Try it online!
> 2 votes

# Answer
# Brachylog, 9 bytes

Not as good as day 1. This one loses to Jelly

```
{~c₂+ᵐ=}ᶜ

```

## Explanation

```
{      }ᶜ   # Count the ways to:
 ~c₂        #   Split the input array in 2 ...
    +ᵐ      #   so that their sums ...
      =     #   are equal

```

Test suite: Try it online!
> 2 votes

# Answer
# bash, 52 bytes

```
IFS=+;for i in 0 $@;{((c+=2*(x+=i)=="$*"));};echo $c

```

TIO

The trick: setting `IFS=+`, `"$*"` expands to a string where arguments are delimited by `+`, in arithmetic expression eval to the sum
> 1 votes

# Answer
## Haskell, ~~46~~ 35 bytes

```
f x=sum[1|a<-scanl(+)0x,a==sum x/2]

```

Try it online!
> 0 votes

# Answer
# , 19 bytes

```
1#.[:(={:-])0+/\@,]

```

Try it online!

## explanation

```
1 #. [: (= ({: - ])) 0 +/\@, ]

                     0     , ]  NB. prepend 0 to input...
                       +/\@     NB. and take the prefix sums...
     [:    ({: - ])             NB. then subtract that list
                                NB. from its final elm
                                NB. (`{:`), giving the list
                                NB. of suffix sums...
     [: (= (      ))            NB. create a 1-0 list showing
                                NB. where the prefix sums
                                NB. equal the suffix sums
1 #.                            NB. and take the sum.

```
> 0 votes

---
Tags: code-golf
---


title: School moving out (Day 1)

text:
# Question
Title: School moving out (Day 1)
Challenge Taken with permission from my University Code Challenge Contest

---

For some years now, the number of students in my school has been growing steadily. First the number of students was increased by classroom, but then it was necessary to convert some spaces for some groups to give classes there, such as the gym stands or, this last course, up to the broom room.

Last year the academic authorities got the budget to build a new building and started the works. At last they have finished and the new building can be used already, so we can move (the old building will be rehabilitated and will be used for another function), but it has caught us halfway through the course. The director wants to know if the move will be possible without splitting or joining groups, or that some students have to change groups.

**Challenge**

Given the amount of students of the current groups and the new classrooms (capacity), output a truthy value if it is possible to assign a different classroom, with sufficient capacity, to each of the current groups, or a falsey value otherwise.

**Test Cases**

```
Input: groups of students => [10, 20, 30], classrooms capacity => [31, 12, 20]
Output: True

Input: groups of students => [10, 20, 30], classrooms capacity => [100, 200]
Output: False

Input: groups of students => [20, 10, 30], classrooms capacity => [20, 20, 50, 40]
Output: True

Input: groups => [30, 10, 30, 5, 100, 99], classrooms => [40, 20, 50, 40, 99, 99]
Output: False

Input: groups => [], classrooms => [10, 10, 10]
Output: True

Input: groups => [10, 10, 10], classrooms => []
Output: False

Input: groups => [], classrooms => []
Output: True

Input: groups => [10, 1], classrooms => [100]
Output: False

Input: groups => [10], classrooms => [100, 100]
Output: True

Input: groups => [1,2,3], classrooms => [1,1,2,3]
Output: True

```

**Notes**

* You can take the input in any reasonable format
* You can output any Truthy/Falsey value (`1/0`, `True/False`, etc...)
*

# Answer
# Brachylog, 4 bytes

It's always nice to see a challenge and know brachylog is gonna beat everyone. Takes current classes as input and new classrooms as output; It will output true if it finds a way to fit the students, false otherwise

```
p≤ᵐ⊆

```

## Explanation

The code has 3 parts of which the order actually doesn't matter

```
≤ᵐ --> projects each value to a value bigger/equal then input
⊆  --> input is a ordered subsequence of output
p  --> permutes the list so it becomes a unordered subsequence

```

Try it online!
> 14 votes

# Answer
# Pyth, 11 bytes

```
.AgM.t_DMQ0

```

Takes input as a list of lists, classroom sizes first, group sizes second. Try it online here, or verify all the test cases at once here.

```
.AgM.t_DMQ0   Implicit: Q=eval(input())
      _DMQ    Sort each element of Q in reverse
    .t    0   Transpose, padding the shorter with zeroes
  gM          Element wise test if first number >= second number
.A            Are all elements truthy? Implicit print

```
> 4 votes

# Answer
# Jelly, 9 bytes

Takes the classrooms as first argument and the groups as second argument.

```
Œ!~+Ṡ‘ḌẠ¬

```

Try it online!

### Commented

*NB: This `Ṡ‘ḌẠ¬` is far too long. But I suspect that this is not the right approach anyway.*

```
Œ!~+Ṡ‘ḌẠ¬  - main link taking the classrooms and the groups e.g. [1,1,2,3], [1,2,3]
Œ!         - computes all permutations of the classrooms    -->  [..., [1,2,3,1], ...]
  ~        - bitwise NOT                                    -->  [..., [-2,-3,-4,-2], ...]
   +       - add the groups to each list; the groups fits   -->  [..., [-1,-1,-1,-2], ...]
             in a given permutation if all resulting values
             are negative
    Ṡ      - take the signs                                 -->  [..., [-1,-1,-1,-1], ...]
     ‘     - increment                                      -->  [..., [0,0,0,0], ...]
      Ḍ    - convert from decimal to integer                -->  [..., 0, ...]
       Ạ   - all truthy?                                    -->  0
        ¬  - logical NOT                                    -->  1

```
> 4 votes

# Answer
# Japt, 9 bytes

```
ñÍí§Vñn)e

```

Try it or run all test cases on TIO

```
ñÍí§Vñn)e     :Implicit input of arrays U=students, V=classrooms
ñ             :Sort U by
 Í            :  Subtracting each integer from 2
  í           :Interleave with
    Vñn       :  V sorted by negating each integer
   §          :  Reduce each pair by checking if the first is <= the second
       )      :End interleaving
        e     :All true?

```

---

```
ñÍeÈ§Vn o

```

Try it or run all test cases on TIO

```
ñÍeÈ§Vn o     :Implicit input of arrays U=students, V=classrooms
ñ             :Sort U by
 Í            :  Subtracting each integer from 2
  e           :Does every element return true
   È          :When passed through the following function
    §         :  Less than or equal to
     Vn       :  Sort V
        o     :  Pop the last element

```
> 4 votes

# Answer
# 05AB1E, ~~14~~ ~~12~~ 8 bytes

```
€{í0ζÆdP

```

Port of *@Sok*'s Pyth answer, so make sure to upvote him as well!

Takes the input as a list of lists, with the classroom-list as first item and group-list as second item.

Try it online or verify all test cases.

**Explanation:**

```
€{         # Sort each inner list
  í        # Reverse each inner list
   0ζ      # Zip/transpose; swapping rows/columns, with 0 as filler
     Æ     # For each pair: subtract the group from the classroom
      d    # Check if its non-negative (1 if truthy; 0 if falsey)
       P   # Check if all are truthy by taking the product
           # (and output implicitly)

```

---

**Old 12-byte answer:**

```
æε{I{0ζÆdP}à

```

Takes the classroom-list first, and then the group-list.

Try it online or verify all test cases.

**Explanation:**

```
æ             # Take the powerset of the (implicit) classroom-list,
              # resulting in a list of all possible sublists of the classrooms
 ε            # Map each classroom sublist to:
  {           #  Sort the sublist
   I{         #  Take the group-list input, and sort it as well
     0ζ       #  Transpose/zip; swapping rows/columns, with 0 as filler
       Æ      #  For each pair: subtract the group from the classroom
        d     #  Check for everything if it's non-negative (1 if truthy; 0 if falsey)
         P    #  Check if all are truthy by taking the product
          }à  # After the map: check if any are truthy by getting the maximum
              # (and output the result implicitly)

```
> 3 votes

# Answer
# Python 2, 49 bytes

Outputs by exit code, fails for falsy input.

```
g,r=map(sorted,input())
while g:g.pop()>r.pop()>y

```

Try it online!
> 3 votes

# Answer
# MATL, 10 bytes

```
yn&Y@>~!Aa

```

Try it online! Or verify all test cases.

### Explanation

Consider inputs `[20, 10, 30]`, `[20, 20, 50, 40]` as an example. Stack is shown bottom to top.

```
y     % Implicit inputs. Duplicate from below
      % STACK: [20 10 30]
               [20 20 50 40]
               [20 10 30]
n     % Number of elements
      % STACK: [20 10 30]
               [20 20 50 40]
               3
&Y@   % Variations. Gives a matrix, each row is a variation
      % STACK: [20 10 30]
               [20 10 30
                20 20 40
                20 20 40
                ···
                50 40 20]
>~    % Less than? Element-wise with broadcast
      % STACK: [1 1 1
                1 1 1
                1 1 1
                ···
                1 1 0]
!     % Transpose
      % STACK: [1 1 1 ··· 0
                1 1 1 ··· 1
                1 1 1 ··· 1]
A     % All. True for columns that only contain nonzeros
      % STACK: [1 1 1 ··· 0]
a     % Any. True if the row vector contains at least a nonzero. Implicit display
      % STACK: 1

```
> 3 votes

# Answer
# Haskell, 40 bytes

```
c%l=[1|x<-l,x>=c]
s#g=and[c%s<=c%g|c<-s]

```

Try it online!
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~77~~ 74 bytes

```
a=>b=>a.Count==a.OrderBy(x=>-x).Zip(b.OrderBy(x=>-x),(x,y)=>x>y?0:1).Sum()

```

Try it online!

Commented code:

```
// a: student group counts
// b: classroom capacities
a=>b=>
  // compare the number of student
  // groups to...
  a.Count==
  // sort student groups descending
  a.OrderBy(x=>-x)
     // combine with classroom
     // capacities sorted descending
     .Zip(
        b.OrderBy(x=>-x),
        // the result selector 1 when
        // the classroom has enough
        // capacity, 0 when it doesn't
        (x,y)=>x<y?0:1
     )
     // add up the 1's to get the number
     // of student groups who can fit
     // in a classroom
     .Sum()

```
> 3 votes

# Answer
## Haskell, 66 bytes

```
import Data.List
q=sortOn(0-)
x#y=and$zipWith(<=)(q x)$q y++(0<$x)

```

Try it online!
> 2 votes

# Answer
# Perl 5 `-pal`, ~~67~~ 62 bytes

*@NahuelFouilleul saved 5 bytes with a rearrangement and a grep*

```
$_=!grep$_>0,map$_-(sort{$b-$a}@F)[$x++],sort{$b-$a}<>=~/\d+/g

```

Try it online!

67 bytes version

Takes the space separated list of class sizes on the first line and the space separated list of room sizes on the next.
> 2 votes

# Answer
# Bash + GNU tools, 68 bytes

```
(sort -nr<<<$2|paste -d- - <(sort -nr<<<$1)|bc|grep -- -)&>/dev/null

```

69 bytes

```
(paste -d- <(sort -nr<<<$2) <(sort -nr<<<$1)|bc|grep -- -)&>/dev/null

```

TIO

takes student rooms as first and second argument as string numbers delimited by newline returns exit status 1 for true or 0 for false
> 2 votes

# Answer
# Common Lisp, 74 bytes

`(defun c(s r)(or(not(sort s'>))(and(sort r'>)(<=(pop s)(pop r))(c s r))))`

## Non-minified

```
(defun can-students-relocate (students rooms)
  (or (not (sort students #'>))
      (and (sort rooms #'>)
           (<= (pop students)
               (pop rooms))
           (can-students-relocate students rooms))))

```

Test it

Note that sort permanently mutates the list, and pop rebinds the variable to the next element.

In effect this just recursively checks that the largest student group can fit in the largest room. There are 3 base-cases:

1. No students - return T
2. Students, but no rooms - return NIL
3. Students and rooms, but largest student group larger than largest room - return NIL
> 2 votes

# Answer
# Python 2, ~~71~~ ~~67~~ 64 bytes

```
lambda g,c:s(g)==s(map(min,zip(s(g)[::-1],s(c)[::-1])))
s=sorted

```

Try it online!
> 1 votes

# Answer
# JavaScript, 56 bytes

```
s=>c=>s.sort(g=(x,y)=>y-x).every((x,y)=>c.sort(g)[y]>=x)

```

Try it
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~105~~ ~~93~~ ~~91~~ ~~82~~ ~~81~~ ~~79~~ ~~77~~ ~~76~~ 74 bytes

Now matches dana's score!

```
n=>m=>{n.Sort();m.Sort();int i=m.Count-n.Count;i/=n.Any(b=>m[i++]<b)?0:1;}

```

Throws an error if false, nothing if true.

-12 bytes thanks to @Destrogio!

Try it online!

# Explanation

```
//Function taking in a list, and returning another function
//that takes in a list and doesn't return
n=>m=>{
  //Sort the student groups from smallest to largest
  n.Sort();
  //Sort the classrooms fom smallest capacity to largest
  m.Sort();
  //Initialize a variable that will function as a sort of index
  int i=m.Count-n.Count;
  //And divide that by...
  i/=
    //0 if any of the student groups...
    n.Any(b=>
      //Don't fit into the corresponding classroom and incrementing i in the process
      /*(In the case that a the amount of classrooms are less than the amount of
      student groups, an IndexOutOfRangeException is thrown)*/
      m[i++]<b)?0
    //Else divide by 1
    :1;
}

```
> 1 votes

# Answer
# Retina 0.8.2, 50 bytes

```
\d+
$*
%O^`1+
%`$
,
^((1*,)(?=.*¶((?>\3?)1*\2)))*¶

```

Try it online! Link includes test suite. Takes two lists of groups and rooms (test suite uses `;` as list separator). Explanation:

```
\d+
$*

```

Convert to unary.

```
%O^`1+

```

Reverse sort each list separately.

```
%`$
,

```

Append a comma to each list.

```
^((1*,)(?=.*¶((?>\3?)1*\2)))*¶

```

Check that each of the numbers in the first list can be matched to the appropriate number in the second list. Each time `\3` contains the previously matched rooms and the next group `\2` therefore needs to be able to fit into the next room. The `(?>\3?)` handles the case of the first room when there are no previous rooms yet.
> 1 votes

# Answer
# Charcoal, 28 bytes

```
Ｗ∧⌊θ¬›⌈§θ¹⌈§θ⁰ＵＭθΦκ⁻ν⌕κ⌈κ¬⊟θ

```

Try it online! Link is to verbose version of code. Takes a list of lists of rooms and groups and outputs `-` if the rooms can accommodate the groups. Explanation:

```
Ｗ∧⌊θ¬›⌈§θ¹⌈§θ⁰

```

Repeat while a group can be assigned to a room.

```
ＵＭθΦκ⁻ν⌕κ⌈κ

```

Remove the largest room and group from their lists.

```
¬⊟θ

```

Check that there are no unallocated groups remaining.
> 1 votes

# Answer
# Perl 6, 34 bytes

```
{none [Z>] $_>>.sort(-*)>>[^.[0]]}

```

Try it online!

Takes input as a list of two lists, the groups and the classrooms, and returns a None Junction that can be boolified to true/false.

### Explanation:

```
{                                }   # Anonymous code block
           $_>>.sort(-*)             # Sort both lists from largest to smallest
                        >>[^.[0]]    # Pad both lists to the length of the first list
 none                                # Are none of
      [Z>]                           # The groups larger than the assigned classroom

```
> 1 votes

# Answer
# Ruby, 57 bytes

```
->c,r{r.permutation.any?{|p|c.zip(p).all?{|a,b|b&&a<=b}}}

```

Try it online!

Takes `c` for classes, `r` for rooms. Checks all permutations of rooms instead of using sort, because reverse sorting costs too many bytes. Still looks rather long though...
> 1 votes

# Answer
# Java (OpenJDK 8), 183 bytes

```
a->{int b=a[0].length;Arrays.sort(a[0]);Arrays.sort(a[1]);if(b>a[1].length){return false;}for(int i=0;i<b;i++){if(a[0][i]>a[1][i]){return false;}}return true;}

```

Try it online!

With a little helpful advice from Kevin Cruijssen and simply another glance over my code myself, I can decrease my score by a whole 9% just by replacing three English words!

# Java (OpenJDK 8), 166 bytes

```
a->{int b=a[0].length;Arrays.sort(a[0]);Arrays.sort(a[1]);if(b>a[1].length){return 0;}for(int i=0;i<b;){if(a[0][i]>a[1][i++]){return 0;}}return 1;}

```

Try it online!
> 0 votes

# Answer
# PowerShell, 80 bytes

```
param($s,$c)!($s|sort -d|?{$_-gt($r=$c|?{$_-notin$o}|sort|select -l 1);$o+=,$r})

```

Try it online!

Less golfed test script:

```
$f = {

param($students,$classrooms)
$x=$students|sort -Descending|where{
    $freeRoomWithMaxCapacity = $classrooms|where{$_ -notin $occupied}|sort|select -Last 1
    $occupied += ,$freeRoomWithMaxCapacity    # append to the array
    $_ -gt $freeRoomWithMaxCapacity           # -gt means 'greater than'. It's a predicate for the 'where'
}                                             # $x contains student groups not assigned to a relevant classroom
!$x                                           # this function returns a true if $x is empty

}

@(
    ,(@(10, 20, 30), @(31, 12, 20), $true)
    ,(@(10, 20, 30), @(100, 200), $False)
    ,(@(20, 10, 30), @(20, 20, 50, 40), $True)
    ,(@(30, 10, 30, 5, 100, 99), @(40, 20, 50, 40, 99, 99), $False)
    ,(@(), @(10, 10, 10), $True)
    ,(@(10, 10, 10), @(), $False)
    ,(@(), @(), $True)
    ,(@(10, 1), @(100), $False)
    ,(@(10), @(100, 100), $True)
    ,(@(1,2,3), @(1,1,2,3), $True)
) | % {
    $students, $classrooms, $expected = $_
    $result = &$f $students $classrooms
    "$($result-eq$expected): $result"
}

```
> 0 votes

# Answer
# , 65 bytes

```
function(g,r)isTRUE(all(Map(`-`,sort(-g),sort(-r)[seq(a=g)])>=0))

```

Try it online!
> 0 votes

---
Tags: code-golf, decision-problem
---


title: Display a MIDI Track

text:
# Question
Title: Display a MIDI Track
### Background

MIDI files are quite different from WAV or MP3 audio files. MP3 and WAV files contain bytes representing a "recording" of the audio, while MIDI files have a series of MIDI messages stored in MIDI events informing a MIDI synthesizer which virtual instrument to play or a MIDI sequencer the playback tempo that should be used. These messages are stored in tracks, and a collection of tracks makes up a MIDI sequence, whose events can be analyzed by a sequencer and have its messages transmitted from the sequencer to a synthesizer's receiver.

Most of the time the MIDI messages stored in MIDI events are Note On messages which tell the synthesizer to play a particular note, or Note Off messages which tell the synthesizer to stop playing the note. These messages contain two data bytes, the first of which informs the synthesizer of the velocity of the note (higher velocity results in a louder note), and the second of which tells the synthesizer the note to play (i.e. Middle C). The events themselves also contain ticks which serve the purpose of telling the sequencer when to send the messages.

### The Challenge

The challenge is to write a full program or a function that analyzes a series of Note On and Note Off MIDI messages in a single-track MIDI sequence and outputs to STDOUT a chart showing when particular notes are on, when they are off, and the velocity of these notes. The vertical axis of the chart represents the note value and should be labeled as described below, and the horizontal axis represents time in MIDI ticks (though it should remain unlabeled to reduce complexity and spacing issues).

Your input may be four separate arrays or lists, each containing a series of integer values; a two-dimensional array or list containing four sub-arrays/sub-lists with a series of integer values; or any other convenient means; this represents the collection MIDI events with Note On and Note Off messages in the track. The values in the first of these arrays specifies the note, the second the velocity, the third the note on event tick, and the fourth the note off event tick. For instance, given four arrays such as these:

```
{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}

```

Analyzing the first element of each array gives two events: an event at tick 0 with a message that has a Note On command, note 60 (Middle C), and note velocity of 20; and an event at tick 2 with a message that has a Note Off command with the same note and velocity.

### Rules

The chart should feature the numbers 0 through 127 displayed in decreasing order on the left side (representing the note value), when the note starts, the duration of each note (Note Off tick minus Note On tick), and the note's velocity. The symbols representing the notes are dependent on their velocity:

* 0-15: `O`
* 16-31: `=`
* 32-47: `#`
* 48-63: `-`
* 64-79: `@`
* 80-95: `+`
* 96-111: `0`
* 112-127: `*`

You can assume the following:

* The values for note and velocity will be within the range \[0, 127\].
* The lengths of each of the four arrays will always equal each other.

Here are a few examples:

```
{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}

127|
126|
125|
...
67 |                00
66 |
65 |            ++
64 |        --
63 |
62 |    ##
61 |
60 |==
59 |
...
2  |
1  |
0  |

{60, 48, 62, 47, 64, 45,  65,  43, 67, 41, 65, 43, 64, 45,  62, 47, 60, 48}
{63, 31, 75, 90, 12, 23, 122, 104, 33, 19, 57, 42,  5, 82, 109, 86, 95, 71}
{0,   0,  2,  2,  4,  4,   6,   6,  8,  8, 10, 10, 12, 12,  14, 14, 16, 16}
{2,   2,  4,  4,  6,  6,   8,   8, 10, 10, 12, 12, 14, 14,  16, 16, 18, 18}

127|
126|
...
68 |
67 |        ##
66 |
65 |      **  --
64 |    OO      OO
63 |
62 |  @@          00
61 |
60 |--              ++
59 |
...
49 |
48 |==              @@
47 |  ++          ++
46 |
45 |    ==      ++
44 |
43 |      00  ##
42 |
41 |        ==
40 |
...
1  |
0  |

```

Here's an example that displays the first few notes of Ode to Joy:

```
{48, 55, 64, 64, 65, 67, 55, 67, 65, 64, 62, 52, 55,  60,  60,  62,  64,  55, 64, 62, 62}
{45, 45, 63, 63, 63, 63, 89, 66, 66, 66, 66, 30, 30, 103, 103, 103, 103, 127, 55, 55, 55}
{ 0,  0,  0,  4,  8, 12, 16, 16, 20, 24, 28, 32, 32,  32,  36,  40,  44,  48, 48, 54, 56}
{16, 16,  2,  6, 10, 14, 32, 18, 22, 26, 30, 48, 48,  34,  38,  42,  46,  64, 50, 55, 64}

127|
...
67 |            --  @@
66 |
65 |        --          @@
64 |--  --                  @@                  00  --
63 |
62 |                            @@          00            - --------
61 |
60 |                                00  00
59 |
58 |
57 |
56 |
55 |################++++++++++++++++================****************
54 |
53 |
52 |                                ================
51 |
50 |
49 |
48 |################
...
0  |

```

You can **reduce your score by 25%** if your submission takes an actual MIDI sequence as input, analyzes the Note On and Note Off messages of any track of your choosing provided it contains at least four events with Note On and Note Off messages, and outputs a chart as described above.

This is code golf, so shortest code wins. Good luck!

# Answer
# PHP, 127 + 571 = 698 total score\*

Okay, I'm claiming the bonus. :) This will take a standard MIDI file and display the output.

I've broken up the score above into the main challenge (analyze note on/off and display as chart) and the bonus challenge (read input from standard MIDI) to make scores more comparable.

## Main: 170 bytes - 25% = 127

For the main, the function `$d()` takes the required array and displays the ASCII output. Included are all tests and output of test MIDI file below.

```
$d=function($a){for($l=max($n=$a[0]);$l>=min($n);){$r=' |';foreach($n as$c=>$e)while($e==$l&$a[2][$c]<$a[3][$c])$r[++$a[2][$c]+1]='O=#-@+0*'[$a[1][$c]/16];echo$l--,$r,"
";}}

```

Try it online!

## Bonus: 761 bytes - 25% = 571

Function `$m()` will load a standard MIDI file (either locally or by URL) and return an array of tracks, each containing an array in the specified note format for all of the MIDI file tracks.

```
$m=function($f){$a=function($f){do$s=($s<<7)+(($c=unpack(C,fread($f,1))[1])&127);while($c&128);return$s;};$r=function($n){foreach($n as$e){if($e[4]==9&&$e[1]>0)foreach($n as$y=>$f)if($f[0]==$e[0]&&($f[4]==8||($f[4]==9&&$f[1]==0))){$o[0][]=$e[0];$o[1][]=$e[1];$o[2][]=$e[2];$o[3][]=$f[2];$n[$y][4]=0;break;}}return$o;};$m=fopen($f,r);while($b=fread($m,8)){$z=unpack(N2,$b)[2];if($b[3]==d){$k=unpack(n3,fread($m,$z))[3]/4;}else{$t=0;$n=[];$d=ftell($m)+$z;while(ftell($m)<$d){$t+=$a($m);if(($e=unpack(C,fread($m,1))[1])==255){fread($m,1);if($w=$a($m))fread($m,$w);}else{if($e>127)list(,$e,$h)=unpack('C*',fread($m,($y=(240&$e)>>4)==12?1:2));else$h=unpack(C,fread($m,1))[1];if($y==9|$y==8)$n[]=[$e,$h,(int)round($t/$k),0,$y];}}if($n)$u[]=$r($n);}}fclose($m);return$u;};

```

See it online! *Obviously TIO is sandboxed as to not allow remote requests or local files, so you'll have to run this code locally to see it in action. The first \[tests\]\[TIO-jrwa60tu\] in the display function includes the array result from the test MIDI file.*

### MIDI file load routine ungolfed:

```
$m=fopen($f,'r');                           // m = midi file handle
while($b=fread($m,8)){                      // read chunk header
    $z=unpack('N2',$b)[2];                  // z = current chunk size
    if($b[3]=='d'){                         // is a header chunk?
        $k=unpack('n3',fread($m,$z))[3]/4;  // k = ticks per quarter note (you can change the 4 to 8 or 16 to "zoom in" so each char represents eights or sixteenth notes)
    }else{                                  // is a track chunk?
        $t=0;                               // track/chunk time offset starts at 0
        $d=ftell($m)+$z;                    // d = end of chunk file pos
        while(ftell($m)<$d){                // q = current file pos
            $t+=$a($m);                     // decode var length for event offset and add to current time
            if(($e=unpack('C',fread($m,1))[1])==255){ // is a META event
                fread($m,1);                // read and discard meta event type
                if($w=$a($m))
                    fread($m,$w);
            }else{                          // is a MIDI event
                if($e>127) {                // is a new event type
                    list(,$e,$h)=unpack('C*',  // if is a prog change (0x0c), event is 1 byte
                        fread($m,($y=(240&$e)>>4)==12?1:2)); // otherwise read 2 bytes
                } else {                    // is a MIDI "streaming" event, same type as last
                    $h=unpack('C',fread($m,1))[1];
                }
                if($y==9|$y==8)             // if is a Note On or Note Off
                    $n[]=[$e,$h,(int)round($t/$k),0,$y];  // add note to output
            }
        }
        if($n)                              // if this track has notes,
            $u[]=$r($n);                    // add to array of output tracks ($u)
    }
}
fclose($m); // yes, could golf this out and rely on PHP GC to close it

```

A test MIDI file of "Ode to Joy" that can be used downloaded here. Example use:

```
$d( $m( 'beethoven_ode_to_joy.mid' )[0] );      // display first track

$d( $m( 'https://www.8notes.com/school/midi/piano/beethoven_ode_to_joy.mid' )[0] );

foreach( $m( 'multi_track_song.mid' ) as $t ) {  // display all tracks
    $d( $t );
}

```

**"Ode to Joy" MIDI file output**

```
67 |            0000++++                                                        00000000                                                                                00000000
66 |
65 |        0000        ++++                                                0000        0000                                                              @@              @@                                0000        ++++
64 |++++++++                ++++                0000000000          00000000                0000                0000                        @@@@        @@  ----        @@  ----                ++++++++++++                ++++                0000
63 |
62 |                            ++++        0000          00++++++++                            ++++        0000    000000          @@@@----        ----            @@@@        ----    ----                                    ++++        0000    000000
61 |
60 |++++                            ++++0000                        0000                            ++++0000              ++00000000            ----            ----                ----            00000000                        ++++0000    ****      ++00000000
59 |                                                        ++++++++
58 |                                                                                00000000
57 |                                                                                ----                            ++++++++
56 |                                                                                --------
55 |++++++++++++++++++++++++00000000000000000000000000000000++++++++00000000000000000000000000000000000000000000000000000000        ----------------------------------------                --------                                        0000    ++++++++00000000
54 |                                                                                ----
53 |                                                                                ++++++++
52 |                                0000000000000000                                                0000000000000000                                                                                ++++0000                00000000
51 |
50 |
49 |
48 |++++++++++++++++                0000000000000000                0000000000000000                0000000000000000        ++++++++                                                                                00000000

```

**Notes**

In MIDI format, Note On / Note Off events are atomic, meaning that you see a Note On event at a certain time for a given note (say E5), and it's implied that it will play until a Note Off event for another E5 note is seen. As such, it's necessary to analyze the MIDI events and match up a given Note On to it's Note Off, which the code for that is ~~297~~ 184 bytes. Further complicating this, it's fairly common in standard MIDI format to see a subsequent matching Note On with a velocity 0 representing the same thing as a Note Off.

This will now correctly read files that have zero-velocity Note On's instead of Note Off's, so should open most standard files.

**Caveats**

This is by no means a complete implementation of the MIDI format, however I have tested this with a fairly extensive collection of MIDI files and it reads them all nicely.

This submission has not been golfed to an extreme yet, so entirely likely this can be made smaller. I do think it's very unlikely that the 25% score reduction bonus would offset the code needed to read a standard MIDI file. As the (current) smallest submission that just does the ASCII display is ~~106~~ 65 bytes, it would require the MIDI file routines to be implemented in ~~25~~ 21 bytes to beat. I'd challenge anyone to do that (without using a language built-in or module). :)
> 6 votes

# Answer
# Ruby, 106 bytes

This was fun. I'm not sure why no one attempted it.

This function takes input as four array arguments and returns an array of strings, one for each line of the chart.

```
->a,*r{q=(0..z=127).map{|i|"%3d|"%(z-i)+" "*1e4}
a.zip(*r){|n,v,o,f|q[z-n][o+4]="O=#-@+0*"[v/16]*(f-o)}
q}

```

Attempt This Online!

The code above assumes no more than 10,000 ticks; the ATO link lowers that to 100 to avoid the output being truncated. You can change `1e4` to any number you want if you run it locally but you'll run out of memory eventually. You may want to pipe the output through `less` so you can scroll horizontally.
> 5 votes

# Answer
# Python 2, ~~163~~ ~~160~~ ~~156~~ 145 bytes

This is not the golfiest way to do it, but it was one of the simplest. If I could figure out how to replace parts of strings without turning them into lists, replacing, and turning them back into strings, that would be very helpful here. Golfing suggestions welcome.

**Edit:** 18 bytes thanks to Leaky Nun. Try it on Ideone!

```
a=input();z=[" "*max(a[3])]*128
for n,v,b,e in zip(*a):z[n]=z[n][:b]+"O=#-@+0*"[v/16]*(e-b)+z[n][e:]
for i in range(128)[::-1]:print"%3d|"%i+z[i]

```
> 2 votes

# Answer
# Japt, 65 bytes

```
®Æ"O=#-@+0*"gXzG
#€Çs ú3 +'|ÃúUmg2 rÔ+5
£VhXÎVgXv)hXÎ+4Xo pXra
Vw

```

Try it online!

Takes input as a list of notes in the format `[pitch, start_tick, end_tick, velocity]`. If taking input as separate lists is mandatory (i.e. one list containing all the pitches, one containing all the velocities etc.), that can be accomplished at the cost of 1 byte.

Explanation:

```
®Æ"O=#-@+0*"gXzG          #Gets the velocity character to use for each note
®                         # For each note in the input
 Æ                        # Replace the last item X with:
             XzG          #  Integer divide X by 16
  "O=#-@+0*"g             #  Get the character at that index in the string "O=#-@+0*"

#€Çs ú3 +'|ÃúUmg2 rÔ+5    #Generate the blank chart
#€Ç        Ã              # For each number X in the range [0...127]:
   s                      #  Turn X into a string
     ú3                   #  Right-pad with spaces until it is 3 characters long
        +'|               #  Add "|" to the end
            ú             # Right pad each of those with spaces to this length:
             Umg2         #  Get all the end_tick values
                  rÔ      #  Find the largest one
                    +5    #  Add 5

£VhXÎVgXv)hXÎ+4Xo pXra    #Put the notes into the chart
£                         # For each note:
     VgXv)                #  Get a line from the chart based on the note's pitch
          h               #  Overwrite part of that line:
           XÎ+4           #   Starting at index start_tick +4
               Xo         #   Overwrite characters with the velocity character
                  pXra    #   For the next end_tick - start_tick characters
 VhXÎ                     #  Put the modified line back into the chart

Vw                        #Print the chart
V                         # Get the chart
 w                        # Reverse it (so 127 is the first line)
                          # Implicitly print it

```
> 1 votes

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


title: Password Bishop Goodness

text:
# Question
Title: Password Bishop Goodness
*Derived from this, now deleted, post.*

Given a string, answer (truthy/falsy or two consistent values) if it constitutes a good Bishop password, which is when all the following conditions are met:

1. it has at least 10 characters
2. it has at least 3 digits (`[0-9]`)
3. it is not a palindrome (identical to itself when reversed)

You get 0 bytes bonus if your code is a good Bishop password.

**Warning:** Do *not* use Bishop goodness as a measure of actual password strength!

## Examples

### Good Bishop passwords

`PPCG123GCPP`
`PPCG123PPCG`
`PPCG123gcpp`
`0123456789`
`Tr0ub4dor&3`

### Not Good Bishop passwords

`PPCG123` (too short)
`correct horse battery staple` (not enough digits)
`PPCG121GCPP` (palindrome)
(too short and not enough digits)
`abc121cba` (too short and palindrome)
`aaaaaaaaaaaa` (palindrome and not enough digits)
`abc99cba` (everything wrong)

# Answer
# Python 2, ~~61~~ ~~59~~ ~~54~~ 51 bytes

```
lambda s:sum(map(str.isdigit,s))>2<s[:9]<s<>s[::-1]

```

Try it online!

-5 bytes, thanks to Erik the Outgolfer
-3 bytes, thanks to xnor
> 5 votes

# Answer
# Japt, ~~17~~ 14 bytes

```
Ê¨A&U¦Ô&3§Uè\d

```

*-3 bytes rearranged by @Shaggy*

Try it online!

---

# Japt, 15 bytes (0 Bytes Bonus :v)

```
Ê¨10&U¦Ô&3§Uè\d

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 12 bytes

```
gT@Iþg3@IÂÊP

```

Try it online or verify all test cases.

**Explanation:**

```
g      # Get the length of the (implicit) input
 T@    # Check if this length >= 10
Iþ     # Get the input and only leave the digits
  g    # Then get the length (amount of digits)
   3@  # And check if the amount of digits >= 3
IÂ     # Get the input and the input reversed
  Ê    # Check if they are not equal (so not a palindrome)
P      # Check if all three above are truthy (and output implicitly)

```
> 4 votes

# Answer
# , ~~80~~ ~~70~~ ~~62~~ ~~64~~ 63 bytes

```
any(rev(U<-utf8ToInt(scan(,'')))<U)&sum(U>47&U<58)>2&sum(U|1)>9

```

Try it online!

From digEmAll, and some rearranging too

```
sum((s<-el(strsplit(scan(,''),"")))%in%0:9)>2&!all(s==rev(s))&s[10]>''

```

Try it online!

Pretty straightforward, no real amazing tricks here. After user inputs string:

* Separates and searches the string for more than 2 numbers. (3 or more digits)
* Checks if not all elements are equal to the reversed version of the string (palindrome)
* Checks that length is greater than 9 (10 or more characters)
> 4 votes

# Answer
# Brachylog, ~~18~~ 12 bytes

*Thanks for the tips, Kroppeb and Fatalize!*

```
¬↔?l>9&ịˢl>2

```

Try it online!

### Explanation

The program is a single predicate, composed of two parts that are chained with `&`.

First:

```
¬       The following assertion must fail:
 ↔        The input reversed
  ?       can be unified with the input
        Also, the input's
   l    length
    >9  must be greater than 9

```

Second:

```
 ˢ     Get all outputs from applying the following to each character in the input:
ị        Convert to number
       This gives an integer for a digit character and fails for a non-digit, so
       we now have a list containing one integer for each digit in the password
  l    Its length
   >2  must be greater than 2

```
> 3 votes

# Answer
# APL+WIN, ~~36, 30~~ 29 bytes

7 bytes saved thank to Adám

Index origin = 0

Prompts for input string

```
(10≤⍴v)×(3≤+/v∊∊⍕¨⍳10)>v≡⌽v←⎕

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
(10≤⍴v) Length test pass 1 fail 0

(3≤+/v∊∊⍕¨⍳10) Number of digits test

>v≡⌽v Palindrome test

```

The code also qualifies for the bonus as it is a good Bishop password.
> 3 votes

# Answer
# Jelly, 12 bytes

```
~Tṫ3ȧL9<Ɗ>ṚƑ

```

Try it online!

`[]` if not enough digits (empty list, falsy), `0` if otherwise bad (zero, falsy), `1` if good (nonzero, truthy).
> 2 votes

# Answer
# Java 8, 92 bytes

```
s->s.length()>9&s.replaceAll("\\D","").length()>2&!s.contains(new StringBuffer(s).reverse())

```

Try it online.

**Explanation:**

```
s->                        // Method with String parameter and boolean return-type
  s.length()>9             //  Check if the length of the input-String is more than 9
  &s.replaceAll("\\D","")  //  AND: remove all non-digits from the input-String
    .length()>2            //       and check if the amount of digits is more than 2
  &!s.contains(new StringBuffer(s).reverse())
                           //  AND: check if the input-String does NOT have the reversed
                           //       input-String as substring (and thus is not a palindrome)

```
> 2 votes

# Answer
# JavaScript, ~~60~~ ~~56~~ 46 bytes

Takes input as an array of characters. Outputs `1` for truthy and `0` for falsey.

```
s=>/(\d.*){3}/.test(s[9]&&s)&s+``!=s.reverse()

```

Try It Online!

Saved 10 bytes(!) thanks to Arnauld.
> 2 votes

# Answer
# Racket, 122 bytes

```
(define(d s)(let([t(string->list s)])(and(< 2(length(filter char-numeric? t)))(< 9(length t))(not(equal? t(reverse t))))))

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), 25 bytesSBCS

```
{∧/(9<≢⍵)(3≤+/⍵∊⎕D),⍵≢⌽⍵}

```

Try it online!
> 2 votes

# Answer
# Perl 6, 32 bytes

```
{$_ ne.flip&&m:g/\d/>2&&.comb>9}

```

Try it online!

Anonymous code block that simply enforces that all the rules are complied with.

### Explanation:

```
{          &&         &&       }  # Anonymous code block
 $_ ne.flip                       # Input is not equal to its reverse
             m:g/\d/>2            # There are more than two digits
                        .comb>9   # There are more than 9 characters

```
> 1 votes

# Answer
# Red, ~~117~~ 111 bytes

```
func[s][d: charset"0123456789"n: 0 parse s[any[d(n: n + 1)|
skip]]all[n > 2 9 < length? s s <> reverse copy s]]

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-p`, 33 bytes

```
$_=/.{10}/&y/0-9//>2&reverse ne$_

```

TIO
> 1 votes

# Answer
# K (oK), ~~31~~ 28 bytes

-3 bytes thanks to ngn!

```
{(x~|x)<(2<#x^x^/$!10)*9<#x}

```

Try it online!
> 1 votes

# Answer
# Clean, 66 bytes

```
import StdEnv
$s=s<>reverse s&&s%(0,8)<s&&sum[1\\c<-s|isDigit c]>2

```

Try it online!

* `s<>reverse s`: `s` is not a palindrome
* `s%%(0,8)<s`: the first 9 characters of `s` are less than all of `s`
* `sum[1\\c<-s|isDigit c]>2`: `s` has more than two digits
> 1 votes

# Answer
# Retina 0.8.2, 40 bytes

```
G`.{10}
G`(\d.*){3}
+`^(.)(.*)\1$
$2
^..

```

Try it online! Link includes test cases. Explanation:

```
G`.{10}

```

Checks for at least 10 characters.

```
G`(\d.*){3}

```

Checks for at least 3 digits.

```
+`^(.)(.*)\1$
$2

```

Remove the first and last character if they match.

```
^..

```

If there are at least 2 characters then it wasn't a palindrome.

.NET's balancing groups mean that this can be done in a single regular expression, but that takes 47 bytes:

```
^(?!(.)*.?(?<-1>\1)*$(?(1).))(?=.{10})(.*\d){3}

```

Try it online! Link includes test cases.
> 1 votes

# Answer
# Python 3, ~~74~~ ~~72~~ 64 bytes

Thanks Neil A. for -2 bytes!
Thanks Jo King for -8 bytes!

```
lambda s:s[9:]and re.findall('\d',s)[2:]and s[::-1]!=s
import re

```

Explanation:

```
lambda s: # Create lambda
           s[9:] # Check if the string is at least 10 characters long
                     and re.findall('\d',s)[2:] #Check for at least 3 matches of the regex \d (which matches all digits)
                     and s[::-1] != s # Check if the string reversed is equal to the string (palindrome test)
import re  # Import regex module

```

Try it online!
> 1 votes

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

```
a=>a.length>9&(a.match(/\d/g)||[]).length>2&a!=[...a].reverse().join``

```

Try it online!

Returns 1 for true and 0 for false
> 0 votes

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

```
n=>n.Count(char.IsDigit)>2&!n.Reverse().SequenceEqual(n)&n.Length>9

```

Try it online!
> 0 votes

# Answer
# Pip, 19 bytes

```
#a>9&XD Na>2&aNERVa

```

Try it online! (all test cases)

### Explanation

With `a` being the first command-line argument:

```
#a > 9      Length of a is greater than 9
&           and
XD N a > 2  Number of matches of regex [0-9] iN a is greater than 2
&           and
a NE RV a   a is not (string-)equal to reverse of a

```
> 0 votes

# Answer
# Stax, 14 bytes

```
ûc╖»¬ë⌂╓âó╗cCé

```

Run and debug it
> 0 votes

# Answer
# Pyth, 17 bytes

```
&&<2l@`MTQ<9lQ!_I

```

Try it online here, or verify all the test cases at once here.

```
&&<2l@`MTQ<9lQ!_IQ   Implicit: Q=eval(input()), T=10
                     Trailing Q inferred
      `MT            [0-10), as strings
     @   Q           Take characters from input which are in the above
    l                Length
  <2                 Is the above greater than 2?
            lQ       Length of Q
          <9         Is the above greater than 9?
               _IQ   Is Q unchanged after reversal?
              !      Logical NOT
&&                   Logical AND the three results together

```
> 0 votes

# Answer
# Groovy, (47 bytes)

```
{p->p=~/.{10}/&&p=~/(\d.*){3}/&&p!=p.reverse()}

```

(Bonus inclusion is left as an exercise to the reader)
> 0 votes

---
Tags: code-golf, string, decision-problem, palindrome
---


title: Meta-bowling Golf

text:
# Question
Title: Meta-bowling Golf
Your task is to create the shortest program (A) that outputs another program (B) with the most unique bytes, which in turn outputs the original program (A). Essentially, you are golfing one half of a pair of ouroboros programs (a.k.a. periodic iterating quine) and bowling the other half. A and B may be in different languages.

## Rules and Scoring

Your final score is `<number of unique bytes in B> / <number of bytes in A>`. Highest score wins. It should be noted that the theoretical maximum score is 256.

* Program A must be at least one byte long
* Program B cannot consist entirely of no-ops, i.e. at least one character must affect the output in some way.
* Standard rules of quines apply to both programs. Notably, error quines are not allowed in either case.

For the sake of answer format consistency, begin your answer with something like this:

```
# <Language for A> & <Language for B>, Score: <B score> / <A score> = <combined score>

```

# Answer
# Japt & Japt, Score: 255 / 38 = 6.71

Program A:

```
"iQ ²¯24
G²õ@i'#+Xd"iQ ²¯24
G²õ@i'#+Xd
```

Program B is over 8kB long, so long that the link breaks, so I won't paste the whole thing. Here's a sample:

```
#þ"iQ ²¯24
G²õ@i'#+Xd"iQ ²,#ÿ"iQ ²¯24
G²õ@i'#+Xd"iQ ²,#Ā"iQ ²¯24
G²õ@i'#+Xd"iQ ²
```

I couldn't find a way to get a `NUL` byte to work, which is why program B only has 255 unique characters. Program B essentially consists of 255 copies of a single program, where a single irrelevant byte is changed each time, and the first 254 executions are ignored.

For the explanation, I'll start with this simplified version of A so that the resulting B is easier to discuss.

```
"iQ ²¯23
3õ@i'#+Xd"iQ ²¯23
3õ@i'#+Xd
```

This program is based on the basic payload-capable Japt quine. The string at the start contains a duplicate of the rest of the program, `iQ ²` inserts a quote and duplicates to create a string representation of the entire program, and then `¯23` trims off itself and everything after it. The resulting string is a program that outputs Program A:

```
"iQ ²¯23
3õ@i'#+Xd"iQ ²
```

I will refer to this string as `U`.

The last line of A duplicates `U` a bunch of times with a small change each time. Specifically, for each number `X` in the range `[1...3]` it outputs `"#c" + U` where `c` is the character with charcode `X`. The default behavior of Japt is to output those strings with no quotation marks and separated by commas, so this is the output of our Simplified A (note that there's an unprintable byte between each `#` and `"iQ`:

```
#"iQ ²¯23
3õ@i'#+Xd"iQ ²,#"iQ ²¯23
3õ@i'#+Xd"iQ ²,#"iQ ²¯23
3õ@i'#+Xd"iQ ²
```

We'll call this Simplified B.

Simplified B has a simple structure, alternating between `#c` and `U`. Fortunately for this answer, each `#c` and `U` is treated as separated by a comma, and in this situation the behavior of that is everything except the very last `U` has no effect on the output. The only portion of Simplified B which affects the output is this:

```
"iQ ²¯23
3õ@i'#+Xd"iQ ²
```

Which is identical to `U` that we already know outputs Simplified A.

The only difference between Simplified A and Program A is that instead of generating copies for the range `[1...3]` the real program generates copies for the range `[1...256]`. That results in 256 versions of `#c` each of which has a different character, though the last version "Ā" is a multi-byte character so it doesn't add any unique bytes, but everything except the last `U` is still ignored.
> 14 votes

# Answer
# Program A, Gol\>\<\>, 256/20 bytes = 12.8

```
"44XFL|r2ssl3%Q4s]|H

```

Try it online!

# Program B, Gol\>\<\>

```
"44XFL|r2ssl3%Q4s]|H

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ

```

Try it online!

The program alternates between outputting itself followed by every byte and just outputting itself.

### Explanation:

```
"            Wrapping string literal pushes the first line to the stack backwards
 44X         Push 256
    FL|      Push the range from 0 to 255
       r                  Reverse the stack
        2ss               Push a quote
           l3%            If the stack length is divisible by 3
              Q4s]|       Only take the top 20 characters
                   H      And output the stack

```
> 5 votes

# Answer
# Program A: 05AB1E, score: ~~256/41~~ 256/31 bytes = 8.258...

```
0"D34çý₅Ýç'q†22ǝ"D34çý₅Ýç'q†22ǝ

```

Try it online.

# Program B: 05AB1E

```
0"D34çý₅Ýç'q†22ǝ"D34çýq

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnoprstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿÝç'q†22ǝ

```

Try it online.

**Explanation:**

The shortest for 05AB1E is this one: `0"D34çý"D34çý` (**14 bytes**) provided by *@OliverNi*. My answer uses a modified version of that quine by adding `₅Ýç'q†vy27ǝD}J`.

```
0            # Push a 0 to the stack
             #  STACK: [0]
 "D34çý₅Ýç'q†vDy27ǝ}J"
             # Push the string "D34çý₅Ýç'q†vDy27ǝ}J" to the stack
             #  STACK: [0,"D34çý₅Ýç'q†vDy27ǝ}J"]
  D          # Duplicate the string
             #  STACK: [0,"D34çý₅Ýç'q†vDy27ǝ}J","D34çý₅Ýç'q†vDy27ǝ}J"]
   34çý      # Join the stack by '"'
             #  STACK: ['0"D34çý₅Ýç'q†vDy27ǝ}J"D34çý₅Ýç'q†vy27ǝD}J']
₅Ý           # Push a list in the range [0,255]
  ç          # Convert each integer to an ASCII character
   'q†      '# Filter the "q" to the front
      22ǝ    # Insert it at index 22 in the string (replacing the second '₅')
             # (and output the result implicitly)

```

Program B will terminate as soon as it reaches the `q`, so the actual program B is:

```
0"D34çý₅Ýç'q†22ǝ"D34çýq

```

Everything after that is ignored, and the top of the stack (`0"D34çý₅Ýç'q†22ǝ"D34çý₅Ýç'q†22ǝ`) is output implicitly.
> 1 votes

---
Tags: code-golf, code-challenge, quine, code-bowling
---


# Question
Title: Mask an IP address and give its broadcast
## Background

Inspired by this Unix.SE question (and of course my own answer).

When an IP address is specified for an interface, it is often given in this dotted-decimal form:

```
a.b.c.d e.f.g.h

```

where `a.b.c.d` is the actual address and `e.f.g.h` is the netmask.

The netmask, when represented in binary, is basically a bunch of `1` bits followed by a bunch of `0` bits. When the netmask is bitwise ANDed against the given IP address, result will be the *network* portion of the address, or simply the *network address*. This will be programmed into the host's route table so that the host knows to send anything destined for this network out this interface.

The broadcast address for a network is derived by taking the network address (from above) and setting all the host-bits to 1. The broadcast address is used to send to *all* addresses within the given network.

## Challenge

Given a dotted-decimal IP address and valid netmask as input, provide the network address and broadcast address as output, also in dotted-decimal format.

* Input must be address and mask as two strings in dotted-decimal format. You may pass this as 2 separate strings, as list or array of 2 string elements or a single string with the address and mask separated by some sensible separator.
* Output format is subject to the same constraints as input format.

## Examples

```
Input                              Output

192.168.0.1 255.255.255.0          192.168.0.0 192.168.0.255
192.168.0.0 255.255.255.0          192.168.0.0 192.168.0.255
192.168.0.255 255.255.255.0        192.168.0.0 192.168.0.255
100.200.100.200 255.255.255.255    100.200.100.200 100.200.100.200
1.2.3.4 0.0.0.0                    0.0.0.0 255.255.255.255
10.25.30.40 255.252.0.0            10.24.0.0 10.27.255.255

```

# Answer
> 5 votes
# JavaScript (ES6), 92 bytes

```
(a,m)=>a.split`.`.map((n,i)=>(v=m[i],m[i]=n&v|v^255,n&v),m=m.split`.`).join`.`+" "+m.join`.`

```

## Explanation

```
(a,m)=>
  a.split`.`
  .map((n,i)=>(
      v=m[i],
      m[i]=n&v|v^255,
      n&v
    ),
    m=m.split`.`
  ).join`.`
  +" "+m.join`.`

```

## Test

```
var solution = (a,m)=>a.split`.`.map((n,i)=>(v=m[i],m[i]=n&v|v^255,n&v),m=m.split`.`).join`.`+" "+m.join`.`
```

```
<input type="text" id="input" value="10.25.30.40 255.252.0.0" />
<button onclick="result.textContent=solution.apply(null,input.value.split` `)">Go</button>
<pre id="result"></pre>
```

# Answer
> 4 votes
# MATL, 47 bytes

This answer uses current version (4.0.0) of the language.

```
'%i.%i.%i.%i't32whh2:"j'\d+'XXU]tbZ&tb255Z~+hYD

```

### Example

```
>> matl
 > '%i.%i.%i.%i't32whh2:"j'\d+'XXU]tbZ&tb255Z~+hYD
 >
> 192.168.0.1
> 255.255.255.0
192.168.0.0 192.168.0.255

```

### Explanation

```
'%i.%i.%i.%i't32whh      % format string: '%i.%i.%i.%i %i.%i.%i.%i'
2:"                      % for loop: do this twice
    j'\d+'XXU            % input string and parse into 4-vector with the numbers
]                        % end
tbZ&                     % compute network address
tb255Z~+                 % compute broadcast address
hYD                      % concatenate into 8-vector and apply format string

```

# Answer
> 4 votes
# Pyth, ~~44~~ 42 bytes

```
LisMcb\.256Lj\..[04jb256'J.&yzKyw'+JxKt^2 32

```

Try it online. Test suite.

Expects the input as an array, like `["10.25.30.40", "255.252.0.0"]`.

# Answer
> 0 votes
# PHP, 126 bytes

With input in $n:

```
preg_filter(~Ð×£ÔÖÐ,~Û¤¢Â×ÛÎÖÑ×ÛÔÔÁÌÀ×ÛÑÂ×ÛÂÛÁÊÀÝÑÝÅÝÝÖÑ×Û¤ÛÒÊ¢ÙÛÎÖÖÑ×ÛÑÂÛÑ×Û¤ÛÒÊ¢ÍÊÊÙÛÎÖÖÅÝÝÖ,$n);echo"$c $b";

```

Hexdump:

```
0000000: 7072 6567 5f66 696c 7465 7228 7ed0 d7a3  preg_filter(~...
0000010: 9bd4 d6d0 9a2c 7edb 9ea4 a2c2 d7db ced6  .....,~.........
0000020: d1d7 db96 d4d4 c1cc c0d7 db9c d1c2 d7db  ................
0000030: 8bc2 db96 c1ca c0dd d1dd c5dd ddd6 d1d7  ................
0000040: db9e a4db 96d2 caa2 d9db ced6 d6d1 d7db  ................
0000050: 9dd1 c2db 8bd1 d7db 9ea4 db96 d2ca a283  ................
0000060: cdca cad9 81db ced6 d6c5 dddd d62c 246e  .............,$n
0000070: 293b 6563 686f 2224 6320 2462 223b       );echo"$c $b";

```

And a more readable version:

```
preg_filter( /* PCRE regex on input */
    '/(\d+)/e', /* match all digits, execute the code for each one */
    '$a[]=($1) /* push the matched value to the array $a */
        .($i++>3 /* if we're at the 5th or higher digit */
            ?($c.=($t=$i>5?".":"").($a[$i-5]&$1)) /* append to $c bitwise AND-ed number */
                .($b.=$t.($a[$i-5]|255&~$1)) /* append to $b the broadcast address */
            :"")',
    $n);
echo"$c $b"; /* output $c and $b */

```

`preg_filter` requires a single statement in the replacement pattern when using the `e` flag, so I 'append' the result of the calculations to the 5th and higher values of $a, because those are never reused.

# Answer
> 0 votes
# Perl, ~~90~~ 85 bytes

*includes +6 for `-pF/\D/`*

```
for(0..3){push@a,$F[$_]&1*($y=$F[$_+4]);push@b,$F[$_]|~$y&255}$"='.';$_="@a @b"

```

Usage:

```
echo "192.168.0.1 255.255.255.0" | perl -pF/\\D/ file.pl

```

More readable:

```
for(0..3) {
    push @a, $F[$_] & 1*($y=$F[$_+4]);  # calc/add network address 'byte'
    push @b, $F[$_] | ~$y & 255         # calc/add broadcast address 'byte'
}
$"='.';                                 # set $LIST_SEPARATOR
$_="@a @b"                              # set output to network address and broadcast

```

The `-F/\D/` splits the input on non-digits and stores it in `@F`.

# Answer
> 0 votes
# Factor, 103 bytes

```
[ [ ipv4-aton ] bi@ 2dup bitand -rot dup bit-count 32 - abs on-bits pick bitor 2nip [ ipv4-ntoa ] bi@ ]

```

Nice.

Ungolfed:

```
: mask-and-broadcast ( ip mask -- netaddr broadcast )
  [ ipv4-aton ] bi@ 2dup bitand -rot dup bit-count 32 - abs on-bits pick bitor 2nip
  [ ipv4-ntoa ] bi@ ;

```

# Answer
> 0 votes
# PHP, 74 bytes

```
<?=long2ip($i=ip2long($argv[1])&$m=ip2long($argv[2])),' ',long2ip($i|~$m);

```

As a standalone, input is via command line:

```
$ php ip.php 192.168.0.1 255.255.255.0
192.168.0.0 192.168.0.255

```

Try it online!

Or as a function, **80 bytes**:

```
function($a,$b){return[long2ip($i=ip2long($a)&$m=ip2long($b)),long2ip($i|~$m)];}

```

Try it online!

***Ungolfed***

```
function ip( $a, $b ) {
    $i = ip2long( $a );          // string IP to 32 bit int
    $m = ip2long( $b );          // string netmask to 32 bit int
    $n = $i & $m;                // network is bitwise AND of IP and netmask
    $c = $i | ~$m;               // broadcast is bitwise OR of IP and inverse netmask
    return [ long2ip( $n ), long2ip( $c ) ];
}

```

PHP has nice (albeit with long function names) built-ins to handle IPv4 dotted-string to binary and back.

***Output***

```
192.168.0.1 255.255.255.0   => 192.168.0.0 192.168.0.255
192.168.0.0 255.255.255.0   => 192.168.0.0 192.168.0.255
192.168.0.255 255.255.255.0 => 192.168.0.0 192.168.0.255
100.200.100.200 255.255.255.255 => 100.200.100.200 100.200.100.200
1.2.3.4 0.0.0.0 => 0.0.0.0 255.255.255.255
10.25.30.40 255.252.0.0 => 10.24.0.0 10.27.255.255

```

---
Tags: code-golf, bitwise, networking
---


title: Generate Ulam Numbers

text:
# Question
Title: Generate Ulam Numbers
Given an integer `n` (where `n < 10001`) as input, write a program that will output the first `n` Ulam numbers. An Ulam number is defined as follows:

1. U1 = `1`, U2 = `2`.
2. For `n > 2`, Un is the smallest integer which is greater than Un-1 that is the sum of two **distinct** earlier terms in exactly one way.

For example, U3 is `3` (2+1), U4 is `4` (3+1) (note that (2+2) does not count as the terms are not distinct), and U5 is `6`, (U5 is not 5 because 5 can be represented as either 2+3 or 4+1). Here are the first few Ulam numbers:

> `1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99`

This is code golf, so the shortest entry wins.

# Answer
# CJam, ~~47~~ ~~41~~ 37 bytes

```
li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`

```

Try it online.

### Example run

```
$ cjam <(echo 'li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`') <<< 26
[1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99]

```

### How it works

This basic idea is the following:

1. Start with the array `A := [ 0 U₁ U₂ ... Uₖ ]`.
2. Compute `S`, the array of all sums `x + y` such that `x,y ∊ A` and `x < y`.
3. Discard all non-unique sums from `S`. Since every Ulam number greater than 2 is both the sum of two smaller ones and the sum of zero and itself, this discards the Ulam numbers `U₃, U₄, ... Uₖ`.
4. The remaining array is `[ U₁ U₂ Uₖ₊₁ ... ]`, so the next Ulam number is the third smallest element. Append it to `A` and go back to step 1.

```
li                                    " Read one integer (I) from STDIN.                  ";
  4,                                  " Push the array A = [ 0 1 2 3 ].                   ";
    1${                        }*     " Do the following I times:                         ";
       __m*                           " Push the Cartesian product A × A.                 ";
           {       }%                 " For each pair (x,y) in A × A:                     ";
            _~<\:+*                   " Compute (x + y) * (x < y).                        ";
                     $2               " Sort the resulting array.                         ";
                       /              " Split it into chunks of length 2.                 ";
                        z             " Transpose the resulting two-dimensional array.    ";
                         :^           " Compute the symmetric difference of its rows.     ";
                           $          " Sort the resulting array.                         ";
                            2=        " Extract its third element.                        ";
                              +       " Push it on the array A.                           ";
                                 1>   " Discard the first element of A (0).               ";
                                   <  " Discard all but the first I elements of A.        ";
                                    ` " Push a string representation of A.                ";

```
> 10 votes

# Answer
# J - 46 char

Function taking `n` as argument.

```
_2}.(,]<./@-.~</~({.+_*1<#)/.~@#&,+/~)@[&0&1 2

```

Explained by explosion:

```
    (                                )          NB. procedure for a list:
                                  +/~           NB.   take an addition table
              </~              #&,              NB.   select the top right half (no diag)
                 (        )/.~@                 NB.   for each unique value:
                       1<#                      NB.     if more than one present
                  {.+_*                         NB.     add infinity to it
      ]    -.~                                  NB.   remove existing Ulam numbers
       <./@                                     NB.   take the smallest
     ,                                          NB.   append to Ulam numbers
                                      @[&0      NB. repeat this procedure:
                                          &1 2  NB.   n times starting with [1, 2]
_2}.                                            NB. drop the last two numbers

```
> 6 votes

# Answer
## T-SQL, ~~301~~ ~~300~~ ~~288~~ 287

I've committed a little light SQL abuse.

```
DECLARE @N INT=100,@T INT=1DECLARE @ TABLE(I INT,U INT)INSERT @ VALUES(1,1),(2,2)#:IF @T>2INSERT @ SELECT TOP 1@T,A.U+B.U FROM @ A,@ B WHERE A.U>B.U GROUP BY A.U+B.U HAVING COUNT(*)=1AND A.U+B.U>ALL(SELECT U FROM @)ORDER BY 2SET @T+=1IF @T<=@N GOTO # SELECT U FROM @ WHERE I<=@N ORDER BY I

```

Try it in SQL Server 2008 here.

@N holds the input integer. Change the example "100" to what n should be. "10000" will probably finish eventually, but I haven't let that run to completion. This entry's char count is for a one-digit input. Output is in query result form.
> 6 votes

# Answer
# Haskell, ~~70~~ 67 characters

```
u n=take n$1:2:[x|x<-[1..],[_]<-[[y|y<-u$n-1,z<-u$n-1,y<z,y+z==x]]]

```

usage:

```
>u 6
[1,2,3,4,6,8]

```
> 5 votes

# Answer
## JavaScript ES6, ~~100 ... 93~~ 90 characters

Run this in Web Console or Scratchpad of latest Firefox (Nightly or release).

**EDIT 8** Golfed a lot!!! and made it down to ~~94 characters~~ ~~93~~ 90 characters (thanks to @openorclose). (My first sub 100)

Here is my version which is much faster ~~but is 3 characters longer (107 characters)~~ ~~and is exactly the same amount of characters as above~~ and is much smaller than the brute force method below!, (thanks to edc65 ) :

```
u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)r.map(j=>c-=j<i/2&s[i-j])})([])||r

```

I will keep trying to golf it further. But we are squeezing it out of the scope of JS :P

Here are some numbers when I run this inside a script tag in a webpage:

```
n           time (s)
10            0.001
100           0.005
1000          2.021
10000       236.983
100000      ~~pending~~ tldr; Too long didn't run :P

```

---

This is my first submission which is heavily inspired by @rink.attendant.6's answer in JavaScript.

```
u=n=>{for(l=[1,g=2],i=3;g<n;++i){z=1;for(j of l)for(k of l)z-=j<k&j+k==i;!z?l[g++]=i:0}return n>1?l:[1]}

```

I know this can be golfed even further. I will post a non-bruteforced solution too, which might be even shorter.

**EDIT 1**: Golfed a bit more and fixed for n = 1

I must say that I do envy Haskell and J for such super handy shortcuts for every kind of requirement -\_-
> 5 votes

# Answer
## Perl - 71 bytes

```
#!perl -p
@a=$b[2]=1;1while$b[++$a]^1||$_>map(++$b[$_+$a],@a)&&push@a,$a;$_="@a"

```

Try it online!

Counting the shebang as one.
Using a second array to store the sums seems to be significantly faster than a hash. Memory usage is also less, which I wouldn't have expected.

Sample usage:

```
$ echo 30 | perl ulam.pl

```

Sample output:

```
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126

```

Approximate runtimes:

```
n = 100     0.015s
n = 1000    0.062s
n = 10000   4.828s

```
> 5 votes

# Answer
## GolfScript (41 37 bytes)

```
~.14*,3,\{1$.{2$1$-.@<*}%&,2=*|}/0-<`

```

Online demo

Cartesian products in GolfScript are quite long, so this takes a different approach. The long-term growth of the Ulam numbers is that the `n`th Ulam number is about `13.5n`, but in the first 10000 terms the greatest ratio between the `n`th Ulam number and `n` is just under `13.3`. So given `n` we can filter the first `14n` numbers to find those which belong in the sequence.

With thanks to Dennis for 41-\>37.
> 5 votes

# Answer
## Java, 259

```
import java.util.*;class C{public static void main(String[]a){List<Integer>l=new ArrayList<>();l.add(1);l.add(2);for(int i=3,z=0;l.size()<new Long(a[0]);i++,z=0){for(int j:l){for(int k:l){if(j<k&j+k==i)z++;}}if(z==1)l.add(i);}l.forEach(System.out::println);}}

```

Brute force works well for this.

```
import java.util.*;
class C {
    public static void main(String[] a) {
        List<Integer>l = new ArrayList<>();
        l.add(1);
        l.add(2);
        for (int i = 3, z = 0; l.size() < new Long(a[0]); i++, z = 0) {
            for (int j : l) {
                for (int k : l) {
                    if (j < k & j + k == i)
                        z++;
                }
            }
            if (z == 1)
                l.add(i);
        }
        l.forEach(System.out::println);
    }
}

```
> 4 votes

# Answer
# APL (Dyalog Extended), ~~36~~ 35 bytes

*-1 byte by Adám*

```
{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}

```

Try it online!

```
{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}      Monadic function taking an argument n:

{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}   Helper function to compute the next Ulam number
                                    given ⍵ (the first few Ulam numbers)
                        +⍀⍨⍵      Make an addition table from ⍵.
                       ,          Flatten into a list.
                   ⍵~⍨            Remove all entries already in ⍵.

     (∊⊢⊆⍨2 3∊⍨⍧⍨)               Helper function taking an argument x:
                ⍧⍨                  The count of elts of x in itself
           2 3∊⍨                    1s where those counts are in (2 3), else 0s.*
       ⊢⊆⍨                          Partition x, removing values corresponding to 0s.
      ∊                             Join the partitions into a single list.

    (∊⊢⊆⍨⍧⍨∊2 3⍨)                Keep all elements that occur exactly 2 or 3 times.
                                  (i.e. that occur once as a
                                  sum of distinct elements of ⍵).
    ∧                         Sort ascending.
   ⊃                          Take the first value (the next Ulam #).
 ⍵,                           Append that value to ⍵.

{⍵↑{...}⍣⍵⍳2}
{  {...}⍣⍵  }                 Call the helper function n times
           ⍳2                 starting with (1 2). First n+2 Ulam numbers.
 ⍵↑                           Keep the first n elements.

```

When we make the addition table, diagonal elements are twice the entries in ⍵. Non-diagonal elements are sums of distinct elements, with each \\$x\\$ occurring twice for each way \\$x\\$ can be written as a sum of distinct elements. Therefore, each number \\$x\\$ occurs \\$2a+b\\$ times, where \\$a\\$ is the number of ways \\$x\\$ can be written as a sum of distinct elements from ⍵, and \\$b\\$ is 1 iff \\$x\\$ is twice some entry in ⍵. We want \\$a=1\\$, so it is sufficient to check \\$2a+b \in \\{ 2, 3\\}\\$.

* (In ngn/APL, a constant can end a train without using . But ngn/APL doesn't have count-in, so we need ⍨ somewhere.)
> 4 votes

# Answer
# PHP 5.4+, 164

Same approach as my answers:

```
<?function u($n){for($l=[1,2],$i=3;count($l)<$n;++$i){$z=0;foreach($l as $j){foreach($l as $k){$z+=$j<$k&$j+$k==$i;}}if($z==1)$l[]=$i;}return array_slice($l,0,$n);}

```
> 3 votes

# Answer
# Jelly, 20 bytes

```
Œc§ḟµḟœ-Q$Ṃɓ;
2RÇ⁸¡ḣ

```

Try it online!

```
Œc§ḟµḟœ-Q$Ṃɓ;    Helper link that appends the next number to x, a list of Ulam numbers:
Œc                  All unordered pairs of x
  §                 Sum each pair
   ḟ                Filter out the numbers already present in x.
    µ               Let this list be y. Then apply the following chain:

     œ-Q$Ṃ          Find the minimum of all unique elements.
     ḟ                Take y and filter out the elements in
      œ-Q$            the multiset difference between y and its unique elements.
          Ṃ           Then find the Ṃinimum of the result.

           ɓ;    Append (ɓ reverses argument order) the result to

2RÇ⁸¡ḣ           Main link:
2R               Start with [1,2].
  Ç⁸¡            Apply the helper link (Ç) n (⁸) times to generate n+2 Ulam #s.
     ḣ           Keep the first n values.

```
> 3 votes

# Answer
## JavaScript, ~~147~~ ~~154~~ 150 (136)

Heavily inspired by @Ypnypn's brute-force Java solution posted earlier:

```
function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;l.forEach(function(j){l.forEach(function(k){z+=j<k&j+k==i})});if(z==1)l.push(i)}return l.slice(0,n)}

```

Thanks for @Dennis for shaving 4 to 18 bytes off my original version

### Dangerous version (using `for..in` loops)

I would not recommend running this because looping through an object that is an `instanceof` `Array` using a `for..in` loop could cause your machine to burst into flames and/or transform into an angry killing machine, but here it is:

```
function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;for(j in l)for(k in l)z+=l[j]<l[k]&l[j]+l[k]==i;if(z==1)l.push(i)}return l.slice(0,n)}

```

### Ungolfed

```
function u(n) {
    var l = [1, 2],
        i = 3,
        j, k, z;

    for (; l.length < n; ++i) {
        z = 0;
        l.forEach(function (j) {
            l.forEach(function (k) {
                if (j < k & j + k === i) {
                    z++;
                }
            });
        });
        if (z === 1) {
            l.push(i);
        }
    }

    return l.slice(0, n);
}

```
> 2 votes

# Answer
## CoffeeScript, ~~119~~ 114

Lately I've been practising CoffeeScript to improve at golfing JavaScript, so here's my JavaScript answer compiled into CoffeeScript:

```
u=(n)->l=[1,2];i=3;z=0;(for j in l
 for k in l
  z+=j<k&j+k==i
l.push(i) if z==1;++i;z=0)while l.length<n;l[..n-1]

```

I don't understand loops and comprehensions in CoffeeScript very well so perhaps this can be golfed further but it's what I have for now. Newlines are counted as one character (Unix style).
> 2 votes

# Answer
# Mathematica, ~~107~~ 91 bytes

```
Nest[#~Append~Min@Cases[Tally[Tr/@#~Subsets~2],{n_,1}:>n]&,{1,2},i=Input[]]~Drop~{3}~Take~i

```

It's a very direct implementation of the spec.

* Find all pairs.
* Delete all duplicates.
* Delete all numbers less than the last Ulam number.
* Append the minimum to the list.

I'm also applying Dennis's trick of including sums with `0`, but the catch is that this makes the third element of the list `0` before resuming as one would expect, so I need to remove that element from the list.

It handles an input of `1000` in a few seconds, but I doubt that you'll get a result for 10k in a reasonable amount of time. But I don't think any of the others performs well on that either.
> 2 votes

# Answer
# OCaml - 254 Characters

The code use an hash table to store the sum of the current elements of the list and update it each time a new element is computed.

```
open Hashtbl let h=create 7 let()=add h 3 1 let rec r n i l=if n=0then List.rev l else if mem h i&&find h i=1then(List.iter(fun x->if mem h(x+i)then replace h(x+i)2else add h(x+i)1)l;r(n-1)(i+1)(i::l))else r n(i+1)l let u n=if n=1then[1]else r(n-2)3[2;1]

```

## Usage:

Within OCaml interpreter:

```
# u 26;;
- : int list =
[1; 2; 3; 4; 6; 8; 11; 13; 16; 18; 26; 28; 36; 38; 47; 48; 53; 57; 62; 69;
 72; 77; 82; 87; 97; 99]

```

## Ungolfed

```
open Hashtbl
let h = create 7
let() = add h 3 1
let rec r n i l =
  if n=0 then List.rev l
  else if mem h i && find h i=1 then
    begin
      List.iter
        (fun x-> if mem h(x+i) then replace h (x+i) 2 else add h (x+i) 1)
        l;
      r (n-1) (i+1) (i::l)
    end
  else r n (i+1) l

let u n = if n=1 then [1] else r (n-2) 3 [2;1]

```
> 2 votes

# Answer
# Python, ~~137~~ ~~128~~ 126 characters.

```
U,i=[1,2],2
for _ in [[0]]*(input()-2):
 t=_*3*i
 for a in U:
  for b in U:t[a+b]+=a!=b
 i=t[i+1:].index(2)+i+1;U+=[i]
print U

```

This is my first golf, and I've brought it down from ~250 characters, I'm pretty happy but would love suggestions on how to improve!
> 2 votes

# Answer
# C#, 257

Brute force approach, using LINQ:

```
using System.Linq;class U{void F(int n){var u=n<2?new int[]{1}:new int[]{1,2};for(int i=3;u.Length<n;++i)if(u.SelectMany(x=>u,(a,b)=>new{A=a,B=b}).Count(x=>x.A>x.B&&x.A==i-x.B)==1)u=u.Union(new int[]{i}).ToArray();System.Console.Write(string.Join("",u));}}

```

## Ungolfed, With Test Harness

```
using System.Linq;
class Ulam
{
    void F(int n)
    {
        //handle special case where n = 1 (ugh)
        var u = n < 2 ? new int[] { 1 } : new int[] { 1, 2 };
        for (int i=3; u.Length<n; ++i)
            if (u.SelectMany(x => u, (a, b) => new { A = a, B = b })
                     .Count(x => x.A > x.B && x.A == i - x.B) == 1)
                u = u.Union(new int[] { i }).ToArray();
        System.Console.Write(string.Join(" ",u));
    }
    public static void Main(string[] args)
    {
        new Ulam().F(1);
        System.Console.WriteLine();
        new Ulam().F(2);
        System.Console.WriteLine();
        new Ulam().F(3);
        System.Console.WriteLine();
        new Ulam().F(26);
        System.Console.WriteLine();
    }
}

```
> 0 votes

# Answer
# Pyth, ~~27~~ 25 bytes

```
<uaGh-sfq1lT.gksM.cG2GQS2

```

Try it online here.

```
<uaGh-sfq1lT.gksM.cG2GQS2Q   Implicit: Q=eval(input())
                             Trailing Q inferred
 u                    Q      Perform the following Q times...
                       S2    ... with G initialised to [1,2]:
                 .cG2          Get all 2-element combinations of G
               sM              Sum each pair
            .gk                Group them by value
                                 The groups are sorted by the result of the sum
       f                       Filter the groups, as T, keeping those where:
          lT                     Length of T
        q1                       Equal to 1
      s                        Flatten list
     -               G         Remove elements of the above which are already in G
    h                          Take the first of the remaining elements
                                 This is the smallest, as the grouping also sorted them
  aG                           Append this to G
<                        Q   Take the first Q elements, implicit print

```

*Edit: golfed 2 bytes by performing summation before grouping. Previous version: `<uaGh-mssdfq1lT.gsk.cG2GQS2`*
> 0 votes

# Answer
# C, 478 bytes

```
#define R return
bs(x,v,l,h,r)unsigned x,*v,l,h,*r;{unsigned m;for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}*r=m;R 0;}
#include<stdlib.h>
unsigned*f(unsigned w){unsigned*u=0,i,k,m,y,z;if(w>1E6||w==0)R u;u=malloc(w*sizeof*u);if(!u)R u;k=0;u[k++]=1;if(w==1)R u;m=u[k++]=2;if(w==2)R u;l:for(i=0,y=0,z=k-1,++m;i<k;y+=bs(m-u[i],u,i+1,z,&z),++i)if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;if(m==0){free(u);u=0;R u;}if(y!=1)goto l;u[k++]=m;if(k< w)goto l;R u;}

```

In Tio now in 9 seconds it would find 10000 values (and in there print the first 100 values). The trick is using not linear search in the inner loop but binary search... These below are functions well indented and full readable (at last for me):

```
bsCopy(x,v,l,h,r)unsigned x,*v,l,h,*r;
{unsigned m;
 for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}
 *r=m;R 0;// in *r if return 0 the min index that fail else the index of find x
}

unsigned*fCopy(unsigned w)
{unsigned*u=0,i,k,m,y,z;
 if(w>1E6||w==0)R u;
 u=malloc(w*sizeof*u);
 if(!u)R u;
 k=0;u[k++]=1;if(w==1)R u;
   m=u[k++]=2;if(w==2)R u;//below I suppose m-u[i] is in the range (if exist in u) (i+1)..z
 l: for(i=0,y=0,z=k-1,++m;i<k;y+=bsCopy(m-u[i],u,i+1,z,&z),++i)
          if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;
   if(m==0){free(u);u=0;R u;}
          if(y!=1)goto l;
   u[k++]=m;if(k< w)goto l;
 R u;
}

```
> 0 votes

# Answer
# APL(NARS), 278 char, 556 bytes

```
∇u←p w;m;y;i;k;z;r;bs
bs←{(x l h)←⍵⋄l>h:0,h⋄x<⍺[t←⌊2÷⍨l+h]:⍺∇x,l,t-1⋄x>⍺[t]:⍺∇x,(t+1),h⋄1,t}
u←⍬  ⋄→0×⍳(w>1E6)∨w≤0
u←u,1⋄→0×⍳w=1
u←u,2⋄→0×⍳w=2⋄k←m←2
i←1⋄y←0⋄m+←1⋄z←k
→7×⍳(y>1)∨i>k⋄→7×⍳m<u[i]+{i=k:0⋄u[i+1]}⋄r←u bs(m-u[i]),(i+1),z⋄y+←↑r⋄z←2⊃r⋄i+←1⋄→6
→5×⍳y≠1⋄u←u,m⋄k+←1⋄→5×⍳k<w
∇

```

it would be the translation in APL of C one I sent. It seems i not understand when to use ∇∇ in place of ∇... possible ∇∇ is used when there is one argument is one function (and not one other type). "u bs x, a,b" should be the bin search in "u" array for the value "x" in the range a..b; it would return 1, indexWhereFind or 0, indexWhereEndOfsearch. With argument 200 p function take +- a minute here...

```
  p 100
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126
  131 138 145 148 155 175 177 180 182 189 197 206 209 219 221 236 238 241 243 253
  258 260 273 282 309 316 319 324 339 341 356 358 363 370 382 390 400 402 409 412
  414 429 431 434 441 451 456 483 485 497 502 522 524 544 546 566 568 585 602 605
  607 612 624 627 646 668 673 685 688 690
  p¨1 2 3 4
1  1 2  1 2 3  1 2 3 4

```
> 0 votes

---
Tags: code-golf, number, number-theory, sequence
---


title: Reverse Engineer Polling Statistics

text:
# Question
Title: Reverse Engineer Polling Statistics
## Introduction

Given a set of percentages of choices in a poll, calculate the minimum number of voters there must be in the poll to generate those statistics.

Example: What is your favorite pet?

* Dog: `44.4%`
* Cat: `44.4%`
* Mouse: `11.1%`

Output: `9` (minimum possible # of voters)

## Specs

Here are the requirements for your program/function:

* You are given an array of percentage values as input (on stdin, as function argument, etc.)
* Each percentage value is a number rounded to one decimal place (e.g., `44.4 44.4 11.1`).
* Calculate the minimum possible number of voters in the poll whose results would yield those exact percentages when rounded to one decimal place (on stdout, or function return value).
* **Bonus**: -15 characters if you can solve in a "non-trivial" way (i.e., doesn't involve iterating through every possible # of voters until you find the first one that works)

## Example

```
>./pollreverse 44.4 44.4 11.1
9
>./pollreverse 26.7 53.3 20.0
15
>./pollreverse 48.4 13.7 21.6 6.5 9.8
153
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6
2000
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7
667
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7
2000
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8
401

```

## Scoring

This is code-golf, so shortest possible characters wins. Any bonuses are further subtracted from the total character count.

# Answer
# APL (Dyalog Classic), ~~48~~ 43 bytes

*-5 bytes by Adám*

```
+/0(⊢+{(⌈/⍷⊢)⍺-⍵÷+/⍵})⍣{z≡⍎3⍕⍺÷+/⍺}⍨z←.01×⎕

```

Full program taking input from stdin.

Try it online! Link is to dfn version.

### Ungolfed

```
normalize ← ⊢ ÷ +/
find_max ← {⍵⍷⍨⌈/⍵}
round ← {⍎3⍕⍵}
increase ← {find_max ⍺ - normalize ⍵}
vote_totals ← {z←⍺ ⋄ ⍺ (⊢+increase)⍣{z ≡ round normalize ⍺} ⍵}
h ← {+/ (.01×⍵) vote_totals 0}

```

Try it online!

* `normalize` divides (`÷`) all elements of its right argument () by its sum (`+/`).
* `round(y)` rounds y to 3 decimal places by formatting () and then evaluating () each element of y.
* `find_max(y)` returns an array with 1 where max(y) is found and 0 elsewhere.
* `increase(x,y)` takes x (the goal percentages) and y (the array of current vote totals) and calculates where to add 1 in y to bring the percentages closer to x.
* `vote_totals(x,y)` takes x (the goal percentages) and y (the starting vote totals) and executes f repeatedly, adding votes until the percentages round to x.
    + The syntax `f ⍣ g` means to execute `f` repeatedly until `g(y,f(y))` is true. In this case we ignore `f(y)`.
* `h(x)` sets y to 0 (equivalent to an array of 0s due to vectorization), executes g, and sums the final vote totals.
> 3 votes

# Answer
# Python, 154

```
def p(x):
 n=[1]*len(x);d=2;r=lambda z:round(1000.*z/d)/10
 while 1:
    if(map(r,n),sum(n))==(x,d):return d
    d+=1
    for i in range(len(x)):n[i]+=r(n[i])<x[i]

```

It works for the last example now.

Example runs:

```
>>> p([44.4, 44.4, 11.1])
9
>>> p([26.7, 53.3, 20.0])
15
>>> p([48.4, 13.7, 21.6, 6.5, 9.8])
153
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 99.6])
2000
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 98.7])
667
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 98.7])
2000
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 97.8])
401

```
> 7 votes

# Answer
# Python, 154

```
def r(l):
 v=0
 while 1:
  v+=1;o=[round(y*v/100)for y in l];s=sum(o)
  if s:
    if all(a==b for a,b in zip(l,[round(y*1000/s)/10for y in o])):return s

```
> 4 votes

# Answer
## J, 57 characters

```
t=:".>'1'8!:0|:100*%/~i.1001
{.I.*/"1(t{~i.#t)e."1~1!:1[1

```

Used the trivial method. It takes input from the keyboard. `t` creates a lookup table and the second line looks for the input within the table. I can provide an expanded explanation of the code if anyone's interested.

I had looked into using the percentage to create a fraction then get the lowest form of the fraction to figure out the number, but I couldn't figure out a way to make it work with the rounding of the results.
> 4 votes

# Answer
# VBA - 541

This has got some glaring errors, but it was my attempt to find a non-trivial/looping-until-I-get-the-right-number solution. I have not fully golfed it, though I don't think there's much to add in that regard. However, I've spent too much time on this, and it hurts my head now. Not to mention, the rules are probably very broken and apply more or less to these examples only.

This does very well for a lot of simple tests I ran, (i.e. even totals, 2 or 3 inputs) but it fails for some of the tests presented by the challenge. However, I found that if you increase the decimal precision of the input (outside the scope of the challenge), the accuracy improves.

Much of the work involves finding the gcd for the set of numbers provided, and I sort of got that through `Function g()`, though it is for sure incomplete and likely a source of at least some of the errors in my outputs.

Input is a space-delimited string of values.

```
Const q=10^10
Sub a(s)
e=Split(s)
m=1
f=UBound(e)
For i=0 To f
t=1/(e(i)/100)
m=m*t
n=IIf(n>t Or i=0,t,n)
x=IIf(x<t Or i=0,t,x)
Next
h=g(n,x)
i=(n*x)/(h)
If Int(i)=Round(Int(i*q)/q) Then
r=i
ElseIf (n+x)=(n*x) Then
r=(1/(n*x))/h/m
ElseIf x=Int(x) Then
r=x*(f+1)
Else
z=((n+x)+(n*x)+m)*h
y=m/(((m*h)/(f+1))+n)
r=IIf(y>z,z,y)
End If
Debug.Print Round(r)
End Sub
Function g(a,b)
x=Round(Int(a*q)/q,3)
y=Round(Int(b*q)/q,3)
If a Then
If b Then
If x>y Then
g=g(a-b,b)
ElseIf y>x Then
g=g(a,b-a)
Else
g=a
End If
End If
Else
g=b
End If
End Function

```

**Testcases** (input ==\> expected/returned):

```
Passed:

"95 5" ==> 20/20
"90 10" ==> 10/10
"46.7 53.3" ==> 15/15
"4.7 30.9 40.4 23.8" ==> 42/42
"44.4 44.4 11.1" ==> 9/9
"26.7 53.3 20.0" ==> 15/15
"48.4 13.7 21.6 6.5 9.8" ==> 153/153
"0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 99.55" ==> 2000/2000
"0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 98.65" ==> 2000/2000
"0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 98.65067" ==> 667/667

Failed:

"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6" ==> 2000/1000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7" ==> 2000/5000
"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7" ==> 667/1000
"0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 98.65" ==> 667/10000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8" ==> 401/500
"0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 97.75" ==> 401/235
"0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 97.75561" ==> 401/14010

```
> 3 votes

# Answer
# C# (.NET Core), 286 bytes

```
double M(string[]a){var p=a.Select(double.Parse).ToList();var n=p.Select(x=>1d).ToList();var c=2;for(;;){Func<double,double>f=x=>Math.Round(x*1000/c,(MidpointRounding)1)/10;if(n.Select(f).Zip(p,(x,y)=>x==y).All(z=>z)&&c==n.Sum())return c;c++;n=n.Zip(p,(x,y)=>x+(f(x)<y?1:0)).ToList();}}

```

Try it online!

Saved lots of bytes thanks to Peter Taylor and Embodiment of Ignorance
> 2 votes

# Answer
# Python 3, ~~140~~ ~~139~~ 137 bytes

```
f=lambda l,m=1,i=0,c=0,x=0:round(x*100,1)-l[i]and(x<1and f(l,m,i,c,x+1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

```

Try it online!

Gives the right answer for the first two test cases, and runs into Python's recursion limits for the others. This is not very surprising, since *every* check is made on a new recursion level. It's short, though...

(An explanation of the used variables can be found in the TIO link)

```
f=lambda l,m=1,i=0,c=0,x=1:round(x*100,1)-l[i]and(x and f(l,m,i,c,x-1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

```

should work for **136** bytes, but doesn't due to float precision.
> 0 votes

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