title: Read out the C variable declaration

text:
# Question
Title: Read out the C variable declaration
## Background

Variable declaration statement in C consists of three parts: the *name* of the variable, its *base type*, and the *type modifier(s)*.

There are three kinds of type modifiers:

* Pointer `*` (prefix)
* Array `[N]` (postfix)
* Function `()` (postfix)
    + You can specify a list of function arguments inside the parens, but for the sake of this challenge, let's ignore it and just use `()` (which technically means "the function can take any kind of arguments").

And a way to read out the notations is as follows:

```
int i;             // i is an int
float *f;          // f is a pointer to a float
my_struct_t s[10]; // s is an array of 10 my_struct_t
int func();        // func is a function returning an int

```

The catch is that we can mix all of these to form a more complicated type, such as *array of arrays* or *array of function pointers* or *pointer to array of pointers*:

```
int arr[3][4];
// arr is an array of 3 arrays of 4 ints

int (*fptrs[10])();
// fptrs is an array of 10 pointers to functions returning an int

float *(*p)[16];
// p is a pointer to an array of 16 pointers to float

```

How did I read these complicated statements?

1. Start from the variable name. `(name) is ...`
2. Select the modifier with the highest precedence.
3. Read it:

* `[N] -> array of N ...`
* `() -> function returning ...`
* `* -> pointer to ...`

4. Repeat 2 and 3 until the modifiers are exhausted.
5. Finally, read the base type. `... (base type).`

In C, postfix operators take precedence over prefix operators, and type modifiers are no exception. Therefore, `[]` and `()` bind first, then `*`. Anything inside a pair of parens `(...)` (not to be confused with function operator) binds first over anything outside.

Illustrated example:

```
int (*fptrs[10])();
      fptrs           fptrs is ...
           [10]       array of 10 ... // [] takes precedence over *
    (*         )      pointer to ...
                ()    function returning ...
int                   int

```

## Task

Given a line of variable declaration statement written in C, output the English expression that describes the line, using the method shown above.

## Input

The input is a single C statement that includes a single base type, a single variable name, zero or more type modifiers and the ending semicolon. You have to implement all the syntax elements covered above, plus:

* Both the base type and the variable name match the regular expression `[A-Za-z_][A-Za-z0-9_]*`.
* Theoretically, your program should support unlimited number of type modifiers.

You can simplify other C syntax elements in the following ways (full implementation is also welcome):

* The base type is always a single word, e.g. `int`, `float`, `uint32_t`, `myStruct`. Something like `unsigned long long` won't be tested.
* For the array notation `[N]`, the number `N` will always be a single positive integer written in base 10. Things like `int a[5+5]`, `int a[SIZE]` or `int a[0x0f]` won't be tested.
* For the function notation `()`, no parameters will be specified at all, as pointed out above.
* For whitespaces, only the space character `0x20` will be used. You can restrict your program to specific usage of whitespaces, e.g.
    + Use only one space after the base type
    + Use a space everywhere between tokens
* However, you cannot use two or more consecutive spaces to convey more information than being a token separator.

According to C syntax, the following three combinations are invalid, and thus won't be tested:

* `f()()` Function returning function
* `f()[N]` Function returning array
* `a[N]()` Array of N functions

C developers use these equivalent forms instead (and all of these are covered in the test cases):

* `(*f())()` Function returning *pointer to function*
* `*f()` Function returning *pointer to array's first element*
* `(*a[N])()` Array of N *pointers to function*

## Output

The output is a single English sentence. You don't need to (but you can if you wish) respect English grammar, e.g. the use of `a, an, the`, singular/plural forms, and the ending dot (period). Each word should be separated by one or more whitespaces (space, tab, newline) so the result is human-readable.

Again, here is the conversion process:

1. Start from the variable name. `(name) is ...`
2. Select the modifier with the highest precedence.
3. Read it:

* `[N] -> array of N ...`
* `() -> function returning ...`
* `* -> pointer to ...`

4. Repeat 2 and 3 until the modifiers are exhausted.
5. Finally, read the base type. `... (base type).`

## Test cases

```
int i;              // i is int
float *f;           // f is pointer to float
my_struct_t s[10];  // s is array of 10 my_struct_t
int func();         // func is function returning int
int arr[3][4];      // arr is array of 3 array of 4 int
int (*fptrs[10])(); // fptrs is array of 10 pointer to function returning int
float *(*p)[16];    // p is pointer to array of 16 pointer to float

_RANdom_TYPE_123 (**(*_WTH_is_TH15)())[1234][567];
/* _WTH_is_TH15 is pointer to function returning pointer to pointer to array of
   1234 array of 567 _RANdom_TYPE_123 */

uint32_t **(*(**(*(***p)[2])())[123])[4][5];
/* p is pointer to pointer to pointer to array of 2 pointer to function returning
   pointer to pointer to array of 123 pointer to array of 4 array of 5 pointer to
   pointer to uint32_t */

uint32_t (**((*(**(((*(((**(*p)))[2]))())))[123])[4])[5]);
// Same as above, just more redundant parens

some_type (*(*(*(*(*curried_func())())())())())();
/* curried_func is function returning pointer to function returning pointer to
   function returning pointer to function returning pointer to
   function returning pointer to function returning some_type */

```

## Scoring & Winning criterion

This is a challenge. The program with the smallest number of bytes wins.

# Answer
# Python 3, ~~331 312 294 261~~ 240 bytes

```
from re import*
class V(str):__pos__=lambda s:V(s+'pointer to ');__call__=lambda s:V(s+'function returning ');__getitem__=lambda s,i:V(s+'array of %i '%i)
t,e=input().split()
print(eval(sub('\*','+',sub('(\w+)',r'V("\1 is ")',e[:-1],1)))+t)

```

Try it online!

*-19 bytes by switching to python 2 and putting the class definition into an `exec`*

*-18 bytes by changing the regex from `[a-zA-Z_][a-zA-Z0-9_]*` to `\\w+`, thanks to Kevin Cruijssen*

*-33 bytes by working some class definition magic and utilising str, thanks to Lynn, changing back to python 3*

*-21 bytes by merging together multiple regexes, thanks to infmagic2047*

Requires that only one space is contained in the input (between the type and the expression).

I think this is a pretty unique approach to the problem. This mostly uses the fact that Python itself can evaluate strings like `(**((*(**(((*(((**(*p)))[2]))())))[123])[4])[5])` and gets the correct sequence of function calls, array indexes and pointers - and that the user can overload these.
> 21 votes

# Answer
# Retina 0.8.2, ~~142~~ ~~138~~ ~~128~~ 117 bytes

```
(\w+) (.+);
($2) $1
\(\)
 function returning
\[(\d+)?]
 array of$#1$* $1
+`\((\**)(.+)\)
$2$1
\*
 pointer to
1`
 is

```

Try it online! Link includes test cases. Better grammar. Edit: Saved ~~10~~ 21 bytes by porting @DLosc's Pip solution. Explanation:

```
(\w+) (.+);
($2) $1

```

Move the type to the end and wrap the rest of the declaration in `()`s in case it contains an outer `*`.

```
\(\)
 function returning

```

Process any functions.

```
\[(\d+)?]
 array of$#1$* $1

```

Process any arrays.

```
+`\((\**)(.+)\)
$2$1

```

Move any pointers to the end of their brackets, and delete the brackets, repeatedly working from the outermost set of brackets inwards.

```
\*
 pointer to

```

Process any pointers.

```
1`
 is

```

Insert the `is`.
> 17 votes

# Answer
# Bash + cdecl \+ GNU sed, 180

`cdecl` is a venerable Unix utility that does most of what is required here, but in order to match I/O requirements, some `sed` pre- and post-processing is required:

```
sed -r 's/^/explain struct /;s/struct (int|char double|float|void) /\1 /;s/\bfunc/_func/g'|cdecl|sed -r 's/^declare //;s/as/is/;s/struct //g;s/([0-9]+) of/of \1/g;s/\b_func/func/g'

```
* No attempts made to correct grammar.

### sed Pre-processing:

* `s/^/explain struct /` \- Add "explain struct " to the start of *every* line
* `s/struct (int|char double|float|void) /\1 /` \- Remove `struct` when dealing with C language types
* `s/\bfunc/_func/g` \- "func" is recognized as a keyword by cdecl - suppress this

### sed Post-processing:

* `s/^declare //` \- remove "declare" at start of line
* `s/as/is/` \- self-explanatory
* `s/struct //g` \- remove all "struct" keywords
* `s/([0-9]+) of/of \1/g` \- correct ordering of "of "
* `s/\b_func/func/g` \- revert any "\_func" that was replaced in pre-processing

### In action:

```
$ < cdecls.txt sed -r 's/^/explain struct /;s/struct (int|char double|float|void) /\1 /;s/\bfunc/_func/g'|cdecl|sed -r 's/^declare //;s/as/is/;s/struct //g;s/([0-9]+) of/of \1/g;s/\b_func/func/g'
i is int
f is pointer to float
s is array of 10 my_struct_t
func is function returning int
arr is array of 3 array of 4 int
fptrs is array of 10 pointer to function returning int
p is pointer to array of 16 pointer to float
_WTH_is_TH15 is pointer to function returning pointer to pointer to array of 1234 array of 567 _RANdom_TYPE_123
p is pointer to pointer to pointer to array of 2 pointer to function returning pointer to pointer to array of 123 pointer to array of 4 array of 5 pointer to pointer to uint32_t
p is pointer to pointer to pointer to array of 2 pointer to function returning pointer to pointer to array of 123 pointer to array of 4 array of 5 pointer to pointer to uint32_t
curried_func is function returning pointer to function returning pointer to function returning pointer to function returning pointer to function returning pointer to function returning some_type
$

```
> 9 votes

# Answer
# Pip `-s`, ~~152~~ ~~150~~ ~~148~~ ~~139~~ ~~137~~ ~~126~~ ~~125~~ ~~123~~ 120 bytes

Third approach!

```
YaRs" ("R`\[(\d+)]`` array of \1`R"()"" function returning"L#aYyR`\((\**)(.+)[);]`{c." pointer to"X#b}{[b"is"g@>2a]}Vy^s

```

Takes the declaration as a command-line input. Try it online!

## Explanation

The code is in three parts: initial setup and handling of functions and arrays; a loop that handles parentheses and pointers; and a final rearrangement.

### Setup, functions & arrays

We want the whole declaration to be parenthesized (this helps with the loop later on), so we change `type ...` into `type (...`. Then, observe that no reordering is done with the descriptions of functions and arrays, so we can perform all those replacements first without affecting the final output.

```
Y                         Yank into y variable...
 a                        The result of a (the cmdline arg)...
  R s                     Replace the space
   " ("                    with " ("
  R `\[(\d+)]`            Replace digits in square brackets
   ` array of \1`          with " array of <digits>"
  R "()"                  Replace function parens
   " function returning"   with " function returning"

```

If our original input was `float *((*p()))[16];`, we now have `float (*((*p function returning)) array of 16;`.

### Parentheses and pointers

We run a loop replacing the outermost pair of parentheses and any asterisks that are immediately inside the opening paren.

```
L#a                     Loop len(a) times (enough to complete all replacements):
 Y                      Yank into y variable...
  y                     The result of y...
   R `\((\**)(.+)[);]`  Replace open paren, 0 or more asterisks (group 1), 1 or more
                        characters (group 2), and close paren or semicolon
    {                    with this callback function (b = group 1, c = group 2):
     c .                 The stuff in the middle, concatenated to...
      " pointer to"      that string
       X #b              repeated len(asterisks) times
    }

```

Example steps:

```
float (*((*p function returning)) array of 16;
float ((*p function returning)) array of 16 pointer to
float (*p function returning) array of 16 pointer to
float p function returning pointer to array of 16 pointer to

```

### Cleanup

The only thing remaining is to move the type to the end and add "is":

```
{[b"is"g@>2a]}Vy^s
               y^s  Split y on spaces
{            }V     Use the resulting list as arguments to this function:
 [          ]        Return a list of:
  b                   2nd argument (the variable name)
   "is"               That string
       g@>2           All arguments after the 2nd
           a          1st argument (the type)
                    The resulting list is printed, joining on spaces (-s flag)

```

