title: Expand Exponentiation

text:
# Question
Title: Expand Exponentiation
Given two integers greater than one, A and B, output four mathematical expressions in this order:

1. The plain expression A^B (A to the power B). e.g. if A = 2 and B = 3, `2^3`.
2. The expansion of A^B in terms of repeated multiplications of A. e.g. `2*2*2`.
3. The expansion of A^B in terms of repeated additions of A. e.g. `2+2+2+2`.
4. The expansion of A^B in terms of repeated additions of 1. e.g. `1+1+1+1+1+1+1+1`.

The four expressions may be output in any reasonable way as long as they are in order and clearly distinct. For example, you might put them in a list, or print them on separate lines

```
2^3
2*2*2
2+2+2+2
1+1+1+1+1+1+1+1

```

or perhaps on one line separated by equals signs:

```
2^3=2*2*2=2+2+2+2=1+1+1+1+1+1+1+1

```

Spaces may be inserted next to math operators so

```
2^3 = 2 * 2 * 2 = 2 + 2 + 2 + 2 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

```

would be equally valid output when A = 2 and B = 3.

You may use symbols alternative to `^`, `*`, and `+`, but *only if* the new symbols are more idiomatic for your language (e.g. `**` instead of `^` in Python).

You may assume that A and B are sufficiently small so that A^B will not overflow your language's default integer type (given that that type has a reasonable maximum, 255 at least).

**The shortest code in bytes wins.**

# Test Cases

One output per line. The input can be inferred as the first expression is always A^B.

```
2^2 = 2*2 = 2+2 = 1+1+1+1
2^3 = 2*2*2 = 2+2+2+2 = 1+1+1+1+1+1+1+1
2^4 = 2*2*2*2 = 2+2+2+2+2+2+2+2 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2^5 = 2*2*2*2*2 = 2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^2 = 3*3 = 3+3+3 = 1+1+1+1+1+1+1+1+1
3^3 = 3*3*3 = 3+3+3+3+3+3+3+3+3 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^4 = 3*3*3*3 = 3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^5 = 3*3*3*3*3 = 3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
4^2 = 4*4 = 4+4+4+4 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
4^3 = 4*4*4 = 4+4+4+4+4+4+4+4+4+4+4+4+4+4+4+4 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
10^2 = 10*10 = 10+10+10+10+10+10+10+10+10+10 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
13^2 = 13*13 = 13+13+13+13+13+13+13+13+13+13+13+13+13 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

```

# Answer
# Python 3.6, ~~88~~ 74 bytes

-2 bytes thanks to Dada (use `~`)
-5 bytes thanks to Erwan (use f-strings from Python 3.6)

```
lambda a,b:f"{a}^{b}={a}{f'*{a}'*~-b}={a}{f'+{a}'*~-a**~-b}=1"+"+1"*~-a**b

```

*online ide anyone?*

### How?

This is an unnamed function taking the two integer inputs `a` and `b` each greater than `0` (even though the specification is only for those greater than `1`).

In Python 3.6 a new feature is available, namely formatted string literals or "f-strings". These allow run-time evaluated string construction. A leading `f` (or `F`) creates such a construct, e.g. `f"blah"` or `f'blah'`. Inside an f-string anything between a pair of braces, `{...}`, is an expression to be evaluated.

As such `f"{a}^{b}={a}{f'*{a}'*~-b}={a}{f'+{a}'*~-a**~-b}=1"` evaluates each of `a`, `b`, `a`, `f'*{a}'*~-b`, `a`, and `f'+{a}'*~-a**~-b}` as expressions, keeping the `^`, `=`, `=`, and `=1` as strings,all of which gets concatenated together.

The `a` and `b` expressions evaluate to the representations of `a` and `b` respectively.

The `f'*{a}'` and `f'+{a}'` in turn are also f-strings inside these expressions, which evaluate to `a` with a leading `'*'` and a leading `'+'` respectively

To create the required number of `a`s and operations for the `*` and `+` portions note that there will be `b` `a`s multiplied together and `a**(b-1)` `a`s added together. Each case then requires one less operator sign than the number of `a`s. So we can repeat the f-strings `f'*{a}`and `f'+{a}'` (using `*`) as many times as there are operators and prepend each with a single `a`. `(b-1)` is `~-b` and `(a**(b-1))-1` is `~-a**~-b`.

The same is done for the `1`s using `(a**b)-1` being `~-**b`, but we don't need the overhead of f-strings since `1` is constant, so a standard string repeated is concatenated with `+`.

---

Prior Python versions, 81:

```
lambda a,b:'%s^%s=%s=%s=1'%(a,b,('*%s'%a*b)[1:],('+%s'%a*a**~-b)[1:])+'+1'*~-a**b

```

**Try it online!**
> 11 votes

# Answer
# Cubix, ~~238 234 217 151 110~~ 100 bytes

*Saved 14 bytes thanks to ETHProductions*

```
u'^.:s+.;;;\-?W?rsos\(rrOIO:ur>'=o;^u.;;.>$.vUo^'rsu1;;@!\q?s*su;;IOu*+qU../;(*\(s.;<..r:''uq....qu\

```

Expanded:

```
          u ' ^ . :
          s + . ; ;
          ; \ - ? W
          ? r s o s
          \ ( r r O
I O : u r > ' = o ; ^ u . ; ; . > $ . v
U o ^ ' r s u 1 ; ; @ ! \ q ? s * s u ;
; I O u * + q U . . / ; ( * \ ( s . ; <
. . r : ' ' u q . . . . q u \ . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

# Try it online!

Try it here

# Explanation

The code consists of 8 steps, with two loops. I'll go over the code part by part.

# Step 1 (A^B)

```
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
I O : u . . . . . . . . . . . . . . . .
U o ^ ' . . . . . . . . . . . . . . . .
; I O u . . . . . . / ; ( * \ . . . . .
? ? r : . . . . . . ? . . . \ ? ? ? ? ?
. . . . ? . . . . . ? . . . . . . . . .
          ? ? ? ? ?
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

This is the cube with the parts that are irrelevant to the first step removed. The question mark shows the no-ops the IP will visit, to make its path more clear.

```
IO:'^o;IO:r*(; # Explanation
I              # Push the first input (A)
 O             #   output that
  :            #   duplicate it
   '^          # Push the character "^"
     o         #   output that
      ;        #   pop it from the stack
       I       # Push the second input (B)
        O      #   output that
         :     #   duplicate
          r    #   rotate top 3 elements
           *   # Push the product of the top two elements
            (  #   decrease it by one
             ; #   pop it from the stack (making the last
               #   two operations useless, but doing it
               #   this way saves 10B)

```

Now, the stack looks like this: `A, B, A, B`

# Step 2 (prepare for print loop)

The print loop takes 3 arguments (the top 3 elements on the stack): `P`, `Q` and `R`. `P` is the amount of repetitions, `Q` is the separator (character code) and `R` is the number to repeat. Luckily, the loop also takes care of the requirement that the resulting string should end in `R`, not `Q`.

We want to repeat `A*` exactly `B` times, so the separator is `*`. Note that the stack starts as `A, B, A, B`. Once again, I removed all irrelevant instructions. The IP start at the `S` pointing north.

```
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
. . . . r . . . . . . . . . . . . . . .
. . . . r . . . . . . . . . . . . . . .
. . . . * . . . . . . . . . . . . . . .
. . . . ' . . . . . . . . . . . . . . .
. . . . S . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

'*rr # Explanation
'*   # Push * (Stack: A, B, A, B, *)
  rr # Rotate top three elements twice

```

The stack is now `A, B, B, *, A`.

# Step 3/6/8 (the print loop)

## Concept

```
E . . . . .
? r s o s u
\ ( r r O <
. . . . . S

```

The IP enters the loop through `S`, pointing north, and exits the loop at `E`, pointing north again. For this explanation, the stack is set to `[..., A, B, C]`. The following instructions are executed. Note that the IP can't leave the loop before the question mark, so the first four instructions will always be executed.

```
Orr(?rsos # Explanation
O         # Output `C`
 rr       # Rotate top three elements twice (Stack: [..., B, C, A])
   (      # Decrease A by one (Stack: [..., B, C, A-1])
    ?     # If top of stack (A) > 0:
     r    #    Rotate top of stack (Stack: [..., A-1, B, C])
      s   #    Swap top elements (Stack: [..., A-1, C, B])
       o  #    Output top of stack (B) as character code
        s #    Swap top elements (Stack: [..., A-1, B, C]
          #
          # ... and repeat ...

```

## Implementation

Here's the cube again, with the irrelevant parts removed. The IP starts at `S`, pointing east.

```
          . . . . .
          . . . . .
          . . . . .
          ? r s o s
          \ ( r r O
. . . . . S ' = o ; ^ u . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

As you can see, the IP comes across four instructions before it enters the loop. Since the character code is removed again, we reach the loop with the exact same stack as we entered this part.

```
'=o; # Explanation
'=   # Push =
  o  #     Output
   ; #     Pop from stack

```

Inside the loop, the explanation above holds.

# Step 4 (differentiating the IPs)

Since we use the above loop multiple times, and they all cause the IP to end up in the same spot, we have to differentiate between multiple runs. First, we can distinguish between the separator (first run has a `*`, whereas runs two and three have a `+` as separator). We can differentiate between runs 2 and 3 by checking the value of the number that is repeated. If that is one, the program should terminate.

## First comparison

Here's what it looks like on the cube. The IP starts at S and points north. The stack contains `[..., * or +, A or 1, 0]`. The number 1 shows where the IP will end up if this is the first loop (pointing north) and the number 2 shows where the IP will end up if this is the second (or third) loop (pointing east).

```
          u ' . . .
          s + . 1 .
          ; \ - ? 2
          S . . . .
          . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

;s'+-? # Explanation
;      # Delete top element (0)
 s     # Swap the top two elements (Stack: 1/A, */+)
  '+   # Push the character code of +
    -  # Subtract the top two elements and push
       #  that to the stack (Stack: 1/A, */+, +, (*/+)-+)
     ? # Changes the direction based on the top
       # item on the stack. If it's 0 (if (*/+) == +)
       # the IP continues going right, otherwise, it
       # turns and continues going north.

```

If the IP now is at `1`, the stack is `[A, *, +, -1]`. Otherwise, the stack is `[A or 1, +, +, 0]`. As you can see, there still is an unknown in the stack of the second case, so we have to do another comparison.

## Second comparison

Because the IP has gone through step 5, the stack looks like this: `[A^(B-1) or nothing, A or 1, +, +, 0]`. If the first element is `nothing`, the second element is `1`, and the reverse holds too. The cube looks like this, with the IP starting at S and pointing east. If this is the second loop, the IP ends up at `E`, pointing west. Otherwise, the program hits the `@` and terminates.

```
          . . . . .
          . . . . ;
          . . . S W
          . . . . .
          . . . . .
. . . . . . . . . . . . . ; . . . . . .
. . . . . . . . . E @ ! \ q . . . . . .
. . . . . . . . . . . . ( * . . . . . .
. . . . . . . . . . . . q u . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

The instructions executed that don't do anything to the control flow are listed below.

```
;;q*q(!@
;;       # Delete top two elements (Stack [A^(B-1)/null, A/1, +])
  q      # Send top element to the bottom (Stack [+, A^(B-1)/0, A/1])
   *     # Push product of top two elements
         #    (Stack [+, A^(B-1)/0, A/1, A^B/0])
    q    # Send top element to the bottom
         #    (Stack [A^B/0, +, A^(B-1)/0, A/1])
     (   # Decrease the top element by 1
         #    (Stack [A^B/0, +, A^(B-1)/0, (A-1)/0])
      !  # If (top element == 0):
       @ #  Stop program

```

The stack is now `[A^B, +, A^(B-1), A-1]`, provided the program didn't terminate.

# Step 5 (preparing for "A+" (repeat A^(B-1)))

Sadly, Cubix doesn't have a power operator, so we need another loop. However, we need to clean up the stack first, which now contains `[B, A, *, +, -1]`.

## Cleaning up

Here's the cube again. As usual, the IP starts at S (pointing north), and ends at E, pointing west.

```
          . . . ? .
          . . . ; .
          . . . S .
          . . . . .
          . . . . .
. . . . . . . . . . . . . . . . > $ . v
. . . . . . . . . . . . . . . . . . . ;
. . . . . . . . . . . . . . . . . . E <
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

;; # Explanation
;; # Remove top 2 elements (Stack: [B, A, *])

```

## Calculating A^(B-1)

Another loop which works roughly the same as the print loop, but it's a bit more compact. The IP starts at `S`, pointing west, with stack `[B, A, *]`. The IP exits at `E` pointing north.

```
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
. . . . . . . . . . . . . . E . . . . .
. . . . . . . . . . . . . . ? s * s u .
. . . . . . . . . . . . . . \ ( s . ; S
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

The loop body is the following.

```
;s(?s*s # Explanation
;       # Pop top element.
 s      # Shift top elements.
  (     # Decrease top element by one
   ?    # If not 0:
    s   #    Shift top elements again
     *  #    Multiply
      s #    Shift back
        #
        # ... and repeat ...

```

The resulting stack is `[A, A^(B-1), 0]`.

## Cleaning up the stack (again)

Now we need to get to the print loop again, with the top of the stack containing `[..., A^(B-1), +, A]`. To do this, we execute the following. Here's the cube again,

```
          . . ^ ? :
          . . . . .
          . . . . .
          . . . . .
          E . . . .
. . . . . s . . . . . . . . ; . . $ . .
. . . . . + q U . . . . . . S . . s . .
. . . . . ' u q . . . . . . . . . ? . .
. . . . . . . ? . . . . . . . . . ? . .
. . . . . . . ? . . . . . . . . . ? . .
          . . ? . .
          . . ? . .
          . . ? . .
          . . ? . .
          . . ? . .

;:$sqq'+s # Explanation
;         # Delete top element (Stack: [A, A^(B-1)])
 :        # Copy top element
  $s      # No-op
    qq    # Send top two elements to the bottom
          #   (Stack: [A^(B-1), A^(B-1), A])
      '+  # Push +
          #   (Stack: [A^(B-1), A^(B-1), A, +])
        s # Swap top two elements
          #   (Stack: [A^(B-1), A^(B-1), +, A])

```

# Step 7 (preparing for last loop)

The stack is now `[A^B, +, A^(B-1), A-1]`, the IP starts at `S`, going west, and ends at `E`, going right.

```
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
. . . . . E . . . . . . . . . . . . . .
. . . . . . u 1 ; ; S . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .
          . . . . .

```

The instructions executed:

```
;;1 # Explanation
;;  # Delete top two elements
  1 # Push 1

```

The stack now looks like `[A^B, +, 1]`, and the IP is about to enter the print loop, so we're done.
> 11 votes

# Answer
# MATL, 46 bytes

```
XH'^'i'='XJ2G:"H'*']xJ&Gq^:"H'+']xJ&G^:"1'+']x

```

Try it online!

Stretching the limits of "reasonable way" here, but the expressions are separated.

## Explanation

First expression:

```
XH'^'i'='XJ

XH         % implicitly take input A, save it to clipboard H
'^'        % push literal '^'
i          % take input B
'='        % push literal '='
XJ         % copy '=' to clipboard J, we'll use this twice more so it's worth it

```

Second expression:

```
2G:"H'*']xJ

2G         % paste the second input (B) again
:"         % do the following B times
  H        % paste A from clipboard H
  '*'      % push literal '*'
]          % end loop
x          % delete the final element (at the moment we have a trailing *)
J          % paste '=' from clipboard J

```

Third expression:

```
&Gq^:"H'+']xJ

&G         % paste all of the input, ie push A and B
q          % decrement B
^          % power, giving A^(B-1)
:"         % do the following A^(B-1) times
  H        % paste A from clipboard H
  '+'      % push literal '+'
]          % end loop
x          % delete the final element (at the moment we have a trailing +)
J          % paste '=' from clipboard J

```

Fourth expression:

```
&G^:"1'+']x

&G         % paste all of the input, ie push A and B
^          % power, giving A^B
:"         % do the following A^B times
  1        % push 1
  '+'      % push '+'
]          % end loop
x          % delete the final element (at the moment we have a trailing +)
           % (implicit) convert all to string and display

