# Question
Title: Help, I can't bloody well memorize this number!
The Brits aren't exactly known for being good at memorizing stuff. That's why scientists need newspaper articles to find those who are, and that's why it shouldn't be a surprise that they forget more than a 1000 things per year, including phone numbers, addresses, birthdays and more. Now, it is your duty to help the Brits remember their numbers.

In a 2010 video by the BBC (from 0:32 to 1:10), a trick is explained on how to do just that:

First, the base-10 string of the number is partitioned into several smaller non-overlapping parts, which then individually fit into one of four categories (three in the video, including one residual category for this challenge). No part of the partition is allowed to start with a `0`, except individual digits (This makes the challenge fairer for languages that only work with numbers and not with strings). Each category then has an associated cost. Your goal is to find the partition of the string such that the total cost is minimal, and output that partition. The four categories are:

---

##### 1. Addition or multiplication:

Three or four digits in which the first two add or multiply to the third or, in case of a carry, the third and fourth digit.

Examples:

```
112   # 1 + 1 = 2
347   # 3 + 4 = 7
549   # 5 + 4 = 9
5510  # 5 + 5 = 10
606   # 6 + 0 = 6
9817  # 9 + 8 = 17
111   # 1 * 1 = 1
3412  # 3 * 4 = 12
5420  # 5 * 4 = 20
5525  # 5 * 5 = 25
600   # 6 * 0 = 0
9872  # 9 * 8 = 72

```

Cost:

* Addition without carry: `2`
* Addition with carry: `3`
* Multiplication without carry: `3`
* Multiplication with carry: `5`

##### 2. Relation to a year:

Four digits that form an year considered to contain an important date. For the sake of this challenge, this is every year in which a British monarch died.

Exhaustive list:

```
1714, 1727, 1760, 1820, 1830, 1837, 1901, 1910, 1936, 1952, 1972, 2022

```

Cost:

* 18th and 19th century: `4`
* 20th century: `2`
* 21st century: `1`

##### 3. Similarity to a symbol:

A sequence of numbers that look like a symbol. Since Unicode is too vast and symbols are ill-defined, we will instead use any sequence of four digits that is a British word if typed on a 7-segment display calculator that is then rotated 180°.

Exhaustive list (taken from this file, filtered by whether there is a C1-level Oxford Dictionary entry of the same exact name):

```
3215, 3507, 3573, 3705, 5507, 5508, 5537, 7105, 7108, 7718, 7735, 7738

```

Cost: `3`

##### 4. Residual digit

Any digit not part of such a pattern will be treated as a residual digit and be assigned a cost of `2`.

### Challenge

In this challenge, you will be given a non-negative number as input and will output the partition of the number such that it is as easy to remember as possible for a Brit, minimizing the total cost. If multiple equivalent partitions exit, you may choose arbitrarily.

You may take the input as a 64-bit (or wider) integer, a string containing the decimal representation or a list of decimal digits. You may output the partition as a list of numbers, or, if your language doesn't support lists, a Gödel-encoded list or similar. You may additionally output the cost, but this is neither required nor beneficial (I'd assume).

If your language has a builtin for generating optimal partitions for Brits to remember numbers, usage of it is not discouraged.

This is , so the shortest code (as measured in bytes) wins.

### Test cases

Note that the test case's outputs are only examples and you might output a different output with the same cost. Note that if you calculate a partition with a different cost, your solution is most likely faulty.

| Input | Output | Cost | Cost explanation | Explanation |
| --- | --- | --- | --- | --- |
| 1972 | \[1972\] | 2 = 2 | Monarch died 20th century | Death of Edward VIII |
| 19729 | \[1972, 9\] | 4 = 2 + 2 | Monarch died 20th century + Single digit | Death of Edward VIII followed by a 9 |
| 1972022 | \[1, 9, 7, 2022\] | 7 = 2 + 2 + 2 + 1 | Single digit x3 + Monarch died 21st century | Lone 1, 9 and 7 followed by the death of Elizabeth II |
| 92183721 | \[9218, 3721\] | 10 = 5 + 5 | Multiplication with carry x2 | 9 * 2 = 18, 3 * 7 = 21 |
| 123 | \[123\] | 2 = 2 | Addition without carry | 1 + 2 = 3 |
| 44812 | \[4, 4812\] | 5 = 2 + 3 | Single digit + Addition with carry | 4 followed by 4 + 8 = 12 |
| 48123 | \[4812, 3\] | 5 = 3 + 2 | Addition with carry + Single digit | 4 + 8 = 12 followed by 3 |
| 1820224610 | \[1, 8, 2022, 4610\] | 8 = 2 + 2 + 1 + 3 | Single digit x2 + Monarch died 21st century + Addition with carry | 1 and 8 followed by the death of Elizabeth II and 4 + 6 = 10 |
| 4312370550707 | \[4312, 3705, 5, 0, 707\] | 14 = 5 + 3 + 2 + 2 + 2 | Multiplication with carry + British word + Single digit x2 + Addition without carry | 4 * 3 = 12, then the word 'sole', a five, a zero and 7 + 0 = 7 |
| 54202243215 | \[5420, 224, 3215\] | 10 = 5 + 2 + 3 | Multiplication with carry + Addition without carry + British word | 5 * 4 = 20, 2 + 2 = 4, and the word 'size' |
| 171419012022 | \[1714, 1901, 2022\] | 7 = 4 + 2 + 1 | Monarch died 18th-19th century + Monarch died 20th century + Monarch died 21st century | The death of every female British monarch |
| 171450119010112022 | \[1714, 5, 0, 1, 1901, 0, 1, 1, 2022\] | 19 = 4 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 | Monarch died 18th-19th century + Single digit x3 + Monarch died 20th century + Single digit x3 + Monarch died 21st century | The death of every female British monarch, interrupted by 5, 0, 1 in the first and 0, 1, 1 in the second position |
| 99819918182022 | \[9981, 9918, 1, 8, 2022\] | 13 = 5 + 3 + 2 + 2 + 1 | Multiplication with carry + Addition with carry + Single digit x2 + Monarch died 21st century | 9 * 9 = 81, 9 + 9 = 18, lone 1 and 8 followed by the death of Elizabeth II |
| 1248163264128 | \[1, 248, 1, 6, 326, 4, 1, 2, 8\] | 20 = 2 + 3 + 2 + 2 + 3 + 2 + 2 + 2 + 2 | Single digit + Multiplication without carry + Single digit x2 + Multiplication without carry + Single digit x4 |  |
| 123512351235 | \[1, 235, 1, 235, 1, 235\] | 12 = 2 + 2 + 2 + 2 + 2 + 2 | Single digit + Addition without carry + Single digit + Addition without carry + Single digit + Addition without carry |  |
| 23550877187738 | \[2, 3, 5508, 7718, 7738\] | 13 = 2 + 2 + 3 + 3 + 3 | Single digit x2 + British word x3 | 2 and 3, 'boss', 'bill', 'bell' |
| 732133933917141760 | \[7321, 339, 339, 1714, 1760\] | 19 = 5 + 3 + 3 + 4 + 4 | Multiplication with carry + Multiplication without carry x2 + Monarch died 18th-19th century x2 |  |

### Computer-readable test cases without explanations

```
1972 -> [1972]
19729 -> [1972, 9]
1972022 -> [1, 9, 7, 2022]
92183721 -> [9218, 3721]
123 -> [123]
44812 -> [4, 4812]
48123 -> [4812, 3]
1820224610 -> [1, 8, 2022, 4610]
4312370550707 -> [4312, 3705, 5, 0, 707]
54202243215 -> [5420, 224, 3215]
171419012022 -> [1714, 1901, 2022]
171450119010112022 -> [1714, 5, 0, 1, 1901, 0, 1, 1, 2022]
99819918182022 -> [9981, 9918, 1, 8, 2022]
1248163264128 -> [1, 248, 1, 6, 326, 4, 1, 2, 8]
123512351235 -> [1, 235, 1, 235, 1, 235]
23550877187738 -> [2, 3, 5508, 7718, 7738]
732133933917141760 -> [7321, 339, 339, 1714, 1760]

```

I express my deepest gratitude for your unwavering support during these challenging times faced by Great Britain. Your contributions to assisting impoverished, forgetful Britons are truly cherished and immensely valued. May God save the King!

# Answer
# JavaScript (ES7), 274 bytes

Expects a string and returns the partition as an array of integers.

```
f=([v,...a],p=[],s=q=0,c="",[w,x,y,z]=c)=>(v&&!z&&f(a,p,s,c+v),c?f(a,[...p,c++],s+=x?/1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7)|2(hc|pg|ra|uy)|49[01u]|5(he|hh|y[fwz])/.test(c.toString(36))?w>2?3:1<<16/x:[w-+-x]==(y+=+w?[z]:f)?3-!z:[w*x]==y?z?5:3:1/0:2,v):v||q&&s>q?o:(q=s,o=p))

```

Try it online!

This gives alternate solutions for a few test cases.

## Scoring method

We make sure that each part \\$c\\$ is made of at most 4 characters and split them into \\$\[w,x,y,z\]\\$.

* If \\$x\\$ is not defined: this is a single digit ➝ the score is \\$2\\$.
* We test all special patterns at once with the following regular expression applied to the base-36 representation of \\$c+1\\$:

```
/1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7) // 1715 to 2023
|2(hc|pg|ra|uy)                         // 3508 to 3706
|49[01u]                                // 5508 to 5538
|5(he|hh|y[fwz])/                       // 7106 to 7739

```

If a match is found:

+ If \\$w\>2\\$, this is a 'symbol' ➝ the score is \\$3\\$.
    + Otherwise the score is given by the expression `1<<16/x` (\\$1\\$ for `2**0**23`, \\$2\\$ for `1**9**xx`, \\$4\\$ for `1**7**xx` or `1**8**xx`).
* If \\$w\neq0\\$:

+ If `[w-+-x]==y+[z]`, the score is either \\$2\\$ or \\$3\\$.
    + If `[w*x]==y+[z]`, the score is either \\$3\\$ or \\$5\\$.
* If none of the above worked out, the score is \\$\infty\\$.

Below is the corresponding code:

```
x ?
  /1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7)|2(hc|pg|ra|uy)|49[01u]|5(he|hh|y[fwz])/
  .test(c.toString(36)) ?
    w > 2 ?
      3
    :
      1 << 16 / x
  :
    [w - +-x] == (y += +w ? [z] : f) ?
      3 - !z
    :
      [w * x] == y ?
        z ?
          5
        :
          3
      :
        1 / 0
:
  2

```

## Main function

```
f = (                // f is a recursive function taking:
  [v, ...a],         //   v = next digit, a[] = remaining digits
  p = [],            //   p[] = list of parts
  s =                //   s = score
  q = 0,             //   q = best score so far, or 0 if not defined
  c = "",            //   c = current part
  [w, x, y, z] = c   //   (w, x, y, z) = the 4 characters in c
) => (               //
  v && !z &&         // if v is defined and z is undefined,
  f(a, p, s, c + v), // do a recursive call where v is added to c
  c ?                // if c is not empty:
    f(               //   do another recursive call:
      a,             //     pass a[]
      [...p, c++],   //     append c (coerced to an integer) to p[],
                     //     then increment c
      s += ...,      //     update the score (see above)
      v              //     set c = v
    )                //   end of recursive call
  :                  // else:
    v ||             //   if v is defined
    q && s > q ?     //   or q != 0 and s > q:
      o              //     leave the final output o unchanged
    :                //   else:
      (q = s, o = p) //     update q to s and o to p
)                    //

```
> 4 votes

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

```
g=([a,b,c,d,...x],v=W=0,L='')=>a?g(x,v+((0x148b65742d80bb478d07e4dd77f38b367e2a48dcc61f5efd8a935817bd574741de37e99f5b1b08aan+a).match(/..../g).includes(P=a+b+c+d)?a<2?b<9?2:4:a<3||3:[a- -b]==c+d?3:[a*b]==c+d?5:9),L+P+' ')+g([d,...x],v+(c-a-b?c-a*b?9:3:2,L+a+b+c+' '))&&g([b,c,d,...x],v+2,L+a+' '):v<W|!W?(W=v,R=L):R

```

Try it online!

---

# JavaScript (Node.js), 268 bytes

Old answer, doesn't output solution and faultfully

```
f=([c,...x],s='')=>c?Math.min(f(x,s+=c),f(x)+('171417271760182018301837190119101936195219722022321535073573370555075508553771057108771877357738'.match(/..../g).includes([A,B,C,D,E]=s)?s<1900?4:s<3e3?3-A:3:B?!+A|E?1/0:A- -B==C+[D]?D?3:2:A*B==C+[D]?D?5:3:1/0:2)):s?1/0:0

```

Try it online!

f(string left, to encode)
> 3 votes

# Answer
# 05AB1E, 114 bytes

```
.œDεεgÐVi·ë5;÷i•иΩÅjnÃñ8ä{5pqŒΩ&™ l
&5ƒZtøà₆é~λãÝαB‡~hq•žEвyk©(iy¬_iëR3äí©`+QY<*D_i\®`*QYD4Q+*D_I*+}ë®Žζ›₂в@O]OWkè

```