For definitions like `int x;`, this approach will result in an extra space, which is permitted by the challenge.
> 9 votes

# Answer
# Java 11, ~~469~~ ~~467~~ ~~463~~ 450 bytes

```
s->{String r="",t,S[];for(s=s.replace("()","~");s.contains("(");s=s.replace(t,"").replace("()",""),r+=t+";")t=s.replaceAll(".*(\\([^()]+\\)).*","$1");S=s.split(" ");t=S[0];r+=r.isEmpty()?S[1]:s;S=r.split(";");r=S[0].replaceAll(".*?(\\w+).*","$1 is ");for(var p:S)r+=p.replaceAll("[A-Za-z_]+\\d+|[^\\[\\d]","").replaceAll("\\[(\\d+)","array of $1 ")+(p.contains("~")?"function returning ":"")+"pointer to ".repeat(p.split("\\*").length-1);return r+t;}

```

Try it online.

**Explanation:**

```
s->{               // Method with String as both parameter and return-type
  String r="",     //  Result-String, starting empty
         t,        //  Temp-String, starting uninitialized
         S[];      //  Temp String-array, starting uninitialized
  for(s=s.replace("()","~");
                   //  Replace all "()" in the input `s` with "~"
      s.contains("(");
                   //  Loop as long as the input `s` still contains "("
      ;            //    After every iteration:
       s=s.replace(t,"")
                   //     Remove `t` from `s`
          .replace("()",""),
                   //     And also remove any redundant parenthesis groups
       r+=t+";")   //     Append `t` and a semi-colon to the result-String
    t=s.replaceAll(".*(\\([^()]+\\)).*","$1");
                   //   Set `t` to the inner-most group within parenthesis
  S=s.split(" ");  //  After the loop, split the remainder of `s` on the space
  t=S[0];          //  Set `t` to the first item (the type)
  r+=              //  Append the result-String with:
    r.isEmpty()?   //   If the result-String is empty
                   //   (so there were no parenthesis groups)
     S[1]          //    Set the result-String to the second item
    :              //   Else:
     s;            //    Simple append the remainder of `s`
  S=r.split(";");  //  Then split `r` on semi-colons
  r=S[0].replaceAll(".*?(\\w+).*",
                   //  Extract the variable name from the first item
     "$1 is ");    //  And set `r` to this name appended with " is "
  for(var p:S)     //  Loop over the parts split by semi-colons:
    r+=            //   Append the result-String with:
      p.replaceAll("[A-Za-z_]+\\d+
                   //    First remove the variable name (may contain digits)
         |[^\\[\\d]","")
                   //    And then keep only digits and "["
       .replaceAll("\\[(\\d+)",
                   //    Extract the number after "["
         "array of $1 ")
                   //    And append the result-String with "array of " and this nr
      +(p.contains("~")?
                   //    If the part contains "~"
         "function returning "
                   //     Append the result-String with "function returning "
       :           //    Else:
        "")        //     Leave the result-String the same
      +"pointer to ".repeat(
                   //    And append "pointer to " repeated
         p.split("\\*").length-1);
                   //    the amount of "*" in the part amount of time
  return r         //  Then return the result-String
          +t;}     //  appended with the temp-String (type)

```
> 8 votes

# Answer
# JavaScript (ES6), ~~316~~ ... ~~268~~ 253 bytes

```
s=>(g=s=>[/\d+(?=])/,/\*/,/!/,/.+ /,/\w+/].some((r,i)=>(S=s.replace(r,s=>(O=[O+`array of ${s} `,O+'pointer to ','function returning '+O,O+s,s+' is '+O][i],'')))!=s)?g(S):'',F=s=>(O='',S=s.replace(/\(([^()]*)\)/,g))!=s?O+F(S):g(s)+O)(s.split`()`.join`!`)

```

Try it online!

## Commented

### Helper function

```
g = s =>                             // s = expression to parse
  [                                  // look for the following patterns in s:
    /\d+(?=])/,                      //   array
    /\*/,                            //   pointer
    /!/,                             //   function
    /.+ /,                           //   type
    /\w+/                            //   variable name
  ].some((r, i) =>                   // for each pattern r at index i:
    ( S = s.replace(                 //   S = new string obtained by removing
      r,                             //       the pattern matching r from s
      s => (                         //     using the first match s and the index i,
        O = [                        //     update the output O:
          O + `array of ${s} `,      //       array
          O + 'pointer to ',         //       pointer
          'function returning ' + O, //       function
          O + s,                     //       type
          s + ' is ' + O             //       variable name
        ][i],                        //
        ''                           //     replace the match with an empty string
    )))                              //   end of replace()
    != s                             //   make some() succeed if S is not equal to s
  ) ?                                // end of some(); if truthy:
    g(S)                             //   do a recursive call with S
  :                                  // else:
    ''                               //   stop recursion and return an empty string

```

### Main part

```
s => (                 // s = input
  g = …,               // define the helper function g (see above)
  F = s => (           // F = recursive function, taking a string s
    O = '',            //   O = iteration output, initialized to an empty string
    S = s.replace(     //   S = new string obtained by removing the next expression from s
      /\(([^()]*)\)/,  //     look for the deepest expression within parentheses
      g                //     and process it with the helper function g
    )                  //   end of replace()
  ) != s ?             // if S is not equal to s:
    O + F(S)           //   append O to the final output and do a recursive call with S
  :                    // else (we didn't find an expression within parentheses):
    g(s) + O           //   process the remaining expression with g and return O
)(s.split`()`.join`!`) // initial call to F with all strings '()' in s replaced with '!'

```
> 7 votes

# Answer
# Perl 6, ~~209~~ ~~190~~ ~~171~~ ~~162~~ 153 bytes

```
{~({(.[1]Z'is'),.<e>.&?BLOCK,('array of'X .[2]),('function returning','pointer to'Zxx.[3,0])if $_}(m:g/(\*)*[(\w+)+|\(<e=~~>.][\[(\d+).]*(\(.)*/[1]),$0)}

```

Try it online!

Recursive regex approach. Produces some extra space characters which can be avoided at the cost of 3 bytes.

### Explanation

```
{     # Anonymous block
 ~(   # Convert list to string
   {  # Block converting a regex match to a nested list
     (.[1]            # Array of 0 or 1 variable names
       Z'is'),        # zipped with string "is"
     .<e>.&?BLOCK,    # Recursive call to block with subexpression
     ('array of'      # String "array of"
       X .[2]),       # prepended to each array size
     ('function returning',  # Strings "function returning"
      'pointer to'           # and "pointer to"
      Zxx             # zipped repetition with
      .[3,0])         # number of function and pointer matches
     if $_            # Only if there's an argument
   }
   (             # Call block
     m:g/        # Input matched against regex
      (\*)*      # Sequence of asterisks, stored in [0]
      [          # Either
       (\w+)+    # the variable name, stored as 1-element array in [1]
       |         # or
       \(        # literal (
         <e=~~>  # the same regex matched recursively, stored in <e>
       .         # )
      ]
      [\[(\d+).]*  # Sequence of "[n]" with sizes stored in [2]
      (\(.)*       # Sequence of "()" stored in [3]
     /
     [1]  # Second match
   ),
   $0     # First match (base type)
 )
}

```
> 5 votes

# Answer
# Clean, 415 bytes

```
import StdEnv,Text
$s#(b,[_:d])=span((<>)' ')(init s)
=join" "(?d++[""<+b])
?[]=[]
?['()':s]=["function returning": ?s]
?['*':s]= ?s++["pointer to"]
?['[':s]#(n,[_:t])=span((<>)']')s
=["array of "<+n: ?t]
?s=case@0s of(['(':h],t)= ?(init h)++ ?t;(h,t)|t>[]= ?h++ ?t=[h<+" is"]
~c=app2((++)[c],id)
@n[c:s]=case c of'('= ~c(@(n+1)s);')'|n>1= ~c(@(n-1)s)=([c],s);_|n>0= ~c(@n s)=span(\c=c<>'('&&c<>'[')[c:s]
@_ e=(e,e)

```

Try it online!
> 4 votes

# Answer
# , ~~225~~ 218 bytes

```
g=gsub
"&"="@"=paste
"["=function(a,b)a&"array of"&b
"+"=function(a)a&"pointer to"
eval(parse(t=g('\\(\\)','@"function returning"',g('(\\w+) (.*?)([A-Za-z_]\\w*)(.*);','\\2"\\3 is"\\4&"\\1"',g('\\*','+',readline())))))

```

Try it online!

Full program, wrapped in a function on TIO for convenient testing of all test cases at once.

First, we use Regex to convert the input of the form `type ...name...;` to `..."name is"..."type"`. Function notation `()` is then converted to text with a high-precedence concatenation operator. Unfortunately, we also have to replace `*` with `+` as the former is not acceptable as an unary operator. The rest is done by R's `eval` with overloaded operators.
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~192~~ 190 bytes

Saved 2 bytes thanks to @Razetime

```
'(\w+) is(.+);'⎕R'\2 \1'((('\*',z)⎕R'\1 pointer to'((∊'\('z'\)')(z,'\[(\d+)\]')('\(\)',⍨z←'([A-Za-z0-9_ ]+)')⎕R'\1' '(\1 array of \2)' '(\1 function returning)'))⍣≡'(\w+)(?!\]|\w)'⎕R'\1 is')

```

Try it online!

This came out longer than I thought. I may have to go back to using parser combinators instead of just plain regex again.

`z` matches an English phrase such as "foo is pointer to". The parentheses allow the capturing group to be used later.

The main train first adds " is" to such phrases, so `int (*p[3])()` becomes `int is(*p is[3])()`. The negative lookahead `(?!\]|\w)` is used to avoid matching array dimensions.

Then `⍣≡` keeps applying the substitutions to the left of it until there is nothing left to replace. First, parentheses around phrases are removed, `z[d]` is replaced with `(z array of d)`, and `z()` is replaced with `(z function returning)`. The parentheses are necessary in case there are multidimensional arrays - we don't want `*z` to be replaced before we come back to the rest of the dimensions. Then `*z` is replaced with `z pointer to`. So `int is(*p is[3])()` becomes `int is(*(p is array of 3))()` -\> `int is(p is array of 3 pointer to)()` -\> `int isp is array of 3 pointer to function returning`.

The last part matches the pattern `TYPE isFIRST_PART;` and rearranges it to become `FIRST_PART TYPE`.
> 4 votes

# Answer
# Red, 418 410 bytes

```
func[s][n: t:""a: charset[#"a"-#"z"#"A"-#"Z"#"0"-#"9""_"]parse s[remove[copy x thru" "(t: x)]to a
change[copy x[any a](n: x)]"#"]b: copy[]until[c: next find s"#"switch c/1[#"("[append
b"function returning"take/part c 2]#"["[parse c[remove[skip copy d to"]"(append b
reduce["array of"d])skip]]]#")"#";"[take c c: back back c while[#"*"= c/1][take c
c: back c append b"pointer to"]take c]]s =""]reduce[n"is"b t]]

```

Try it online!

## Explanation:

```
f: func [ s ] [
    n: t: 0                                         ; n is the name, t is the type
    a: charset [ #"a"-#"z" #"A"-#"Z" #"0"-#"9" "_" ]; characters set for parsing
    parse s[                                        ; parse the input with the following rules
        remove [ copy x thru " " ](t: x)            ; find the type, save it to t and remove it from the string
        to a                                        ; skip to the next alphanumerical symbol
        change [ copy n [ any a ] (n: x) ] "#"      ; save it to n and replace it with '#'
    ]
    b: copy [ ]                                     ; block for the modifiers
    until [                                         ; repeat
       c: next find s "#"                           ; find the place of the name
       switch c/1 [                                 ; and check what is the next symbol
           #"(" [ append b "function returning"     ; if it's a '('- it's a function - add the modifier
                  take/part c 2                     ; and drop the "()"
                ]
           #"[" [ parse c [                         ; '[' - an array
                     remove [ skip copy d to "]"    ; save the number
                             (append b reduce [     ; and add the modifier
                                  "array of" d
                              ] )
                             skip ]                 ; and remove it from the string
                     ]
                ]
           #")"                                     ; a closing bracket
           #";" [ take c                            ; or ';' - drop it
                    c: back back c                  ; go to the left
                    while [ #"*" = c/1 ]            ; and while there are '*'
                    [
                        take c                      ; drop them
                        c: back c                   ; go to the left
                        append b "pointer to"       ; add the modifier
                    ]
                    take c                          ; drop '(' (or space)
                 ]
       ]
       s = ""                                       ; until the string is exhausted
    ]
    reduce [ n "is" b t ]                     ; display the resul
]

```
> 3 votes