```
> 7 votes

# Answer
## JavaScript (ES7), 78 bytes

Takes input in currying syntax `(a)(b)`. Outputs a string.

```
a=>b=>a+'^'+b+(g=o=>'='+a+('+*'[+!o]+a).repeat(b-1))()+g(b=a**~-b)+g(b*=a,a=1)

```

### Test cases

```
let f =

a=>b=>a+'^'+b+(g=o=>'='+a+('+*'[+!o]+a).repeat(b-1))()+g(b=a**~-b)+g(b*=a,a=1)

console.log(f(2)(2));
console.log(f(2)(3));
console.log(f(2)(4));
console.log(f(2)(5));
console.log(f(3)(2));
console.log(f(3)(3));
console.log(f(3)(4));
console.log(f(3)(5));
console.log(f(4)(2));
console.log(f(4)(3));
console.log(f(10)(2));
console.log(f(13)(2));
```
> 5 votes

# Answer
## Ruby, 52 bytes

```
->a,b{[[a,b]*?^,[a]*b*?*,[a]*a**~-b*?+,[1]*a**b*?+]}

```
> 3 votes

# Answer
# 05AB1E, 30 bytes

```
mUð¹'^²J'*¹«²×'+¹«X¹÷×„+1X×)€¦

```

Explanation:

```
mU                               # Store a^b in variable X
  ð                              # Push a space character to the stack (will be deleted at the end, but this is needed to keep the character count low)
   ¹'^²J                         # Push the string "a^b" to the stack
        '*¹«                     # Push the string "*a" to the stack
            ²×                   # Repeat b times
              '+¹«               # Push the string "+a" to the stack
                  «X¹÷×          # Repeat a^b / a times
                       „+1       # Push the string "+1" to the stack
                          X×     # Repeat a^b times
                            )    # Wrap stack to array
                             €¦  # Remove the first character from each element in the array

```

Try it online!
> 3 votes

# Answer
# C (gcc), ~~156~~ 149 bytes

```
#define q for(x=0;x
x,y;p(a,b,c){printf("%c%d",x?b:61,c),x+=a;}e(n,i){x=1;p(0,0,n);p(0,94,i);y=!!i;q<i;y*=n)p(1,42,n);q<y;)p(n,43,n);q<y;)p(1,43,1);}

```

*-2 bytes* if we can ignore 0 powers; `y=!!i` may become `y=1`

Try it online!
> 2 votes

# Answer
# Java 7, 170 bytes

```
String c(int a,int b){String s="=",r=a+"^"+b+s+a;double i=0,x=Math.pow(a,b);for(;++i<b;r+="*"+a);r+=s+a;for(i=0;++i<x/a;r+="+"+a);r+=s+1;for(i=0;++i<x;r+="+1");return r;}

```

**Ungolfed:**

```
String c(int a, int b){
  String s = "=",
         r = a+"^"+b+s+a;
  double i = 0,
         x = Math.pow(a,b);
  for(; ++i < b; r += "*"+a);
  r += s+a;
  for(i = 0; ++i < x/a; r += "+"+a);
  r += s+1;
  for(i = 0; ++i < x; r += "+1");
  return r;
}

```

**Test code:**

Try it here.

```
class M{
  static String c(int a,int b){String s="=",r=a+"^"+b+s+a;double i=0,x=Math.pow(a,b);for(;++i<b;r+="*"+a);r+=s+a;for(i=0;++i<x/a;r+="+"+a);r+=s+1;for(i=0;++i<x;r+="+1");return r;}

  public static void main(String[] a){
    System.out.println(c(2,2));
    System.out.println(c(2,3));
    System.out.println(c(2,4));
    System.out.println(c(2,5));
    System.out.println(c(3,2));
    System.out.println(c(3,3));
    System.out.println(c(3,4));
    System.out.println(c(3,5));
    System.out.println(c(4,2));
    System.out.println(c(4,3));
    System.out.println(c(10,2));
    System.out.println(c(13,2));
  }
}

```

**Output:**

```
2^2=2*2=2+2=1+1+1+1
2^3=2*2*2=2+2+2+2=1+1+1+1+1+1+1+1
2^4=2*2*2*2=2+2+2+2+2+2+2+2=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2^5=2*2*2*2*2=2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^2=3*3=3+3+3=1+1+1+1+1+1+1+1+1
3^3=3*3*3=3+3+3+3+3+3+3+3+3=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^4=3*3*3*3=3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
3^5=3*3*3*3*3=3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
4^2=4*4=4+4+4+4=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
4^3=4*4*4=4+4+4+4+4+4+4+4+4+4+4+4+4+4+4+4=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
10^2=10*10=10+10+10+10+10+10+10+10+10+10=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
13^2=13*13=13+13+13+13+13+13+13+13+13+13+13+13+13=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

```
> 2 votes

# Answer
# Brainfuck, 372 bytes

```
,.>++++++++[>++++++++++++>++++++++>+++++<<<-]>--.<,.>>---.>++>++++++++[<<<<------>>>>-]<<<<-[<.>>>>.>>+<<<<<-]<.>>>.<<++++++++[<------>-]<[>+>>>>+<<<<<-]>>>>>>>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]>[<+>>+<-]>[<+>-]<<<<<<<<++++++++[>++++++<-]>>>>+>>-[<<<<<.>>>.>>-]<<<<<.>>.>>>>[<+>-]<<[->[->+>+<<]>>[-<<+>>]<<<]>>>++++++++[<<<++++++>>>-]<<<+>>-[<<.<.>>>-]<<.

