title: Point-free madness

text:
# Question
Title: Point-free madness
This challenge is about Haskell point-free style polynomial functions.

Although you **don't** need to know Haskell language to do this challenge, Haskellers might have an advantage here.

Point-free means roughly that variables(points) are not named and the function is created from compositions of others functions.

For example, in Haskell, the function `f : x->x+1` can be defined by: `f x = x+1` which uses the variable `x` and is not point-free. But it can be simplified to its point-free version: `f=(+1)`. Likewise, you have `f x=x^k` -\> `f=(^k)`, and `f x=x*k` -\> `f=(*k)`, `f x y=x*y` -\> `f=(*)`

More complex functions can be constructed using the Haskell's function composition operator `(.)`:

`f x = x->2*x+1` is converted to `f = (+1).(*2)`: Multiply by 2 then add 1.

In this challenge you will have to create a point-free style Haskell code generator. This generator will take a polynomial function of multiple variables as input and output corresponding code in Haskell language and in point-free style.

This is way harder than the previous simple functions, so if you don't know Haskell at all, or if you are not comfortable with operators `(.)`, `(>>=)`, `(<*>)` on functions, You should follow the **Construction Process** which is detailled bellow or start directly from its **Python Implementation**.

## Example

Say you want to write the polynomial function `x, y -> x²+xy+1` point-free.

Your program might output the folowing code:

```
((<*>).(.)((<*>).(.)(+)))                           -- sum 2 functions of 2 variables
    (
        ((<*>).(.)((<*>).(.)(+)))                   -- sum 2 functions of 2 variables
            (
                (
                    ((.)((.(^0)).(*)))              -- g x y = y^0 * f x   => g x y = x^2
                    (((.(^2)).(*))(1))              -- f x = 1*x^2
                )
            )
            (
                ((.)((.(^1)).(*)))                  -- g x y = y^1 * f x   => g x y = x*y
                (((.(^1)).(*))(1))                  -- f x = 1*x^1
            )
    )
    (
        ((.)((.(^0)).(*)))                          -- g x y = y^0 * f x   => g x y=1
        (((.(^0)).(*))(1))                          -- f x = 1*x^0
    )

```

This is a really ugly yet valid Haskell code, and this is really not the shortest one (`(.).(.)(+1).(*)<*>(+)` works as well), but we will see how it can be generalized to any multivariable polynomial.

## Construction Process:

One possible algorithm is to first write each monomial function in point-free style (step 1), then create operators to add functions two at a time (step 2), and apply this to the list of monomials, writing `f+g+h` as `(f+(g+h))` (step 3).

1. Write each monomial, taking each of the factors successively. Example: `11*a^12*b^13*c^14`.

* Start with `(11)`, a 0-argument function.
    * Take the previous function `f0` and write `((.(^12)).(*))(f0)`; this is a 1-argument function `a->11*a^12`
    * Take the previous function `f1` and write `((.)((.(^13)).(*)))(f1)`; this is a 2-argument function `a->b->11*a^12*b^13`.
    * Finally, take the previous function `f2` and write `((.)((.)((.(^14)).(*))))(f2)`. Thus `a->b->c->11*a^12*b^13*c^14` is converted to point-free style as `((.)((.)((.(^14)).(*))))(((.)((.(^13)).(*)))(((.(^12)).(*))(11)))`.
    * In general, continue transforming `f` to something of the form `((.) ((.) ((.) ... ((.(^k)).(*)) ))) (f)` until your monomial is built and takes the desired number of arguments.
    * Warning: If using this construction algorithm, each monomial must take the same number of arguments. Add some `^0` for missing variables (`a^2*c^3` -\> `a^2*b^0*c^3`)
    * You can test your monomial generator here with this example and the next iteration: Try it online!
2. Create the operator \\$O\_n\\$ that adds two functions of \\$n\\$ arguments:

* \\$O\_0\\$ is `(+)`
    * For \\$n\geq0\\$, \\$O\_{n+1}\\$ can be constructed recursively as `((<*>).(.)( O_n ))`
    * E.g. `((<*>).(.)(((<*>).(.)(+))))` adds two 2-argument functions.
3. Chain the addition: The operator from step 2 only adds two monomials, so we must manually fold addition. For example, for monomials f, g, h, write `f+g+h` =\> `O_n(f)( O_n(g)( h ) )` replacing f, g, and h with their point-free equivalents from step 1, and \\$O\_n\\$ by the correct operator from step 2 depending on the number of variables.

## Implementation in Python

This is an ungolfed implementation in Python 3 which reads polynomials as list of monomials where monomial is a list of integers:

```
def Monomial(nVar,monoList):
    if nVar==0:
        return "({})".format(monoList[0])
    else:
        left = "((.(^{})).(*))"
        mono = "({})".format(monoList[0])
        for i in range (0,nVar):
            p = monoList[i+1] if i+1<len(monoList) else 0
            mono = left.format(p) + "(" + mono + ")"
            left = "((.)" + left + ")"
        return mono

def Plus(nVar):
    if nVar==0:
        return "(+)"
    else:
        return "((<*>).(.)(" + Plus(nVar-1) + "))"

def PointFree(l):
    nVar = 0
    for monoList in l:
        if nVar<len(monoList)-1: nVar = len(monoList)-1

    pointfree = Monomial(nVar,l[0])

    plusTxt = Plus(nVar)

    for monoList in l[1:]:
        pointfree = plusTxt + "(" + Monomial(nVar,monoList) + ")(" + pointfree + ")"

    return pointfree

```

## Input

The input is the polynomial function to be converted.

The input format shall consist of a list of Integers in any format you want. For example, you might define the polynomial `5*a^5+2*a*b^3+8` as the list `[[5,5,0],[2,1,3],[8]]`

## Output code

The output is the Haskell code for that polynomial as a function of n Integers,

written in point-free style with only numeric literals and base functions(no Import).

Of course, the above process and implementation comply to these rules.

For Haskell programmers, this means no list comprehension, no lambdas and only Prelude functions(no import, language extensions..): `(+) (-) (*) (^) (.) (<*>) (>>=) flip sum zip uncurry curry ($) ...`

## Test cases

Your program should work for all valid inputs, but will be scored on on these five polynomials:

```
f1 a b c d = 5*a^4*b^3*c^2 + a^2*b^3*c^4*d^5
f2 a b c   = -5*a^5*c^8 + 3*b^3*c^4 + 8
f3 a b     = 5*a^5+3*b^3+8
f4 a       = a^3+a^2+a+1
f5         = 1+2-3

```

Tests cases with the Python code given above:Try it online!

Once you have run your program on these samples, copy/paste your output code into the following program (in the "Code" section) and run it in order to check your outputs:

Try it online!

If your functions are correct, it will output:

```
f1 : +++ OK, passed 100 tests.
f2 : +++ OK, passed 100 tests.
f3 : +++ OK, passed 100 tests.
f4 : +++ OK, passed 100 tests.
f5 : +++ OK, passed 100 tests.

```

## Scoring

Code length + (sum of the test cases output length)/8.

-300 if your program consist in a point-free style Haskell function (with the same rules as for output).

I'll give a Bounty of **250 points** if you beat my score of 73.125 (272 + 809/8 - 300).

The Python solution given above is 797 bytes long, and outputs functions of length: 245, 282, 180, 132, and 24 so the score would be `797 + (245+282+180+132+24)/8 = 904.875`.

The smallest score wins!!

# Answer
> 6 votes
# Haskell, 278+448/8-300=34

```
(foldr.pure.pure.((++).(foldr(('(':).(++".)")<$id).((++).("(sum.zipWith(*)"++).show.map head<*>(".flip(map.(product.).zipWith(^))"++).(++")").show.map tail)<*>tail.head)<*>(++" pure)").("("++).foldr(("(("++).(++".flip(:)).)")<$id)"id".drop 2.head))<*>show.sum.concat<*>tail.head

```

Saved 14 bytes by having a closer look at parens as suggested by @Damien, then saved 8 more using another hint from them.