# Answer
# JavaScript 250 Bytes \[249?\]

This uses 250 Bytes:

```
k=>(a=k.match(/\W|\w+/g),s=[v=j=r=""],f=y=>!j&!a[i+1]||(m=a[i],v?(r+=v=m=='['?`array of ${a[i+=3,i-2]} `:m<')'?(i+=2,"function returning "):s[j-1]=='*'?j--&&"pointer to ":""):m==')'?v=j--|i++:m<'+'?s[j++]=a[i++]:r+=a[v=i++]+" is ",f(),r+a[0]),f(i=2))

```

Explanation:

Basically, it's reading from a buffer `a`, which is the tokenized input. It continuously moves tokens from the buffer `a` to a stack `s`, until evaluation mode is triggered. Evaluation mode will consume postfix operations first `()`, `[]` from the buffer, and then it will consume the prefix operator `*` from the stack. Evaluation mode is triggered when the state is where a word would be (Either the typename is found and consumed, or an ending `)` is found and removed). Evaluation mode is deactivated when no more prefix/postfix operators are found.

```
k=>( // k is input
    a=k.match(/\W|\w+/g), // split by symbol or word
    s=[v=j=r=""], // j=0, v=false, r="", s=[]
    // s is the stack, r is the return string,
    // v is true if we're in evaluation mode (Consume (), [], *)
    // v is false if we're waiting to see a ) or token, which triggers evaluation
    // j is the index of the top of the stack (Stack pointer)
    f=y=>!j&!a[i+1]||( // !j means stack is empty, !a[i+1] means we're at the ;
        m=a[i], // Save a[i] in a variable
        v // Are we evaluating?
        ?(
        r+=v=
            m=='[' // Array
            ?`array of ${a[i+=3,i-2]} ` // Skip three tokens: "[", "10", "]"
                                        // a[i-2] is the "10"
            :m<')' // m == '('
                ?(i+=2,"function returning ") // Skip two tokens: "(", ")"
                :s[j-1]=='*' // Stack has a pointer
                    ?j--&&"pointer to " // Pop the stack
                    :"" // Set v to be false, r+=""
        )
        :m==')'
            ?v=j--|i++ // Pop the '(', skip over the ')', v = Evaluation mode
            :m<'+' // m == '*' || m == '('
                ?s[j++]=a[i++] // push(s, pop(a))
                :r+=a[v=i++]+" is " // Otherwise we have the token
        , f(), r+a[0] // Recurse f(), and return r+a[0]. a[0] is the type.
    ),
    f(i=2) // Set i=2, and call f(), which returns the final value r + type
    // a = ["type", " ", ...], so i=2 give the first real token
    // This soln assumes there is only one space, which is an allowed assumption
)

```

# NOTE

If I understand "Use a space everywhere between tokens" correctly:

```
k=>(a=k.split(" "),s=[v=j=r=""],f=y=>!j&!a[i+1]||(v?(r+=v=a[i]=='['?`array of ${a[i+=3,i-2]} `:a[i]<')'?(i+=2,"function returning "):s[j-1]=='*'?j--&&"pointer to ":""):a[i]==')'?v=j--|i++:a[i]<'+'?s[j++]=a[i++]:r+=a[v=i++]+" is ",f(),r+a[0]),f(i=1))

```

is technically valid, and uses

# 249 Bytes

Assuming that there's a space between every token.
> 3 votes

# Answer
# APL(NARS), chars 625, bytes 1250

```
CH←⎕D,⎕A,⎕a,'_'⋄tkn←nm←∆←''⋄in←⍬⋄⍙←lmt←lin←0
eb←{∊(1(0 1 0)(0 1)(1 0))[⍺⍺¨⍵]}
tb←{x←({⍵='[':3⋄⍵=']':4⋄⍵∊CH,' ':1⋄2}eb⍵)\⍵⋄(x≠' ')⊂x}

gt
tkn←''⋄→0×⍳⍙>lin⋄tkn←∊⍙⊃in⋄⍙+←1⋄→0×⍳(⍙>lin)∨'('≠↑tkn⋄→0×⍳')'≠↑⍙⊃in⋄tkn←tkn,⍙⊃in⋄⍙+←1

r←dcl;n
   n←0
B: gt⋄→D×⍳'*'≠↑tkn⋄n+←1⋄→B×⍳tkn≢''
D: r←ddcl⋄∆←∆,∊n⍴⊂'pointer to '

r←ddcl;q
   r←¯1⋄→0×⍳0>lmt-←1
   →A×⍳∼'('=↑tkn⋄q←dcl⋄→F×⍳')'=↑tkn⋄→0
A: →B×⍳∼(↑tkn)∊CH⋄nm←tkn⋄→F
B: r←¯2⋄→0
F: gt⋄→G×⍳∼tkn≡'()'⋄∆←∆,'function that return '⋄→F
G: →Z×⍳∼'['=↑tkn⋄∆←∆,'array of ',{''≡p←(¯1↓1↓tkn):''⋄p,' '}⋄→F
Z: r←0

r←f w;q
   nm←∆←''⋄in←tb w⋄⍙←1⋄lin←↑⍴in⋄lmt←150⋄gt⋄→A×⍳∼0>q←dcl⋄r←⍕q⋄→0
A: r←nm,' is a ',∆,1⊃in

```

this is just one traslation from C language to APL from code in the book: "Linguaggio C" by Brian W. Kerninghan and Dennis M. Ritchie chapter 5.12. I don't know how reduce all that because i had not understood 100% that code, and because I do not know too much on APL... The function for exercise it is f; i think are only allowed 150 nested parentesis '(' ')' for error return one strign with one negative value in that or the string descrition if all is ok. It seems this is not better than the other version even if less chars because the other sees the errors better. Some test:

```
  f 'int f()()'
f is a function that return function that return int
  f 'int a[]()'
a is a array of function that return int
  f 'int f()[]'
f is a function that return array of int
  f 'int i;'
i is a int
  f 'float *f;'
f is a pointer to float
  f 'my_struct_t s[10];'
s is a array of 10 my_struct_t
  f 'int func();'
func is a function that return int
  f 'int arr[3][4];'
arr is a array of 3 array of 4 int
  f 'int (*fptrs[10])();'
fptrs is a array of 10 pointer to function that return int
  f 'float *(*p)[16]; '
p is a pointer to array of 16 pointer to float
  f '_RANdom_TYPE_123 (**(*_WTH_is_TH15)())[1234][567];'
_WTH_is_TH15 is a pointer to function that return pointer to pointe
  r to array of 1234 array of 567 _RANdom_TYPE_123
  f 'uint32_t (**((*(**(((*(((**(*p)))[2]))())))[123])[4])[5]);'
p is a pointer to pointer to pointer to array of 2 pointer to funct
  ion that return pointer to pointer to array of 123 pointer to
   array of 4 array of 5 pointer to pointer to uint32_t

```
> 1 votes

---
Tags: code-golf, parsing, c, syntax
---


# Question
Title: Into how many pieces can you cut this string?
Consider a piece of string (as in "rope", not as in "a bunch of characters"), which is folded back and forth on the real line. We can describe the shape of the string with a list of points it passes through (in order). For simplicity, we'll assume all of those points are integers.

Take as an example `[-1, 3, 1, -2, 5, 2, 3, 4]` (note that not each entry implies a fold):

The string extending along the vertical direction is only for visualisation purposes. Imagine the string all flattened onto the real line.

Now here is the question: what is the greatest number of pieces this string can be cut into with a single cut (which would have to be vertical in the above picture). In this case, the answer is *6* with a cut anywhere between `2` and `3`:

To avoid ambiguities, the cut *has* to be performed at a non-integer position.

## The Challenge

Given a list of integer positions a string is folded through, you're to determine the greatest number of pieces the string can be cut into with a single cut at a non-integer position.

You may write a full program or a function. You may take input via STDIN, command-line argument, prompt or function parameter. You may write output to STDOUT, display it in a dialog box or return it from the function.

You may assume that the list is in any convenient list or string format.

The list will contain at least **2** and no more than **100** entries. The entries will be integers, each in the range **-231 ≤ pi \< 231**. You may assume that no two consecutive entries are identical.

Your code must process any such input (including the test cases below) in less than 10 seconds on a reasonable desktop PC.

## Test Cases

All test cases are simply input followed by output.

```
[0, 1]
2

[2147483647, -2147483648]
2

[0, 1, -1]
3

[1, 0, -1]
2

[-1, 3, 1, -2, 5, 2, 3, 4]
6

[-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868,  -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526,  -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846,  -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888,  -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488,  -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463,  676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202,  2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212,  -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326,  1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157,  1072577364, -538901064]
53

[-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718,  -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585]
2

```

# Answer
# APL, ~~16~~ 14 bytes

```
1+⌈/+/2≠/∘.≤⍨⎕

```

Thanks to @ngn for saving 2 bytes.

The  is actually a box character, not a missing-font error. You can try the program at tryapl.org, but since  is not fully supported there, you have to replace it by the input value:

```
    1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6

```

### Explanation

The program is best explained with the example input `s = ¯1 3 1 ¯2 5 2 3 4`, which is taken from STDIN by . First, we compute the -outer product of `s` with itself using `∘.≤⍨`. This results in a Boolean matrix whose `i`th row tells which elements of `s` are less than or equal to `s[i]`:

```
1 1 1 0 1 1 1 1
0 1 0 0 1 0 1 1
0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1
0 0 0 0 1 0 0 1

```

The occurrences of `0 1` and `1 0` on row `i` mark places where the string passes over the point `s[i] + 0.5`. We match on these on every row using `2≠/`, "reduce 2-sublists by ":

```
0 0 1 1 0 0 0
1 1 0 1 1 1 0
1 0 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
1 1 0 1 0 0 0
1 1 0 1 1 1 0
0 0 0 1 1 0 1

```

What remains is to take the sums of the rows with `+/`

```
2 5 3 0 2 3 5 3

```

and one plus the maximum of these with `1+⌈/`:

```
6

```

The result is automatically printed to STDOUT in most APL implementations.
> 16 votes

# Answer
# Python, ~~88~~ ~~75~~ 73 bytes

```
lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1

```

Just a straightforward lambda

---

Just to show another approach:

# Pyth, ~~28~~ 27 bytes

```
heSmsmq@S+k(d)1dC,QtQm+b.5Q

```

This one's roughly equivalent to

```
lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1

```

applied to the input list from STDIN. Try it on the online interpreter.
> 16 votes

# Answer
# Pyth: ~~31~~ ~~30~~ ~~29~~ ~~28~~ ~~24~~ 23 character (Python 68 chars)

```
heSmsm&<hSkdgeSkdC,tQQQ

```

Try it here: Pyth Compiler/Executor

It expects a list of integers as input `[-1, 3, 1, -2, 5, 2, 3, 4]`

It's a straightforward translation of my Python program:

```
lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)

```

## Old solution: Pyth 28 char

Just for archiving reasons.

```
heSmsm<*-dhk-dek0C,tQQm+b.5Q

```

A corresponding Python code would be:

```
f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])

```
> 16 votes

# Answer
# CJam, ~~36 34 33~~ 30 bytes

```
q~[__(+]zW<f{f{1$+$#1=}1b}$W=)

```

I believe that there is a better algorithm out there in the wild. Still, this works under the limit required for all test cases (even on the online compiler)

Input is like