```

Try it online!

# Notes

1. The two inputs must be chosen in such a way, that `A**B` does not exceed `255`. This is because brainfuck can only store values of one byte.
2. If one input is bigger than 9, use the next ASCII character. `10` becomes `:`, `11` becomes `;` etc. This is because Brainfuck can only take inputs of one byte.

# Explanation

Here is my somewhat commented code. I'll expand on this later.

```
,.                      print A
> +++++ +++
[
    > +++++ +++++ ++    set up 96 (for ^ sign)
    > +++++ +++         set up 64 (for = sign)
    > +++++             set up 40 (for plus and * sign)
    <<< -
]
> --.                   print ^
< ,.                    print B
>
> ---.                  print =
> ++                    prepare *

> +++++ +++             convert B from char code
[
    <<<< ----- -
    >>>> -
]

<<<< -                  print loop "A*"
[
    < .
    >>>> .
    >> +
    <<<<< -
]
< .                     print final A
>>> .                   print =

<< +++++ +++            convert A from char code
[
    < ----- -
    > -
]

<
[                       duplicate A
    > +
    >>>> +
    <<<<< -
]

>>>>>                   exponentiation (A**(B minus 1))
>>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]<

>>
[                       duplicate
    < +
    >> +
    < -
]

>[<+>-]                 move

<<<<< <<< +++++ +++     convert A to char code
[
    > +++++ +
    < -
]

>>>> +                  convert * to plus sign
>> -                    print loop "A plus"
[
    <<<< < .
    >>> .
    >> -
]
<<<<< .                 print final A
>> .                    print =

>>>>                    move
[
    < +
    > -
]

                        multiply A**(B minus 1) by A
<<[->[->+>+<<]>>[-<<+>>]<<<]

>>> +++++ +++           generate the char code for 1 (49)
[                           generate 8*6 = 48
    <<< +++++ +
    >>> -
]
<<< +                       add one

>> -                    print loop "1 plus"
[
    << .
    < .
    >>> -
]
<< .                    print final 1

```
> 2 votes

# Answer
## Javascript ~~115~~ ~~113~~ 104 bytes

Thanks to @Neil and @TuukkaX for golfing off one byte each and @ETHproductions and Luke for golfing off 9 bytes

```
a=>b=>[a+'^'+b,(a+'*').repeat(b-1)+a,(a+'+').repeat(Math.pow(a,b-1)-1)+a,1+'+1'.repeat(Math.pow(a,b)-1)]

```

Try it Online
> 1 votes

# Answer
# Pip, ~~38~~ ~~35~~ 34 bytes

33 bytes of code, +1 for `-n` flag.

```
Ya**b[gJ'^aRLbJ'*aRLy/aJ'+1XyJ'+]

```

Takes A and B as command-line arguments; prints one expression per line. Try it online!

### Explanation

`Ya**b` is setup code: yank `a**b` into the `y` variable. After that, we have a list (in `[]`) containing our four expressions:

* `gJ'^`: take full ar`g`list (here, a list containing `a` and `b`) and `J`oin it on `^`
* `aRLbJ'*`: use `R`epeat`L`ist to create a list with `b` copies of `a`, then `J`oin it on `*`
* `aRLy/aJ'+`: use `RL` to create a list with `y/a` (i.e. `a**(b-1)`) copies of `a`, then `J`oin it on `+`
* `1XyJ'+`: `1`, string-multiplied by `y`, `J`oined on `+`

The list is printed with newline as the separator thanks to the `-n` flag.
> 1 votes

# Answer
# Jelly, 29 bytes

```
*⁹’,¤;@
,`;1ẋ"ç
,W;çj"“^*++”Y

```

**Try it online!**

### How?

```
*⁹’,¤;@ - Link 1, get list lengths: a, b
    ¤   - nilad followed by link(s) as a nilad
 ⁹      - right: b
  ’     - decrement: b-1
   ,    - pair with right: [b-1, b]
*       - exponentiate: [a^(b-1), a^b]
     ;@ - concatenate with reversed arguments: [b, a^(b-1), a^b]

,`;1ẋ"ç - Link 2, create lists: a, b
 `      - monad from dyad by repeating argument
,       - pair: [a, a]
  ;1    - concatenate 1: [a, a, 1]
      ç - last link (1) as a dyad: [b, a^(b-1), a^b]
     "  - zip with the dyad...
    ẋ   -     repeat list:  [[a, a, ..., a], [a, a, ..., a], [1, 1, ..., 1]]
                                <- b ->       <- a^(b-1) ->     <- a^b ->

,W;çj"“^*++”Y - Main link: a, b
,             - pair: [a, b]
 W            - wrap: [[a, b]]
   ç          - last link (2) as a dyad: [[a, a, ..., a], [a, a, ..., a], [1, 1, ..., 1]]
  ;           - concatenate [[a, b], [a, a, ..., a], [a, a, ..., a], [1, 1, ..., 1]]
      “^*++”  - list of characters: ['^', '*', '+', '+']
     "        - zip with the dyad...
    j         -     join: ["a^b", "a*a*...*a", "a+a+...+a", "1+1+...+1"]
            Y - join with line feeds
              - implicit print