Since input is "list of Integers in any format you want", I take list of lists with first elements the multiplicative constants of the summands, and the rest all the corresponding exponents in reverse order. So the example polynomial `5*a^5+2*a*b^3+8` is given by `[[5,0,5],[2,3,1],[8,0,0]]`. (Didn't try `[(5,[0,5]),(2,[3,1]),(8,[0,0])]` \- would that be allowed?)

The result for this example polynomial is this:

```
(((sum.zipWith(*)[5,2,8].flip(map.(product.).zipWith(^))[[0,5],[3,1],[0,0]]).).)(((id.flip(:)).) pure)

```

See the results for the test cases or try your own polynomial at the TIO-Link:

Try it online!

Check the results for the test cases here:

Check it online! (testing code from OP with my results)

# Answer
> 3 votes
# 05AB1E, score: 167 (111 bytes \+ 448/8)

```
¬g©i˜Oëøć',ý’.Œ¬With(’DŠ’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’sø',ý€…[ÿ]',ý…[ÿ]s…ÿÿ)®G"(ÿ.)"}„id®ÍF’((ÿ.ÒÀ(:)).)’}s“ÿ(ÿ©¬)

```

Since I don't know Haskell, I figured I'd just port the output of *@ChristianSievers*' Haskell answer, so make sure to upvote him!!
Input is taken in a similar matter as well (first being the multiplicative constant, and after that the exponents in reverse order). So for example: test case \\$5a^4b^3c^2+a^2b^3c^4d^5\\$ is given as input-list `[[5,0,2,3,4],[1,5,4,3,2]]`.

Try it online or verify all test cases.
Verify the outputs with OP's validator.

**Explanation:**

```
¬                       # Get the first inner list in the (implicit) input-list
 g                      # Get the length of that list
  ©                     # And store it in variable ® (without popping)
i                       # If that length is 1:
 ˜O                     #  Take the flattened sum of the input-list
ë                       # Else:
 ø                      #  Zip/transpose the input-list; swapping rows/columns
  ć                     #  Extract head; pop and push head and remainder
   ',ý                 '#  Join this first list by ","
      ’.Œ¬With(’        #  Push dictionary String ".zipWith("
                D       #  Duplicate it
                 Š      #  Triple swap the items on the stack (a,b,c → c,a,b)
   ’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’
                        #  Push dictionary string "(sumÿ*)[ÿ].flip(map.(product.)ÿ^))",
                        #  where the three ÿ are filled with the values on the stack
   s                    #  Swap to take the remainder again
    ø                   #  Zip/transpose it back
     ',ý               '#  Join each inner-most list by ","
        €…[ÿ]           #  Surround each inner string in []-blocks
             ',ý       '#  Join those by "," again
                …[ÿ]    #  And surround the entire thing by []-blocks again
    s                   #  Swap the two strings on the stack
     …ÿÿ)               #  And fill them in into the string "ÿÿ)"
 ®G      }              #  Now loop ®-1 amount of times:
   "(ÿ.)"               #   And fill in the top string on the stack into string "(ÿ.)"
 „id                    #  Then push string "id"
    ®ÍF              }  #  Loop ®-2 amount of times:
       ’((ÿ.ÒÀ(:)).)’   #   And fill the top string of the stack into dictionary
                        #   string "((ÿ.flip(:)).)"
 s                      #  Swap the two strings of the stack again
  “ÿ(ÿ©¬)               #  And fill them into the dictionary string "ÿ( pure)"
                        # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why:

* `’.Œ¬With(’` is `".zipWith("`
* `’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’` is `"(sumÿ*)[ÿ].flip(map.(product.)ÿ^))"`
* `’((ÿ.ÒÀ(:)).)’` is `"((ÿ.flip(:)).)"`
* `“ÿ(ÿ©¬)` is `"ÿ( pure)"`

Unfortunately `ÿ` doesn't work for inner items in a list and requires an explicit , otherwise `',ý€…[ÿ]',ý…[ÿ]` could have been `2F',ý…[ÿ]}` instead.

---
Tags: code-challenge, polynomials, functional-programming, haskell
---


# Question
Title: Check if 2 arrays contain the same element
Write a program which will take for input 2 integer arrays and return a truthy value if there exists an element which is present in both of arrays, or a falsy one otherwise. The obvious solution to this problem would be to iterate through each element in the first array and compare it against each element in the second, but here's the catch: Your program must have an algorithmic complexity of at most, in the worst case, O(NlogN), where N is the length of the longer array,

Test cases:

```
 {1,2,3,4,-5},{5,7,6,8} -> false
 {},{0}                 -> false
 {},{}                  -> false
 {1,2},{3,3}            -> false
 {3,2,1},{-4,3,5,6}     -> true
 {2,3},{2,2}            -> true

```

This is , so the shortest code in bytes wins.

# Answer
# Actually, 1 byte

Try it online!

This is merely the set intersection built-in. The resultant value is the intersection of the two sets - a non-empty list (which is a truthy value) if there is an intersection, and an empty list (which is a falsey value) otherwise.

## Complexity

According to the Python Wiki, set intersection has a worst-case time complexity of `O(N*M)` (where `N` and `M` are the lengths of the two sets). However, the time complexity is only that bad when the two sets contain distinct objects that all have the same hash value (for example, `{"some string"} & {hash("some string")}`). Since the set elements are only integers in this case (and no two integers hash to the same value unless they are equal), the actual worst-case complexity is `O(min(N, M))` (linear in the length of the smaller of the two sets). The construction of each set is `O(N)` (linear in the number of elements), so the overall complexity is `O(max(N, M))` (the complexity is dominated by the construction of the larger set).
> 11 votes

# Answer
# TSQL, ~~40~~ ~~37~~ 36 bytes

SQL doesn't have arrays, it is using tables instead

Returns -1 for true or 0 for false

```
DECLARE @ table(a INT)
DECLARE @2 table(b INT)

INSERT @ values(1),(2),(3),(4),(-5)
INSERT @2 values(5),(6),(7),(8)

SELECT~-sign(min(abs(a-b)))FROM @,@2

```

**Try it out**
> 3 votes

# Answer
# Perl, 25+1 = 26 bytes in collaboration with Dada

```
print 2<($a{$_}|=$.)for@F

```

Run with `-a` (1 byte penalty).

An improved version of the program below (which is kept around to see the history of the solution, and to show the solution I found by myself; it also has more explanation). The `-a` option reads space-separated arrays as the input, storing them in `@F`. We use the `%a` dictionary (accessed as `$a{$_}`) to store a bitmask of which input arrays the input is in, and print `1` every time we see an element in both arrays, i.e. a value higher than 2 inside the resulting bitmask (fortunately, a failing comparison returns the null string, so the `print` does nothing). We can't use `say` because a newline is truthy in Perl. Performance is asymptotically the same as the older version of the program (but faster in terms of constant factors).

# Perl, 44+1 = 45 bytes

```
$a{"+$_"}|=$.for split}{$_={reverse%a}->{3}

```

Run with `-p` (1 byte penalty). Input one array per line, separating the elements by spaces.

This works via creating a hash table `%a` that stores a bitmask of the input arrays that a value has been seen in. If it's been seen in both the array on line 1 and on line 2, the bitmask will therefore store the value 3. Reversing the hash and seeing if 3 has a corresponding key lets us know if there are any values in common.

The complexity of this algorithm is O(n) if you consider hash creation to be constant time (it is, if you have bounded integers, like Perl does). If using bignum integers (which could be input into this program, as it leaves the input as a string), the complexity of the algorithm itself would nominally be O(n log n) for each hash creation, and O(n) for the hash reversal, which adds up to O(n log n). However, Perl's hashing algorithm suffers from potential O(n²) performance with maliciously selected input; the algorithm is randomized, though, to make it impossible to determine what that input is (and it's possible that it can't be triggered simply with integers), so it's debatable what complexity class it "morally" counts with. Luckily, this doesn't matter in the case where there's only finitely many possible distinct elements in the array.

This code will work for input other than integers, but it won't work for more than two arrays (because the `3` is hardcoded and because input on the third line wouldn't bitmask correctly, as it isn't a power of 2). Rather annoyingly, the code naturally returns one of the duplicate elements, which is truthy in *almost* all cases, but `"0"` is falsey in Perl and a valid duplicate element in the array. As such, I had to waste three bytes prepending a `+` to the output, which is the cheapest way I found to give a truthy output in the edge case of the arrays overlapping at `0`. If I'm allowed to use notions of truthy and falsey from a language other than Perl (in which any nonempty string is truthy), you can change `"+$_"` to `$_` to save three bytes.
> 2 votes

# Answer
# Ruby, 37 bytes:

```
exit ($*.map{|x|eval x}.reduce:&)!=[]

```

As in the definition: "program which will take for input 2 integer arrays and return a truthy value if...", this is a program, accepts 2 arrays as strings in input, returns true or false.

as a function - 14 bytes:

```
->a,b{a&b!=[]}

```

## Complexity:

The ruby documentation of the itnersection (&) operator says "It compares elements using their hash and eql? methods for efficiency.", which I suppose is exactly what we are looking for.

Empirically:

```
$ time ruby a.rb "[*1..1000001]" "[*1000001..2000000]"

real    0m0.375s
user    0m0.340s
sys 0m0.034s

$ time ruby a.rb "[*1..2000001]" "[*2000001..4000000]"

real    0m0.806s
user    0m0.772s
sys 0m0.032s

$ time ruby a.rb "[*1..4000001]" "[*4000001..8000000]"

real    0m1.932s
user    0m1.857s
sys 0m0.073s

$ time ruby a.rb "[*1..8000001]" "[*8000001..16000000]"

real    0m4.464s
user    0m4.336s
sys 0m0.119s

```

Which seems to confirm it.
> 2 votes

# Answer
# Python2 - ~~41~~ 30 bytes

```
lambda a,b:bool(set(a)&set(b))

```

Set intersection: O(min(N,M)) where N and M are the length of the sets.

Conversion from a list to a set: O(max(N,M))

* Thanks to Jakube for saving 9 bytes! `set(a).intersection(b)` -\> `set(a)&set(b)`
* Thanks to Kade for saving 2 bytes! -\> removed `f=`
> 2 votes

# Answer
## PowerShell, ~~88~~ ~~78~~ ~~77~~ 23 bytes

```
!!(diff -Inc -Ex $A $B)
```

Thanks to @briantist for shaving off a whopping 54 bytes from my original, more verbose answer by shortening `-IncludeEqual`, `-ExcludeDifferent`, and `-Not`!

```
~~if(-Not(diff -IncludeEqual -ExcludeDifferent $A $B)){("false")}else{("true")}~~
```

I can't find the source for `Compare-Object` (`diff` is an alias for `Compare-Object`), so I'm not certain on the time complexity.
> 2 votes

# Answer
# Axiom, 439 bytes

```
c:=0;s(x,y)==(free c;if x.1=%i and y.2=%i then(x.2<y.1=>return true;x.2>y.1=>return false;c:=1;return false);if x.2=%i and y.1=%i then(x.1<y.2=>return true;x.1>y.2=>return false;c:=1;return false);if x.1=%i and y.1=%i then(x.2<y.2=>return true;x.2>=y.2=>return false);if x.2=%i and y.2=%i then(x.1<y.1=>return true;x.1>=y.1=>return false);false);r(a,b)==(free c;c:=0;m:=[[%i,j] for j in a];n:=[[i,%i] for i in b];r:=merge(m,n);sort(s,r);c)

```

this convert the first list in a list as \[\[i,1\], \[i,2\]...\] the second list in a list as \[\[1,i\], \[0,i\]...\] where i is the variable imaginary than merge the 2 list, and make one sort that would find if there is one element of list 1 in the list 2 so it is at last O(N log N) where N=lenght list 1 + lenght list 2

ungolfed

```
-- i get [0,0,1,2,3] and [0,4,6,7]  and build [[%i,0],[%i,0],[%i,1],[%i,2] [%i,3],[0,%i],..[7,%i]]
c:=0
s(x:List Complex INT,y:List Complex INT):Boolean==
  free c  -- [%i,n]<[n,%i]
  if x.1=%i and y.2=%i then
    x.2<y.1=> return true
    x.2>y.1=> return false
    c:=1
    return false
  if x.2=%i and y.1=%i then
    x.1<y.2=>return true
    x.1>y.2=>return false
    c:=1
    return false
  if x.1=%i and y.1=%i then
    x.2< y.2=>return true
    x.2>=y.2=>return false
  if x.2=%i and y.2=%i then
    x.1< y.1=>return true
    x.1>=y.1=>return false
  false

r(a,b)==
  free c
  c:=0
  m:=[[%i, j]  for j in a]
  n:=[[ i,%i]  for i in b]
  r:=merge(m,n)
  sort(s, r)
  c

```

results

```
(12) -> r([1,2,3,4,-5], [5,7,6,8]), r([],[0]), r([],[]), r([1,2],[3,3]), r([3,2,1],[-4,3,5,6]), r([2,3],[2,2])
   Compiling function r with type (List PositiveInteger,List Integer)
       -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiled code for s has been cleared.
   Compiling function r with type (List PositiveInteger,List
  PositiveInteger) -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiling function s with type (List Complex Integer,List Complex
      Integer) -> Boolean
   Compiled code for s has been cleared.

   (12)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

```

i dont understand why it "clears" code for r and s...
> 2 votes

# Answer
# PHP, 15 bytes

```
array_intersect

```

Try it online!

A PHP built-in, as a callable/lambda function. Return is a PHP `truthy`/`falsey` testable value. Also, per the other PHP submission, this implementation should meet the challenge complexity requirements (StackExchange).
> 2 votes

# Answer
## R, 23 bytes

```
sum(scan()%in%scan())>0

```

If we assume that there will always be one and only one element matching and that `1` is a truthy value (which it is in **R**), then we can write :

```
sum(scan()%in%scan())

```

which is 21 bytes.
> 1 votes

# Answer
# PHP, ~~55~~ 51 bytes

```
<?=count(array_intersect($_GET[a],$_GET[b]))<1?0:1;

```

Usage: save in a file and call from browser:

`intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=5` outputs `0` for `false`.

`intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1` outputs `1` for `true`.

About complexity, I couldn't find references but according to this StackOverflow's post the script should be OK
> 1 votes

# Answer
# GolfScript, 1 byte

If taking the input directly as arrays on the stack is allowed, this one-byte GolfScript solution should meet the spec:

```
&

```

If text-based I/O is required, the input needs to be evaluated first, pushing the length up to *two* bytes:

```
~&

```

Both of these solutions use the GolfScript array intersection operator, which is implemented using the corresponding operator in Ruby. They return an empty array (which is falsy) if the arrays contain no matching elements, or a non-empty array (which is truthy) containing all the matching elements otherwise.

I have so far not been able to find any documentation on the internal implementation or asymptotic complexity of the Ruby array intersection operator, beyond the brief statement that "It compares elements using their hash and eql? methods for efficiency." However, a reasonable implementation using hash tables would run in O(*n*) time (assuming that hashing and comparisons are O(1)), and some quick performance testing suggests that this is indeed the case:

These tests were carried out using the GolfScript program `~2?.2*,/&`, which takes an integer *k*, generates an arithmetic sequence of 2 × 2*k* elements, split it into two arrays of 2*k* elements and computes their (obviously empty) intersection. The red stars show the measured execution time *t* in seconds (on a logarithmic scale) for various values of *k*, while the green line plots the function *t* = *c* × 2*k*, where the scaling constant *c* ≈ 2−17.075 was chosen to best fit the measured data.

(Note that, on a log-log plot like this, *any* polynomial function of the form *t* = *c* × (2*k*)*a* would yield a straight line. However, the slope of the line depends on the exponent *a*, and the data is certainly consistent with *a* = 1 as shown by the green line above. FWIW, the numerical best-fit exponent for this data set was *a* ≈ 1.00789.)
> 1 votes

# Answer
## JavaScript (ES6), 39 bytes

```
(a,b,c=new Set(b))=>a.some(e=>c.has(e))

```

Will be worse than O(n+m) but hopefully not as bad as O(n\*m).
> 0 votes

# Answer
## Rust, 103 bytes

```
|a:&[i32],b:&[i32]|!b.iter().collect::<std::collections::HashSet<_>>().is_disjoint(&a.iter().collect())

```

Takes two array slices (or references to full arrays, they dereference to slices automatically), bundles them up into sets, and checks for non-disjointness. I'm not quite sure how set union is implemented in the Rust standard library, but it should be O(n + m) at worst.

Without using collections, the easiest alternative I see is to sort both arrays, then step over them carefully to look for duplicates. Something like this

```
fn overlapping(a: &Vec<i32>, b: &Vec<i32>) -> bool{
    let mut sa = a.clone();
    sa.sort();
    let mut sb = b.clone();
    sb.sort();
    let mut ai = 0;
    let mut bi = 0;
    while ai < a.len() && bi < b.len() {
        if sa[ai] < sb[bi] {
            ai += 1;
        } else if sa[ai] > sb[bi] {
            bi += 1;
        } else{
            return true;
        }
    }
    false
}

```

But that requires too much mutation to be fun to golf in Rust IMO :)
> 0 votes

# Answer
# Axiom, ~~50~~ 221 bytes

```
binSearch(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)

```

ungolfed

```
--suppose v.1<=v.2<=....<=v.#v
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v  --1  4
    repeat
       l>h=>break
       m:=(l+h)quo 2   --m=(4+1)/2=5/2=2
                       --output [l,m,h]
       x<v.m=>(h:=m-1) --l x m  h =>
       x>v.m=>(l:=m+1)
       return m
    0

g(a,b)==
  if #a>#b then (v:=a;w:=b)
  else          (v:=b;w:=a)
  c:=sort(v)
  --output c
  for x in w repeat(if binSearch(x,c)~=0 then return 1)
  0

```

g(a,b) gets the more big array beetwin a and b; suppose it has N elements: sort that array, do binary search with elements that other array. This would be O(Nlog(N)). It return 0 for no element of a in b, 1 otherwise.

results

```
(6) ->  g([1,2,3,4,-5], [5,7,6,8]), g([],[0]), g([],[]), g([1,2],[3,3]), g([3,2,1],[-4,3,5,6]), g([2,3],[2,2])
   Compiling function binSearch with type (PositiveInteger,List Integer
      ) -> NonNegativeInteger

   (6)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

```
> 0 votes

# Answer
## Python, 11 bytes

```
set.__and__

```

Builtin that takes 2 sets and does an intersection on them
> 0 votes

# Answer
# Jelly, 2 bytes

```
œ&

```

Try it online!

Explanation

```
 œ&  Main link. Arguments: x y
⁸    (implicit) x
   ⁹ (implicit) y
 œ&  Intersection of x and y

```
> 0 votes

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


title: Programmer's Garden

text:
# Question
Title: Programmer's Garden
# Programmer's Garden

Being a professional software developer, you cannot risk exposing yourself to the harsh non-artificial light of the sun, but you also have a soft spot for flowers, and want to keep your garden in good shape all year round.

To this end, a gardener is hired each month to tidy up the flowerbed at the foot of your house. However you need to make sure the gardener is doing his job properly, and work out a suitable payment for the hard working fellow. Naturally a software solution is best.

### Input

Your program will be fed input describing the flowerbed as it appears current, and details of items that need to be removed. The program must output the garden devoid of the clutter, and print out a breakdown of the gardeners pay. The input can be either be from STDIN, or as a single command line argument.

The first line of input is of the format

```
width height unwanted_item_type_count

```

where `width` is the width of the flowerbed, `height` is the height of the flowerbed (both in ASCII characters), and `unwanted_item_type_count` tells you how many lines will following containing a description of a type of item to be removed from the garden.

Each line for each unwanted type of item is of the format

```
width height string_representation name fee_per_item

```

where `width` is the width of the item, `height` is the height of the item (both in ASCII characters), `string_representation` is the string representation of the item without line breaks, `name` is an identifier for the type of item (spaces will be replaced with underscores), and `fee_per_item` is how much the gardener must be paid for the removal of each type of item.

For example

```
3 2 .R.\|/ rouge_flower 3

```

Represents an item type of name `rouge_flower`, which costs 3 to remove, and looks like this:

```
.R.
\|/

```

The items will not contain spaces, and no item may have a border consisting entirely of dots, and the string representation will also be the exact size described. Thusly, all of the following are invalid inputs:

```
3 1 ( ) space 0
1 1 . dot 0
2 1 .! bang 0
3 2 .@.\|/. plant 0

```

Note that 0 is however a valid fee (fees will always be integers greater than -1).

Note also that the flowerbed is predominately made up of dots (`.`) rather than spaces, and you can safely use whitespace as delimitation for all the inputs. The flowerbed is always bounded by dots itself.

After the unwanted item types are listed, then comes the ASCII representation of the flowerbed of given width and height.

### Output

Output should be to STDOUT, or suitable alternative if your language doesn't support it.

The output starts with a print-out of the flowerbed, but with all unwanted items removed (replaced with dots), so you can see how it should appear and check the gardener has done his job. Each item in the flowerbed will be surrounded by a rectangle of dots, and will be one-contiguous item (i.e. there will be no separating dots *inside* the item). For example

```
.....
.#.#.
.....

```

shows 2 separate items

```
.....
.\@/.
.....

```

shows 1 item

```
......
.#....
....|.
....|.
.o--/.
......

```

is invalid, as while the stone (#) can be matched, the snake (you couldn't tell it was a snake?) cannot because the stone interferes with the required surrounding of dots.

```
...
\@.
...

```

This is also invalid, as the snail is on the edge of the flowerbed, and the edge must always be bounded by dots in a valid input.

After this, there should be a listing of each type of unwanted item, giving the count, the cost per item, and costs for all the items (count * cost per item), in the format:

```
<count> <name> at <cost_per_item> costs <cost>

```

After this, there should be a single line yielding the total cost (the sum of the costs for unwanted items):

```
total cost <total_cost>

```

### Example

For this given input

```
25 18 3
4 2 .\/.\\// weeds 5
2 1 \@ snails 2
1 1 # stones 1
.........................
.\@/.................\@..
............\/...........
......O....\\//..^|^.....
.#...\|/.........^|^.....
..................|......
.................\|/.....
..\@.....\/...........#..
........\\//....#........
....*....................
...\|/......\/......\@/..
...........\\//..........
..................*......
.......\@/.......\|/.....
...O.....................
..\|/.......*............
.......#...\|/....\@.....
.........................

```

The program should produce this output

```
.........................
.\@/.....................
.........................
......O..........^|^.....
.....\|/.........^|^.....
..................|......
.................\|/.....
.........................
.........................
....*....................
...\|/..............\@/..
.........................
..................*......
.......\@/.......\|/.....
...O.....................
..\|/.......*............
...........\|/...........
.........................
3 weeds at 5 costs 15
3 snails at 2 costs 6
4 stones at 1 costs 4
total cost 25

```

The output *must* be terminated by a line-break.

This is code-golf, may the shortest code win.

### Additional test case

*Edit: this used to contain Unicode, which isn't allowed in the flowerbed, far too modern. This has been rectified, sorry about that.*

```
25 15 5
5 3 ..@..\\|//.\|/. overgrown_plants 3
5 3 @-o....|...\|/. semi-articulated_plant 4
3 2 .|.\@/ mutant_plants 5
1 1 $ dollars 0
1 1 # stones 1
.........................
........@................
....$..\|/...........@...
............|.......\|/..
...#.......\@/...........
.........................
.........................
......@.......@......@...
.....\|/....\\|//...\|/..
.............\|/.........
.#....................#..
.........$.......|.......
...\/.......\/..\@/..\/..
..\\//.....\\//.....\\//.
.........................

```

Expected Output:

```
.........................
........@................
.......\|/...........@...
....................\|/..
.........................
.........................
.........................
......@..............@...
.....\|/............\|/..
.........................
.........................
.........................
...\/.......\/.......\/..
..\\//.....\\//.....\\//.
.........................
1 overgrown_plants at 3 costs 3
0 semi-articulated_plants at 4 costs 0
2 mutant_plants at 5 costs 10
2 dollars at 0 costs 0
3 stones at 1 costs 3
total cost 16

```

# Answer
> 3 votes
## Perl - 636

There is definitely some more golfing that can be done. And probably better ways to do it too.

```
<>;while(<>){if(/ /){chomp;push@v,$_}else{$t.=$_}}for(@v){r(split/ /)}say$t.$y."total cost $u";sub r{my($e,$w,$c,$h,$z)=@_;($i,$f,$q,$d)=(1,0,0,"."x$e);@m=($c=~/($d)/g);@l=split/\n/,$t;while($i>0){($g,$j)=(1,0);for(0..$#l){if($j==0&&$l[$_]=~/^(.*?)\.\Q$m[$j]\E\./){$j++;$l="."x length$1}elsif($j<@m&&$l[$_]=~/^$l\.\Q$m[$j]\E\./){$j++}elsif($j>0){$l[$_-1]=~s!.\Q$m[$j-1]\E.!" ".$m[$j-1]=~s/\./ /gr." "!e;($j,$g)=(0,0)}if($j==@m){$k=$j;for($f=$_;$f>$_-$j;$f--){$k--;$o="."x length$m[$k];$l[$f]=~s/^($l)\.\Q$m[$k]\E\./$1.$o./}($g,$j)=(0,0);$q++}}if($g){$i--}}$t=join("\n",@l)."\n";$t=~s/ /./g;$p=$z*$q;$u+=$p;$y.="$q $h at $z costs $p\n"}

```

635 characters + 1 for `-C` flag to handle the euros.

If you have the input stored in `input.txt` you can run it with:

```
cat input.txt | perl -C -E'<>;while(<>){if(/ /){chomp;push@v,$_}else{$t.=$_}}for(@v){r(split/ /)}say$t.$y."total cost $u";sub r{my($e,$w,$c,$h,$z)=@_;($i,$f,$q,$d)=(1,0,0,"."x$e);@m=($c=~/($d)/g);@l=split/\n/,$t;while($i>0){($g,$j)=(1,0);for(0..$#l){if($j==0&&$l[$_]=~/^(.*?)\.\Q$m[$j]\E\./){$j++;$l="."x length$1}elsif($j<@m&&$l[$_]=~/^$l\.\Q$m[$j]\E\./){$j++}elsif($j>0){$l[$_-1]=~s!\Q$m[$j-1]\E!$m[$j-1]=~s/\./ /gr!e;($j,$g)=(0,0)}if($j==@m){$k=$j;for($f=$_;$f>$_-$j;$f--){$k--;$o="."x length$m[$k];$l[$f]=~s/^($l)\.\Q$m[$k]\E\./$1.$o./}($g,$j)=(0,0);$q++}}if($g){$i--}}$t=join("\n",@l)."\n";$t=~s/ /./g;$p=$z*$q;$u+=$p;$y.="$q $h at $z costs $p\n"}'

```

Here is the deparsed version. I went through and added some comments to help explain things. Maybe I'll go make the variable names more readable sometime. There may be some edge cases this doesn't work with but it works with the examples at least.

```
BEGIN { # These are the features we get with -C and -E flags
    $^H{'feature_unicode'} = q(1); # -C gives us unicode
    $^H{'feature_say'} = q(1); # -E gives us say to save 1 character from print
    $^H{'feature_state'} = q(1);
    $^H{'feature_switch'} = q(1);
}
<ARGV>; # throw away the first line
while (defined($_ = <ARGV>)) { # read the rest line by line
    if (/ /) { # if we found a space (the garden doesn't have spaces in it)
        chomp $_; # remove the newline
        push @v, $_; # add to our array
    }
    else { # else, we construct the garden
        $t .= $_;
    }
}
foreach $_ (@v) { # call the subroutine r by splitting our input lines into arguments
    r(split(/ /, $_, 0)); # the arguments would be like r(3,2,".R.\|/","rouge_flower",3)
}
say $t . $y . "total cost $u"; # print the cost at the end

# this subroutine removes weeds from the garden and counts them
sub r {
    BEGIN {
        $^H{'feature_unicode'} = q(1);
        $^H{'feature_say'} = q(1);
        $^H{'feature_state'} = q(1);
        $^H{'feature_switch'} = q(1);
    }
    my($e, $w, $c, $h, $z) = @_; # get our arguments
    ($i, $f, $q, $d) = (1, 0, 0, '.' x $e); # initialize some variables
    @m = $c =~ /($d)/g; # split a string like this .R.\|/ into .R. and \|/
    @l = split(?\n?, $t, 0); # split the garden into lines to process line by line
    while ($i > 0) {
        ($g, $j) = (1, 0);
        foreach $_ (0 .. $#l) { # go through the garden
            if ($j == 0 and $l[$_] =~ /^(.*?)\.\Q$m[$j]\E\./) { # this matches the top part of the weed. \Q and \E make it so the weed isn't intepreted as a regex. Capture the number of dots in front of it so we know where it is
                ++$j;
                $l = '.' x length($1); # this is how many dots we have
            }
            elsif ($j < @m and $l[$_] =~ /^$l\.\Q$m[$j]\E\./) { # capture the next line
                ++$j;
            }
            elsif ($j > 0) { # if we didn't match we have to reset
                $l[$_ - 1] =~ s[.\Q$m[$j - 1]\E.][' ' . $m[$j - 1] =~ s/\./ /rg . ' ';]e; # this line replaces the dots next to the weed and in the weed with spaces
                # to mark it since it didn't work but the top part matches
                # that way when we repeat we go to the next weed
                ($j, $g) = (0, 0);
            }
            if ($j == @m) { # the whole weed has been matched
                $k = $j;
                for ($f = $_; $f > $_ - $j; --$f) { # remove the weed backwards line by line
                    --$k;
                    $o = '.' x length($m[$k]);
                    $l[$f] =~ s/^($l)\.\Q$m[$k]\E\./$1.$o./;
                }
                ($g, $j) = (0, 0);
                ++$q;
            }
        }
        if ($g) {
            --$i; # all the weeds of this type are gone
        }
    }
    $t = join("\n", @l) . "\n"; # join the garden lines back together
    $t =~ s/ /./g; # changes spaces to dots
    $p = $z * $q; # calculate cost
    $u += $p; # add to sum
    $y .= "$q $h at $z costs $p\n"; #get message
}

```

**Feel free to suggest improvements!**

# Answer
> 0 votes
# Python 3, 459 bytes

```
    from re import*
E=input()
W,H,C=map(int,E[0].split())
B,T,O='\n'.join(E[~H:]),0,''
for L in E[1:~H]:
 w,h,s,n,c=L.split();w,h,c=map(int,(w,h,c));r,t='.'*(w+2),0;a=[r]+['.%s.'%s[i:i+w]for i in range(0,w*h,w)]+[r]
 for L in['(%s)'%'\\n'.join('.{%d})%s(.*'%(i,escape(b))for b in a)for i in range(W)]:t+=len(findall(L,B));B=sub(L,r.join('\\%d'%b for b in range(1,h+4)),B,MULTILINE)
 O+='%d %s at %d costs %d\n'%(t,n,c,t*c);T+=t*c
print(B+O+'total cost',T)

```

Assumes the input will be given as a list of strings.

---
Tags: code-golf
---


title: Lípínguapua dopo Pêpê

text:
# Question
Title: Lípínguapua dopo Pêpê
Língua do Pê, or P Language, is a language game spoken in Brazil and Portugal with Portuguese. It is also known in other languages, such as Dutch and Afrikaans. (Wikipedia)

There are some dialects in this language game. The different languages the game is played with even have their own unique dialects. Some people are fluent in speaking P Language and the best can even translate any text to their preferred dialect on the spot!

# P Language

In this challenge, we will use the *Double Talk* dialect.

To translate text into P Language, any sequence of vowels in the text is appended with a single `p` character followed by a copy of the sequence of vowels.

# Challenge

Write a function or program that accepts a string as input and outputs its translation in P Language.

* The input consists only of printable ASCII characters.
* The output consists only of the translated input and optionally a trailing newline.
* Vowels are any of the following characters `aeiouyAEIOUY`.
* A sequence of vowels is delimited by any other character. The string `"Aa aa-aa"` has three vowel sequences.
* Leading and trailing whitespace may optionally be omitted from the translated output string.

# Examples

```
""                              =>   ""
"Lingua do Pe"                  =>   "Lipinguapua dopo Pepe"
"Hello world!"                  =>   "Hepellopo woporld!"
"Aa aa-aa"                      =>   "AapAa aapaa-aapaa"
"This should be easy, right?"   =>   "Thipis shoupould bepe eapeasypy, ripight?"
"WHAT ABOUT CAPS?"              =>   "WHApAT ApABOUpOUT CApAPS?"
"   Hi "                        =>   "   Hipi " or "Hipi"

```

The double quotes character `"` is used to delimit the input and output strings in the examples but obviously this character may also appear in any valid input string.

# Answer
> 9 votes
# JavaScript (ES6), 35 bytes

```
s=>s.replace(/[aeiouy]+/gi,'$&p$&')

```

Try it online!

Where the special replacement pattern `$&` means *matched substring*.

# Answer
> 9 votes
# Sed, ~~30~~, ~~25~~, ~~21~~, 19 Bytes

-5 Bytes Thanks to Arnauld!
-4 Bytes Thanks to Shaggy!
-2 Bytes Thanks to Leo Tenenbaum!

```
s/[aeiouy]\+/&p&/gi

```

Try it Online!

# Answer
> 7 votes
# Japt, 10 bytes

```
r"%y+"_+ip

```

Try it

```
r"%y+"_+ip     :Implicit input of string
r              :Replace
 "%y+"         :RegEx /[aeiouy]+/gi
      _        :Pass each match through a function
       +       :  Append a copy of the match
        ip     :  Prepended with "p"

```

# Answer
> 6 votes
# Java 8, 40 bytes

```
s->s.replaceAll("(?i)[aeiouy]+","$0p$0")

```

Try it online.

**Explanation:**

```
s->                              // Method with String as both parameter and return-type
  s.replaceAll("(?i)[aeiouy]+",  //  Replace the regex matches
               "$0p$0")          //  With this replacement

```

*Regex explanation:*

```
(?i)[aeiouy]+                    // MATCH:
(?i)                             //  Enable case insensitivity
            +                    //  Match one or more
    [aeiouy]                     //  Adjacent vowel characters

$0p$0                            // REPLACEMENT:
$0                               //  The entire match (the vowel 'sequence')
  p                              //  Appended with a literal "p"
   $0                            //  Appended with the entire match again

```

# Answer
> 4 votes
# Perl 5 `-p`, 20 bytes

```
s/[aeiouy]+/$&p$&/gi

```

Try it online!

# Answer
> 3 votes
# Python 3, 55 bytes

```
lambda s:re.sub('([aeiouy]+)',r'\1p\1',s,0,2)
import re

```

Try it online!

---

Sans regex:

# Python 3, 101 bytes

```
def f(s,q=''):i=s[:1];t=i in{*'aeiouyAEIOUY'};return(q+(q!='')*'p'+q+i)*0**t+(s and f(s[1:],(q+i)*t))

```

Try it online!

Python 3.8 (pre-release): 99 bytes

## Explanation

Recursive function, accepting a string `s` and an optional argument `q`. If the first character of `s` (`i`) is a vowel, it is stored in the queue `q`. If not, a string is returned which is composed of `q`, the letter `'p'`, `q` again, the character `i` and the result of the recursive function with the first character of the string stripped off. Recursion stops when the function encounters an empty string `s`.

# Answer
> 3 votes
# 05AB1E, ~~22~~ 20 bytes

```
.γžÁyå}vyžÁyнåi'py}J

```

05AB1E doesn't have any regexes unfortunately.
I don't really like the duplicated `žÁyнå`, but I'm currently a bit too busy to look for alternatives..

-2 bytes thanks to *@Grimy* for showing me a constant I didn't even knew existed (and was missing from the Wiki page.. \>.\>)

Try it online or verify all test cases.

**Explanation:**

```
.γ               # Group the characters in the (implicit) input-string by:
  žÁ             #  Push vowels builtin: "aeiouyAEIOUY"
    yå           #  And check if the current character is in this string
 }v              # After grouping: loop over each group `y`:
   y             #  Push group `y`
    žÁyнåi   }   #  If the first character of the group is a vowel:
          'p    '#   Push a "p"
            y    #   And push group `y` again
              J  #  Join everything on the stack together to a single string
                 # (after the loop, implicitly output the result)

```

# Answer
> 2 votes
# Retina 0.8.2, 17 bytes

```
i`[aeiouy]+
$&p$&

```

Try it online! Link includes test cases. Explanation: Trivial regexp approach; the `i` flag turns on case insensitivity (Retina already defaults to a global match).

# Answer
> 1 votes
# Jelly, 20 bytes

```
Żṁe€ØyŒg$$,j”pƊ€ÐeẎḊ

```

Try it online!

# Answer
> 1 votes
# Red, 92 bytes

```
func[s][v: charset"aeiouyAEIOUY"parse s[any[to v copy t any v insert(rejoin["p"t])| skip]]s]

```

Try it online!

Of course Red's `Parse` is much more verbose than `regex`.

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 97 bytes

```
	I =INPUT
S	I ARB . L SPAN('AEIOUYaeiouy') . V REM . I	:F(O)
	O =O L V 'p' V	:(S)
O	OUTPUT =O
END

```

Try it online!

Vowel clusters match `SPAN('AEIOUYaeiouy')`.

# Answer
> 1 votes
# Stax, 17 bytes

```
àº`≈Zö=q╦ⁿ↔èblTï÷

```

Run and debug it at staxlang.xyz!

### Unpacked (20 bytes) and explanation:

```
Vv'y+c^+:}'++{'pnL}R
                   R    Regex replace using
                        Pattern:
Vv'y+                     Push "aeiou", push "y", and concatenate
     c^+                  Copy, convert copy to all caps, and concatenate
        :}                Enclose in []
          '++             Push "+" and concatenate
                        And replacement:
             {    }       Block:
              'p            Push "p"
                n           Copy second item (matching substring) to top
                 L          Listify
                          Implicit concatenate
                        Implicit print

```

No case-insensitive regular expressions in Stax, and the vowel builtins don't include Y. The documentation won't tell you about using a block as a replacement, but it's a working feature nevertheless.

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


title: Residue Number System

text:
# Question
Title: Residue Number System
In the vein of large number challenges I thought this one might be interesting.

In this challenge, we will be using the Residue Number System (RNS) to perform addition, subtraction, and multiplication on large integers.

**What is the RNS**

The RNS is one of many ways that people have developed to identify integers. In this system, numbers are represented by a sequence of residues (which are the results after a modulus operation (i.e. the remainder after integer division)). In this system, each integer has many representations. To keep things simple, we are going to limit things so that each integer is uniquely represented. I think it is easier to describe what is happening with a concrete example.

Let us look at the first three prime numbers: 2, 3, 5. In the RNS system, we can use these three numbers to *uniquely* represent any number that is less than 2\*3\*5 = 30 using residues. Take 21:

21 is less than 30, so we can represent it using the results after modding by 2, 3, and 5. (i.e. the remainder after integer dividing by 2, 3, and 5)

We would identify 21 with the following sequence of integers:

21 ~ { 21 mod 2, 21 mod 3, 21 mod 5 } = {1, 0, 1}

And so in our RNS system, instead of "21", we would use {1,0,1}.

In general **given an integer *n*, we represent *n* as { *n* mod 2, ..., *n* mod *p\_k* } where *p\_k* is the smallest prime such that *n* is less than the product of all primes less than or equal to *p\_k*.**

Another example, say we have 3412. We need to use 2,3,5,7,11,13 here because `2*3*5*7*11*13=30030` whereas, `2*3*5*7*11=2310` which is too small.

3412 ~ { 3412 mod 2, 3412 mod 3, 3412, mod 5, ... , 3412 mod 13 } = { 0, 1, 2, 3, 2, 6 }

You notice that using this system we can represent very large numbers relatively painlessly. Using {1, 2, 3, 4, 5, 6, 7, 8, ... } residues, we can represent numbers up to {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} respectively. ( Here is the series )

**Our task**

We will be using these residues to perform +, -, and * on large numbers. I will describe these processes below. For now here are the input and output specs.

**Input**

You will be given two (potentially very large) numbers via a stdin or function argument. They will be given as strings of base 10 digits.

For the purposes of outlining the problem further, we call the first input `n` and the second `m`. **Assume n \> m \>= 0**.

You will also be given `+` or `-` or `*` to indicate the operation to perform.

**Output**

Let *x* be an integer. We will use \[*x*\] to refer to the RNS representation described above of *x*.

You are to output `[n] <operator> [m] = [result]`

**How to perform the operations in RNS**

These operations are relatively simple. Given two numbers in RNS notation, to add, subtract, or multiply them, simply perform the given operations component-wise and then take the modulus.

i.e.

{ 1, 2, 3 } + { 1, 1, 4 } = { (1+1) mod 2, (2+1) mod 3, (3+4) mod 5 } = {0, 0, 2}

Note that if the number of residues used to represent two different numbers are not the same, when performing operations, you will need to extend the "shorter" number so that it has the same number of residues. This follows the same process. See the test cases for an example.

The same goes if the result requires more residues than either input. Then both inputs need to be "extended".

**Important Details**

* We will be dealing with big numbers here, but not arbitrarily large. **We will be responsible for numbers up to the product of the first 100 primes** (see below). To this end, **you are given the first 100 primes for free (no byte cost)**. You may stick them in an array called `p` or something idiomatic to your language and then subtract the number of bytes used to initiate this array from your final total. This of course means that they may be hard-coded or you may use a built-in to generate them.
* If for someone reason this is the default integer representation used in your language. That is fine.
* You may not use any Arbitrary Precision Integer type unless it is the default of your language. If it is the default, you may not use it to store integers that would not typically fit in 64 bits.
* To be clear, each integer will always be represented with the fewest residues possible. This goes for both input and output.
* I think the other specs should prevent this, but to be redundant: you may not perform the given operation on the inputs and then and then change everything to RNS and then output. You must change the inputs to RNS and then perform the operations to produce the output.

**Test Cases**

1. Input:

```
n = 10
m = 4
+

```

Output:

```
{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }

```

Explanation:

First, change each number to its RNS representation as described above:

`10 ~ {0,1,0}` and `4 ~ {0,1}`. Notice that when we want to do component-wise addition, that `10` has more components than `4`. Therefore we must "extend" the shorter number. So we will briefly write `4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}`. Now we proceed with addition and then take the modulus.

2. Input

```
n=28
m=18
+
```

Output:

```
 [ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]
```
3. Input (me mashing my face on the keyboard)

```
n=1231725471982371298419823012819231982571923
m=1288488183
*
```

Output (broken onto separate lines for readability):

```
[1, 2, 3, 6, 2, 10, 2, 1, 12, 16, 7, 15, 34, 29, 31, 5, 55, 32, 66, 61, 3, 76, 52, 14, 65, 44, 99, 57 ]
*
[1, 0, 3, 3, 4, 8, 9, 10, 8, 0 ]
=
[1, 0, 4, 4, 8, 2, 1, 10, 4, 0, 17, 7, 27, 21, 44, 51, 56, 9, 6, 9, 12, 0, 52, 36, 43, 68, 99, 24, 96, 39, 96, 66, 125]

```

`n` requires 28 primes. `m` requires 10. `n*m` requires 33.

4. Input

```
n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-
```

Output:

```
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 509]
-
[0, 2, 1, 6, 1, 12, 11, 18, 14, 28, 21, 36, 37, 42, 16, 52, 41, 60, 16, 70, 49, 78, 80, 88, 49, 100, 13, 106, 4, 112, 68, 130, 36, 138, 37, 150, 0, 162, 8, 172, 163, 180, 18, 192, 129, 198, 135, 222, 78, 228, 90, 238, 57, 250, 36, 262, 87, 270, 206, 280, 193, 292, 253, 310, 224, 316, 57, 336, 48, 348]
=
[0, 1, 4, 1, 10, 1, 6, 1, 9, 1, 10, 1, 4, 1, 31, 1, 18, 1, 51, 1, 24, 1, 3, 1, 48, 1, 90, 1, 105, 1, 59, 1, 101, 1, 112, 1, 0, 1, 159, 1, 16, 1, 173, 1, 68, 1, 76, 1, 149, 1, 143, 1, 184, 1, 221, 1, 182, 1, 71, 1, 90, 1, 54, 1, 89, 1, 274, 1, 299, 1, 266, 1, 228, 1, 340, 1, 170, 1, 107, 1, 340, 1, 88, 1, 157, 1, 143, 1, 22, 1, 22, 1, 58, 1, 296, 1, 371, 1, 140]
```

`n` uses 100 primes. `m` uses 70 primes. `n-m` uses 99 primes.

*I checked these using the `ChineseRem` built-in implementation of the Chinese Remainder theorem on GAP (which basically takes RNS numbers and changes them to base 10 integers). I believe they are correct. If something seems fishy, please let me know.*

---

For those who care, the product of the first 100 primes is:

```
471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090
```

This number is 1 larger than the maximal number we can represent using the given system (and 100 prime limitation).

Somewhat related

# Answer
# GAP

*Some Background:* I will admit that when I created this question, so many months ago, I did not have a method for solving the hard part of this question: determining the correct number of primes to use. We have a lot of very intelligent people on this site, and I really expected that someone would figure out a way to do it fairly quickly. However, as this did not happen, I wasn't even sure that it was truly possible to solve this problem. So, I had to take the time to devise a method. I believe that what I have done does not break any of the rules in this challenge, of course I would love this to be fact checked.

I also slightly regret the choice of because the solutions are slightly more in depth than would usually fit the tag format. Having said this, to follow site rules, there is a "golfed" version of my solution at the bottom of this post.

---

**Code**

```
### The first 100 primes;
primes := Primes{[1..100]};

### In many of the functions below, the 'string' variable is a string of digits
###

### Returns the 'index' digit of 'string' as an integer
GetValueAsInt := function(string, index)
    return IntChar(string[index]) - 48;
end;

### Used in the 'modulus' function. See that comment for more information.
### Calculates the contribution to the modulus of a digit 'digit' in the 10^power place.
### 'integer' is the modulus
digit_contribution := function(digit, integer, power)
    local result, i;
    result := 1;
    for i in [0..power-1] do
        result := ( result * (10 mod integer) ) mod integer;
    od;
    result := (result * (digit mod integer) ) mod integer;
    return result;
end;

### This modulus function is used to calculate the modulus of large numbers without storing them
##### as large numbers.
### It does so by breaking them into digits, and calculating the contribution of each digit.
### e.g. 1234 mod 5 = (1000 mod 5)(1 mod 5) + (200 mod 5)(2 mod 5) + (10 mod 5)(3 mod 5) + (4 mod 5)
### It actually mods after every calculation to ensure that we never get a number larger
##### than the modulus ('integer') squared, which will never be even close to 10^64-1
modulus := function(string, integer)
    local i, result, digit, len;
    len := Length(string);
    result := 0;
    for i in [1..len] do
        digit :=  IntChar(string[i]) -48;
        result := ( result + digit_contribution(digit, integer, len-i) )  mod integer;
    od;
    return result;
end;

### This returns the product of the first i-1 primes (mod j). It must not (and does not)
##### ever store an integer larger than 2^64-1
phi_i := function(i,j)
    local index, result;
    result := 1;
    for index in [1..i-1] do
        result := ( result * primes[index] ) mod primes[j];
    od;
    return result;
end;

### Calculates the first residues of 'string' mod the first 100 primes
get_residues := function(string)
    local p, result;
    result := [];
    for p in primes do
        Add( result, modulus(string, p) );
    od;
    return result;
end;

### Gets the ith element in the partial_chinese array, given the previous elements
### See the explanation section and partial_chinese function for more info
get_partial_i := function( i, residues, previous_array )
    local index, result;
    result := residues[i];
    for index in [1..Length(previous_array)] do
        result := ( result - previous_array[index]*phi_i(index,i) ) mod primes[i];
    od;
    result := ( result / phi_i(i,i) ) mod primes[i];
    return result;
end;

### returns an array such that the sum of prod_primes(i)*array[i] is equal to the integer value
##### that is represented by the residues. (It basically just does the CRT without
##### actually summing everything.) prod_primes(i) is the product of the first i-1 primes
### See the explanation for a bit more info
### This is what allows us to determine the minimal number of primes to represent a RNS number
partial_chinese := function( string )
    local array, i, residues;
    residues := get_residues(string);
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### Same as partial_chinese but takes input in a different form.
partial_chinese_from_residues := function(residues)
    local array, i;
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### gives you the number of primes needed to represent an integer. Basically asks how
##### many trailing zeros there are in the chinese array.
get_size := function(string)
    local array, i, len, result;
    array := partial_chinese(string);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### Same as above but with different input format
get_size_from_residues := function(residues)
    local array, i, len, result;
    array := partial_chinese_from_residues(residues);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### the actual function. inputs are all strings
f := function(in1, in2, opperation)
    local residues_1, residues_2, residues_result, i;
    residues_1 := get_residues(in1);
    residues_2 := get_residues(in2);
    residues_result := [];
    if opperation = "+" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] + residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "*" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] * residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "-" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] - residues_2[i] ) mod primes[i]);
        od;
    fi;
    Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );
end;

```

**Explanation:**

To start off, we calculate all the 100 of the residues for both inputs. We do this with the `modulus` function in the code. I tried to be careful so that we use the built-in `mod` function after every step. This ensures that we never have a number that is larger than `540^2`, which is 1 less than the 100th prime squared.

After we have all the residues, we can perform the given operation and `mod` each entry again. Now we have a unique designator for the result, but we need to determine the minimal number of entries that we have to use to represent the result and each of the inputs.

Figuring out how many residues we actually need is by far the hardest part of this problem. To determine this, we perform most of the steps of the Chinese Remainder Theorem (CRT). However, we obviously have to make modifications so that we don't end up with numbers that are too large.

Let `prod(i)` be the sum of the first `i-1` primes. For example,

```
prod(1) = 1
prod(2) = 2
prod(3) = 6
prod(4) = 30
etc

```

Let `X` be an integer. Let `{r_i}` be the residues of `X`, that is

```
r_i = X mod p_i

```

Where `p_i` is the `i`th prime. This is for `1<i<=100` in our case.

Now we are going to use the CRT to find a sequence `{u_i}` such that the sum over `i` of `prod(i) * u_i` is equal to `X`. Note that each `u_i` is also technically a residue, as `u_i < p_i`. Furthermore, if `X < prod(i)` then `u_i = 0`. This is of critical importance. It means that by examining trailing zeros, we can determine how many of the residues `r_i` we actually need to represent `X` in the RNS.

If you care to examine some sequences of `u_i`, the `partial_chinese` function returns the `u_i` sequence.

By messing around with the CRT, I was able to find a recursive formula for the `u_i` values, solving the issue of determining how many residues we need.

The formula is:

```
u_i = [ r_i - SUM ] / prod(i)       (mod p_i)

```

Where `SUM` is the sum over `j in [1,i)` of `u_j * prod(i)`.

Of course, `prod(i)` cannot actually be calculated in some cases because it is too large. For this purpose, I used the `phi_i` function. This function returns `prod(j) (mod p_i)`. It `mod`s at every step, so we never actually calculate anything that is too large.

If you are curious where this formula comes from, I would recommend working a couple of CRT examples, which can be found on the wikipedia page.

Finally, for each input as well as our output, we calculate the `u_i` sequence and then determine the trailing zeros. Then we throw out that many `r_i` from the end of the residue sequences.

---

**"Golfed" Code, 2621 bytes**

```
primes:=Primes{[1..100]};GetValueAsInt:=function(string,index)return IntChar(string[index])-48;end;digit_contribution := function(digit, integer, power)local result, i;result:=1;for i in [0..power-1] do result := ( result * (10 mod integer) ) mod integer;od;result:=(result*(digit mod integer) ) mod integer;return result;end;modulus:=function(string, integer)local i,result,digit,len;len:=Length(string);result:=0;for i in [1..len] do digit:= IntChar(string[i])-48;result:=(result+digit_contribution(digit,integer,len-i)) mod integer;od;return result;end;phi_i:=function(i,j)local index,result;result:=1;for index in [1..i-1] do result:=(result*primes[index] ) mod primes[j];od;return result;end;get_residues:=function(string) local p,result;result:=[];for p in primes do Add(result,modulus(string,p));od;return result;end;get_partial_i:=function(i,residues,previous_array)local index,result;result:=residues[i];for index in [1..Length(previous_array)] do result:=(result-previous_array[index]*phi_i(index,i) ) mod primes[i];od;result:=(result/phi_i(i,i)) mod primes[i];return result;end;partial_chinese:=function(string)local array,i,residues;residues:=get_residues(string);array:=[];for i in [1 .. Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;partial_chinese_from_residues:=function(residues)local array,i;array:=[];for i in [1..Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;get_size:=function(string)local array,i,len,result;array:=partial_chinese(string);len:=Length(array);for i in [0..len-1] do if not (array[len-i] = 0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;get_size_from_residues:=function(residues)local array,i,len,result;array:=partial_chinese_from_residues(residues);len:=Length(array);for i in [0..len-1] do if not (array[len-i]=0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;f:=function(in1,in2,opperation)local residues_1,residues_2,residues_result,i;residues_1:=get_residues(in1);residues_2:=get_residues(in2);residues_result:=[];if opperation = "+" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]+residues_2[i] ) mod primes[i]);od;elif opperation = "*" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]*residues_2[i])mod primes[i]);od;elif opperation = "-" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]-residues_2[i]) mod primes[i]);od;fi;Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );end;

```
> 6 votes

# Answer
# Mathematica, not golfed

```
rns[d_,l_]:=Table[Reap[
    FoldPairList[Sow@QuotientRemainder[10#+#2,Prime@i]&,0,d]
  ][[2,1,-1,2]],{i,l}];
plus[a_,b_]:=Mod[a+b,Prime@Range@Length@a];
subtract[a_,b_]:=Mod[a-b,Prime@Range@Length@a];
times[a_,b_]:=Mod[a b,Prime@Range@Length@a];
mag[f_]:=LengthWhile[FoldList[#/#2&,f,Prime@Range@100],#>1.1&];
ext[m_,n_,i_]:=Fold[Mod[1##,Prime@i]&,m,Prime@Range@n];
multi[e_,p_,t_]:=Tr@Position[Mod[e Range@p,p],p-t];
appx[d_] := N@FromDigits[{d~Take~UpTo[6], Length@d}]

```
* Function `rns[d_,l_]` converts a base-10 integer `d` into a RNS integer of length `l`.
* Function `plus` / `times` / `subtract` add / multiply / subtract one RNS integer to / from another, both of which are of the same length.
* Function `mag[f_]` estimates the approximate magnitude of the floating point number `f` in terms of the lower bound of the length of its RNS representation.
* Function `ext[m_,n_,i_]` finds out the remainder from division of the product of `m` and `Prime[Range@n]` by `Prime[i]`.
* Function `multi[e_,p_,t_]` gives the smallest multiplier `m` satisfying that `Divisible[m*e+t,p]`
* Function `appx[d_]` take the first `6` digits of a decimal integer and gives its approximate floating point value.

---

With the help of functions above, now we are able to solve a tricky problem - **to determine the length of the result**.

First, I have to clarify that it is not an easy task to determine the RNS length of an integer. For small integers, we can compare them directly with the product of primes. But for very large integers, since it is forbidden to calculate the product of primes infinitely accurate, such comparison no longer works.

For example, given that the product of prime `1` to `30` is `3.16*10^46`, the RNS length of integers around `3.16*10^46` can possibly be `29` or `30`. The function `mag` will give `29` as a reference for these integers, showing that both `29` and `30` are possible.

Once knowing the magnitude, we simply represent the integer according to that magnitude directly, hoping to calculate its true length. The trick here is to add some new numbers to the original number and modify its RNS representation, until the representation is all zero.

For example, `mag[211.]` is `4`, and its length `4` representation is `{1, 1, 1, 1}`.

```
step 1:   {1,1,1,1} -> {0,2,2,2}  by adding  (1) * 1 = 1
step 2:   {0,2,2,2} -> {0,0,1,6}  by adding  (2) * 2 = 4
step 3:   {0,0,1,6} -> {0,0,0,2}  by adding  (2*3) * 4 = 24
step 4:   {0,0,0,2} -> {0,0,0,0}  by adding  (2*3*5) * 6 = 180
step 5:   calculate 211 + (1 + 4 + 24 + 180) ~ 420

```

By adding some number, we increase `211` to the smallest number that is divisible by `210` (`2*3*5*7`). And now we conclude that the original number is greater than `210`, since `420` equals "approximately" two times of `210`. It is not difficult to imagine that if we start from `209`, the final number is "approximately" `210`.

Function `length[f_,n_]` takes the floating point value `f` to estimate the magnitude, and correct it base on its RNS representation `n`.

```
length[f_,n_]:=With[{g=mag@f},
    g+If[#==0,1,Round[(#+f)/Times@@Prime@Range@g]-1]&[
      FoldList[Times,1.,Prime[Range[g-1]]].
      FoldPairList[
        Block[{i=#2,m},
          {m=multi[ext[1,i-1,i],Prime@i,Part@##],rnsPlus[#,ext[m,i-1,#]&/@Range[g]]}
        ]&,n,Range[g]]]]

```

---

Function `rnsOperation[a_,b_,op_,rnsop_]` gives `rnsop[a,b]` and `op` is corresponding normal operations used to get approximate results based on floating point values.

```
rnsOperation[a_,b_,op_,rnsop_]:=Block[{c=op[appx@a,appx@b],m},
    m=mag[c];m=length[c,rnsop[rns[a,m],rns[b,m]]];rnsop[rns[a,m],rns[b,m]]]

```

*Example*

```
rnsOperation[
    IntegerDigits@1231725471982371298419823012819231982571923,
    IntegerDigits@1288488183,
    Times, times]
(* {1,0,4,4,8,2,1,10,4,0,17,7,27,21,44,51,56,9,6,9,12,0,52,36,43,68,99,24,96,39,96,66,125} *)

```
> 2 votes

# Answer
# Python 3, 435 bytes

This challenge has been on my bucket list for a while, but it's only recently that: a) I put time and attention into actually attempting an answer; and b) actually tested my idea to calculate the size of the numbers (and so the number of primes by comparing it to the size of the primorials) using some unholy combination of logarithms and the Chinese Remainder Theorem. Unfortunately, working with logarithms while trying to determine the number of primes that, for example, `large_primorial + 3` requires, meant that I was having to find ways to work around floating-point problems.

And so, this is a port of Liam's answer.

Try it online!

```
from functools import reduce as R
G=range
d=lambda s:[R(lambda z,c:(z*10+int(c))%q,s,0)for q in p]
h=lambda j,i:R(lambda z,q:z*q%p[i],p[:j],1)
def s(r):
 a=[];z=99
 for i in G(100):
  P=p[i];u=r[i]
  for j in G(len(a)):u=(u-a[j]*h(j,i))%P
  for k in G(1,P):
   if h(i,i)*k%P<2:break
  a+=u*k%P,
 while(a[z]<1)*z:z-=1
 return r[:z+1]
def f(a,b,n):u=d(a);v=d(b);print(s(u),n,s(v),'=',s([eval(str(u[i])+n+str(v[i]))%p[i]for i in G(100)]))

```

# Explanation

While trying to port Liam's answer, I personally found some of the explanation given was confusingly worded, so this is my attempt at explaining his algorithm.

First, we get the residues of `n` and `m`.

```
res1 = get_residues(n)
res2 = get_residues(m)

```

This involves turning all the digits of the input strings and turning them into numbers modulo each of our primes, e.g. for 28, we would have `[(20 + 8) mod 2, (20 + 8) mod 3, (20 + 8) mod 5, etc]`

```
def get_residues(string):
    result = []
    for p in primes:
        result.append(reduce(lambda z, c:(z*10+int(c)) % p, string, 0))

```

Then we add, multiply, or subtract the residues pairwise using `eval()`

```
result = []
for i in range(len(primes)):
    result.append((eval(str(res1[i]) + op + str(res2[i])) % primes[i])

```

Then we get the sizes of our residues, i.e. the minimum number of primes we need.

```
size1 = get_size(res1)
size2 = get_size(res2)
size3 = get_size(result)

```

Getting the sizes is the trickiest and most code-intensive part. We use the `partial_chinese` function, which gets us our sequence of `u_i` to determine the size with. More on `u_i` in a moment.

```
def get_size(residues):
    array = partial_chinese(residues)
    size = len(residues)-1
    while array[size] == 0 and size:
        size -= 1
    return size+1  # to prevent off-by-one errors from 0-indexing

```

The sequence `u_i` is calculated by taking each residue `r_i`, subtracting the sum `u_j * primorial(j) for j in [1, i)`, and then `dividing` by `primorial(i)`, all modulo `primes[i]`. That is, `u_i = (r_i - SUM) / primorial(i)`. More on our primorial and division functions in a moment.

```
def partial_chinese(residues):
    array = []
    for i in range(len(primes)):
        array.append(get_partial_i(i, residues, array))
    return array

def get_partial_i(i, residues, previous_array):
    result = residues[i]
    for j in range(len(previous_array)):
        result = (result - previous_array[j] * phi_i(j, i)) % primes[i]
    result = result * inverse(phi_i(i, i), primes[i]) % primes[i]
    return result

```

`phi_i(j, i)` calculates `primorial(j) mod primes[i]`. Division modulo any prime `p` is easily implemented by checking for multiplicative inverses manually, as we can be sure that any possible `u_i` is `0 <= u_i < p` is guaranteed to be coprime to p and so is guaranteed a multiplicative inverse.

```
def phi_i(j, i):
    return reduce(lambda z, q: z * q % primes[i], primes[:j], 1)

def inverse(n, p):
    for i in range(1, p):
        if n * i % p == 1:
            return i

```

With all that done, we print our string and we're done.

```
print(res1[:size1], op, res2[:size2], "=", result[:size3])

```

# What's next

This was fun to implement. I still want to see if I can use logarithms in some way in another answer. And I'd like to implement this code or something like in a functional golfing language, like APL or Jelly. Any and all golfing suggestions and corrections are welcome!
> 2 votes

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


title: Elimination ordering

text:
# Question
Title: Elimination ordering
Your task is to remove smallest amount elements from a list, so the most elements are on their corresponding place. The element is on it's corresponding place, when it's value is equal to it's position.

Let's look at this example list:

```
1 5 3 2 5

```

This list has three elements on their corresponding place (1 on position 1, 5 on position 5, 3 on position 3).

## Input

The input is a sequence of decimals in any reasonable format. For example:

```
1 3 2 3 6

```

## Output

The output is a sequence of decimals in any reasonable format which contains, as its first element, the amount of elements removed from the input then the corresponding, 1-based element positions removed.

For example, for input given above, the (correct) output:

```
1 2

```

instructs us to remove one element, the one at index two (the first `3`), which will leave us with `1 2 3 6` which has three elements at their index positions.

This output would be incorrect:

```
2 2 5

```

Since although removing the two elements at indexes two and five would leave us with `1 2 3` which *also* has three elements at their index positions, we've removed more than the minimal necessary.

## More complicated example

```
1 2 3 3 4 5 6

```

In this case you can remove **either** of 3's, but not both (so `1 3` and `1 4` are both acceptable outputs).

```
1 3 2 3 4 5 6 7 8

```

In this case, if you would remove 3 on position 2, it would pass more elements, than if you would remove 3 on position 4 (so `1 4` is incorrect while `1 2` is correct).

```
1 3 2 3 5 6 7 8 9

```

Here removing 3 on position 2 is a mistake, because this actually makes the situation worse in obvious way (there are now less correctly placed elements than before). (the correct output is `0` since removing no elements is the best thing to do)

```
1 7 2 8 1 3 9

```

In this case we want to remove the three elements at positions 2, 4, and 5 (leaving us `1 2 3 9` for three in the correct location) so the correct output would be `3 2 4 5`)

## Rules

* This is code golf, so the shortest code wins!
* Loopholes are forbidden.
* Assume that input is valid, contains nothing more than digits and spaces, and the input numbers inside the string are decimals in range of 0 \<= n \<= 99.
* Please include a link to an online interpreter for your code.
* If anything is unclear, please let me down in the comments.

# Answer
> 1 votes
# Pyth, 20 bytes

```
lBhMh.Ms.eqktb.DQZyU

```

Try it online!

# Answer
> 1 votes
# Jelly, 18 bytes

```
JŒPṚœPF=J$SʋÞ⁸ṪL;$

```

**Try it online!**

### How?

```
JŒPṚœPF=J$SʋÞ⁸ṪL;$ - Link: list of numbers, A
J                  - range of length (A) [1,2,3,...,len(A)]
 ŒP                - all partitions      [[1],[2],...,[1,2],[1,3],...,[2,3],...]
   Ṛ               - reversed (so longest to shortest)
            Þ      - sort (the p's in all partitions) by:
             ⁸     -   (using the chain's left argument, A, as the right argument)
           ʋ       -   last four links as a dyad, i.e. f(p, A):
    œP             -     partition A at the indices in p
      F            -     flatten (to give result of dropping the values at indices in p)
         $         -     last two links as a monad:
        J          -       range of length (of the flatten result)
       =           -       equals? (vectorises)
          S        -     sum
              Ṫ    - tail (i.e. the shortest p which yields the maximal sum)
                 $ - last two links as a monad:
               L   -   length (of that result)
                ;  -   concatenate

```

---

An alternative for `=J$` is `ĖE€`

---
Tags: code-golf, array
---


# Question
Title: Shortest Longest Increasing Subsequence Code
The Challenge is to write the **shortest** implementation to find the Longest increasing subsequence .

**Example** : Let S be the sequence 1 5 7 1 8 4 3 5 \[length of S = 8 \]

* We have 1 sub-sequence of length 0 \[will consider it increasing\]
* 6 sub-sequences of length 1 {1,5,7,8,4,3}\[all of them are considered increasing\]
* (7\*8)/2 sub-sequences of length 2 \[but we will remove duplicates\], the increasing sub-seq are in strong black.
{**15,17**,11,**18,14,13,57**,51,**58**,54,53,55,71,**78**,74,73,75,84,83,85,43,**45,35**}

*\[note that we only interested in strictly-increasing sub-sequences\]*

\[you **can't change the order** of the elements inside the sequence , so there is no sub-sequence \[37\] in the example sequence\]

* We have increasing sub-sequences of length 4 which is 1578 , but there's no sub-sequence of length 5 , so we consider the length of the longest increasing sub-sequence = 4.

**Input**:

a1 a2 ... aN (The sequence)

all numbers are positive integers less than 103
N \<= 1000

**Output**:

One integer denoting the length of the longest increasing sub-sequence of the input sequence .

```
sample input(1)
1 2 4 2 5
sample output(1)
4

sample input(2)
1 5 7 1 8 4 3 5
sample output(2)
4

```

**Your code should run in a timely manner** please test your code on this case before submit it here (also the link contains my 290-byte c++11 solution )

*You can either take the input from a file/stdin or as a function parameter and you can either print the output to a file/stdout or just return the value if you write a function*

## Score Board

1. Dennis CJam - **22**
2. isaacg Pyth - **26**
3. Howard GolfScript - **35**
4. proud haskeller Haskell - **56**
5. Ray Python 3 - **66**
6. histocrat Ruby - **67**
7. DLeh C# - **92**
8. YosemiteMark Clojure - **94**
9. faubiguy Python 3 - **113**

# Answer
> 2 votes
# CJam, 22 bytes

```
1e3,q~{_2$<$0=(t}/$0=z

```

Try it online.

### Example

```
$ cjam subsequence.cjam <<< '[2 1]'; echo
1
$ cjam subsequence.cjam <<< '[1 9 2 4 3 5]'; echo
4

```

The program prints `57` for this test case after 0.25 seconds.

### How it works

I took the general idea from @Ray's answer.

```
1e3,    " Push the array [ 0 ... 999 ] (J).        ";
q~      " Read from STDIN and evaluate.            ";
{       " For each integer (I) of the input array: ";
  _2$<  " Push [ J[0] ... J[I - 1] ] (A).          ";
  $0=(  " Compute min(A) - 1.                      ";
  t     " Update J[I] with the value on the stack. ";
}/      "                                          ";
$0=     " Compute abs(min(J)).                     ";

```

# Answer
> 5 votes
# Python 3, 66

Note that all numbers are in range \[1, 999\], we can use an array `b` to maintain the longest subsequence length ending with each number. `b[x] = d` means that the longest subsequence ending with `x` has length `d`. For each number from the input, we update the array using `b[x] = max(b[:x]) + 1` and then we got the job done by taking `max(b)` finally.

The time complexity is ~~O(n)~~ **O(m n)**, where `m` is always 1000 and `n` is the number of input elements.

```
def f(a):
 b=[0]*1000
 for x in a:b[x]=max(b[:x])+1
 return max(b)

```

Wow, looks like already ungolfed :) You can test it using stdin/stdout by adding a line:

```
print(f(map(int,input().split())))

```

# Answer
> 3 votes
# Pyth, 26 29 33 39

```
J*]0^T3Fkyw=@JkheS:J0k)eSJ

```

Port of @ray's solution. Passes official tests. Now uses space-separated STDIN input, not function call.

Run as follows:

```
./pyth.py -c "J*]0^T3Fkyw=@JkheS:J0k)eSJ" <<< "1 5 7 2 8 4 3 5"
4

```

Explanation:

```
J*]0^T3                 J = [0]*10^3
Fkyw                    For k in space_sep(input()):
=@Jk                    J[k]=
heS:J0k                 max(J[0:k])+1
)                       end for
eSJ                     max(J)

```

---

Time unlimited:

# Pyth, 18

```
L?eS,ytbhyf>Thbbb0

```

---

Technical note: I noticed a bug in my Pyth complier while writing this golf. `L` wasn't working. That's why there is a recent commit to the above git repository.

# Answer
> 3 votes
# Python - 113

```
a=[]
for i in map(int,input().split()):
 if not a or i>a[-1]:a+=[i]
 z=0
 while a[z]<i:z+=1
 a[z]=i
print(len(a))

```

# Answer
> 3 votes
# Haskell, ~~58~~ ~~57~~ 56 characters

```
(x:s)%v|v>x=x:s%v|0<1=v:s
_%v=[v]
l s=length$foldl(%)[]s

```

This uses an algorithm I saw once on the internet, but i can't find it. It takes an unnoticeable amount of time on the given test case on my computer with GHCi (probably would be even faster if it was compiled).

# Answer
> 3 votes
### Clojure, 94 characters

Using @Ray's approach of updating results in a 1000-item vector:

```
(defn g[s](apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s)))

```

Per request, with print statement (will print answer and return nil). Input should be a vector (g \[1 2 3\]) or a list (g '(1 2 3)):

```
(defn g[s](prn(apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s))))

```

# Answer
> 2 votes
### GolfScript, 35 characters

```
~]]){1${~2$<*)}%1+$-1>[\+]+}/$-1=0=

```

An implementation working as a complete program with input on STDIN (without the length number given). The implementation is reasonable fast, even for longer inputs (try here).

Examples:

```
> 1 5 7 1 8 4 3 5
4

> 5 1 9 9 1 5
2

```

# Answer
> 2 votes
# Ruby, 67

```
s=Hash.new{|s,a|f,*r=a
s[a]=f ?[1+s[r.select{|x|x>f}],s[r]].max: 0}

```

This runs in 30 seconds on the large input, does that count as a timely manner? :p

It's brute recursion, but with some memoization.

# Answer
> 2 votes
# Bash+coreutils, 131 bytes

This solution fails horribly on the **timely manner** requirement, and is not even particularly short, but I liked that this sort of thing is at least theoretically possible in shell script, so I'm posting anyway. This runs with an eternity-inducing time complexity of O(2^n).

```
s=${1//,/,:\},\{}
a=`eval echo "{$s,:}"`
for s in $a;{
b="$(tr , \\n<<<$s|grep -v :)"
sort -nC<<<"$b"&&wc -w<<<$b
}|sort -nr|sed 1q

```

Input is a comma separated list passed as a single command-line argument:

```
$ time ./slisc.sh 1,5,7,1,8,4,3,5
4

real    0m1.240s
user    0m0.518s
sys 0m0.689s
$

```

Brace expansion is used to build the list of all possible subsequences.

* The first line replaces commas with `,:},{`, which produces a string like `1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5`
* The second line completes this string with braces, commas and semicolons to give this `{1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5,:}`. This is a valid bash brace expansion, which when `eval`ed with an `echo` produces this space-separated list `1,5,7,1,8,4,3,5 1,5,7,1,8,4,3,: 1,5,7,1,8,4,:,5 1,5,7,1,8,4,:,: ...`
* by default, bash splits strings with whitespace, so we loop over each element of this list:
    + commas are replaced with newlines, then lines containing colons are removed, giving newline-separated lists for each possible subsequence
    + we then `sort -C` to test for increasing order, and if so, use `wc -w` to print the length of the list
* the resulting list of list lengths is sorted in reverse and the first value printed to give the longest increasing subsequence length.

# Answer
> 2 votes
### C#, ~~172~~ 92 chars

Nothing special, but I did it so I figured I might as well submit it.

```
int a(int[] j){int c=2,m=2,i=1;for(;++i<j.Length;){c=j[i]>j[i-1]?c+1:2;m=c>m?c:m;}return m;}

```

Thanks Armin and Bob for their improvements!

# Answer
> 2 votes
# Stax, 21 bytes

```
ë/NS7Γ╥╚┌{1╤╒¬è¶²╢╦┌☼

```

Run and debug it

This has two test cases, one of which is the 1000-element case. It runs that one in 24 seconds on my machine. It uses the classic dynamic programming approach for this type of problem.

# Answer
> 2 votes
# , 19 bytes

```
[:#]`I.`[} ::,~/@|.

```

Try it online!

Runs in *O(n log n)*, using a modified patience sort since only the length, not the actual subsequence, is needed.

## Explanation

```
[:#]`I.`[} ::,~/@|.  Input: array
                 |.  Reverse
               /     Reduce right-to-left
     I.                Find the index to insert while keeping it sorted
                       (uses binary search)
         }             Amend the current search array at that index with the next value
           ::          If error (when the index is not found)
             ,           Append the value at the end
 #                   Length of that array

```

# Answer
> 0 votes
## J 34

Note that I read standard input as well.

```
>./;+/@:*&.>(<*>.)/\&.><\.".1!:1]3

```

Without reading standard input, the meat is 26 characters.

```
>./;+/@:*&.>(<*>.)/\&.><\.

```

Just noticed mine runs slow for large input, oh well.

# Answer
> 0 votes
# C++ (gcc), 129 bytes

```
int f(int*a,int n){int l[n]{},i=n,j,m=0;for(;i--;m=l[i]>m?l[i]:m)for(j=n;--j>i;)if(a[i]<a[j]&&l[i]<l[j]+1)l[i]=l[j]+1;return++m;}

```

Try it online!

# Answer
> 0 votes
# C# (.NET Core), 155 bytes

Used an array to compute the longest increasing subsequence ending at each position in the input array (dynamic programming), then returned the largest value. For example, the computed array for input `[1,5,7,1,8,4,3,5]` would be `[1,2,3,1,4,2,2,3]`, and the largest value `4` is returned.

```
int b(int[]x){int l=x.Length,r=1,i=0,j,c;var a=new int[l];a[0]=1;while(++i<l)for(j=0;j<i;j++){c=x[j]<x[i]?a[j]+1:1;a[i]=a[i]<c?c:a[i];r=r<c?c:r;}return r;}

```

Try it online!

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

```
Length@LongestOrderedSequence[#,Less]&

```

Try it online!

There is of course a *Mathematica* built-in for finding longest ordered sequences. Its name is very long: it makes up more than half the solution, and I won't be surprised if someone out-golfs this solution.

---
Tags: code-golf
---