```
[-2142140080 -2066313811 -2015945568 -2013211927 -1988504811 -1884073403 -1860777718  -1852780618 -1829202121 -1754543670 -1589422902 -1557970039 -1507704627 -1410033893  -1313864752 -1191655050 -1183729403 -1155076106 -1150685547 -1148162179 -1143013543  -1012615847 -914543424 -898063429 -831941836 -808337369 -807593292 -775755312 -682786953 -679343381 -657346098 -616936747 -545017823 -522339238 -501194053  -473081322 -376141541 -350526016 -344380659 -341195356 -303406389 -285611307 -282860017 -156809093 -127312384 -24161190 -420036 50190256 74000721 84358785  102958758 124538981 131053395 280688418 281444103 303002802 309255004 360083648  400920491 429956579 478710051 500159683 518335017 559645553 560041153 638459051  640161676 643850364 671996492 733068514 743285502 1027514169 1142193844 1145750868  1187862077 1219366484 1347996225 1357239296 1384342636 1387532909 1408330157  1490584236 1496234950 1515355210 1567464831 1790076258 1829519996 1889752281  1903484827 1904323014 1912488777 1939200260 2061174784 2074677533 2080731335 2111876929 2115658011 2118089950 2127342676 2145430585]

```

Output (for above case) is

```
2

```

**How it works**

```
q~[__(+]zW<f{f{1$+$#1=}1b}$W=)
q~                                "Evaluate input string as array";
  [__                             "Put two copies of it in an array";
     (+]                          "Shift first element of second copy to its end";
        z                         "Zip together the two arrays. This creates";
                                  "pair of adjacent elements of the input.";
         W<                       "Remove the last pair";
           f{            }        "For each element of input array, take the zipped";
                                  "array and run the code block";
             f{       }           "For each element of the zipped array along with";
                                  "the current element from input array, run this block";
               1$+                "Copy the current number and add it to the pair";
                  $#              "Sort the pair and find index of current number";;
                    1=            "check if index == 1 for a < I <= b check";
                       1b         "Get how many pairs have this number inside of them";
                          $W=)    "Get the maximum parts the rope can be cut into";

```

Now suppose the input array is `[-1 3 1 -2 5 2 3 4]`, the zipping steps look like:

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

```

The second array on the last line is the folds of the string.

Now we iterate over `[-1 3 1 -2 5 2 3 4]` and calculate the number of sets each of them lie in. Get the maximum out of that number, increment it and we have our answer.

Try it online here
> 10 votes

# Answer
# Matlab (123)(97)(85)

Yay, finally a use for *XNOR*=) I am sure it can be golfed down way more.

But honestly I am a little embarassed that MatLab is becoming the language I know best =/

Approximate runtime is `O(n^2)`.

**EDIT2:**

```
a=input();v=2:nnz(a);disp(max(arrayfun(@(e)sum(~xor(a(v-1)<e,e<a(v))),sort(a)-.5))+1)

```

**EDIT:** New more golfed version (including hints from @DennisJaheruddin, thanks!)

```
a=input();c=sort(a)-.5;n=0;v=2:nnz(c);for e=c;n=[n,sum(~xor(a(v-1)<e,e<a(v)))];end;disp(max(n)+1)

```

Old version:

```
a=input();
c=conv(sort(a),[.5,.5],'valid');' %find all cutting positions by taking the mean of two successive points
k=numel(c);
for e=1:k %iterate over all 'cuts'
    n(e)=sum(~xor(a(1:k)<c(e),c(e)<a(2:k+1)));%find the number of threads the cut cuts
end
disp(max(n)+1) %output the max

```

@MartinBüttner: I really enjoy your nice little just-before-I-go-to-bed-challenges!
> 10 votes

# Answer
# Mathematica ~~134 133~~ 104

Fun to solve, despite the size of the code. Further golfing can still be achieved by replacing the idea of `IntervalMemberQ[Interval[a,b],n]` with `a<n<b`.

```
n_~f~i_:=Count[IntervalMemberQ[#,n]&/@i,1>0];
g@l_:=Max[f[#,Interval/@Partition[l,2,1]]&/@(Union@l+.5)]+1

```

---

```
g[{-1, 3, 1, -2, 5, 2, 3, 4}]

```

> 6

---

## Explanation

`list1` is the given list of points `list2` is a shortened list that removes numbers that were not at folds; they are irrelevant. It's not necessary to do this, but it leads to a clearer and more efficient solution.

```
list1 = {-1, 3, 1, -2, 5, 2, 3, 4};
list2 = {-1, 3, 1, -2, 5,2, 3, 4} //. {beg___, a_, b_, c_, end___} /; (a <= b <= c)
 \[Or] (a >= b >= c) :> {beg, a, c, end}

```

The intervals in `list1` and `list2` are shown in the plots below:

```
NumberLinePlot[Interval /@ Partition[list1, 2, 1]]
NumberLinePlot[intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1]]

```

---

We only need to test a single line in each interval determined by the fold points. The test lines are the dashed vertical lines in the plot.

```
delimitersLeftToRight = Union[list2]
testLines = delimitersLeftToRight + .5
NumberLinePlot[
 intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1],
 GridLines -> {testLines, {}},
 GridLinesStyle -> Directive[Gray, Dashed]]

```

---

`f` finds the number of cuts or crossings of each test line. The line at x= 2.5 makes 5 crossings. That leaves 5 + 1 pieces of string.

```
f[num_, ints_] := Count[IntervalMemberQ[#, num] & /@ ints, True]
f[#, intervalsArrangedVertically] & /@ testLines
Max[%] + 1

```

> {2, 3, 5, 3, 2, 0}
> 6
> 9 votes

# Answer
# Pyth, 21 bytes

```
heSmsmq1xS+dSkdC,tQQQ

```

Try it here.

Give input as Python-style list, e.g. `[-1, 3, 1, -2, 5, 2, 3, 4]`

Closely based off of @jakube's program, but with an improved central algorithm. Instead of doing a `>` check and a `>=` check, I do a `.index()` on the three numbers combined and make sure the index is 1, meaning it's greater than minimum and less than or equal to the maximum.
> 8 votes

# Answer
## R, ~~86~~ 83

Was working through this and then realised that I had essentially come up with the same solution as Optimizer and others I suspect.

Anyway here it is as a function that takes a vector

```
f=function(l)max(colSums(mapply(function(n)c(l[-1],NA,l)<=n&c(l,l[-1],NA)>=n,l),T))

```
> 7 votes

# Answer
# Python - 161

This can probably be golfed more. gnibbler helped golf this a lot.

```
l=input()
d={}
for i in zip(l,l[1:]):d[sum(i)/2.]=0
for i,k in zip(l,l[1:]):
 for j in[m for m in d.keys()if min(i,k)<m<max(i,k)]:d[j]+=1
print max(d.values())+1

```
> 4 votes

# Answer
## GolfScript (43 bytes)

```
~[.(;]zip);{$}%:x{0=:y;x{{y>}%2,=},,}%$-1=)

```

In terms of efficiency, this is O(n^2) assuming that comparisons take O(1) time. It breaks the input into line segments and for each starting point it counts the half-open line segments which cross it.

Online demo
> 4 votes

# Answer
# Ruby, 63

Similar to the Python solutions in concept.

```
->a{a.map{|x|a.each_cons(2).count{|v|v.min<x&&x<=v.max}}.max+1}

```

Add 2 chars before the code e.g. `f=` if you want a named function. Thx to MarkReed.
> 3 votes

# Answer
# C#, ~~73~~ 65 bytes

```
N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b))

```

Reading the rules I thought a C# lambda should do pretty well.

Edit: just found `Count` has a useful overload for filtering!

You can test this by defining the appropriate `delegate` type:

```
delegate int solver(int[] l);

```

And then

```
var l = new int[] { -1, 3, 1, -2, 5, 2, 3, 4 };
solver s = N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b));

Console.WriteLine(s(l));

