title: Center The Text!

text:
# Question
Title: Center The Text!
# Center The Text!

In this challenge you will be centering various lines.

## Examples

```
Foo
barbaz

 Foo
barbaz

```

```
Hello
World

Hello
World

```

```
Programming Puzzles
&
Code Golf

Programming Puzzles
         &
     Code Golf

```

## Specifications

Each input line will always have at least one non-whitespace character, you may assume the only whitespace character are spaces () and newlines. Each input line won't have any trailing and/or leading whitespace (except for the newline). Trailing whitespace in the output is *not* allowed.

You should be centering among the longest line in the input. If that line is even in length, your program/function should prefer to center to the left. The maximum line length is whatever your language can handle but your program should function on lines of at least 500 in length.

---

## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=66731,OVERRIDE_USER=8478;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

---

This is so shortest code in bytes wins!

# Answer
> 15 votes
# Pyth, ~~19~~ 17 bytes

*2 bytes thanks to Jakube*

```
V.ztr+1.[l.T.zNd6

```

Demonstration

I think this is the first time the center-pad function of `.[` has been useful. The length of the longest line is found using non-truncating transpose (`.T`).

Trailing spaces are removed by adding a non-space character to the front, stripping spaces, then removing the added character.

# Answer
> 31 votes
## vim, ~~43~~ ~~36~~ 35 bytes

```
VGrx:sor
G:let &tw=col("$")
uu:%ce

```

Too good not to post. Note the trailing newline; it is significant.

Thanks to @Marth for saving a character!

vim-friendly format:

```
VGrx:sor<cr>G:let &tw=col("$")<cr>uu:%ce<cr>

```

Explanation:

```
VGrx                   replace every character with an "x"
:sor<cr>               sort (since all chars are now same, sorts by line length)
G                      go to the very last line
:let &tw=col("$")<cr>  set &tw to column number of last char on this line
                         "let &tw" is equivalent to "set tw"
                         tw is short for textwidth, used in :center
uu                     undo the sort, and the replacing-with-x too
:%ce<cr>               center over entire file (%), using textwidth set earlier

```

# Answer
> 23 votes
## Mathematica, 96 bytes

```
StringRiffle[#~StringPadLeft~Floor[Max@(l=StringLength)@a/2+l@#/2]&/@(a=#~StringSplit~"
"),"
"]&

```

Don't ask me how it worked, I just fiddled with it until it produced the correct output.

# Answer
> 11 votes
# Funciton, non-competitive

This challenge has highlighted the sore lack of a “maximum value” (and minimum value) function for lazy sequences, so... I added them to the core library (they’re called ⊤ and ⊥, respectively). Therefore I didn’t bother to submit this as a *golfed* answer (it would have to include the ⊤ function declaration to be valid), so here’s just the main program.

Execute `(function(){$('pre,code').css({lineHeight:5/4,fontFamily:'DejaVu Sans Mono'});})()` in your browser console to get some nicer rendering.

```
   ╓───╖         ╔════╗  ┌───╖  ╔═══╗
 ┌─╢ ‡ ╟─┐       ║ 10 ╟──┤ ǁ ╟──╢   ║
 │ ╙───╜ │       ╚════╝  ╘═╤═╝  ╚═══╝
 │ ┌───╖ │  ┌──────────────┴──────────────────┐
 └─┤ ‼ ╟─┘┌─┴─╖ ┌───╖ ┌───╖ ┌───╖ ┌───╖       │     │
   ╘═╤═╝  │ ɱ ╟─┤ ⊤ ╟─┤ + ╟─┤ ~ ╟─┤ ℓ ╟───┐ ┌─┴─╖ ┌─┴─╖ ╔════╗
     │    ╘═╤═╝ ╘═══╝ ╘═╤═╝ ╘═══╝ ╘═══╝   │ │ ɱ ╟─┤ ʝ ╟─╢ 10 ║
    ┌───╖ ╔═╧═╕ ╔═══╗ ┌─┴──╖ ┌───╖ ╔════╗ │ ╘═╤═╝ ╘═══╝ ╚════╝
  ┌─┤ ℓ ╟─╢   ├─╢ 1 ║ │ >> ╟─┤ … ╟─╢ 32 ║ │   │
  │ ╘═══╝ ╚═╤═╛ ╚═╤═╝ ╘═╤══╝ ╘═╤═╝ ╚════╝ │ ╔═╧═╕ ╔═══╗
  └─────────┘     └─────┘      │   ┌───╖  ├─╢   ├─╢ 0 ║
                               └───┤ ‡ ╟──┘ ╚═╤═╛ ╚═══╝
                                   ╘═╤═╝      │
                                     └────────┘

```

## Explanation

I believe this may be the first Funciton answer on this site that uses lambda expressions.

* First, we use `ǁ` to split the input string at the newlines (ASCII 10). This returns a lazy sequence.
* We pass that sequence through `ɱ` (map), giving it a lambda that calculates the length of each string, and then pass the final sequence through  to get the length of the longest line.
* We *also* pass that sequence through another `ɱ`, giving it a lambda that calculates the length of each string, subtracts it from the maximum line length calculated earlier, divides that by 2 (actually shift-right 1), generates that many spaces (ASCII 32) and then concatenates the string onto those spaces. (For geometric reasons, I declared a  function that calls  (string concatenate) with the parameters reversed.)
* Finally, we use `ʝ` to put all of the strings back together, using newlines (ASCII 10) as the separator.

# Answer
> 9 votes
## Retina, ~~54~~ 52 bytes

```
+m`^(.)+$(?<=(?=[^\t]*^..(?<-1>.)+(?(1)^))[^\t]*)
 $0

```

The `\t`s can replaced with actual tabs, but I've used `\t` here, because otherwise SE will convert the tabs to spaces. Note that there is a leading space on the second line.

Try it online.

### Explanation

The basic idea is to match a line which is at least two characters shorter than the longest line (or technically, two characters shorter than *any* other line), and surround it in two spaces. This is repeated until we can no longer find such a line, which means that all lines are within one character of the maximum length (where the one character is to account for parity mismatches, and guarantees that these lines are shifted to the left off-centre).

As for the actual regex:

```
^(.)+$

```

Just matches any one line while pushing one capture onto group `1` for each character.

```
(?<=...[^\t]*)

```

Is a lookbehind which is matched right-to-left and moves the cursor to the beginning of the string, so that the lookahead inside can check the entire string. Note that due to a lack of an anchor, the lookahead could be applied from anywhere else, but that does not create additional matches. We know that `[^\t]` will always match *any* character in the string, because the input is guaranteed to contain only spaces and linefeeds as far as whitespace is concerned.

```
(?=[^\t]*^..(?<-1>.)+(?(1)^))

```

This lookahead tries to find a line which is at least two characters longer than the one we're currently matching. `[^\t]*` moves through the string in order to be able to match any line. `^` ensures that we're starting from the beginning of the line. `..` then matches the two additional characters we require for the longer line. Now `(?<-1>.)+` matches individual characters in that line while popping from group `1` (note that `.` cannot match a linefeed, so this is constrained to one line). Finally, `(?(1)^)` asserts that we managed to empty the entire group `1`. If the line is shorter than required, this is not possible, because there are not enough characters in the line to pop from group 1 often enough to empty it.

# Answer
> 7 votes
# CJam, ~~26~~ ~~23~~ 19 bytes

```
qN/_z,f{1$,m2/S*\N}

```

My first time using CJam! Four bytes saved thanks to Martin Büttner. Try it online.

### Explanation

```
qN/    e# Read input and split each line
_z,    e# Transpose a copy and get its length to find the longest line
f{     e# For each line...
  1$,- e# Subtract its length from the longest length
  2/   e# Divide by two to get just the spaces to add to the left
  S*\  e# Add a string with that many spaces to the beginning
  N    e# Add a newline to go on to the next line
}

```

# Answer
> 7 votes
# Jolf, 3 bytes

*Noncompeting, update postdates question.*

Try it here!.

```
pci
pc  center
  i  string input

```

¯\\\_(ツ)\_/¯ I thought it'd be a useful function.

# Answer
> 7 votes
# JavaScript (ES6), ~~93~~ 91 bytes

```
s=>(m=l=s.split`
`).map(x=>(v=x.length/2)<m?v:m=v).map((x,i)=>" ".repeat(m-x)+l[i]).join`
`

```

*2 bytes saved thanks to @edc65!*

## Explanation

```
s=>(
  m=                // m = max line length (divided by 2)
    l=s.split`
`)                  // l = array of lines
.map(x=>            // for each line
  (v=x.length/2)    // v = current line length / 2
    <m?v:m=v        // set m to the max line length and return v
)
.map((x,i)=>        // for each line length / 2
  " ".repeat(m-x)   // add spaces before
    +l[i]           // add line text
)
.join`
`                   // return lines as a newline-separated string

```

## Test

```
var solution = s=>(m=l=s.split`
`).map(x=>(v=x.length/2)<m?v:m=v).map((x,i)=>" ".repeat(m-x)+l[i]).join`
`
```

```
<textarea id="input" rows="4" cols="20">Programming Puzzles
&
Code Golf</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 6 votes
# Python 2, ~~83~~ 81 bytes

```
def f(s):
 t=s.split('\n')
 for y in t:print(max(len(f)for f in t)-len(y))/2*' '+y

```

Thanks to @xnor for saving 2 chars

example input:

```
f("""Programming Puzzles
&
Code Golf""")

```

example output:

```
Programming Puzzles
         &
     Code Golf

```

And ending in second place with 84 bytes using str.center() and str.rstrip (thanks @J F).

```
def f(s):
 t=s.split('\n')
 for y in t:print y.center(max(len(f)for f in t)).rstrip()

```

# Answer
> 6 votes
# LabVIEW, 3 or 35 LabVIEW Primitives

Finds lines until none are left, then calculates how many spaces to add and puts everything together.

Alternatively you could use the built-in center alignment on string indicators, it kinda does feel like cheating though.

# Answer
> 5 votes
# TeaScript, 24 bytes

```
£p.R((aßln)¯-ln)/2)+l,§)

```

Loops through lines, adds `floor((max line length - line length) / 2)` spaces to the beginning.

## Ungolfed

```
£   p.R((aß  ln)¯  -ln)/2)+l,§   )
xl(#p.R((am(#ln)X()-ln)/2)+l,`\n`)

xl(#    // Loops through newlines
    p.R(   // Repeats spaces
      (
       am(#ln)    // Map all line lengths
              X() // Get largest line length
       -ln)       // Subtract current line length
      /2)  // Divide by two
      +l,  // Add current line text
`\n`)

```