Try it online or verify almost all test cases (the largest two are omitted because they'll timeout on TIO).

**Explanation:**

```
.œ                         # Get all partitions of the (implicit) input
  D                        # Duplicate it
   ε                       # Map over each partition:
    ε                      #  Inner map over each part:
     g                     #   Pop and push the length of the part
      Ð                    #   Triplicate this length
       V                   #   Pop one copy, and store it in variable `Y`
      i                    #   Pop another copy, and if it's 1:
       ·                   #    Double the length to 2
      ë                    #   Else (the length is >=2):
       5;                  #    Push 2.5 (halve 5)
         ÷                 #    Integer-divide the length by this 2.5
       i                   #    If this is 1 (aka the length was 3 or 4):
        •иΩÅjnÃñ8ä{5pqŒΩ&™ l\n&5ƒZtøà₆é~λãÝαB‡~hq•
                           #     Push compressed integer 2059679753934118777767891051414020721847227706932308941504785260793787677550089063849770927917
         žEв               #     Convert it to base-8192 as list: [2022,1901,1910,1936,1952,1972,3215,3507,3573,3705,5507,5508,5537,7105,7108,7718,7735,7738,1714,1727,1760,1820,1830,1837]
             yk            #     Get the index of the current part in this list
                           #     (or -1 if it's not in this list)
               ©           #     Store this index in variable `®` (without popping)
        (i                 #     If the index is -1:
          y                #      Push the current part again
           ¬               #      Push its leading digit (without popping)
          _i               #      If this leading digit is a 0:
                           #       (use the current part implicitly)
           ë               #      Else:
            R              #       Reverse the part
             3ä            #       Split it into three parts
               í           #       Reverse each part
                           #       (converts the part to a triplet: ABC→[C,B,A] and ABCD→[CD,B,A])
                ©          #       Store this triplet in variable `®` (without popping)
                 `         #       Pop and push the parts to the stack
                  +        #       Add the top two (B+A)
                   Q       #       Check if its equal to the other integer (C or CD)
                    Y<     #       Push the part's length - 1
                      *    #       Multiply it to the check
            D              #       Duplicate it
             _i            #       Pop and if it's 0:
               \           #        Discard the duplicated part
                ®          #        Push triplet `®` again
                 `*Q       #        B*A this time
                    YD4Q+  #        Push the part's length + (length==4)
                         * #        Multiply it to the check
               D           #        Duplicate it
                _          #        Pop and check whether its 0
                 I*        #        Multiply it to the input
                   +       #        Add it to the earlier value
              }            #       Close this if-statement
                           #       (implicit else: use the duplicated value)
         ë                 #     Else (the index was not -1):
          ®                #      Push the index again from variable `®`
           Žζ›             #      Push compressed integer 17749
              ₂в           #      Convert it to base-26 as list: [1,0,6,17]
                @          #      Check for each whether it's >= the index
                 O         #      Sum those checks together
                           #    (implicit else: the length is 2 or >=5)
                           #     (implicitly use the implicit input-integer)
   ]                       # Close all if-else statements and the nested maps
    O                      # Sum each inner list together
     W                     # Push the minimum of the sums (without popping the list)
      k                    # Get the (first) index of this minimum in the list of sums
       è                   # Use that to index into the list of partitions
                           # (after which this partition is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand how the compressed integers and lists work.
> 3 votes

# Answer
# Haskell, 560 bytes

```
i x=read[x]
r x c=(\(a,b)->(a+c,x:b)).f
m(a:b:c:l)|i a+i b==i c&&a/='0'=r[a,b,c]2l
 |i a*i b==i c&&a/='0'=r[a,b,c]3l
m(a:b:c:d:l)|i a+i b==read[c,d]&&a/='0'&&c/='0'=r[a,b,c,d]3l
 |i a*i b==read[c,d]&&a/='0'&&c/='0'=r[a,b,c,d]5l
m _=(maxBound::Int,[])
y(a:b:c:d:l)|elem[a,b,c,d]$words"1714 1727 1760 1820 1830 1837"=r[a,b,c,d]4l
 |elem[a,b,c,d]$words"1901 1910 1936 1952 1972"=r[a,b,c,d]2l
 |[a,b,c,d]=="2022"=r[a,b,c,d]1l
 |elem[a,b,c,d]$words"3215 3507 3573 3705 5507 5508 5537 7105 7108 7718 7735 7738"=r[a,b,c,d]3l
y(x:l)=r[x]2l
f[]=(0,[])
f l=min(m l)$y l

```

Ungolfed version:

```

import Data.Char
import Control.Arrow

type Partition = [String]

badResult :: (Int, Partition)
badResult = (maxBound, [])

optimalMemorization :: String -> (Int, Partition)
optimalMemorization [] = (0, [])
optimalMemorization xs = minimum $ map ($ xs) [math, relation]

recurse :: String -> String -> Int -> (Int, Partition)
recurse prefix rest cost = ((+ cost) *** (prefix :)) (optimalMemorization rest)

math :: String -> (Int, Partition)
math (a:b:c:xs)
    | digitToInt a + digitToInt b == digitToInt c && a /= '0' = recurse [a, b, c] xs 2
    | digitToInt a * digitToInt b == digitToInt c && a /= '0' = recurse [a, b, c] xs 3
math (a:b:c:d:xs)
    | digitToInt a + digitToInt b == read ([c, d]) && a /= '0' && c /= '0' = recurse [a, b, c, d] xs 3
    | digitToInt a * digitToInt b == read ([c, d]) && a /= '0' && c /= '0' = recurse [a, b, c, d] xs 5
math _ = badResult

relation :: String -> (Int, Partition)
relation (a:b:c:d:xs)
    | [a, b, c, d] `elem` ["1714", "1727", "1760", "1820", "1830", "1837"] = recurse [a, b, c, d] xs 4
    | [a, b, c, d] `elem` ["1901", "1910", "1936", "1952", "1972"] = recurse [a, b, c, d] xs 2
    | [a, b, c, d] == "2022" = recurse [a, b, c, d] xs 1
    | [a, b, c, d] `elem` ["3215", "3507", "3573", "3705", "5507", "5508", "5537", "7105", "7108", "7718", "7735", "7738"] = recurse [a, b, c, d] xs 3
relation (x:xs) = recurse [x] xs 2 -- Residual option

```

We pass around `(Int, Partition)`s where the `Int` is the cost and `Partition` is the answer. As we go, we take a `min` of these. `min` on tuples compares the first element first, so we always take a minimum cost element using the default Haskell comparison.

In terms of branching, we only have to check `math` (`m` in the golfed version) and `relation` (resp. `y`). `relation` checks the year condition and the symbol condition, which are mutually exclusive and hence safe to check together. `math` checks the four mathematical conditions in order: 3-digit sum, 3-digit product, 4-digit sum, 4-digit product. This order will always produce an optimal mathematical result.

Proof: If 3-digit sum succeeds, then 3-digit product just costs more and is not optimal. 4-digit sum cannot succeed since two numbers cannot add up to two different results simultaneously, and 4-digit product is not optimal because it's worse than just taking the 3-digit sum and treating the fourth digit as residual (`2 + 2` vs. `5`). If 3-digit product succeeds, then 4-digit sum must fail (sums are not larger than products), and 4-digit product must fail since the product can't be two different numbers. Finally, if 4-digit sum succeeds, it's better than 4-digit product by cost alone. ∎

So implement our main function `optimalMemorization` (resp. `f`) recursively. If the string is empty, cost is zero. Else, try `math` and `relation` and take the minimum cost between the two (if the cost is the same, we choose the string that would appear first in the dictionary, which is a harmless tiebreaker).

`recurse` (resp. `r`) is a helper function, since we always combine our results in the same way, so it's better to give this helper a name. `i` in the golfed version is just `Data.Char.digitToInt`, but it's shorter to write it ourselves rather than importing.

Our `badResult` is just the "failure" case (since the math rules might not even apply at all) and produces a memorization string with the worst possible cost. Unfortunately, in the golfed version, we need a `::Int` here. It didn't have to be here, but we had to put a type annotation somewhere, because without specifying that our math is being done with integers, all Haskell can tell is that our math is being done with some `(Num a, Bounded a, Ord a) => a` type, and it's ambiguous which one.
> 3 votes

# Answer
# Jelly, 111 bytes

```
“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’ḃ;@ƭ/€ÄFfḌ:ȷ2«21ị⁽⁵ȥD¤
3œṖS,PƊD⁼€ɗ/×2,3×LH_.ƲĊ;ÇoȷṂµLḤ$aL$Ḣ>2Ʋ?€S
ŒṖÇÞḢ

```

Try it online!

A monadic link that takes either an integer or a list of decimal digits and returns a list of lists of digits with the optimal score. If the output needs to be a list of integers, this can be done at the cost of one byte () at the end of the main link.

## Explanation

```
“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’ḃ;@ƭ/€ÄFfḌ:ȷ2«21ị⁽⁵ȥD¤  # Helper link 1: takes a list of digits and returns a score based on the two types of fixed four-digit integers, or zero if no match
“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’                        # Compressed integer list of lists: [[105435108560611884151247538639414029, 1802, 3215], [15599387739683358002, 64, 1714]]
                                             €                  # For each list:
                                           ƭ/                   # - Reduce by doing the following alternately
                                        ḃ                       #   - Convert to bijective base
                                         ;@                     #   - Concatenate, in reverse order
                                              Ä                 # Cumulative sum
                                               F                # Flatten
                                                fḌ              # Keep only those that match the helper link’s argument (after it’s been converted to an integer from decimal digits)
                                                  :ȷ2           # Integer divide by 100
                                                     «21        # Min of this and 21
                                                        ị⁽⁵ȥD¤  # Index into 3,4,4,2,1 (⁽⁵ȥ encoded 34421 which is then split into decimal digits)

3œṖS,PƊD⁼€ɗ/×2,3×LH_.ƲĊ;ÇoȷṂµLḤ$aL$Ḣ>2Ʋ?€S                      # Helper link 2: takes a list of lists of digits and works out the score for each sublist before summing them
                                        €                       # For each list:
                                      Ʋ?                        # - If the following is true:
                                aL$                             #   - And list with its length (handles voiding lists that start with zero)
                                   Ḣ                            #   - Head
                                    >2                          #   - Is greater than 2
                            µ                                   # - Then:
3œṖ                                                             #   - Split before third list member
          ɗ/                                                    #   - Reduce this list using the following:
   S,PƊ                                                         #     - Sum paired with product
       D                                                        #     - Convert to decimal digits
        ⁼€                                                      #     - Check whether each equal to second half of list
            ×2,3                                                #   - Multiply by 2 (for addition) and 3 (for multiplication)
                ×    Ʋ                                          #   - Multiply by the following
                 LH                                             #     - Half the length of the list
                   _.                                           #     - Minus 0.5
                      Ċ                                         #   - Ceiling
                       ;Ç                                       #   - Concatenate to result of running helper link 1 on the original list
                         oȷ                                     #   - Or with 1000 (replaced zeros with 1000)
                           Ṃ                                    #   - Minimum
                             LḤ$                                # - Else: double the length of the list
                                         S                      # Sum

ŒṖÇÞḢ                                                           # Main link: takes an integer or a list of decimal digits and returns a list of lists of digits with the lowest score
ŒṖ                                                              # Partitions of list
  ÇÞ                                                            # Sort by results of helper list 2 on each partition
    Ḣ                                                           # Head

```

Created with the help of Luminespire.
> 3 votes

# Answer
# Charcoal, 156 bytes

```
≔⟦⟦⁰Ｓ⟧⟧θＦθ«≔⊟ιη¿ηＦ⊞Ｏ⁺Ｅ⪪”)¶≕⁰∨℅U:.ï4◧Π-⊙⁵z›“Dνq⬤◧≦rＳ=≦:nＷ→NＥE⊕ζTΣ✂aＨ⟲“↶¿!⧴p↘Y”⁵⪪κ⁴Ｅ∧›η1⟦Σ…η²Π…η²⟧⟦⁺…η²κ×⊕λＬκ⟧⟦…η¹2⟧Ｆ¬⌕η§κ⁰⊞θ⁺Ｅι⎇νμ⁺Σ⊟κμ⟦…ηＬ§κ⁰✂ηＬ§κ⁰⟧⊞υι»✂⌊υ¹

```

Try it online! Link is to verbose version of code. Gives alternative results for two of the inputs. Explanation:

```
≔⟦⟦⁰Ｓ⟧⟧θＦθ«

```

Perform a breadth first search over partitions starting with no partitions yet and a score of zero.

```
≔⊟ιη

```

Get the next unpartitioned suffix.

```
¿η

```

If it wasn't empty:

```
Ｆ⊞Ｏ⁺Ｅ⪪”...”⁵⪪κ⁴Ｅ∧›η1⟦Σ…η²Π…η²⟧⟦⁺…η²κ×⊕λＬκ⟧⟦…η¹2⟧

```

Loop over three lists: a) A list of years and symbols, with their scores b) If the suffix does not begin with `0`, then a list of additions and products, with their scores c) A list of the first digit with a score of `2`.

```
Ｆ¬⌕η§κ⁰

```

If the suffix starts with this potential partition, then...

```
⊞θ⁺Ｅι⎇νμ⁺Σ⊟κμ⟦…ηＬ§κ⁰✂ηＬ§κ⁰⟧

```

Push the updated partition and score to the search list.

```
⊞υι

```

But if it was empty, then collect the completed partition in the predefined empty list.

```
»✂⌊υ¹

