title: Repeat Values In Array

text:
# Question
Title: Repeat Values In Array
Given two arrays of non-negative integers \\$A = \[A\_1,A\_2,\ldots,A\_n\]\\$ and \\$R = \[R\_1,R\_2,\ldots,R\_n\]\\$ which are equal in length, return an array which has the element \\$A\_1\\$ repeated \\$R\_1\\$ times, then element \\$A\_2\\$ repeated \\$R\_2\\$ times, all the way up to \\$A\_n\\$.

Standard loopholes are forbidden. As this is , the shortest program wins.

### Test Cases

| \\$A\\$ | \\$R\\$ | Output |
| --- | --- | --- |
| `[1,2,3]` | `[1,2,3]` | `[1,2,2,3,3,3]` |
| `[6,0,0,6]` | `[5,1,1,0]` | `[6,6,6,6,6,0,0]` |
| `[100,100]` | `[0,0]` | `[]` |

# Answer
> 10 votes
# Jelly, 1 byte

```
x

```

Try it online!

# Answer
> 8 votes
# Haskell, 27 bytes

```
(concat.).zipWith replicate

```

Try it online!

These built-ins have long names, but I haven't found anything shorter.

# Answer
> 8 votes
# Raku, 12 bytes

```
(*Zxx*).flat

```

Try it online!

* `xx` is Raku's replication operator. It produces a list of a number of copies of its left argument given by its right argument. (Very conveniently, though irrelevant for this problem, the left-hand side is re-evaluated the requested number of times, so for example `rand xx 10` will produce a list of ten different random numbers.)
* `Z` is the zip "meta-operator." It can be prepended to any other operator to produce a new operator that zips two lists together using the original operator.
* The asterisks make this a "WhateverCode" expression, a short way of defining anonymous functions. The first and second argument to the function will take the place of the first and second asterisk, respectively.
* `.flat` flattens the list of replicated lists.

# Answer
> 8 votes
# , 1 byte

```
#

```

Try it online!

Simple built-in solution: The copy verb.

# Answer
> 8 votes
# , 3 bytes

```
rep

```

Try it online!

In  many functions are vectorized and so is `rep` \- it happens to work correctly for this challenge.

# Answer
> 6 votes
# JavaScript (Node.js), ~~44~~ 43 bytes

−1 thanks to Arnauld.

```
A=>R=>A.flatMap((a,i)=>Array(R[i]).fill(a))

```

Try it online!

# Answer
> 6 votes
# Python 3, ~~42~~ ~~41~~ 40 bytes

```
lambda*a:sum(map(lambda x,*y:x*y,*a),())

```

Try it online!

-1 thanks to Jonathan Allan!

-1 thanks to loopy walt!

# Answer
> 5 votes
# Factor,  ~~27~~  25 bytes

```
[ [ <array> ] 2map-flat ]

```

Try it online!

Takes input as `R A`.

# Answer
> 5 votes
# APL (Dyalog Unicode), 1 byte

```
/

```

Try it online!

# Answer
> 5 votes
# Pyth, 3 bytes

```
r9C

```

Test suite

Takes input as `R,A`.

# Answer
> 5 votes
# Python NumPy, 39 bytes

```
lambda a,b:[0,*b]*1**b[:1]@[(),*zip(a)]

```

Attempt This Online!

Of course, there is also the `repeat` builtin.

### How?

Beside the usual bending over backwards to avoid the explicit numpy import this uses the fact that if we write \\$c\_i = \[b\_i\]\\$ then, formally, \\$c\_1 a\_1 + c\_2 a\_2 + ... + c\_n a\_n\\$ is a dot product. It is mildly tricky to set up an array of equal length sequences because numpy will just create an additional dimension and create an array of scalars. Here we prepend a different length sequence, forcing a ragged array (after using zip to create a list of singleton tuples). To match we must also prepend one value to the length array. The 1\**b\[:1\] factor, mathematically a nop, is there to trigger a coercion cascade to numpy arrays-

# Answer
> 4 votes
# Vyxal, 4 bytes

```
¨£ẋf

```

Try it Online!

This two-byte solution should work, but it seems to bork when the length is an array only of zeros: Try it Online!

# Answer
> 4 votes
# MATL, 2 bytes

```
Y"

```

Try it online! Or verify all test cases.

# Answer
> 4 votes
# Octave, 7 bytes

```
repelem

```

It seem's that TIO's version of Octave doesn't have this built-in.

# Answer
> 4 votes
# Goruby, ~~25~~ 22 bytes

-3 bytes thanks to G B

```
->a,b{a.fl{[_1]*b.sh}}

```

Attempt This Online!

# Ruby, ~~33~~ 31 bytes

-2 bytes thanks to G B

```
->a,b{a.flat_map{[_1]*b.shift}}

```

Attempt This Online!

# Answer
> 3 votes
# Japt, 6 bytes

Takes `R` as the first input.
A byte or 2 could be saved if output could be a 2D-array but I'm guessing a flat array is one of the points of the challenge.

```
cÈÇYgV

```

Try it

```
cÈÇYgV     :Implicit input of arrays U=R & V=A
c          :Flat map U
 È         :Pass each X at index Y through the following function
  Ç        :  Map the range [0,X)
   YgV     :    Index into V

```

# Answer
> 3 votes
# Desmos, 72 bytes

```
f(A,R)=[A[i<=∑_{n=1}^{[1...R.length]}R[n]][1]fori=[0...R.total][2...]]

```

Might post an explanation if I feel like it.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 3 votes
# K (ngn/k), 4 bytes

```
,/#'

```

Try it online!

# Answer
> 3 votes
# C (clang), ~~59~~ 55 bytes

* -2 bytes thanks to @jdt.

```
f(*a,*b,n){for(;n;)~--*b?printf("%d ",*a):a++-b++-n--;}

```

Try it online!

# Answer
> 3 votes
# Brachylog, 9 bytes

```
z⟨kj₎t⟩ˢc

```

Try it online!

*-2 bytes thanks to @DLosc*.

*-1 byte thanks to @Kroppeb*

### Explanation

Given inputs `[a1, …, an]` and `[r1, …, rn]`:

```
z         Zip: [[a1,r1], ..., [an, rn]]
 ⟨    ⟩ˢ   For each sublist [ai, ri]
  k         Take [ai]
     t      Take ri
   j₎       Juxtapose the list [ai] ri times to itself
       c  Concatenate into one list

```

# Answer
> 3 votes
# Julia 1.0, 23 bytes

```
a^b=vcat(fill.(a,b)...)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 9 bytes

```
ＩΣＥθＥ§ηκι

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
   θ        Array of values
  Ｅ         Map over values
      η     Array of counts
     §      Indexed by
       κ    Current index
    Ｅ       Map over implicit range
        ι   Current value
 Σ          Concatenate arrays
Ｉ           Cast to string
            Implicitly print

```

# Answer
> 2 votes
# PowerShell Core, 30 bytes

```
param($a,$r)$r|%{,$a[$i++]*$_}

```

Try it online!

# Answer
> 2 votes
# simply, 87 bytes

The code defines an anonymous function that returns the expected result.
Nothing special here...

```
fn($A$R){$X=[]each$R as$k=>$v;if$v$X=&array_concat($X&array_fill($A[$k]$v))send$X;}

```

## Usage

Just use it normally...
Example using the 2nd test case.

```
$fn = fn($A$R){$X=[]each$R as$k=>$v;if$v$X=&array_concat($X&array_fill($A[$k]$v))send$X;}

// should output: 6,6,6,6,6,0,0
echo &join(call $fn([6,0,0,6], [5,1,1,0]), ',');

```

Since it is an anonymous function, using `call` is required.

## Ungolfed

This code does exactly the same as the golfed version.

This is pretty close to pseudo-code.

```
Set $fn to an anonymous function($A, $R)
Begin.
    Define the variable $result = [].
    Loop through $R as value $value key $key.
    Begin.
        If $value then.
        Begin.
            Set $result to the result of calling &array_concat(
                $result,
                &array_fill($A[$key], $value)
            ).
        End.
    End.

    Return the $result.
End.

```

A little further from pseudo-code...

```
$fn = fn($A, $R) => {
    $result = [];
    foreach $R as $key => $value {
        if $value {
            $result = &array_concat(
                $result,
                &array_fill($A[$key], $value)
            );
        }
    }

    return $result;
};

```

# Answer
> 2 votes
# 05AB1E, 2 bytes

```
ÅΓ

```

Try it online!

# Answer
> 2 votes
# Excel (ms365), 60 bytes

```
=IFERROR(TEXTSPLIT(CONCAT(REPT(A1:C1&"|",A2:C2)),"|",,1),"")

```

---

Or, if you don't mind whole rows as input arrays, for 56 bytes:

```
=IFERROR(TEXTSPLIT(CONCAT(REPT(1:1&"|",2:2)),"|",,1),"")

```

# Answer
> 2 votes
# , 1 byte

```
\

```

Try it online!

Body must be at least 30 characters; you entered 27.

# Answer
> 2 votes
# Pip `-p`, 16 bytes

```
{FA({aRLb}MZab)}

```

Try It Online!

```
{FA({aRLb}MZab)}     ; First argument = A = a
                     ; Second argument = B = b
{              }     ; Create a function that...
          MZab       ; maps a and b (as zipped pairs of elements) to...
    {aRLb}           ; a block that repeats the (first argument) by (second argument)...
 FA(          )      ; and flattens the resulting list
                     ; (after which the list is implicitly printed out)

```

# Answer
> 1 votes
# MathGolf, 7 bytes

```
mÅaam*─

```

Try it online.

Or alternatively, with the input-lists swapped:

```
^mæ~Ä_;

```

Try it online.

**Explanation:**

```
m     # Map over the first (implicit) input-list,
 Å    # using two characters as inner code-block:
  a   #  Wrap it into a list
   a  #  Wrap that into a list
      # (e.g. [6,0,0,6] → [[[6]],[[0]],[[0]],[[6]]])
m*    # Repeat each the second (implicit) input amount of times
      # (e.g. [5,1,1,0] and [[[6]],[[0]],[[0]],[[6]]] →
      #  [[[6,6,6,6,6]],[[0]],[[0]],[[]]])
─     # Flatten it to a single list
      # (e.g. [[[6,6,6,6,6]],[[0]],[[0]],[[]]] → [6,6,6,6,6,0,0])
      # (after which the entire stack is output implicitly as result)

```

Unfortunately, using `m*` on lists `[6,0,0,6]` and `[5,1,1,0]` results in `[30,0,0,0]` and lists `[[6],[0],[0],[6]]` and `[5,1,1,0]` results in `[[30],[0],[0],[0]]` (apparently..). Hence the need for two wraps before we can use `m*`.

```
^        # Zip the two (implicit) input-lists together
         # (e.g. [5,1,1,0] and [6,0,0,6] → [[6,5],[0,1],[0,1],[6,0]]
 m       # Map over each inner pair,
  æ      # using 4 characters as inner code-block:
   ~     #  Pop and push the contents of the pair separately to the stack
    Ä    #  Pop the top, and loop that many times:
     _   #   Duplicate
      ;  #  After the inner loop, discard the top item
         # (after which the entire stack is output implicitly as result)