Try it online

# Answer
> 5 votes
# PowerShell, 58 67 bytes

down to 58 bytes thanks to @mazzy's comments:

```
param($a)$a|%{$_|% *ft(($a|% le*|sort)[-1]/2+$_.length/2)}

# It takes an array of strings as input
PS C:\Temp> .\center.ps1 'aaa','bb','c'
aaa
bb
 c

# Or here, read from a file
PS C:\Temp> .\center.ps1 (gc t.txt)
info0:info1:info2:info3
      info0:info1
          ttt
          tt
           t

```
* It takes an array of strings as `$a`, loops over each string with `|%{...}`.
* calls the `string.padleft()` method on each string, via `% -member` shortcut, which takes desired final line length as a parameter.
    + we need `array_longest_line_length/2 + current_line_length/2`
    + the end part is `current_line_length/2` -\> `$_.length/2`
    + the other part is recalculating the array's maximum line length every time through the loop, and it does so with a nested loop making an array of line lengths, sorts that, then takes the last one.

# Answer
> 3 votes
# Emacs Lisp, 203 bytes

```
(let((f 0)(l 0))(dolist(s(split-string(buffer-string)"\n"))(set'l(string-width s))(when(> l f)(set'f l)))(let((fill-column f))(goto-char(point-min))(while(<(point)(point-max))(center-line)(next-line)))))

```

Ungolfed:

```
(let ((f 0) (l 0))
  (dolist (s (split-string(buffer-string) "\n"))
    (set 'l (string-width s))
    (when (> l f)
      (set 'f l)))
    (let ((fill-column f))
      (goto-char (point-min))
      (while (< (point) (point-max))
        (center-line)
        (next-line)))))

```

Centered:

```
               (let ((f 0) (l 0))
 (dolist (s (split-string(buffer-string) "\n"))
           (set 'l (string-width s))
                 (when (> l f)
                  (set 'f l)))
             (let ((fill-column f))
            (goto-char (point-min))
         (while (< (point) (point-max))
                 (center-line)
                (next-line)))))

```

# Answer
> 3 votes
# Ruby, ~~76~~ ~~68~~ 61 bytes

```
->t{(s=t.split$/).map{|l|l.center(s.map(&:size).max).rstrip}}

```

Sample run:

```
2.1.5 :001 > puts ->t{(s=t.split$/).map{|l|l.center(s.map(&:size).max).rstrip}}["Programming Puzzles\n&\nCode Golf"]
Programming Puzzles
         &
     Code Golf

```

# Answer
> 3 votes
## HTML, 40 bytes

```
<xmp style=float:left;text-align:center>

```

```
<xmp style=float:left;text-align:center>
Programming Puzzles
&
Code Golf
</xmp>
```

Snippet includes `</xmp>` tag because the code snippet viewer wants my tags to be balanced.

# Answer
> 2 votes
# MATL, 22 ~~31~~ bytes

```
`jtYz~]xXhc4X4H$ZuZ{Zv

```

Each line is input with a trailing line (that is, an `enter` keystroke). An empty line (two `enter` keystrokes) marks the end of input.

### Example

```
>> matl `jtYz~]xXhc4X4H$ZuZ{Zv
> foo
> barbaz
>
 foo
barbaz

```

### Explanation

```
`          % do...
  j        % input one string
  tYz~     % is it not empty?
]          % ...while
x          % delete last input (empty string)
Xh         % concatenate all inputs into a cell array
c          % convert to char (2D array). This fills with spaces to the right
4X4H$Zu    % center justify
Z{         % convert to cell array of strings
Zv         % remove trailing blanks of each string

```

# Answer
> 2 votes
# Haskell, ~~111~~ ~~81~~ 77 bytes

```
l=length
f s|q<-lines s=unlines[([1..div(maximum(l<$>q)-l w)2]>>" ")++w|w<-q]

```

Input to the f function, the output is not printed.

Usage: load in interpreter `ghci center.hs` and then if you want to print the output of f on a given string `putStr$f"Programming Puzzles\n&\nCode Golf"`

Edit: Thanks to nimi for 34 bytes, great job! :D

# Answer
> 2 votes
# R, 126 bytes

### code

```
for(z in 1){l=scan(,"");m=sapply(l,nchar);t=max(m[m==max(m)]);for(i in 1:length(m))cat(rep(" ",(t-m[i])/2),l[i],"\n", sep="")}

```

### ungolfed

```
for(z in 1){                          # any way to get rid of this?
  l=scan(,"")
  m <- sapply(l,nchar)
  t <- max(m[m==max(m)])
  for(i in 1:length(m)){
    cat(rep(" ",(t-m[i])/2),l[i],"\n", sep="")
  }
}

```

Probably there are waay better ways to do this, still working on it.

# Answer
> 1 votes
# Gema, 160 bytes

```
\L<T>=@push{i;$0}@set{m;@cmpn{@length{$0};${m;};$m;$m;@length{$0}}}
?=
\Z=@repeat{@sub{@line;1};@set{o;@right{@div{@add{$m;@length{$i}};2};$i}\n${o;}}@pop{i}}$o

```

Written mostly for my curiosity to see what can be done in a language without proper array structure and proper loop instruction.

Sample run:

```
bash-4.3$ gema '\L<T>=@push{i;$0}@set{m;@cmpn{@length{$0};${m;};$m;$m;@length{$0}}};?=;\Z=@repeat{@sub{@line;1};@set{o;@right{@div{@add{$m;@length{$i}};2};$i}\n${o;}}@pop{i}}$o' <<< $'Programming Puzzles\n&\nCode Golf'
Programming Puzzles
         &
     Code Golf

```

# Answer
> 1 votes
# Perl 6, 61 bytes

```
$/=(my@l=lines)».chars.max;for @l {put ' 'x($/-.chars)/2~$_} # 61 bytes

```

usage:

```
$ perl6 -e '$/=(my@l=lines)».chars.max;for @l {put " "x($/-.chars)/2~$_}' <<< \
'Programming Puzzles
&
Code Golf'

```

```
Programming Puzzles
         &
     Code Golf

```

# Answer
> 1 votes
# Japt, ~~28~~ 25

```
¡V=VwXl}R;¡Sp½*(V-Xl¹+X}R

```

Try it online!

### How it works

```
¡     V=VwXl}R;¡     Sp½*(V-Xl¹ +X}R
UmXYZ{V=VwXl}R;UmXYZ{Sp½*(V-Xl) +X}R

           // Implicit: U = input string, V = 0
UmXYZ{  }  // Map each item X in U through this function,
         R // splitting U at newlines beforehand:
  V=VwXl   //  Set V to max(X, Y.length).
           // V is now set to the length of the longest line.

UmXYZ{  }  // Map each item X in U with this function,
         R // again splitting U at newlines beforehand:
 ½*(V-Xl)  //  Take V minus X.length, and multiply by 1/2.
Sp         //  Repeat a space that many times.
        +X //  Concatenate X to the end.

```

# Answer
> 1 votes
# 05AB1E, 2 bytes

```
.c

```

Builtins ftw ¯\\\_(ツ)\_/¯

Try it online or verify all test cases.

**Explanation:**

```
.c   # Centralize the (implicit) multi-line input-string with preference to the left
     # (output the result implicitly)