```
> 1 votes

# Answer
# tinylisp repl, ~~178~~ 186 bytes

```
(load library
(d W(q((_ N S #)(i(e # 1)(c N _)(W(c S(c N _))N S(s # 1
(d ^(q((x y)(i y(*(^ x(s y 1))x)1
(d X(q((A B)(list(list A(q ^)B)(W()A(q *)B)(W()A(q +)(^ A(s B 1)))(W()1(q +)(^ A B

```

Using the repl saves 8 bytes in implied closing parentheses at the ends of lines. Defines a function `X` which takes two numbers and returns a list of expressions. Each expression is parenthesized, with spaces around the operators (actually, it's a list of numbers and operator symbols):

```
((2 ^ 3) (2 * 2 * 2) (2 + 2 + 2 + 2) (1 + 1 + 1 + 1 + 1 + 1 + 1 + 1))

```

Hopefully this output format is acceptable. Try it online! (with several test cases).

### Explanation

```
(load library)

```

We need two functions from the standard library: `list` and `*`.

```
(d W(q((_ N S #)(i(e # 1)(c N _)(W(c S(c N _))N S(s # 1))))))

```

Define a function `W` (short for "weave") that takes an accumulator `_`, a number `N`, a symbol `S`, and a count `#`. We will use this function to generate most our expressions: for example, `(W () 2 (q +) 3)` will result in `(2 + 2 + 2)`.

If the count is 1 `(e # 1)`, then cons the number to the front of the accumulator `(c N _)` and return that. Otherwise, recurse:

* New accumulator is `(c S(c N _))`: the symbol and the number cons'd to the front of the previous accumulator;
* `N` and `S` are the same;
* New count is `(s # 1)`: count - 1.

The accumulator idiom is needed to achieve proper tail recursion, preventing a recursion depth error. (This change is responsible for the +8 to the byte count. The `13^2` case didn't work in the previous version.)

```
(d ^(q((x y)(i y(*(^ x(s y 1))x)1))))

```

Unfortunately, the library has no exponentiation function at this time, so we have to define one. `^` takes `x` and `y`. If `y` is truthy (nonzero), we recurse with `y-1` (`(s y 1)`) and multiply the result by `x`. Otherwise, `y` is zero and we return `1`.

(Note: This function does *not* use proper tail recursion. I assume that the exponents will be small enough that it won't matter. Some experimenting on TIO indicated a maximum exponent of 325, which I would argue should be sufficient for this question. If the OP disagrees, I will change it.)

```
(d X(q((A B)(list(list A(q ^)B)(W()A(q *)B)(W()A(q +)(^ A(s B 1)))(W()1(q +)(^ A B))))))

```

Finally, the function we're interested in, `X`, takes `A` and `B` and returns a list of four items:

* `(list A(q ^)B)`: a list containing `A`, a literal `^`, and `B`;
* `(W()A(q *)B)`: call `W` to get a list of `B` copies of `A`, interwoven with literal `*`;
* `(W()A(q +)(^ A(s B 1)))`: call `W` to get a list of `A^(B-1)` copies of `A`, interwoven with literal `+`;
* `(W()1(q +)(^ A B))`: call `W` to get a list of `A^B` copies of `1`, interwoven with literal `+`.
> 1 votes

# Answer
# Pyth, ~~32~~ 31 bytes

```
AQjMC,"^*++"[Q*]GH*^GtH]G*]1^GH

```

Takes input as `[2,10]`, outputs as `["2^10", "2*2*2*2*2*2*2*2*2*2", "2+2+...`

Explanation:

```
Q = eval(input())                     #
G, H = Q                              #  AQ
operators = "^*++"                    #        "^*++"
operands = [Q,                        #              [Q
  [G]*H,                              #                *]GH
  G**(H-1)*[G]                        #                    *^GtH]G
  [1]*G**H                            #                           *]1^GH
]                                     #
map( lambda d: join(*d),              #    jM
     zip(operators, operands)         #      C,...
)                                     #

```

Try it here.
> 0 votes

# Answer
# Perl, 81 bytes

78 bytes of code + `-n` flag (counted as 3 bytes since the code contains `$'`).

```
$,=$/;print s/ /^/r,map{/\D/;join$&,($`)x$'}"$`*$'","$`+".$`**~-$',"1+".$`**$'

```

Try it online!
> 0 votes

# Answer
## R, 147 bytes

```
w=switch;function(A,B)for(s in letters[1:4]){cat(rep(w(s,d=1,a=c(A,B),b=,c=A),w(s,a=1,b=B,c=A^B/A,d=A^B)),sep=w(s,a="^",b="*",d=,c="+"));cat("\n")}

```

Anonymous function that outputs the required, well, outputs, line-by-line. This solution makes extensive use of the `switch` function.

The `switch` function takes an expression (here, `s`) that evaluates to a number or a character string (see `?switch`), followed by the alernatives corresponding to `s`. If an alternative is missing (e.g. `switch(s, a=, b= "PPCG")`, the next non-missing alternative is evaluated (in the example, `s="a"` outputs `"PPCG"`).

The `rep` functions repeats (replicates, actually) its first argument the number of times indicated in the second argument.

`cat`, to finish, concatenate and prints the objects, with a separator that can be chosen with the `sep =` argument. The second `cat` function is here for the line-break.

**Ungolfed:**

```
f=function(A,B)
    for(s in letters[1:4]){
        cat(
            rep(switch(s, d = 1, a = c(A,B), b =, c = A),
            switch(s, a = 1, b = B, c = A^B/A, d = A^B)),
        sep=switch(s,a = "^", b = "*", d =, c = "+"))
    cat("\n")
}

```
> 0 votes

# Answer
# CJam, 42 bytes

```
q_'#/)i*_'**\__:i:*_@0=i/@0=*'+*\'1*'+*]N*

```

Try it online!
> 0 votes

# Answer
# k, 44 bytes

```
{"^*++"{x/$y}'(x,y;y#x;(x*y-1)#x;(*/y#x)#1)}

```

Test cases.
> 0 votes

# Answer
# Cardinal 202 bytes

```
%:.~:#"^"."=">v
x            "~
             *.
     >~=088v "~
     v88+88< ?
     8       -
     8      x#<
     v     < 0
     >   t / <
v~.~ <#"="?<
-
#?"+"^t
0
V
#?"="  >"1"-v
/ {   <^"+"?<
>     ^

```

Will only work for numbers where the calculated value \<256 due to limitations in the values that can be held by pointers in Cardinal

Try it Online

# Explanation:

## Step 1

```
%:.~:#"^"."="

```

Receives two numbers a and b as input and outputs as "a^b="
Passes a pointer with active value a and inactive value b

## Step 2

```
        >v
        "~
        *.
>~=088v "~
v88+88< ?
8       -
8      x#<
v     < 0
>   t / <

```

Receives a pointer with active value a and inactive value b printing "a"+("\*a")(b-1) times
Passes a pointer with active value a^(b-1) to the next part

## Step 3

```
v~.~ <#"="?<
-
#?"+"^t
0
V
#?"="
/ {   <
>     ^

```

Receives a pointer with value of a^(b-1) and outputs "=a"+("+a")repeated(a^(b-1)-1)times+"="
Passes a pointer with value a^b to the next part

## Step 4

```
>"1"-v
^"+"?<

```

Receives a pointer with value a^b and prints out "1"+("+1")repeated a^b-1 times
> 0 votes

# Answer
# Retina, ~~89~~ 88 bytes

```
*`,
^
+`(1+),1
$1*$1,
:`.1+.$

{`^[1+]+
a$&z
+`a(.+)z.1
$1+a$1z*
)`.a.+z.

:`a

+`11
1+1

```

Input is comma separated unary numbers.

Try it online!
> 0 votes

---
Tags: code-golf, math, number, arithmetic
---


title: Round the string

text:
# Question
Title: Round the string
Some decimal numbers cannot be precisely represented as binary floats due to the internal representation of the binary floats. For example: rounding 14.225 to two decimal digits does not result in 14.23 as one might expect but in 14.22.

**Python**:

```
In: round(14.225, 2)
Out: 14.22

```

Assume, however, that we have a string representation of 14.225 as '14.225', we should be able to achieve our desired rounding '14.23' as a string representation.

This approach can be generalized to arbitrary precision.

# Possible Python 2/3 Solution

```
import sys

def round_string(string, precision):
    assert(int(precision) >= 0)
    float(string)

    decimal_point = string.find('.')
    if decimal_point == -1:
        if precision == 0:
            return string
        return string + '.' + '0' * precision

    all_decimals = string[decimal_point+1:]
    nb_missing_decimals = precision - len(all_decimals)
    if nb_missing_decimals >= 0:
        if precision == 0:
            return string[:decimal_point]
        return string + '0' * nb_missing_decimals

    if int(all_decimals[precision]) < 5:
        if precision == 0:
            return string[:decimal_point]
        return string[:decimal_point+precision+1]

    sign = '-' if string[0] == '-' else ''
    integer_part = abs(int(string[:decimal_point]))
    if precision == 0:
        return sign + str(integer_part + 1)
    decimals = str(int(all_decimals[:precision]) + 1)
    nb_missing_decimals = precision - len(decimals)
    if nb_missing_decimals >= 0:
        return sign + str(integer_part) + '.' + '0' * nb_missing_decimals + decimals
    return sign + str(integer_part + 1) + '.' + '0' * precision

```

Try it online!

**Usage**:

```
     # No IEEE 754 format rounding
In:  round_string('14.225',2)
Out: '14.23'

     # Trailing zeros
In:  round_string('123.4',5)
Out: '123.40000'

In: round_string('99.9',0)
Out: '100'

    # Negative values
In: round_string('-99.9',0)
Out: '-100'

In: round_string('1',0)
Out: '1'

    # No unnecessary decimal point
In: round_string('1.',0)
Out: '1'

    # No unnecessary decimal point
In: round_string('1.0',0)
Out: '1'

In:  for i in range(8):
         print(round_string('123456789.987654321',i))
Out: 123456790
     123456790.0
     123456789.99
     123456789.988
     123456789.9877
     123456789.98765
     123456789.987654
     123456789.9876543

```

# Task

**Input argument 1**: a string containing

* at least one digit (`0`, `1`, `2`, `3`, `4`, `5`,`6`, `7`, `8`, `9`),
* at most one decimal point (`.`) which must be preceded by at least one digit,
* an optional minus (`-`) as first character.

**Input argument 2**: a non-negative integer

**Output**: the correctly rounded (base 10) string

rounding = Round half away from zero

This is a . The lowest number of bytes wins!

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

Dyalog APL uses enough internal precision.

```
⎕⍕⍎⍞

```

Try it online!

`⍎⍞` execute string input

`⎕⍕` get numeric input and use that as precision for formatting

# Answer
> 5 votes
# Perl, ~~22~~ 20 bytes

```
printf"%.*f",pop,pop

```

Using:

```
perl -e 'printf"%.*f",pop,pop' 123456789.987654321 3

```

It is Dada’s version of code. Previous:

```
printf"%*2\$.*f",@ARGV

```

# Answer
> 5 votes
# PHP, ~~33~~ 31 bytes

PHP rounds correctly too (at least on 64 bit):

```
printf("%.$argv[2]f",$argv[1]);

```

takes input from command line arguments. Run with `-r`.

# PHP, no built-ins, 133 bytes

```
[,$n,$r]=$argv;if($p=strpos(_.$n,46))for($d=$n[$p+=$r],$n=substr($n,0,$p-!$r);$d>4;$n[$p]=(5+$d=$n[$p]-4)%10)$p-=$n[--$p]<"/";echo$n;

```

Run with `-nr` or test it online.

**breakdown**

```
[,$n,$r]=$argv;             // import arguments
if($p=strpos(_.$n,46))      // if number contains dot
    for($d=$n[$p+=$r],          // 1. $d= ($r+1)-th decimal
        $n=substr($n,0,$p-!$r); // 2. cut everything behind $r-th decimal
        $d>4;                   // 3. loop while previous decimal needs increment
        $n[$p]=(5+$d=$n[$p]-4)%10   // B. $d=current digit-4, increment current digit
    )
        $p-=$n[--$p]<"/";           // A. move cursor left, skip dot
echo$n;

```

A null byte doesn´t work; so I have to use `substr`.

# Answer
> 4 votes
# Python, ~~114~~  ~~105~~ ~~103~~ ~~96~~ ~~91~~ 89 bytes

Saved 5 bytes thanks to *Kevin Cruijssen*
Saved 2 bytes thanks to *Krazor*

```
from decimal import*
d=Decimal
lambda x,y:d(x).quantize(d('0.'[y>0]+'1'*y),ROUND_HALF_UP)

```

Try it online!

# Answer
> 4 votes
## REXX, 24 bytes

```
arg n p
say format(n,,p)

```

Since REXX always uses text representation of numbers, correct rounding of numbers is free.

Try it online!

# Answer
> 4 votes
## Ruby 2.3, 12 + 45 = 57

Uses the `BigDecimal` built-in, but it needs to be required before use, which is cheaper to do as a flag.

the flag: `-rbigdecimal`

the function:

```
->(s,i){BigDecimal.new(s).round(i).to_s('f')}

```

Ruby 2.3 by default uses `ROUND_HALF_UP`

# Answer
> 4 votes
# Javascript (ES6), 44 bytes

```
n=>p=>(Math.round(n*10**p)/10**p).toFixed(p)

```

### Try it online:

```
const f = n=>p=>(Math.round(n*10**p)/10**p).toFixed(p)

console.log(f('14.225')(2));

[...Array(8).keys()].map(i=>console.log(f('123456789.987654321')(i)))

console.log(f('123.4')(5))
```

# Answer
> 3 votes
# TI-Basic, ~~53~~ 16 bytes

TI-Basic does not use IEEE and the below method works for 0-9 (inclusive) decimal positions.

```
Prompt Str1,N
toString(round(expr(Str1),N

```

Thanks to @JulianLachniet for showing that CE calcs have the `toString(` command which I was not aware of (Color Edition calcs OS 5.2 or higher are required).

P.S. I did have a second line with `sub(Str1,1,N+inString(Str1,".` but then I realized it was useless.

# Answer
> 3 votes
# Java 7, ~~77~~ ~~72~~ 71 bytes

```
<T>T c(T n,int d){return(T)"".format("%."+d+"f",new Double(n+""));}

```

-1 byte thanks to *@cliffroot*

**72-byte answer:**

```
String c(String n,int d){return n.format("%."+d+"f",new Double(n));}

```

Unlike Python, Java already rounds correctly and already returns a String when you use `String.format("%.2f", aDouble)` with the `2` replaced with the amount of decimals you want.

EDIT/NOTE: Yes, I'm aware `new Float(n)` is 1 byte shorter than `new Double(n)`, but apparently it fails for the test cases with `123456789.987654321`. See this test code regarding Double vs Float.

**Explanation:**

```
<T> T c(T n, int d){               // Method with generic-T & integer parameters and generic-T return-type (generic-T will be String in this case)
  return (T)"".format("%."+d+"f",  //  Return the correctly rounded output as String
    new Double(n+""));             //  After we've converted the input String to a decimal
}                                  // End of method

```

**Test code:**

Try it here.

```
class M{
  static <T>T c(T n,int d){return(T)"".format("%."+d+"f",new Double(n+""));}

  public static void main(String[] a){
    System.out.println(c("14.225", 2));
    System.out.println(c("123.4", 5));
    System.out.println(c("99.9", 0));
    System.out.println(c("-99.9", 0));
    System.out.println(c("1", 0));
    System.out.println(c("1.", 0));
    System.out.println(c("1.0", 0));
    for(int i = 0; i < 8; i++){
      System.out.println(c("123456789.987654321", i));
    }
  }
}

```

**Output:**

```
14.23
123.40000
100
-100
1
1
1
123456790
123456790.0
123456789.99
123456789.988
123456789.9877
123456789.98765
123456789.987654
123456789.9876543

```

# Answer
> 3 votes
# BASH, ~~26~~ ~~23~~ 21 bytes

```
bc<<<"scale=$2;$1/1"

```

## usage

save to round\_string.sh, chmod +x round\_string.sh

```
./round_string.sh 23456789.987654321 3

```

edit:no need to load library

# Answer
> 3 votes
# AHK, 25 bytes

```
a=%1%
Send % Round(a,%2%)

```

Again I am foiled by the inability of AHK to use passed in parameters directly in functions that accept either a variable name or a number. If I replace `a` with `1` in the `Round` function, it uses the value `1`. If I try `%1%`, it tries to use the first argument's *contents* as a variable name, which doesn't work. Having to set it as another variable first cost me 6 bytes.

# Answer
> 3 votes
## Batch, 390 bytes

```
@echo off
set s=%1
set m=
if %s:~,1%==- set m=-&set s=%s:~1%
set d=%s:*.=%
if %d%==%s% (set d=)else call set s=%%s:.%d%=%%
for /l %%i in (0,1,%2)do call set d=%%d%%0
call set/ac=%%d:~%2,1%%/5
call set d=00%s%%%d:~,%2%%
set z=
:l
set/ac+=%d:~-1%
set d=%d:~,-1%
if %c%==10 set c=1&set z=%z%0&goto l
set d=%m%%d:~2%%c%%z%
if %2==0 (echo %d%)else call echo %%d:~,-%2%%.%%d:~-%2%%

```

Explanation. Starts by extracting the sign, if applicable. Then, splits the number into integer and fraction digits. The fraction is padded with `n+1` zeros to ensure it has more than `n` digits. The `n`th (zero-indexed) digit is divided by 5, and this is the initial carry. The integer and `n` fraction digits are concatenated, and the carry added character by character. (The extra zeros guard against carry ripple.) After the carry stops rippling the number is reconstructed and any decimal point inserted.

# Answer
> 2 votes
## Python (2/3), 394 bytes

```
def rnd(s,p):
    m=s[0]=='-'and'-'or''
    if m:s=s[1:]
    d=s.find('.')
    l=len(s)
    if d<0:
        if p>0:d=l;l+=1;s+='.'
        else:return m+s
    e=(d+p+1)-l
    if e>0:return m+s+'0'*e
    o=''
    c=0
    for i in range(l-1,-1,-1):
        x=s[i]
        if i<=d+p:
            if i!=d:
                n=int(x)+c
                if n>9:n=0;c=1
                else:c=0
                o+=str(n)
            else:
                if p>0:o+=x
        if i==d+p+1:c=int(x)>4
    if c:o+='1'
    return m+''.join(reversed(o))

```

Works for arbitrary precision numbers.

# Answer
> 2 votes
## JavaScript (ES6), 155 bytes

```
(s,n)=>s.replace(/(-?\d+).?(.*)/,(m,i,d)=>i+'.'+(d+'0'.repeat(++n)).slice(0,n)).replace(/([0-8]?)([.9]*?)\.?(.)$/,(m,n,c,r)=>r>4?-~n+c.replace(/9/g,0):n+c)

```

Explanation: The string is first normalised to contain a `.` and `n+1` decimal digits. The trailing digit, any preceding `9`s or `.`s, and any preceding digit, are then considered. If the last digit is less than 5 then it and any immediately preceding `.` are simply removed but if it is greater than 5 then the `9`s are changed to `0`s and the previous digit incremented (or 1 prefixed if there was no previous digit).

# Answer
> 1 votes
# Python 3 \+ SymPy, 54 bytes

```
from sympy import*
lambda s,p:'%.*f'%(p,S(s).round(p))

```

Try it online!

# Answer
> 1 votes
# J, ~~22~~ 17 bytes

```
((10 j.[)]@:":".)

NB.    2    ((10 j.[)]@:":".)   '12.45678'
NB.    12.46

```

Thanks to @Conor O'Brien for correcting my understanding of the rules.

```
t=:4 :'(10 j.x)":".y'

    NB.    Examples
    NB.    4 t'12.45678'
    NB.    12.4568
    NB.    4 t'12.456780'
    NB.    12.4568
    NB.    4 t'12.4567801'
    NB.    12.4568
    NB.    2 t'12.45678'
    NB.      12.46
    NB.    2 t'12.4567801'
    NB.      12.46
    NB.    2 (10 j.[)":". '_12.4567801'
    NB.     _12.46

format
    x t y
where x is a digit number of decimal places required and y
is the character string containing the value to be rounded.

```

# Answer
> 1 votes
# Scala, 44 bytes

```
(s:String,p:Int)=>s"%.${p}f"format s.toFloat

```

Test:

```
scala> var x = (s:String,p:Int)=>s"%.${p}f"format s.toFloat
x: (String, Int) => String = <function2>

scala> x("14.225",2)
res13: String = 14.23

```

# Answer
> 1 votes
# Wonder, 10 bytes

```
@@fix#1E#0

```

Usage:

```
@@fix#1E#0

```

Set decimal precision and add trailing zeros if necessary.

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


# Question
Title: Number of string permutations that are palindromes
Your input will be a string consisting of small english letters.

Your task is to determine the number of distinct permutations of the original string that are a palindrome.

The input string has up to 100 letters. In the case of a longer string the result might be very big so the output should be the number of permutations modulo 666013.

For example,

```
cababaa -> 3

```

The possible permutations are:

```
aabcbaa
abacaba
baacaab

```

This is , so the shortest answer wins!

# Answer
# Brachylog (2), 15 bytes

```
{p.↔}ᶠdl%₆₆₆₀₁₃

```

Try it online!

## Explanation

```
{p.↔}ᶠdl%₆₆₆₀₁₃
{   }ᶠdl          Count (l) the number of distinct (d) results (ᶠ) obtainable by:
 p                  permuting {the input}
  .                 to produce an output
   ↔                that, if reversed, is still the output
        %₆₆₆₀₁₃   then take that number modulo 666013

```
> 5 votes

# Answer
# 05AB1E, ~~17~~ ~~16~~ 13 bytes

*-1 byte from Jonathon Allan*

*-3 bytes from Emigna and Adnan*

```
œÙvyÂQO•E›j•%

```

Explanation:

```
œÙ                # Unique permutations of [implicit] input
  vy              # For each permutation...
    ÂQ            # Check if it is a palindrome
      O           # If so, increment the counter
       •E›j•%     # Modulo 666013 (no clue why this number, or even why this rule is in place)

```

Try it online!
> 5 votes

# Answer
# Perl 6, ~~104~~ ~~108~~ ~~88~~ 84 bytes

```
{my &f={[*] 1..$_ div 2}
.comb.Bag{*}.&{(2>.grep(*%2))*f(.sum)/[*]($_».&f)%666013}}

```

Try it online!

### How it works

I can't easily generate all permutations and filter them, even if astronomical run-times are allowed, because Perl 6's built-in `permutations` routine straight-out refuses to permute lists of more than 20 elements and the task description requires inputs of up to 100 characters.

So instead I use a direct formula based on the letter frequencies of the input:

1. ```
my &f={[*] 1..$_ div 2}
```

A helper function that halves a number and rounds it down to the nearest integer, and then takes the factorial of that.
2. ```
.comb.Bag{*}.&{    };
```

Tally up the letter frequencies in the input string, and make them the topic for the rest of the code. E.g. for input `abcdabcdddddd` this would be the list `(2, 2, 2, 7)`.
3. ```
(2>.grep(*%2))*
```

If there is more than one odd letter frequency, multiply the result by zero, because no palindromes are possible in that case.
4. ```
f(.sum)/[*]($_».&f)
```

Calculate the number of possible permutations of the characters that will be on "one side" of each palindrome *(which corresponds to a multiset with the multiplicities obtained by halving and flooring the input letter frequencies)*. The formula used is from this PDF:
**(n1+...+ nk)! / (n1!⋅...⋅nk1)**
E.g. for input letter frequencies `(2,2,2,7)`, the letters on *one* side of the palindrome form a multiset with multiplicities `(1,1,1,3)`, and the number of permutations is thus `(1+1+1+3)! / (1!⋅1!⋅1!⋅3!) = 120`.
5. ```
%666013
```

Take the result modulo 666013.
> 4 votes

# Answer
# Python3, ~~81~~ 80 bytes

```
from itertools import*
lambda s:sum(a==a[::-1]for a in{*permutations(s)})%666013

```

This is the shortest I could come up with. Not sure if the permutations can be generated more easily...

## Explanation

```
lambda s:                       # Anonymous function taking a parameter <s>.
    sum(                        # Sum the following terms.
        a==a[::-1]              # Check whether the permutation <a> is a palindrome,
        for a in                # for each element <a>,
        {                       # inside a set that can only contain distinct elements.
            *                   # Splat the elements of the following object:
            permutations(s)     # the permutations of the input parameter <s>.
        }                       #
    )%666013                    # Modulo the sum by 666013.

```

## Notes

1. The check `a==a[::-1]` returns a boolean value, but the `sum(...)` function implicitly casts it to an integer (0 or 1) and sums accordingly.
2. I have to use the 'splat operator' (not the real name), to extract the elements from the object `permutations(...)`. Otherwise the set (`{...}`) would contain only one element, the object itself.
3. I use a set (`{...}`) to keep only distinct permutations inside.

In Floroid, this is (almost) `z(T(a==aDKaIW(cb(L)))%666013)`, but prints the result instead, and takes input through the command line.

Thanks to @Jonathan Allan for saving a byte! --\> Changed the `import` style

Try it online!
> 3 votes

# Answer
# Jelly, 13 bytes

```
Œ!QŒḂ€S%“µɲ€’

```

**Try it online!**

### How?

A brute forcer.

```
Œ!QŒḂ€S%“µɲ€’ - Main link: string
Œ!            - all permutations
  Q           - unique
     €        - for each
   ŒḂ         - isPalindromic? (yep a built-in!)
      S       - sum
       %      - mod
        “µɲ€’ - base 250 compressed number 666013

```

---

I *believe* that **this** will do it more efficiently, but it's **30** bytes (edit: this pdf seems to confirm it, courtesy of smls's answer):

```
ÑHḞµS!÷!P$ - Link 1, palindrome count: string a    e.g. 'abcabcd'
Ñ          - call the next link (2) as a monad(a)  e.g. [2, 2, 2, 1]
 H         - halve                                 e.g. [1, 1, 1, 0.5]
  Ḟ        - floor (get pair counts)               e.g. [1, 1, 1, 0]
   µ       - start a new monadic chain - call that p
    S      - sum(p)                                e.g. 3
     !     - factorial                             e.g. 6
         $ - last 2 links as a monad:
       !   -     factorial(p) (vectorises)         e.g. [1, 1, 1, 1]
        P  -     product                           e.g. 1
      :    - integer division                      e.g. 6

ĠL€ - Link 2, count characters: string a           e.g. 'abcabcd'
Ġ   - group indexes                                e.g. [[1, 4], [2, 5], [3, 6], 7]
 L€ - length of €ach                               e.g. [2, 2, 2, 1]

ÇḂS⁼LḂ$aÑ%“µɲ€’ - Main link: string a              e.g. 'abcabcd'
                - first check to see if any palindromes will be possible:
Ç               - last link (2) as a monad         e.g. [2, 2, 2, 1]
 Ḃ              - mod 2                            e.g. [0, 0, 0, 1]
  S             - sum                              e.g. 1
      $         - last two links as a monad:
    L           -     length(a string)             e.g. 7
     Ḃ          -     mod 2                        e.g. 1
   ⁼            - equal?                           e.g. 1 (1 when palindromes are possible)
       a        - and
        Ñ       - next link as a monad             e.g. 6
         %“µɲ€’ - mod 666013, as in the brute force version.

```
> 3 votes

# Answer
## Mathematica, 46 bytes

```
Permutations@#~Count~_?PalindromeQ~Mod~666013&

```

Takes a list of characters as input.

Terribly inefficient, because it actually generates all permutations of the input and then counts the palindromic ones.
> 2 votes

# Answer
# Mathematica, 68 bytes

```
If[i=Floor[t=Last/@Tally@#/2];Tr[t-i]<1,Multinomial@@i,0]~Mod~666013

```

Pure function taking a list of characters as input and returning an integer. Not as short as Martin Ender's Mathematica answer, but it's a cute approach nonetheless, which seems to be the same approach as in smls's Perl 6 answer.

First, `t=Last/@Tally@#/2` computes the counts of all the distinct characters in the input, divided by `2`; then `i=Floor` rounds down any fractions occurring in `t`. Note that palindromic permutations of the input exist exactly when there is at most one odd number among the original counts, that is, when there is at most one fraction in `t`. We can test for that by simply adding up all the elements of `t-i` (using `Tr`): if the answer is less than `1`, there are palindromic permutations, otherwise not.

If there are, then `i` represents the counts of distinct characters in the left half of the permutations, which can be arranged arbitrarily. The number of ways to do that is exactly the `Multinomial` coefficient (a quotient of certain factorials), which Mathematica has built-in.
> 2 votes

# Answer
# k, 23 bytes

```
{666013!+/{x~|x}'cmb x}

```

If using oK, or `cmb` doesn't exist, use `prm` instead of `cmb`.
> 1 votes

# Answer
# Pyth - 15 bytes

```
%l{_I#.pQ666013

```

Try it online here.
> 1 votes

# Answer
# Ruby, 67 57 52 59 chars

```
->s{s.chars.permutation.uniq.count{|t|t.reverse==t}%666013}

```
> 1 votes

# Answer
# Japt, 20 18 bytes

```
á f_¥Zw} l %666013

```

Saved 2 bytes thanks to ETHproductions.

Try it online!
> 1 votes

# Answer
# C++14, 161 bytes

As unnamed lambda assuming input is like `std::string` and returning via reference parameter.

```
#import<algorithm>
[](auto s,int&n){auto a=s.begin(),b=s.end();std::sort(a,b);n=0;do n=(n+std::equal(a,b,s.rbegin()))%666013;while(std::next_permutation(a,b));}

```

Ungolfed and usage:

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

#import<algorithm>
auto f=
[](auto s,int&n){
 auto a=s.begin(),b=s.end();
 std::sort(a,b);
 n=0;
 do
  n=(n+std::equal(a,b,s.rbegin()))%666013;
 while(std::next_permutation(a,b));
}
;

using namespace std;

int main(){
 string s;
 s = "cababaa";
 s = "abcdabcddddd";
 int n;
 f(s,n);
 cout << n << endl;
}

```
> 1 votes

# Answer
# MATL, 13 bytes

```
Y@Xu!"@tP=Avs

```

Try it at **MATL Online**

**Explanation**

```
        % Implicitly grab input as a string
Y@      % Compute all permutations of the inputs (one per row)
Xu      % Determine the unique rows
!       % Take the transpose so each permutation is a column
"       % For each unique permutation
  @     % Take this permutation
  tP=A  % Duplicate it, reverse it, and compare (yields 1 for palindrome and 0 otherwise)
  v     % Vertically concatenate the entire stack
  s     % Compute the sum of all elements
        % Implicitly end for loop and display the result

```
> 0 votes

# Answer
# CJam, 19 bytes

```
qe!{_W%=}%:+666013%

```

Try it online!

Explanation:

```
qe!{_W%=}%:+666013% e# Full program.
q                   e# Get all input.
 e!                 e# Get all unique permutations.
   {_W%=}           e# Function to check if a list is a palindrome.
    _               e# Duplicate ToS.
     W%             e# Reverse ToS (Push -1, Modular index of ToS).
       =            e# Check if ToS is equal to SToS.
         %          e# Map.
          :+        e# Sum (Reduce by addition).
            666013  e# Push 666013.
                  % e# Modulo.
```
> 0 votes

# Answer
# Ohm, 17 bytes

```
I⌐:_₧?¡;;¼,

```

Explanation:

```
I⌐:_₧?¡;;¼,  ■Main wire
I⌐:     ;    ■for _ in permutations(input()){
   _₧? ;     ■  if(palindrome(_)){
      ¡      ■    counter++;
       ;     ■  }
        ;    ■}
         ¼,  ■print(counter)

```
> 0 votes

# Answer
# PHP, 182 Bytes

```
function f($a,$b=1){return$a?f($a-1,bcmul($a,$b)):$b;}$a=count_chars($argv[1],$r=1);foreach($a as$v){$c+=$v%2?:0;$c>1?die("0"):$z+=$f=$v/2^0;$r=bcmul(f($f),$r);}echo bcdiv(f($z),$r);

```

Online Version

## Breakdown

```
function f($a,$b=1){  #Factorial
    return$a?f($a-1,bcmul($a,$b)):$b;
}
$a=count_chars($argv[1],$r=1); # Array count for every char
foreach($a as$v){
    $c+=$v%2?:0; # counter mod 2 ==1
    $c>1?die("0"):$z+=$f=$v/2^0; # end program if there are 2 chars which cannot divide by 2
    $r=bcmul(f($f),$r);
}
echo bcdiv(f($z),$r);

```
> 0 votes

---
Tags: code-golf, string, combinatorics, permutations, palindrome
---


# Question
Title: Count how many distance sequences are far from all others
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Let `P` be a binary string of length `n` and `T` be a binary string of length `2n-1`. We can compute the `n` Hamming distances between `P` and every `n`-length substring of `T` in order from left to right and put them into an array (or list).

**Example Hamming distance sequence**

Let `P = 101` and `T = 01100`. The sequence of Hamming distances you get from this pair is `2,2,1`.

**Definition of closeness**

Now let's consider two such sequences of Hamming distances. Say `x = (0, 2, 2, 3, 0)` and `y = (2, 1, 4, 4, 2)` as examples. We say that `x` and `y` are `close` if `y <= x <= 2*y` or if `x <= y <= 2*x`. Here the scalar multiplication and inequality are taken elementwise. That is to say, for two sequences `A` and `B`, `A <= B iff A[i] <= B[i]` for all indices `i`.

Note that sequences of Hamming distances form a partial order under this way of comparing them. In other words, many pairs of sequences are neither greater than or equal nor less than or equal to each other. For example `(1,2)` and `(2,1)`.

So using the example above, `(0, 2, 2, 3, 0) <= 2*(2, 1, 4, 4, 2) = (4, 2, 8, 8, 4)` but `(0, 2, 2, 3, 0)` is not bigger than `(2, 1, 4, 4, 2)`. Also `(2, 1, 4, 4, 2)` is not smaller than or equal to `2*(0, 2, 2, 3, 0) = (0, 4, 4, 6, 0)`. As a result `x` and `y` are not close to each other.

**Task**

For increasing `n` starting at `n=1`, consider all possible pairs of binary strings `P` of length `n` and `T` of length `2n-1`. There are `2^(n+2n-1)` such pairs and hence that many sequences of Hamming distances. However many of those sequences will be identical . The task is to find the size of the largest set of Hamming distance sequences so that no two sequences are close to each other.

Your code should output one number per value of `n`.

**Score**

Your score is broadly speaking the highest `n` your code reaches on my machine in 5 minutes (but read on). The timing is for the total running time, not the time just for that `n`.

In order to give scores for non-optimal answers, because finding optimal answers is likely to be hard, we will need a slightly subtle scoring system. Your score is the highest value of `n` for which no one else has posted a higher correct answer for any size which is smaller than equal to this. For example, if you output `2, 4, 21` and someone else outputs `2, 5, 15` then you would only score `1` as someone else has a better answer for `n = 2`. If you output `2, 5, 21` then you would score `3` no matter what anyone else outputs because those answers are all optimal. Clearly if you have all optimum answers then you will get the score for the highest `n` you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

**Example answers and worked example**

(This answers are as yet unchecked. Independent verification would be gratefully received.)

Thanks to ETHproductions:

* n = 1 gives 2.
* n = 2 gives 5.
* n = 3 gives 21.

Let's look at `n = 2` in more detail. In this case the full list of Hamming distance sequences (represented by tuples here) is:

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

```

We can see that `(0,0)` is not close to any other tuple. In fact if we take `(0, 0)`, `(0, 1)`, `(1, 0)`, `(2, 1)`, `(1,2)` then none of those tuples are close to any of the others. This gives a score of `5` for `n = 2`.

For `n = 3` the full list of distinct Hamming distance sequences is:

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

```

Of those `48` sequences, we can pick out a set of size `21` so that no pair in that set are close to each other.

**Languages and libraries**

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

**My Machine** The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

**Leading answer**

* Score of **4** for 2, 5, 21, 83, 361 by Christian Sievers. **C++**
* Score of **5** for 2, 5, 21, 83, 372 by fəˈnɛtɪk. **Javascript**

# Answer
> 5 votes
## C++ using the igraph library

Thanks for a nice opportunity to learn a new library!

This program now computes `2, 5, 21, 83, 361` fast. You can control printing of the nodes with the `PRINTNODES` constant.

The graph used has extra edges between nodes corresponding to distance vectors where one is near (but not equal) to the other one reversed. That speeds up the computation, and any independent set found is of course also one of the original graph. Also, even if it is not completely enforced, the computed independent set is closed under reversion. I believe there always exists a maximal independent set with that property. At least there is one for `n<=4`. (I'm sure I can show 83 is optimal.)

```
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<igraph.h>

using vect = std::vector<int>;

constexpr int MAXDIRECT=100;
constexpr int PRINTNODES=1;

std::set<int> avoid{};
igraph_t graph;
std::vector<vect> distance_vectors{};
int count;

int close_h(const vect &a, const vect &b ){
  // check one direction of the closeness condition
  for(auto i=a.begin(), j=b.begin(); i!=a.end(); i++,j++)
    if ( (*i > *j) || (*j > 2 * *i))
      return 0;
  return 1;
}

int close(const vect &a, const vect &b ){
  return close_h(a,b) || close_h(b,a);
}

vect distances(int n, int p, int t){
  vect res{};
  for (int i=0; i<n; ++i){
    int count = 0;
    for (int j=0; j<n; ++j)
      count += 1 & ((p>>j)^(t>>j));
    res.push_back(count);
    t >>= 1;
  }
  return res;
}

void print_vect( vect &v ){
  std::cout << "(";
  auto i=v.begin();
  std::cout << *i++;
  for( ; i!=v.end(); ++i)
    std::cout << "," << *i ;
  std::cout << ")\n";
}

void use_node( int n ){
  if(PRINTNODES)
    print_vect( distance_vectors[n] );
  ++count;
  avoid.insert( n );
  igraph_vector_t neighs;
  igraph_vector_init( &neighs, 0 );
  igraph_neighbors( &graph , &neighs, n, IGRAPH_OUT );
  for(int i=0; i<igraph_vector_size( &neighs ); ++i)
    avoid.insert( VECTOR(neighs)[i] );
  igraph_vector_destroy( &neighs );
}

void construct(int n){
  std::set<vect> dist_vects;
  for(int p=0; p>>n == 0; ++p)
    for(int t=0; t>>(2*n-2) == 0; ++t)   // sic! (because 0/1-symmetry)
      dist_vects.insert(distances(n,p,t));
  int nodes = dist_vects.size();
  std::cout << "distinct distance vectors: " << nodes << "\n";

  distance_vectors.clear();
  distance_vectors.reserve(nodes);
  std::copy(dist_vects.begin(), dist_vects.end(),
            back_inserter(distance_vectors));

  igraph_vector_t edges;
  igraph_vector_init( &edges, 0 );
  igraph_vector_t reversed;
  igraph_vector_init_seq( &reversed, 0, nodes-1 );
  for (int i=0; i<nodes-1; ++i){
    vect &x = distance_vectors[i];
    vect xr ( x.rbegin(), x.rend() );
    for(int j=i+1; j<nodes; ++j){
      vect &y = distance_vectors[j];
      if( xr==y ){
        VECTOR(reversed)[i] = j;
        VECTOR(reversed)[j] = i;
      }else if( close( x, y ) || close( xr, y) ){
        igraph_vector_push_back(&edges,i);
        igraph_vector_push_back(&edges,j);
      }
    }
  }
  std::cout << "edges: " << igraph_vector_size(&edges)/2 << "\n";

  igraph_create( &graph, &edges, nodes, IGRAPH_UNDIRECTED);
  igraph_vector_destroy( &edges );

  igraph_cattribute_VAN_setv( &graph, "r", &reversed );
  igraph_vector_destroy( &reversed );

  igraph_vector_t names;
  igraph_vector_init_seq( &names, 0, nodes-1 );
  igraph_cattribute_VAN_setv( &graph, "n", &names );
  igraph_vector_destroy( &names );

}

void max_independent( igraph_t *g ){
  igraph_vector_ptr_t livs;
  igraph_vector_ptr_init( &livs , 0 );
  igraph_largest_independent_vertex_sets( g, &livs );

  igraph_vector_t *nodes = (igraph_vector_t *) VECTOR(livs)[0];
  igraph_vector_t names;
  igraph_vector_init( &names, 0 );
  igraph_cattribute_VANV( g, "n", igraph_vss_vector( nodes ), &names );

  for(int i=0; i<igraph_vector_size(&names); ++i)
    use_node( VECTOR(names)[i] );
  igraph_vector_destroy( &names );
  igraph_vector_ptr_destroy_all( &livs );
}

void independent_comp( igraph_t *g );

void independent( igraph_t *g ){
  if(igraph_vcount( g ) < MAXDIRECT){
    max_independent( g );
    return;
  }
  igraph_vector_ptr_t components;
  igraph_vector_ptr_init( &components, 0 );
  igraph_decompose( g, &components, IGRAPH_WEAK, -1, 1);
  for(int i=0; i<igraph_vector_ptr_size( &components ); ++i)
    independent_comp( (igraph_t *) VECTOR(components)[i] );
  igraph_decompose_destroy( &components );
}

void independent_comp( igraph_t *g ){
  if (igraph_vcount( g ) < MAXDIRECT){
    max_independent( g );
    return;
  }
  igraph_vector_t degs;
  igraph_vector_init( &degs, 0 );
  igraph_degree( g, &degs, igraph_vss_all(), IGRAPH_OUT, 1 );
  int maxpos = igraph_vector_which_max( &degs );
  igraph_vector_destroy( &degs );

  int name = igraph_cattribute_VAN( g, "n", maxpos );
  int revname = igraph_cattribute_VAN( g, "r", maxpos );
  int rev = -1;
  if(name!=revname){
    igraph_vector_ptr_t reversed_candidates_singleton;
    igraph_vector_ptr_init( &reversed_candidates_singleton, 0 );
    igraph_neighborhood( g, &reversed_candidates_singleton,
                         igraph_vss_1(maxpos), 2, IGRAPH_OUT );
    igraph_vector_t * reversed_candidates =
      (igraph_vector_t *) VECTOR(reversed_candidates_singleton)[0];
    igraph_vector_t names;
    igraph_vector_init( &names, 0 );
    igraph_cattribute_VANV( g, "n", igraph_vss_vector( reversed_candidates ),
                        &names );
    long int pos;
    igraph_vector_search( &names, 0, revname, &pos );
    rev = VECTOR(*reversed_candidates)[pos];
    igraph_vector_destroy( &names );
    igraph_vector_ptr_destroy( &reversed_candidates_singleton );
  }
  igraph_vs_t delnodes;
  igraph_vs_vector_small( &delnodes, maxpos, rev, -1 );
  igraph_delete_vertices( g, delnodes );
  igraph_vs_destroy( &delnodes );

  independent( g );
}

void handle(int n){
  std::cout << "n=" << n << "\n";
  avoid.clear();
  count = 0;
  construct( n );
  independent( &graph );
  // try all nodes again:
  for(int node=0; node<igraph_vcount( &graph ); ++node)
    if(avoid.count(node)==0)
      use_node(node);
  std::cout << "result: " << count << "\n\n";
  igraph_destroy( &graph );
}

int main(){
  igraph_i_set_attribute_table( &igraph_cattribute_table );
  for(int i=1; i<6; ++i)
    handle(i);
}

```

To compile on debian, install `libigraph0-dev` and do `g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph`.

Old description:

The igraph library has a function to compute the maximal size of an independent vertex set of a graph. It can handle this problem up to `n=3` in less than a second and does not terminate in days for `n=4`.

So what I do is decompose the graph into connected components, and let the library handle the small (less than `MAXDIRECT` nodes) components. For the other components, I select a vertex and delete it. In the best case, this splits the graph into several components, but usually it doesn't. Anyway, the components (maybe only one) are smaller, and we can use recursion.

Obviously the selection of the vertex is important. I just take one of maximal degree. I found that I get better result (but only for `n=4`) when I use a reversed node list. That explains the magic part of the `construct` function.

It might be worth while improving the selection. But it seems more important to reconsider the deleted nodes. Right now, I never look at them again. Some of them may be unconnected to any of the selected nodes. The problem is that I don't know which nodes form the independent set. For one, deleting nodes renumbers the remaining nodes. That can be handled by attaching attribtes to them. But worse, the computation of the independence number just gives this number. The best alternative the library offers is to compute *all* largest independent sets, which is slower (how much seems to depend on the graph size). Still, this seems the immediate way to go. Much more vaguely, I also think it might be useful to consider if we can use the special way the graph is defined.

The case `n=6` might become reachable (at all, not necessarily in 5 minutes) if I replace the recursion with a loop using a queue for the remaining components.

I found it interesting to look at the components of the graphs. For `n=4`, their sizes are `168, 2*29, 2*28, 3, 4*2, 4*1`. Only the biggest one can not be handled directly.

For `n=5`, the sizes are `1376, 2*128, 2*120, 119, several <=6`.

I expect those double sizes to correspond to isomorphic graphs, but using this doesn't seem worth while because there is always one single dominating biggest component:

For `n=6`, the biggest component contains `11941` nodes (from a total of `15425`), the next two biggest components have size `596`.

For `n=7`, these numbers are `107593 (125232), 2647`.

# Answer
> 3 votes
# Javascript, Seq: 2,5,21, ~~81~~ 83,372 ~~67,349~~

Managed to increase the value for 4 by using random removal of elements at the start of my search. Oddly enough, removing 20 elements with more than 6 connections was faster than removing 5 elements with more than 8 connections...

This sequence is probably not optimal for 5 and might not be optimal for 4. None of the nodes are close to another in the set though.

## Code:

```
input=4;
maxConnections=6;
numRand=20;

hammings=[];
h=(x,y)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal};
for(i=1<<(input-1);i<1<<input;i++){
  for(j=0;j<1<<(2*input);j++){
    hamming=[];
    for(k=0;k<input;k++){
      hamming.push(h((j>>k)%(1<<input),i));
    }
    equal=0;
    for(k=0;k<hammings.length;k++){
      if(hamming.join("")==hammings[k].join("")){
        equal=1;
        break;
      }
    }
    if(!equal)hammings.push(hamming);
  }
}
adjMat=[];
for(i=0;i<Math.pow(input+1,input);i++){
  row=[];
  for(j=0;j<Math.pow(input+1,input);j++){
    row.push(0);
  }
  adjMat.push(row);
}
nodes=[]
for(i=0;i<Math.pow(input+1,input);i++){
  nodes[i]=0;
}
for(i=0;i<hammings.length;i++){
  sum=0;
  chkNodes=[[]];
  for(j=0;j<input;j++){
    chkVal=[];
    t=Math.pow(input+1,j);
    sum+=t*hammings[i][j];
    tmp=[];
    for(r=0;r<chkNodes.length;r++){
      for(k=hammings[i][j];k<=Math.min(hammings[i][j]*2,input);k++){
        stor=[]
        for(s=0;s<chkNodes[r].length;s++){
          stor.push(chkNodes[r][s])
        }
        stor.push(k)
        tmp.push(stor);
      }
    }
    chkNodes=[];
    for(r=0;r<tmp.length;r++){
      chkNodes.push(tmp[r])
    }
  }
  nodes[sum]=1;
  for(j=0;j<chkNodes.length;j++){
    adjSum=0
    for(k=0;k<input;k++){
      adjSum+=Math.pow(input+1,k)*chkNodes[j][k]
    }
    if(adjSum!=sum)adjMat[sum][adjSum]=adjMat[adjSum][sum]=1
  }
}
t=nodes.length;
for(i=0;i<t;i++){
  if(!nodes[i]){
    for(k=0;k<t;k++){
      adjMat[i][k]=adjMat[k][i]=0
    }
  }
}
sum=(a,b)=>a+b;
console.log(nodes.reduce(sum))
connections=x=>x.reduce(sum)
counts=adjMat.map(connections);
stor=[];
for(i=0;i<t;i++){
  stor.push(nodes[i]);
}
maxRemainder=0;

greater=[]
for(i=0;i<t;i++){
  if(nodes[i]&&counts[i]>maxConnections){
    greater.push(i);
  }
}

if(input==4){
  for(w=0;w<greater.length*numRand;w++){
    for(i=0;i<t;i++){
      nodes[i]=stor[i];
    }
    counts=adjMat.map(connections);
    toRemove=Math.floor(Math.random()*numRand*2)
    for(i=0;i<toRemove&&i<greater.length;i++){
      rand=Math.floor(Math.random()*greater.length);
      if(nodes[greater[rand]]){
        nodes[greater[rand]]=0;
        for(j=0;j<t;j++){
          if(adjMat[rand][j]){
            counts[j]--;
          }
        }
      }
    }

    for(i=0;i<t*t;i++){
      max=0;
      maxLoc=0;
      for(j=0;j<t;j++){
        if(counts[j]>=max&&nodes[j]){
          max=counts[j];
          maxLoc=j;
        }
      }
      if(max>0){
        for(j=0;j<t;j++){
          if(adjMat[maxLoc][j]){
            counts[j]--;
            if(counts[j]<max-1&&stor[j]&&!nodes[j]){
              nodes[j]=1;
              for(k=0;k<t;k++){
                if(adjMat[j][k])counts[k]++;
              }
            }
          }
          nodes[maxLoc]=0;
        }
      }
      else{
        break;
      }
    }
    maxRemainder=Math.max(maxRemainder,nodes.reduce(sum))
    //console.log(nodes.reduce(sum));
  }
  console.log(maxRemainder);
}
else{
  for(i=0;i<t*t;i++){
    max=0;
    maxLoc=0;
    for(j=0;j<t;j++){
      if(counts[j]>=max&&nodes[j]){
        max=counts[j];
        maxLoc=j;
      }
    }
    if(max>0){
      for(j=0;j<t;j++){
        if(adjMat[maxLoc][j]){
          counts[j]--;
          if(counts[j]<max-1&&stor[j]&&!nodes[j]){
            nodes[j]=1;
            for(k=0;k<t;k++){
              if(adjMat[j][k])counts[k]++;
            }
          }
        }
        nodes[maxLoc]=0;
      }
    }
    else{
      break;
    }
  }
  console.log(nodes.reduce(sum));
}

```

Try it online!

**Snippet that can be added the end of the program to show what Hamming distance sequences each selected Hamming distance sequence**

```
for(i=0;i<t;i++){
  if(nodes[i]){
    tmp=[]
    for(j=0;j<input;j++){
      tmp.unshift(Math.floor(i/Math.pow(input+1,j))%(input+1))
    }
    console.log(tmp.join(""))
    output=""
    for(j=0;j<t;j++){
      if(adjMat[i][j]&&stor[j]){
        outArr=[]
        for(k=0;k<input;k++){
          outArr.unshift(Math.floor(j/Math.pow(input+1,k))%(input+1))
        }
        output+=" "+outArr.join("");
      }
    }
    console.log(output)
  }
}

```

## Explanation:

First, the code generates all unique hamming distances from the substrings.

```
input=3;
hammings=[];
h=(x,y)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal};
for(i=1<<(input-1);i<1<<input;i++){
  for(j=0;j<1<<(2*input);j++){
    hamming=[];
    for(k=0;k<input;k++){
      hamming.push(h((j>>k)%(1<<input),i));
    }
    equal=0;
    for(k=0;k<hammings.length;k++){
      if(hamming.join("")==hammings[k].join("")){
        equal=1;
        break;
      }
    }
    if(!equal)hammings.push(hamming);
  }
}

```

Next, the code converts this list into an undirected graph

```
adjMat=[];
for(i=0;i<Math.pow(input+1,input);i++){
  row=[];
  for(j=0;j<Math.pow(input+1,input);j++){
    row.push(0);
  }
  adjMat.push(row);
}
nodes=[]
for(i=0;i<Math.pow(input+1,input);i++){
  nodes[i]=0;
}
for(i=0;i<hammings.length;i++){
  sum=0;
  chkNodes=[[]];
  for(j=0;j<input;j++){
    chkVal=[];
    t=Math.pow(input+1,j);
    sum+=t*hammings[i][j];
    tmp=[];
    for(r=0;r<chkNodes.length;r++){
      for(k=hammings[i][j];k<=Math.min(hammings[i][j]*2,input);k++){
        stor=[]
        for(s=0;s<chkNodes[r].length;s++){
          stor.push(chkNodes[r][s])
        }
        stor.push(k)
        tmp.push(stor);
      }
    }
    chkNodes=[];
    for(r=0;r<tmp.length;r++){
      chkNodes.push(tmp[r])
    }
  }
  nodes[sum]=1;
  for(j=0;j<chkNodes.length;j++){
    adjSum=0
    for(k=0;k<input;k++){
      adjSum+=Math.pow(input+1,k)*chkNodes[j][k]
    }
    if(adjSum!=sum)adjMat[sum][adjSum]=adjMat[adjSum][sum]=1
  }
}

```

Finally, the code cycles through this graph, removing the vertex with the most connections each cycle before restoring any nodes that would now have less connections than the current maximum. When it has finished with this cycle it outputs the number of remaining nodes

```
t=nodes.length;
for(i=0;i<t;i++){
  if(!nodes[i]){
    for(k=0;k<t;k++){
      adjMat[i][k]=adjMat[k][i]=0
    }
  }
}
sum=(a,b)=>a+b;
counts=adjMat.map(x=>x.reduce(sum));
stor=[];
for(i=0;i<t;i++){
  stor.push(nodes[i]);
}
for(i=0;i<t*t;i++){
  max=0;
  maxLoc=0;
  for(j=0;j<t;j++){
    if(counts[j]>=max&&nodes[j]){
      max=counts[j];
      maxLoc=j;
    }
  }
  if(max>0){
    for(j=0;j<t;j++){
      if(adjMat[maxLoc][j]){
        counts[j]--;
        if(counts[j]<max-1&&stor[j]&&!nodes[j]){
          nodes[j]=1;
          for(k=0;k<t;k++){
            if(adjMat[j][k])counts[k]++;
          }
        }
      }
      nodes[maxLoc]=0;
    }
  }
  else{
    break;
  }
}
console.log(nodes.reduce(sum));

```

## Sets:

1:

```
0 1

```

2:

```
00 01 10 12 21

```

3:

```
000 001 011 013 030 031 100 101 110 111 123 130 132 203 213 231 302 310 312
321 333

```

4:

```
0000 0001 0011 0111 0124 0133 0223 0230 0232 0241 0313 0320 0322 0331 0403
0412 1000 1001 1013 1021 1100 1102 1110 1111 1134 1201 1224 1233 1243 1304
1314 1323 1330 1332 1342 1403 1413 1420 1422 2011 2033 2124 2133 2140 2142
2214 2230 2241 2303 2313 2320 2331 2411 3023 3032 3040 3041 3101 3114 3123
3130 3132 3141 3203 3213 3220 3231 3302 3310 3312 3321 3334 3343 3433 4031
4113 4122 4131 4210 4212 4221 4311 4333

```

5:

```
00000 00001 00011 00111 00123 01112 01235 01244 01324 01343 02111 02230
02234 02333 02342 02432 02441 02522 02530 02531 03134 03142 03220 03224
03233 03241 03314 03323 03331 03403 03412 03421 03520 04133 04141 04214
04223 04232 04303 04313 04322 05042 05050 05051 05132 10000 10001 10011
10122 10212 10221 10245 11000 11001 11013 11022 11100 11112 11120 11121
11202 11211 11345 11353 11443 12012 12111 12201 12245 12253 12335 12344
12352 12425 12430 12434 12442 12513 12532 13033 13042 13244 13252 13325
13330 13334 13342 13404 13424 13433 13441 13520 13522 13531 14032 14051
14140 14152 14225 14230 14234 14241 14243 14304 14315 14324 14332 14413
14420 14422 14431 15041 15050 15125 15133 15142 15215 15223 15232 20112
20135 20211 20253 20334 20352 21012 21021 21102 21110 21111 21201 21245
21344 21352 21430 21433 21442 21514 21523 22011 22101 22135 22244 22252
22325 22334 22340 22343 22405 22415 22424 22441 22520 22522 22531 23041
23144 23150 23152 23225 23234 23240 23243 23251 23304 23315 23324 23333
23341 23403 23413 23420 23432 23521 24031 24050 24125 24130 24134 24142
24151 24215 24224 24233 24303 24314 24320 24323 24331 24412 24421 25123
25132 25141 25203 25214 25222 25231 25302 25312 25321 30234 30243 30252
30324 30333 30340 30342 30414 30423 30430 30432 31011 31235 31244 31253
31325 31334 31340 31343 31405 31415 31424 31432 31441 31504 31521 32025
32034 32100 32144 32152 32225 32234 32240 32243 32251 32304 32315 32324
32330 32333 32342 32403 32414 32423 32512 33024 33031 33033 33125 33134
33140 33143 33151 33215 33224 33230 33233 33242 33303 33314 33320 33323
33332 33412 33431 34124 34133 34203 34214 34223 34232 34241 34310 34313
34322 34411 35202 35213 35221 35311 40323 40332 40341 40431 40505 40513
41135 41144 41240 41243 41252 41324 41330 41333 41342 41403 41414 41423
41512 42033 42134 42143 42230 42233 42242 42303 42310 42314 42323 42332
42341 42413 42422 42431 43023 43124 43130 43133 43142 43203 43220 43223
43232 43241 43302 43313 43322 43331 43421 44114 44123 44132 44210 44213
44222 44231 44312 44321 50413 50422 50504 51233 51242 51251 51323 51332
51341 51413 51422 52023 52133 52142 52151 52223 52232 52241 52313 52322
52331 52421 53102 53114 53122 53210 53213 53321 54201 54212 54221 54311

```

---
Tags: sequence, combinatorics, fastest-code, binary, optimization
---