```

# Answer
> 1 votes
# Husk, 1 byte

Try it online!

Built-in solution. Input is arg1=R, arg2=A

---

# Husk, 5 bytes

```
Σz(↑∞

```

Try it online!

Roll-your-own solution avoiding  built-in.

```
Σz(↑∞
 z     # zip the two inputs together with
  (    #   combination of functions:
    ∞  #   make an infinite list of copies of arg1
   ↑   #   and then take arg2 elements from it;
Σ      # finally, flatten the output

```

# Answer
> 1 votes
# BQN, 1 byte

```
/

```

Try it at BQN REPL

Built-in solution.

---

# BQN, 3 bytes

```
∾⥊¨

```

Try it at BQN REPL

Roll-your-own solution avoiding `/` (Replicate) built-in.

```
   ¨    # Each: for each element of R arg
  ⥊     # Reshape: reshape to a list of L arg copies
 ∾      # Join: and join all the lists together

```

# Answer
> 1 votes
# Red, 51 bytes

```
func[a b][collect[forall a[loop take b[keep a/1]]]]

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), 6 bytes

```
{y#'x}

```

Try it online!

I don't know if this is accepted or not. Take input as `(A);(R)`.

Render output with `,x` for array with only one element `x`, and `!0` for array with no element (aka null duplication).

# Answer
> 1 votes
## Clojure, 21 bytes

```
#(mapcat repeat %2 %)

```

Yay, short built-in names and neat composition!

Try it online!

# Answer
> 1 votes
# Nibbles, 4.5 bytes (9 nibbles)

```
+!$_~.,$_

```

Input is arg1=R, arg2=A

Nibbles has a 'replicate' function, `^`, but it unfortunately does not work on numeric values (the `^` op exponentiates these instead). So we need to use a slightly more convoluted map, returning the value of arg2 for each element of 1..arg1, instead.

```
 !$_        # zip together arg1 and arg2
    ~       # using the following function:
     .      # map over each element of
      ,$    # 1..arg1
        _   # returning arg2;
+           # finally, flatten the list of lists.

```

# Answer
> 1 votes
# MATLAB, 56 bytes

```
L=[];for k=1:1:numel(a) L=[L repmat(a(k),1,r(k))]; end;L

```

# Answer
> 1 votes
# tinylisp, 55 bytes

```
(load library
(q((A R)(foldl concat(map* repeat-val A R

```

The second line is an anonymous function that takes two lists. Try it online!

### Explanation

Too bad the tinylisp library doesn't have a `flatten` function.

```
(q                       ; Two-element list acting as a function:
 ((A R)                  ;  Take two arguments, A and R
  (foldl concat          ;  Fold on list concatenation:
   (map* repeat-val A R  ;  Map repeat-val over corresponding pairs of elements
                         ;  from A and R

```

---

A non-library version is **67 bytes** for a named recursive function that takes the two lists in the opposite order:

```
(d F(q((R A)(i A(i(h R)(c(h A)(F(c(s(h R)1)(t R))A))(F(t R)(t A)))(

```

Try it online!

# Answer
> 1 votes
# Nim, 68 bytes

```
import sugar,sequtils
(x,y)=>concat zip(x,y).map x=>x[0].repeat x[1]

```

Attempt This Online!

-3 bytes thanks to Michael Chatiskatzi

# Answer
> 1 votes
# Wolfram Language (Mathematica), 20 bytes

```
Join@@Table@@@In@##&

```

Try it online!

# Answer
> 1 votes
# x86-64 machine code, 15 bytes

```
8B 0A 48 83 C2 04 F3 AB AD 85 C0 79 F3 AB C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RSI the address of an array `A` of 32-bit integers with a −1 terminator; in RDX, the address of an array `R` in the same form; and in RDI, an address at which to place the result, in the same form. The starting point is after the first 8 bytes.

In assembly, re-arranged for easier understanding:

```
f:  lodsd           # Load a number from A into EAX, advancing the pointer.
    test eax, eax   # Set flags based on that value.
    jns r           # Proceed to r if it's nonnegative.
    stosd       # When -1 is reached, add it to the result array
    ret         #  and return.
#----------------------------------------------------------------------------------
r:  mov ecx, [rdx]  # Load a number from R into ECX.
    add rdx, 4      # Advance the pointer into R.
    rep stosd       # Add EAX to the result array ECX times, advancing the pointer.
# (This section is actually placed at the start; continue at f.)

```

# Answer
> 1 votes
# jq, 34 bytes

```
[transpose[]|range(last)as$_|.[0]]

```

Try it online!

# Answer
> 1 votes
# Arturo, 48 bytes

```
$[a r][flatten map combine a r'x->repeat x\0x\1]

```

Try it

# Answer
> 1 votes
# , 5 bytes

```
where

```

# k, 2 bytes

```
&:

```

Built-in where and indexing does exactly as specified

# Answer
> 1 votes
# Uiua, 1 byte

Try it online!

# Answer
> 1 votes
# GolfScript, 9 bytes

```
~zip{)*}%

```

Try it online!

`~` Eval STDIN, input is a list containing the list of items followed by the list of repetitions.

`zip` Zip the two lists together

`{...}%` Map each to:

* `)` Separate the tail from the rest.
* `*` Repeat the rest {tail} times.

Each item of the resulting list is implicitly printed. Although the list isn't flat, it appears flat when printed.

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


title: The Rod Cutting problem

text:
# Question
Title: The Rod Cutting problem
Given a rod of length n inches and a list of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

```
length   | 1   2   3   4   5   6   7   8
-------------------------------------------
price    | 1   5   8   9  10  17  17  20

```

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

```
length   | 1   2   3   4   5   6   7   8
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

```

The input will be given in this form: The prices will be in ascending order, index starting at 1 to n separated by a space.

`{price of length 1} {price of length 2}.... {price of length N}`

The output should be the maximum Obtainable Value

`{maxVal}`

a Non-Golfed solution to this, in Python is:

```
INT_MIN = -32767
def cutRod(price, n):
    val = [0 for x in range(n+1)]
    val[0] = 0
    for i in range(1, n+1):
        max_val = INT_MIN
        for j in range(i):
             max_val = max(max_val, price[j] + val[i-j-1])
        val[i] = max_val

    return val[n]

arr = [1,2,3,4,5,6,7,8,9,10]
size = len(arr)
print(cutRod(arr, size))

```

Test cases:

```
|                                      Input                                     | Output |
|:------------------------------------------------------------------------------:|:------:|
|                              `1 5 8 9 10 17 17 20`                             |  `22`  |
|                                `1 3 2 5 6 7 4 8`                               |  `12`  |
|                     `5 6 3 2 4 6 8 7 3 4 6 2 12 4 5 7 4 3`                     |  `90`  |
| `23 2 3 45 34 23 3143 13 13 213 1321 3123 12 312 312 31 3 213 432 41 3 123 43` | `9475` |

```

# Answer
# Jelly, 7 bytes

```
LŒṗịµ§Ṁ
L        length
 Œṗ      integer partitions
   ị     index
     §Ṁ  sum each and take the maximum

```

My first jelly answer, so there can probably be improvements made.

Try it online!
> 12 votes

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

```
a=>a.map((v,i)=>a[i]=w=a.map(u=>v=(u+=a[--i])>v?u:v)|v)|w

```

Try it online!

As the question is a knapsack problem. Let \\$ val\left\[i\right\] \\$ be the price of segment of length \\$i\\$. We have:

$$ dp\left\[0\right\] = 0$$ $$ dp\left\[i\right\] = \max\_{j=1..i} \left\\{ val\left\[j\right\] + dp\left\[i-j\right\] \right\\} $$

And \\$dp\left\[len\right\]\\$ is the answer.

To golf more bytes, we slightly modify the transition equation into $$ dp\left\[i\right\] = \max\left\\{val\left\[i\right\], \max\_{j=1..i-1} \left\\{ dp\left\[j\right\] + dp\left\[i-j\right\] \right\\} \right\\} $$

We use \\$a\\$ for both \\$val\\$ and \\$dp\\$ during iteration. When try to calculate \\$a\left\[i\right\]\\$, all values \\$a\left\[0..i-1\right\]\\$ equals to \\$dp\\$ and all other values equals to \\$val\\$. Also, our array is 0-indexed instead of 1-indexed. So we modify the equation into

$$ a\left\[i\right\] = \max\left\\{a\left\[i\right\], \max\_{j=0..i-1} \left\\{ a\left\[j\right\] + a\left\[i-j-1\right\] \right\\} \right\\} $$

Use the feature that when access values out of array range, `undefined` is returned. And mathematics operation on `undefined` results `NaN`. `NaN>v` will also be `false`. We can ignore \\$j=0..i-1\\$ part from \\$\max\\$. And the code is shown above.

Ungolfed C program as reference:

```
int f(int* a) {
  int i, j, val;
  // before loop: a[i] = price of length (i+1) segement
  // after loop: a[i] = max sum price of cutted length (i+1) segment
  for (i = 0; a[i]; i++) {
    // before loop j
    // a[i] = price of length (i+1) segment
    //      = price if do not cut the segment
    for (j = 0; j < i; j++) {
      // price when cut the segment into two parts with length (j+1), (i-j)
      val = a[j] + a[i - j - 1];
      // we prefer higher price if we can
      if (a[i] < val) {
        a[i] = val;
      }
    } // j
  } // i
  return a[i - 1];
}

```

Try it online!

Above C code may golf to 81 bytes, but still longer than JavaScript implementation. :(

---
> 10 votes

# Answer
# JavaScript (ES6), 78 bytes

*Saved 1 byte thanks to @Davide*

```
a=>(m=F=(n,i=0,s=0)=>n?i>n||F(n+~i,i,s+a[i])|F(n,i+1,s):m=s<m?m:s)(a.length)&m

```

Try it online!

### Commented

```
a => (              // a[] = input array
  m =               // initialize m to a non-numeric value
  F = (             // F is a recursive function taking:
    n,              //   n = integer to be partitioned
    i = 0,          //   i = integer to be subtracted from n (-1)
    s = 0           //   s = price sum
  ) =>              //
    n ?             // if n is not equal to 0:
      i > n         //   abort if i is greater than n
      ||            //   otherwise:
        F(          //     first recursive call with:
          n + ~i,   //       n - i - 1
          i,        //       i unchanged
          s + a[i]  //       s + i-th price
        ) |         //
        F(          //     second recursive call with:
          n,        //       n unchanged
          i + 1,    //       i + 1
          s         //       s unchanged
        )           //
    :               // else:
      m = s < m ? m //   update m to max(m, s)
                : s //
)(a.length)         // initial call to F with n = length of a[]
& m                 // return m

```
> 2 votes

# Answer
# C (gcc), ~~98~~ 89 bytes

-9 bytes thanks to ceilingcat

```
m;*n;l;g(N,L)int*N;{n=N;l=L;f(0,m=0);}f(t,s,i){m<t?m=t:0;for(i=0;++i<l-s;f(t+n[i],s+i));}

```

Try it online!

### Explanation

That's the explanation of a previous illegal version, but not so much has changed, so the explanation is still valid.

The function `f()` call itself recursively and into a loop, so that for each index of the loop it starts a whole new loop, and for each index of this other loop it launches a whole new loop and so on.

Each branch stops when the sum of the lengths of the pieces of that particular branch reaches the length of the rod.

Every time, before to enter a new branch-generating loop, the current maximum value possible is compared with that of the branch and eventually updated to a greater value.

```
m;             // variable used to store the maximum value possible
f(            // this is a recursive function creating all the possible combinations of the pieces
n,            // it takes: an array of integers
l,             // the length of the array
t,            // the total price of the current branch
s)             // the sum of the inches virtually sold till now
int*n;{
    m<t?m=t:0;    // if the maximum value is less than the total of a branch, update it
    for(int i=0;  // `i` represents the inches of a particular piece
    ++i<l-s;      // untill `i` is less than the maximum length minus the current sum of the inches
      f(         // f() calls itself with:
      n,         // the same array
      l,          // the same length
      t+n[i],     // the current total price plus the price of this one more piece
      s+i)        // the current sum of the inches plus the length of this one more piece
    );            // end of for() loop
}                // end of function

```

Ported to JavaScript
> 2 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
Max[Range@#~FrobeniusSolve~#.#2]&

```

Try it online!

Input the length and list of prices.
> 1 votes

# Answer
# Python 3.8 (pre-release), 51 bytes

```
f=lambda l,n:n and max(x+f(l,n:=n-1)for x in l[:n])

```

Try it online!

Same length:

**51 bytes**

```
f=lambda l,n:max([0]+[x+f(l,n:=n-1)for x in l[:n]])

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), ~~82~~ 79 bytes

```
(n,m=0)=>(g=(t,s,i=0)=>{m<t?m=t:0;while(i<n.length-s)g(t+n[i],s-~i++);})(0,0)|m

```

Try it online!

### That's my first JavaScript answer!!

Made translating my C answer. The algorithm is the same (you can read the explanation from there if interested).
> 1 votes

# Answer
# Wenyan Language, 2178 bytes

I know what you're going to say -- **WHAT ON EARTH IS THIS?!**

```
吾有一術名之曰「獲取」欲行是術必先得一物曰「對象」一物曰「域」乃行是術曰乃得對象[域]是謂「獲取」之術也吾有一術名之曰「賦值」欲行是術必先得一物曰「對象」一物曰「域」一物曰「值」乃行是術曰乃得對象[域]=值是謂「賦值」之術也減零以三萬二千七百六十七名之曰「極小」吾有一術名之曰「分桿」欲行是術必先得一物曰「物價」一物曰「桿數」乃行是術曰吾有一列名之曰「遞歸」昔之「索引」者今零是矣恆為是吾有一爻名之曰「甲丙」若「索引」不大於「桿數」者昔之「甲丙」者今陽是矣云云若「甲丙」等於零者乃止云云充「遞歸」以零加「索引」以一昔之「索引」者今其是矣云云昔之「索引」者今一是矣恆為是加「桿數」以一吾有一爻名之曰「甲申」若「索引」小於其者昔之「甲申」者今陽是矣云云若「甲申」等於零者乃止云云吾有一物曰「極小」名之曰「最大」昔之「索引其二」者今零是矣恆為是吾有一爻名之曰「亥卯」若「索引其二」小於「索引」者昔之「亥卯」者今陽是矣云云若「亥卯」等於零者乃止云云吾有一術名之曰「丁戊」欲行是術必先得一物曰「a」一物曰「b」乃行是術曰乃得Math.max(a,b)是謂「丁戊」之術也施「獲取」於「物價」於「索引其二」名之曰「子甲」減「索引」以「索引其二」夫「遞歸」之其加「子甲」以其名之曰「午申」施「丁戊」於「最大」於「午申」昔之「最大」者今其是矣加「索引其二」以一昔之「索引其二」者今其是矣云云施「賦值」於「遞歸」於「索引」於「最大」噫加「索引」以一昔之「索引」者今其是矣云云施「獲取」於「遞歸」於「桿數」。名之曰「支子」乃得 「支子」是謂「分桿」之術也噫吾有一列名之曰「桿長」吾有一數名之曰「桿數」夫「桿長」之長昔之「桿數」者今其是矣施「分桿」於「桿長」於「桿數」名之曰「卯地」吾有一物曰「卯地」書之

```

Expect an input at char 678:

```
...
吾有一列名之曰「桿長」(INPUT GOES HERE!)吾有一數
...

```

Using the format:

```
充「桿長」以(some number)以(some number)以(some number)以......

```

Well I know it's difficult for those who don't understand Chinese. Fortunately the language compiles into equivalent JavaScript. I'll show it below for you to understand:

```
var 獲取 = () => 0
獲取 = function(對象) {
  return function(域) {
    return 對象[域]
  }
}
var 賦值 = () => 0
賦值 = function(對象) {
  return function(域) {
    return function(值) {
      return (對象[域] = 值)
    }
  }
}
// Notice that functions above are only for convenience, because all function calls in this language is curry.

var 極小 = 0 - 32767

// The main function
var 分桿 = () => 0
分桿 = function(物價) {
  return function(桿數) {
    // The above two lines is to make the function a curry.
    var 遞歸 = []
    索引 = 0
    while (true) {
      // In this language we only have while-loops, but we can use 'if' and 'break' to control it.
      var 甲丙 = false
      if (索引 <= 杆數) {
        甲丙 = true
      }
      if (甲丙 == 0) {
        break
      }
      遞歸.push(0)
      索引 = 索引 + 1
    }
    索引 = 1
    while (true) {
      var 甲申 = false
      if (索引 < 杆數 + 1) {
        甲申 = true
      }
      if (甲申 == 0) {
        break
      }
      var 最大 = 極小
      索引其二 = 0
      while (true) {
        var 亥卯 = false
        if (索引其二 < 索引) {
          亥卯 = true
        }
        if (亥卯 == 0) {
          break
        }
        var 丁戊 = () => 0
        丁戊 = function(a) {
          return function(b) {
            return Math.max(a, b)
          }
        }
        var 子甲 = 獲取(物價)(索引其二)
        var _ans5 = 索引 - 索引其二
        var _ans6 = 遞歸[_ans5 - 1]
        var _ans7 = 子甲 + _ans6
        var 午申 = _ans7
        最大 = 丁戊(最大)(午申)
        索引其二 = 索引其二 + 1
      }
      var _ans10 = 賦值(遞歸)(索引)(最大)
      索引 = 索引 + 1
    }
    var 支子 = 獲取(遞歸)(杆數)
    return 支子
  }
}
var 桿長 = []
// There should be some input...
杆數 = 桿長.length
var 卯地 = 分桿()
console.log(卯地) // Program complete

```
> 1 votes

# Answer
# 05AB1E, 7 bytes

```
gÅœ<èOà

```

Try it online or verify all test cases.

**Explanation:**

```
g        # Get the length of the (implicit) input-list
 Åœ      # Get all lists of positive integers that sum to this length
   <     # Decrease each by 1 to make it a 0-based index
    è    # Index those into the (implicit) input-list
     O   # Sum each inner list
      à  # Pop and push the maximum
         # (after which it is output implicitly as result)

```

Try it online with step-by-step output.
> 0 votes

# Answer
# Charcoal, 19 bytes

```
ＦＡ⊞υ⌈⊞ＯＥ⮌υ⁺κ§υλιＩ⊟υ

```

Try it online! Link is to verbose version of code. Explanation: Based on @tsh's approach.

```
ＦＡ

```

Loop over each input element.

```
⊞υ⌈⊞ＯＥ⮌υ⁺κ§υλι

```

The value of each length is the maximum of the current input element and the array sum of the array of values so far with its reverse. This is pushed to the array of values.

```
Ｉ⊟υ

```

Output the last value.
> 0 votes

# Answer
# Python 3, 103 bytes

```
lambda p,n:max(map(sum,d(p,n)))
d=lambda p,n:[[p[n-1]]]+[m+[p[i]]for i in range(n-1)for m in d(p,n+~i)]

```

Try it online!

Inputs the prices as a list of integers along with the length of the rod.
Returns the maximum price you can get.

Uses a variation of the integer partition function I wrote for my Landau logarithm answer.
> 0 votes

# Answer
# Julia 1.0, <sup>~~47~~</sup> 36 bytes

port of xnor's answer

```
n*l=max(0,(1:n.|>x->l[x]+(n-x)l)...)

```

Try it online!

# Julia 0.4, 42 bytes

or with Julia 1.0+ and Combinatorics.jl

```
f(p,n)=maximum(x->sum(p[x]),partitions(n))

```

Try it online!
> 0 votes

# Answer
# Pyth, 13 bytes

```
eSmsm@Qtkd./l

```

Try it online!

The obvious approach: try all integer partitions, compute their value, and take the maximum. I spent a while trying to use the `M` or `L` builtins, but they didn't end up being shorter.
> 0 votes

# Answer
# Scala, 98 bytes

Port of @tsh's Javascript answer in Scala.

---

Golfed version. Try it online!

```
a=>{var i,j,v=0;while(a(i)!=0){j=0;while(j<i){v=a(j)+a(i-j-1);if(a(i)<v)a(i)=v;j+=1};i+=1};a(i-1)}

```

Ungolfed version. Try it online!

```
object Main {
  def f(a: Array[Int]): Int = {
    var i = 0
    var j = 0
    var val_ = 0

    while (a(i) != 0) {
      j = 0
      while (j < i) {
        val_ = a(j) + a(i - j - 1)
        if (a(i) < val_) {
          a(i) = val_
        }
        j += 1
      }
      i += 1
    }
    a(i - 1)
  }

  def main(args: Array[String]): Unit = {
    val n = Array(
      Array(1, 5, 8, 9, 10, 17, 17, 20, 0),
      Array(1, 3, 2, 5, 6, 7, 4, 8, 0),
      Array(5, 6, 3, 2, 4, 6, 8, 7, 3, 4, 6, 2, 12, 4, 5, 7, 4, 3, 0),
      Array(23, 2, 3, 45, 34, 23, 3143, 13, 13, 213, 1321, 3123, 12, 312, 312, 31, 3, 213, 432, 41, 3, 123, 43, 0)
    )

    for (i <- n.indices) {
      println(f(n(i)))
    }
  }
}

```
> 0 votes

---
Tags: code-golf
---


title: Multibase Numbers

text:
# Question
Title: Multibase Numbers
(Similar: Through the bases)

Normally, our number system is base ten, with the digits `0123456789`. However, we can increase or decrease the base count (so hexadecimal uses `0123456789abcdef` and octal uses `01234567`.

Your goal is: given a string, interpret it in all bases 2-36 for which it's valid, compute the total, and express that total in the smallest base that was valid for the original string.

The valid base characters are `0123456789abcdefghijklmnopqrstuvwxyz`. It is not case sensitive!

If it is invalid, return zero. There may be a sign for the first character (a `+` or `-`): if it is a `-`, then return the result with a `-` before it.

## Test cases:

```
Xx -> 32s (base 34-36, in base 34, after lowercasing)
zzzzzz -> zzzzzz (36 is the only base that works, the number in base 36 is just "zzzzzz")
12 -> 1000002
MultiBase -> 8qa4f6laud
1v1 -> app
gy -> ye
+Huh -> 41ou
+h -> hh
abc -> 58b5b
-hello -> -k029mh
one -> hmm5
NaN -> k1hl
-Infinity -> -16di5ohk2
hello world -> 0
$0.99 -> 0

```

This is , so the shortest answer in bytes wins!

# Answer
> 1 votes
# Pip, 22 bytes

```
aFB:,37($+FIaTB:uNa)|0

```

Outputs in uppercase. Attempt This Online! Or, verify all test cases.

### Explanation

Pip's base-conversion builtins were *made* for this challenge.

* They work for bases 2 through 36, using 0..9A..Z as digits.
* They accept both lower- and uppercase inputs.
* They even handle the leading `+` and `-` correctly.
* If `FB` can't convert from a given base, it returns nil (and issues a warning which is ignored by default).

Thus:

```
aFB:,37($+FIaTB:uNa)|0
a                      ; First command-line input
 FB:                   ; Convert from the following base(s) and assign back to a:
    ,37                ; All numbers from 0 through 36
                       ; This results in a 37-element list, which contains nil for
                       ; any base that's too small (including 0 and 1) and a
                       ; decimal integer for the rest
          FIa          ; Filter the falsey values out of that list
        $+             ; Sum it
                uNa    ; Count the number of times nil occurs in the list
             TB:       ; Convert the sum to that base
                       ; If the input was invalid, every element of the list was
                       ; nil, which means we just tried to convert 0 to base 37,
                       ; which returns nil rather than 0, so...
       (           )|0 ; If that result was falsey, use 0 instead

```

# Answer
> 5 votes
# Go, 146 bytes

```
import."strconv"
func f(n string)string{s,m:=int64(0),36
for b:=m;b>1;b--{if i,e:=ParseInt(n,b,0);e==nil{s+=i;if m>b{m=b}}}
return FormatInt(s,m)}

```

Attempt This Online!

### Explanation

```
import."strconv"        // boilerplate
func f(n string)string{ // boilerplate
s,m:=int64(0),36        // `s`um, `m`inimum usable base
for b:=m;b>1;b--{       // for all bases from 36 to 2...
if i,e:=ParseInt(n,b,0);e==nil{ // parse `n` as that base. if successful...
s+=i                    // add to the sum
if m>b{m=b}}}           // set to the lower base
return FormatInt(s,m)}  // format the number in the `m`inimum base.

```

# Answer
> 4 votes
# JavaScript (ES7), 83 bytes

```
s=>(g=b=>s>'!'&(P=parseInt)(s+0,b)**2>(v=P(s,b))*v&&v+g(b-1,q=b))(q=36).toString(q)

```

Try it online!

# Answer
> 3 votes
# Ruby, 89 bytes

```
->s{o=p;(2..36).sum{|b|q=s.to_i b;s.tr(?+,'').downcase==q.to_s(b)?(o||=b;q):0}.to_s o||2}

```

Attempt This Online!

# Answer
> 2 votes
# Factor, ~~77~~ 75 bytes

```
[ 2 36 [a,b] [ base> ] with map dup sift sum swap [ f = ] count 2 + >base ]

```

Try it online!

```
                   ! "abc"
2 36 [a,b]         ! "abc" { 2 3 ... 36 }
[ base> ] with map ! { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 }
dup                ! { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 } { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 }
sift               ! { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 } { 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 }
sum                ! { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 } 162316
swap               ! 162316 { f f f f f f f f f f f 1845 2126 2427 2748 3089 3450 3831 4232 4653 5094 5555 6036 6537 7058 7599 8160 8741 9342 9963 10604 11265 11946 12647 13368 }
[ f = ] count      ! 162316 11
2 +                ! 162316 13
>base              ! "58b5b"

```

# Answer
> 2 votes
# Charcoal, 48 bytes

```
≔⌕θ-η×¬η-≔↧Φθ∨κ∧η⌕θ+θ≔ＥΦ³⁷⬤θ№Ｅι⍘νιλ⍘θιη⍘↨η¹⁻³⁷Ｌη

```

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

```
≔⌕θ-η

```

See whether the string begins with `-`.

```
×¬η-

```

Output a `-` if it does.

```
≔↧Φθ∨κ∧η⌕θ+θ

```

Remove the first character of the string if it was `-` or `+` and lowercase the result.

```
≔ＥΦ³⁷⬤θ№Ｅι⍘νιλ⍘θιη

```

Loop through the bases up to `36`, checking that all the characters in the string can be represented in that base, and if so, convert the string from that base. No number can successfully be represented in base `0`, and while `0` can be successfully represented in base `1`, fortunately this won't affect the result.

```
⍘↨η¹⁻³⁷Ｌη

```

Take the sum of all of the conversions and convert that into the lowest successful base, calculated as `37` minus the number of successful base conversions (if there were none then the `0` will be converted into base `37` but that's still `0`).

# Answer
> 2 votes
# 05AB1E, ~~36~~ 35 bytes

```
„+-мl©žLRlÙη¤®Skà.$¬UδÅβþOXÅвJI'-Ãì

```

Try it online or verify all test cases.

**Explanation:**

(Assumes the input will never contain any `-` or `+` in the middle of the input, only optionally at the front.)

```
„+-м            # Remove a potential "+" or "-" from the (implicit) input
    l           # Convert it to lowercase
     ©          # Store this modified input in variable `®` (without popping)
žL              # Push builtin "zyx..cbaZYX..CBA987..210"
  R             # Revert it
   l            # Convert it to lowercase as well
    Ù           # Uniquify it to "012...789abc...xyz"
     D          # Duplicate this string
      η         # Get all its prefixes
       s        # Swap so the string is at the top again
        ®       # Push modified input `®`
         S      # Convert it to a list of characters
          k     # Get the 0-based index of each character in the string
           à    # Pop and push the maximum
            .$  # Remove that many leading items from the list of prefixes
¬               # Push the first prefix (without popping the list of prefixes)
 U              # Pop and store this first prefix in variable `X`
δ               # Map and use each prefix separately as argument on the modified input:
 Åβ             #  Convert it to this prefix as custom base
þ               # Only keep all items consisting solely of digits (for invalid inputs)
 O              # Sum this list together
  X             # Push the first prefix from variable `X`
   Åв           # Convert the sum to this custom base as list
J               # Join this list of characters together to a string
 I              # Push the input-again
  '-Ã          '# Only keep its "-"
     ì          # Prepend it in front of the string
                # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Excel, 136 bytes

```
=LET(
    b,"-",
    c,TEXTSPLIT(A1,"+",b,1),
    d,ROW(A:A),
    e,DECIMAL(c,d),
    f,1-ISERR(e),
    IFERROR(REPT(b,LEFT(A1)=b)&BASE(SUM(IF(f,e)),MIN(IF(f,d))),0)
)

```

Input in cell `A1`.

# Answer
> 1 votes
# Rust, 362 bytes

```
|s|{let(mut o,mut m)=("".repeat(1),36);let mut n=(2i32..=36).rev().filter_map(|i|i128::from_str_radix(s,i as u32).ok()).zip((2i32..=36).rev()).fold(0,|a,(n,b)|{if m>b{m=b}a+n});let k=n<0;n=n.abs();while{let(d,r)=(n/m as i128, n%m as i128);o=format!("{}{o}",&"0123456789abcdefghijklmnopqrstuvwxyz"[r as usize..=r as usize]);n=d;n>0}{}if k{format!("-{o}")}else{o}}

```

Attempt This Online!

I'm not very familiar with golfing in Rust, but here is a quick-and-dirty port of my Golang answer.

About half the bytes are dedicated specifically for turning the sum back into base `m`, because apparently, Rust doesn't have a `to_str_radix` or equivalent method for an arbitrary base \<=36.

# Answer
> 1 votes
# Raku, 70 bytes

```
{{.sum.base(.first(?*):k//2)}([map {!/\./&&.parse-base($^b)//0},^37])}

```

Try it online!

This is an anonymous function taking its argument in `$_`. Its form is `{ ... }(expr)`, where the inner braces are another anonymous function, which is immediately evaluated with the argument `expr`, available in the inner function as `$_`. This is a golfing idiom I use to avoid assigning to a temporary variable.

* `map { !/\./ && .parse-base($^b) // 0 }, ^37` parses the input string into all bases from zero to thirty-six. `parse-base` returns an error for the invalid bases 0 and 1, as well as any bases for which the input string has invalid characters, so the `// 0` converts those errors into the number zero. `parse-base` is case-insensitive and also handles leading "+" and "-" characters. Unfortunately for this problem, it also accepts a single period character, parsing such a string into a floating-point number, so I have to explicitly guard against that with `!/\./`.
* `[ ... ]` wraps the result of that mapping into an array, so that we can traverse it twice later. (`map` returns a lazy sequence object that can only be traversed once.)
* `.sum.base(...)` is the sum of those parsed numbers (plus zeroes for the invalid bases) expressed in the base given by the `...`, to wit:
* `.first(?*):k` returns the index (thanks to the `:k`ey adverb) of the first element of those parsed numbers that is nonzero, per the `?*` anonymous function that converts its argument to a boolean value.
* `// 2` defaults the base to 2 if `first` did not find any nonzero numbers, as when the input string is not valid in any base. The sum in this case will always be zero, so any valid base could be used here, though of course 2-9 are the best for golfing.

# Answer
> 1 votes
# Zsh, 84 bytes

```
for b ({36..1})((r+=$b#${(M)1:#(+|-|)[[:alnum:]]##}))||break
<<<$[[##$[b+1]]r]||<<<0

```

Try it online!

```
for base ({36..1})

    # ${(M)1:#$pattern} substitutes $1 if $pattern matches
    # Zsh supports [base]#[string] numbers.
    (( sum += $base#${(M)1:#(+|-|)[[:alnum:]]##} )) ||
        # The previous statement fails in three ways:
        # - base is invalid (1#...)
        # - the string is empty
        # - the string contains invalid characters for the base (13#abc)
        break

# increment $b back to the last valid base. This fails when $1 was invalid,
# since then $b is still 36. In that case, we output 0.
<<< $[ [##$[base+1]] sum ] || <<<0

```

# Answer
> 0 votes
# Java (JDK), 114 bytes

```
s->{Integer t=0,b=1,r=40;for(;++b<37;)try{t+=t.parseInt(s,b);r=b<r?b:r;}finally{continue;}return t.toString(t,r);}

```

Try it online!

Saved 2 bytes thanks to ceilingcat.

# Answer
> 0 votes
# Pyth, 35 bytes

```
K37#=+Ziz=tK;s+*>0Z\-@Ljk+UTGj.aZhK

```

Try it online!

### Explanation

```
                                       # implicitly Z=0 and z=input()
K37                                    # K = 37
   #        ;                          # repeat infinitely until an error occurs, then break
         =tK                           #   K = K-1
       iz                              #   convert the input from base K to int
    =+Z                                #   Z = Z + input as int (base K)
                              .aZ      # absolute value of Z
                             j   hK    # converted to base K+1 as a list of ints
                     @L                # convert each int to the value at its index in
                         +UTG          # [0-9] + the alphabet
                       jk              # joined as a string
               *>0Z\-                  # "-" if Z is less than 0, "" otherwise
              +                        # prepend
             s                         # join all elements together

```

# Answer
> 0 votes
# C (gcc) with `-lgmp`, ~~231~~ 225 bytes

* -6 thanks to ceilingcat

Uses GMP in case of large values.

```
#import<gmp.h>
f(s,t,b,r,g)char*s,*t;{mpz_t x,y;mpz_inits(x,y,r=0);t=s;g=*s;for(g-43&&g-45?g=0:(t=++s);*t;)r+=!isalnum(*t++);for(b=36;b>1&!r&&!mpz_set_str(y,s,b);b--)mpz_add(x,x,y);printf("-%s"+(g!=45),mpz_get_str(0,b+1,x));}

```

Try it online!

Ungolfed:

```
#import<gmp.h>
f(s,t,b,r,g)char*s,*t;{
  mpz_t x,y;
  mpz_inits(x,y,r=0);
  t=s;
  g=*s; // get sign (if any)
  for(g-43&&g-45?g=0:(t=++s); // advance past sign (GMP only parses unsigned)
      *t;)r+=!isalnum(*t++); // check for non-digit characters
  for(b=36; // start at base 36
      b>1&& // end at base 2 if it gets this far
      !r&& // only parse valid strings
      !mpz_set_str(y,s,b); // stop when the parse fails
    b--) // base worked: go to next-lowest base
    mpz_add(x,x,y); // add the parsed value to the sum
  printf("-%s"+(g!=45),mpz_get_str(0,b+1,x)); // print the sum in lowest base, adding sign if needed
}

```

# Answer
> 0 votes
# Julia 1.0, 84 bytes

```
!a=string((l=2:36 .|>b->try parse(Int,a;base=b)catch;0end)|>sum;base=1+argmax(l.>0))

```

Try it online!

# Answer
> 0 votes
# Scala, 325 bytes

I was rewriting @naffetS's Ruby answer in Scala.

\\$ \color{red}{\text{But the scala code fails on 4 cases. Any help would be appreciated.}} \\$

---

Golfed version. Try it online!

```
def f(s:String)={val l=s.toLowerCase;val B="0123456789abcdefghijklmnopqrstuvwxyz".toList;var o:Option[Int]=None;val r=(2 to 36).flatMap{b=>if(l.forall(c=>B.take(b).contains(c))){val q=BigInt(s,b);if(s.replace("+","").toLowerCase==q.toString(b)){o=o.orElse(Some(b));Some(q)}else None}else None}.sum;r.toString(o.getOrElse(2))}

```

Ungolfed version. Try it online!

```
object Main extends App {
  def f(s: String): String = {
    var o: Option[Int] = None
    val baseChars = "0123456789abcdefghijklmnopqrstuvwxyz".toList
    val sum = (2 to 36).flatMap { b =>
      if (s.toLowerCase.forall(char => baseChars.take(b).contains(char))) {
        val q = BigInt(s, b)
        if (s.replace("+", "").toLowerCase == q.toString(b)) {
          o = o.orElse(Some(b))
          Some(q)
        } else {
          None
        }
      } else {
        None
      }
    }.sum

    sum.toString(o.getOrElse(2))
  }

  val data = List(
    ("Xx", "32s (base 34-36, in base 34, after lowercasing)"),
    ("zzzzzz", "zzzzzz (36 is the only base that works, the number in base 36 is just \"zzzzzz\")"),
    ("12", "1000002"),
    ("MultiBase", "8qa4f6laud"),
    ("1v1", "app"),
    ("gy", "ye"),
    ("+Huh", "41ou"),
    ("+h", "hh"),
    ("abc", "58b5b"),
    ("-hello", "-k029mh"),
    ("one", "hmm5"),
    ("NaN", "k1hl"),
    ("-Infinity", "-16di5ohk2"),
    ("hello world", "0"),
    ("$0.99", "0")
  )

  data.map { case (y, z) =>
    val s = f(y)
    val k = z.split(" \\(").head
    s + " " * (30 - s.length) + k + " " * (30 - k.length) + (if (s == k) "✅" else "❌")
  }.foreach(println)
}

```

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


title: Replace all items with their counts

text:
# Question
Title: Replace all items with their counts
**Task:**

Given an array of numbers as input (you can choose what subset, such as integers or natural numbers), replace all items with the number of times they appear within the array. As an example, `[1, 2, 2, 1, 4, 8, 1]` would become `[3, 2, 2, 3, 1, 1, 3]`.

You can take input/produce output as arrays, lists, tuples, or any other reasonable representation of some numbers.

**Test cases:**

```
[1]                     [1]
[1, 2]                  [1, 1]
[1, 1]                  [2, 2]
[1, 4, 4]               [1, 2, 2]
[4, 4, 2]               [2, 2, 1]
[4, 4, 4, 4]            [4, 4, 4, 4]
[10, 20, 10, 20]        [2, 2, 2, 2]
[1, 2, 2, 4, 4, 4, 4]   [1, 2, 2, 4, 4, 4, 4]
[1, 2, 2, 1, 4, 8, 1]   [3, 2, 2, 3, 1, 1, 3]

```

**Other:**

This is , shortest answer (in bytes) per language wins!

# Answer
# Python 2, 23 bytes

```
lambda l:map(l.count,l)

```

Try it online!
> 16 votes

# Answer
# MATL, 3 bytes

```
&=s

```

Try it online! Or verify all test cases.

### Explanation

```
     % Implicit input: numeric row vector
&=   % Matrix of all pairwise equality comparisons
s    % Sum of each column
     % Implicit display

```
> 9 votes

# Answer
# JavaScript (ES6), 36 bytes

```
a=>a.map(x=>a.map(y=>t+=x==y,t=0)|t)

```

Try it online!
> 8 votes

# Answer
# APL(Dyalog Unicode), 6 bytes SBCS

```
+/∘.=⍨

```

Try it on APLgolf!

```
+/∘.=⍨  dfn submission
  ∘.=   product table using equality
     ⍨  applied to the input on the left and the right
+/      reduce by addition / sum

```
> 7 votes

# Answer
# Factor, 28 bytes

```
[ dup histogram substitute ]

```

Try it online!

It's a bit shorter than the version for squares:

```
[ dup [ '[ _ = ] count ] with map ]

```

## Explanation:

It's a quotation (anonymous function) that takes a sequence from the data stack as input and leaves a sequence on the data stack as output. Assuming `{ 1 4 4 }` is on the data stack when this quotation is called...

* `dup` Duplicate an object.

**Stack:** `{ 1 4 4 } { 1 4 4 }`
* `histogram` Create a histogram from a sequence.

**Stack:** `{ 1 4 4 } H{ { 1 1 } { 4 2 } }`
* `substitute` Take a sequence and an associative array and substitute elements in the sequence that have keys in the assoc with their values.

**Stack:** `{ 1 2 2 }`
> 7 votes

# Answer
# Brachylog, 8 bytes

```
∋;?{∈ᵈ}ᶜ

```

Try it online!

Generates the output through the output variable.

```
∋;          Pair some element of the input with
  ?         the input.
   {  }ᶜ    In how many ways is
    ∈ᵈ      the element an element of the input?

```

Using  comes out one byte longer:

# Brachylog, 9 bytes

```
⟨ọ⟨∋h⟩∋⟩t

```

Try it online!

Also generates the output through the output variable.

```
      ∋      Choose an element of the input.
  ⟨ h⟩       It is the first element of
   ∋         an element of
⟨ọ     ⟩     the list of pairs [element of input, how many times it occurs in input]
        t    the last element of which is the output.

```
> 5 votes

# Answer
# Ruby, 27 bytes

```
f=->*a{a.map{|e|a.count e}}

```

Testing:

```
p f[4,3,4]  #=> [2, 1, 2]

```
> 5 votes

# Answer
# Raku, 10 bytes

```
{.Bag{$_}}

```

Try it online!

`.Bag` generates a Bag (a set with multiplicity) from the input argument `$_`. Then `{$_}` slices into that Bag with the original list, producing a list of the multiplicities of the elements of that list, in order.
> 5 votes

# Answer
# Jelly, 2 bytes

```
ċⱮ

```

Try it online!

## How it works

```
ċⱮ - Main link. Takes a list L on the left
 Ɱ - For each element in L
ċ  -   Count the times it appears in L

```
> 4 votes

# Answer
# Vyxal, 2 bytes

```
vO

```

Try it Online!

Wow y'all using unicode in your golfing languages while I'm chilling in the ASCII zone.

## Explained

```
vO  # vectorise count over the input
    # essentially, [input.count(n) for n in input]

```
> 4 votes

# Answer
# Python 3, 26 bytes

```
lambda l:[*map(l.count,l)]

```

Try it online!

-5 bytes (indirectly) thanks to xnor!
> 4 votes

# Answer
# Pyth, 3 bytes

```
/LQ

```

Test suite

Explanation:

```
/LQ  | Full program
/LQQ | with implicit variables
-----+-------------------------------------
 L Q | replace each element d in input with
/ Q  | the count of d in input

```
> 4 votes

# Answer
# JavaScript (ES2021), 35 bytes (not quite reasonable I/O)

```
a=>a.map(n=>a[++(a[n]||=[0])[0],n])

```

Accept an array of ~~1 element array of~~ *negative* numbers. Return an array of 1 element array...

```
f([-1, -2, -2, -1, -4, -8, -1]) // [[3], [2], [2], [3], [1], [1], [3]]
f([[-1], [-2], [-2], [-1], [-4], [-8], [-1]]) // [[3], [2], [2], [3], [1], [1], [3]]

```

~~Just consider input / output as column vectors...~~

---

# JavaScript (ES2021), 42 bytes

Add an extra `.flat()` to make it reasonable would cost +7 bytes (42 bytes in total)

```
a=>a.map(n=>a[++(a[n]||=[0])[0],n]).flat()

```

That's too long.
> 4 votes

# Answer
# Racket, 42 bytes

```
(λ(b)(map(λ(y)(count(λ(x)(= x y))b))b))

```

Try it online!
> 4 votes

# Answer
# , 6 bytes

```
1#.=/~

```

Try it online!

# K (oK), 9 bytes

```
{+/x=\:x}

```

Try it online!
> 4 votes

# Answer
# Haskell, 27 bytes

```
f a=[sum[1|y<-a,y==x]|x<-a]

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 1 byte

```
¢

```

Try it online! Beats all other answers.

```
¢  # full program
¢  # number of times...
   # (implicit) each element in...
   # implicit input...
¢  # appears in...
   # implicit input
   # implicit output

```
> 3 votes

# Answer
# Perl 5 `-pa`, 22 bytes

```
s/\S+/grep$_==$&,@F/ge

```

Try it online!
> 3 votes

# Answer
# Excel 17, bytes

```
=COUNTIF(A1#,A1#)

```

Assuming `A1 = { .... }` then this works. It's a longer, less flexible formula if the data in entered in individual cells.
> 3 votes

# Answer
# Java, 58 bytes

```
l->l.stream().map(x->java.util.Collections.frequency(l,x))

```

Try it online!

# Java, 56 bytes

```
l->l.stream().map(x->l.stream().filter(y->y==x).count())

```

This only works for integers in the Integer Cache (-128 to 127, by default).

Try it online!
> 3 votes

# Answer
# Thunno, \\$ 2 \log\_{256}(96) \approx \\$ 1.65 bytes

```
ec

```

Attempt This Online!

```
ec : implicit input array
e  : map the input to the following:
 c :   count the occurrences of the number in the input
   : implicit output

```

Thought I'd try an easy and short problem for my first Thunno answer.
> 3 votes

# Answer
# Julia 1.0, ~~24~~ 21 bytes

```
~a=@.count(==(a),[a])

```

Try it online!

-3 bytes thanks to MarcMush: replace `Ref(a)` with `[a]`
> 3 votes

# Answer
# , 26 bytes

```
ave(a,a<-scan(),FUN=table)

```

Try it online!

`ave` takes a vector `x`, an arbitrary number of grouping variables `...`, and a function `FUN`, and replaces each element of `x` with the result of applying `FUN` to the group containing that element.

I've also found a number of 26 byte variants with `FUN=sum`; they differ only in the way they generate a vector of ones with length `length(a)`.

```
ave(a^0,a<-scan(),FUN=sum)
ave(a,a<-scan(),FUN=sum)/a
ave(a|1,a<-scan(),FUN=sum)

```
> 2 votes

# Answer
# AWK, 47 45 bytes

```
{++f[l[++n]=$1]}END{for(x in l)print f[l[x]]}

```

Try it online!

*-2 thanks to cnamejj*
> 2 votes

# Answer
# Japt, 4 bytes

```
£è¥X

```

Try it

maps input by returning number of occurrence in input
> 2 votes

# Answer
# C (clang), ~~84~~ \\$\cdots\\$ ~~81~~ 75 bytes

Saved 6 bytes thanks to AZTECCO!!!

```
b;i;j;f(*a,l){for(i=-1;++i<l;printf("%d ",b))for(b=j=l;j--;)b-=a[i]!=a[j];}

```

Try it online!

Inputs a pointer to an array and its length (because array pointers in C don't carry any length info) and prints the occurrence counts.
> 2 votes

# Answer
# PHP, 56 bytes

```
fn($a)=>array_map(fn($e)=>array_count_values($a)[$e],$a)

```

Try it online!

As usual, those "array\_" PHP prefixes are ruining the golfing :P
> 2 votes

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

Nothing special

```
a=>a.Select(x=>a.Count(y=>x==y))

```

Try it online!
> 2 votes

# Answer
# Neim, 2 bytes

Right language, right time.

```
Ψ

```

Try it online!

Explanation:

```
Ψ  # Apply next token to all in list
  # Count element in list

```
> 2 votes

# Answer
# Zsh, 23 bytes

```
xargs -I. grep -c . f<f

```

Try it online!
> 2 votes

# Answer
# Arturo,  ~~34~~  27 bytes

```
$->a[map a=>[get tally a&]]

```

Try it!
> 2 votes

# Answer
# Pyt, 2 bytes

```
Đɔ

```

Try it online!

```
Đ      implicit input; duplicate
 ɔ     for each item in input, count occurrences in input; implicit print

```
> 2 votes

# Answer
# TI-Basic, 13 bytes

```
seq(sum(I=Ans),I,1,dim(Ans

```

Takes input in `Ans`.
> 2 votes

# Answer
# Go, 103 bytes

```
func f(l[]int)[]int{m:=make(map[int]int)
for _,e:=range l{m[e]++}
for i,e:=range l{l[i]=m[e]}
return l}

```

Attempt This Online!
> 2 votes

# Answer
# Thunno 2, 1 byte

```
c

```

Try it online!

Just the `c`ount command, vectorised over the array implicitly.
> 2 votes

# Answer
# Desmos, 77 bytes

```
f(a)=\sum_{n=[1...a.length]}^{[1...a.length]}(total(\left\{a=a[n],0\right\}))

```

Try it online! Takes in a list as input, and outputs a new list as per the specifications. The linked graph uses an action to replace the list with the function's output.
> 2 votes

# Answer
# Java, 44 Bytes

```
n.stream().map(e->frequency(n1,e)).toList();

```

with `n1` beeing a copy of `n` and static import of `java.util.Collections.*`
> 2 votes

# Answer
# PowerShell Core, 29 bytes

```
($a=$args)|%{($a-eq$_).count}

```

Try it online!
> 2 votes

# Answer
### Common Lisp, 42

```
(lambda(x)(mapcar(lambda(u)(count u x))x))

```
> 2 votes

# Answer
# Pip `-p`, 5 bytes

```
_NgMg

```

Attempt This Online!

### Explanation

```
    g  ; List of command-line args
   M   ; Map to each:
_N     ;  Number of occurrences of that argument in...
  g    ;  ... the list of command-line args

```
> 2 votes

# Answer
# Charcoal, 6 bytes

```
ＩＥθ№θι

```

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

```
  θ     Input array
 Ｅ      Map over elements
   №    Count of
     ι  Current element in
    θ   Input arrray
Ｉ       Cast to string
        Implicitly print

```
> 1 votes

# Answer
# 05AB1E, 2 bytes

```
€¢

```

Try it online!

## Explained

```
€¢   # [input.count(n) for n in input]

```
> 1 votes

# Answer
# Scala, 22 bytes

```
a=>a.map(a count _.==)

```

Try it in Scastie!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 12 bytes

```
Counts@#/@#&

```

Try it online!
> 1 votes

# Answer
# Pari/GP, 36 bytes

```
f(v)=apply(x->sum(i=1,#v,x==v[i]),v)

```

Try it online!
> 1 votes

# Answer
# Excel, 45 bytes

```
=COUNTIF(A:A,INDEX(A:A,SEQUENCE(COUNT(A:A))))

```

Input is in column A. The formula goes anywhere not in column A.

`COUNT(A:A)` counts the numeric entries.
`SEQUENCE(~)` creates an array from 1 to whatever that count was.
`INDEX(A:A,~)` pulls the inputs one at a time, thanks to the sequence input.
`COUNTIF(A:A,~)` counts the inputs that match the one it just pulled.
> 1 votes

# Answer
# Arn, 6 bytes

```
█Â(ÂÍL

```

Found some pretty major precedence bugs... so that's why I'm a day late

# Explained

Unpacked: `@a{/:=a`

```
  _       STDIN; implied
@         Bind following to each value
  a{         Block with key of 'a'
     /:      Bind next arg with the arg after, use truthiness to filter and then count
          _    Current value, implicit
        =      Equals
          a    Current value of map bind (defined by block)
        _    It's binded to STDIN
  }

```

Came up with some alternatives when I got bored from fixing the bug, here are some

# Arn, 8 bytes

```
ñ=èÍù«Á&

```

Unpacked: `@a{+{=a}\` (Replace each val with a mapped for equality + folded version of stdin)

# Arn, 8 bytes

```
hLdŠÅk$'

```

Unpacked: `@a{+\(@=a` (Same as last one but written a different way)

# Arn, 6 bytes

```
╔½†Œ#ç

```

Unpacked: `@a{$=a&#` (Very similar to the actual answer, but uses filter and a binded size suffix. Compression shaved two bytes off of this, instead of the one byte my real answer lost from compression, which is why they're the same length)
> 1 votes

# Answer
# Matlab, 32 bytes

```
@(x)table(histcounts(x)).Var1(x)

```

...assuming inputting only integer numbers from 1 to 50. Rules says I can choose a subset.
To work for integers from 1 to 65536 (216) you need few extra bytes and code like that:

```
@(x)table(histcounts(x,'BinMethod','int')).Var1(x)

```

Both solutions are anonymous functions.
The fragment of code `table(...).Var1(x)` is a trick allowing for indexing the function output without saving it to a variable. Normally one would do something like that:

```
y = histcounts(x);
return y(x)

```

but anonymous functions doesn't allow for that and full function would be longer.

The solution unfortunatelly doesn't work for Octave, because it doesn't have `histcounts` implemented. :(
> 1 votes

# Answer
# Thunno, \\$ 2\log\_{256}(96)\approx\\$ 1.65 bytes

```
Dc

```

Attempt This Online!

Or, **\\$1 \log\_{256}(96) \approx\\$ 0.82 bytes with the `D` flag!**: Attempt This Online!

`D` duplicates the (implicit) input, and `c` gets the count of each one (vectorises automatically).

*Edit: Just realised that there's another Thunno answer here. I'll keep this undeleted, though, since it is different from the other answer.*
> 1 votes

# Answer
# Nekomata, 2 bytes

```
ᵐĈ

```

Attempt This Online!

```
ᵐĈ
ᵐ   Map
 Ĉ  Count

```
> 1 votes

# Answer
# Uiua, 5 bytes

```
⊏∶⍘⊚.

```

Try it!

Works with natural numbers.

```
⊏∶⍘⊚.
    .  # duplicate
  ⍘⊚   # inverse where (occurrences)
 :     # flip
⊏      # select

```
> 1 votes

# Answer
# T-SQL, 80 bytes

```
SELECT c FROM (SELECT a b,COUNT(*)c FROM @ GROUP BY a)x JOIN @ ON a=b ORDER BY i

```

# Example Input

Requires something like this for input

```
DECLARE @ TABLE (a int, i int identity)
INSERT INTO @ VALUES (1), (2), (2), (4), (4), (4), (4)

```

# Explanation

Group by the number and count them up. Then join back to the original list so that we can output in the correct order.
> 0 votes

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


title: Hilbert-Curvify a Matrix

text:
# Question
Title: Hilbert-Curvify a Matrix
Inspired by this question

Another way to unroll a 2D image into a 1D string is to use an Hilbert Curve.

There are many version of this curve, depending on the number of iterations used while computing it. Below follow example of Hilbert Curves from first order to fifth order.

The way of computing this curve is the following. First we define the first order Hilbert Curve as the one shown in figure (the one for n = 1), so that it fits in a 1x1 square. We than make four copies of this curve, spacing them in a 4x4 square, so that they all present the "concavity" towards the left side. We then flip the two leftmost order 1 curves, so that the top one concavity faces toward the top, while the bottom's faces the bottom. We finally connect the the corners of the adjacent Hilbert Curves. If wanting to obtain a (n+1)-order Curve, we just need to repeat the process with four n-order Curves. We can see a visualisation of the process here (I will also add an image detailing the process soon)

Your task in this challenge is to unroll a matrix of integers along the **lowest order Hilbert Curve** for that matrix.

For simplicity's sake, we will have the curve starting from the top left corner of the matrix.

You can receive the input either as a list of list of integers, where each sub-list represents a row of the matrix.

You can assume that the input will be a square matrix (n\*n).

For example:

Input:

```
[[ 1, 2,]
 [ 3, 4 ]]

```

Output:

```
[ 1, 2, 4, 3 ]

```

Since we are using the first order Hilbert Curve shown in figure

Input:

```
[[ 1, 2, 3, 4,    ]
 [ 5, 6, 7, 8,    ]
 [ 9, 10, 11, 12, ]
 [ 13, 14, 15, 16 ]]

```

Output:

```
[ 1, 5, 6, 2, 3, 4, 8, 7, 11, 12, 16, 15, 14, 10, 9, 13 ]

```

Using the second order Hilbert Curve

As usual, standard loopholes are not permitted.

This is code-golf, so the shortest answer in byte wins.

# Answer
# APL (Dyalog Unicode), 41 bytesSBCS

Saved 30 bytes (!) by consulting the wisdom of the APL Orchard, especially @ngn and @Sherlock9.

```
{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵}

```

Try it online!

Explanation as follows:

```
{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵} ⍝ Recursive function - takes input as an
                                          ⍝ n*n square matrix
 0::⍵                                     ⍝ Our base case - this is an error guard
                                          ⍝ If there's any error, catch it and
                                          ⍝ return the function's input
                                      ≢⍵  ⍝ Find the number of rows in the input
                                2 ¯2÷⍨    ⍝ Divide the above by 2 and negative 2,
                                          ⍝ resulting in a 2-element vector
                            ∘.,⍨          ⍝ Outer product - take the above vector and
                                          ⍝ apply concatenation (,) with each element
                                          ⍝ against all elements in the vector. Since
                                          ⍝ we have a 2-element vector, this results in
                                          ⍝ a 2-by-2 matrix, e.g.
                                          ⍝ [[(2,2),(2,¯2)],[(¯2,2),(¯2,¯2)]]
                        ↑∘⍵¨              ⍝ For each element in the matrix, we apply
                                          ⍝ "take" against our original input matrix.
                                          ⍝ Take, given a negative number, will take
                                          ⍝ elements from the end of a particular rank.
                                          ⍝ With our argument above, this means that we end
                                          ⍝ up with our original original input matrix
                                          ⍝ split by quadrant into a 2-by-2 matrix.
                                          ⍝ It is also worth noting that take expects
                                          ⍝ an integer argument, so for matrices whose
                                          ⍝ rowcount divided by two results in a decimal
                                          ⍝ (i.e., 1-by-1 matrices), we throw an error
                                          ⍝ which is caught by the guard above, returning
                                          ⍝ the original input.
                       ⌽                  ⍝ Flip the above matrix about the vertical axis.
                   ⊢∘⍉\                   ⍝ Apply a "monadic transpose scan". More details
                                          ⍝ on how this works below, but for our purposes
                                          ⍝ this applies transpose to each of the two
                                          ⍝ sub-matrices on the right half.
                ⌽@1                       ⍝ Swap the two upper sub-matrices. Given our
                                          ⍝ flip for the overall matrix above, this returns
                                          ⍝ the two upper quadrants to their original
                                          ⍝ positions.
               ,                          ⍝ Ravel: flatten the 2-by-2 matrix into a
                                          ⍝ 4-element vector
         ⌽∘⊖¨@4                           ⍝ Take the last element of the list (the lower
                                          ⍝ right quadrant originally) and flip it
                                          ⍝ along the vertical and horizontal axes. Given
                                          ⍝ the transposition above, this has the final
                                          ⍝ effect of transposition along the antidiagonal.
       ∇¨                                 ⍝ For each element in the above vector, recurse.
      ∊                                   ⍝ Recursively flatten the results into a single
                                          ⍝ vector.

```

More details on "monadic transpose scan".

Dyalog documentation on error guards.
> 7 votes

# Answer
# MATL, ~~86~~ 85 bytes

This solution is based upon Jonas Lundgren's File Exchange entry which utilizes complex numbers to generate the Hilbert curve. These complex numbers are then converted to index values to retrieve the elements of the matrix that fall along the curve.

```
nZl2/1XLJQXH1J-XI0,1L:"XJJZj1j*XKKH-JI-JH+IK-,4$h2/]XJJ1L*XJJH+J1)-XHGHXjHYj3$)1$Xd1$

```

Try it online!

**Explanation**

```
%--- Define some numbers to be used throughout ---%
n                   % Retrieve the number of elements in the input matrix
Zl2/                % Compute the order of the curve (log2(numel(i))/2)
1XL                 % Store the order in the 1L clipboard
JQ XH               % Store 1 + j in H clipboard
1J- XI              % Store 1 - j in I clipboard
0                   % Place 0 onto the stack

%--- Compute the hilbert curve ---%
1L:"                % For k = 1:order
    XJ                   % Store the top of the stack (z) in J clipboard
    JZj                  % Compute the conjugate of z (stored in J)
    1j*                  % Multiply by j to get conj(z) * j
    XK                   % Store result in K clipboard
    KH- JI- JH+ IK- 4$h  % Horizontal concatenation of K-H, J-I, J+H, and I-K
    2/                   % Divide entire array by 2
]                   % End for loop
XJ                  % Store z in J clipboard

%----- Convert complex decimal values to complex integer indices ----%
J1L*                % Multiply z by the order
XJ                  % Store result in clipboard J
JH+                 % Add 1 + j to H
J1)-                % Subtract the first element of z
XH                  % Store integer complex numbers in H

%--- Retrieve the elements from the input along the curve ---%
G HXj HYj 3$)       % Index into input using real/imag components input(real, imag)
                    % This will yield an numel(real) x numel(imag) matrix where
            % the diagonal values are the values we want
1$Xd                % Extract the diagonals using diag with one input
1$                   % Display only the top element on the stack

```
> 6 votes

# Answer
# Python 3, ~~327~~ ~~289~~ ~~275~~ ~~271~~ ~~239~~ 234 bytes

This is a solution I modified from my answer for another Hilbert curve question here. Any golfing tips are appreciated.

**Edit:** Changed how `g` is incremented and decremented. Now using `eval()` and `str.translate`. No longer using `l=len(s)`.

```
def h(s):
 t=[s[0][0]];x=y=g=0;b="A"
 for j in range(len(bin(len(s)))-3):b=b.translate({65:"-BF+AFA+FB-",66:"+AF-BFB-FA+"})
 for c in b:g+=(c<"-")-(c=="-");a=c>"B";x,y=[[x,y],[[x+1-g%4,y],[x,y+g%4-2]][g%2]][a];t+=[s[x][y]]*a
 return t

```

**Ungolfed:**

```
# the following function is implemented in the code with b=b.translate

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def matrix_to_hilbert(mat):
    length = len(mat)       # this returns the number of rows in the matrix
    if length < 2:
        return mat
    it = len(bin(length)) - 3
    hil = hilbert(it)
    output = [mat[0][0]]    # a list that starts with the first element of the matrix
    x = 0
    y = 0
    heading = 0
    for char in hil:        # navigating the Hilbert curve
        if char == "-": heading += -1
        elif char == "+": heading += 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output.append(mat[x][y])
    return output

```
> 4 votes

# Answer
# Mathcad, 302 bytes

The Mathcad program below is based on the @Sherlock9 Python program. It differs by curvifying rectangular matrices by ignoring those parts of the Hilbert Curve that lie outside of the matrix bounds. Note that as Mathcad has relatively poor string handling, I've mapped the Lindenmayer symbols to integers in the Hilbert function.

Mathcad works through a 2D interface that allows the user to place (and freely mix) mathematical expressions, plots, text, inputs and outputs. I've equated a byte to the minimum user keyboard equivalent operation to create a symbol (for example, the definition operator (:=) is entered by simply typing :.
> 3 votes

# Answer
# Uiua, 36 bytes

```
⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1

```

Try it online!

Constructs the path on the matrix directly, and uses it to index into the matrix.

```
⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1    input: matrix M of size 2^n*2^n
↯1⇡1    the initial Hilbert matrix [[0]]
ₙ2⧻,    log 2 of the length of M (= n)
⍥(...)   repeatedly construct the Hilbert matrix by calling the inner function n times...
  ∶⧻♭.   put the number of elements in the current matrix under itself
  ⊃⍉+   construct the top two submatrices: 1) transpose 2) add to each element
  ≡⊂     join horizontally
  ⇌.     create a copy and reverse its rows
  ¯+¬×2⧻♭.  a bunch of arithmetic to get the bottom two submatrices
  ⊂∶      join vertically in reverse
∩♭    flatten the Hilbert matrix and M
⊏⍏    put the elements of M in the increasing order in the Hilbert matrix

```

# Uiua, 41 bytes

```
⊡⍉∧(≡⊂∶⍜⊢-≡⇌,-1×2∶≡⊂∶⇌⍜⊢+,,⇌)↯2⇡1ⁿ∶2⇡ₙ2⧻.

```

Try it online!

Constructs the list of coordinates and indexes into the original matrix using  "pick".
> 3 votes

# Answer
# Wolfram - 233

Based on representation as Lindenmayer system:

```
f[m_]:=m[[Sequence@@Reverse[#+1]]]&/@DeleteDuplicates@AnglePath[Pi/2,List@@StringReplace[Last@SubstitutionSystem[{"A"->"-BF+AFA+FB-","B"->"+AF-BFB-FA+"},"A",Round@Sqrt@Length@m],{"A"|"B"->"","-"->{0,-Pi/2},"+"->{0,Pi/2},"F"->{1,0}}]]

```
> 2 votes

# Answer
# Ruby, ~~224~~ ~~221~~ 216 bytes

This answer is based on my Python answer.

```
->s{t=[s[0][0]];x=y=g=0;b=?A;(s.size.bit_length-1).times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};b.each_char{|c|g+=c==?-?-1:c==?+?1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t<<s[x][y])if c==?F};t}

```

**Ungolfing:**

```
def hilbert(mat)
  result = mat[0][0]
  x = 0
  y = 0
  heading = 0
  b = "A"
  (mat.size.bit_length-1).times do each |j| # Hilbert curve using a Lindenmayer system
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  b.each_char do |char| # navigating the matrix
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
      result << s[x][y]
    end
  return result
  end

```
> 2 votes

# Answer
# CJam, 60

```
Lq~:A,2mL{:B1f^0B1B2B3f^]:+}*1+{AT=U=\2md'U^_~)@2*-':@+~;}%p

```

Try it online

**Explanation:**

I'm building the fractal as a series of movement directions: 0=right, 1=down, 2=left, 3=up.

```
L          push an empty array (level 0 fractal)
q~:A       read the input, evaluate and store in A
,2mL       get the length (number of rows) and calculate the logarithm in base 2
            (to get the desired level)
{…}*       repeat <level> times
  :B       store the previous-level fractal in B
  1f^      XOR it with 1 (top-left part)
  0        (move right)
  B        copy the fractal (top right part)
  1        (move down)
  B        copy the fractal (bottom right part)
  2        (move left)
  B3f^     copy the fractal and XOR it with 3 (bottom left part)
  ]:+      put everything in an array and concatenate the parts
1+         add a dummy move (needed for the last step)
{…}%       apply to each direction in the array
  AT=U=    push A[T][U] (T and U are initially 0)
  \2md     bring the direction to the top and get the quotient and remainder mod 2
  'U^      XOR the 'U' character with the remainder,
            to get the variable we want to modify
  _~)      make a copy of it, then evaluate it and increment
  @2*-     bring the quotient to the top, multiply by 2 and subtract
  ':@+     concatenate ':' with the variable name
  ~;       evaluate (this updates the variable) and pop the result
p          pretty-print the resulting array

```
> 1 votes

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


title: Number of palindrome splits

text:
# Question
Title: Number of palindrome splits
In this task you will take as input a non-negative integer \\$n\\$, and output the number of pairs of non-negative integers \\$a,b\\$ such that both are palindromes*, \\$a \leq b\\$, and \\$a+b = n\\$. For example if \\$n\\$ is \\$22\\$ then the valid pairs are

\\$ \begin{array}{c|c} a & b \\ \hline 0 & 22 \\ 11 & 11 \\ \end{array} \\$

So the output is \\$2\\$.

As another example, if \\$n\\$ is \\$145\\$ then the valid pairs are

\\$ \begin{array}{c|c} a & b \\ \hline 4 & 141 \\ 44 & 101 \\ \end{array} \\$

So the output is 2.

Your submission should be a program or function. Answers will be scored in bytes with fewer bytes being the goal.

## Test Cases

\\$ \begin{array}{c|c c|c} \mathrm{Input} & \mathrm{Output} & \mathrm{Input} & \mathrm{Output} \\ \hline 0 & 1 & 12 & 5\\ 1 & 1 & 13 & 4\\ 2 & 2 & 14 & 4\\ 3 & 2 & 15 & 3\\ 4 & 3 & 16 & 3\\ 5 & 3 & 17 & 2\\ 6 & 4 & 18 & 2\\ 7 & 4 & 19 & 1\\ 8 & 5 & 20 & 1\\ 9 & 5 & 21 & 0\\ 10 & 5 & 22 & 2\\ 11 & 5 & 23 & 1\\ \end{array} \\$

OEIS A260254

---

* In base 10

# Answer
> 4 votes
# Jelly, 9 bytes

```
ŻŒḂ€ḋṚ$HĊ

```

A monadic Link accepting a non-negative integer which yields a non-negative integer.

**Try it online!**

### How?

Counts all pairs without the \\$a\leq b\\$ restriction, halves and rounds up. Note that the halved count is only a fraction if \\$\frac n 2\\$ is a palindrome and in such cases we want to count this \\$a=b\\$ pair.

```
ŻŒḂ€ḋṚ$HĊ - Link: integer, n    e.g. 22
Ż         - zero-range               [0,1,2,...,9,10,11,12,...,21,22]
   €      - for each:
 ŒḂ       -   is palindrome (digits) [1,1,1,...,1,0,1,0,...0,1]
      $   - last two links as a monad:
     Ṛ    -   reverse                [1,0,...,0,1,0,1,...,1,1,1]
    ḋ     -   dot-product           3  (=1×1+1×0+...+1×0+1×1+0×1+...+0×1+1×1)
       H  - halve                   1.5
        Ċ - ceil                    2

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~74~~  73 bytes

```
n=>(g=a=>a>n-a?0:![a,n-a].some(n=>[...n+''].reverse().join``-n)+g(-~a))``

```

Try it online!

# Answer
> 3 votes
# Python 2,  ~~73 70~~  63 bytes

```
lambda n:sum(`n-v`+`v`==(`v`+`n-v`)[::-1]for v in range(n/2+1))

```

**Try it online!**

Note that:

```
(string_a == reverse(string_a)) and (string_b == reverse(string_b))

```

is equivalent to

```
reverse(string_a + string_b) == (string_b + string_a)

```

(where `+` is concatenation)

# Answer
> 2 votes
# Prolog (SWI), 99 bytes

```
N-C:-aggregate_all(count,(between(0,N,A),B is N-A,B=<A,+A,+B),C).
+N:-atom_codes(N,C),reverse(C,C).

```

Try it online!

# Ungolfed Code

After adding white space, this solution reads very similarly to the challenge specification. It simply asks for the number of pairs palindrome integers within specified bounds that sum to N.

```
count_splits(N,C) :-
  aggregate_all(count,(
    between(0,N,A),
    B is N-A, B=<A,
    palindrome(A),
    palindrome(B)
  ),C).

palindrome(N) :-
  atom_codes(N,C),
  reverse(C,C).

```

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
ÝεÂQ}Â*O;î

```

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

Try it online or verify all test cases.

**Explanation:**

```
Ý        # Push a list in the range [0, (implicit) input-integer]
 ε       # Map each value to:
  Â      #  Bifurcate the value; short for Duplicate & Reverse copy
   Q     #  And check if it's equal to the value itself (1 if a palindrome; 0 if not)
 }Â      # After the map: bifurcate the entire list as well
   *     # Multiply the values at the same indices in the lists
    O    # Take the sum of that
     ;î  # And then halve and ceil it
         # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Perl 6, 44 bytes

```
{+grep {.flip eq[R,] $_},(^$_ Z($_...$_/2))}

```

Try it online!

Finds the number of pairs of numbers such that the reverse of the string representation is equal to the string representation of the reversed pair.

# Answer
> 1 votes
# Python 3.8, ~~89~~ ~~87~~ ~~68~~ 66 bytes

Adapting Jonathan's clever answer to Python 3 (with f format strings) and removing `[]` for a generator expression instead of list comprehension, we shave 21 bytes with

```
lambda n:sum(f"{i}{n-i}"==f"{n-i}{i}"[::-1]for i in range(n//2+1))

```

Try it online

My old answer:

```
lambda n:len([i for i in range(n//2+1)if(s:=str(i))==s[::-1]and(t:=str(n-i))==t[::-1]])

```

You can try it online

# Answer
> 1 votes
# Charcoal, 18 bytes

```
ＩＬΦ⊕⊘θ⬤Ｉ⟦ι⁻θι⟧⁼λ⮌λ

```

Try it online! Link is to verbose version of code. The halved input has to be incremented because `a` needs to vary over the inclusive range from `0` to `n/2`. Explanation:

```
     θ              Input `n`
    ⊘               Halved
   ⊕                Incremented
  Φ                 Filter over implicit range
        ⟦           Begin list
         ι          Current index `a`
           θ        Input `n`
            ι       Current index `a`
          ⁻         Subtracted (i.e. `b`)
             ⟧      End list
       Ｉ            Vectorised cast to string
      ⬤             Both strings satisfy
                 λ  Current string
                ⮌   Reversed
               λ    Current string
              ⁼     Are equal
 Ｌ                  Length
Ｉ                   Cast to string for implicit print

```

# Answer
> 1 votes
# PHP, ~~83~~ ~~86~~ ~~85~~ 73 bytes

```
for(;$i<=$argn/2;$i++)$k+=strrev($j=$argn-$i)==$j&&strrev($i)==$i;echo$k;

```

Try it online!

-13 bytes and bug fix thanks to @640KB

# Answer
> 1 votes
# JavaScript (Node.js),  ~~70 69~~  67 bytes

-2 thanks to Arnauld (change each string cast from `x+''+y` to `x+[y]`)

I don't really know much JavaScript, I based this around Arnauld's answer, any advice is very welcome!

```
n=>(g=a=>(v=n-a)<a?0:(v+[a]==[...a+[v]].reverse().join``)+g(-~a))``

```

**Try it online!**

Note that:

```
(string_a == reverse(string_a)) and (string_b == reverse(string_b))

```

is equivalent to

```
reverse(string_a + string_b) == (string_b + string_a)

```

(where `+` is concatenation)

# Answer
> 1 votes
# C (gcc), ~~114~~ \\$\cdots\\$ ~~105~~ 98 bytes

Saved 7 bytes thanks to rtpax!!!

```
i;m;p(n){for(i=0,m=n;i=i*10+n%10,n/=10;);n=i==m;}r;a;f(n){for(a=r=0;a<=n/2;)r+=p(a)*p(n-a++);n=r;}

```

Try it online!

# Answer
> 1 votes
# Vyxal `l`, 63 bitsv2, 7.875 bytes

```
½ʀ2('Ḃ⁼;-

```

Try it Online!

Bitstring:

```
000100100000010110000001100101111001000100100001100010110111001

```

## Explained

```
½ʀ2('Ḃ⁼;-
½ʀ         # Push the range [0, input / 2] for later
  2(       # Twice:
    'Ḃ⁼;   #   Filter the top of the stack by is palindromic
        -  #   And subtract that from the input.
        -  #   This acts as a check for pairs, by keeping numbers that are palindromes before and after subtraction
# The l flag outputs the length of the top of the stack

```

Created with the help of Luminespire.

Only took me around 3 and a half years to finally write this answer. Things sure have changed since then.

# Answer
> 0 votes
# MathGolf, 14 bytes

```
)rmÑ_x^mÅε*Σ)½

```

Try it online.

**Explanation:**

```
)               # Increase the (implicit) input-integer by 1
 r              # Pop and push a list in the range [0, input+1)
  mÑ            # Check for each value whether it's a palindrome (1 if truthy; 0 if falsey)
    _           # Duplicate this list
     x          # Reverse the copy
      ^         # Zip the two together to create pairs
       m        # Map over each pair,
        Å       # using the following two commands:
         ε      #  Reduce by:
          *     #   Multiplying
           Σ    # Then take the sum of this list
            )   # Increase this sum by 1
             ½  # And integer-divide it by 2
                # (after which the entire stack joined together is output implicitly)

```

# Answer
> 0 votes
# Perl 5 `-p`, 51 bytes

```
$\+=($,==reverse$,)&&$_==reverse;++$,<=--$_&&redo}{

```

Try it online!

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