```
> 3 votes

# Answer
# Matlab (63 43)

Input is given as a row vector passed to the function `f`. So for example `f([-1, 3, 1, -2, 5, 2, 3, 4])` returns `6`.

```
f=@(x)max(sum(diff(bsxfun(@le,2*x',x(1:end-1)+x(2:end)))~=0))+1

```

Shorter version:

```
f=@(x)max(sum(diff(bsxfun(@lt,x',x))~=0))+1

```

# Octave (31)

In Octave `bsxfun` can be removed thanks to automatic broadcasting:

```
f=@(x)max(sum(diff(x'<x)~=0))+1

```
> 3 votes

# Answer
# K (ngn/k), 17 bytes

```
{|/+/'~~':'x>/:x}

```

Try it online!

Modeled after Zgarb's APL answer.

* `x>/:x` build matrix storing whether or not each value of x is larger than each other value of x
* `~~':'` for each "row", determine where the values change (i.e. `differ each`)
* `+/'` take the sum of each row
* `|/` take/return the maximum sum
> 3 votes

# Answer
# JavaScript (ES6) 80 ~~82~~

See comments - byte count does not include assign to F (that's still needed to test)

```
F=l=>Math.max(...l.map(v=>l.map(t=>(n+=t>u?v<t&v>=u:v>=t&v<u,u=t),n=1,u=l[0])&&n))

```

**Test** In FireFox/FireBug console

```
;[
 F([0, 1])
,F([2147483647, -2147483648])
,F([0, 1, -1])
,F([1, 0, -1])
,F([-1, 3, 1, -2, 5, 2, 3, 4])
,F([-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868, -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526, -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846, -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888, -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488, -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463, 676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202, 2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212, -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326, 1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157, 1072577364, -538901064])
,F([-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718, -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585])
]

```

*Output*

> \[2, 2, 3, 2, 6, 53, 2\]
> 2 votes

# Answer
# Python 2, 63 bytes

```
lambda x:max(sum(a-m^a-n<0for m,n in zip(x,x[1:]))for a in x)+1

```

Try it online!

I'm back 6 years in the future to golf the Python answers by Sp3000 and Jakube!

The improvement is shorten the core expression of `(a+.5-m)*(a+.5-n)<0` or `min(t)<a<=max(t)` with `t` for `m,n` to:

```
a-m^a-n<0

```

This is parsed as `(a-m)^(a-n)<0`. Due the how XOR acts on the Python's bit representations of negative numbers, two the XOR of two numbers is negative if and only if exactly one of them is negative. So, this expression is equivalent to `(a-m<0)^(a-n<0)` or `(a<m)^(a<n)`. This expresses that exactly one of `m,n` is smaller than `a` while the other one isn't, which is equivalent to `min(m,n)<a<=max(m,n)`.
> 2 votes

# Answer
# Jelly, 10 bytes

```
>þ`^ƝS$€Ṁ‘

```

Try it online!

## How it works

```
>þ`^ƝS$€Ṁ‘ - Main link. 1 argument        e.g.   [1, 0, -1]
>þ`        - Greater than outer product          [[0, 0, 0], [1, 0, 0], [1, 1, 0]]
      $€   - Over each sublist:           e.g.   [1, 1, 0]
    Ɲ      -   Over each overlapping pair e.g.   [1, 0]
   ^       -     Perform XOR                     1
     S     -   Take the sums                     [0, 1, 1]
        Ṁ  - Take the maximum                    1
         ‘ - Increment                           2

```
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
ε@Ôg}à

```

Try it online!

Explanation:

```
ε   }    # for each element of the input
 @       # is each element >= this one? (returns list of booleans)
  Ô      # connected uniquified
   g     # length
     à   # maximum

```
> 1 votes

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

```
a=>Math.max(...a.map(t=>a.map(u=>s+=(a[i++]-t-.5)*(u-t-.5)<0,s=i=1)|s))

```

Try it online!
> 0 votes

# Answer
# Add++, 27 bytes

```
D,w,@@,VbUG€<ÑBxs
L~,A€wM1+

```

Try it online!

Approach thanks to Zgarb for their APL answer

The key part of this challenge is implementing an outer product command. Unfortunately, Add++ doesn't have a builtin to do so, not does it have any way of defining functions that take other functions as arguments. However, we can still make a generalised outer product function nonetheless. As the only way for a function to be accessed inside another function is via referencing an existing function, user defined or builtin, we have to create a 'builtin' that references such a function.

A generalised "table" function would look something like this:

```
D,func,@@,+

D,iter,@@*, VbUG €{func}
D,table,@@, $ bRbU @ €{iter} B]

```

Try it online!

where `func` is a dyadic function that contains our operand. You can see faint similarities of this structure in the original submission, at the start of the **w** function, but here we want, primarily, a *monadic* outer product function - an outer product function that takes the same argument on both sides.

The general **table** function takes advantage of how the ach quick approaches dyadic functions. If the stack looks like

```
 [a b c d e]

```

when `€{func}` is encountered, the  pops `e`, binds that as the left argument to the dyad, and maps that partial function over `a, b, c, d`. However, the  quick maps over the entire stack, rather than over lists. So we need to flatten the arrays passed as arguments first.

The **table** function works overall like this

```
D,func,@@,+

D,iter,		; Define our helper function **iter**
		;   This takes an array as its left argument
		;   And a single integer as its right argument
	@@	; Dyadic arguments - take two arguments and push to the stack
	*,	; After execution, return the entire stack, rather then just the top element
		;
		; Example arguments:	[5 6 7 8] 1
		;
	VbUG	; Unpack the array;	[5 6 7 8 1]
		;
	€{func}	; Map **func** over the stack
		; As **func** is dyadic, this pops the right argument
		;   and binds that to a monadic **func**
		; This then maps the remaining elements, [5 6 7 8]
		;   over the monadic call of **func**, yielding [6 7 8 9]
		; Now, as the ***** flag was defined, we return the entire array
		;   rather than just the last element.
		; We'd achieve the same behaviour by removing the flag and appending **B]**

D,table,	; Define the main **table** function
		;   This takes two arrays as arguments
		;   Returns a single 2D array representing their outer product with **func**
	@@,	; Take the two arrays and push to the stack
		;
		; Example arguments:	[[1 2 3 4] [5 6 7 8]]
		;
	$	; Swap;		STACK = [[5 6 7 8] [1 2 3 4]]
	bR	; Reverse last;	STACK = [[5 6 7 8] [4 3 2 1]]
	bU	; Unpack;	STACK = [[5 6 7 8] 4 3 2 1]
	@	; Reverse;	STACK = [1 2 3 4 [5 6 7 8]]
		;
		; This allows us to place the stack so that each element of
		;   the first array is iterated over with the second array
		;
	€{iter}	; Map **iter**;	STACK = [[6 7 8 9] [7 8 9 10] [8 9 10 11] [9 10 11 12]]
		;
	B]	; Return the whole stack;

$table>?>?
O

```

However, we can shorten this by quite a lot due to the fact that we need our outer table to be *monadic*, and only needs to apply to the argument passed. The `A` command pushes each argument to the stack individually, so we don't need to mess around with any stack manipulation. In short, if our argument is the array `[a b c d]`, we need to make the stack into

```
[a b c d [a b c d]]

```

The top value is, of course, the argument.You may have noticed from the general example that `bU` is the **unpack** command i.e. it splats the top array to the stack. So to make the above configuration, we can use the code

```
L,bUA

```

Try it online!

However, this can be shortened by a byte. As an alias for `L,bU`, we can use the `~` flag, to splat the arguments to the stack beforehand, making our configuration example into

```
L~,A

```

Try it online!

which is the start of the second line in the program. Now we've implemented monadic outer product, we just need to implement the rest of the algorithm. Once retrieving the result of **table** with `<` (less than), and count the number of `[0 1]` and `[1 0]` pairs in each row. Finally, we take the maximum of these counts, and increment it.

The complete step for step walk through is

```
D,w,		; Define a function **w**
		;   This takes an array and an integer as arguments
		;   First, it produces the outer product with less than
		;   Then reduce overlapping pairs by XOR
		;   Finally, sum the rows
	@@,	; Take two arguments
		;
		; Example arguments:		[[0 1 2 3] 0]
		;
	VbUG€<	; Map **<** over the array;	STACK = [0 1 1 1]
	ÑBx	; Equals [1 0];		STACK = [1 0 0]
	s	; Sum;			STACK = [1]

L		; Define a lambda function
		;   This takes one argument, an array
	~,	;   Splat the array to the stack before doing anything
		;
		; Example argument:		[0 1 2 3]
		;
	A€w	; Map with **w**;		STACK = [1 1 1 0]
	M	; Maximum;		STACK = [1]
	1+	; Increment;		STACK = [2]

```
> 0 votes

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


title: Minimal Pairing

text:
# Question
Title: Minimal Pairing
Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.

Your mission, should you choose to accept it, will be to pair up members of the first list with members of the second, outputting a list of triples of the form `(i, j, n)` where `i` is an index into the first input list, `j` is an index into the second input list, and `n` is the number of members of group `i` from the first list who are paired up with a member of group `j` from the second list.

Every member of both lists should be paired up in this way.

In pseudocode, `∀i, sum(n for (i1, _, n) in output if i1 == i) == first_list[i]`, and `∀j, sum(n for (_, j1, n) in output if j1 == j) == second_list[j]`, `all(n > 0 and is_integer(n) for (_, _, n) in output)`, where `first_list` and `second_list` are the two input lists, and `i` and `j` range over valid indices into the respective inputs.

Your output list must have minimal length among all valid solutions. Zero-based and one-based indexing are both acceptable. Shortest answer wins.

### Example

Input: `[3, 4, 5] [5, 6, 1]`

Possible optimal output: `[(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)]`

```
   list 1    list 2     i  j  n
  [ 3 0 0 ] [ 0 3 0 ]  (0, 1, 3)
+ [ 0 3 0 ] [ 0 3 0 ]  (1, 1, 3)
+ [ 0 1 0 ] [ 0 0 1 ]  (1, 2, 1)
+ [ 0 0 5 ] [ 5 0 0 ]  (2, 0, 5)
---------------------
= [ 3 4 5 ] [ 5 6 1 ]

```

### Test cases

The test cases use zero-based indexing.

```
[3, 4, 5] [5, 6, 1]  ->  [(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)] (length 4 optimal)
[4, 3, 1, 5] [2, 1, 3, 7]  ->  [(1, 2, 3), (2, 1, 1), (0, 3, 4), (3, 3, 3), (3, 0, 2)] (length 5 optimal)
[1, 7, 5] [4, 5, 4]  ->  [(0, 0, 1), (1, 2, 4), (1, 0, 3), (2, 1, 5)] (length 4 optimal)
[4, 5, 5] [3, 7, 4]  ->  [(0, 2, 4), (1, 1, 5), (2, 0, 3), (2, 1, 2)] (length 4 optimal)
[4, 3] [3, 1, 3]  ->  [(0, 0, 3), (0, 1, 1), (1, 2, 3)] (length 3 optimal)
[4, 3, 2] [4, 5]  ->  [(0, 0, 4), (1, 1, 3), (2, 1, 2)] (length 3 optimal)
[] [] -> [] (length 0 optimal)

```

# Answer
> 4 votes
# Scala, ~~222..187~~ 180 bytes

*-7 bytes thanks to user!*

```
x=>y=>{var(a,b,r)=(x,y,Set[Any]())
while(a.sum>0){var?,m=a.max min b.max
var p,q= -1
while(p<0|q<0){if(p<0)p=a indexOf?
if(q<0)q=b indexOf?
? +=1}
a(p)-=m
b(q)-=m
r+=Seq(p,q,m)}
r}

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 137 bytes

```
a=>g=(b,k=O=0,o=[],n,c)=>O=O&&!O[k]||a.map((p,i)=>b.map((q,j)=>b[a[i]-=n=p<q?p:q,b[j]-=n,n&&g(b,k+1,[...o,[i,j,c=n]]),a[i]=p,j]=q))|c?O:o

```

Try it online!

### Commented

```
a =>                           // outer function taking the 1st list a[]
g = (                          // inner function taking:
  b,                           //   the 2nd list b[]
  k = O = 0,                   //   k = length of current solution, O = output
  o = [],                      //   o[] = current solution
  n,                           //   n is a local variable
  c                            //   c is a flag telling whether both lists are cleared
) =>                           //
  O =                          // update O:
    O &&                       //   abort if an output is already defined
    !O[k] ||                   //   and it's shorter than the current solution
    a.map((p, i) =>            //   otherwise, for each value p at position i in a[]:
      b.map((q, j) =>          //     for each value q at position j in b[]:
        b[                     //
          a[i] -=              //       subtract n from a[i]
            n = p < q ? p : q, //       where n = min(p, q)
          b[j] -= n,           //       subtract n from b[j]
          n && g(              //       if n > 0, do a recursive call:
            b,                 //         pass b[] unchanged
            k + 1,             //         increment k
            [ ...o,            //         update the solution o[]
              [i, j, c = n] ]  //         with the triplet [i, j, n]
                               //         and set the flag c
          ),                   //       end of recursive call
          a[i] = p,            //       restore a[i]
          j                    //
        ] = q                  //       restore b[j]
      )                        //     end of inner map()
    ) | c ?                    //   end of outer map(); if c is set:
      O                        //     leave O unchanged
    :                          //   else:
      o                        //     update O to o

```

---
Tags: code-golf, combinatorics, optimization
---


title: Silly Stock Market

text:
# Question
Title: Silly Stock Market
Given a string with a multiple people's investment data, find out how much profit/loss they recorded.

The string only contains capital and lowercase letters, like this:

```
AABaBbba

```

Each letter represents a person - a capital letter means buy, a lowercase letter means sell. The price of the stock they are investing in (CGLF) starts at $50. After someone buys, the price goes up 5%. After someone sells the price goes down 5%. You need to figure out how much money each person who participated made/lost.

## Notes:

* The string will always be valid, no selling without first buying. Also, everyone who buys a stock will sell it eventually.
* Your calculations should be accurate to at least 6 decimal places. However, final answers should be rounded to two decimals.

## Test Cases:

**Input:** `AABaBbba`

> * A: Buy - $50
> * A: Buy - $52.50
> * B: Buy - $55.125
> * a: Sell - $57.88125
> * B: Buy - $54.9871875
> * b: Sell - $57.736546875
> * b: Sell - $54.8497195313
> * a: Sell - $52.1072335547

* Person A profit: `57.88125+52.1072335547-50-52.50=`7.4884835547
* Person B profit: `57.736546875+54.8497195313-55.125-54.9871875=`2.4740789063

**Output:** `A:7.49,B:2.47` (order doesn't matter, separators not required)

---

**Input:** `DGdg`

> * D: Buy - $50
> * G: Buy - $52.50
> * d: Sell - $55.125
> * g: Sell - $52.36875

* Person D profit: `55.125-50=`5.125
* Person G profit: `52.36875-52.50=`-0.13125

**Output:** `D:5.13,G:-.13`

---

**Input:** `ADJdja`

> * A: Buy - $50
> * D: Buy - $52.50
> * J: Buy - $55.125
> * d: Sell - $57.88125
> * j: Sell - $54.9871875
> * a: Sell - $52.237828125

* Person A profit: `52.237828125-50=`2.237828125
* Person D profit: `57.88125-52.50=`5.38125
* Person J profit: `54.9871875-55.125=`-0.1378125

**Output:** `A:2.24,D:5.38,J:-.14`

# Answer
# Japt, ~~91~~ 84 bytes

```
A=[]J=50¡AhD=Xc %H(X<'_?[AgD ª0 -JJ*=1.05]:[AgD +JJ*=.95] g};A£X©[Y+I d X*L r /L]} f

```

Based on my JS answer. Try it online!
> 0 votes

# Answer
# APL (Dyalog Extended), ~~34~~ 32 bytes

```
⌊{⍺,2⍕+/-⍵}⌸××50×¯1×\⍤↓1,1+.05××

```

```
Monadic × in Dyalog extended for letters corresponds to the casing
¯1 1 ≡ ×'aA'

1+.05×× - 1 + 0.05 times the sign (either 1.05 or 0.95)
1,      - concat 1 to the front
¯1×\⍤↓  - cumulative product and drop the last element
50×     - multiply by 50
××50... - the sign times that
⌊{⍺,2⍕+/-⍵}⌸ - group (dyadic ⌸) by the lowercased input (⌊)
 {⍺,2⍕+/-⍵}  - return the left item (the person) concat their rounded total

```

-2 thanks to Adám

Try it online!
> 5 votes

# Answer
## Java, 277 bytes

```
class c{public static void main(String[]a){double[]m=new double[26];double s=50;for(byte b:a[0].getBytes()){if(b>=97){m[b-97]+=s;s*=.95;}else{m[b-65]-=s;s*=1.05;}}char g=65;for(double k:m){if(k!=0){System.out.println(g+String.format(java.util.Locale.ENGLISH,"%.2f",k));}g++;}}}

```

Ungolfed:

```
class c {
    public static void main(String[]a) {
        double[] m = new double[26];
        double s = 50;
        for(byte b : a[0].getBytes()) {
            if(b>=97) {
                m[b-97]+=s;
                s*=.95;
            } else {
                m[b-65]-=s;
                s*=1.05;
            }
        }
        char g=65;
        for(double k:m) {
            if(k!=0) {
                System.out.println(g+String.format(java.util.Locale.ENGLISH,"%.2f",k));
            }
            g++;
        }
    }
}

```
> 3 votes

# Answer
# JavaScript (ES7), ~~145~~ 142 bytes

I can't find a shorter way to round out the results...

```
x=>[for(c of(i=50,a={},x))(a[d=c.toUpperCase()]=a[d]||0,c<"["?(a[d]-=i,i*=1.05):(a[d]+=i,i*=.95))]&&Object.keys(a).map(k=>[k,a[k].toFixed(2)])

```

Fun fact: this would only be 101 bytes if not for the rounding requirement:

```
x=>[for(c of(i=50,a={},x))(a[d=c.toUpperCase()]=a[d]||0,c<"["?(a[d]-=i,i*=1.05):(a[d]+=i,i*=.95))]&&a

```
> 2 votes

# Answer
# Python 3, 116 bytes

```
P=50
M={}
for c in input():C=c.upper();u=c>C;u+=~-u;M[C]=M.get(C,0)+P*u;P*=1-u*.05
for k in M:print(k,round(M[k],2))

```

### Ungolfed

```
price = 50
profits = {}
for char in input():
    upper = char.upper()
    direction = 2 * (char > upper) - 1
    profits[upper] = profits.get(upper, 0) + price * direction
    price *= 1 - direction * .05
for key in profits:
    print(key, round(profits[key], 2))

```
> 2 votes

# Answer
# ARM Thumb-2 (VFP + `printf`, softfp ABI), ~~109~~ 104 bytes

Uses the softfp ABI (default on Android). It won't work on `armhf` Linux. `f7ff fffe` is a 4 byte linker placeholder for `printf`.

Both of these examples must be placed at an address that is **not** a multiple of 4 (but even), and must be in a W+X section because we modify an inline `printf` string in place.

```
b5f8 2100 2234 3a01 b402 d8fc f2c4 0249
ec42 1b10 ed9f 1b11 f810 2b01 b192 3a61
bf48 3220 eb0d 02c2 ed92 5b00 bf47 ee35
5b40 ee00 0b01 ee35 5b00 ee00 0b41 ed82
5b00 e7e9 2641 bc0c b11b a005 7006 f7ff
fffe 3601 2e5a ddf6 bdf8 999a 9999 9999
3fa9 2558 322e 0066

```

Assembly:

```
        .syntax unified
        .arch armv6t2
        // We need VFPv2 for this.
        .fpu vfpv2
        // We modify an inline string in place, so we need W+X.
        .section ".writeable_text","awx",%progbits
        .thumb
        .globl silly_stocks
        .thumb_func
        // Must NOT be 4 byte aligned.
        // .align 4
        // nop

        // void silly_stocks(const char *input);
        // Follows AAPCS convention.
        // input is a null-terminated string in r0.
silly_stocks:
        push          {r3-r7, lr}
        // double buf[26] = {0}
        movs          r1, #0
        movs          r2, #26*2
.Lclear_loop:
        subs          r2, #1
        push          {r1}
        bhi           .Lclear_loop
.Lclear_loop_end:
        // note: r1 and r2 are zero at this point
        // r1:r2 = 0x4049000000000000 = 50.0 double
        movt           r2, #0x4049
        vmov           d0, r1, r2
        vldr           d1, .Lfloat_pool
.Lprocess_loop:
        // Loop until the null terminator.
        // while (r2 = *input++)
        ldrb          r2, [r0], #1
        cbz           r2, .Lprocess_loop_end
        // tolower(r2) - 'a'
        //
        // Specifically, we subtract 'a', and if the char was uppercase,
        // it would be negative, triggering the N flag, which is why we
        // check the mi condition in the following IT blocks.
        subs          r2, #'a'
        it            mi
        // if (isupper(r2))
          addmi       r2, #'a' - 'A'

        // Yucky. We can't use proper offsetting with VFP and we need to
        // keep the flags for the IT block.
        add.w         r2, sp, r2, lsl #3
        // Behold, the beautiful syntax of VFP/NEON.
        // Combine it with a an IT block and you get a 10 letter mnemonic. OwO
        vldr.64       d5, [r2]
        ittee         mi
        // if (isupper(r2)) {    // Buy
          vsubmi.f64  d5, d5, d0 //   profit[i]   -= d0
          vmlami.f64  d0, d0, d1 //   stock_price += stock_price * 0.05
        // } else {              // Sell
          vaddpl.f64  d5, d5, d0 //   profit[i]   += stock_price
          vmlspl.f64  d0, d0, d1 //   stock_price -= stock_price * 0.05
        // } endif
        vstr.64       d5, [r2]
        b             .Lprocess_loop
.Lprocess_loop_end:

        movs          r6, #'A'
.Lprint_loop:
        // Pop the double into r2 and r3. We are using the softfp abi, so
        // doubles are passed in integer registers.
        pop           {r2, r3}
        // Only check if the most signicant half of the double is zero.
        // Any non-zero double that is 0x00000000xxxxxxxx is denormal.
        cbz           r3, .Lprint_loop_skip
        // Set up an AEABI call to printf.
        adr           r0, .Lprintf_str
        // Instead of %c, store the char directly (that's why we need W+X)
        strb          r6, [r0]
        bl            printf
.Lprint_loop_skip:
        // Loop from A-Z.
        adds          r6, #1
        cmp           r6, #'Z'
        ble           .Lprint_loop
        pop           {r3-r7, pc}
        // At least for the softfp ABI, doubles are smaller than floats.
        // This is because printf takes doubles, not floats, and we need
        // to pass them in a register pair.
        // So we would need something like this, which is 12 bytes.
        //  vpop         {d0}
        //  vcvt.f64.f32 d0, s0
        //  vmov         r2, r3, d0
        .align 2
.Lfloat_pool:
        .double       0.05
.Lprintf_str:
        // Our printf string. We modify X directly.
        .asciz        "X%.2f"

        .section ".testsuite_unscored","ax",%progbits
.macro $TEST str
        adr           r0, 1f
        bl            puts
        adr           r0, 1f
        bl            silly_stocks
        movs          r0, #'\n'
        bl            putchar
        b             2f
        .align 2
1:
        .asciz        "\str"
.align 2
2:
.endm

        .align 2
        .globl main
        .thumb_func
main:
        push          {r4, lr}
        $TEST         "AABaBbba"
        $TEST         "DGdg"
        $TEST         "ADJdja"
        pop           {r4, pc}

```

Decided to take a shot at VFP code in ARM assembly instead of doing something easy (and basically identical to the Java entry) like C or C++.

One of the things I realized the hard way was that ARM actually needs the stack to be 8 byte aligned, or else subtle bugs will occur. Two hours of debugging I am NEVER getting back.

Oddly enough, using doubles is smaller than floats, despite the larger literal pool. This is because the C calling convention mandates that `float`s be promoted to `double` in variadic functions, so we would have to convert to `double` anyways, and that is larger than the 8 bytes for the larger pool.

Output isn't pretty. But the question says "**separators not required**" so I took that in the most literal sense.

```
AABaBbba
A7.49B2.47
DGdg
D5.12G-0.13
ADJdja
A2.24D5.38J-0.14

```

But aside from the `5.12` which is the same rounding error that was mentioned in Python, the results are correct.

# ARM Thumb-2 (VFP + `printf`, softfp ABI, very imprecise), ~~99~~ 96 bytes

This version uses 32-bit x 16-bit fixed point arithmetic.

It lacks the required 6 digits of precision, but for the test cases it products the same results. Interpret it as you wish.

Must be loaded at an address that is not a multiple of 4 for constant pool alignment.

Machine code:

```
b5f8 2100 2534 3d01 b402 d8fc f2c0 0132
4d11 f810 2b01 b172 3a61 bf48 3220 f85d
3032 fb51 f605 bf47 1a5b 4431 440b 1b89
f84d 3032 e7ed 2641 ecbd 0b02 eeba 0bc8
ec53 2b10 b11b a004 7006 f7ff fffe 3601
2e5a ddf1 bdf8 cccc 0ccc 2558 322e 0066

```

Assembly:

```
        .syntax unified
        .arch armv6t2
        // We need VFPv2 for this.
        .fpu vfpv2
        // We modify an inline string in place, so we need W+X.
        .section ".writeable_text_fixed","awx",%progbits
        .thumb
        .globl silly_stocks_fixed
        .thumb_func

        // Must not be 4 byte aligned.
        // .align 4
        // nop
        // void silly_stocks_fixed(const char *input);
        // Follows AAPCS convention.
        // input is a null-terminated string in r0.
silly_stocks_fixed:
        push          {r3-r7, lr}
        // We use double the width because we need to keep alignment.
        // int64_t buf[26] = {0}
        movs          r1, #0
        movs          r5, #26*2
.Lclear_loop_fixed:
        subs          r5, #1
        push          {r1}
        bhi           .Lclear_loop_fixed
.Lclear_loop_end_fixed:
        // Load our float constants from the pool.
        movt          r1, #0x32       // 0x00320000 = 50.0 in 16-bit fixed point
        ldr           r5, .L.05.fix32 // 0x0ccccccc = 0.05 in 32-bit fixed point
.Lprocess_loop_fixed:
        // Loop until the null terminator.
        // while (r2 = *input++)
        ldrb          r2, [r0], #1
        cbz           r2, .Lprocess_loop_end_fixed
        // tolower(r2) - 'a'
        //
        // Specifically, we subtract 'a', and if the char was uppercase,
        // it would be negative, triggering the N flag, which is why we
        // check the mi condition in the following IT blocks.
        subs          r2, #'a'
        it            mi
        // if (isupper(r2))
          addmi       r2, #'a' - 'A'

        ldr           r3, [sp, r2, lsl #3]
        // fixed point multiply:
        // x<fixA> = (y<fixB> * z<fixC>) >> (B + C - A)
        // tmp<fix16> = (stock_price<fix16> * 0.05<fix32>) >> 32
        smmul         r6, r1, r5  // r6 = stock_price * 0.05
        ittee         mi
        // if (isupper(r2)) {     // Buy
          submi       r3, r1      //   profit[i]   -= stock_price
          addmi       r1, r6      //   stock_price += stock_price * 0.05
        // } else {               // Sell
          addpl       r3, r1      //   profit[i]   += stock_price
          subpl       r1, r6      //   stock_price -= stock_price * 0.05
        // } endif
        str           r3, [sp, r2, lsl #3]
        b             .Lprocess_loop_fixed
.Lprocess_loop_end_fixed:
        movs          r6, #'A'
.Lprint_loop_fixed:
        // Pop the result into d0 (also cleaning the stack)
        vpop          {d0}
        // Convert from fix16 to double
        vcvt.f64.s32  d0, d0, #16
        // Move the double result into r2 and r3. This is for the softfp ABI
        // which passes floating point values in registers.
        vmov          r2, r3, d0
        // Only check if the most signicant half of the double is zero.
        // Any non-zero double that is 0x00000000xxxxxxxx is denormal.
        cbz           r3, .Lprint_loop_skip_fixed
        // Set up an AEABI call to printf.
        adr           r0, .Lprintf_str_fixed
        // Instead of %c, store the char directly (that's why we need W+X)
        strb          r6, [r0]
        bl            printf
.Lprint_loop_skip_fixed:
        // Loop from A-Z.
        adds          r6, #1
        cmp           r6, #'Z'
        ble           .Lprint_loop_fixed
        pop           {r3-r7, pc}
        // 0.05 in fix32.
.L.05.fix32:
        .word         0x0ccccccc
        // Our printf string. We replace the X when we use it.
.Lprintf_str_fixed:
        .asciz        "X%.2f"

        .section ".testsuite_unscored","ax",%progbits
.macro $TEST str
        adr           r0, 1f
        bl            puts
        adr           r0, 1f
        bl            silly_stocks_fixed
        movs          r0, #'\n'
        bl            putchar
        b             2f
        .align 2
1:
        .asciz        "\str"
.align 2
2:
.endm

        .align 2
        .globl main
        .thumb_func
main:
        push          {r4, lr}
        $TEST         "AABaBbba"
        $TEST         "DGdg"
        $TEST         "ADJdja"
        pop           {r4, pc}

```

For the reference, here is the results for float vs fixed point at 6 digits of precision.

```
AABaBbba
float: A:7.488484,B:2.474079,
fixed: A:7.488434,B:2.474060,
DGdg
float: D:5.125000,G:-0.131250,
fixed: D:5.124969,G:-0.131256,
ADJdja
float: A:2.237828,D:5.381250,J:-0.137812,
fixed: A:2.237808,D:5.381226,J:-0.137817,

```
> 2 votes

# Answer
# Perl 5 `-MList::Util=pairmap -F`, 80 bytes

```
$p=50;map{$k{uc$_}+=$q=95>ord?-$p:$p;$p-=$q/20}@F;pairmap{printf"$a:%.2f ",$b}%k

```

Try it online!
> 1 votes

# Answer
# Javascript (ES6, Node.js), 136 bytes

## Source

```
s=>(m=50,a={},[...s].map(p=>(u=p.toUpperCase(),n=p==u?1:-1,a[u]=(a[u]||0)-m*n,m*=1+n/20)),Object.keys(a).map(k=>a[k]=a[k].toFixed(2)),a)

```

## Explanation

```
f=s=>( // (s)tring
    m=50, // stock value (m)oney
    a={}, // (a)ll people
    [...s].map(
        p=>(
            u=p.toUpperCase(), // (u)ppercase: used to group buys and sells for each person
            n=p==u?1:-1, // sig(n): 1 for buy, -1 for sell
            a[u]=(a[u]||0)-m*n, // adjust balance with stock value and sign
            m*=1+n/20 // adjust stock value
        )
    ),
    Object.keys(a).map(k=>a[k]=a[k].toFixed(2)), // round profits
    a // return profits
)

```

## Proof

```
f=s=>(m=50,a={},[...s].map(p=>(u=p.toUpperCase(),n=p==u?1:-1,a[u]=(a[u]||0)-m*n,m*=1+n/20)),Object.keys(a).map(k=>a[k]=a[k].toFixed(2)),a)
const TESTS = [
    ['AABaBbba',{A:'7.49',B:'2.47'}],
    ['DGdg',{D:'5.13',G:'-0.13'}],
    ['ADJdja',{A:'2.24',D:'5.38',J:'-0.14'}]
]

TESTS.forEach(([input,expected])=>{
    console.log(input);
    console.log(expected);
    console.log(f(input))
});
```
> 1 votes

# Answer
# , 64 bytes

```
tolower(~.@[,.(0j2":_50*+/)/.)](]*1*/\@}:@,1+0.05*])_1+2*91>3&u:

```

Try it online!
> 0 votes

---
Tags: code-golf
---


title: Is my triangle on the lattice?

text:
# Question
Title: Is my triangle on the lattice?
Write a program or function which takes three positive integers \\$a, b, c\\$ and returns/outputs one value if there is, and a different value if there isn't, a triangle on the square lattice, whose sides' lengths are \\$\sqrt{a}, \sqrt{b}, \sqrt{c}\\$. By "on the square lattice" I mean that its vertices are in the \\$xy\\$ plane, and their \\$x\\$ and \\$y\\$-coordinates are all integers

This is so the shortest code in bytes wins.

Test cases:

* 16 9 25: true (3-4-5 triangle)
* 8 1 5: true (e.g. (0,0), (1,0), (2,2))
* 5 10 13: true (e.g. (0,1), (1,3), (3,0); sides needn't be on grid lines)
* 10 2 1: false (not a triangle: long side is too long for short sides to meet)
* 4 1 9: false (not a triangle: three points in a straight line)
* 3 2 1: false (triangle is on the cubic lattice but not the square lattice)
* 3 7 1: false (triangle is on the hex lattice but not the square lattice)
* 25 25 25: false (no such triangle on this lattice)
* 5 5 4: true (isosceles is OK)
* 15 15 12: false (OK shape, wrong size)
* 25 25 20: true (OK shape and size; common prime factor 5 is OK)
* 4 4 5: false (Bubbler's suggestion)
* 17 17 18: true (acute isosceles with equal short sides OK)
* 26 37 41: true (acute scalene is OK)

These same test cases, but just the numbers. First, those that should return true:

```
16 9 25
8 1 5
5 10 13
5 5 4
25 25 20
17 17 18
26 37 41

```

Then those that should return false:

```
10 2 1
4 1 9
3 2 1
3 7 1
25 25 25
15 15 12

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), ~~76~~ ~~69~~ 65 bytes

```
{}=!=Solve[Norm/@{a={w,x},b={y,z},a+b}^2==#&&w z!=x y,,Integers]&

```

Try it online!

If no solution exists, `Solve` returns an empty list `{}`; otherwise, since the variables to solve for are not given, it remains unevaluated. From there it's just a matter of collapsing unevaluated `Solve`s into a single form.

# Answer
> 5 votes
# Python3, ~~171~~ ~~151~~ ~~142~~ ~~137~~ 133 bytes

* 151 =\> 142 Thanks to @user
* 142 =\> 137 and fixed correctness thanks to @Bubbler
* 137 =\> 133 thanks to @xnor and @Bubbler

```
lambda l:l in[[d*d+D*D,e*e+E*E,(d-e)**2+(D-E)**2]for d,e,D,E in product(*[range(-max(l),max(l))]*4)if d*E-e*D]
from itertools import*

```

Tests here:

```
TESTS = [
    (16,9,25,True),
    (8,1,5,True),
    (5,10,13,True),
    (10,2,1,False),
    (4,1,9,False),
    (3,2,1,False),
    (3,7,1,False),
    (25,25,25,False),
    (5,5,4,True),
    (15,15,12,False),
    (25,25,20,True),
    (4,4,5,False)
]

for x,y,z,true in TESTS:
    print('testing',x,y,z)
    computed = f([x,y,z])
    assert computed == true

```

Try it online!

# Answer
> 5 votes
# 05AB1E, ~~26~~ 25 bytes

```
ZD(Ÿ4ãʒÁ2ôPÆĀ}ειDøÆªnOQ}à

```

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

Very slow. The larger the maximum value in the input-list, the slower it is.

Try it online or verify a few of the smaller test cases.

**Explanation:**

```
Z          # Push the maximum of the (implicit) input-list
 D(        # Duplicate this maximum, and negate the copy
   Ÿ       # Pop both, and push a list in the range [max,-max]
    4ã     # Create all possible quartets of this list with the cartesian product
ʒ          # Filter this list of quartets [a,b,c,d] by:
 Á         #  Rotate it once towards the right: [d,a,b,c]
  2ô       #  Split it into parts of size 2: [[d,a],[b,c]]
    P      #  Take the product of each inner pair: [d*a,b*c]
     Æ     #  Reduce the list by subtracting: d*a-b*c
      Ā    #  Check that this is NOT 0 with a Python-style truthify
}ε         # After the filter: map each remaining quartet to:
  ι        #  Uninterleave the list: [[a,c],[b,d]]
   D       #  Duplicate it
    ø      #  Zip/transpose the copy, swapping rows/columns: [[a,b],[c,d]]
     Æ     #  Reduce each by subtracting: [a-b,c-d]
      ª    #  Add this pair to the earlier list: [[a,c],[b,d],[a-b,c-d]]
       n   #  Square each: [[a²,c²],[b²,d²],[(a-b)²,(c-d)²]
        O  #  Take the sum of each inner pair: [a²+c²,b²+d²,(a-b)²+(c-d)²]
         Q #  Check that this list is equal to the (implicit) input-list
 }à        # After the map: check if any were truthy by taking the maximum
           # (after which the result is output implicitly)

```

# Answer
> 5 votes
# 05AB1E, ~~23~~ 22 bytes

-1 thanks to @ovs

```
ZÝã3ãεDÁ-nOQ}àIt{R`+‹*

```

Try it online!

very very slow.

Explanation:

```
Z maximum
Ý push the range [0, maximum]
ã cartesien power which defaults to 2, returning all pairs
3ã cartesien power with 3, returning all possible traingles in the box (0,0,maximum,maximum)
ε map
 D duplicate
 Á rotate left 1
 - subtract # the offset between the three points
 n square
 O sum      # the side lengths of the triangle
 Q check if equals to the implicit input, returning 0/1
}
à maximum  # 1 if one of the cases was 1, 0 otherwise
I push the input
t square root
{ sort         # increasing order, e.g. [1,2,3]
R reverse      # e.g. [3, 2, 1]
` dump         # dump the array to stack e.g. 3, 2, 1
+ addition     # e.g. 3, 3
‹ is less than
* multiply, works as AND

```

# Answer
> 4 votes
# C (gcc), ~~281~~ ~~244~~ ~~225~~ ~~215~~ ~~192~~ 179 bytes

-14 thanks to @AZTECCO
-9 thanks to @ceilingcat

```
#define s(x,y)x>y?x^=y^=x^=y:0;
#define f(x,y)for(x=~b;x++<b;)for(y=~b;y++<b;)if(x*x+y*y==
r,i,j,k,l;t(a,b,c){r=0;s(a,c)s(b,c)s(a,b)f(i,j)a)f(k,l)b)r|=j*k&&c-a-b==i*k+j*l<<1;r=r;}

```

Try it online!

# Answer
> 3 votes
# Charcoal, ~~90~~ ~~79~~ ~~73~~ 71 bytes

```
≔⌈θη≔⁻Σθ⁺η⌊θζ≔…·±ζζεＦεＦε¿⁼⌊θ⁺Ｘι²Ｘκ²ＦεＦε¿⁼ζ⁺Ｘλ²Ｘμ²¿⁻×ιμ×κλＰ⁼η⁺Ｘ⁺ιλ²Ｘ⁺κμ²

```

Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. `-` if there is a solution, nothing if not. Edit: Saved 11 bytes by explicitly ranging one coordinate over negative values instead of testing both of its signs. Saved 6 bytes by using a colinearity test instead of a triangle test. Saved 2 bytes by inlining a variable. Made all variables range over negative values to fix the case where the three sides point in different quadrants, fortunately without costing any more bytes. Explanation: Uses brute force to find a solution.

```
≔⌈θη≔⁻Σθ⁺η⌊θζ≔…·±ζζε

```

Get the maximum and middle squared lengths. Call these \\$ f \\$ and \\$ e \\$. Create a range from \\$ -e \\$ to \\$ e \\$.

```
ＦεＦε¿⁼⌊θ⁺Ｘι²Ｘκ²

```

Find integers \\$ -e \le g \le e \\$ and \\$ -e \le h \le e \\$ such that \\$ d = g^2 + h^2 \\$ where \\$ d \\$ is the minimum squared length.

```
ＦεＦε¿⁼ζ⁺Ｘλ²Ｘμ²

```

Find integers \\$ -e \le i \le e \\$ and \\$ -e \le j \le e \\$ such that \\$ e = i^2 + j^2 \\$.

```
¿⁻×ιμ×κλ

```

If the two sides are not colinear, ...

```
Ｐ⁼η⁺Ｘ⁺ιλ²Ｘ⁺κμ²

```

... check whether \\$ f = (g + i)^2 + (h + j)^2 \\$.

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

Expects three distinct arguments. Returns either `0` or a non-zero integer.

```
(a,b,c)=>(F=(C,m=M=a|b|c)=>m+M&&C(m)|F(C,m-1))(w=>F(x=>F(y=>F(z=>a-w*w-x*x|b-y*y-z*z|c-a-b^w*y+x*z<<1?0:x*y-w*z))))

```

Try it online!

### How?

This is similar to other answers, but the main test has been modified some more to save a few bytes (at least in JS). Besides, we use `a|b|c` instead of `Math.max(a,b,c)`. This is \\$2\cdot\max(a,b,c)-1\\$ in the worst case.

Given \\$(w,x,y,z)\\$, we want to know if we have:

$$w^2+x^2=a\tag{1}$$ $$y^2+z^2=b\tag{2}$$ $$(x+z)^2+(w+y)^2=c\tag{3}$$

\\$(3)\\$ is turned into:

$$x^2+z^2+2xz+w^2+y^2+2wy=c$$

Provided that \\$(1)\\$ and \\$(2)\\$ are true, this becomes:

$$a+b+2(xz+wy)=c$$

or:

$$c-a-b=2(xz+wy)$$

Hence the JavaScript expression:

```
c-a-b^w*y+x*z<<1

```

# Answer
> 1 votes
# JavaScript (Node.js), 136 bytes

```
(p,q,r)=>(g=(n,t,x=0,y=(n-x*x)**.5)=>y%1==0&&t(x,y)|t(x,-y)||1/y&&g(n,t,x<0?-x:~x))(p,(a,b)=>g(q,(c,d)=>(a+c)**2+(b+d)**2==r&&a*d!=b*c))

```

Try it online!

---
Tags: code-golf, decision-problem, geometry
---


title: X+Y=Z - but in which base?

text:
# Question
Title: X+Y=Z - but in which base?
# The Challenge

Given 3 numbers `X`, `Y` and `Z` in base `B`, find a `B`ase in which the addition of `X` and `Y` yields `Z`. The inputs `x = 20`, `Y = 12` and `Z = 32` could yield `5` because `20 + 12 = 32` in base 5.

* You may assume that there will always be a base in which the addition is correct (there are cases where no base exists, thanks to @MasonWheeler and @Not that Charles for some examples of that).
* The lowest possible base is 1. You may use 1s or 0s as the digits in unary, but you may not mix those.

# I/O

* The digits of the input numbers will be non-negative integers.
* You may assume that the input numbers contain leading zeros, so the have a specific (or all the same) length.
* You may take the numbers in the most convenient format, as long as it's not preprocessed. This includes the overall format of the three input numbers and the format of the digits of each of those numbers. Please make it clear which format you use.
* If there are multiple possible bases, you can output all or just one of them.
* You may assume that the base and the input numbers will be within the numerical limits of your language.

# Rules

# Test cases

Input format here is a list of integers to represent each number. The three lists are separated by commas.
Note that there are sometimes multiple bases possible. Only one (random) solution is outputted here.

```
[12, 103],[4, 101],[16, 204] -> 349
[4, 21, 25],[5, 1, 20],[9, 23, 17] -> 28
[16, 11],[25, 94],[41, 105] -> 147
[2, 140],[21, 183],[24, 100] -> 223
[8, 157],[1, 28],[9, 185] -> 227
[2, 158],[88],[3, 12] -> 234
[8, 199],[1, 34],[9, 233] -> 408
[3, 247],[7, 438],[11, 221] -> 464
[3, 122],[3, 2],[6, 124] -> 480
[6, 328],[3, 31],[9, 359] -> 465
[2, 1, 0, 0, 0, 0],[1, 2, 0, 0, 1, 0, 1, 0],[1, 2, 2, 1, 1, 0, 1, 0] -> 3
[16, 105],[16, 120],[33, 84] -> 141
[15, 60],[9, 30],[24, 90] -> 268
[2, 0],[1, 2],[3, 2] -> 5
[1, 3, 3, 7],[1, 2, 3],[1, 4, 6, 0] -> 10
[0],[1, 12, 8],[1, 12, 8] -> 16
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1],[1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1],[1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0] -> 2
[1],[1],[1,1] -> 1

```

You can generate additional test cases with this Pyth program. Enter a base on the first line and the decimal values for `X` and `Y` on the following two lines.
Also you can use this Pyth program to create multiple test cases at once by using random values. Just enter the desired amount of test cases in the input.

**Happy Coding!**

# Answer
# Jelly, ~~16~~ ~~11~~ 7 bytes

```
_/N,‘FṀ

```

This approach is heavily based on @beaker's Octave answer.

Input format is **Z, Y, X**, with little-endian digit order, using the digit **0** for unary.

Try it online! or run all test cases.

### How it works

Rather than incrementally testing potential bases, this solves the polynomial that corresponds to the array **P := X + Y - Z**. This returns either the largest coefficient of **P ≠ 0** – which has to be a root, since there is at least one valid base – or the highest digit of **X**, **Y** and **Z**, incremented by **1**.

```
_/N,‘FṀ  Main link. Argument: [Z, Y, X]

_/       Reduce by subtraction; yield Z - X - Y.
         This works since Z must have at least as many digits as X and Y.
  N      Negate to yield X + Y - Z.
    ‘    Yield [Z, Y, X], with all digits increments by 1.
   ,     Pair the results to the left and to the right.
     F   Flatten the resulting, nested list.
      Ṁ  Compute the maximum.

```
> 13 votes

# Answer
# Pyth, 13 bytes

```
f!-FiRTQheSsQ

```

Expects Z, followed by X and Y.

Test suite

Essentially, we test every possible base, starting at one more than the largest digit. The test is that we convert each number to the base in question, then fold subtraction over the numbers, and logically negate the result.
> 11 votes

# Answer
# Octave, ~~67~~ ~~75~~ ~~38~~ 32 bytes

Because "loop over ALL the things" is too much work.

```
@(x,y,z)max([m=max(x+y-z) z])+~m

```

Requires 0 padding to make the input arrays the same size, e.g.:

```
[2, 158],[88],[3, 12]
becomes
[2, 158],[0, 88],[3, 12]

```

Since `0` is used for padding, `1` is used as the token for unary.

(Thanks to @DenkerAffe for clarification in the question.)

Sample run on ideone.

---

**Short Explanation:**

Take a case involving no carries:

```
   [ 8, 199]
 + [ 1,  34]
 -------------
     9, 233
 - [ 9, 233]
 -------------
     0,   0 --- no carries

```

In this case there are no restrictions on base as long as it's greater than any "digit". Simply take the max element of `z` (as `z >= x,y`) and add 1 (or any positive integer).

In the case of a carry-out (with no carry-in), we've exceeded the base in one of the columns and the difference between `x+y` and `z` is the base:

```
   [ 2, 140]
 + [21, 183]
--------------
    23, 323
 - [24, 100]
 -------------
    -1  223
     ^   ^------ base
     |---------- carry in

```

If the second column's sum also exceeded the base, requiring a carry-out as well as the carry-in, its value would be `base+(-1)`. We will have had a column somewhere to the right with a carry-out and no carry-in that has the correct (greater) base value.
> 10 votes

# Answer
## Haskell, ~~90~~ 73 bytes

```
f l=[b|b<-[1..],all(<b)$id=<<l,[x,y,z]<-[foldl((+).(b*))0<$>l],x+y==z]!!0

```

Usage example: `f [[3, 247],[7, 438],[11, 221]]` -\> `464`.

Simply try all bases `b` (where `b` is greater than the maximum of the digits). Pick the first one where `x+y==z`.

Edit: @xnor saved many bytes by primarily getting rid of the `import Data.Digits`.
> 9 votes

# Answer
# MATL, 20 bytes

```
`GY:@XJZQ2:"wJZQ-]]J

```

Input is in the format (note outer curly braces):

```
{[4, 21, 25],[5, 1, 20],[9, 23, 17]}

```

This works in current version (15.0.0).

**Try it online!**

### Explanation

```
`        % do...while index
  G      %   push input. First time pushed nothing but asks for input implicitly
  Y:     %   unpack the cell array, pushing the three numeric arrays
  @      %   loop index: candidate base
  XJ     %   copy into clipboard J
  ZQ     %   evaluate polynomial: interpret third array in that base
  2:"    %   for loop: do this twice (subtract the other numbers from the third)
    w    %     swap, to process another array
    J    %     push base
    ZQ   %     evaluate polynomial: interpret array in that base
    -    %     subtract
  ]      %   end for loop. A result 0 indicates a solution has been found
]        % end do....while loop. Exit if top of stack is 0
J        % push found base. Implicitly display

```
> 8 votes

# Answer
# MATL, ~~13~~ 12 bytes

```
--X>t~1G+hX>

```

Translation of my Octave answer into MATL. (My first MATL answer!)

* Input order is `Z, X, Y` (or `Z, Y, X` if you prefer, I'm easy)
* Input arrays are zero-padded to equal lengths
* Takes unattractives as 1

Try it online!

### Explanation

```
--X>t~1G+hX>

--            % M = Z - X - Y
  X>          % P = max(M)
    t~        % Duplicate and negate
      1G      % Push 1st argument (Z)
        +     % ~P + Z
         h    % Concatenate [P (~P + Z)]
          X>  % Return max

```
> 8 votes

# Answer
# APL (Dyalog Unicode), ~~28~~ 27 bytes (SBCS)

Saved 1 byte thanks to @Adám

```
{⍺←1+⌈/∊⍵⋄0=-/⍺⊥⍵:⍺⋄⍵∇⍨⍺+1}

```

Try it online!

Takes a matrix with columns `x z y`, with all of them padded with zeroes to have the same number of digits.

Explanation:

<pre><code>{
⍺←1+⌈/∊⍵                 ⍝ First base
      ∊⍵                ⍝ Flatten the input into a single vector of digits
     ⌈/                  ⍝ Maximum digit (reduce with max)
  1+                    ⍝Add one to that to get the lowest possible base

0=-/⍺⊥⍵                ⍝If this base works
 :⍺                     ⍝Return it
    ⍺⊥⍵                ⍝Convert to base ⍺
  -/                    ⍝Reduce with subtraction (x - (z - y)) = x + y - z
0=                      ⍝Check if it's 0 (the equation works)

⍵∇⍨⍺+1                  ⍝Otherwise, call itself (∇) with the next base
}
```
</code></pre>
> 2 votes

# Answer
# 05AB1E (legacy), 6 bytes

```
ζÆ(I>M

```

Port of *@Dennis*'s Jelly answer, so make sure to upvote him as well! The I/O is also in the same format, except with the input wrapped inside a list instead of three loose inputs: \\$\[Z,Y,X\]\\$, with little-endian digit order, using the digit \\$0\\$ for unary.

Try it online or verify all test cases.

The new 05AB1E version would require an additional leading `0` to overwrite the default space-filler of `ζ`. In the legacy 05AB1E version built in Python, the spaces are counted as 0 when we reduce by subtracting with `Æ`, though. Which would have given an error in the new version, which is built in Elixir.

**Explanation:**

```
        #  i.e. input = [[12,3],[88],[158,2]]
ζ       # Zip/transpose the (implicit) input-matrix, swapping rows/columns,
        # using a space filler by default if the rows doesn't have matching lengths
        #  STACK: [[12,88,158],[3," ",2]]
 Æ      # Reduce each inner-most list by subtracting, counting the spaces as 0
        #  STACK: [-234,1]
  (     # Negate each
        #  STACK: [234,-1]
   I>   # Push the input again, and increase each value by 1
        #  STACK: [234,-1],[[13,4],[89],[159,3]]
     M  # Push the largest value on the stack, which also looks inside (nested) lists
        #  STACK: [234,-1],[[13,4],[89],[159,3]],234
        # (after which this top value is output implicitly as result)

```
> 1 votes

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