```

(Preference to the right would be with a capital `.C` instead: see the differences.)

# Answer
> 0 votes
# PHP, 98 bytes

```
function($s){foreach($a=explode("
",$s)as$l)echo str_pad($l,max(array_map(strlen,$a)),' ',2),"
";}

```

Try it online!

Ungolfed:

```
function str_center( $s ) {
    $a = explode( PHP_EOL, $s );
    $m = max( array_map( 'strlen', $a ) );
    foreach( $a as $l ) {
        echo str_pad( $l, $m, ' ', STR_PAD_BOTH ), PHP_EOL;
    }
}

```

Output:

```
Programming Puzzles
         &
     Code Golf

```

# Answer
> 0 votes
# Japt, 1 byte

```
û

```

Try it or run all test cases

# Answer
> 0 votes
# APL (Dyalog Extended), 25 bytes

```
{↑(-⌊((⌈/≢¨⍵)+≢¨⍵)÷2)↑¨⍵}

```

There's an APLcart snippet for centering in a field:

`Is(⊢↑⍨∘-∘⌊2÷⍨+∘≢)Dv`

This answer is partly based on it.

Try it online!

## Explanation

```
{↑(-⌊((⌈/≢¨⍵)+≢¨⍵)÷2)↑¨⍵}
      (⌈/≢¨⍵)             Maximum of lengths of each line
             +≢¨⍵         Plus length of each line
     (           )÷2      divided by two
   -⌊(           )        Floor it, and take negative
  (                 )↑¨⍵  Take that much from each line
                          (taking a negative value prepends spaces)
 ↑                        Mix the final array to print on each line
{                       } dfn

```

# Answer
> 0 votes
## Pascal, 404 bytes

This complete `program` is suitable for any processor complying with ISO standards 7185 (“Standard Pascal”) or 10206 (“Extended Pascal”). The `maximumLineLength` algorithm requires that every line has a maximum length of `maxInt` characters.

```
program p(input,output);type Z=integer;var b:text;l:file of Z;c,m:Z;begin
m:=0;c:=0;rewrite(b);rewrite(l);while not EOF do begin if EOLn then begin
write(l,c);c:=0;writeLn(b)end else begin c:=c+1;if c>m then
m:=c;write(b,input^)end;get(input)end;reset(b);reset(l);while not EOF(b)do
begin read(l,c);for c:=1 to(m-c)div 2 do write(' ');while not EOLn(b)do
begin write(b^);get(b)end;writeLn;get(b)end end.

```

Ungolfed:

```
program centerTheText(input, output);
    type
        integerNonNegative = 0‥maxInt;

    var
        { The behavior of `reset(input)` is implementation-defined.
          Using a buffer `text` file avoids relying on specific behavior. }
        buffer: text;
        { Stores the length of a line in `input` (buffered in `buffer`). }
        lineLength: file of integerNonNegative;
        { The length of the currently processed line. }
        currentLineLength: integerNonNegative;
        { The length of the longest line found. }
        maximumLineLength: integerNonNegative;

    begin
        maximumLineLength ≔ 0;
        currentLineLength ≔ 0;
        { Open files for writing and set their lengths to zero (“truncate”). }
        rewrite(buffer);
        rewrite(lineLength);

        { process and analyze `input` ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ }
        while not EOF(input) do
        begin
            { Invocation of `EOLn(input)` is only valid if `not EOF(input)`. }
            if EOLn(input) then
            begin
                { `input↑` contains a space so we cannot just copy it. }
                writeLn(buffer);
                { Store the determined line length for the centering. }
                write(lineLength, currentLineLength);
                { Prepare `currentLineLength` for the next line. }
                currentLineLength ≔ 0;
            end
            else
            begin
                currentLineLength ≔ currentLineLength + 1;
                { In Extended Pascal you could write: `maximumLineLength ≔
                  card([0‥currentLineLength, 0‥maximumLineLength]) − 1`. }
                if currentLineLength > maximumLineLength then
                begin
                    maximumLineLength ≔ currentLineLength;
                end;
                { For later reference store `input↑` in `buffer`. }
                write(buffer, input↑);
            end;
            { Advance reading cursor. }
            get(input);
        end;

        { Open files for reading from the start. }
        reset(buffer);
        reset(lineLength);

        { Reproduce `input` but centered. ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ }
        while not EOF(buffer) do
        begin
            read(lineLength, currentLineLength);
            { In Extended Pascal you could also just write:
              `write('':(maximumLineLength − currentLineLength) div 2)` }
            for currentLineLength ≔ 1 to
                (maximumLineLength − currentLineLength) div 2 do
            begin
                write(output, ' ');
            end;
            { Do not enter loop in case of an empty line. }
            while not EOLn(buffer) do
            begin
                write(output, buffer↑);
                get(buffer);
            end;
            { Discard the end-of-line marker character. }
            get(buffer);
            { Emit the implementation-specific end-of-line marker character. }
            writeLn(output);
        end;
    end.

```

## Extended Pascal, 252 bytes

Requiring a processor compliant with ISO standard 10206 “Extended Pascal” the schema data type `string` becomes available. Lots of operations can be thus abbreviated:

```
program p(input,output);var b:text;l:string(maxInt);m:integer;begin
m:=0;rewrite(b);while not EOF do begin readLn(l);if m<length(l)then
m:=length(l);writeLn(b,l)end;reset(b);while not EOF(b)do begin
readLn(b,l);writeLn('':(m-length(l))div 2,l)end end.

```

Ungolfed:

```
program centerTheText(input, output);
    type
        { `integer…` prefix to facilitate sorting in documentation tools. }
        integerNonNegative = 0‥maxInt;

    var
        buffer: text;
        line: string(maxInt);
        maximumLineLength: integerNonNegative value 0;

    begin
        { The size of `buffer` immediately becomes zero. }
        rewrite(buffer);
        { Find the length of the longest line in `input`. }
        while not EOF(input) do
        begin
            readLn(input, line);
            { Is the current line longer than the longest line so far? }
            if length(line) > maximumLineLength then
            begin
                maximumLineLength ≔ length(line);
            end;
            { Store the read `input` line in `buffer` for later retrieval. }
            writeLn(buffer, line);
        end;

        { (Re‑)open `buffer` and start reading `buffer` from the start. }
        reset(buffer);
        { The `while` loop is not entered in case `buffer` is an empty file. }
        while not EOF(buffer) do
        begin
            readLn(buffer, line);
            { Empty strings (`''`) are only allowed in Extended Pascal.
              For `string` values the `integer` expression after the colon
              dictates the _exact_ width of the string padded with spaces. }
            writeLn('':(maximumLineLength − length(line)) div 2, line);
        end;
    end.

```

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


# Question
Title: Determine if an integer is divisible by 3
Your goal is to determine if a number is divisible by 3 without using conditionals. The input will be an unsigned 8 bit number from 0 to 255. Creativity encouraged!

You are ONLY allowed to use

* Equality/Inequality (`==`, `!=`, `>`, `<`, `>=`, `<=`)
* Arithmetic (`+`, `-`, `x`)
* Logical Operators (`!` not, `&&` and, `||` or)
* Bitwise Operators (`~` not, `&` and, `|` or, `^` xor, `<<`, `>>`, `>>>` arithmetic and logical left and right shifts)
* Constants (it would be better if you kept these small)
* Variable assignment

Output `0` if false, `1` if true.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. Example methods here. A token is any of the above excluding constants and variables.

# Answer
# C - 2 tokens

```
int div3(int x) {
    return x * 0xAAAAAAAB <= x;
}

```

Seems to work up to 231-1.

Credits to `zalgo("nhahtdh")` for the multiplicative inverse idea.
> 31 votes

# Answer
# Python, 3 2 tokens

Brute force solution, but it works.

```
0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

```

Thanks to Howard for the 1 token reduction.
> 17 votes

# Answer
## C - ~~5~~ 4 (?) tokens

```
int div3_m2(uint32_t n) {
    return n == 3 * (n * 0xAAAAAAABull >> 33);
}

```

Works for **any unsigned 32-bit number**.

This code makes use of multiplicative inverse modulo 232 of a divisor to convert division operation into multiplication operation.

**Edit**

My solution (posted 2 minutes after) has the same spirit as aditsu's solution. Credit to him for the use of `==` that improves my solution by 1 token.

### Reference
> 7 votes

# Answer
# C - 15 (?) tokens

```
int div3_m1(unsigned int n) {
    n = (n & 0xf) + (n >> 4);
    n = (n & 0x3) + (n >> 2);
    n = (n & 0x3) + (n >> 2);
    return n == 0 || n == 3;
}

```

Since 4 ≡ 1 (mod 3), we have 4n ≡ 1 (mod 3). The digit summing rule is not limited to summing the digits, but also allows us to arbitrarily break the number into sequences of digits and sum all of them up while maintaining the congruency.

An example in base 10, divisor = 9:

1234 ≡ 12 + 34 ≡ 1 + 2 + 3 + 4 ≡ 123 + 4 ≡ 1 (mod 9)

All statements in the program makes use of this property. It can actually be simplified to a loop that runs the statement `n = (n & 0x3) + (n >> 2);` until `n < 4`, since the statement simply breaks the number in base-4 at the least significant digit and add the 2 parts up.
> 4 votes

# Answer
# Python (2 tokens?)

```
1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

```

Or

```
1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

```

Or

```
1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x

```
> 2 votes

# Answer
# JavaScript - 3 tokens

```
function div3(n) {
    var a = n * 0.3333333333333333;
    return (a | 0) == a;
}

```

This abuses the fact that using bitwise operators on a number truncates it to an integer in JavaScript.
> 2 votes

# Answer
# C - 4 tokens

```
int div3(int x) {
    return ((x * 43) >> 7) * 3 == x;
}

```

Works up to 383.

Previous version (bigger constants):

```
int div3(int x) {
    return ((x * 171) >> 9) * 3 == x;
}

```

Works up to 1535
> 1 votes

# Answer
# **Befunge 93 - 5 tokens**

**Fixed - division removed.**

```
v      @._1.@
         \
         0
         +
         3
>&>3-:0\`|
  ^      <

```

Gets input, keeps subtracting 3 until it's smaller than 0, direct the pointer up ('|'), then adds 3. If the value is 0 then the pointer moves right ("*1.@" outputs '1') else moves left ("@.*" outputs '0'). '@' terminates the program.
> 1 votes

# Answer
## Ruby, 6(?) tokens

I'm really not sure how to count tokens. OP, can you score me?

I think it's 6... `1`, `0`, `0`, `*`, `255`, `x`

Note that the `*` is not integer multiplication.

```
def div3(x)
  ([1,0,0]*255)[x]
end

```
> 1 votes

# Answer
# Python - 25 tokens

To get things started, I have a lengthy solution that is a implementation of one of the answers in the link in my first post. `n` is input.

```
a = (n>>7)-((n&64)>>6)+((n&32)>>5)-((n&16)>>4)+((n&8)>>3)-((n&4)>>2)+((n&2)>>1)-(n&1)
print(a==0 or a==3)

```

`or` is equivalent to `||`.
> 0 votes

# Answer
# Tcl, 83 bytes

```
proc T n {while \$n>9 {set n [expr [join [split $n ""] +]]};expr {$n in {0 3 6 9}}}

```

Try it online!
> 0 votes

# Answer
## Pascal, 1 token

Pascal does not have bitwise operators. (Some *dialects* do and some *implementations* use under the hood bitwise operators for operations on the `set` data type nevertheless.) Since the `in` set membership operator is not listed among the allowed operators, another relational operator is used:

```
    type
        wholeNumberLessThan256 = 0..255;

    function divisibleByThree(n: wholeNumberLessThan256): Boolean;
        const
            wholeNumbersLessThan256divisibleByThree = [
                      0,   3,   6,   9,  12,  15,  18,  21,  24,  27,
                     30,  33,  36,  39,  42,  45,  48,  51,  54,  57,
                     60,  63,  66,  69,  72,  75,  78,  81,  84,  87,
                     90,  93,  96,  99, 102, 105, 108, 111, 114, 117,
                    120, 123, 126, 129, 132, 135, 138, 141, 144, 147,
                    150, 153, 156, 159, 162, 165, 168, 171, 174, 177,
                    180, 183, 186, 189, 192, 195, 198, 201, 204, 207,
                    210, 213, 216, 219, 222, 225, 228, 231, 234, 237,
                    240, 243, 246, 249, 252, 255];
        begin
            { In Pascal `<=` denotes the `⊆` operator with sets. }
            divisibleByThree := [n] <= wholeNumbersLessThan256divisibleByThree;
        end;

```

## Extended Pascal, 0 token

NB: A lookup table could be written in Standard Pascal (ISO standard 7185), too.

```
    type
        wholeNumberLessThan256 = 0‥255;

    { The reserved word `protected` is defined by Extended Pascal.
      It just means the value of `n` may not be altered in the definition. }
    function divisibleByThree(protected n: wholeNumberLessThan256): Boolean;
        type
            tableFormat = array[type of n] of Boolean;
        const
            lookupTable = tableFormat[
                      0,   3,   6,   9,  12,  15,  18,  21,  24,  27,
                     30,  33,  36,  39,  42,  45,  48,  51,  54,  57,
                     60,  63,  66,  69,  72,  75,  78,  81,  84,  87,
                     90,  93,  96,  99, 102, 105, 108, 111, 114, 117,
                    120, 123, 126, 129, 132, 135, 138, 141, 144, 147,
                    150, 153, 156, 159, 162, 165, 168, 171, 174, 177,
                    180, 183, 186, 189, 192, 195, 198, 201, 204, 207,
                    210, 213, 216, 219, 222, 225, 228, 231, 234, 237,
                    240, 243, 246, 249, 252, 255: true;
                    otherwise false
                ];
        begin
            divisibleByThree ≔ lookupTable[n];
        end;

```
> 0 votes

---
Tags: restricted-source, atomic-code-golf
---


title: Find the Circle-Tangent Polynomials

text:
# Question
Title: Find the Circle-Tangent Polynomials
# Introduction

A circle-tangent polynomial is a polynomial of degree \\$N\ge3\\$ or above that is tangent to the unit circle from inside at all of its N-1 intersection points. The two tails that exits the circle are considered tangent at their intersection points from inside as well. You may consider such polynomials are wrapped inside the unit circle except for the two tails.

The first several circle-tangent polynomials are shown here.

The mirror images of a circle-tangent polynomial along x- or y- axis are also circle-tangent polynomials.

# Challenge

Write a full program or function that, given a whole number input \\$N\ge3\\$, outputs a circle-tangent polynomial. You may either output the whole polynomial or only its coefficient in a reasonable order. Since such coefficients can be irrational, floating point inaccuracy within reasonable range is allowed.

The algorithm you used should be theoretically able to calculate with any valid input provided, although in reality the program could timeout.

Since this is a code-golf challenge, the shortest code of each language wins.

# Example input/output

Both exact forms and approximate forms are shown for reference. The polynomials here are shown with positive leading terms, but mirrored counterparts around the axes are acceptable. The approximate forms are shown with 6 decimal places, but the calculation should be as accurate as possible.

```
Input -> Output

3     -> 8√3/9 x^3 - √3 x
         1.539601 x^3 - 1.732051 x

4     -> 27/8 x^4 - 9/2 x^2 + 1
         3.375 x^4 - 4.5 x^2 + 1

5     -> 2048√15/1125 x^5 - 128√15/45 x^3 + √15 x
         7.050551 x^5 - 11.016486 x^3 + 3.872983 x

6     -> 3125/216 x^6 - 625/24 x^4 + 25/2 x^2 - 1
         14.467593 x^6 - 26.041667 x^4 + 12.5 x^2 - 1

7     -> 1492992√35/300125 x^7 - 62208√35/6125 x^5 + 216√35/35 x^3 - √35 x
         29.429937 x^7 - 60.086121 x^5 + 36.510664 x^3 - 5.916080 x

```

# Restrictions

NO HARDCODING POLYNOMIALS. NO USE OF DEFAULT LOOPHOLES.

# Answer
> 7 votes
# Wolfram Language (Mathematica), 84 bytes

-18 bytes thanks to @att. Now returns a polynomial in `Quantifier`LocalVariable$1`.

```
p/.#&@@Solve@ForAll[x,t#2#####&@@(x-b/@2~Range~#)==x^2+(p=Sum[a@i*x^i,{i,0,#}])p-1]&

```

Try it online!

This is the first time that I write `#####` in a Mathematica program.

The two intersections that enters and exits the circle have multiplicity 3, and other intersections have multiplicity 2.

Let the polynomial be \\$p=\sum\_{i=0}^{N} a\_i x^i\\$, and the \\$x\\$-coordinate of the intersections be \\$x\_1,\dots,x\_{N-1}\\$, where \\$x\_1\\$ and \\$x\_2\\$ has multiplicity 3. Then we must have \\$x^2+(\sum\_{i=0}^{N} a\_i x^i)^2-1 = t(x-x\_1)(x-x\_2)\prod\_{i=1}^{N-1}(x-x\_i)^2\\$ for some \\$t\\$ and for all \\$x\\$. Comparing the coefficients of \\$x\\$, we have \\$2N+1\\$ equations and \\$2N+1\\$ unknowns (\\$a\_0,\dots,a\_N,x\_1,\dots,x\_{N-1},t\\$). We can solve this with the built-in function `Solve`.

# Answer
> 1 votes
# Maxima, 227 bytes

Port of @alephalpha's Mathematica code in Maxima.

This is the first time that I write a Maxima program.

---

Golfed version. Try it online!

```
f(n):=block(p:sum(a[i]*x^i,i,0,n),realonly:true,Z:subst(first(solve(makelist(coeff(expand(x^2+(p^2-1)-t*(x-x[1])*(x-x[2])*product((x-x[i])^2,i,1,n-1)),x,i)=0,i,0,2*n),append(makelist(a[i],i,0,n),makelist(x[i],i,1,n),[t]))),p))$

```

Ungolfed version. Try it online!

```
kill(all);
f(n):=block(
  p: sum(a[i]*x^i, i, 0, n),
  equationLHS: x^2 + (p^2 - 1),
  equationRHS:
    t*(x - x[1])*(x - x[2])*
    product((x - x[i])^2, i, 1, n - 1),
  equation: expand(equationLHS - equationRHS),

  /* Get the coefficients of the equation and set them to zero */
  equations: makelist(coeff(equation, x, i) = 0, i, 0, 2*n),

  realonly: true,  /* Setting Maxima to prefer real solutions */
  solution: solve(equations, append(makelist(a[i], i, 0, n), makelist(x[i], i, 1, n), [t])),

  /* Substitute the first solution into p */
  ans: subst(first(solution), p)
)$

print(makelist(f(n), n, 3, 4));

```

---
Tags: code-golf, geometry, polynomials
---


title: Characteristic polynomial

text:
# Question
Title: Characteristic polynomial
The characteristic polynomial of a square matrix \\$A\\$ is defined as the polynomial \\$p\_A(x) = \det(Ix-A)\\$ where \\$I\\$ is the identity matrix and \\$\det\\$ the determinant. Note that this definition always gives us a monic polynomial such that the solution is unique.

Your task for this challenge is to compute the coefficients of the characteristic polynomial for an integer valued matrix, for this you may use built-ins but it is discouraged.

### Rules

* input is an \\$N\times N\\$ (\\$N \ge 1\\$) integer matrix in any convenient format
* your program/function will output/return the coefficients in either increasing or decreasing order (please specify which)
* the coefficients are normed such that the coefficient of \\$x^N\\$ is 1 (see test cases)
* you don't need to handle invalid inputs

### Testcases

Coefficients are given in decreasing order (ie. \\$x^N, x^{N-1}, ..., x^2, x, 1\\$):

```
[0] -> [1 0]
[1] -> [1 -1]
[1 1; 0 1] -> [1 -2 1]
[80 80; 57 71] -> [1 -151 1120]
[1 2 0; 2 -3 5; 0 1 1] -> [1 1 -14 12]
[4 2 1 3; 4 -3 9 0; -1 1 0 3; 20 -4 5 20] -> [1 -21 -83 559 -1987]
[0 5 0 12 -3 -6; 6 3 7 16 4 2; 4 0 5 1 13 -2; 12 10 12 -2 1 -6; 16 13 12 -4 7 10; 6 17 0 3 3 -1] -> [1 -12 -484 3249 -7065 -836601 -44200]
[1 0 0 1 0 0 0; 1 1 0 0 1 0 1; 1 1 0 1 1 0 0; 1 1 0 1 1 0 0; 1 1 0 1 1 1 1; 1 1 1 0 1 1 1; 0 1 0 0 0 0 1] -> [1 -6 10 -6 3 -2 0 0]

```

# Answer
# SageMath, 3 bytes

*5 bytes saved thanks to @Mego*

```
fcp

```

Try it online!

Takes a `Matrix` as input.

`fcp` stands for **f**actorization of the **c**haracteristic **p**olynomial,

which is shorter than the normal builtin `charpoly`.
> 11 votes

# Answer
# Octave, ~~16~~ 4 bytes

@BruteForce just told me that one of the functions I was using in my previous solution can actually do the whole work:

```
poly

```

Try it online!

**16 Bytes:** This solution computes the eigenvalues of the input matrix, and then proceeds building a polynomial from the given roots.

```
@(x)poly(eig(x))

```

But of course there is also the boring

```
charpoly

```

(needs a `symbolic` type matrix in Octave, but works with the usual matrices in MATLAB.)

Try it online!
> 9 votes

# Answer
# Pari/GP, 8 bytes

```
charpoly

```

Try it online!

---

# Pari/GP, 14 bytes

```
m->matdet(x-m)

```

Try it online!
> 6 votes

# Answer
# , 53 bytes

```
function(m){for(i in eigen(m)$va)T=c(0,T)-c(T,0)*i
T}

```

Try it online!

Returns the coefficients in increasing order; i.e., `a_0, a_1, a_2, ..., a_n`.

Computes the polynomial by finding the eigenvalues of the matrix.

# \+ pracma, 16 bytes

```
pracma::charpoly

```

`pracma` is the "PRACtical MAth" library for R, and has quite a few handy functions.
> 6 votes

# Answer
# Mathematica, 22 bytes

```
Det[MatrixExp[0#]x-#]&

```

-7 bytes from alephalpha
-3 bytes from Misha Lavrov

Try it online!

and... of course...

# Mathematica, 29 bytes

```
#~CharacteristicPolynomial~x&

```

Try it online!

both answers output a polynomial
> 5 votes

# Answer
# Haskell, ~~243 223~~ 222 bytes

```
s=sum
(&)=zip
z=zipWith
a#b=[[s$z(*)x y|y<-foldr(z(:))([]<$b)b]|x<-a]
f a|let c=z pure[1..]a;g(u,d)k|m<-[z(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[s[b|(n,b)<-c&a,n==m]|(a,m)<-a#m&c]`div`k)=snd<$>scanl g(0<$c<$c,1)c

```

Try it online!

Thanks to @ØrjanJohansen for helping me golf this!

### Explanation

This uses the Faddeev–LeVerrier algorithm to compute the coefficients. Here's an ungolfed version with more verbose names:

```
-- Transpose a matrix/list
transpose b = foldr (zipWith(:)) (replicate (length b) []) b

-- Matrix-matrix multiplication
(#) :: [[Int]] -> [[Int]] -> [[Int]]
a # b = [[sum $ zipWith (*) x y | y <- transpose b]|x<-a]

-- Faddeev-LeVerrier algorithm
faddeevLeVerrier :: [[Int]] -> [Int]
faddeevLeVerrier a = snd <$> scanl go (zero,1) [1..n]
  where n = length a
        zero = replicate n (replicate n 0)
        trace m = sum [sum [b|(n,b)<-zip [1..n] a,n==m]|(m,a)<-zip [1..n] m]
        diag d = [[sum[d|x==y]|y<-[1..n]]|x<-[1..n]]
        add as bs = [[x+y | (x,y) <- zip a b] | (b,a) <- zip as bs]
        go (u,d) k = (m, -trace (a#m) `div` k)
          where m = add (diag d) (a#u)

```

<sub>**Note:** I took this straight from this solution</sub>
> 4 votes

# Answer
# Python 2 \+ numpy, 23 bytes

```
from numpy import*
poly

```

Try it online!
> 3 votes

# Answer
# MATL, 4 bytes

```
1$Yn

```

Try it online!

This is merely a port of flawr's Octave answer, so it returns the coefficients in decreasing order, i.e., `[a_n, ..., a_1, a_0]`

```
1$Yn          # 1 input Yn is "poly"

```
> 3 votes

# Answer
## CJam (48 bytes)

```
{[1\:A_,{1$_,,.=1b\~/A@zf{\f.*1fb}1$Aff*..+}/;]}

```

Online test suite

### Dissection

This is quite similar to my answer to *Determinant of an integer matrix*. It has some tweaks because the signs are different, and because we want to keep all of the coefficients rather than just the last one.

```
{[              e# Start a block which will return an array
  1\            e#   Push the leading coefficient under the input
  :A            e#   Store the input matrix in A
  _,            e#   Take the length of a copy
  {             e#     for i = 0 to n-1
                e#       Stack: ... AM_{i+1} i
    1$_,,.=1b   e#       Calculate tr(AM_{i+1})
    \~/         e#       Divide by -(i+1)
    A@          e#       Push a copy of A, bring AM_{i+1} to the top
    zf{\f.*1fb} e#       Matrix multiplication
    1$          e#       Get a copy of the coefficient
    Aff*        e#       Multiply by A
    ..+         e#       Matrix addition
  }/
  ;             e#   Pop AM_{n+1} (which incidentally is 0)
]}

```
> 1 votes

# Answer
# Python 3 and my dronery library, 476 bytes

```
λ M: C(λ f: λ t,m: t if len(t)==len(M) else f(f)(t+[n:=-sum(map(λ i: m[i][i],range(len(M))))/len(t)],matmul(M,lap(laph(__add__),m,lap(λ i: i*[0]+(n,)+(len(M)+~i)*[0],range(len(M)))))))([1],deepcopy(M))

```

(also using the Faddeev-LaVerrier algorithm)
> 1 votes

# Answer
# Maple, 39 bytes

```
LinearAlgebra[CharacteristicPolynomial]

```

```
M := <<1, 0, 0, 1, 0, 0, 0> | <1, 1, 0, 0, 1, 0, 1> | <1, 1, 0, 1, 1, 0, 0> | <1, 1, 0, 1, 1, 0, 0> | <1, 1, 0, 1, 1, 1, 1> | <1, 1, 1, 0, 1, 1, 1> | <0, 1, 0, 0, 0, 0, 1>>;
LinearAlgebra[CharacteristicPolynomial](M, x);

```
> 1 votes

# Answer
# GAP, 24 bytes

```
CharacteristicPolynomial

```

```
m := [[4,2,1,3],[4,-3,9,0],[-1,1,0,3],[20,-4,5,20]];;
chPolynomial := CharacteristicPolynomial(m);
coup := CoefficientsOfUnivariatePolynomial(chPolynomial);
Print(chPolynomial , "\n");
Print(coup , "\n");

```

Try it online!
> 1 votes

# Answer
# Maxima, 8 bytes

```
charpoly

```

```
A : matrix( [0, 5, 0, 12, -3, -6], [6, 3, 7, 16, 4, 2], [4, 0, 5, 1, 13, -2], [12, 10, 12, -2, 1, -6], [16, 13, 12, -4, 7, 10], [ 6, 17, 0, 3, 3, -1] );
ans:  expand (charpoly (A, lambda));
print(ans);

```

Try it online!
> 1 votes

---
Tags: code-golf, math, matrix, polynomials, linear-algebra
---


title: Calculate the partitions of N

text:
# Question
Title: Calculate the partitions of N
Your challenge is simple: GIven an integer **N**, ouput every list of positive integers that sums to **N**. For example, if the input was 5, you should output

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

```

These lists do not have to be output in any particular order, nor do the numbers inside each list. For example, this would also be an acceptable output for '5':

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

```

You can safely assume that the input will be a positive integer, and you can take this number in any reasonable format.

**You may NOT use any builtin functions that do this.**

If your program either fails or takes too long for large **N** this is OK, but you must at the very least produce the correct output for the first 15.

Standard loopholes apply, and the shortest answer in bytes wins!

# Test IO

```
1:
[[1]]

2:
[[1, 1], [2]]

3:
[[1, 1, 1], [1, 2], [3]]

4:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]

7:
[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 4], [1, 1, 2, 3], [1, 1, 5], [1, 2, 2, 2], [1, 2, 4], [1, 3, 3], [1, 6], [2, 2, 3], [2, 5], [3, 4], [7]]

10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]

```

Super large test case: 15 should output this

```
[[1, 1, 1, 1, 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], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]

```

### Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 84165; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 31716; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
> 6 votes
## Pyth, ~~10~~ 9 bytes

```
{SMlMM./U

```

Not too sure if this isn't cheating, but the rules only said one cannot use **integer** partition (it's not stated clearly in the question itself, but a comment by OP in the question says integer partition). I'm using ~~string~~ **list** partition, which makes slices of the list that concatenate up to the "mother" list. I believe I have to thank @Maltysen for the idea of using lists rather than strings.

n=15 takes less than one second on my machine.

In dataflow pseudocode:

```
              input       // initial data
        U     range       // makes a list of length equal to input
      ./      partition   // partitions string
   lMM        length      // length of each substring in each way to partition
 SM           sort        // sort each way to partition
{             deduplicate // removes all duplicate after sorting
              print       // implicit, output final result

```

Try it online here.

# Answer
> 6 votes
# Pyth, 18 bytes

```
L?b{SM+R-bsdsyMb]Y

```

Try it online! (The `y` at the end is used to call the function)

This is fairly quick.

This uses recursion. If the input is `b`, my method will generate the partitions from `0` to `b-1`, and then generate the correct partitions from each.

For example, when `b=4`:

* `b=0` gives `[[]]`
* `b=1` gives `[[1]]`
* `b=2` gives `[[2], [1, 1]]`
* `b=3` gives `[[3], [1, 2], [1, 1, 1]]`

Then, to each partition in `b=0`, append `4` (to make the sum 4); to each partition in `b=1`, append `3` (to make the sum `4`); etc.

This is mainly how it works.

```
L?b{SM+R-bsdsyMb]Y

L                    define a function called "y" which takes an argument: "b"
 ?b                  test for truthiness of b (in this case, test if b>0).

   {SM+R-bsdsyMb     if truthy:

             yMb         call this function from 0 to b-1.
            s            unpack each list of partitions, generating only partitions.
      +R                 to each partition (d), append:
        -                    the difference of
         b                   b (the argument) and
          sd                 the sum of d (the partition).
    SM                   sort each partition.
   {                     remove duplicates.

                ]Y   if falsey:

                 Y       yield [].
                ]        yield [[]].

```

# Answer
> 6 votes
# Haskell, 53 bytes

```
p=[[]]:[map(1:)q++[a+1:b|a:b<-q,all(a<)b]|q<-p]
(p!!)

```

# Answer
> 5 votes
# MATL, 20 bytes

```
:"0Gq:@XNG3$Yc!dS!Xu

```

**Try it online!**

For input `15` it takes about 2 seconds in the online compiler.

### Explanation

This works by generating partition *points* and then converting to partition *lengths*. What I mean by this is the following. Given input *N* = 5, a possible partition is \[2 2 1\]. This is represented by partition points \[0 2 4 5\], such that *consecutive differences* (or lengths) of the partition points give the resulting partition of the input number.

All arrays of partition points start with 0 and end with *N*. The number *k* of intermediate points varies from 0 to *N*-1. For *N* and *k* given, the intermediate points can be generated as a combination of the numbers \[1, 2, ..., *N*-1\] taken *k* at a time.

Several arrays of partition points may give rise to the same result in a different order. For example, partition points \[0 1 3 5\] would give the partition lengths \[1 2 2\], i.e. the same as the previous \[2 2 1\] only in a different order. This has to be taken into account by *sorting* each array of partition lengths and *removing duplicates*.

```
:        % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
         % except with N instead of 0
"        % For each
  0      %   Push 0
  Gq:    %   Push [1 ... N-1]. These the possible intermediate points
  @XN    %   Push k and produce the combinations. Each k produces a 2D array with
         %   each combination on a row. The value k=N produces an empty array
  G      %   Push N
  3$Yc   %   Prepend a column of zeros and append a column of N to the array
  !d     %   Transpose. Consecutive differences of each column
  S!     %   Sort each column. Transpose
  Xu     %   Keep only unique rows
         % Implicitly end for and display all arrays in the stack

```

# Answer
> 5 votes
# J, ~~49~~ ~~42~~ ~~36~~ ~~35~~ 32 bytes

```
a:1&([:~.@,(,;}./:~@,(+{.))&>)~]

```

It's tacit now!

Builds the integer partition of *n* by constructing the integer partitions from 1 to *n*. Computes the result for *n* = 15 in a millisecond.

Starting with the initial integer partition `[[1]]` which corresponds to *n* = 1, construct the next integer partition by joining the results from two operations: appending a 1 to each partition; incrementing the smallest value by 1 in each partition. Of course, duplicate partitions will be removed. To get the integer partition *n* = 2 and onwards,

```
Partition for n = 1
[[1]]

Partition for n = 2
[[1, 1]] join [[2]]
= [[1, 1], [2]]

Partition for n = 3
[[1, 2], [1, 1, 1]] join [[3], [1, 2]]
= [[3], [1, 2], [1, 1, 1]]

... and so on

```

## Usage

```
   f =: a:1&([:~.@,(,;}./:~@,(+{.))&>)~]
   f 1
┌─┐
│1│
└─┘
   f 2
┌───┬─┐
│1 1│2│
└───┴─┘
   f 3
┌─────┬───┬─┐
│1 1 1│1 2│3│
└─────┴───┴─┘
   f 5
┌─────────┬───────┬─────┬───┬─────┬───┬─┐
│1 1 1 1 1│1 1 1 2│1 2 2│2 3│1 1 3│1 4│5│
└─────────┴───────┴─────┴───┴─────┴───┴─┘
   # f 15
176

```

## Explanation

Since J does not support ragged arrays, each partition has to be boxed so they they won't be zero padded when appended to other partitions.

```
a:1&([:~.@,(,;}./:~@,(+{.))&>)~]  Input: n
a:                                The empty box
                               ]  Get the input n
  1&(                        )~   Repeat n times with an initial array of one empty box
           (              )&>       Operate on each partition
                     (   )            Hook a partition
                       {.               Get its head (the smallest value)
  1                   +                 Add 1 to it
  1           }.                      Drop the first value in each partition
                    ,                 Join the previous two results
                /:~@                  Sort it
  1         ,                         Prepend a 1 to the initial partition
             ;                        Box the last two results and join them
     [:   ,                         Flatten the pairs of boxes
       ~.@                          Remove duplicates and return
                                  Return the final result where each box
                                  is a partition of n

```

# Answer
> 4 votes
## Python, 65 bytes

**Python 3**

```
def f(n,i=1,l=[]):n or print(l);i>n or[f(n-i,i,[i]+l),f(n,i+1,l)]

```

This function accumulates a partition and prints the outputs, branching on choices. It decides how many 1's to put in the partition, how many 2's, and so on. For each value `i`, it either

* Adds a part of size `i`, and decreases `n` to `n-i`, or
* Moves on to `i+1`

If `i>n`, then no more parts can be made, so it stops. If `n` falls to `0`, the partition is successful and so is printed.

**Python 2**

```
f=lambda n,i=1:n/i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:]

```

A recursive method that outputs a list of partitions. As with the Python 3 code, it counts up the part size `i` and decides at each step whether to add another part of size `i` or stop.

Both of these do `n=15` almost instantly.

# Answer
> 3 votes
## Javascript, 194 bytes

```
p=n=>{var a=[];for(var i=1;i<=n-i;i+=1){for(v of p(n-i)){v.push(i);a.push(v.sort())}}a.push([n]);return a};n=5;s=p(n).map(v=>JSON.stringify(v));s=s.filter((v,i)=>s.indexOf(v)==i);console.log(s);

```

**Non-minified**

Finding uniques by sorting and comparing to a string is quite a hack, but probably saves space.

```
p = n => {
    var a = [];

    for (var i = 1; i <= n-i; i++)
    {
        for (v of p(n-i)) {
            v.push(i);
            a.push(v.sort());
        }
    }

    a.push([n]);

    return a;
}

n = 5;
s = p(n).map(v =>  JSON.stringify(v));
s = s.filter((v,i) => s.indexOf(v) == i);
console.log(s);

```

# Answer
> 3 votes
## Haskell, 44 bytes

```
0%m=[[]]
n%m=[j:r|j<-[m..n],r<-(n-j)%j]
(%1)

```

The auxiliary function `n%m` gives the partitions of `n` into parts `≥m`, with the main function using `m=1`. It branches of each first entry `j` with `m≤j≤n`, recursing on the remaining partition of `n-j` into parts that are at least `j`. The base case `n==0` gives just the empty partition.

# Answer
> 2 votes
# Python 3.5, ~~82~~ 72 bytes

```
f=lambda n:{(*sorted([*p,i]),)for i in range(1,n)for p in f(n-i)}|{(n,)}

```

Returns a set of tuples. **n = 15** finishes instantly.

Test it on repl.it.

# Answer
> 2 votes
# Brachylog, 33 bytes (Non-competing)

```
:1f:oad.
:1eI,.##lI,.:{.>0}a+?,.=

```

This is non-competing because of a bug fix.

This takes about 1 second for `15` on my machine. For `20` and greater this crashes with an `Out of global stack` exception.

### Explanation

This uses no partitioning built-in of any kind, and instead uses the fact that `+` works both ways through constraints propagation.

* Main predicate:

```
:1f                       Find the list of all valid outputs of predicate 1
   :oa                    Sort each element of that list
      d.                  Output is that list of sorted lists minus all duplicates

```
* Predicate 1:

```
:1eI                      I is an integer between Input and 1
    .##lI,                Output is a list of length I
          .:{.>0}a        Elements of Output are integers greater than 0
                  +?,     The sum of the elements of Output is Input
                     .=   Assign values to the elements of Output

```

# Answer
> 1 votes
# Mathematica, ~~62~~ 54 bytes

```
Inner[#2~Table~#&,FrobeniusSolve[r=Range@#,#],r,Join]&

```

The partitions of an integer *n* can be found by solving for *n*-tuples of non-negative integers (*c*<sub>1</sub>, *c*<sub>2</sub>, ..., *c*<sub>*n*</sub>) such that *c*<sub>1</sub> \+ 2 *c*<sub>2</sub> \+ ... + *n* *c*<sub>*n*</sub> = *n*. `FrobeniusSolve` is able to find all solutions to this equation which are used to create that many copies of their respective values in order to find all integer partitions of *n*.

# Answer
> 1 votes
# Pyth, 17 bytes

```
L|{SMs+LVrb0yMb]Y

```

Defines a function named `y`. Try it online.

# Answer
> 1 votes
# Jelly, 9 bytes

```
b1ŒṖḅ1Ṣ€Q

```

Try it online!

### How it works

```
b1ŒṖḅ1Ṣ€Q  Main link. Argument: n (integer)

b1         Convert n to unary, i.e., a list A of n 1's.
  ŒṖ       Generate all partitions of the list A.
    ḅ1     Convert each flat list from unary to integer.
      Ṣ€   Sort each resulting list.
        Q  Unique; deduplicate the lists.

```

# Answer
> 1 votes
## J, 39 bytes

```
[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:

```

This is a monadic verb that takes an integer and returns an array of boxed arrays. Try it here. Usage:

```
   p =: [:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:
   p 3
+-----+---+-+
|1 1 1|2 1|3|
+-----+---+-+

```

On input 15, it runs for about a second on my machine.

## Explanation

This challenge immediately looked like a job for Catalogue (`{`) and Cut (`;.`). The outline of the algorithm is:

* Produce all 0-1 arrays of length `n`.
* For each of them, cut a dummy length-`n` array along the 1s, and list the lengths of each part.
* Sort the lengths, and remove duplicate arrays from the result.

Apparently, Luis Mendo had the same idea too.

Explanation of code:

```
[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:   Input is n.
                                     <:   n-1
                                   #~     copies of
                             (<1 0)       the boxed array [1 0].
                       1    ;             Prepend the boxed array [1].
                          {@              Catalog: produces all combinations of taking one
                                          item from each box, in a high-dimensional matrix.
                        ,@                Flatten the matrix. This results in a list of all
                                          boxed 0-1 arrays of length n that begin with a 1.
    i.                                    The array A =: 0, 1, ..., n-1.
            (     "1 0)                   For each of the boxed arrays B:
              ;.1~                          cut A along the occurrences of 1s in B,
             #                              take the length of each part,
        \:~@                                sort the lengths,
      <@                                    and put the result in a box.
[:~.                                      Remove duplicate boxes.

```

# Answer
> 1 votes
# Vyxal, 7 bytes

```
ɾÞ×'∑?=

```

Try it Online!

```
ɾÞ×'∑?=
ɾ       # Get a list in the range [1, input]
 Þ×     # Get all combinations (with replacement) of all lengths
   '    # Filter for:
    ∑?= #  Sum equals the input

```

# Answer
> 0 votes
## JavaScript ~~(Firefox 30-57) 79~~ ES6, 65 bytes

```
f=(n,m=1,a=[])=>n?m>n?[]:[...f(n-m,m,[...a,m]),...f(n,m+1,a)]:[a]

```

Port of @xnor's Python solution. (If only I'd noticed that you could recurse over `m` as well as `n`...)

# Answer
> 0 votes
# 05AB1E, 8 bytes

```
Å1.œO€{ê

```

Outputs as a list of lists, from `n` amount of 1s to `[n]`, where each inner list is sorted (I know the rules allow them to be unsorted, but it's necessary for the uniquify of lists).

Try it online or verify the first 15 result.

If builtins were allowed, this would be **2 bytes** instead (with the same exact results):
`Åœ` \- Try it online or verify the first 15 results.

**Explanation:**

```
Å1        # Push a list with the (implicit) input amount of 1s
  .œ      # Get all partitions of this list
    O     # Sum each inner-most list
     €{   # Sort each inner list
       ê  # Sorted uniquify the list of lists
          # (after which the result is output implicitly)

```

Minor note: `ê` (sorted uniquify) could also just be `Ù` (uniquify) for the same result, but with the added sort it's a lot faster in this case.

# Answer
> 0 votes
# Curry (PAKCS), 44 bytes

```
(1!)
_!0=[]
a!n=anyOf[a ..n]#n
a#n=a:a!(n-a)

```

Try it online!

# Answer
> 0 votes
## Scala, 117 bytes

Port of @Dennis's Python answer in Scala.

---

Golfed version. Try it online!

```
def f(n:Int):Set[Seq[Int]]=if(n==1)Set(Seq(1))else(1 until n).flatMap(i=>f(n-i).map(_:+i).map(_.sorted)).toSet+Seq(n)

```

Ungolfed version. Try it online!

```
object Main extends App{
  def f(n: Int): Set[List[Int]] = {
    if (n == 1) {
      Set(List(1))
    } else {
      (1 until n).flatMap { i =>
        f(n - i).map { p =>
          (p :+ i).sorted
        }
      }.toSet + List(n)
    }
  }
  println(f(15));
}

```

---
Tags: code-golf, math, number-theory, combinatorics, integer-partitions
---


title: Walk by walls in a room

text:
# Question
Title: Walk by walls in a room
# Challenge

You just entered a room. Here's how it looks (you are the X):

```
|\  /|
| \/ |
| X  |
|    |
|----|

```

You challenge yourself to see if you can reach where you started by following the walls. You go right until you find a wall. Then, you turn clockwise until you are facing parallel to the wall.

For example, if you hit a `\` while going down, you will go up-left.

After that, you continue and repeat. In this visualisation, you will leave a trail. Here is how the example above would progress:

```
|\  /|
| \/ |
| Sxx|
|   X|
|----|

```

You continue following this pattern.

```
|\  /|
|X\/ |
|xSxx|
|xxxx|
|----|

```

And yes, you reached the starting point.

```
|\  /|
|x\/ |
|xXxx|
|xxxx|
|----|

```

However, if there was a hole, you could get lost:

```
|\  /|
| \/ |
| SxxX
|    |
|----|

```

## Input

As input, in any reasonable format, your program must recieve the room you are in, which consists of walls (|/-), spaces and your starting point (the X) (the starting direction is always right).

## Output

As output, your program needs to output a truthy or falsy value representing if you got to your starting point.

# Test cases

The format here is input -\> output (reason for being false).

```
/-\
|X| -> true
\-/

```

```
X -> false (hits boundary)

```

```
X    |

       -> true

    \

```

```
X    |
 -
   |   -> false (trapped in endless loop)
|
  - -

```

# Scoring

This is code-golf, so the program with the least bytes wins!

# Answer
> 2 votes
# Charcoal, 94 bytes

```
ＷＳ⊞υι≔⪫υ¶θＰθ…θ⌕θX≔⟦⟧η≔⁰ζＷ∧ＫＫ∧¬№η⟦ⅈⅉζ⟧∨φ⁻XＫＫ«⊞η⟦ⅈⅉζ⟧¿№ X⊟ＫＤ²✳ζ«Ｍ✳ζ≔⁰φ»≔＆⁷⁻ζ＆³⁻ζ⌕-/|⊟ＫＤ²✳ζζ»Ｔ¹¦¹

```

Try it online! Link is to verbose version of code. Takes input as a rectangular array of newline-terminated strings and outputs `X` if you reach the starting point. Explanation:

```
ＷＳ⊞υι

```

Input the map.

```
≔⪫υ¶θＰθ…θ⌕θX

```

Write the map to the canvas and start at the `X`.

```
≔⟦⟧η

```

Prepare to detect an infinite loop.

```
≔⁰ζ

```

Start moving horizontally.

```
Ｗ∧ＫＫ∧¬№η⟦ⅈⅉζ⟧∨φ⁻XＫＫ«

```

Repeat until the cursor moves out of bounds, repeats itself, or moves back on to the X.

```
⊞η⟦ⅈⅉζ⟧

```

Remember the current position for loop detection.

```
¿№ X⊟ＫＤ²✳ζ«

```

If the next step is out of bounds, empty or the start, then...

```
Ｍ✳ζ

```

... move to that square, and...

```
≔⁰φ

```

... remember that a step was taken.

```
»≔＆⁷⁻ζ＆³⁻ζ⌕-/|⊟ＫＤ²✳ζζ

```

Otherwise, rotate clockwise appropriately to the new direction.

```
»Ｔ¹¦¹

```

Output the final square.

# Answer
> 1 votes
# JavaScript (Node.js), 197 ~~199~~ ~~205~~ ~~208~~ bytes

> Gained some bytes by improving solution, but lost some by fixing a bug regarding "bonus case 2"
> Gained 8 bytes after analyzing suggestions from *ceilingcat* !

Interesting challenge!
The input is a single string, with line breaks at the end of each row. Each row must have the same length. Returns `true` if we can reach the starting point `X`, and `false` otherwise.

```
s=>{i=(d=(p,q)=>p.indexOf(q))(s,"X");l=~d(s,`
`);try{(g=(x,y)=>{d(`X `,c=s[z=i+x-y*l]||" ")+1?i=z:0;g([0,x,-y,0,-x|-y,t=x|-y][a=d(`X -|/\\`,c)],[0,y,0,x,x|y,t][a])})(1,0)}catch(e){}return"X"==s[i]}

```

Try it online!

---

This solution uses recursive calls of the `g()` function and catching exceptions to end an infinite loop (particularly useful for test cases 1 and 4)
Our position is the single int `i` corresponding to the index in our one-dimensional string. To go up or down, we substract or add the length `l` of the first row. This works only if all lines have the same length, which is a prerequisite for this code.
In each call we check the cell where we are supposed to go with our current direction (expressed with the `x` and `y` parameters of the `g()` function. These 2 parameters can only have the values `[-1, 0, 1]`) :

* if it's a `space`, we change our position to this cell and keep the same direction, then proceed to the next call
* if it's an `X` or a `line break` or if our target cell is outside of the string (`undefined`), we change our position to the index of this cell, and change our direction to `[0,0]`, then proceed to the next call. This allow to "stuck" our cursor on the target cell, and never move while we provoke an infinite loop to end the algorithm
* if we encounter a wall, we don't move but we determine the resulting direction for the next call, and we proceed with this call. For this part i created **this tool** to help golfing it separately of the whole "mess".
* At the end we check the final position we've reached. If it's `X`, it's truthy.
* `d()` function is a shortened `indexOf` (because we use it more than 2 times)
* in the core mechanism, i used a lot of arrays combined with the already shortened `indexOf` because i throught it's the shortest way of doing a switch case?

# Answer
> 0 votes
# Python3, 484 bytes:

```
E=enumerate
def f(b):
 r,X,Y,F=[(x,y)for x,r in E(b)for y,c in E(r)if'X'==c],0,1,0
 x,y=r.pop(0)
 while 1:
  if F==4 or(r and(x,y)==r[0][:2]):return 1
  if(len(r)>1 and(x,y,X,Y)in r)or any([(j:=x+X)<0,j>=len(b),(k:=y+Y)<0,k>=len(b[0])]):return
  B,U,I=b[j][k],X,Y
  if'|'==B:X,Y=[-1,1][Y>0],0
  if'-'==B:X,Y=0,[1,-1][X>0]
  if'\\'==B:X,Y=[1,-1][max(X,Y)>0],[1,-1][max(X,Y)>0]
  if'/'==B:X,Y=[-1,1][min(X,Y)<0],[-1,1][min(X,Y)<0]
  if(X,Y)==(U,I):r+=[(x,y,U,I)];x,y=j,k;F=0
  else:F+=1

```

Try it online!

# Answer
> 0 votes
# Java (JDK), 282 ~~283~~ ~~287~~ ~~292~~ bytes

> -2 and -1 bytes thanks to *ceilingcat* !
> -7 bytes with some optimizations

Not bad for Java!
The input is a single string, with line breaks at the end of each row. Each row must have the same length. Returns `true` if we can reach the starting point `X`, and `false` otherwise.
In this solution, we take advantage of the thinness of the boundary between `char` and `int` in Java.

```
s->{int i=s.indexOf(88),l=~s.indexOf(10),x=1,y=0,z,a,c=0,d[],r=2;for(var t=s.toCharArray();r>1;y=d[z+5])x=(d=new int[]{x,-y,0,-x|-y,a=x|-y,y,0,x,x|y,a,r=(z=i+x-y*l)<0|z>=s.length()||(c=t[z])==10|c==40?0:t[i=c>31&c<41?z:i]++>0&c==88|t[i]>95?1:2})[z="-|/\\".indexOf(c)+1];return r>0;}

```

Try it online!

---

This solution transforms the input string into an array of characters, and our cursor "increases" the ASCII values of the characters it passes through.
An infinite path is detected if we pass strictly more than **8 times** through the same cell, which would return a `false`. But if this cell also happens to be our starting point `X`, then it returns a `true`.
If we aren't in an infinite loop at all, reaching the `X` or a `\n` or having an index outside of the string will return a `true` or `false` accordingly.
`r` is the result and is kind of a ternary boolean: as long as it has the value `2`, the algorithm must continue. `0` and `1` are the falsy and truthy values before normalization.
Note:

1. I reused my "wall direction conversion system", and 1-dimensional string indexing from my JavaScript solution.
2. For debugging purpose, we can visualize the path drawn by the cursor (via increase of the ASCII values of the characters) : to do so, move `var t=s.toCharArray()` with a `;` before the `for`, and add `System.out.println(t);` just before the `return`.

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


title: Minimum base to count to a string

text:
# Question
Title: Minimum base to count to a string
### The Challenge

**Input:** alphanumeric string. You can assume that the string will only contain the characters \[0-9A-Z\]. This can come from a parameter, command line, or STDIN. Digits are always before letters in terms of the base. Think like an extended version of HEX.

**Output** `X,Y` Such that `Y` is the *minimum* base required to parse the string and `X` is the decimal value of the input string in that base.

**Examples**

> Input: "1"
>
> Output: 1,2

> Input: "HELLOWORLD"
>
> Output: 809608041709942,33

**Scoring:** This is a golf, so shortest code in bytes wins.

# Answer
> 4 votes
# Pyth, 23 bytes

```
Jmx+jkUTGdrz2KheSJ,iJKK

```

Try it online: Pyth Compiler/Executor

```
      UT       create the list [0, 1, 2, ..., 9]
    jk         join them, creates the string "0123456789"
   +    G      G is initialized with the alphabet, add both strings
               creates "0123456789abcdefghijklmnopqrstuvwxyz"
 m        rz2  maps each charater d of input().lower() to:
  x      d         the index of d in "012...xyz"
J              store the resulting list of indices in J

   SJ          sorted(J) (doesn't sort J in place, but gives you a sorted copy)
  e            last element (=maximum)
 h             + 1
K              store result in K

 iJK           convert J from base K to base 10
,   K          create the tuple (iJK, K) and prints

```

# Pyth, 16 bytes (?)

I'm not sure if this counts. The functionality I'm using was in Pyth for quite a while, but didn't work because of one stupid little bug. So the following code didn't work when the question was asked, although the docs said that it does.

```
DeGJ1#~J1#R,iGJJ

```

This defines a function `e`. Try it online.

This one was based a submission by @Reticality. He uses a different algorithm now though.

```
DeG               Define a function e(G):
   J1               J = 1
     #              while True:
      ~J1             J += 1
         #            try:
            izJ         convert z (=input) from base J into base 10
          R,izJJ        return tuple(base_10, J)
                      if exception (converting failed) do nothing

```

# Answer
> 7 votes
# Python 2, ~~74~~ ~~64~~ ~~56~~ ~~55~~ 53 bytes

```
def f(x):a=ord(max(x))-54;a+=7*(a<8);print int(x,a),a

```

Call the function (i.e. `f("HELLOWORLD")`) and outputs to stdout (`809608041709942 33`)

This is case-sensitive, requiring upper case letters, and crashes for invalid input (e.g. `"$^$%!(&£%)()`)

This code gets the `max` letter in the string (z\>x\>y\>...\>b\>a\>9\>8\>...\>2\>1\>0) and gets the largest base needed to represent it.

Change the `54` into a `76` to make it work for lowercase (but no longer upper case).

# Answer
> 6 votes
# APL (24)

```
{(B⊥D-1),B←⌈/D←⍵⍳⍨⎕D,⎕A}

```

This is a function that takes a string and returns two values, the value and the base.

```
      {(B⊥D-1),B←⌈/D←⍵⍳⍨⎕D,⎕A} 'DEADBEEF'
3735928559 16

```

Explanation:

* `⎕D,⎕A`: digits followed by letters
* `D←⍵⍳⍨`: store in `D` the 1-based index of each character of ⍵ in the string of digits followed by letters
* `B←⌈/D`: store in `B` the highest value in `D`. (which is the base to use)
* `(B⊥D-1)`: subtract 1 from each value in `D` (making them the values of the digits), and decode them as a base-`B` number.

# Answer
> 5 votes
# Pure Bash, 48

```
for((b=37;$[--b]#$1;)){ :;}
echo $[$[++b]#$1],$b

```

### Output

```
$ ./minbase.sh HELLOWORLD
./minbase.sh: line 1: ((: 32#HELLOWORLD: value too great for base (error token is "32#HELLOWORLD")
809608041709942,33
$ ./minbase.sh HELLOWORLD 2>/dev/null
809608041709942,33
$ ./minbase.sh 1 2>/dev/null
1,2
$

```

I'm taking advantage of this meta answer \- specifically that warnings output to STDERR may be ignored.

# Answer
> 4 votes
# J - 50 char

Worry not, Martin, I have come to restore order.

```
(>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower)

```

The `u:(47+i.11),65+i.26` portion creates the string `/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ`, and we want the slash so that when we find the largest digit of `HELLOWORLD` with `>./@i.`, we correct an off-by-one error at no extra charge.

Then we use J's built-in base conversion by evaling e.g. `33bhelloworld`; J has this weird internal language for specifying numbers, so we exploit that to do the base interpretation for us.

```
   (>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower) 'HELLOWORLD'
809608041709942 33
   f =: (>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower)
   f '1'
1 2
   f 'POTATO'
627732894 30
   f '1FISH2FISH'
22338345482731 29

```

# Answer
> 4 votes
# J, 31 bytes

```
3&u:(-47+7*60<]@)(>./(#.,[)<:@)

```

Usage:

```
   f=.3&u:(-47+7*60<]@)(>./(#.,[)<:@)

   f 'POTATO'
627732894 30
   f '1FISH2FISH'
22338345482731 29

```

1 byte thanks to @FUZxxl.

Try it online here.

# Answer
> 3 votes
## CJam (25 chars)

```
q{i48-_9>7*-}%_:e>):Zb',Z

```

Online demo

It's 28 chars in GolfScript, mainly because `base` doesn't have a one-char alias:

```
{48-.9>7*-}%.$-1=):^base','^

```

# Answer
> 2 votes
# Mathematica, 55 bytes

~~Hmmm, beating J with Mathematica? Something's fishy...~~

```
Print[f=FromDigits;f[#,y=f/@Max@Characters@#+1],",",y]&

```

This defines an unnamed function, which takes the string as a parameter and prints the result. You can either give it a name or use it directly:

```
Print[f=FromDigits;f[#,y=f/@Max@Characters@#+1],",",y]&@"HELLOWORLD"

```

The idea is pretty simple. Mathematica's integer parser supports bases up to 36 out of the box, so we only need to figure out the minimum base. We do that with

```
y=f/@Max@Characters@#+1

```

where `#` is the function's parameter and we've defined `f` as an alias of `FromDigits`. Note that `FromDigits` normally reads things in base 10, but that doesn't change the value of a single digit. Then we just use that to parse the string with `f[#,y...]` and the print the result, a comma and `y`.

# Answer
> 1 votes
# JavaScript, ~~100~~ 89 bytes

Thanks to nderscore for saving 10 bytes!

Works for base-2 to base-36; that's all bases JavaScript's `parseInt` supports.

```
function b(s){for(i=1;(x=parseInt(s,++i))!=x|!x.toString(i)[s.length-1];);return x+","+i}

```

The code uses a for loop starting from 1 and tries to parse the int on base-N (I use N here as `i + 1`; `i` is incremented before parsing the number) is the current number in the loop. It checks whether the parsed int is not NaN (`x==x` is the shortest way, and it works because `NaN != NaN`). It also checks that the integer converted to base-N equals the original string; this is necessary because when JavaScript parses an int, only the first part has to be valid, so `parseInt` would be able to parse "abc" on base-11 because "a" is a valid base-11 integer (while "b" and "c" are not). If the input cannot be parsed in base-N, then the for loop continues until it finds the correct base; after the for loop, the function returns the base-10 number and the original base.

Ungolfed code:

```
function getBase(str) {
    for (var base = 1;
    (parsed = parseInt(s, ++base)) != parsed | !parsed.toString(base)[str.length - 1];);
    return parsed + "," + base;
}

```

# Answer
> 1 votes
# Rust (1.0 beta), ~~81~~ 80 bytes

```
let f=|a|loop{for i in 2..{if let Ok(m)=u64::from_str_radix(a,i){return(m,i)}}};

```

Test:

```
fn main() {
    let f=|a|loop{for i in 2..{if let Ok(m)=u64::from_str_radix(a,i){return(m,i)}}};
    assert_eq!(f("1"), (1, 2));
    assert_eq!(f("POTATO"), (627732894, 30));
    assert_eq!(f("HELLOWORLD"), (809608041709942, 33));
    println!("ok!");
}

```

---

This is similar to all other answers, we try to parse the string into an integer using the internal function `u32::from_str_radix`, and start from base 2 and return immediately.

Rust is static-typed, and it requires all reachable branches to return the same type of value. The `for` loop is *not* infinite, so Rust would require a return value after the `for` loop. In order to make the type-checker happer, an outer infinite `loop` is added to make sure there is no other exit point. This saves 1 byte compared with returning a default value.

# Answer
> 1 votes
# J (61)

Explicit funcions in J can be... Somewhat hard to read.

```
3 :'(+/i*b^|.x:i.#y),b=.>:>./i=.(y i.~a.{~(48+i.10),65+i.26)'

```

### Example usage:

```
   f=: 3 :'(+/i*b^|.x:i.#y),b=.>:>./i=.(y i.~a.{~(48+i.10),65+i.26)'
   f 'POTATO'
627732894 30

```

# Answer
> 1 votes
# JavaScript (ES6) 70 ~~72~~

The base is 1 more than the biggest digit in the string, so sort and find it.

**Edit** Save 2 bytes thx @nderscore (particularly, shame on me for using `>=` instead of `>`)

```
F=s=>(b=[...s].sort().pop().charCodeAt()-47,[parseInt(s,b-=b>8&&7),b])
// TEST:
C.innerHTML=F('1') + '\n' + F('HELLOWORLD')+ '\n' + F('POTATO')
```

```
<pre id=C></pre>
```

# Answer
> 1 votes
# Vyxal, 74 bitsv2, 9.25 bytes

```
⇩:fGkrḟ›…β,

```

Try it Online!

# Answer
> 0 votes
# Swift, 105

Not very short and can probably be improved

```
func n(x:String) {var m=64;for c in x.utf8{m=max(Int(c),m)};println("\(strtoul(x,nil,10+m-64)),\(m-54)")}

```

# Answer
> 0 votes
# Haskell, 97 bytes

```
import Data.Char
j x|x>64=x-54|1<2=x-47
l=j.ord
m=l.maximum
f x=(foldl(\a b->a*m x+l b-1)0 x,m x)

```

Example run:

```
*Main> map f ["HELLOWORLD", "POTATO", "1"]
[(809608041709942,33),(627732894,30),(1,2)]

```

It's so long because I need do `import Data.Char` for `ord` and I don't have a built in read function for integers of arbitrary base.

# Answer
> 0 votes
# PHP (\>=5.4), 90

(-2 for an anoynomous function in PHP 7; 74 for a snippet)

```
function f($s){$b+=7*(8>$b=ord(max(str_split($s)))-54);return[base_convert($s,$b,10),$b];}

```

Thanks @user34736 for the -54(+8) idea; saved two bytes on my -54/-47 approach.

The function returns an array instead of printing the result. +/-0 for printing:

```
function f($s){$b+=7*(8>$b=ord(max(str_split($s)))-54);echo base_convert($s,$b,10),",$b";}

```

but a return value is easier to test:

```
function test($x,$y,$e){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>$x</td><td>$y</td><td>$e</td><td>",(strcmp($y,$e)?'N':'Y'),"</td></tr>";$h='';}
foreach([1=>'1,2','HELLOWORLD'=>'809608041709942,33','ILOVECODEGOLF'=>'21537319965321352644,32','POTATO'=>'627732894,30','1FISH2FISH'=>'22338345482731,29']as$x=>$e)test($x,implode(',',f($x)),$e);echo'</table>';

```

# Answer
> 0 votes
## Pascal, 217 B

Extended Pascal (as specified by ISO standard 10206) allows you to write (in your source code) `integer` literals up to base 36 (for example `−16#fF` denotes the value `−255` decimal). To be functionally consistent, all number literals that are allowed *in Pascal source code* are allowed as user input, too: Therefore the built‑in procedures `read`/`readLn`/`readStr` accept strings constituting valid number literals in your Pascal source (and in fact all numeric representations defined by ISO standard 6093). The task can be boiled down to determining the minimal base:

```
program p(input,output);var U,P:string(65);Y,X:integer;begin read(U);Y:=2;for X:=1 to length(U)do
Y:=card([1..Y,1..index('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',U[X])]);writeStr(P,Y:1,'#',U);readStr(P,X);write(X,Y)end.

```

Ungolfed:

```
program minimumBaseToCountToAString(input, output);
    const
        { Pascal does not make any assertion with regard to character encoding
          (except that `'A' < 'Z'`/`'a' < 'z'` (subject to availability) and
          digit characters `'0'` through `'9'` are consecutive and ascending).
          Hence another mechanism needs to be sought. }
        digit = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    type
        { A `type` range restriction will cause an error
          should we attempt to assign values outside of this range. }
        base = 2‥36;
    var
        unprocessed: string(62);
        { This size is sufficient for `'2#1010…0101'` on a 64‑bit system.
          However, it will not prevent `'36#ZZZ…ZZZ'` overflow mistakes. }
        prefixed: string(65);
        { Stores the value of the largest digit found + 1 (a. k. a. base). }
        minimumBase: base value 2;
        { Cannot reuse variable since `minimumBase` needs to be printed, too. }
        number: integer;
    begin
        { Reads up to `unprocessed.capacity` characters from `input`
          and discards the remainder of the line. }
        readLn(unprocessed);
        { In Pascal `string` indices are `1`-based. }
        for number ≔ 1 to length(unprocessed) do
        begin
            { Determines the maximum of two values without calculating
              the potential new maximum multiple times.
              The Extended Pascal function `index` returns `0`
              if `representation[number]` is not found in `digit`. }
            minimumBase ≔ card([1‥minimumBase,
                                1‥index(digit, unprocessed[number])]);
        end;
        { The `:1` is necessary so the base specification does not get padded
          with an implementation-defined default number of space characters
          (possibly causing /trailing/ characters to spill over). }
        writeStr(prefixed, minimumBase:1, '#', unprocessed);
        { This performs the actual conversion honoring `minimumBase`. }
        readStr(prefixed, number);
        { I can count to potato! }
        writeLn(number, minimumBase);
    end.

```

# Answer
> 0 votes
# Ruby `-n`, 46 bytes

```
x=0
1until(x=Integer($_,$.+=1)rescue p)
p x,$.

```

Attempt This Online!

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