```

Output the partition with the lowest score, tied by shortest length of the first different substring.
> 2 votes

# Answer
# Ruby `-nl`, 380 bytes

Probably the wrong approach to use. Creates a recursive function that checks the input against a gigantic regex sequence, cutting off valid pieces and comparing the scores to find the smallest one. Then, feed input from STDIN into that function and print the result.

```
r=(r=*1..9).product([0]+r)
f=->i,*k{i=~/(2022)|19(01|10|36|52|72)|18(20|30|37)|(3215|3507|3573|3705|550[78]|5537|710[58]|7718|773[58])|17(14|27|60)|(#{r.map{|a,b|[a,b,a+b]*''}*?|})|(#{r.map{|a,b|[a,b,a*b]*''}*?|})|(.)/
k=*$&;l=$&.size/4
s=$6?2+l:$7?3+2*l:[p,$1,$2||$8,$4,$3||$5].index{_1}
(n,v=f[$'];k+=n;s+=v)if$'[0]
i[1]&&(n,v=f[i[1..]];s>v+2&&[[i[0]]+n,v+2])||[k,s]}
p f[$_][0]

```

Attempt This Online!
> 2 votes

---
Tags: code-golf, integer, set-partitions
---


# Question
Title: Reconstruct an array by successive insertions
Given an array of letters in the range 'a' to 'o', compute how to construct the array by successively inserting the letters in alphabetical order. You will always start the insertion with a base array of all the 'o's that are in the array to be reconstructed.

# Examples

Let the input array be:

```
['o', 'b', 'o', 'b', 'a']

```

The base would have been \['o', 'o'\] in this case. To construct it you would do the following insertings.

* Insert 'a' at index 2 (indexing from 0). This gives \['o', 'o', 'a'\]
* Insert 'b at index 1. This gives \['o', 'b', 'o', 'a'\]
* Insert 'b' at index 3. This gives \['o', 'b', 'o', 'b', 'a'\]

Let the input array be:

```
['a', 'o', 'b', 'o', 'a', 'c', 'b']

```

The base case to start inserting will therefore be: \['o', 'o'\]

* Insert 'a' at index 0 giving \['a', 'o', 'o'\]
* Insert 'a' at index 3 giving \['a', 'o', 'o', 'a'\]
* Insert 'b' at index 2 giving \['a', 'o', 'b', 'o', 'a'\]
* Insert 'b' at index 5 giving \['a', 'o', 'b', 'o', 'a', 'b'\]
* Insert 'c' at index 5 giving \['a', 'o', 'b', 'o', 'a', 'c', 'b'\]

Let the input array be:

```
['c', 'b', 'a', 'o',  'o', 'o']

```

The base case to start inserting will therefore be: \['o', 'o', 'o'\]

* Insert 'a' at index 0
* Insert 'b' at index 0
* Insert 'c' at index 0

Let the input array be:

```
['c', 'b', 'a', 'o', 'b', 'o', 'b', 'a']

```

# Output

The exact output format is of your choosing but it should be equivalent to:

For case 1:

```
'a', 2
'b', 1, 3

```

For case 2:

```
'a', 0, 3
'b', 2, 5
'c', 5

```

For case 3:

```
'a', 0
'b', 0
'c', 0

```

For case 4:

```
'a', 0, 3
'b', 0, 3, 5
'c', 0

```

BONUS (just for bragging rights) Make your code time efficient. That is can you minimise the number of operations it performs?

# Answer
> 12 votes
# 05AB1E, 11 bytes

```
η@O<ø{.γн}¦

```

Try it online!

Takes a list of numbers, 0 to 14, with `o` being 0, and `a, b, ...` being 1,2,....

We can notice that the index of an element in the correct list is the number of elements before it which are less than or equal to it.

```
η      # prefixes [[1], [1, 0], [1, 0, 2], [1, 0, 2, 0], [1, 0, 2, 0, 1], [1, 0, 2, 0, 1, 3], [1, 0, 2, 0, 1, 3, 2]]
@      # element in list greater than or equal to each element in the prefixes: [[1], [0, 1], [1, 1, 1], [0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1]]
O      # sum: [1, 1, 3, 2, 4, 6, 6]
<      # subtract one, to account for the element itself: [0, 0, 2, 1, 3, 5, 5]
ø      # zip with the original array: [[1, 0], [0, 0], [2, 2], [0, 1], [1, 3], [3, 5], [2, 5]]
{      # sort: [[0, 0], [0, 1], [1, 0], [1, 3], [2, 2], [2, 5], [3, 5]]
.γ     # group by:
 н     # the first element
} # [[[0, 0], [0, 1]], [[1, 0], [1, 3]], [[2, 2], [2, 5]], [[3, 5]]]
¦      # remove the first element, the zeros: [[[1, 0], [1, 3]], [[2, 2], [2, 5]], [[3, 5]]]

```

If we can use a looser output format, not grouping the pairs by value, we can get 8 bytes: `η@O<øʒнĀ`

# Answer
> 7 votes
# Vyxal, 11 bytes

```
14ʁṘ(n~=T,o

```

Try it Online!

Takes a list of numbers, outputs 14 arrays containing the indices from `n` to `a`, descending.

9 bytes if I can take input as \[14...0\] instead of \[0...14\].

```
14ʁṘ(n~=T,o
             # Implicitly inputting the array
14ʁṘ(        # Loop n from 13 to 0:
     n~=T,   # Print all the indices of n in the current array
          o  # Remove n from the array

```

# Vyxal, 10 bytes

```
K≥Ṡ‹Zs⁽hġḢ

```

Try it Online!

Port of Command Master's clever answer.

# Answer
> 7 votes
# , 41 bytes

```
\(x)Map(\(i)which(x[x<=i]==i)-1,1:max(x))

```

**How?**

```
f=
\(x)                        # define function with argument x;
    Map( ... ,1:max(x))     # map over integers from 1 to max(x)
                            #   for each of these, assigned to variable i:
      which(          )     #     find the indices of
            x[    ]         #       elements of the subset of x
              x<=i          #       that contains only elements <=i
                   ==i      #     that are equal to i
                       -1   #   and subtract 1 to convert to 0-based indices

```

Attempt This Online!

Outputs a list of vectors of the 0-based indices to insert each element that is present in the input.
Can be 2 bytes shorter by also including some empty vectors for elements that aren't present in the input. And, of course, trivially 2 bytes shorter again using R's native 1-based indexing (omit the `-1`).

---

# , 93 bytes

```
\(x){a=l=!1:15
a[]=list({})
Map(\(v){a[[v]]<<-c(a[[v]],l[v])
l[v:15]<<-l[v:15]+1},x+1)
a[-1]}

```

Attempt This Online!

Runs in O(n) time complexity, making a single pass through the input list with only O(1) operations at each step.

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

Expects an array of integers in \\$\[1\dots15\]\\$. Returns an array of 14 arrays containing the insertion indices.

```
f=(a,n=14,b=[])=>n?[...f(a.filter((c,i)=>c-n||!b.push(i)),n-1),b]:b

```

Try it online!

### Commented

```
f = (              // f is a recursive function taking:
  a,               //   a[] = input array
  n = 14,          //   n   = item counter
  b = []           //   b[] = output array for the current item
) =>               //
n ?                // if n is not equal to 0:
  [                //   update the output:
    ...f(          //     do a recursive call:
      a.filter(    //       filter a[]
      (c, i) =>    //       for each value c at index i in a[]:
        c - n ||   //         keep this value if it's not equal to n
        !b.push(i) //         otherwise, remove it and append i to b[]
      ),           //       end of filter()
      n - 1        //       decrement n
    ),             //     end of recursive call
    b              //     append b[]
  ]                //
:                  // else:
  b                //   stop

```

# Answer
> 4 votes
# Python3, 202 bytes:

```
def f(a):
 t=[[],[]]
 for i in a:t[i!='o']+=[i]
 q=[(t[0],sorted(t[1]),[])]
 while q:
  j,k,I=q.pop(0)
  if a==j:return I
  if k:
   for u in range(len(j)+1):q+=[(j[:u]+[k[0]]+j[u:],k[1:],I+[(k[0],u)])]

```

Try it online!

# Answer
> 4 votes
# Pip, 22 bytes

```
FiR,14{PiAEg@*ig:gRMi}

```

`a` to `o` is mapped from 0 to 14.

*Semi-port of Steffan's Vyxal answer*

Attempt This Online! | 19 bytes if indices don't have to be grouped

```
FiR,14{PiAEg@*ig:gRMi}
FiR,14{              }  # For i in range 14, 0
       P   g@*i         # Print all indices of i in list
        iAE             # Prepended with i
               g:gRMi   # Remove all instances of i in list

```

# Answer
> 4 votes
# K (ngn/k), 60 58 56 bytes

```
{-1_'"o"_(+/'</1*:\-1_(1_)\|<<x*~"o"=x)@|'=|x,:@/1>:\?x}

```

Try it online!

Probably missing something clever but sorting the keys in the result cost ~~16~~ 14 bytes.

-2 : Cheaper way to force o’s to bottom

# Answer
> 4 votes
# Python 3, 74 bytes

```
f=lambda x:sorted((i,sum(j<=i for j in x[:n]))for n,i in enumerate(x)if i)

```

Takes input as integers:

```
['a', 'o', 'b', 'o', 'a', 'c', 'b'] -> [1, 0, 2, 0, 1, 3, 2]

```

Outputs an array in the form \[(input, index)\]:

Input:

```
['a', 'o', 'b', 'o', 'a', 'c', 'b']

```

Output:

```
[(1, 0), (1, 3), (2, 2), (2, 5), (3, 5)]

```

# Answer
> 3 votes
# Charcoal, 22 bytes

```
⊞υoＷ⌊⁻θυ⟦ιＩ⌕Ａ⁻θ⁻θ⊞Ｏυιι

```

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

```
⊞υo

```

Start as if `o` had already been processed.

```
Ｗ⌊⁻θυ

```

While there are any unprocessed letters, take the minimum.

```
⟦ιＩ⌕Ａ⁻θ⁻θ⊞Ｏυιι

```

Output the letter and the indices that it would have been at i.e. the indices after removing the remaining unprocessed letters.

```
         ⊞Ｏυι   All processed letters so far (including the current one)
       ⁻θ⊞Ｏυι   All unprocessed letters so far (may include duplicates)
     ⁻θ⁻θ⊞Ｏυι   Input with unprocessed letters removed
   ⌕Ａ        ι  Get the indices of the current letter
⟦ιＩ             Output the letter with its indices

```

# Answer
> 3 votes
# Python, 95 bytes

```
f=lambda a,c='l':[0]*(c<'a')or-~(x:=a.rfind(c))and[c,x]+f(a[:x]+a[x+1:],c)or f(a,chr(ord(c)-1))

```

Attempt This Online!

# Python, 97 bytes

```
f=lambda a,c='n':c>'`'and(-~(x:=a.rfind(c))and f(a[:x]+a[x+1:],c)+[c,x]or f(a,chr(ord(c)-1)))or[]

```

Attempt This Online!

Using a more standard output format.

Explanation forthcoming.

# Answer
> 3 votes
# , 21 bytes

```
*@/:~#/:{1#.(}:<:{:)\

```

Attempt This Online!

Inspired by CommandMaster's nice insight, though the mechanics are different.

* `1#.(}:<:{:)\` For each prefix, count `1#.` the number of those to the left of the last element `}:` that are less than or equal to `<:` the last element `{:`. This part is the same as CommandMaster's approach.
* `/:{` Now order those elements according to the "grade up" `/:` of the original input. For example, if, when ordering the original input, the 3rd element moves to the first slot, then move the 3rd element of the result of step 1 to the first slot, and so on.
    + At this point we are done, except that we are still including the "base element" zeroes. They will all be at the beginning of our answer now, so we only need to remove from the start of our solution array the number of zeroes contained in the input.
* `*@/:~` To remove them, we sort the input and take the signum, which will give as an array like `0 0 1 1 1 1`, where the number of zeroes at the start matches the number of zeroes in the input.
* `#` Use that to filter our previous result.

# Answer
> 3 votes
# jq, 62 bytes

```
unique[:-1][]as$e|map(select(.<=$e or.=="o"))|[$e]+indices($e)

```

Try it online!

# Answer
> 2 votes
# Scala, 420 bytes

Port of @Ajax1234's Python answer in Scala.

---

Golfed version. Try it online!

```
def f(a:List[Char])={val t=a.foldRight((List[Char](),List[Char]())){case(i,(x,y))=>if(i!='o')(i::x,y)else(x,i::y)}
def l(q:List[(List[Char],List[Char],List[(Char,Int)])]):Option[List[(Char,Int)]]=q match{case Nil=>None
case(j,k,i)::r=>if(a==j)Some(i.reverse)else if(k.nonEmpty)l(r++(0 to j.length).toList.flatMap(u=>List((j.take(u)++(k.head::j.drop(u)),k.tail,(k.head,u)::i))))else l(r)}
l(List((t._2,t._1.sorted,Nil)))}

```

Ungolfed version. Try it online!

```
object Main extends App {
  def f(a: List[Char]): Option[List[(Char, Int)]] = {
    val t = a.foldRight((List[Char](), List[Char]())) { case (i, (x, y)) =>
      if (i != 'o') (i :: x, y) else (x, i :: y)
    }

    def loop(queue: List[(List[Char], List[Char], List[(Char, Int)])]): Option[List[(Char, Int)]] =
      queue match {
        case Nil => None
        case (j, k, i) :: rest =>
          if (a == j) Some(i.reverse)
          else if (k.nonEmpty) {
            val newQueue = (0 to j.length).toList.flatMap(u => List((j.take(u) ++ (k.head :: j.drop(u)), k.tail, (k.head, u) :: i)))
            loop(rest ++ newQueue)
          } else {
            loop(rest)
          }
      }

    loop(List((t._2, t._1.sorted, Nil)))
  }

  println(f(List('o', 'b', 'o', 'b', 'a')))
  println(f(List('a', 'o', 'b', 'o', 'a', 'c', 'b')))
  println(f(List('c', 'b', 'a', 'o',  'o', 'o')))
}

```

# Answer
> 2 votes
# Nibbles, 9 bytes (18 nibbles)

```
. ,@ :$ +-1 `? |@~-$@ @

```

Attempt This Online!

Outputs a list containing 100 lists: the first entry of each is the element to add, the next entry/entries are the 0-based positions to insert it. Obviously only lists 1-14 can contain insertion positions if these are the only values possible in the input.
8 bytes by outputting only lists of positions (without the element itself as the first entry); 6 bytes using 1-based indexing.

```
.                           # map over
  ,@                        # 1..100
     :$                     #   prepending each value to:
            `?              #   indices of
                @           #     the input
               |            #       (filtered to retain only
                 ~-$        #       elements less than or equal to
                    @       #       the current value)
                      @     #     that equal the current value
        +-1                 #   minus 1 (for 0-based indexing)

```

---

# Nibbles, 10.5 bytes (21 nibbles)

```
. ,`/$] :$ +-1 `? |@~-$@ @

```

Attempt This Online!

Outputs a list as above, but only containing lists of element(s) + position(s) for values that are present in the input.
8.5 bytes or 6.5 bytes by outputting only lists of positions, and with 1-based indexing, respectively.

# Answer
> 2 votes
# K (ngn/k), 39 bytes

```
{a!1_{&(*z)=x^y}[x]':(1_)\a@:<a:?x^"o"}

```

Try it online!

Takes input as a string, returning a dictionary mapping the sorted non-"o" characters to lists of indices.

* `a:?x^"o"` identify the non-"o" characters in the input
* `a@:<` sort them, storing the result in the `a` variable
* `(1_)\` generate the suffixes of the sorted characters
* `{...}[x]':` set up an each-previous, fixing the `x` variable to the original input
    + `&(*z)=x^y` identify the indices each character should be inserted into
* `a!1_` build a dictionary mapping the non-"o" characters to the indices

# Answer
> 1 votes
# Jelly, 10 bytes

```
>Ðḟ¹ẹɗⱮṀ’Ė

```

Try it online!

A monadic link that takes a list of numbers from 0 to 14, with 0 corresponding to 'o' and 1 to 14 corresponding to 'a' to 'n'. Returns a list of lists; each list in the return value has the number in the original input it corresponds to as the first item and then a list of the 0-indexed insertion indices as the second item. If 1-indexing was allowed this would save a byte. If it were permissible to omit the labelling of the index lists with the number to which they correspond, this would save a further byte.

## Explanation

```
     ɗⱮṀ   | For each integer y from 1 to the max integer in the argument:
>Ðḟ        | - Filter the original argument removing those values > y
   ¹       | - No-op (needed because of the way chaining works in Jelly within a dyadic chain)
    ė      | - Indices of y in this filtered list
        ’  | Decrease by 0 (because of Jelly’s 1-indexing)
         Ė | Enumerate (prefix each list with a sequential number)

```

# Answer
> 1 votes
# Excel (ms365), 170 bytes

Formula in `B1`:

```
=DROP(IFNA(REDUCE(0,CHAR(ROW(97:110)),LAMBDA(o,n,IFERROR(VSTACK(o,HSTACK(n,LET(x,TOROW(A:A,3),y,FILTER(x,(x<=n)+(x="o")),FILTER(SEQUENCE(,COUNTA(y)),y=n)-1))),o))),""),1)

```

There is most likely some room for improvement. I deliberately use `TOCOL(A:A,3)` instead of an exact reference just so it's easy to moderate the input in column `A:A`.

Therefor, without too much hassle you can get the following:

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


title: Rational Polynomial Interpolation

text:
# Question
Title: Rational Polynomial Interpolation
## Explanation

In this task you'll be given a set of *N* points *(x1,y1),…,(xN,yN)* with distinct *xi* values and your task is to interpolate a polynomial through these points. If you know what Lagrange interpolation is you can skip this section.

The goal of a polynomial interpolation is to construct the (unique) polynomial *p(x)* with degree *N-1* (for higher degrees there are infinite solutions) for which *p(xi) = yi* for all *i = 1…N*. One way to do so is to construct *N* Lagrange basis polynomials and form a linear combination. Such a basis polynomial is defined as follows:

As you can see if you evaluate *li* at the points x1,…,xi-1 ,xi+1,… ,xN it is 0 by construction and 1 for xi, multiplying by yi will only change the value at xi and set it to yi. Now having N such polynomials that are 0 in every point except one we can simply add them up and get the desired result. So the final solution would be:

## Challenge

* the input will consist of *N* data points in any reasonable format (list of tuples, Points, a set etc.)
* the coordinates will all be of integer value
* the output will be a polynomial in any reasonable format: list of coefficients, Polynomial object etc.
* the output has to be exact - meaning that some solutions will have rational coefficients
* formatting doesn't matter (`2/2` instead of `1` or `1 % 2` for `1/2` etc.) as long as it's reasonable
* you won't have to handle invalid inputs (for example empty inputs or input where *x* coordinates are repeated)

## Testcases

These examples list the coefficients in decreasing order (for example `[1,0,0]` corresponds to the polynomial *x2*):

```
[(0,42)] -> [42]
[(0,3),(-18,9),(0,17)] -> undefined (you don't have to handle such cases)
[(-1,1),(0,0),(1,1)] -> [1,0,0]
[(101,-42),(0,12),(-84,3),(1,12)] -> [-4911/222351500, -10116/3269875, 692799/222351500, 12]

```

# Answer
# Pari/GP, 14 bytes

```
polinterpolate

```

Takes two lists `[x1, ..., xn]` and `[y1, ..., yn]` as input. Outputs a polynomial.

Try it online!

---

# Pari/GP, 35 bytes, without built-in

```
f(x,y)=y/matrix(#x,,i,j,x[j]^(i-1))

```

Takes two lists `[x1, ..., xn]` and `[y1, ..., yn]` as input. Outputs a list of coefficients.

Try it online!
> 5 votes

# Answer
# Enlist, 25 bytes

```
Ḣ‡ḟ¹‡,€-÷_Ḣ¥€§æc/§₱W€$↙·Ṫ

```

Try it online!

---

Monadic link takes an array of length 2 (e.g., `[[101,0,-84,1],[-42,12,3,12]]`) as input. The first element of the array is list of x value, the second is list of y value. Output as list of coefficient in increasing degree.

Because @HyperNeutrino forgot to wrap numbers in rational wrapper if it is evaluated in list, (Try it online!) the argument must be hardcoded in the code.

The  is necessary because HyperNeutrino make some mistake in implementing `·` I don't know (or is this a feature? Not sure)

Equivalent Mathematica code:

```
Expand[ Table[
 Times @@ ((z - #)/(xi - #) & /@ DeleteCases[x, xi])
 , {xi, x}] . y]

```

Try it online!

where `x` and `y` are list of coordinates. This prints the polynomial.

---

What Enlist have for this challenge:

* Built in rational number support
* Convolution `æc` (my feature request)
> 1 votes

# Answer
# Python, with `numpy`, 301 bytes

See this notebook for how it works.

---

Golfed version. 301 bytes, it can be golfed much more. Attempt this online!

```
import numpy as np
from itertools import combinations as C
from numpy.polynomial import Polynomial as P
def l(k,x):return P([sum([np.prod(x) for x in C(np.delete(x,k),i)])*(-1)**(i+1)/np.prod(np.delete(x,k)-x[k]) for i in range(len(x))][::-1])
def f(x,y):return sum(l(k,x)*y[k] for k in range(len(y)))

```

Ungolfed version. Attempt this online!

```
import numpy as np
from itertools import combinations
from numpy.polynomial import Polynomial

# get the Lagrange basis function
def l(k, x):
    n = len(x)
    assert (k < len(x))

    x_k = x[k]
    x_copy = np.delete(x, k)

    denominator = np.prod(x_copy - x_k)

    coeff = []

    for i in range(n):
        coeff.append(sum([np.prod(x) for x in combinations(x_copy, i)]) * (-1)**(i+1) / denominator)

    coeff.reverse()

    return Polynomial(coeff)

def f(x,y):return sum(l(k,x)*y[k] for k in range(len(y)))

x=[101,0,-84,1]
y=[-42,12,3,12]
print(f"{l(0,x)=}\n")
print(f"{l(1,x)=}\n")
print(f"{l(2,x)=}\n")
print(f"{l(3,x)=}\n")
print("y[0]*l(0,x)+y[1]*l(1,x)+y[2]*l(2,x)+y[3]*l(3,x)== f(x):")
print(f(x,y))

```
> 1 votes

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


# Question
Title: Discrete Convolution or Polynomial Multiplication
Given two *non empty* lists of integers, your submission should calculate and return the *discrete convolution* of the two. Interestingly, if you consider the list elements as coefficients of polynomials, the convolution of the two lists represents the coefficients of the product of the two polynomials.

### Definition

Given the lists `A=[a(0),a(1),a(2),...,a(n)]` and `B=[b(0),b(1),b(2),...,b(m)]` (setting `a(k)=0 for k<0 and k>n` and `b(k)=0 for k<0 and k>m`) then the convolution of the two is defined as `A*B=[c(0),c(1),...,c(m+n)]` where `c(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]`

### Rules

* Any convenient input and output formatting for your language is allowed.
* Built-ins for convolution, creating convolution matrices, correlation and polynomial multiplication are not allowed.

### Examples

```
[1,1]*[1] = [1,1]
[1,1]*[1,1] = [1,2,1]
[1,1]*[1,2,1] = [1,3,3,1]
[1,1]*[1,3,3,1] = [1,4,6,4,1]
[1,1]*[1,4,6,4,1] = [1,5,10,10,5,1]

[1,-1]*[1,1,1,1,1] = [1,0,0,0,0,-1]
[80085,1337]*[-24319,406] = [-1947587115,7,542822]

```

# Answer
> 14 votes
# J, ~~10~~ 8 bytes

```
[:+//.*/

```

Usage:

```
ppc =: [:+//.*/    NB. polynomial product coefficients
80085 1337 ppc _24319 406
_1947587115 7 542822

```

Description: The program takes takes two lists, makes a multiplication table, then adds the numbers on the positive diagonals.

# Answer
> 6 votes
# MATL, 19 bytes

```
PiYdt"TF2&YStpsw]xx

```

**Try it online!**

### Explanation

This builds a block-diagonal matrix with the two inputs, reversing the first. For example, with inputs `[1 4 3 5]`, `[1 3 2]` the matrix is

```
[ 5 3 4 1 0 0 0
  0 0 0 0 1 3 2 ]

```

Each entry of the convolution is obtained by shifting the first row one position to the right, computing the product of each column, and summing all results.

In principle, the shifting should be done padding with zeros from the left. Equivalently, *circular* shifting can be used, because the matrix contains zeros at the appropriate entries.

For example, the first result is obtained from the shifted matrix

```
[ 0 5 3 4 1 0 0
  0 0 0 0 1 3 2 ]

```

and is thus `1*1 == 1`. The second is obtained from

```
[ 0 0 5 3 4 1 0
  0 0 0 0 1 3 2 ]

```

and is thus `4*1+1*3 == 7`, etc. This must be done `m+n-1` times, where `m` and `n` are the input lengths. The code uses a loop with `m+n` iterations (which saves some bytes) and discards the last result.

```
P          % Take first input (numeric vactor) implicitly and reverse it
i          % Take second input (numeric vactor)
Yd         % Build diagonal matrix with the two vectors
t          % Duplicate
"          % For each column of the matrix
  TF2&YS   %   Circularly shift first row 1 step to the right
  t        %   Duplicate
  p        %   Product of each column
  s        %   Sum all those products
  w        %   Swap top two elements in stack. The shifted matrix is left on top
]          % End for
xx         % Delete matrix and last result. Implicitly display

```

# Answer
> 4 votes
# Haskell, ~~55~~ 49 bytes

```
(a:b)#c=zipWith(+)(0:b#c)$map(a*)c++[]#b
_#c=0<$c

```

Defines an operator `#`.

# Answer
> 3 votes
# 05AB1E, ~~18~~ 17 bytes

### Code

```
0Ev²¹g<Å0«y*NFÁ}+

```

### Explanation

**The theory behind:**

To find the convolution, let's take the example `[1, 2, 3]`, `[3, 4, 5]`. We position the values of the first array upside down and vertically, like this:

```
3
2
1

```

Now, we place the second array like a ladder and multiply it by :

```
3 ×       [3  4  5]
2 ×    [3  4  5]
1 × [3  4  5]

```

Resulting into:

```
        9   12   15
    6   8   10
3   4   5

```

Then, we add them up, resulting into:

```
        9   12   15
    6   8   10
3   4   5

3   10  22  22   15

```

So, the convolution is `[3, 10, 22, 22, 15]`.

**The code itself:**

We are going to do this step by step using the `[1, 2, 3]`, `[3, 4, 5]` as the test case.

```
0Ev²¹g<Å0«y*NFÁ}+

```

We first push `0` and then we `E`valuate the first input array. We map over each element using `v`.

So, for each element, we push the second array with `²` and then the length of the first array using `¹g` and decrease this by 1 (with `<`). We convert this into a **list of zeros** with **(length 1st array - 1)** zeros, using `Å0` and append this to our list. Our stack now looks like this for the first item in the input list:

```
[3, 4, 5, 0, 0]

```

We multiply this array with the current item, done with `y*`. After that, we push `N`, which indicates the index of the current item (zero-indexed) and rotate the array that many times to the right using `FÁ}`. Finally, we add this to our initial value (`0`). So, what basically is done is the following:

```
[0, 0, 9, 12, 15] +
[0, 6, 8, 10, 0] +
[3, 4, 5, 0, 0] =

[3, 10, 22, 22, 15]

```

Which is then implicitly printed. Uses **CP-1252** encoding. Try it online!.

# Answer
> 3 votes
# Octave, 48 bytes

```
@(p,q)ifft(fft([p q*0]).*fft([q p*0]))(1:end-1)

```

**Try it here**.

### Explanation

Discrete convolution corresponds to multiplication of the (discrete-time) Fourier transforms. So one way to multiply the polynomials would be transform them, multiply the transformed sequences, and transform back.

If the discrete Fourier transform (DFT) is used instead of the Fourier transform, the result is the *circular* convolution of the original sequences of polynomial coefficients. The code follows this route. To make circular convolution equal to standard convolution, the sequences are zero-padded and the result is trimmed.

# Answer
> 3 votes
# Matlab / Octave, 41 bytes

```
@(p,q)poly([roots(p);roots(q)])*p(1)*q(1)

```

This defines an anonymous function. To call it, assign it to a variable or use `ans`.

**Try it here**.

### Explanation

This exploits the facts that

* The (possibly repeated) roots characterize a polynomial up to its leading coefficient.
* The product of two polynomials has the roots of both.

The code computes the roots of the two polynomials (function `roots`) and concatenates them into a column array. From that it obtains the coefficients of the product polynomial with a leading `1` (function `poly`). Finally the result is multiplied by the leading coefficients of the two polynomials.

# Answer
> 3 votes
# Jelly, 9 bytes

```
0;+
×'Ṛç/

```

Try it online! or verify all test cases.

### How it works

```
×'Ṛç/  Main link. Arguments: p, q (lists)

×'     Spawned multiplication; multiply each item of p with each item of q.
  Ṛ    Reverse the rows of the result.
   ç/  Reduce the rows by the helper link.

0;+    Helper link. Arguments: p, q (lists)

0;     Prepend a 0 to p.
  +    Perform vectorized addition of the result and q.

```

# Answer
> 3 votes
# Husk, 5 bytes

```
mΣ∂Ṫ*

```

Try it online!

**Note:** When supplying the zero-polynomial/empty list, you need to specify its type (ie. `[]:LN`)!

### Explanation

```
mΣ∂Ṫ*  -- implicit inputs xs ys, for example: [1,-1] [1,1]
   Ṫ*  -- compute the outer product xsᵀ·ys: [[1,1],[-1,-1]]
  ∂    -- diagonals: [[1],[1,-1],[-1]]
mΣ     -- map sum: [1,0,1]

```

# Answer
> 2 votes
# Matlab, 33 bytes

```
@(x,y)sum(spdiags(flip(x').*y),1)

```

Try it online!

Creates a matrix of all element-wise products of the inputs, then sums along the diagonals. The `,1` at the end forces matlab to sum along the correct direction when one of the input vectors has length 1.

In Octave `spdiags` does not work for vectors, resulting in an error when one of the inputs has length 1. Matlab 2016b or newer is required for the explicit expansion of the element-wise product.

# Answer
> 2 votes
# Itr, 6 bytes

`##C*µS`

reads two lists from standard input, returns a list

online interpreter

## Explanation

```
##     ; read two lists from standard input
  C    ; go through all diagonals of the Cartesian product
   *   ; multiplying the elements from the two lists
    µS ; sum up the diagonals
       ; implicit output

```

# Answer
> 1 votes
# Ruby, 83 bytes

Almost directly pulled out of an answer I did earlier regarding expanding roots into a polynomial.

```
->a,b{q=a.map{|c|r=b.map{|e|e*c};b=[0]+b;r}
q.pop.zip(*q).map{|e|(e-[p]).reduce:+}}

```

# Answer
> 1 votes
# Python, 90 bytes

```
lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in range(k+1))for k in range(len(p+q)-1)]

```

# Answer
> 1 votes
## JavaScript (ES6), 64 bytes

```
(a,b)=>a.map((n,i)=>b.map((m,j)=>r[j+=i]=m*n+(r[j]||0)),r=[])&&r

```

Returns the empty array if either input is empty. Based on my answer to Polynomialception.

# Answer
> 1 votes
# Julia, ~~62~~ 55 bytes

```
~=endof
p%q=[sum(diag(p*rot180(q'),-k))for k=1-~q:~p-1]

```

Try it online!

# Answer
> 1 votes
## Clojure, 104 bytes

```
#(vals(apply merge-with +(sorted-map)(for[i(range(count %))j(range(count %2))]{(+ i j)(*(% i)(%2 j))})))

```

Merging to `sorted-map` guarantees that values are returned in the correct order. I wish there were a few more test cases.

# Answer
> 1 votes
# Mathematica, 28 bytes

Definitely, Mathematica has built-in for *LinearConvolution (like Polynomial Multiplication) of 2 length-limited lists*.

Try it online!

```
ListConvolve[#,#2,{1,-1},0]&

```

---
Tags: code-golf, math, array, number-theory, polynomials
---


# Question
Title: Find the conflict-free sitting arrangement
**Party time!** All of your guests are sitting around a round table, but they have very particular seating requirements. Let's write a program to organize them automatically!

Guests are represented by letters: Female guests are uppercase, males are lowercase. Couples have the same letter, one lower and one upper, like `gG`, who just had their golden marriage (congrats!).

**The rules**

1. Neither place a male between two other males nor a female between two other females.
2. Couples must sit next to each other.
3. Alphabetically adjacent letters of the same sex are rivals! Never place two rivals next to each other (like `BA`) or a rival next to the partner of an attendant partner (like `bBc`, but `xaBcz` is fine, because none of them have jealous partners at the party). Answering a comment: `A`and `Z` are not adjacent in any alphabet I'm aware of. (-;

## I/O

You may take input as either a string or a list of letters `[a-zA-Z]` <sub>\*(or, only if your language of choice has no characters, integers from 1 to 52 representing them, males are even, females are odd :-)</sub>, which will always be unique (i.e. no duplicates). Remember: this is a *round* table, so ensure that your answer takes wrapping into account.

Your output has to be at least one of all possible table arrangements for the input. Where the cut is doesn't matter. If no valid arrangements exist for the input, give an output of your choice which is obviously no sitting arrangement, from an ugly program crash over empty output to some polite message (sorry, no extra score for that).

**Examples**

```
A       --> A (boring party, but valid)
BbCc    --> <none>
gdefEDH --> HfdDgeE
OMG     --> <none>
hiJk    --> <none>
hMJkK   --> hJMkK
NoP     --> NoP
rt      --> rt
qQXZxyz --> <none>
BIGbang --> bIgGanB

```

*(P.S.: In case you miss same-sex couples, non-binaries, polycules, and such – I like those at my personal party, but not in this challenge, to keep it simple.)*

# Answer
# Ruby, 151 bytes

```
f=->x{[x,x[1..-1]+x[0]].any?{|g|a=g.upcase
g=~/[a-z]{3}|[A-Z]{3}/||a=~/(.).+\1/||a.bytes.each_cons(2).any?{|a,b|(a-b).abs==1}}?f[x.chars.shuffle*'']:x}

```

Try it online!

Shuffles input until valid, if can't find shuffles forever as undefined behavior
> 2 votes

# Answer
# Python3, 486 bytes:

```
R=lambda a,b:chr(ord(a)+1)!=b and chr(ord(a)-1)!=b
K=lambda a,b:len(a)<2or a[-2].islower()!=b.islower()
V=lambda a,i:K(a,i)and R(a[-1],i)and(len(a)<2 or R(a[-2],i))
def f(s):
 q=[(i,{*s}-{i})for i in s]
 for a,b in q:
  if not b:
   if V(a,a[0]):return a
   continue
  if(T:=a[-1].upper())in b:
   if K(a,T):q+=[(a+T,b-{T})];q+=[(T+a,b-{T})]*(len(a)==1)
  elif(T:=a[-1].lower())in b:
   if K(a,T):q+=[(a+T,b-{T})];q+=[(T+a,b-{T})]*(len(a)==1)
  else:q+=[(a+i,b-{i})for i in b if V(a,i)]

```

Try it online!

A little long, but not naive brute force.
> 2 votes

# Answer
# Jelly, ~~49~~ 37 bytes

```
O-ṫ?3;Od32ạƝS‘1¦Ʋ3Ƥ;ạƝ’Ʋ;ŒuĠIỊƲȦ
Œ!ÇƇ

```

Try it online!

(shows just one example for each case for brevity)

*Thanks to @JonathanAllan for saving 2 bytes!*

A pair of monadic links taking a list of characters and returning a list of lists of characters. Returns all possible arrangements except those where a couple is split across the join.

Handling inputs with length 1 and 2 added more complexity than I would have expected!

## Explanation (outdated)

```
ŒuĠIỊ;O.ịjƊ;-$L>2Ɗ?:96E3Ƥ;%32IASƲ3Ƥ;IỊƲƲ¬ƲȦ  # Helper link: takes a list of characters and returns 1 if it’s a valid arrangement and 0 if not
Œu                                           # Convert to upper case
  Ġ                                          # Indices of like-members (partners here) grouped together
   I                                         # Increments within each group
    Ị                                        # <= 1 (overall, this tests for rule 2; i.e. indices of partners are adjacent
     ;                                   Ʋ   # Concatenate to the following, applied to the original helper link argument:
      O                                      # - Convert to codepoints
              L>2Ɗ?                          # - If length of list >2:
       .ịjƊ                                  #   - Then: Take the last and first members of the list, and respectively prepend and append them
           ;-$                               #   - Else: Concatenate -1
                                       Ʋ     # - Following as a monad (argument to this is referred to as a in description below):
                   :96                       #   - z div 96
                      E3Ƥ                    #   - Check whether each overlapping infix length 3 has three equal values
                         ;            Ʋ      #   - Concatenate to the result of the following applied to z:
                                Ʋ3Ƥ          #     - Apply the following to each infix of z of length 3:
                          %32                #     - Mod 32
                             I               #     - Increments
                               S             #     - Sum
                              A              #     - Absolute
                                   ;I        #     - Concatenate to increments of z
                                     Ị       #     - Absolute of this <= 1
                                        ¬    # - Not
                                          Ȧ  # Any and all (flattened list contains no zeros)

Œ!ÇƇ                                         # Main link: takes a list of characters and returns a list of lists of characters
Œ!                                           # All permutations
  ÇƇ                                         # Keep those where the helper link returns 1

```

Created with the help of Luminespire.
> 2 votes

# Answer
# 05AB1E, ~~44~~ ~~43~~ 40 bytes

```
œʒā._»A3ãDu«åylDÔsÙÊyĆÇüαyĆlÇüαĆü«Dí)˜≠P

```

Outputs a list of all valid table-arrangements, or `[]` if none are. (If this is not allowed, `ʒ` can be  for +1 byte, so it'll output the first valid result, or `-1` if none are.)

Try it online. (Times out after 60 seconds, only outputting some of the valid results.)

Here a slightly modified version (`A3ãDu«` to `Dáü3Dlsu«`) which is fast enough to output all test cases:
Try it online or verify all test cases.

**Explanation:**

```
œ                 # Get all permutations of the (implicit) input
 ʒ                # Filter the list of permutation-strings by:
  ā._»A3ãDu«å)˜≠P #  Verify rule 1:
  ā               #   Push a list in the range [1,length] (without popping)
   ._             #   For each value, convert it to a rotation of the permutation
     »            #   Join this list of rotation-strings by newlines
      A           #   Push the lowercase alphabet
       3ã         #   Cartesian power of 3 to create all possible lowercase triplets
         D        #   Duplicate this list of triplets
          u       #   Uppercase each string in the copy
           «      #   Merge the lowercase and uppercase lists of triplets together
            å     #   Check for each triplet if it's a substring of the joined
                  #   rotations of the current permutation
             ...  #   (rules 2 and 3)
             )    #   Wrap all checked rules into a list (of lists/values)
              ˜   #   Flatten it
               ≠P #   Verify that none are truthy
  ylDÔsÙÊ)˜≠P     #  Verify rule 2:
  y               #   Push the permutation string again
   l              #   Convert the string to lowercase
    D             #   Duplicate it
     Ô            #   Connected uniquify its characters
      s           #   Swap so the lowercase string is at the top again
       Ù          #   Regular uniquify its characters
        Ê         #   Check that they are NOT the same
         ...      #   (rule 3)
         )˜≠P     #   Same as above: verify that it's not truthy,
                  #   which is why we've used an inverted equals-check `Ê` here
  yĆÇüα)˜≠P       #  Verify rule 3a:
  y               #   Push the permutation string yet again
   Ć              #   Enclose; append its own first character
    Ç             #   Convert it to a list of codepoint integers
     ü            #   For each overlapping pair:
      α           #    Get the absolute difference
       ...        #   (rule 3b)
       )˜≠P       #   Same as above: verify that none are 1
  yĆlÇüαĆü«Dí)˜≠P #  Verify rule 3b:
  y               #   Push the permutation string yet again
   Ć              #   Enclose; append its own first character
    l             #   Convert it to lowercase
     Ç            #   Convert it to a list of codepoint integers
      üα          #   For each overlapping pair: Get the absolute difference
        Ć         #   Enclose this list as well
         ü«       #   Join each overlapping pair of integers together to a string
           D      #   Duplicate this list of integer-strings
            í     #   Reverse each string in the copy
             )˜≠P #   Same as above: verify that none are "01"
                  # (after which the filtered list is output implicitly)

```
> 1 votes

# Answer
# Charcoal, ~~158~~ ~~133~~ ~~131~~ 114 bytes

```
≔§θ⁰η⊞υηＦυ«≔⁻⪪θ¹⪪ι¹ζＦ∨ζη«≔⁺κιδ¿∨‹Ｌδ³﹪ΣＥ…δ³№αλ³¿⬤⁻ζ⟦κ⟧¬№↥⁻ιη↥λ¿⊖↔⁻℅↥κ℅↥§ι⁰¿ζ⊞υδ¿∨‹Ｌι³﹪ΣＥ…⁺§ι⁰⮌ι³№αλ³¿¬№↥✂ι¹±²¦¹↥η⟦ι

```

Try it online! Link is to verbose version of code. Always places the first guest last but will output each solution twice, once with the guests in reverse order. Explanation:

```
≔§θ⁰η

```

Get the first guest.

```
⊞υηＦυ«

```

Start a breadth-first search with just the first guest seated so far.

```
≔⁻⪪θ¹⪪ι¹ζ

```

Get the unplaced guests. (There is an alternative way of doing this using the newer version of Charcoal on ATO which is the same length but allows for a two byte saving later on.)

```
Ｆ∨ζη«

```

If there are unplaced guests, then loop over the guests, otherwise just check the first guest can sit after the last guest.

```
≔⁺κιδ

```

Get the updated placement.

```
¿∨‹Ｌδ³﹪ΣＥ…δ³№αλ³

```

Except on the first pass, check that this doesn't cause there to be three men or women in a row, by checking that the number of the last three guests which are women is not a multiple of 3. (The two guests sitting on either side of the first guest are checked later.)

```
¿⬤⁻ζ⟦κ⟧¬№↥⁻ιη↥λ

```

Check that this doesn't separate a guest from their spouse. (The first guest's spouse is checked later.)

```
¿⊖↔⁻℅↥κ℅↥ε

```

Check that this doesn't place a guest next to a rival.

```
¿ζ

```

If there are more guests to check, then...

```
⊞υδ

```

... save the updated placement for later processing.

```
¿∨‹Ｌι³﹪ΣＥ…⁺§ι⁰⮌ι³№αλ³

```

Check that the first guest is not the middle of three men or women in a row.

```
¿¬№↥✂ι¹±²¦¹↥η

```

Check that the first guest is sitting next to their spouse (if present).

```
⟦ι

```

Output the found placement on its own line.
> 1 votes

# Answer
# sed `-E`,  ~~455~~  448 bytes

(theoretically 447 bytes, see explanation, but who cares as long as `sed` beats `python`?!)

I finally added my own reference implementation using `sed` just because regex-golfing is fun.

```
G
s/./&_-/
:1
s/(\S*)_(\S*)-(\S)(\S*\n)/\1\3_-\2\4\1_\2\3-\4/
t1
s/[-_]//g
h
:2
g
/^$/q
s/\S*.//
x
s/\n.*//
s/(..)?.+/aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ #:&\1/
:r
/:#/b4
/^(..)*(.)(.)(.)(.).*(\2\4|\3\5\3\2\5|\2\3\4|\3\4\5|\2\5\4)/b2
/(.).(..)*(.).(..)*(.).* .*(\1\3\5|\1\5\3|\3\1\5)/b2
:3
s/ (.*:)(.)/ \2\1/
t3
s/(\S*):/:\1/
br
:4
s/^((..)*)(.)(.)(.*(\3\4|\4\3))/\1\5/
t4
/^(..)*(.)(.).*(\2.+\3|\3.+\2)/b2
s/.*#(..)?(...*)/\2/

```

It's brute force, with the `1` loop producing all combinations of guests, ignoring duplicates in favor of size over speed. Yes, you could save one more byte with `s/^/_-/` in line two, but this will create so extremely amounts of duplicates that it will time out even for quite small parties.

The `2` loop takes one combination after another from the hold space to test it. I need to waste a lot of bytes to teach `sed` the alphabet, but at the same time I can close the round table by duplicating the first two guest at the end. Here I originally had a giant regex for the rival test and another regex for the three-of-the-same-sex-test, both backwards and forwards. But then I discovered that the extra bytes for reverting the string in loop `3` and using loop `r` to check the reversed order pays out by having only half of the expressions.

The test for couples sitting apart was more tricky: A simple regex check won't work, because if they are at the first two seats, they will look like sitting apart because of the first partner reappearing on the other end. I solved it by removing couples I found sitting next to each other from the alphabet in loop `4` before testing. I wonder if there are still some bytes to save!

Try it online!
> 1 votes

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


# Question
Title: How can I shorten a C code that repeatedly outputs a number?
I wrote a code that separates the numbers from 1 to 9999 by comma

```
void p(n){printf("%d,",n);if(n<9999){p(n+1);}}main(){p(1);}

```

Is there a way to make this short code without using a repeat statement?

# Answer
# C (gcc), 40 bytes by Sisyphus, exit by stack overflow

```
i;main(){main(dprintf(i++<9999,"%d,"));}

```

Try it online!

# C (gcc), 41 bytes by dingledooper

```
i;main(){++i<1e4&&main(printf("%d,",i));}

```

Try it online!

# C (gcc), 42 bytes, original

```
main(i){i<1e4&&main(i+1,printf("%d,",i));}

```

Try it online!

`main` can be used to recurse
> 16 votes

# Answer
# C (gcc) (Linux only), 31 bytes

```
main(){system("seq -s, 9999");}

```

Try it online!
> 14 votes

# Answer
# Python 3, 30 bytes by Karl Knechtel

```
print(*range(1,10000),sep=',')

```

Try it online!

# Python 3, 36 bytes by onetoinfinity

```
print(str(list(range(10000)))[4:-1])

```

Try it online!

# Python 3, 39 bytes by UndoneStudios

```
i=0
while i<1e5:print(end='%d,'%i);i+=1

```

Try it online!

# Python 3, 40 bytes by Lemon

```
print(",".join(map(str,range(1,10000))))

```

Try it online!
> 2 votes

# Answer
# C# 71 bytes

~~`Console.WriteLine(string.Join(",",Enumerable.Range(1, 999).ToList()));`~~

Saved 14 bytes thanks to Jupotters comment

```
Console.Write(string.Join(",",Enumerable.Range(1,9999)));

```
> 1 votes

# Answer
# PowerShell, 15 bytes

```
1..9999-join","

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~36~~ 35 bytes

```
main=putStr.init.tail$show[1..9999]

```

Try it online!

## Old version

```
main=putStr.init.tail.show$[1..9999]

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 27 bytes

```
Range@9999~StringRiffle~","

```

Try it online!

`Range@9999` (10 bytes) almost does it...
> -2 votes

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


title: Generate Eban Numbers

text:
# Question
Title: Generate Eban Numbers
(Continuing on the number sequences code-golf, here is an interesting sequence)

Eban Numbers (A006933) are the sequence of numbers whose names (in English) do not contain the letter "e" (i.e., "e" is "banned")

The first few numbers in the sequence are:

```
2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56

```

Given an integer `n`, via function argument or STDIN, return the first `n` terms of the Eban Numbers (in numbers) .

Since some answers will involve some sort of string check for character `e`, assume that the maximum value of `n` can be such that the `nth` Eban number is less than 1 Quadrillion.

# Answer
> 7 votes
## ~~Mathematica~~ CJam, ~~108~~ ~~95~~ ~~46~~ ~~35~~ 30 bytes

**Edit:** Ported to CJam! The original and ungolfed Mathematica code is at the bottom and explains the algorithm quite well.

```
li,{)Kb65430s2046sm*$f=0s*ip}/

```

And now I know CJam. :D Thanks to Dennis for some golfing improvements.

After analysing them a bit to determine how many there are below one quadrillion, I came to the conclusion that all eban numbers are basically base-1000 numbers using only a set of 20 digits:

```
0, 2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 62, 64, 66

```

So we enumerate them by converting the input to base 20, picking the right digit from the set and build a base 1000 number from it.

This is how the code works in detail:

```
li                             "Read from STDIN, convert to integer n";
li,                            "Turn into a range array [0 ... n-1]";
li,{                        }/ "For each number execute a block";
li,{)                       }/ "Increment";
li,{)K                      }/ "K is initialised to 20, push that";
li,{)Kb                     }/ "Convert to base 20";
li,{)Kb65430s               }/ "Push a string with possible multiples of 10";
li,{)Kb65430s2046s          }/ "Push a string with possible least significant digits";
li,{)Kb65430s2046sm*        }/ "Take the Cartesian product of the two character
                                arrays, generating the 20 'digits'";
li,{)Kb65430s2046sm*$       }/ "Sort the result";
li,{)Kb65430s2046sm*$f=     }/ "For each digit in our base-20 number, get the
                                base-1000 digit from the list";
li,{)Kb65430s2046sm*$f=0s   }/ "Push a '0' character";
li,{)Kb65430s2046sm*$f=0s*  }/ "Join all the digits, with that '0' as the delimiter";
li,{)Kb65430s2046sm*$f=0s*ip}/ "Convert to an integer and print the result";

```

Here was the original Mathematica code, which doesn't encode the digit list and is hence fairly readable:

```
{0,2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,66}[[IntegerDigits[#,20]+1]]~FromDigits~1000 & /@ Range @ # &

```

# Answer
> 5 votes
# Bash+coreutils+BSDGames package, 79 70 bytes

```
seq $[9**16]|while read n
do number $n|grep -q e||echo $n
done|sed $1q

```

Unfortunately this spawns `number $n|grep -q e` for every number, so is rather slow.

### Output:

```
$ ./eban.sh 5
2
4
6
30
32
$

```

---

### Previous answer - outputs words instead of digits, 43 bytes

```
seq $[9**16]|number -l|grep -v [e.]|sed $1q

```

This outputs each term written in words:

```
$ ./eban.sh 5
two
four
six
thirty
thirty-two
$

```

A bit faster, because each process is only spawned once.

---

# Much faster, no dependence on cheaty `number`, 77 bytes

```
t=0{0,3,4,5,6}{0,2,4,6}
eval echo $t$t$t$t$t|tr \  '
'|sed "s/^0*//;$[$1+1]q"

```

This one uses bash brace expansion to generate all (according to my thinking) eban numbers up to 10^15. Looking at each group of 3 digits, the units digit must be one of {zero,two,four,six}, the tens digit must be one of {zero,thirty,forty,fifty,sixty}, and the hundreds digit must be zero. Since *x*-illion contains no e's up to quadrillion, then we can just combine the groups of three digits up to one quadrillion. The only exception is zero which must be skipped.

So we simply build a brace expansion to generate all these numbers. There are thus 205-1 of them (3.2 million). Evaluating the full bash brace expansion takes less than 5 seconds on my VM.

The `sed` expression just strips off leading zeros and counts to n.

### Output:

```
$ time ./eban.bash 5

2
4
6
30
32

real    0m4.065s
user    0m3.724s
sys 0m0.276s
$ ./eban.bash 10000000 | wc -w
3199999
$ ./eban.bash 3199999 | tail -5
66066066066056
66066066066060
66066066066062
66066066066064
66066066066066
$

```

# Answer
> 2 votes
## Ruby, ~~128~~ ~~121~~ 119 bytes

```
f=->n{a=[]
i=0
(j=i+=2
b=p
(m=j%t=1000
b=b||m%2>0||m%10==8||m>9&&m<30||m>69
j/=t)while j>0
a<<i if !b)while a.size<n
a}

```

I'm basically just checking groups of three digits for numbers that contain `e`s, because none of `{thousand, million, billion, trillion, quadrillion}` contains an `e`.

# Answer
> 2 votes
## Perl - 78

Here is a Perl one-liner to do it.

```
perl -MLingua::EN::Numbers=num2en -nE'while($n<=$_){$n++&&say$i if num2en($i)!~/e/;$i++}' <(echo 5)

```

It is 50 characters plus 1 for the `M`, 1 for the `n`, and 26 for `Lingua::EN::Numbers=num2len`.

Using Lingua::EN::Numbers from CPAN. Here are instructions for installing CPAN modules.

# Answer
> 1 votes
# Vyxal, 66 bitsv2, 8.25 bytes

```
Þ∞'∆ċ\ec¬;Ẏ

```

Try it Online!

Bitstring:

```
001001110101101011111000111110011011000101110000000110101001010010

```

```
Þ∞'∆ċ\ec¬;Ẏ
Þ∞           # infinite list of integers
  '      ;   # filter by
   ∆ċ\ec¬    # cardinal of the number does not contain 'e'
          Ẏ  # slice to length of input

```

Created with the help of Luminespire.

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


title: The longest "Hello World!" program

text:
# Question
Title: The longest "Hello World!" program
I was seen multiple shortest "Hello World!" program, but this is the **longest** program.

**The Rules**

* Each submission must be a full program.
* This must be non-interpreted language (for example, JavaScript, Python, HTML, etc.)
* Target OS must be Windows, Mac, Linux or MS-DOS.

**The challenge**

* Writing a **longest** Hello World program.

# Answer
# C (gcc) (little-endian), 9,624,671,272,932,611,623 bytes

```
#include<string.h>
main(){char x[14];long i,j;/* i++; repeated 2406167339672739884 times */ /* j++; repeated 478560413000 times */memcpy(x,&j,8);memcpy(x+5,&i,8);puts(x);}

```

Try an equivalent version online!

For some reason I can't post the full program, so it has been abbreviated in the comments.
> 3 votes

---
Tags: hello-world
---


title: Divisor chain counts (1 3 3 7 ...)

text:
# Question
Title: Divisor chain counts (1 3 3 7 ...)
The divisors of a natural number form a poset under the relation of "a divides b?", \\$a | b\\$. This challenge is to produce the number, \\$C\\$, of non-empty chains of such posets for natural numbers, \\$N\\$.

This is A253249 in the Online Encyclopedia of Integer Sequences.

That may sound complicated, but it's not really, let's look at an...

#### Example

For \\$N=28\\$ the divisors are \\$\\{1, 2, 4, 7, 14, 28\\}\\$ and the number of non-empty chains is \\$C(28) = 31\\$. The non-empty chains are these subsets of those divisors:

$$\\{1\\}, \\{2\\}, \\{4\\}, \\{7\\}, \\{14\\}, \\{28\\}$$ $$\\{1, 2\\}, \\{1, 4\\}, \\{1, 7\\}, \\{1, 14\\}, \\{1, 28\\}, \\{2, 4\\},$$ $$\\{2, 14\\}, \\{2, 28\\}, \\{4, 28\\}, \\{7, 14\\}, \\{7, 28\\}, \\{14, 28\\}$$ $$\\{1, 2, 4\\}, \\{1, 2, 14\\}, \\{1, 2, 28\\}, \\{1, 4, 28\\}, \\{1, 7, 14\\},$$ $$\\{1, 7, 28\\}, \\{1, 14, 28\\}, \\{2, 4, 28\\}, \\{2, 14, 28\\}, \\{7, 14, 28\\},$$ $$\\{1, 2, 4, 28\\}, \\{1, 2, 14, 28\\}, \\{1, 7, 14, 28\\}$$

These chains are those non-empty subsets of \\$\\{1, 2, 4, 7, 14, 28\\}\\$ such that all pairs of elements \\$\\{a, b\\}\\$ satisfy either \\$a|b\\$ or \\$b|a\\$ \- that is one is a divisor of the other.

Since \\$2\\$ does not divide \\$7\\$ **and** \\$7\\$ does not divide \\$2\\$, no chain has a subset of \\$\\{2, 7\\}\\$.

Similarly no chain has a subset of either \\$\\{4, 7\\}\\$ or \\$\\{4, 14\\}\\$.

Furthermore the empty chain, \\$\emptyset = \\{\\}\\$, is not counted.

#### I/O

You may take input and give output using defaults.
\\$N\\$ is guaranteed to be a positive integer, \\$N \ge 1\\$.

#### Tests

The first \\$360\\$ values are:

```
1, 3, 3, 7, 3, 11, 3, 15, 7, 11, 3, 31, 3, 11, 11, 31, 3, 31, 3, 31, 11, 11, 3, 79, 7, 11, 15, 31, 3, 51, 3, 63, 11, 11, 11, 103, 3, 11, 11, 79, 3, 51, 3, 31, 31, 11, 3, 191, 7, 31, 11, 31, 3, 79, 11, 79, 11, 11, 3, 175, 3, 11, 31, 127, 11, 51, 3, 31, 11, 51, 3, 303, 3, 11, 31, 31, 11, 51, 3, 191, 31, 11, 3, 175, 11, 11, 11, 79, 3, 175, 11, 31, 11, 11, 11, 447, 3, 31, 31, 103, 3, 51, 3, 79, 51, 11, 3, 303, 3, 51, 11, 191, 3, 51, 11, 31, 31, 11, 11, 527, 7, 11, 11, 31, 15, 175, 3, 255, 11, 51, 3, 175, 11, 11, 79, 79, 3, 51, 3, 175, 11, 11, 11, 831, 11, 11, 31, 31, 3, 175, 3, 79, 31, 51, 11, 175, 3, 11, 11, 447, 11, 191, 3, 31, 51, 11, 3, 527, 7, 51, 31, 31, 3, 51, 31, 191, 11, 11, 3, 703, 3, 51, 11, 79, 11, 51, 11, 31, 79, 51, 3, 1023, 3, 11, 51, 103, 3, 175, 3, 303, 11, 11, 11, 175, 11, 11, 31, 191, 11, 299, 3, 31, 11, 11, 11, 1007, 11, 11, 11, 175, 11, 51, 3, 447, 103, 11, 3, 175, 3, 51, 51, 79, 3, 175, 11, 31, 11, 51, 3, 1471, 3, 31, 63, 31, 31, 51, 11, 79, 11, 79, 3, 703, 11, 11, 51, 511, 3, 51, 11, 175, 31, 11, 3, 527, 11, 51, 11, 31, 3, 527, 3, 191, 51, 11, 31, 175, 3, 11, 31, 527, 3, 51, 3, 31, 51, 51, 11, 2175, 7, 51, 11, 31, 3, 175, 11, 79, 79, 11, 11, 703, 11, 11, 11, 191, 11, 175, 3, 175, 11, 51, 3, 527, 3, 11, 175, 31, 3, 51, 11, 1023, 11, 51, 11, 831, 31, 11, 11, 79, 11, 299, 3, 31, 31, 11, 11, 1471, 3, 31, 11, 175, 11, 175, 15, 79, 51, 11, 3, 175, 3, 175, 79, 447, 3, 51, 11, 31, 51, 11, 3, 2415

```

#### Scoring

This is , so try to make code in as few bytes as possible in your language of choice. Your score is the number of bytes of your program or function.

# Answer
> 8 votes
# Jelly, ~~10~~ ~~9~~ 7 bytes

```
ÆḌƬFLḤ’

```

Try it online!

```
  Ƭ        Loop while unique:
ÆḌ         Recursively vectorizing proper divisors (empty list if 1).
  ƬF       Deep flatten the full history of results,
    L      take the length,
     Ḥ     double (to account for the chains including the original n),
      ’    and decrement (to not double count the trivial chain of just {n}).

```

# Answer
> 8 votes
# Python 3, 45 bytes

```
f=lambda n,d=1:d//n or-~f(d)*(n%d<1)+f(n,d+1)

```

Try it online!

**51 bytes**

```
f=lambda n:1+sum(1+f(d)for d in range(1,n)if n%d<1)

```

Try it online!

# Answer
> 6 votes
# Nekomata \+ `-n`, 6 bytes

```
ĎSᵉti¦

```

Attempt This Online!

```
ĎSᵉti¦
Ď       Divisors
 S      Find a subset such that
  ᵉt      removing the first element
     ¦    is divisible by
    i     removing the last element

```

`-n` counts the number of solutions.

# Answer
> 6 votes
# , 44 bytes

```
`?`=\(n,d=1)`if`(d<n,(n?d+1)+(1+?d)*!n%%d,1)

```

Attempt This Online!

Port of @xnor's Python answer.

# Answer
> 5 votes
# 05AB1E, 10 bytes

```
ÑæʒRüÖP}g<

```

Try it online!

```
Ñ      # divisors of N
æ      # subsets
ʒ      # keep those such that
 R      # when reversed
 üÖ     # whether each term divides the previous one?
 P      # all
}
g      # and take the length
<      # -1

```

# Answer
> 5 votes
# Rust, ~~63~~ 54 bytes

## (#2)

Thanks to @att for the massive –9 bytes!

```
fn f(n:i64)->i64{(1..n).fold(1,|a,d|a-(1>>n%d)*!f(d))}

```

Attempt This Online!

# Rust, 63 bytes

## (#0)

Originally based on @xnor's Python answer. Straightforward functional implementation of their idea.

```
fn f(n:u64)->u64{(1..n).filter(|d|n%d<1).fold(1,|a,d|1+a+f(d))}

```

Attempt This Online!

# Rust, 63 bytes

## (#1)

Works just like #0, but the filter is inlined into the fold.

```
fn f(n:u64)->u64{(1..n).fold(1,|a,d|if n%d<1{1+f(d)}else{0}+a)}

```

Attempt This Online!

Previous attempts and ideas can be found in the ATO links. It took me a while to realize that the descriptive symbolic idea of using itertools, powerset and so on looks extremely cool but just isn't suited for code golf at all if less readable solutions exist.

They all work the same way, with the exception that the first two functions evaluate recursively lazily and the last one eagerly (Infinite recursion is prevented by not calling the closure when the iterator is empty, providing this as a base case). The performance difference is noticeable. ~~I'm sure there must be a way to golf one of these even further (more likely the latter two than the former).~~ It's quite likely that the golfing potential has now been exhausted.

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

*-11 bytes thanks to @Neil!*

Returns the \\$n\\$-th term.

```
f=(n,d=n)=>d--&&f(n,d)-!(n%d)*~f(d)

```

Try it online!

Or try a faster version (36 bytes) that generates the 360 first values listed in the challenge.

### Commented

```
f = (        // f is a recursive function taking:
  n,         //   n = input
  d = n      //   d = current divisor candidate
) =>         //
d-- &&       // if d is not 0 (decrement it afterwards):
  f(n, d) -  //   do a 1st recursive call with the updated d
  !(n % d) * //   test whether d is a divisor of n
             //   if not, ignore the result of ...
  ~f(d)      //   ... a 2nd recursive call with n = d
             //   (otherwise, increment the final count)

```

# Answer
> 4 votes
# JavaScript (Node.js), 37 bytes

```
f=(n,p=n)=>--p?f(n,p)+!(n%p)*-~f(p):1

```

Try it online!

Found independent, I'd just leave it here

# Answer
> 4 votes
# Uiua, 18 bytes

```
∧+1+1∵(|1↬2)⊚=0◿⇡.

```

Try it online!

```
∧+1+1∵(|1↬2)⊚=0◿⇡.  input: a positive integer n
⊚=0◿⇡.   proper divisors of n:
  ◿⇡.       n modulo (each of) range of n
  ⊚=0       indices of zeros
∵(|1↬2)  recurse on each
+1         add 1 to each result
∧+1       sum the results and add 1

```

# Answer
> 3 votes
# Retina 0.8.2, 34 bytes

```
.+
$*
+%M!&`^|(1+$)(?<=^\1\1+)|$
¶

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
+%M!&`^|(1+$)(?<=^\1\1+)|$

```

Calculate \\$ A253249(i) = 1 + \sum\_{j|i} 1 + A253249(j) \\$. The `+%` repeatedly processes inner terms until they become empty. The `!&` outputs overlapping matches. The `(1+$)(?<=^\1\1+)` matches factors of \\$ i \\$, and the leading and trailing empty match applies the two \\$ 1 + \\$ terms somehow... not quite sure how that works, but I'm not complaining. The result is actually the number of newlines generated by the repeated factorisation.

Convert to decimal.

# Answer
> 2 votes
# Ruby, ~~79~~ 38 bytes

```
f=->n{1+(1...n).sum{|r|1[n%r]*-~f[r]}}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 21 bytes

```
ＦＮ⊞υ↨Ｅι∧¬∧κ﹪ικ⊕§υκ¹Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first \\$ n \\$ values starting at \\$ N=0 \\$ whose value is considered to be \\$ 0 \\$. Explanation: \\$ A253249(i) = \sum\_{j|i} 1+A253249(j) \\$ where \\$ 0 \\$ is considered to divide any integer.

```
ＦＮ

```

Loop \\$ n \\$ times.

```
⊞υ↨Ｅι∧¬∧κ﹪ικ⊕§υκ¹

```

Calculate \\$ A253249(i) \\$ using the above recurrence relation.

```
Ｉυ

```

Output the results.

22 bytes for a 1-indexed version:

```
ＦＮ⊞υ⊕↨Ｅι∧¬﹪⊕ι⊕κ⊕§υκ¹Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first \\$ n \\$ values. Explanation: \\$ A253249(i+1) = 1 + \sum\_{j+1|i+1} 1+A253249(j+1) \\$.

```
ＦＮ

```

Loop \\$ n \\$ times.

```
⊞υ⊕↨Ｅι∧¬﹪⊕ι⊕κ⊕§υκ¹

```

Calculate \\$ A253249(i+1) \\$ using the above recurrence relation.

```
Ｉυ

```

Output the results.

# Answer
> 2 votes
# PARI/GP, 31 bytes

```
f(n)=sumdiv(n,d,1+if(d<n,f(d)))

```

Attempt This Online!

# Answer
> 2 votes
# Mathematica, ~~43~~ 28 bytes

Saved 15 bytes thanks to the comment of @alephalpha

---

Golfed version. Try it online!

```
1+Tr[1+#0/@Most@Divisors@#]&

```

Ungolfed version. Try it online!

```
f[n_] := f[n] = With[{divisors = Divisors[n]}, Total[(1 + If[# < n, f[#], 0]) & /@ divisors]];
Table[Print[i, " -> ", f[i]], {i, 1, 30}]

```

# Answer
> 2 votes
# Japt v1.4.5 `-x`, ~~15~~ 10 bytes

```
â à ®ä!v ×

```

Try it

Thanks to @Shaggy for saving 5 bytes by using an older version of Japt ( improvements specified inside parens )

```
â       divisors( now sorted )
à       combinations( now without empty combination )
®       map by
ä       map each consecutive pair of a combination
!v      divisible? ( now with argument swapped by prepending ! to function argument)
×       multiply reduce

-x flag to output the sum

```

# Answer
> 2 votes
# Haskell, 38 bytes

```
f n=1+sum[1+f d|d<-[1..n-1],mod n d<1]

```

A simple port of @xnor's python answer

Attempt This Online!

# Answer
> 2 votes
# Desmos, ~~119~~ 118 bytes

```
L=[1...n]
D=L[mod(n,L)=0]
d=D.count
F=D[mod(floor(2k/2^{[1...d]}),2)=1]
f(n)=∑_{k=1}^{2^d-1}0^{mod(F[2...],F).total}

```

Try It On Desmos!

Try It On Desmos! - Prettified

Port of Command Master's answer, so make sure to go upvote that answer as well!

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~51~~ ~~45~~ 44 bytes

```
+/((∘.≤⍨⍳∘⍴)≡0=∘.|⍨)¨¯1↓{,⊃∘.,/⍵,¨⊂⊂⍬}(∪⊢∨⍳)

```

The index origin is set to 1 (⎕IO←1). The number to be analyzed is entered to the right of the code.

Try it on TryAPL.org!

With credit to ngn's prior challenge answer for the short powerset code segment.

---
Tags: code-golf, math, sequence, division
---


title: Hermite interpolation

text:
# Question
Title: Hermite interpolation
We already have a challenge for polynomial interpolation: given a list of points, output the coefficients of the polynomial that passes through them.

Hermite interpolation is a generalization of polynomial interpolation. Instead of just specifying the points that the polynomial passes through, we also specify the higher-order derivatives at those points. If we have \\$n\\$ points, and we specify the value and the first \\$m-1\\$ derivatives at each point, then we can uniquely determine a polynomial of degree less than \\$mn\\$.

For example, the following data uniquely determines the polynomial \\$x^8+1\\$:

| \\$x\\$ | \\$y=x^8+1\\$ | \\$y'=8x^7\\$ | \\$y''=56x^6\\$ |
| --- | --- | --- | --- |
| 0 | 1 | 0 | 0 |
| 1 | 2 | 8 | 56 |
| 2 | 257 | 1024 | 3584 |

## Task

Given an \\$m \times n\\$ matrix \\$\mathbf{A}=(a\_{ij})\_{1\leq i\leq m, \\; 1\leq j\leq n}\\$, find a polynomial \\$p\\$ of degree less than \\$mn\\$ such that \\$p^{(i)}(j) = a\_{i+1,j+1}\\$ for all \\$0 \leq i \< m\\$ and \\$0 \leq j \< n\\$. Here \\$p^{(i)}(j)\\$ denotes the \\$i\\$th derivative of \\$p\\$ evaluated at \\$j\\$.

For example, if \\$\mathbf{A}=\begin{bmatrix}1&0&0\\2&8&56\\257&1024&3584\end{bmatrix}\\$, then \\$p(x)=x^8+1\\$.

You may take input and output in any convenient format.

You may transpose the input matrix if you wish. You may flatten it into a list. You may take \\$m\\$ or \\$n\\$ or both as additional inputs.

Here are some example formats for the output polynomial:

* a list of coefficients, in descending order, e.g. \\$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\\$ is represented as `[24,96,72,16,1]`;
* a list of coefficients, in ascending order, e.g. \\$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\\$ is represented as `[1,16,72,96,24]`;
* taking an additional input \\$k\\$ and outputting the coefficient of \\$x^k\\$;
* a built-in polynomial object.

When the degree of the polynomial is less than \\$mn-1\\$, you may pad the coefficient list with zeros.

When the coefficients are not integers, you may output them as rational numbers, floating-point numbers, or any other convenient format.

This is , so the shortest code in bytes in each language wins.

## Test Cases

Here I output lists of coefficients in descending order.

```
[[1,0,0],[1,0,0]] -> [1]
[[1,2],[0,0]] -> [4,-7,2,1]
[[1,2],[3,4]] -> [2,-2,2,1]
[[0,0,1],[3,11,33]] -> [1,1/2,1,1/2,0,0]
[[1,2],[3,4],[5,6]] -> [3,-14,21,-10,2,1]
[[1,2,3],[4,5,6]] -> [-3/2,9/2,-7/2,3/2,2,1]
[[1,16],[209,544],[1473,2224]] -> [24,96,72,16,1]
[[0,0,0],[0,1,0],[0,0,0]] -> [-1,7,-18,20,-8,0,0,0]
[[1,0,0],[2,8,56],[257,1024,3584]] -> [1,0,0,0,0,0,0,0,1]
[[1,0,0],[0,0,0],[0,0,0]] -> [3/2,-207/16,713/16,-1233/16,1083/16,-99/4,0,0,1]

```

# Answer
# Mathematica, 76 bytes

Mathematica has built-in `InterpolatingPolynomial` to construct an interpolating polynomial that reproduces function values and derivatives.

Try it online!

```
f@m_:=InterpolatingPolynomial[MapIndexed[Join[{#2[[1]]-1},#1]&,m],x]//Expand

```
> 3 votes

# Answer
# Python3, 604 bytes:

```
import math
E=enumerate
def M(p,*P):
 for i in P:
  D={}
  for a,b in i.items():
   for A,B in p.items():D[a+A]=D.get(a+A,0)+b*B
  p=D
 return p
def O(p,*P):
 for i in P:
  for j,k in i.items():p[j]=p.get(j,0)+k
 return p
def f(A):
 z,l,d=zip(*[(i,a[0],a[1:])for i,a in E(A)for _ in a])
 L=[[(a,[i])for i,a in E(l)]]
 c=1
 while len(U:=L[-1])>1:L+=[[(d[min(U[i][1])][c-1]/math.factorial(c)if 0==(D:=z[max(U[i+1][1]+U[i][1])]-z[min(U[i+1][1]+U[i][1])])else(U[i+1][0]-U[i][0])/D,U[i][1]+U[i+1][1])for i in range(len(U)-1)]];c+=1
 return O(*[M({0:a[0][0]},*[{1:1,0:-z[j]}for j in range(i)])for i,a in E(L)])

```

Try it online!
> 2 votes

# Answer
# Charcoal, ~~99~~ 94 bytes

```
ＦＬθＦ⌊θ⊞υι≔Ｅυ¬κη≔×⁰ηζＦＬυ«≔Ｅυ⎇⁼κ§υ⁺λι∕§§θκι∨Π…·¹ι¹∕⁻§ε⊕λ§ελ⁻§υ⁺λικεＵＭζ⁺κ×§ε⁰§ηλＵＭη⁺§η⊖λ×±§υικ»Ｉζ

```

Try it online! Link is to verbose version of code. Outputs the polynomial coefficients in ascending order of degree. Explanation:

```
ＦＬθＦ⌊θ⊞υι

```

Create a list of x-coordinates `xᵢ` where each coordinate is repeated by the number of times equal to the number of differentials provided.

```
≔Ｅυ¬κη

```

Create a unit polynomial.

```
≔×⁰ηζ

```

Create a zero polynomial, which will be the running total.

```
ＦＬυ«

```

Loop over each row of the divided difference table.

```
≔Ｅυ⎇⁼κ§υ⁺λι∕§§θκι∨Π…·¹ι¹∕⁻§ε⊕λ§ελ⁻§υ⁺λικε

```

Calculate the row. For each cell, if the x-coordinates of the triangle that generates this cell are all equal then divide the appropriate derivative of that coordinate by the factorial of the row number, otherwise divide the difference of the two cells from the previous row by the difference of the x-coordinates. (Some additional bogus entries are also calculated but none of them affect the final result.)

```
ＵＭζ⁺κ×§ε⁰§ηλ

```

Multiply the (originally unit) polynomial by the first entry in the row and add it to the running total.

```
ＵＭη⁺§η⊖λ×±§υικ

```

Multiply the (originally unit) polynomial by `x-xᵢ`. (This generates a bogus result on the last pass but since it won't be used this is irrelevant.)

```
»Ｉζ

```

Output the final total polynomial.

97 bytes for a version that accepts a list of x-coordinates as an additional argument, rather than assuming that they're 0-indexed:

```
ＦηＦ⌊θ⊞υι≔Ｅυ¬κη≔×⁰ηζＦＬυ«≔Ｅυ⎇⁼κ§υ⁺λι∕§§θ÷λＬ⌊θι∨Π…·¹ι¹∕⁻§ε⊕λ§ελ⁻§υ⁺λικεＵＭζ⁺κ×§ε⁰§ηλＵＭη⁺§η⊖λ×±§υικ»Ｉζ

```

Try it online! Link is to verbose version of code.
> 2 votes

# Answer
# Jelly, ~~71~~ 63 bytes

```
I÷ḢṛṪḢ?@"Z}
FJḶṚ1ị+",Ʋ:L_/żṪ©ị"¥ɗ÷"J’!Ɗ$Żç\Ḣ€Ḋ×"®Ḣ1;$Ż_×ɗ\Ṗ¤F€S

```

Try it online!

A pair of monadic links that takes a list of lists and returns a list of polynomial coefficients.

The argument holding the input is transposed and then rotated both vertically by 1 such that the 0th column appears at the end. This is done to best fit with Jelly’s 1-indexing and the fact that zero refers to the last column. The output starts with the zeroth coefficient and works upwards.

Updated to a more efficient algorithm, but still based on the one on the Wikipedia page.

## Explanation

```
I÷ḢṛṪḢ?@"Z}                                          # Helper link: takes the current list of values for the divided difference algorithm on the left, and a list of the x differences and potential relevant derivatives on the right and returns the next column for the divided difference algorithm
I                                                    # Increments
 ÷                                                   # Divided by the right argument
  Ḣ                                                  # Head (effectively gives the differences divided by the x differences)
       @"Z}                                          # Take each pair of x differences and possible relevant derivatives as the left argument and the relevant divided difference as the right and do the following for each:
     Ḣ?                                              # - If the x-difference was non-zero:
   ṛ                                                 # - Then the divided difference
    Ṫ                                                # - Else the relevant derivative

FJḶṚ1ị+",Ʋ:L_/żṪ©ị"¥ɗ÷"J’!Ɗ$Żç\Ḣ€Ḋ×"®Ḣ1;$Ż_×ɗ\Ṗ¤F€S  # Main link: takes a matrix as described above and returns a list of coefficients
F                                                    # Flatten
 J                                                   # Sequence along flattened matrix from 1 to length
  Ḷ                                                  # For each of these, sequence from 0 to value minus 1
   Ṛ                                                 # Reverse
         Ʋ                                           # Following as a monad (argument z):
    1ị                                               # - First list within z
      +"                                             # - Add zipped to z (so each member of first list in z increases by zero, each member of second list of z increases by 1, etc.)
        ,                                            # - Pair with z
          :L                                         # Integer divide by length of matrix (m)
                    ɗ                                # Following as a dyad (see below for right argument details, referred to as y)
            _/                                       # - Reduce by subtraction (gives x differences)
              ż                                      # - Zip with
                   ¥                                 # - Following as a dyad:
               Ṫ©                                    #   - Tail (effectively z from above but after the integer divide bit), also copying this for later
                 ị"                                  #   - Index zipped into right argument
                           $                         # y, which will be the result of the following applied as a monad to the original argument (the matrix)
                     ÷"   Ɗ                          # - Divide zipped by the result of the following applied as a monad to the original matrix:
                       J                             #   - Sequence along original matrix rows
                        ’                            #   - Decrease by 1
                         !                           #   - Factorial
                            Ż                        # Prepend zero
                             ç\                      # Reduce using the helper link, collecting all intermediate values
                               Ḣ€                    # Head of each
                                 Ḋ                   # Remove the original zero
                                  ×"®          ¤     # Multiply zipped by the result of applying the following to the register value stored earlier
                                     Ḣ               # - Head
                                      1;$            # - Prepend 1 ($ used to prevent the ¤ only tracking back to the 1)
                                            ɗ\       # - Reduce using the following, collecting up intermediate values
                                         Ż           #   - Prepend zero
                                          _×         #   - Subtract the result of multiplying the previous list by the incoming x value
                                              Ṗ      # - Remove the last list member
                                                F€   # Flatten each (deals with the 1 introduced above that is not a list)
                                                  S  # Sum

```

Created with the help of Luminespire.
> 2 votes

# Answer
# PARI/GP, 52 bytes

```
f(a,m)=a/matrix(#a,,k,i,derivn(x^k--,i--%m)%(x-i\m))

```

Attempt This Online!

Takes input as a flatten list and \\$m\\$. Outputs a list of coefficients in ascending order.

Using the fact that Hermite interpolation is a linear map. We can construct a \\$mn\times mn\\$ matrix, whose entries are the \\$i\\$th derivative of \\$x^k\\$ evaluated at \\$x=j\\$, where \\$0\leq i\< m\\$, \\$0\leq j\< n\\$, and \\$0\leq k\< mn\\$. Then we can multiply the flattened input by the inverse of this matrix.
> 2 votes

# Answer
# , 149 bytes

```
\(y,n,m,o=m*n-1,z=y,v={},`^`=c){for(i in 0:o){v=v^0+(z=ifelse(x<-i:o%/%n-(j=0:(o-i)%/%n),diff(z)/x,y[i+1,j+1]/factorial(i)))[1]*T;T=0^T-T^0*i%/%n};v}

```

Attempt This Online!

A function taking the matrix, n and m as arguments and returning a vector of coefficients, starting from the zeroth.
> 2 votes

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