title: Reachable numbers

text:
# Question
Title: Reachable numbers
# Definitions

* **Euler Phi Function** (AKA **totient function**): a function which takes in a positive number and returns the number of positive numbers less than the given number which are co-prime with given number. It is denoted as `φ(n)`.
* **Reachable number**: if there exists a positive integer `x` such that `φ(x) == n`, then `n` is **reachable**.

# Task

Write a function/program to determine if a given positive integer is reachable.

# Input

A positive number, in any reasonable format. One can assume that the number is within the capability of the language. Unary input is accepted.

# Output

Two consistent values, one for reachable numbers, and the other for unreachable numbers. The two values can be anything, as long as they are consistent.

# Testcases

The reachable numbers bellow `100` are:

> 1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96

(A002202 on OEIS)

# Rules

Standard loopholes apply.

# Winning criterion

This is . Submission with lowest byte-count wins.

# References

# Answer
# Jelly, ~~7~~ 6 bytes

```
²RÆṪe@

```

Not exactly fast. Returns **1** or **0**.

Try it online!

### How it works

```
²RÆṪe@  Main link. Argument: n

²       Square; yield n².
 R      Range; yield [1, ..., n²].
  ÆṪ    Compute the totient of each integer in the range.
    e@  Exists swap; test if n occurs in the generated array.

```
> 6 votes

# Answer
# Mathematica, 28 bytes

```
EulerPhi@Range[#^2]~FreeQ~#&

```

Like Dennis's Jelly answer, we compute the φ-values of all the numbers up to the square of the input and see if the input appears therein. Returns `False` if the input is reachable and `True` if it's not. Yep, that's confusing. But `FreeQ` is a byte shorter than `MatchQ`, and hey, the spec said any two consistent values \>:)
> 6 votes

# Answer
## JavaScript (ES6), ~~90~~ 82 bytes

Returns `0` or `true`.

```
f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

```

This is based on the assumption that if ***x*** exists then ***x ≤ 2n***. If proven false, this should be updated to use `x=n*n` instead of `x=n*2` (same size, much slower).

An edge case is ***n = 128*** which requires to compute ***ϕ(255)***.

### Demo

```
f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

for(n = 1; n <= 50; n++) {
  console.log(n, f(n));
}
```
> 2 votes

# Answer
# Axiom, 56 bytes

```
f(x:PI):Boolean==member?(x,[eulerPhi(i)for i in 1..2*x])

```

i don't know if it is right...test code and results

```
(35) -> [i  for i in 1..100|f(i)]
   (35)
   [1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46,
    48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100]

```

The range 1..(2\*x) would be ok until input x=500...
> 1 votes

# Answer
# 05AB1E, 5 bytes

```
nLÕså

```

Explanation:

```
n       Square [implicit] input
 L      Range [1 .. a]
  Õ     Euler totient
   s    Put first input at the top of the stack
    å   Is it in the list?

```

Try it online!
> 1 votes

# Answer
# Pari/GP, 34 bytes

```
x->![n|n<-[1..x^2],eulerphi(n)==x]

```

Returns `0` if reachable, `1` if not.

Try it online!
> 1 votes

# Answer
# 05AB1E, ~~13~~ 12 bytes

**EDIT**: Saved a byte because input is reused if the stack doesn't have enough elements.

Outputs 1 if reachable, 0 if not.

Relies on assumption that x ≤ 2n if it exists.

```
xGNÕQi1,q}}0

```

Try it online!

How it works

```
              # implicit input
x            # push input, 2 * input
 G           # for N in 1..2*input
             # implicit push input
  N          # push N
   Õ         # push totient of N
    Q        # check if both are equal
     i.      # if equal
      1,     # print 1
        q    # quit program
         }   # end if
          }  # end for
           0 # push 0 if condition never reached
             # implicit print

```
> 0 votes

# Answer
# C, 123 bytes

```
g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

```

**Try Online**

```
#include <stdio.h>

// gcd function
g(a,b){return!a?b:g(b%a,a);}

// Euler phi(x) function
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}

// check if m is reachable, phi(x) for x in (m , m^2]
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

main()
{
    // print all reachable number below 50
    for(int x=1; x<50; x++)
    {
        s(x);

        if(t)
        {
            printf(" %d ~ phi(%d) \n", x, k);
        }
    }
}

```
> 0 votes

# Answer
# Whispers v2, 63 bytes

```
> Input
>> 1²
>> [2]
>> φ(L)
>> Each 4 3
>> 1∈5
>> Output 6

```

Try it online!

Works by brute force. We square the input, then generate the range `[1, 2, ..., x²]`. Next we calculate \\$\phi(i)\\$ for each \\$i\\$ in this range. Finally, we check if the original input \\$x\\$ is in the array of \\$\phi(i)\\$ values.
> 0 votes

# Answer
# Stax, 6 bytes

```
┬$τ▀Ω♀

```

Run and debug it

I'm not sure why 3 golflangs have an Euler Totient function, but I guess it's convenient for these challenges.

0 for reachable and 1 for non-reachable.
> 0 votes

---
Tags: code-golf, math, number-theory, decision-problem
---


title: Convert height to US Men’s Jacket size

text:
# Question
Title: Convert height to US Men’s Jacket size
In the US, clothing size sometimes has rough designations like M, L, XXL, etc. The US designation of the "men's jacket" category depends on the height of the person. So, in this challenge, you should implement this conversion, which is defined by the following table, taken from this site:

```
US size Body height (cm)
XXXS    160 - 164
XXS     162 - 166
XS      166 - 170
S       168 - 173
M       171 - 176
L       174 - 182
XL      180 - 186
XXL     184 - 189
3XL     187 - 193
4XL     191 - 194
5XL     193 - 198
6XL     197 - 200

```

* I chose the "men's jacket" category from there because it has the most variability

### Input

Body height, in cm. As a number or a string.

### Output

Size designation - as a return value or printed.

### Additional rules

* For some sizes, designation is uncertain (e.g. 174, 175 and 176 correspond to both M and L) - your converter should return one of these, deterministically or not
* If it's easier, output fully spelled versions like XXXXL instead of 4XL; however, 2XL and 2XS are invalid (apparently they are used in real life, but I decided to forbid them because I thought they weren't)
* Assume the input is valid, i.e. a whole number between 160 and 200

# Answer
# Python 2, ~~58~~ ~~55~~ ~~52~~ ~~49~~ ~~47~~ 45 bytes

-13 bytes with great contributions from Arnauld (thanks!!!), xnor and xash.
Switched from Python 3 to Python 2 for an extra 2 bytes.

Tried to profit from the overlapping regions. You don't even need a size M, because the sizes of S and L don't have a gap between them. Luckily, the number of X's for S and L can be expressed as a linear integer expression.

```
lambda h:max(173-h>>2,h/3-60)*'X'+'SL'[h>173]

```

Try it online!

Just for fun (and for educational purposes) the original 58 bytes submission:

```
lambda h:(-h+173)//4*'X'+'S'if h<174else(h-180)//3*'X'+'L'

```
> 12 votes

# Answer
# JavaScript (ES8), 50 bytes

This version is derived from the method used in Python by agtoever.

```
n=>'SL'[q=n/87>>1].padStart(q?n/3-59:177-n>>2,'X')

```

Try it online!

---

# JavaScript (ES6), 61 bytes

```
n=>'6543X LMS X3'[i=59-n/3.4|0].trim()+(i<6?'XL':i>8?'XS':'')

```

Try it online!
> 9 votes

# Answer
# Python 2, 82 bytes

```
lambda x:"3XXSMLXX3456XXS   LXXXXXSS     LLLLL"[~-x/3-53-x/177-x/189+(x==195)::12]

```

Try it online!

-2 bytes thanks to ovs
> 8 votes

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

```
{"XSL"(&0|(-4!x)|-3!-7-x),1+0>x}173-

```

Try it online!

Adapted by @ngn from @agtoever's python golf.

# K (ngn/k), 51 bytes

```
|$`SXXX`SXX`SX`M`L`LX`LX3`LX5`LX6@(159+\7\8689119)'

```

Try it online!

`bin`s the input, using a reduced subset of the available sizes to reduce the byte count.

* `(...)'` run a binary lookup of the (implicitly provided) height against the list of heights; this returns the index of the first value equal to or larger than the input
* `(159+\7\8689119)` a compressed version of `160 163 166 171 177 183 187 193 198`
* ``SXXX`SXX`SX`M`L`LX`LX3`LX5`LX6@` index into the list of sizes
* `|$` convert to string and reverse the characters

The sizes with heights unique to them are:

* `XXXS` =\> `160 161`
* `XXS` =\> `165`
* `XS` =\> `167`
* `L` =\> `177 178 179`
* `XL` =\> `183`
* `3XL` =\> `190`
* `5XL` =\> `195 196`
* `6XL` =\> `199 200`

The only heights not covered by these sizes are `171 172 173`, which can be covered by either `S` or `M`. `M` is preferable, as it minimizes the differences between successive items of the list of heights. The other cutoffs between sizes were similarly chosen.
> 7 votes

# Answer
# , 49 bytes

`M` is not needed, and the Xs are written out.

```
(+/\157,6 7#4 3)&(('X'#~0>._1+5|@-I.),'LS'{~5>I.)

```

Try it online! Prints the table with all possible outputs. First column is the `f(n)`, followed by `n`, followed by the possible sizes for `n`.

* `157,6 7#4 3`: `157 4 4 4 4 4 4 3 3 3 3 3 3 3`
* `(+/\…)&f` `157 161 165 169 173 177 181 184 187 190 193 196 199 202` are the intervals `…,x_0], (x_0, x_1], (x_1, x_2], …`.
* `'LS'{~5>I.` get the interval index of `n` – if it is less than 5, then S, otherwise L.
* `('X'#~0>._1+5|@-I.),` interval index, subtracted by 5 (…, XS is -1, S is 0, L is 1, XL is 2, …), absolute value, take `max(n-1, n)` to lower the L side by one. Take this amount of X's and prepend it to the S/L.
> 6 votes

# Answer
# 05AB1E, ~~37~~ 36 bytes

Thanks to Kevin Cruijssen for -1 byte!

Looking at some answers in practical languages, this seems way too long.

```
‘—ŽS‘.sR…MLX`6×«ηí)˜IŽ6lbS3+.¥Ƶz+›Oè

```

Try it online! or See all outputs

This uses the following lookup table:

```
XXXS    160 - 162
XXS     163 - 166
XS      167 - 170
S       171 - 173
M       174 - 176
L       177 - 179
XL      180 - 183
XXL     184 - 186
3XL     187 - 190
4XL     191 - 193
5XL     194 - 196
6XL     197 - 200

```

`"SXXX"ηíR…MLX`6×«ηí)˜` generates all possible outputs, `IŽ6lbS3+.¥Ƶz+›Oè` selects the correct one.

```
‘—ŽS‘                  # dictionary string   "XXXS"
     .s                # take the suffixes   ["S", "SX", "SXX", "SXXX"]
       R               # reverse the list    ["XXXS", "XXS", "XS", "S"]
        …MLX           # push string literal "MLX"
            `          # push each character to the stack
             6×        # repeat "X" 6 times  "XXXXXX"
               «       # concat with "L"     "LXXXXXX"
                η      # take prefixes       ["L", "LX", ..., "LXXXXXX"]
                 í     # reverse each        ["L", "XL", ..., "XXXXXXL"]
                  )    # put the entire stack into a list
                   ˜   # and flatten the list

I                      # push the input
 Ž6l                   # compressed integer  1577
    b                  # convert to binary   "11000101001"
     S                 # split into digits   [1,1,0,0,0,1,0,1,0,0,1]
      3+               # add 3 to each digit [4,4,3,3,3,4,3,4,3,3,4]
        .¥             # un-delta, cumulative sum with 0 prepended
          Ƶz           # compressed integer  162
            +          # add to each element
                       # [162,166,170,173,176,179,183,186,190,193,196,200]
             ›         # is each item larger than the input
              O        # sum the results
               è       # index into the list of possible outputs

```

---

A port of agtoevers's Python answer comes in at ~~28~~ 25 bytes in the legacy edition:

```
Ƶи‹i'SƵвI-4ë'LIƵΔ-3}÷'X×ì

```

See all outputs!

Thanks to Kevin Cruijssen for -3 bytes!
> 5 votes

# Answer
# Charcoal, ~~42~~ 26 bytes

```
≔⁻Ｎ¹⁷³θ×X÷±θ⁴×X⊖⊖÷θ³§LS›⁰θ

```

Try it online! Link is to verbose version of code. Port of @Port of @agtoever's answer, so outputs using `XXXL` etc.. Explanation:

```
≔⁻Ｎ¹⁷³θ

```

Subtract 173 from the input.

```
×X÷±θ⁴

```

If it's negative then print a number of `X`s equal to a quarter of the negated value.

```
×X⊖⊖÷θ³

```

If it's positive then print a number of `X`s two less than a third of the value.

```
§LS›⁰θ

```

Output `S` for negative and `L` for positive. The resulting lookup table:

```
XXXS    160 - 161
XXS     162 - 165
XS      166 - 179
S       170 - 173
L       174 - 182
XL      183 - 185
XXL     186 - 188
XXXL    189 - 191
XXXXL   192 - 194
XXXXXL  195 - 197
XXXXXXL 198 - 200

```

Previous 42-byte answer using `3XL` style output:

```
§⪪”{➙✳FＩ2κ？↓gＶＫ¤↘⸿⊙⁻QR”¶Σ÷Ｎ⁺¹⁶²Ｅ⁸Σ…426676ι

```

Try it online! Link is to verbose version of code. Explanation: Implements the following lookup table:

```
XXXS    160 - 161
XXS     162 - 165
XS      166 - 167
S       168 - 173
L       174 - 179
XL      180 - 186
3XL     187 - 192
5XL     193 - 196
6XL     197 - 200

```

`XXXS` is used for sizes of up to 161, and subsequent sizes depends on how many digits from the substring `426676` can added while the keeping the total less than the input, with `0` digits giving `XXS` and `7` digits (by repeating the initial `4`) giving `6XL`. (It's not possible to repeat additional digits as the 6th digit must be at least 6 but neither of the first two digits can be that high.)
> 4 votes

# Answer
# Python 3, ~~278~~ ~~277~~ ~~260~~ 217 bytes

-1 byte thanks to @HyperNeutrino
-17 bytes thanks to @SunnyMoon
another -43 bytes thanks to @HyperNeutrino

```
lambda x:[c for a,b,c in[[160,165,"3XS"],[162,167,"XXS"],[166,171,"XS"],[168,174,"S"],[174,183,"L"],[180,187,"XL"],[184,190,"XXL"],[187,194,"3XL"],[191,195,"4XL"],[193,199,"5XL"],[197,201,"6XL"]]if x in range(a,b)][0]

```

Try it online!
> 3 votes

# Answer
# Perl 5, 39 bytes

```
$_=$_<174?X x(57-$_/3).S:X x($_/3-60).L

```

Try it online!

With all tests: Try it online!

Recognising that size M is not needed and that the number of X'es can be calculated from a difference divided by 3. Uses unquoted barewords for S, L and X.
> 3 votes

# Answer
# Husk, ~~26~~ ~~25~~ 25 bytes

*Edit: fixed bug, same bytes*

```
§:oR'X?_-3<0o?'S'L<1-57/3

```

Try it online!

```
§:oR'X?_-3<0o?'S'L<1-57/3
                    -57/3  # x = (height/3)-57
§:                         # now join 2 strings:
            o?'S'L<1       # string 1: 'S' if x<1, 'L' otherwise
  ȯR'X                     # string 2: repeat 'X'
      ?_-3<0               # if x is positive: x-3 times
                           # if x is negative: -x times

```
> 3 votes

# Answer
# Groovy, ~~74 71 70~~ 64 bytes

```
f={('XXXSXXSXSSMLXLXXL3XL4XL5XL6XL'=~/\d?X*./)[it/3.4-47as int]}

```

Try it online!

1. `('XXXSXXSXSSMLXLXXL3XL4XL5XL6XL'=~/\d?X*./)` finds all matches of the regex against the string, i.e. `[XXXS, XXS, XS, S, M, L, XL, XXL, 3XL, 4XL, 5XL, 6XL]`.
2. `it/3.4-47as int` converts the height to a valid index within the list of matches.
3. `(string=~pattern)[index]` retrieves the match at the given index
> 2 votes

# Answer
# Python 3, 85 bytes

```
lambda s:[b for*b,a in b"3XSB XXSD XSH SK LT XLX 3XL_ 5XLd 6XLf".split()if s-99<a][0]

```

Try it online!

Outputs as a list of ASCII code-points.
> 1 votes

# Answer
# Julia, 65 bytes

```
x->split("XXXS XXS XS M L XL XXL 3XL 5XL 6XL")[x.<162:4.3:204][1]

```

Try it online!
> 1 votes

# Answer
# Retina 0.8.2, 57 bytes

```
.+
$*1-174$*
(1+)-\1
-
-(1111)*1+
$#1$*XS
111
X
X?X?1*-
L

```

Try it online! Link includes test suite. Port of @agtoever's answer, so outputs using `XXXL` etc.. Explanation:

```
.+
$*1-174$*
(1+)-\1
-

```

Convert to unary and subtract 174.

```
-(1111)*1+
$#1$*XS

```

If the result is negative, then negate, subtract 1, and divide by 4, which gives the size in `X*S`.

```
111
X
X?X?1*-
L

```

Otherwise, divide by 3 and subtract up to 2, which gives the size in `X*L`.

The resulting lookup table:

```
XXXS    160 - 161
XXS     162 - 165
XS      166 - 179
S       170 - 173
L       174 - 182
XL      183 - 185
XXL     186 - 188
XXXL    189 - 191
XXXXL   192 - 194
XXXXXL  195 - 197
XXXXXXL 198 - 200

```
> 1 votes

# Answer
# Bash, 128 bytes

```
L=kfd90HK
H=uBgI0LP
s=$[$1-150]
c=L
((s<24))&&c=S
for ((;;i++)) {
(($[64#${L:i:1}]<s&&s<$[64#${H:i:1}]))&&echo $c&&exit
c=X$c
}

```

Try it online!

Ungolfed version below for review:

```
# Size  cm range	-150	>Low	<High	# of X
#XXXS	160-163		10-13	9		3
#XXS	164-165		14-15	13	16	2
#XS	166-170		16-20	15		1
#S	171-173		21-23	20		0
#M
#L	174-179		24-29		30	0
#XL	180-186		30-36		37	1
#XXL
#3XL	187-193		37-43		44	3
#4XL
#5XL	194-196		44-46	43	47	5
#6XL	197-200		47-50	46	51	6

#L=20 15 13 9 0 43 46
#H=30 37 16 44 0 47 51
L=kfd90HK
H=uBgI0LP

# print the high and low threshold arrays to verify base64 numbers
for ((k=0;k<7;k++)) {
  l=$[64#${L:k:1}]
  h=$[64#${H:k:1}]
  echo $k: low:$l high:$h
}
echo

# Test set: check algorithm on all values [160-200]
for ((j=160;j<=200;j++)) {
  s=$[j-150]

  c=L;((s<24))&&c=S
  for ((i=0;i<8;i++)) {
    l=$[64#${L:i:1}]
    h=$[64#${H:i:1}]
    ((l<s&&s<h))&&echo $j:$c&&break
    c=X$c
  }
}

```

Try it online!
> 1 votes

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


title: Crop an image to a square

text:
# Question
Title: Crop an image to a square
In this challenge, you will take an input image and crop it to make a square, leaving only the central part of the input image.

The answers must work with landscape, portrait, or square input images. The width of the output image should be equal to the shortest side of the input image e.g. the result of a 200x300 image should be a 200x200 image. An equal amount must be cropped from both ends of the input image e.g. for a 200x300 input image, 50 pixels should be cropped from each end of the image, leaving only the central part of the image. Where its not possible to crop an equal amount from both sides e.g. a 200x301 image, the extra 1 pixel may be cropped from either end of the image. For a square input image, the output should be identical to the input.

**Input:**

The input file should be read from the hard disk of the machine running the program. You may choose which of bmp, jpeg, png or pnm to support as the input image format.

**Output**

The output file should be written to the hard disk of the machine running the program. The format of the output image should be bmp, jpeg, png or pnm.

**Win Criteria**

This is code golf. Shortest code wins.

**Notes:**

1. The input/output file paths do not count towards the program size.
2. The standard libraries of your programming language may be used. Other libraries are disallowed.
3. Standard loopholes apply.

**Example:**

Input Image:

Expected Output:

Images by kirill777 - licenced CC-BY 3.0

# Answer
# Parsing the raw bytestream: Haskell (319 = 332 - 13)

Without any imports at all, this program crops P1 PBM images.

```
g _[]=[]
g z x=(\(a,b)->a:g z b).splitAt z$x
q=map
f=filter
main=do c<-readFile"in.pbm";let(r:p)=tail.f((/='#').head).lines$c;(w:h:_)=(q read).words$r;m=min w h;t s=take m.drop((s-m)`div`2);k d=[[m,m]]++(q(t w)(t h d))in writeFile"out.pbm".("P1\n"++).unlines.q(unwords.(q show)).k.(q((q read).g 1)).take h.g w.f(`elem`"01").concat$p

```

## Special case: helpful formatting (214 = 227 - 13)

My first attempt at PBM (P1) was based on the example at Wikipedia and assumed spaces separated the pixels, and lines in the text correlated with lines in the image. Under those conditions, this shorter version works fine.

```
main=do c<-readFile"in.pbm";writeFile"out.pbm".("P1\n"++).unlines.q(unwords.(q show)).k.q((q read).words).tail.filter((/='#').head).lines$c
k((w:h:_):d)=let m=min w h;t s=take m.drop((s-m)`div`2)in[[m,m]]++(q(t w)(t h d))
q=map

```

Bonus feature: strips out comments!

Both of the above work in essentially the same manner as the original below, but with a simpler header, lower bit depth, and no padding, although the topmost program works harder to allow for a range of formatting options.

# Also available in a wide range of colours: Haskell (545 = 558 - 13)

No pre-existing image-handling functions were harmed in the making of this program.

Uncompressed 24-bit RGB bitmaps have a fairly straight-forward header system but are complicated by the mod-4 padding for each row's byte array. This code grabs the bitmap offset, width, and height from the input header, calculates the row padding, and extracts the bitmap data into a list of lists (rows of columns, bottom-left corner first).

Cropping is as simple as dropping half the excess and then taking the desired length from each list. The new file size is calculated as 3\*(padded width)\*height + 54 bytes (for the minimal required headers). The new header is constructed and the cropped image data appended. It's all mapped to characters and written back out to disk.

Input: `in.bmp` (6 characters removed from total)
Output: `out.bmp` (7 characters removed from total)

I think there's still some redundancy still in there, but my brain hurts to look at it this way.

```
import System.IO
import Data.Char
import Data.List.Split
main=do k"in.bmp"ReadMode(\h->do i h u;c<-hGetContents h;let d=l(ord)c;w=s 18d;h=s 22d;p=o w;m=min w h;q=o m;j a b=y a(r b m)in k"out.bmp"WriteMode(\g->do i g u;hPutStr g$"BM"++l chr((z e[m*(3*m+q)+54,0,54,40,m,m,1572865,0,0,1,1,0,0])++((z((++(f q$cycle[0])).y(3*m)(3*r w m)).j m h$chunksOf(3*w+p)$n(s 10d)d)))))
i=hSetBinaryMode
k=withFile
z=concatMap
l=map
v=div
f=take
n=drop
u=True
y t d=f t.n d
s d=sum.zipWith(*)(l(256^)[0..3]).y 4d
o=(`mod`4)
r a b=v(a-b)2
e x=l((`mod`256).(x`v`).(256^))[0..3]

```

For comparison, an ungolfed version is over 8 times as long, at 4582 (4595 - 13) bytes:

```
import System.IO
import Data.Char
import Data.List.Split

main = readImage cropImageToSquare

cropImageToSquare fileHandle = do

  hSetBinaryMode fileHandle True
  fileContents <- hGetContents fileHandle

  let
    inImageData         = asBytes fileContents

    inImageBitmapOffset = getIntFromWordAt 10 inImageData
    inImageWidth        = getIntFromWordAt 18 inImageData
    inImageHeight       = getIntFromWordAt 22 inImageData

    inImageBitmapData   = drop inImageBitmapOffset inImageData
    inImageBitmap       = chunksOf (paddedBytesForWidth inImageWidth) inImageBitmapData

    outImageSideLength  = min inImageWidth inImageHeight

    outFileHeader       = fileHeader  outImageSideLength outImageSideLength
    outImageHeader      = imageHeader outImageSideLength outImageSideLength
    outHeaders          = outFileHeader ++ outImageHeader

    outImageBitmap      = crop outImageSideLength outImageSideLength inImageWidth inImageBitmap

    in
      writeImage "out.bmp" outHeaders outImageBitmap

--- Read Image ---------------------------------------------------------

readImage = withFile "in.bmp" ReadMode

--------------------------------------------------------- Read Image ---

--- Write Image --------------------------------------------------------

writeImage filename header imageBitmap = do
  withFile filename WriteMode write'
    where
      write' fileHandle = do
        hSetBinaryMode fileHandle True
        hPutStr fileHandle . ("BM"++)
                           . map chr $ (concatMap wordFromInt header)
                                     ++ (concat imageBitmap)

-------------------------------------------------------- Write Image ---

--- Character-Integer Conversion ---------------------------------------

asBytes = map ord

getWordAt offset = take 4 . drop offset

getIntFromWordAt offset = intFromWord . getWordAt offset

intFromWord     = sum . zipWith (*) (map (256^) [0..3])

wordFromInt int = map((`mod` 256) . (int `div`) . (256^)) [0..3]

--------------------------------------- Character-Integer Conversion ---

--- Headers ------------------------------------------------------------

fileHeader width height = [ fileSize
                          , reserved
                          , bitmapOffset
                          ]
  where
    fileSize     = imageFileSize width height
    reserved     = 0
    bitmapOffset = 54

imageFileSize width height = 54 + height * (paddedBytesForWidth width)
paddedBytesForWidth width  = 3 * width + rowPadding width
rowPadding = (`mod` 4)

imageHeader width height = [ imageHeaderSize
                           , width
                           , height
                           , planesAndBits
                           , compression
                           , bitmapSize
                           , horizontalImageResolution
                           , verticalImageResolution
                           , paletteSize
                           , coloursUsed
                           ]
  where
    imageHeaderSize  = 40
    planesAndBits    = int32FromInt16s colourPlanes bitDepth
    colourPlanes     = 1
    bitDepth         = 24
    compression      = 0
    bitmapSize       = 0
    horizontalImageResolution = pixelsPerMetreFromDPI 72
    verticalImageResolution   = pixelsPerMetreFromDPI 72
    paletteSize      = 0
    coloursUsed      = 0

pixelsPerMetreFromDPI = round . (* (100/2.54))

int32FromInt16s lowBytes highBytes = lowBytes + shift 2 highBytes
shift bytesUp number  = (256 ^ bytesUp) * number

------------------------------------------------------------ Headers ---

--- Crop Image ---------------------------------------------------------

crop toHeight toWidth fromWidth = cropWidth toWidth fromWidth
                                . cropHeight toHeight

cropHeight toHeight image = take toHeight
                          . drop ( halfExtra (length image) toHeight)
                          $ image

cropWidth toWidth fromWidth image = map ( padRow toWidth
                                        . take (3 * toWidth)
                                        . drop (3 * (halfExtra fromWidth toWidth))
                                        )
                                      $ image

padRow toWidth xs = take (paddedBytesForWidth toWidth)
                      $ xs ++ (repeat 0)

halfExtra fromLength toLength = (fromLength - toLength) `div` 2

--------------------------------------------------------- Crop Image ---

```
> 4 votes

# Answer
# Rebol, ~~165~~ 92 (105 - 13)

```
i: load %in.bmp
s: i/size
m: min s/1 s/2
c: to-pair reduce[m m]save %out.bmp copy/part skip i s - c / 2 c

```

At its simplest if you have a image file (*in.bmp*) of 300x200 then it can be cropped and saved to file (*out.bmp*) like so:

```
save %out.bmp copy/part skip load %in.bmp 50x0 200x200

```

Rebol comes with a spatial coordinates datatype called `Pair!` Here are some examples of this datatype (using Rebol console):

```
>> type? 300x200
== pair!

>> first 300x200
== 300.0

>> second 300x200
== 200.0

>> 300x200 - 200x200
== 100x0

>> 300x200 - 200x200 / 2
== 50x0

```

The last example shows how the `skip` coordinates were worked out for balanced cropping.

NB. This solution was tested using latest version of Rebol 3 (see http://rebolsource.net/) on OS X. BMP is currently supported on all platforms. PNG, Jpeg & other formats are only partially implemented (across platforms) at this time.
> 3 votes

# Answer
## Mathematica 52

Spaces not needed:

```
ImageCrop[#, {#, #} &@Min@ImageDimensions@#] &@Import@"c:\\test.png"

```
> 3 votes

# Answer
# Bash, 115

with ImageMagic, hard to say if you can count it as a standard lib :)

```
#!/bin/bash
convert $1 -set option:size '%[fx:min(h,w)]x%[fx:min(h,w)]' xc:red +swap -gravity center -composite _$1

```
> 2 votes

# Answer
# Java, ~~373~~ ~~348~~ ~~342~~ ~~336~~ 322

```
import java.awt.image.*;import java.io.*;import javax.imageio.*;class M{public static void main(String[]a)throws Exception{BufferedImage i=ImageIO.read(new File(a[0]));int[]d={i.getWidth(),i.getHeight()},o={0,0};int s=d[0]>d[1]?1:0;o[1-s]=(d[1-s]-d[s])/2;ImageIO.write(i.getSubimage(o[0],o[1],d[s],d[s]),"bmp",new File("out.bmp"));}}

```

Ungolfed:

```
import java.awt.image.*;
import java.io.*;

import javax.imageio.*;

class M{
    public static void main(String[] args) throws Exception{
        // read file as argument, instead of args[0] the path to the file could hardcoded.
        // Since the path to the input file don't count towards the character count, I'm not counting args[0]
        BufferedImage i = ImageIO.read(new File(args[0]));

        int[] dimension = { i.getWidth(), i.getHeight() }, origin = { 0, 0 };

        int smaller = dimension[0] > dimension[1] ? 1 : 0;

        // 1-smaller is the index of the bigger dimension
        origin[1-smaller] = (dimension[1-smaller] - dimension[smaller]) / 2;

        // again, path to output file don't count
        ImageIO.write(i.getSubimage(origin[0], origin[1], dimension[smaller], dimension[smaller]), "bmp", new File("out.bmp"));
    }
}

```

Usage: `java M image.type`

Should be able to read jpg, png, bmp, wbmp and gif. Writes a bmp called "o".

Who said you couldn't use Java for golf?

Edit: Just realised that file paths don't count towards the character count.
> 2 votes

# Answer
# C# - ~~250~~ ~~271~~ ~~265~~ 229 (incl. 26 for file names)

Forgot about the import for it to work.

```
using System.Drawing;
class P{static void Main(string[] a){var b=new Bitmap(@"C:\Dev\q.jpg",true);int h=b.Height,w=b.Width,s=h<w?h:w,d=(h-w)/2;b.Clone(new Rectangle(d>0?0:d*-1,d>0?d:0,s,s),b.PixelFormat).Save(@"C:\Dev\q2.jpg");}}

```

De-golfed (or what you call it).

```
using System.Drawing;
class Program
{
static void Main(string[] a)
{
var b = new Bitmap(@"C:\Dev\q.jpg",true);
int h=b.Heightw=b.Width,s=h<w?h:w,d=(h-w)/2;
b.Clone(new Rectangle(d>0?0:d*-1,d>0?d:0,s,s),b.PixelFormat).Save(@"C:\Dev\q2.jpg");
}
}

```

Thanks (again) to w0lf for pointing out different declaration style.
> 2 votes

# Answer
# C#, 420

If the image is portrait it gets rotated while cropping and then cropped image is rotated to correct orientation.

Edit: now crop centre of the image. Run in terminal as `crop.exe a.jpg`

```
class P
{
static void Main(string[] a)
{
if (a.Length > 0)
{
Bitmap b = (Bitmap)Image.FromFile(a[0]);
int w = b.Width;
int h = b.Height;
int d = Math.Abs(w - h) / 2;
if (h > w) { b.RotateFlip(RotateFlipType.Rotate270FlipNone); }
Bitmap c = new Bitmap(h, h);
for (int x = d; x < (h+d); x++)
{
for (int y = 0; y < h; y++)
{
c.SetPixel(x-d, y, b.GetPixel(x, y));
}
}
if (h > w) { c.RotateFlip(RotateFlipType.Rotate90FlipNone); }
c.Save("Q.jpg");
}
}
}

```
> 1 votes

# Answer
# Clojure, 320 (333 - 13 for filenames)

Deciding to sidestep types, this P1 (ASCII) PBM cropper is written in Clojure.

With function names like `interpose`, `read-string`, and `clojure.string/replace`, it's not exactly golf friendly, and I'm not sufficiently experienced to know if I can compile without a namespace declaration. (Leiningen puts it in automatically, and Leiningen is nice to me, so I'm going to leave it there, though I did eject `.core`.) On the plus side, however, file access and string concatenation are short.

```
(ns a(:gen-class))(defn -main[](let[[[_ r p]](re-seq
#"(^\s*\d+\s+\d+)([\s\S]*$)"(clojure.string/replace(slurp"in.pbm")#"(P1)|(#.*\n)"""))[w
h](map read-string(re-seq #"\d+"r))c(min w h)](spit"out.pbm"(apply
str"P1\n"c" "c"\n"(flatten(interpose"\n"(take
c(partition c w(drop(+(*(quot(- h c)2)w)(quot(- w c)2))(re-seq #"\S"p))))))))))

```

The function at the heart of the program is ungolfed below.

```
(defn crop-pbm [in out]
  (let [         filestream (slurp in)
                 image-data (clojure.string/replace (str filestream "\n") #"(P1)|(#.*\n)" "")
    [[_ resolution pixels]] (re-seq #"(^\s*\d+\s+\d+)([\s\S]*$)" image-data)
                     pixels (re-seq #"\S" pixels)
             [width height] (map read-string (re-seq #"\d+" resolution))
                       crop (min width height)
                 drop-width (- width  crop)
                drop-height (- height crop)
         initial-drop-width (quot drop-width  2)
        initial-drop-height (quot drop-height 2)
               initial-drop (+ (* initial-drop-height width) initial-drop-width)
             cropped-pixels (take crop
                                  (partition crop width
                                             (drop initial-drop pixels)))
              cropped-image (apply str "P1\n" crop " " crop "\n"
                                       (flatten (interpose "\n" cropped-pixels)))]
      (spit out cropped-image)))

```

Rather than constructing a two-dimensional array to represent the image, this program calculates the number of pixels to the new top-left corner and drops them, then jumps original-width pixels at a time, taking cropped-side-length pixels from as many steps.

The regular expression function `re-seq` does much of the heavy lifting, stripping out whitespace and forming arrays simultaneously, which leads me to suspect that Perl could follow this approach and yield a shorter program.
> 1 votes

# Answer
# Perl, 276 ~~287~~ (289 ~~300~~ \- 13)

## Regex to the Rescue!

Who needs dedicated image functions when you have regular expressions? (And 1-bit images to crop.)

```
local$/;open I,"in.pbm";$_=<I>;s/(P1)|(#.*\n)//g;/^\s*(\d+)\s+(\d+)([\s\S]*)$/;($w,$h,$_)=($1,$2,$3);$c=$w<$h?$w:$h;s/\D//g;$d=$w-$c;while($z++<$w*int(($h-$c)/2)+int($d/2)){s/^\d//};while($i++<$c){/^(\d{$c})(\d{$d})(.*)/;$p.=$1."\n";$_=$3."0"x$w}open O,'>',"out.pbm";print O"P1\n$c $c\n$p"

```

That's the golfed version of:

```
use strict;
use warnings;

# Read in the image file
local $/ = undef;

open IMAGEIN, '<', "in.pbm" or die "Can't read 'in.pbm': $!";
my $image_data = <IMAGEIN>;
close IMAGEIN;

# Remove the header and any comments
$_ = $image_data;
s/(P1)|(#.*\n)//g;

# Divide into width, height, and pixels
/^\s*(\d+)\s+(\d+)([\s\S]*)$/;
(my $width, my $height, $_) = ($1, $2, $3);

# Remove anything that isn't a number from the pixel data
s/\D//g;
my $pixels = $_;

# Determine the new dimensions
my $crop = $width < $height ? $width : $height;

# Calculate total to remove along each axis
my $drop_width  = $width  - $crop;
my $drop_height = $height - $crop;

# Calculate how much to remove from the first side along each axis
my $initial_drop_width  = int($drop_width  / 2);
my $initial_drop_height = int($drop_height / 2);

# Calculate total pixels to the new top-left corner
my $initial_drop = $width * $initial_drop_height + $initial_drop_width;

# Remove the pixels preceding the corner
$_ = $pixels;
while (32760 < $initial_drop)  # Stay under regex limit
{
    s/^\d{32760}//;
    $initial_drop -= 32760;
}
s/^\d{$initial_drop}//;

# Take *crop* rows of *crop* pixels
$pixels = "";
for (my $i=0; $i<$crop; $i++)
{
    /^(\d{$crop})(\d{$drop_width})(.*)/;
    $pixels .= $1 . "\n";
    $_ = $3 . "0"x$width;  # Add some 0s to ensure final match
}

# Construct the new, cropped image
my $cropped_image = "P1\n$crop $crop\n$pixels";

# Write out the image file
open IMAGEOUT, '>', "out.pbm" or die "Can't write 'out.pbm': $!";
print IMAGEOUT $cropped_image;
close IMAGEOUT;

```

There's a limit to the length of a string the substitution functions will handle, which necessitates a bothersome `while` loop for taller images. Even so, finally under 300!
> 1 votes

# Answer
# C++/Qt 146

This might technically break rule #2 as Qt is not part of standard C++.

The first argument will be the input filename and the second will be the output filename.

```
#include<QtGui>
main(int c,char**v){QApplication a(c,v);QPixmap p(v[1]);int w=p.width(),h=p.height(),m=qMin(w,h);p.copy(w-m,h-m,m,m).save(v[2]);}

```
> 0 votes

# Answer
# Io, 103 bytes (excluding file path)

```
i := Image open("img.png");e := (i width) min(i height);i crop(((i width)-e)/2,((i height)-e)/2,e,e) save("crop.png")

```

*You can* use Io for CG!
> 0 votes

# Answer
# Matlab, 116 (130 with file names)

Pretty straightforward.

```
I=imread('a.jpg');[m,n]=size(I);z=min(m,n);c=m<n;r=[1,ceil((m-z)/2)]*~c+c*[ceil((n-z)/2),1];imwrite(imcrop(I,[r,z-1,z-1]),'z.jpg')

```
> 0 votes

# Answer
# APL (dzaima/APL), 66 bytes

```
i←P5.img p
P5.size←2⍴a←⌊/s←i.sz
P5.draw←{i P5.G.img⍨.5×a-s⋄i.save}

```

Try it online!
> 0 votes

---
Tags: code-golf, graphical-output, image-processing
---


# Question
Title: Hacker Challenge: Guess the Correct Password
In an attempt to “liberate” their fellow birds, a group of highly intelligent hens are attempting to compromise the zoo’s security system. To get access to the zoo’s mainframe, the hens first need to guess the administrative password. The hens know that the password is a string built from up to 62 possible characters: a, b, c, ..., z, A, B, C, ..., Z, 0, 1, ... 9. They also know that no character appears more than once in the password, which means that it has a maximum length of 62 (and a minimum length of 1). The password is case-sensitive.

We define a guess be close if and only if the real password can be obtained by inserting additional characters among the letters and numbers of the original guess. In other words, a guess is close if it is a (not necessarily contiguous) subsequence of the password. Every time the hens guess a password, the zoo’s security system will do one of three things:

* If the guess is exactly equal to the password, it will print ‘C’ and grant the hens access to the mainframe.
* If the guess close but not exactly equal to the password, it will print ‘Y’.
* If the guess is neither close nor exactly equal to the password, it will print ‘N’.

The mainframe permits at most 750 guesses before it locks further attempts and alerts the zoo officials of suspicious activity. The hens have hired you to guess the password before you use all of your allotted attempts.

There will be no initial input. Every time your program makes a guess, the grader will output ‘C’, ‘Y’, or ‘N’, which your program can then read via the usual input channel. The grader will only respond to the first 750 guesses. Make sure that you end each guess with a new line.

*This question was adapted from the 2020 mBIT Computing Olympiad.*

**Test Program made by me in Python 3 (works):**

```
from functools import cmp_to_key

def ask(s):
    print(s)
    c = input()
    if c == 'C':
        exit()
    return c == 'Y'

def cmp(a, b):
    return -1 if ask(a + b) else 1

ret = []
for i in range(48, 58):
    if ask(chr(i)):
        ret.append(chr(i))
for i in range(65, 91):
    if ask(chr(i)):
        ret.append(chr(i))
for i in range(97, 123):
    if ask(chr(i)):
        ret.append(chr(i))

ret = "".join(sorted(ret, key=cmp_to_key(cmp)))
print(ret)

```

I think it can be condensed even further, but that sample is just to show what the program is trying to ask. I do not own this question and all rights are to 2020 mBIT. The rules are simple. **Do not just print answers and shortest one wins in any language.**

# Answer
> 2 votes
### Python 3.7, 162 bytes

```
import string as S,functools as F
A=lambda s:'N'!=Input(s+'\n')
print(''.join(sorted(filter(A,S.ascii_letters+S.digits),key=F.cmp_to_key(lambda a,b:1-2*A(a+b)))))

```

Tries characters one-by-one to see which ones are in the password. Then sorts those letters using a comparison function. To compare 'A' and 'B', check to see if 'AB' returns 'Y'. If is does, then 'A' comes before 'B', otherwise 'A' comes after 'B'.

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


title: Print the alphabet Christmas tree

text:
# Question
Title: Print the alphabet Christmas tree
I know it's 1.5 weeks after Christmas but trying to print an isosceles triangle in a monospaced font makes it look weird.

# Challenge

Print the alphabet from A to Z so that it forms a filled triangle in the output. For each line in the output, starting from "A", add the next letter.

No inputs, only outputs. Pad the leading edge of the triangle with spaces.

Best answer is the code with the least bytes.

# Output

```
            A
            AB
           ABC
           ABCD
          ABCDE
          ABCDEF
         ABCDEFG
         ABCDEFGH
        ABCDEFGHI
        ABCDEFGHIJ
       ABCDEFGHIJK
       ABCDEFGHIJKL
      ABCDEFGHIJKLM
      ABCDEFGHIJKLMN
     ABCDEFGHIJKLMNO
     ABCDEFGHIJKLMNOP
    ABCDEFGHIJKLMNOPQ
    ABCDEFGHIJKLMNOPQR
   ABCDEFGHIJKLMNOPQRS
   ABCDEFGHIJKLMNOPQRST
  ABCDEFGHIJKLMNOPQRSTU
  ABCDEFGHIJKLMNOPQRSTUV
 ABCDEFGHIJKLMNOPQRSTUVW
 ABCDEFGHIJKLMNOPQRSTUVWX
ABCDEFGHIJKLMNOPQRSTUVWXY
ABCDEFGHIJKLMNOPQRSTUVWXYZ

```

# Sample Java Code (430 bytes)

```
public static void main(String args[]) {
    String spaces = "";
    String alpha = "";
    char A = 'A';

    for (int i = 0; i < 26; i++) {
        for (int j = 13 - (i/2); j > 0; j--) {
           spaces += " ";
        }

        alpha += (char)(A + i);

        System.out.println(spaces + alpha);
        spaces = "";
    }
}

```

# Answer
# Ruby, 44 bytes

```
t=''
26.times{|x|puts' '*(12-x/2)+(t<<65+x)}

```

Try it online!
> 5 votes

# Answer
# 05AB1E, 5 bytes

```
Auη.c

```

Try it online!

**Exlpanation**

```
A        # push the alphabet
 u       # convert to upper case
  η      # get list of prefixes
   .c    # centralize, focused to the left

```
> 3 votes

# Answer
# SOGL V0.12, 8 bytes

```
'⁸∫Zm}¹╚

```

Try it Here!

Explanation:

```
'⁸        push 26
  ∫  }    that many times, pushing the counter
   Zm       mold the alphabet to the counters length
      ¹   wrap the stack in an array
       ╚  center horizontally

```
> 2 votes

# Answer
# C# (.NET Core), 114 + 18 = 132 bytes

Try It Online!

```
()=>string.Join("\n",new int[26].Select((i,e)=>"ABCDEFGHIJKLMNOPQRSTUVWXYZ".Substring(0,e+1).PadLeft(13+(e+1)/2)))

```
> 1 votes

# Answer
# , <sub>~~38~~</sub> 36 bytes

```
echo(' '<@#"0~2#i._13),&><\u:65+i.26

```

Try it online!

This is honestly disgusting.

# 39 bytes

```
echo(2#i._13)(>@],~' '#~[)"0<\u:65+i.26

```

# Explanation

These will be snippets of the code built up from a REPL session. Three spaces means an input, and no spaces means the output from it.

### The alphabet

First we generate the alphabet by making the range \[65,90\] and converting this to unicode using `u:`.

```
   65 + i.10 NB. truncated
65 66 67 68 69 70 71 72 73 74
   u: 65 + i.26
ABCDEFGHIJKLMNOPQRSTUVWXYZ

```

Then we generate the `A`, `AB`, etc. sections by taking all of the prefixes of the alphabet and boxing them using `<\`

```
   <\ u: 65 + i.5 NB. truncated again
┌─┬──┬───┬────┬─────┐
│A│AB│ABC│ABCD│ABCDE│
└─┴──┴───┴────┴─────┘

```

### The padding

We need to pad the alphabet with 12, 12, 11, 11, etc. spaces. So first we construct this range using `i.` with a negative argument (which makes it go from that value minus 1 to 0, descending).

```
   i. _13
12 11 10 9 8 7 6 5 4 3 2 1 0

```

We then copy each value twice

```
   2 # i. _13
12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0

```

And then copy the space character as many times as specified, boxing it because J would pad the matrix with spaces to fill otherwise.

```
   '*' #"0~ 2 # i. _5 NB. truncated, and using '*' so you can see the output
****
****
***
***
**
**
*
*
    NB. This line is empty
    NB. This line is empty, too

```

### Getting the output

Then we just join the two together using `,` (unboxing first using `&>`) and write to STDOUT using `echo`. There's nothing to show here since it's just the output.
> 1 votes

# Answer
# Excel (VBA), ~~129~~ 82 bytes

Using Immediate Window. ~~and cell `[A1]` as output.~~

```
For x=25to 0Step -1:For y=x to 25:b=b &Chr(65+y-x):Next:?Space(x/2.01)&b:b="":Next

```
> 1 votes

# Answer
# Perl 5, 32 bytes

```
say$"x(13-++$k/2),A..$_ for A..Z

```

Try it online!
> 0 votes

# Answer
# C,  ~~84~~  81 bytes

*Thanks to @ceilingcat for saving three bytes!*

```
f(i,j){for(i=1;i++<27;puts(""))for(j=51;j<63-~i/2;)putchar(j++<64-i/2?32:j+i/2);}

```

Try it online!

**Unrolled:**

```
f(i, j) // Using the argument list only to declare the variables.
{
    for (i=1; i++<27; puts(""))
        for (j=51; j<63-~i/2;)
            putchar(j++<64-i/2 ? 32 : j+i/2);
}

```
> 0 votes

# Answer
# Jelly, 12 bytes

```
ØAJ’HU⁶ẋż¹ƤY

```

Try it online!

Uses code very similar to the linked question (further evidence that it is most likely a dupe).

-3 bytes thanks to FlipTack and Jonathan Allan (though indirectly)

## Old version, 15 bytes

```
12Rx2U⁶ẋżØA¹Ƥ¤Y

```

Try it online!
> 0 votes

# Answer
# Canvas, 6 bytes

```
øＺ［∔｝ｒ

```

Try it here!
> 0 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, alphabet
---


title: Find a set of maximal matching edges

text:
# Question
Title: Find a set of maximal matching edges
Consider a connected undirected graph. A matching set of edges on this graph is defined as a set of edges such that no two edges in the set share a common vertex. For example, the left figure denotes a matching set in green, while the right figure denotes a non-matching set in red.

A matching set is said to be `maximally matching`, or a `maximal matching` if it is impossible to add another edge of the graph to the matching set. So both examples above are not maximal matching sets, but both of the sets below in blue are maximal matchings. Note that maximal matchings are not necessarily unique. Furthermore, there's not requirement that the size of each possible maximal matching for a graph is equal to another matching.

The goal of this challenge is to write a program/function to find a maximal matching of a graph.

# Input

Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the graph shown above could be described with the following unordered set of edges (assuming the numbering of vertices starts at 0):

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

```

An alternative way to describe a graph is via an adjacency list. Here is an example adjacency list for the above graph:

```
[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

```

Your program/function must take as input a graph from any source (stdio, function parameter, etc.). You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.

You may assume:

1. The graph is connected (e.g. it is possible to reach any vertex given any starting vertex).
2. There is at least one edge.
3. An edge never connects a vertex directly to itself (ex. the edge `(1,1)` will not be given as input). Note that cycles are still possible (ex.: the above graphs).
4. You may require that the input vertices start at any index (e.g. the first vertex can be 0, 1, -1, etc.).
5. Vertex numbering is sequentially increasing from your chosen starting index (ex.: `1,2,3,4,...`, or `0,1,2,3,...`).

# Output

Your program/function should output a list of edges denoting a maximal matching set. An edge is defined by the two vertices which that edge connects. Ex. output for the left blue set (using the example input vertex ordering):

```
[(1,4), (2,3), (5,6)]

```

Note that the order of the vertices are not important; So the following output describes the same matching set:

```
[(4,1), (2,3), (6,5)]

```

Output may be to stdout, a file, function return value, etc.

# Examples

Here are a few example inputs (using the adjacency list format). These examples happen to start counting vertices at `0`.

Note that no example outputs are given, instead I've included a Python 3 validation code.

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

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

[0:(1,2), 1:(0,2,3,4,5), 2:(0,1), 3:(1), 4:(1), 5:(1)]

[0:(1,2), 1:(0,2,3), 2:(0,1,4), 3:(1,4,5), 4:(2,3), 5:(3)]

```

## Validation Python 3 code

Here's a Python 3 validation code which takes in a graph and set of edges and prints out whether that set is maximally matching or not. This code works with any vertex start index.

```
def is_maximal_matching(graph, edges):
    '''
    Determines if the given set of edges is a maximal matching of graph
    @param graph a graph specified in adjacency list format
    @param edges a list of edges specified as vertex pairs

    @return True if edges describes a maximal matching, False otherwise.
    Prints out some diagnostic text for why edges is not a maximal matching
    '''

    graph_vtxs = {k for k,v in graph.items()}
    vtxs = {k for k,v in graph.items()}

    # check that all vertices are valid and not used multiple times
    for e in edges:
        if(e[0] in graph_vtxs):
            if(e[0] in vtxs):
                vtxs.remove(e[0])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[0]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] in graph_vtxs):
            if(e[1] in vtxs):
                vtxs.remove(e[1])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[1]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] not in graph[e[0]]):
            print('edge (%d,%d): edge not in graph'%(e[0],e[1]))
            return False

    # check that any edges can't be added
    for v in vtxs:
        ovtxs = graph[v]
        for ov in ovtxs:
            if(ov in vtxs):
                print('could add edge (%d,%d) to maximal set'%(v,ov))
                return False

    return True

```

Example usage:

```
graph = {0:[1,2], 1:[0,3,4], 2:[0,3], 3:[1,2,4,5], 4:[1,3], 5:[3,6], 6:[5]}
candidate = [(0,1),(2,3)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6),(0,1)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6)]
is_maximal_matching(graph, candidate) // True

```

# Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins desired.

# Answer
> 9 votes
## CJam (16 chars)

```
{M\{_2$&!*+}/2/}

```

Online demo

This is a greedy approach which accumulates edges which don't have any vertex in common with the previously accumulated edges.

# Answer
> 7 votes
# Pyth, 8 bytes

```
ef{IsTty
       y  power set (gerenate all set of edges)
      t   remove the first one (the first one is
          empty and will cause problems)
 f        filter for sets T satisfying:
     T        T
    s         flatten
  {I          is invariant under deduplicate, i.e. contains no
              duplicating vertices, as the elements represent vertices
e         pick the last one (the power set is ordered from
          smallest to largest)

```

Try it online!

## Specs

* Input: `[(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]`
* Output: `[(1, 4), (2, 3), (5, 6)]`

# Answer
> 6 votes
# Wolfram Language, ~~25~~ 22 bytes

Saved 3 bytes thanks to @MartinEnder

```
FindIndependentEdgeSet

```

This takes input as a `Graph` object (defined as `Graph[{1<->2,2<->3,1<-3>}]` etc.)

# Answer
> 6 votes
# Brachylog, 5 bytes

```
 ⊇.c≠∧

?⊇.cL≠   implicit ? at the beginning;
         ∧ breaks implicit . at the end;
         temporary variable inserted.
?⊇.      input is a superset of output
  .cL    output concatenated is L
    L≠   L contains distinct elements

```

Try it online!

This is guaranteed to be maximal, since Brachylog searches from the largest subset.

# Answer
> 1 votes
# Husk, 10 bytes

```
►LOfoS=uΣṖ

```

Try it online!

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

```
let f =
a=>a.map(b=>r.some(c=>c.some(d=>~b.indexOf(d)))||r.push(b),r=[])&&r

let g = a => console.log("[%s]", f(a).map(x => "[" + x + "]").join(", "))
g([[0,1]])
g([[0,1], [0,2], [1,3], [1,4], [2,3], [3,4], [3,5], [5,6]])
g([[0,1], [0,2], [1,2], [1,3], [1,4], [1,5]])
g([[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [3,5]])
```

Uses the greedy approach for maximal golfiness.

# Answer
> 0 votes
## JavaScript (ES6), ~~68~~ 66 bytes

```
f=a=>a[0]?[a[0],...f(a.filter(b=>!a[0].some(c=>~b.indexOf(c))))]:a
f=([b,...a])=>b?[b,...f(a.filter(c=>!c.some(c=>~b.indexOf(c))))]:a

```

I thought I'd give the recursive approach a go, and by stealing @ETHproduction's set intersection trick I managed to undercut his answer!

I was not the first to misread the original question, and I was about to submit the following recursive function which finds a maximal set of matching edges, rather than a set of maximal matching edges. Subtle difference, I know!

```
f=a=>a.map(([b,c])=>[[b,c],...f(a.filter(([d,e])=>b-d&&b-e&&c-d&&c-e))]).sort((d,e)=>e.length-d.length)[0]||[]

```

Simple recursive approach. For each input element, deletes all conflicting edges from the set and finds the maximal set of matching edges of the remaining subset, then finds the maximal result over each input element. Somewhat inefficient for large sets (9-byte speed-up possible).

# Answer
> 0 votes
# Jelly, ~~12~~ 11 bytes

```
FQ⁼F
ŒPÇÐfṪ

```

Try it online!

Sample input: `[0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]`

Sample output: `[[1, 4], [2, 3], [5, 6]]`

### How it works

```
FQ⁼F    - Helper function, returns 1 if a set of edges is non-matching
F       - Flatten input
 Q      - Remove repeated elements
  ⁼     - Return boolean value. Is this equal to
   F    - The flattened input list

ŒPÇÐfṪ - Main link.
ŒP     - Power set of input list of edges
   Ðf  - Remove all elements which return 1 if
  Ç    - (Helper function) it is a non-matching set
     Ṫ - Get the last element in the resultant list (the longest).
           Always maximal because it is the longest, so any
           edge added would not be in this list (not matching)

```

# Answer
> 0 votes
# Python 3, 68 bytes

```
f=lambda g:len({*sum(g,())})<2*len(g)and max(f(g-{k})for k in g)or g

```

Try it online!

Takes input as set. Recursively removes one item until there are no duplicate vertices. It then returns the set with the most items.

---
Tags: code-golf, graph-theory
---


# Question
Title: Is this string a letter doing a cartwheel?
Challenge inspiration was this that I saw somewhere:

> The word "nun" is just the letter **n** doing a cartwheel

Your challenge is to take a string and determine if it is the first letter doing a cartwheel.

# Rules

A string is a letter doing a cartwheel if:

* The first letter is the same as the last letter. (The letter can't land on its head.)
* The string alternates between cartwheeling letters every one character.

The cartwheeling letters are `n` and `u`, `m` and `w`, `b` and `q`. Note that `n` and `w` together are *not* cartwheeling letters, and neither are `w` and `b`.

* You will take a string using any of our standard input methods.
* You will output a truthy value if the string is a cartwheeling letter, and a falsy value if it is not. Output can be done using any standard output methods.

Additional rules:

* Only lowercase cartwheel letters `n`/`u`/`m`/`w`/`b`/`q` need to be handled.
* You may assume that input is never empty.
* A one-character string is not a valid cartwheel.

# Test cases

```
Input        -> Output
nun          -> truthy
nunun        -> truthy
nunununu     -> falsy
wmw          -> truthy
wmwun        -> falsy
bqbqbqbqbqb  -> truthy
v^v^v        -> falsy
AVAVA        -> falsy
OOO          -> falsy
ununununu    -> truthy
nunwmwnun    -> falsy
nun unun     -> falsy
nunwmw       -> falsy
nnuunnuunnuu -> falsy
nwnwnwnwn    -> falsy
m            -> falsy
nunuuunun    -> falsy

```

# Winner

As with , the shortest code (in each language) wins!

# Answer
> 2 votes
# Jelly, 23 bytes

*This took more work than one might think!*

```
“nmbuwq”iÐ€o⁵IAs2⁼€3,3Ȧ

```

A monadic link taking a list of characters and returning `1` (truthy) or `0` (falsey).

**Try it online!** or see a test suite.

### How?

Finds the index of each character of the input in the 1-indexed list of characters `nmbuwq`. This string is arranged such that the indexes of pairs are three apart, as such the incremental difference of the indexes for valid cartwheels will be repetitions of one of `[-3,3]` or `[3,-3]`.

When an item is not found in a list by the "index of" atom, `i`, it returns `0`, which would pair unfound characters with `b`, making input like `bxbxb` truthy. So `0`s are replaced by `10` a value more than three away from any other value prior to checking for validity.

```
“nmbuwq”iÐ€o⁵IAs2⁼€3,3Ȧ - Link: list of characters, s
         Ð€             - map across c in s:
        i               -   first index of c in (1-indexed; 0 if not present)
“nmbuwq”                -   literal "nmbuwq"
            ⁵           - literal 10
           o            - logical or (vectorises - replace any 0s with 10s)
             I          - incremental differences (i.e. deltas)
              A         - absolute value (vectorises)
               s2       - split into chunks of 2 (possibly with a single remainder)
                   3,3  - pair three with three = [3,3]
                 ⁼€     - equals? for €ach (1 if so, otherwise 0 - including a single 3)
                      Ȧ - any and all? (0 if any 0s or if empty, 1 otherwise)

```

# Answer
> 13 votes
# sed 4.2.2, 30 + 1 `-r` = ~~43~~ 31 bytes

*Saved 12 bytes thanks to @Neil by shortening the first line*

```
/nu|wm|qb/!d
/^((.).)\1*\2$/!d

```

Try it online!

Deletes input if falsey, otherwise does nothing to the input.

### Explanation

With the `-r` flag, we do not need to use `\(` and `\)` for capturing groups and this saves bytes.

```
/nu|wm|qb/!                # On every line that does not match this regex
           d               # Delete
/^((.).)\1*\2$/!           # On every line that does not math
 ^((.).)                   #  the first two characters at the beginning of the line
        \1*                #  repeated
           \2$             #  with the first character at the end of the line
                d          # Delete

```

# Answer
> 8 votes
## JavaScript (ES6), ~~82~~ ~~78~~ 77 bytes

*Saved 1 byte by using two falsy values, as suggested by ThePirateBay and MD XF.*

```
([c,...s],S='bqwmun')=>s.reduceRight((r,a)=>r&a==S[S.search(c)^++k&1],k=s>'')

```

### Test cases

```
let f =

([c,...s],S='bqwmun')=>s.reduceRight((r,a)=>r&a==S[S.search(c)^++k&1],k=s>'')

console.log('Truthy ...')
console.log(f("nun"         )) // -> truthy
console.log(f("nunun"       )) // -> truthy
console.log(f("wmw"         )) // -> truthy
console.log(f("bqbqbqbqbqb" )) // -> truthy
console.log(f("ununununu"   )) // -> truthy

console.log('Falsy ...')
console.log(f("nunununu"    )) // -> falsy
console.log(f("wmwun"       )) // -> falsy
console.log(f("v^v^v"       )) // -> falsy
console.log(f("AVAVA"       )) // -> falsy
console.log(f("OOO"         )) // -> falsy
console.log(f("nunwmwnun"   )) // -> falsy
console.log(f("nun unun"    )) // -> falsy
console.log(f("nunwmw"      )) // -> falsy
console.log(f("nnuunnuunnuu")) // -> falsy
console.log(f("m"           )) // -> falsy
```

# Answer
> 5 votes
# Python 3, 111 bytes

*-2 bytes thanks to Mr. Xcoder.*

```
lambda s:s[0]==s[-1]and any(any({*s[::2]}=={i[j]}and{*s[1::2]}=={i[j<1]}for j in[0,1])for i in['nu','mw','bq'])

```

Try it online!

# Answer
> 5 votes
# Python 3, 71 bytes

```
lambda n:''.join(sorted({*n[1::2]}|{*n[::2]}))in"nu,mw,bq"*(n==n[::-1])

```

Try it online!

*-1 thanks to @HyperNeutrino and **-13** thanks to @ovs*

If the above is found to fail for any test case, there is an alternative:

```
lambda n:(sorted(list({*n[1::2]}.union({*n[::2]})))in[[*'nu'],[*'mw'],[*'bq']])*n[0]==n[-1]

```

Try it online!

---

# Explanation

* `''.join(sorted(list({*n[1::2]}).union({*n[::2]}))))` \- Gets the characters at odd indexes and the characters at even indexes, de-duplicates them and sorts the list formed by their union.
* `in'nu,mw,bq'` \- Checks if they are valid cart-letter combinations.
* `n[0]==n[-1]` \- Checks if the first character is the same as the last one.

# Answer
> 5 votes
# Python 2, 63 bytes

```
lambda s:s[:3]in'ununqbqbwmwm'and s==s[:2]*max(len(s)/2,1)+s[0]

```

Try it online!

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

```
s=>/^(nu|un|bq|qb|wm|mw)+$/.test(s+s[1])

```

Checks to see if the input string concatenated with the second character of the input string is a repeating string of the same pair of cartwheel characters.

Tests:

```
[
  "nun",
  "nunun",
  "nunununu",
  "wmw",
  "wmwun",
  "bqbqbqbqbqb",
  "v^v^v",
  "AVAVA",
  "OOO",
  "ununununu",
  "nunwmwnun",
  "nun unun",
  "nunwmw",
  "nnuunnuunnuu",
  "nwnwnwnwn",
  "m",
  "nunuuunun"
].forEach( x=>console.log( x, (s=>/^(nu|un|bq|qb|wm|mw)+$/.test(s+s[1]))(x) ) )
```

# Answer
> 4 votes
# Retina, 24 bytes

```
G`nu|mw|bq
^((.).)\1*\2$

```

Outputs 1 for truthy, 0 for falsy.

Port of Cows quack's answer.

Try it online!

# Answer
> 4 votes
## Haskell, ~~80~~ 78 bytes

```
f s|l<-length s=odd l&&l>1&&any((==s).take l.cycle)(words"un nu mw wm bq qb")

```

Try it online!

How it works:

```
l<-length s        -- let l be the length of the input string

f s         =      -- return True, if
    odd l          -- l is odd and
    l > 1          -- l is greater than 1 and
    any            -- any of the following is also True
      (     )(words "  ...  ")
                   -- apply the function to each of the words "un", "nu" ... "qb"
           cycle   --  infinitely repeat the word
      take l       --  take the first l characters
     (==s)         --  and compare to s

```

# Answer
> 4 votes
# Clojure, 156 bytes

```
(fn[w](let[s["nu""wm""bq"]c #(= 1(count(set %)))e #(take-nth 2 %)r #(and(c(e %))(c(e(drop 1 %))))](and(=(first w)(last w))(r w)(some #(=(set w)(set %))s))))

```

This was deceptively difficult! I ended up having to break it down into 3 sub problems:

* Is the first letter the same as the last?
* Do the letters repeat?
* Are all the letters a part of one of the valid sets?

I certainly didn't win, but this was a good morning exercise! Full explanation below:

```
(defn cartwheel? [word]
  (let [; Valid Character Sets
        cs ["nu" "wm" "bq"]

        ; Is the list composed of only a single character?
        count-1? #(= 1 (count (set %)))

        ; Grabs every other element of the list
        every-other #(take-nth 2 %)

        ; Do the characters repeat? Works by checking if every other element is the same, then drops the first letter
        ; to check all the odd indexed characters
        repeating? #(and (count-1? (every-other %))
                         (count-1? (every-other (drop 1 %))))]

    ; Do all the predicates hold?
    (and (= (first word) (last word))
         (repeating? word)
         ; Is the set of letters in the word part of some set of the valid characters?
         (some #(= (set word) (set %)) cs))))

```

# Answer
> 4 votes
# Python 2, 45 bytes

```
lambda s:s[2:]+s[1:3]==s>s[:2]in'bqbunuwmw'

```

Try it online!

The spaces in the string are `DEL` characters.

# Answer
> 3 votes
## Grime, 28 bytes

```
e`..-#!"nu\|bq\|mw"oTv&..v+.

```

Try it online! Prints `1` for truthy inputs and `0` for falsy ones.

## Explanation

Grime syntax resembles regular expressions, and a Grime program specifies a pattern that may or may not match a rectangle of characters.

```
e`..-#!"nu\|bq\|mw"oTv&..v+.
e`                            Match input against pattern:
      !                       Does not
     #                        contain
  ..                          a 2-character substring
    -                         which is not
       "nu\|bq\|mw"           any of these strings
                   oT         potentially reversed,
                     v&       AND
                       ..     two characters
                         v+   one or more times
                           .  then one more character.

```

Some features of Grime that helped shorten this:

* Normally a character literal must be escaped with a backslash, but `""` changes this: syntax elements are escaped but literals are not. Without the quotes, the part that enumerates the character pairs would be `(\n\u|\b\p|\m\w)oT`.
* Unary operators that follow a binary operator (here `-`) act on its result: `..-#!"…"oT` is equivalent to `(..-"…"oT)#!`.
* The `v`s lower the precedence of the syntax elements that follow them. A lone `&` has higher precedence than `-`, but `v&` has lower. Similarly, `..+` is parsed as `.(.+)`, but `..v+` is equivalent to `(..)+`.

# Answer
> 2 votes
# Python 2, 103 bytes

```
lambda x:len(x)>1and{x[0],x[1]}in[{i,j}for i,j in zip('ubw','nqm')]and x==(-~len(x)/2*(x[0]+x[1]))[:-1]

```

Try it online!

# Answer
> 2 votes
# Japt, 47 bytes

```
g ¦U¬o ª`q¿nwm`ò má c aU¯2)<0?0:UÅë ä¥ ©Uë ä¥ e

```

Try it online!

# Answer
> 2 votes
# Pyth, 27 bytes

```
&qeQhQ/"nu,mw,bq"S+{%2tQ{%2

```

Test Suite.

Outputs `1` for truthy and `False` or `0` for falsy, as the OP allowed in chat.

# Answer
> 2 votes
# Jelly, 27 bytes

```
Ḋm2Qµ³m2Q;Ṣe“nu“mw“bq”ȧ³⁼U¤

```

Try it online!

# How it works

```
Ḋm2Qµ³m2Q;µṢe“nu“mw“bq”ȧ³⁼U¤  Main link; z is the argument
Ḋ                             z[1:]
 m2                           z[1::2]
   Q                          deduplicate(z[1::2])
    µ                         New Chain
     ³                        z
      m2                      z[::2]
        Q                     deduplicate(z[::2])
         ;                    deduplicate(z[1::2]) + deduplicate(z[::2])
          Ṣ                  Sort the result
           e                 Is it an element of the following?
            “nu“mw“bq”       ["nu", "mw", "bq"]
                      ȧ      It has the correct characters and:
                       ³  ¤  Nilad followed by links as nilad
                       ³     z
                        ⁼      ==
                         U        z[::-1]
                          ¤  [End chain]

```

# Answer
> 2 votes
# Python 2, 69 bytes

```
lambda x:any([x in p*len(x)for p in'nu','mw','bq'])*len(x)%2*len(x)>2

```

Try it online!

# Answer
> 1 votes
# Python 3, 88 bytes

```
lambda x:[len(x)%2,x[:2]in'nu,un,bq,qb,mw,wm',len(set(x[::2])),len(set(x[1::2]))]==[1]*4

```

`len(x)%2`: an even-length string can't end on the first character

`x[:2] in`: check for any of the 6 valid beginning pairs

`len(set())`: get the length of the sets of characters at 0,2,4... and 1,3,5...

Returns `True` if the list of evaluations is equal to \[1,1,1,1\], else `False`.

Try it online!

# Answer
> 1 votes
# Perl 5, 55 + 1 (-p) = 56 bytes

```
$c={"nuunmwwmbppb"=~/./g}->{$l=chop};$_=/^($l$c)+$/&&$c

```

Try it online!

Prints the "upside down" version of the first character for true, nothing for false.

# Answer
> 1 votes
# MATL, 25 bytes

```
'nuwmbq'&mq2&\d~wdts~Gnqv

```

The ouput is a non-empty numeric column vector, which is truthy if all its entries are nonzero, and falsy otherwise. **Try it online!**

To **verify all test cases**, an `if` branch is added in the footer that replaces any truthy value by the string `'truthy'`, or any falsy value by the string `'falsy'`, and then displays the string.

### Explanation

```
'nuwmbq'  % Push this string
&m        % Implicit input. For each char, push index of membership in the above
          %  string, or 0 if not member
q         % Subtract 1
2         % Push 2
&\        % Divmod. Pushes remainders, then quotients
d~        % Consecutive differences negated. Gives an array of ones iff all
          % quotients were equal
w         % Swap. Moves remainders to top
d         % Consecutive differences. Gives nonzeros iff no consecutive
          % remainders were equal
ts~       % Duplicate, sum, negate. Gives true iff sum was 0. For unequal
          % consecutive differences of remainders, this corresponds to an odd
          % number of remainders
Gnq       % Push input, length, subtract 1. True iff input longer than 1
v         % Concatenate into column vector. Truthy iff all entries are nonzero

```

# Answer
> 1 votes
# PHP, 59+1 bytes

```
<?=preg_match('#^(nu|un|mw|wm|bq|qb)\1+$#',$argn.$argn[1]);

```

Run as pipe with `-F`.

partly regex solution, 101+1 bytes:

```
for($s=$argn;$c=$s[$i++];$p=$c)$c!=$p||die;echo$i%2<1&&preg_match("#^(nu|mw|bq)#",count_chars($s,3));

```

Empty output for falsy. Run as pipe with `-nR`.

# Answer
> 1 votes
# Java 8, 57 bytes

```
s->s.matches("(nu)+n|(un)+u|(mw)+m|(wm)+w|(bq)+b|(qb)+q")

```

Try it here.

Simple regex to match all six cases. Note that Java's `String#matches` automatically matches the entire String, so there is no need for `^...$`.

# Answer
> 0 votes
# Python 2, 74 bytes

```
import re
re.compile('(n(un)+|u(nu)+|m(wm)+|w(mw)+|b(pb)+|p(bp)+)$').match

```

Try it online! This take on the problem is surprisingly competitive.

# Answer
> 0 votes
# Clojure, 115 bytes

```
(apply some-fn(map(fn[r]#(re-matches r %))(map(fn[[x y]](re-pattern(str x"("y x")+")))["nu""un""mw""wm""bq""qb"])))

```

Build a regex out of each letter pair and see if the input matches one. Lots of more elegant ways to do all of these parts, but they're all more verbose. Such is life with Clojure golfing.

# Answer
> 0 votes
# Perl 5, 68 + 1 = 69 bytes

```
if(/../&&$&=~/nu|un|bq|qb|mw|wm/){s/^($&)*//;$&=~/./;print if/^$&$/}

```

Run with `-n`.

Explanation:

```
# Match the first two characters, and if they exist, then...
if (/../ &&
 # Make sure they are a pair of compatible cartwheel characters.
 $&=~/nu|un|bq|qb|mw|wm/) {
  # If that's true, then eliminate as many of that pair of characters
  # from the beginning of the string as possible.
  s/^($&)*//;
  # Then get the first character out of the match (the first character
  # of the original string).
  $&=~/./;
  # Print the text (which is truthy since it's nonempty) if the original
  # first character matches exactly the remaining string.
  print if/^$&$/
  # Otherwise, print nothing (the empty string in Perl is falsy).
}

```

# Answer
> 0 votes
## TXR Lisp, 50 bytes

```
(f^$ #/n(un)+|u(nu)+|m(wm)+|w(mw+)|b(qb)+|q(bq)+/)

```

Run:

```
1> (f^$ #/n(un)+|u(nu)+|m(wm)+|w(mw+)|b(qb)+|q(bq)+/)
#<intrinsic fun: 1 param>
2> [*1 "nun"]
"nun"
3> [*1 "nuns"]
nil
4> [*1 "mwm"]
"mwm"
5> [*1 "wmw"]
"wmw"
6> [*1 "abc"]
nil

```

`f^$` is a combinator which takes a regex object and returns a function which matches that regex in an anchored way. (By itself, a regex object is function-callable object which takes a string and searches for itself through it.)

# Answer
> 0 votes
# Python 3, 66 bytes

```
lambda x:x==len(x)//2*x[:2]+x[0]and{*x}in[{*'nu'},{*'mw'},{*'bq'}]

```

Try it online!

# Answer
> 0 votes
## TXR: ~~78~~ 74 bytes

```
@{x 2}@(rep :gap 0)@x@(end)@y
@(bind(x y)(#"nu un mw wm bq qb"@[x 0..1]))

```

Run, from system prompt. Number in prompt is termination status: 0 = success, 1 = failure:

```
0:$ ./txr cart.txr
nun
0:$ ./txr cart.txr
abc
1:$ ./txr cart.txr
bab
1:$ ./txr cart.txr
mwm
1:$ ./txr cart.txr
nununununun
0:$

```

Explanation:

* `@{x 2}`: match two characters, bind to `x` variable.
* `@(rep :gap 0)@x@(end)`: repeated match with no skipped gaps: zero or more occurrences of `x`, the previously matched digraph.
* `@y`: remainder of line matched, captured into `y`.
* `@(bind(x y)(foo bar))`: bind `x` to `foo`, y to `bar`. Since `x` and `y` are already bound, they have to match `foo` and `bar`, or else there is a failure.
* `foo` is `#"nu un mw wm bq qb"`, a word list literal, syntactic sugar for the Lisp list `("nu" "un" ... "qb")`. A `bind` match between a variable and a list means that the variable must match an element.
* `bar` is `@[x 0..1]`: the one-character substring of `x` from its beginning. The `bind` match between `y` and this forces the last letter of the line to match the first.

# Answer
> 0 votes
## C++, 268 bytes

```
#include<map>
#include<string>
std::map<char,char>c{{'n','u'},{'m','w'},{98,'q'},{'w','m'},{'u','n'},{'q',98}};
int w(std::string s){if(s[0]!=s[s.size()-1]||c.find(s[0])==c.end()||s.size()<3)return 0;for(int i=0;i<s.size()-1;i+=2)if(s[i+1]!=c[s[i]])return 0;return 1;}

```

# Answer
> 0 votes
# JavaScript (ES6), 63 bytes

```
s=>/bq|wm|un/.test(s)&s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

```

Returns `1` or `0`.

**Explanation**

All cartwheel strings will have one or more of **bq**, **wm**, or **un**. We test for that with:

```
/bq|wm|un/.test(s)

```

If you replace all instances of the first two letters of a cartwheel string with nothing, you're left with the first letter of the string. We test for that with:

```
s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

```

```
let f=
s=>/bq|wm|un/.test(s)&s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

console.log(f('nun'))          // truthy
console.log(f('nunun'))        // truthy
console.log(f('nunununu'))     // falsy
console.log(f('wmw'))          // truthy
console.log(f('wmwun'))        // falsy
console.log(f('bqbqbqbqbqb'))  // truthy
console.log(f('v^v^v'))        // falsy
console.log(f('AVAVA'))        // falsy
console.log(f('OOO'))          // falsy
console.log(f('ununununu'))    // truthy
console.log(f('nunwmwnun'))    // falsy
console.log(f('nun unun'))     // falsy
console.log(f('nunwmw'))       // falsy
console.log(f('nnuunnuunnuu')) // falsy
console.log(f('nwnwnwnwn'))    // falsy
console.log(f('m'))            // falsy
```

# Answer
> 0 votes
# Japt, 28 bytes

```
`wmq¿n`pw ò øU¯2)«(U+g1)rU¯2

```

Test it online!

### Explanation

```
`wmq¿n` pw ò øU¯  2)«  (U+ g1)rU¯  2
"wmqbun"pw ò øUs0,2)&&!(U+Ug1)rUs0,2
                                       Implicit: U = input string
"wmqbun"                               Take this string.      "wmqbun"
        pw                             Append its reverse.    "wmqbunnubqmw"
           ò                           Form into groups of 2. ["wm","qb","un","nu","nq","mw"]
             ø     )                   Check whether this contains
              Us0,2                      the first two chars of U.
                        U+             Take U and append
                       (  Ug1)           the second char of U.
                              r        Remove all copies of
                               Us0,2     the first two chars of U.
                                       This returns "" iff U has the pattern "xyxyxyx".
                      !                Take the logical NOT: true iff the result is "".
                    &&                 Return whether both of these conditions are true.
                                       Implicit: output result of last expression

```

# Answer
> 0 votes
# Javascript, 58 bytes

```
s=>/^((nu)+n|(un)+u|(mw)+m|(wm)+w|(bq)+b|(qb)+q)$/.test(s)

```

Tests string for all possible cartwheel strings. Port of this Java answer

# Answer
> 0 votes
# C (gcc), ~~91~~ 90 bytes

Fixed to support strings longer than 255 bytes, which also saves a byte.

```
f(i){char*s=i,*p=strchr("nunmwmbqb",*s);for(i=0;p&&*s;p=p[i++%2]^*s++?0:p);i=i^1&&i&1&&p;}

```

Try it online!

# Answer
> 0 votes
# Japt, 20 bytes

```
Êu *`q¿nwm`pÔò d@¥îX

```

Try it

```
Êu *`...`pÔò d@¥îX     :Implicit input of string U
Ê                      :Length
 u                     :Mod 2
   *                   :Times
    `...`              :  Compressed string "wbunwm"
         p             :  Append
          Ô            :    Reverse
           ò           :  Partitions of length 2
             d         :  Any true
              @        :  When passed through the following function as X
               ¥       :    Test U for equality with
                îX     :    X repeated and sliced to length of U

```

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


# Question
Title: How to print the below format in the fewest bytes?
This challenge is inspired by this, now deleted question.

---

Take a positive integer **N** as input, and output a matrix with the numbers **1 .. N2** that follows the pattern below:

Fill in the first row with **1 .. N** then fill the last row (row number **N**) with **(N+1) .. 2N**, then fill the second row with **(2N+1) .. 3N** and continue until you have filled all rows.

The output format is flexible, so list of lists etc. are accepted.

```
N = 1
1

N = 2
1  2
3  4

N = 3
1  2  3
7  8  9
4  5  6

N = 4
 1  2  3  4
 9 10 11 12
13 14 15 16
 5  6  7  8

N = 5
 1  2  3  4  5
11 12 13 14 15
21 22 23 24 25
16 17 18 19 20
 6  7  8  9 10

```

Standard rules apply. Shortest answer in bytes in each language wins. Explanations are encouraged as always.

# Answer
> 7 votes
# 05AB1E, ~~13~~ 8 bytes

Saved 5 bytes thanks to *Rod*

```
nLôÂ«āÉÏ

```

Try it online!

**Explanation**

```
n           # push input^2
 L          # push range [1 ... input^2]
  ô         # split into pieces each the size of the input
   Â«       # append the reverse of this 2D-list
     ā      # push range [1 ... len(list)]
      É     # check each element for oddness
       Ï    # keep only the elements in the 2D list which are true in this list

```

# Answer
> 5 votes
# Ruby, 53 bytes

```
->n{r=*1..n*n;n.times{|x|p r.slice!(r[x*=n]?x:-n,n)}}

```

## Explanation:

Put all the numbers into a single array first, then slice the array skipping a line for each iteration. After the first (n/2+n%2) iterations there is nothing left to skip, then get all the remaining lines backwards.

Try it online!

# Answer
> 4 votes
# Python 2, 75 bytes

```
def f(n):a=range(n);print[[i*n-~j for j in a]for i in a[::2]+a[~(n%2)::-2]]

```

Try it online!

# Answer
> 4 votes
# JavaScript, 68 bytes

*Edit* 3 bytes saved, whetted by @user71546

~~First try,~~ following the obvious route: count from 1 and fill the array from both sides, from outer to inner

```
n=>(v=0,q=[...Array(n)]).map((_,i)=>q[i&1?--n:i/2]=q.map(_=>++v))&&q

```

**Test**

```
var F=
n=>(v=0,q=[...Array(n)]).map((_,i)=>q[i&1?--n:i/2]=q.map(_=>++v))&&q

function test() {
  var n=+N.value;
  O.innerHTML = '<tr><td>'
  +F(n).map(r=>r.join('</td><td>')).join('</td></tr><tr><td>')
  +'</td></tr>'
}

test()
```

```
#O { margin: 1em }
td { text-align: right }
```

```
<input id=N type=number min=1 value=5 oninput='test()'>
<table id=O>
```

# Answer
> 3 votes
# \>\<\>, ~~51+3=54~~ 47 bytes

```
:&v
?!\1-:&:&*}}r:
 ~\
!~>1+::n&:&%:a84*@@?$~o?

```

Try it online!

Input is expected on top of the stack at program start using the `-v` flag. Output consists of non-aligned numbers separated by single spaces, and each line is separated by a single newline. Example output for `N=5`:

```
1 2 3 4 5
11 12 13 14 15
21 22 23 24 25
16 17 18 19 20
6 7 8 9 10

```

... followed by a single newline. Program terminates with an error (`something smells fishy...`), but that's on STDERR rather thatn STDOUT.

**Explaination:**

The first line simply stores a copy of `N` in the register.

The second line builds up the offset for each output row by subtracting 1 from `N`, multiplying this by `N`, rotating it to the bottom of the stack and then reversing the entire stack. When the number on top of the stack reaches 0, the stack should look like this (example uses `N=5`):

```
5 15 20 10 0 0

```

The third line discards the duplicate `0` from the top of the stack.

The fourth line increments the top of the stack and outputs a copy of it. This is then taken mod `N`, and this is used to decide if a space or newline should be printed, and if the top of the stack should be discarded - if last number printed is `x`, then `x mod N == 0` indicates that the end of that output row has been reached. Execution ends when `1+` gets executed on an empty stack, throwing the termination error.

**Previous version**

This explicitly checked for an empty stack to end execution, and I was also including 3 bytes for the `-v` flag usage.

```
:&v
?!\1-:&:&*}}r:
 ~\
!;>1+::n&:&%:a84*@@?$~o?!~l?

```

Try it online!

# Answer
> 3 votes
# Haskell, 62 bytes

```
(0#)
m#n|m>=n^2=[]|k<-m+n=[m+1..k]:(k+n)#n++[[k+1..k+n]|k<n^2]

```

Try it online! Output is a list of lists, e.g. `(0#) 3` yields `[[1,2,3],[7,8,9],[4,5,6]]`.

# Answer
> 3 votes
# Perl 5, `-p` ~~52~~ 51 bytes

```
#!/usr/bin/perl -p
map{$|--?$\="@0
".$\:say"@0";$_+=@0for@0}@0=1..$_}{

```

Try it online!

# Answer
> 2 votes
## JavaScript (ES6), ~~69~~ 68 bytes

```
n=>[...Array(n)].map((_,i,a,j=((i*=2)<n?i:n+n+~i)*n)=>a.map(_=>++j))

```

~~Well it got outgolfed before I could post it but here it is anyway.~~ Edit: Saved 1 byte thanks to @KevinCruijssen.

# Answer
> 2 votes
# Java (OpenJDK 9), 101 bytes

```
n->{int x[][]=new int[n][n],i=0,j;for(;i<n;i++)for(j=0;j<n;)x[i%2<1?i/2:n+~i/2][j]=++j+i*n;return x;}

```

Try it online!

### Credits

# Answer
> 2 votes
# Jelly, ~~13~~ ~~...~~ 6 bytes

Thanks *JonathanAllan* for -1 byte!

```
²sm0m2

```

Try it online!

---

Use an identical algorithm to the 05AB1E answer.

# Answer
> 2 votes
# , ~~70~~ ~~59~~ 47 bytes

```
function(n)matrix(1:n^2,n,,T)[c(1:n,n:1)*!0:1,]

```

Try it online!

Thanks to Robin Ryder for a 4 byte golf, which I then golfed further.

Returns a matrix; constructs the `matrix` in sequence, e.g., `[[1 2 3] [4 5 6] [7 8 9]]`, then rearranges the rows.

# Answer
> 2 votes
# Jelly, 10 bytes

```
²ss2Ṛj@/Fs

```

Try it online!

### How it works

```
²ss2Ṛj@/Fs  Main link. Argument: n

²           Square; yield n².
 s          Split; promote n² to [1, ..., n²] and split it into chuks of length n.
  s2        Split 2; generate all non-overlapping pairs of chunks.
            If n is odd, this leaves a singleton array at the end.
    Ṛ       Reverse the order.
     j@/    Reduce by join with reversed arguments.
            In each step, this places the first and second element of the next pair
            at the top and bottom of the accumulator.
        Fs  Flatten and split to restore the matrix shape.

```

# Answer
> 2 votes
# Stax, 10 bytes

```
│æ╘▐⌡r▌═∟Y

```

Run and debug it online

The corresponding ascii representation of the same program is 12 characters.

```
JRx/r{]+rFmJ

```

Here's how it works.

```
JR              range [1 .. x^2] where x=input
  x/            split into subarrays of size x
    r           reverse
     {   F      for each subarray, execute block
      ]+r       concat array, and reverse result
          m     for each row, output ...
           J        each subarray joined by spaces

```

# Answer
> 1 votes
# Python 2, ~~72~~ ~~68~~ 63 bytes

-4 bytes thanks to Neil

```
def f(n):w=zip(*[iter(range(1,n*n+1))]*n);print(w+w[::-1])[::2]

```

Try it online!

# Answer
> 1 votes
# C++ + Range V3, 159 bytes

```
#include<range/v3/all.hpp>
using namespace ranges::view;

[](int n){auto r=iota(1,n*n+1)|chunk(n);return concat(r|stride(2),r|reverse|drop(n%2)|stride(2));}

```

Live on Wandbox

Not counting the 2 newlines after `using namespace range::view`; they are just there to separate imports from the lambda.

Mildly interesting fact: this solution makes no heap allocations. It solves the problem in `O(1)` space.

---

Explanation:

1. `iota(1, n*n+1)` -\> `[1 ... n*n]`
2. `chunk(n)`: every `n` elements together, so `[1 ... n] [n+1 ... 2*n] ...`
3. Call that `r`
4. `r | stride(2)`: take every other element: `[1 ... n] [2*n+1...] ...`
5. concatenate that with:
6. `r | reverse | drop(n % 2)`: reverse, then drop the `[1 ... n]` term if `n` is odd (there'll be an odd number of rows and we only want to print the first term once). It seems like I should be able to just do `r | reverse | take`, but that doesn't work for some reason.
7. `stride(2)` again, take every other element. This time it's in reverse.

More readable, and testable:

```
#include <range/v3/all.hpp>
using namespace ranges::view;

auto f(int n)
{
    auto rows = iota(1, n * n + 1)
        | chunk(n);
    return concat(
        rows | stride(2),
        rows
            | reverse
            | drop(n % 2)
            | stride(2));
}

#include <iostream>
int main(int argc, char** argv)
{
    std::cout << "N = " << argc << '\n';
    auto res = f(argc);

    for (auto const& row : res | bounded) {
        for (auto const& elem : row | bounded) {
            std::cout << elem << ' ';
        }
        std::cout << '\n';
    }
}

```

# Answer
> 1 votes
# Octave, 102 bytes

```
n=input('');A=B=vec2mat(1:n*n,n);i=j=0;do
B(++i,:)=A(++j,:);if++j<n
B(n-i+1,:)=A(j,:);end;until j>=n
B

```

Try it online!

# Answer
> 1 votes
# C (gcc), 110 bytes

```
i,c,t,b;f(a,n)int*a;{for(b=n-1;i<n*n;t++,b--){for(c=0;c<n;)a[t*n+c++]=++i;for(c=0;c<n&i<n*n;)a[b*n+c++]=++i;}}

```

Try it online!

Fills out an array by alternating between 2 indices for rows: one index starting at the top and one starting at the bottom. The top row index starts at 0 and is incremented every 2 rows; the bottom row index starts at n-1 and is decremented every 2 rows.

Ungolfed:

```
void f(int* a, int n)
{
    //i = value to be written [1,n]; c = column index; t = top row index; b = bottom row index
    for(int i=1, c=0, t=0, b=n-1;
        i <= n*n; //when i = n*n, we have written all the values and we're done
        t++, b--) //t increments every 2 rows, b decrements every 2 rows
    {
        //write out 2 rows per loop

        //first row: fill out row at t
        for(c=0; c<n; c++, i++)
            a[t*n+c]=i;

        //second row: fill out row at b
        //this step will be skipped on the final loop for odd values of n, hence the (i<=n*n) test
        for(c=0; c<n && i<=n*n; c++, i++)
            a[b*n+c]=i;
    }
}

```

# Answer
> 1 votes
# APL (Dyalog Extended), 19 bytes (SBCS)

Anonymous tacit prefix function.

```
(⍋1∘+|-\⍤⍳)⊇,⍨⍴∘⍳×⍨

```

Try it online!

`×⍨` self-multiplicate (i.e. square **N**)

`∘⍳`**ɩ**ndices one through that, then:

…**r**eshape to the following shape:

`,⍨` self-concatenate (i.e. \\$N\\$-by-\\$N\\$ matrix)

`(``)⊇` permute the rows into the following order:

`∘⍳`**ɩ**ndices one through \\$N\\$, then

`-\` alternating sum; \\$\big\\{1,(1-2),(1-2+3),(1-2+3-4),…,(1-2+3-…\pm N)\big\\}=\Big\\{1,-1,2,-2,…,\pm\big\lfloor\frac{N}2\big\rfloor\Big\\}\\$

…`|` division remainder when divided by:

`1∘+` the incremented \\$N\\$

grade (permutation that would sort)

# Answer
> 0 votes
# Jelly, 11 bytes

```
s2ZU2¦Ẏị²s$

```

Try it online!

# Answer
> 0 votes
# CJam, 22 bytes

```
ri__*,:)/2/z[1W].{%:p}

```

Try it online!

# Answer
> 0 votes
# C (gcc) ~~80~~ ~~78~~

I see now this solution is wrong

```
i;f(n){for(i=0;i++<n*n;printf("\n%3d"+!!(~-i%n),i>n?n+(i+n>n*n?i%n?:n:i):i));}

```

Try it online!

# Answer
> 0 votes
# C (gcc), 36+8+61 = 105 bytes

compile with `-Dp=printf("%d ",i),i++%n;);puts("")` `-Dq=i,n)`

```
f(q{g(1,i);}g(q{for(;p;i<n*n&&h(q;}h(q{for(n+i<n*n&&g(n+q;p;}

```

Try it online!

# Answer
> 0 votes
# Japt, 10 bytes

Outputs a 3D array; add `c1` at the end for `+2` bytes to flatten by one level.

```
²õ òU ó oÔ

```

Try it

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


title: Maximum sub-array

text:
# Question
Title: Maximum sub-array
Define the "maximum sub-array" of a given array as "a (consecutive) sub-array that has the biggest sum". Note there's no "non-zero" requirement. Output that sum.

Give a description of your code if possible.

Sample input 1:

```
1 2 3 -4 -5 6 7 -8 9 10 -11 -12 -13 14

```

Sample output 1: `24`

Description 1:
The biggest sum is yielded by cutting `6 7 -8 9 10` out and summing up.

Sample input 2: `-1 -2 -3`
Sample output 2: `0`
Description 2: It's simple :) An empty subarray is the "biggest".

Requirement:

* Don't read anything except stdin, and output should go to stdout.
* Standard loopholes **restrictions** apply.

Ranking: The shortest program wins this .

# Answer
> 10 votes
# Husk, ~~6~~ 4 bytes

```
▲ṁ∫ṫ

```

Try it online!

```
      -- implicit input (list) xs  - eg. [-1,2,3]
   ṫ  -- get all tails of xs       -     [[-1,2,3],[2,3],[3],[]]
 ṁ∫   -- map & concat cumsum       -     [0,-1,1,4,0,2,5,0,3,0]
▲     -- get maximum               -     5

```

# Answer
> 6 votes
# Python 3, 61 bytes

```
a=b=0
for x in eval(input()):a=max(x,a+x);b=max(a,b)
print(b)

```

Try it online!

Algorithm stolen from Wikipedia.

# Answer
> 4 votes
# Jelly, 6 bytes

```
ẆS€;0Ṁ

```

Try it online!

# Answer
> 4 votes
# Pyth, 8 bytes

```
eS+0sM.:

```

**Try it online!**

---

# How?

```
eS+0sM.:Q - Q is implicit, meaning input. Let's say it's [-1, -2, -3].

      .:  - All contiguous non-empty sublists. We have [[-1], [-2], [-3], [-1, -2], [-2, -3], [-1, -2, -3]].
    sM    - Get the sum of each sublist. [-1, -2, -3, -3, -5, -6]
  +0      - Append a 0 to the sum list. [0, -1, -2, -3, -3, -5, -6]
eS        - Maximum element. S gives us [-6, -5, -3, -3, -2, -1, 0], while e returns 0, the last element.

```

# Answer
> 4 votes
# 05AB1E, 4 bytes

```
ÎŒ0M

```

Try it online!

-1 thanks to Adnan.

# Answer
> 4 votes
# Haskell, 28 bytes

```
maximum.scanl((max<*>).(+))0

```

Try it online!

# Answer
> 3 votes
## C++, ~~197~~ ~~195~~ 187 bytes

-10 bytes thanks to Zacharý

```
#include<vector>
#include<numeric>
int f(std::vector<int>v){int i=0,j,t,r=0;for(;i<v.size();++i)for(j=i;j<v.size();++j){t=std::accumulate(v.begin()+i,v.begin()+j,0);if(t>r)r=t;}return r;}

```

# Answer
> 3 votes
# , 54 bytes

```
a=b=0;for(x in scan()){a=max(x,a+x);b=max(a,b)};cat(b)

```

Try it online!

Algorithm taken from: Maximum subarray problem

# , 65 bytes

```
y=seq(x<-scan());m=0;for(i in y)for(j in y)m=max(m,sum(x[i:j]));m

```

Try it online!

* Read `x` from stdin.
* Set `y` as index of `x`.
* Iterate twice over all possible nonempty subsets.
* Compare sum of a subset with `m` (initially `m=0`).
* Store maximum value in `m`.
* Print value of `m`.

# , 72 bytes

```
n=length(x<-scan());m=0;for(i in 1:n)for(j in i:n)m=max(m,sum(x[i:j]));m

```

Try it online!

* Read `x` from stdin.
* Do a full search over all possible nonempty subsets.
* Compare sum of a subset with `m` (initially `m=0`).
* Store maximum value in `m`.
* Print value of `m`.

# Other unsuccessful ideas

## 58 bytes

```
Reduce(max,lapply(lapply(seq(x<-scan()),tail,x=x),cumsum))

```

## 63 bytes

```
Reduce(max,lapply(seq(x<-scan()),function(i)cumsum(tail(x,i))))

```

## 72 bytes

```
m=matrix(x<-scan(),n<-length(x),n);max(apply(m*lower.tri(m,T),2,cumsum))

```

# Answer
> 2 votes
# 05AB1E, 4 bytes

-2 bytes thanks to Adnan

```
ÎŒOM

```

Try it online!

# Answer
> 2 votes
# Mathematica, 24 bytes

```
Max[Tr/@Subsequences@#]&

```

# Answer
> 2 votes
# Haskell, 41 33 bytes

```
import Data.List
g=maximum.concatMap(map sum.inits).tails

```

```
maximum.(scanl(+)0=<<).scanr(:)[]

```

Try it online! thanks to Laikoni

# Answer
> 1 votes
# Gaia, 6 bytes

```
0+ḋΣ¦⌉

```

Try it online!

# Answer
> 1 votes
# Ruby, ~~61~~ ~~59~~ 57 bytes

I just started learning Ruby, so this is what I came up with.

```
s=0
p [gets.split.map{|i|s=[j=i.to_i,s+j].max}.max,0].max

```

I first saw this algorithm at the Finnish version of this unfinished book. It is very well explained at the page 23.

Try it online!

# Answer
> 1 votes
# , 14 bytes

```
|/,/+\'(1_)\0,

```

Try it online!

```
            0, /prepend a zero (in case we're given all negatives)
       (1_)\   /repeatedly remove the first element, saving each result
    +\'        /cumulative sum over each result, saving each result
  ,/           /flatten (fold concat)
|/             /maximum (fold max)

```

# Answer
> 1 votes
# Japt, 11 bytes

```
£ãY mxÃc rw

```

Try it online!

## Explanation

```
£ãY mxÃc rw
m@ãY mx} c rw   // Ungolfed
m@     }        // Map the input array by the following function, with Y=index
  ãY            //   Get all subsections in input array length Y
     mx         //   Sum each subsection
         c rw   // Flatten and get max

```

## Alternate method, 11 bytes

From @ETHproductions; based on Brute Forces' Husk answer.

```
£sY å+Ãc rw

```

Gets all tails of the input array and cumulatively sums each. Then flattens the array and gets the max.

Try it online!

# Answer
> 1 votes
# JavaScript, 58 bytes

```
m=Math.max;x=y=>eval("a=b=0;for(k of y)b=m(a=m(a+k,k),b)")

```

Golfed JS implementation of Kadane's algorithm. Made as short as possible. Open to constructive suggestions!

**What I learnt from this post:** return value of `eval` \- when its last statment is a `for` loop - is basically the last value present *inside* the loop. Cool!

**EDIT:** saved four bytes thanks to Justin's and Hermann's suggestions.

# Answer
> 1 votes
# J, 12 bytes

```
[:>./@,+/\\.

```

Similar to zgrep's K solution: the scan sum of all suffixes (produces a matrix), raze, take max

Try it online!

### NOTE

for not too many more bytes, you can get an efficient solution (19 bytes golfed):

```
[: >./ [: ({: - <./)\ +/\

```

# Answer
> 1 votes
# Japt `-h`, 4 bytes

```
ãx ñ

```

Try it

```
ãx ñ     :Implicit input of array
ã        :Sub-arrays
 x       :Reduced by addition
   ñ     :Sort
         :Implicit output of last element

```

# Answer
> 0 votes
# Python 2, ~~52~~ 51 bytes

```
f=lambda l:len(l)and max(sum(l),f(l[1:]),f(l[:-1]))

```

Try it online!

# Answer
> 0 votes
# Common Lisp, 73 bytes

```
(lambda(a &aux(h 0)(s 0))(dolist(x a s)(setf h(max x(+ h x))s(max s h))))

```

Try it online!

# Answer
> 0 votes
# MY, 11 bytes

```
⎕35ǵ'ƒ⇹(⍐↵

```

Try it online! MY is on TIO now! Woohoo!

## How?

* = evaluated input
* = subvectors
* `35ǵ'` = `chr(0x53)` (Σ, sum)
* `ƒ` = string as a MY function
* = map
* `(` = apply
* = maximum
* = output with a newline.

Sum was fixed (`0` on empty arrays) in order for this to work. Product was also fixed.

# Answer
> 0 votes
# APL, ~~31~~ ~~29~~ 27 bytes

```
⌈/∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕

```

Try it online! (modified so it will run on TryAPL)

## How?

* `∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕` Generate sums of subvectors
* `⌈/` Maximum

# Answer
> 0 votes
# CJam, 24 bytes

```
q~:A,{)Aew{:+}%}%e_0+:e>

```

Function that takes array of numbers as input.

Try it Online

```
q~:A   e# Store array in 'A' variable
,{)Aew e# Get every possible sub-array of the array
{:+}%  e# Sum every sub array
}e_    e# flatten array of sums
0+     e# Add zero to the array
:e>    e# Return max value in array

```

# Answer
> 0 votes
# Axiom, 127 bytes

```
f(a:List INT):Complex INT==(n:=#a;n=0=>%i;r:=a.1;for i in 1..n repeat for j in i..n repeat(b:=reduce(+,a(i..j));b>r=>(r:=b));r)

```

This would be O(#a^3) Algo; I copy it from the C++ one... results

```
(3) -> f([1,2,3,-4,-5,6,7,-8,9,10,-11,-12,-13,14])
   (3)  24
                                                    Type: Complex Integer
(4) -> f([])
   (4)  %i
                                                    Type: Complex Integer
(5) -> f([-1,-2,3])
   (5)  3
                                                    Type: Complex Integer

```

# Answer
> 0 votes
# Scala, 105 bytes

```
val l=readLine.split(" ").map(_.toInt);print({for{b<-l.indices;a<-0 to b+2}yield l.slice(a,b+1).sum}.max)

```

I didn't find any better way to generate the sublists arrays.

# Answer
> 0 votes
# Java 8, 242 bytes

```
import java.util.*;v->{List a=new Stack();for(String x:new Scanner(System.in).nextLine().split(" "))a.add(new Long(x));int r=0,l=a.size(),i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;)s+=(long)a.get(k++);System.out.print(r);}

```

Try it here.

# 106 bytes without using STDIN/STDOUT requirement.. \>.\>

```
a->{int r=0,l=a.length,i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;s+=a[k++]);return r;}

```

Try it here.

**Explanation:**

```
import java.util.*;      // Required import for List, Stack and Scanner

v->{                     // Method with empty unused parameter and no return-type
  List a=new Stack();    //  Create a List
  for(String x:new Scanner(System.in).nextLine().split(" "))
                         //  Loop (1) over the STDIN split by spaces as Strings
    a.add(new Long(x));  //   Add the String converted to a number to the List
                         //  End of loop (1) (implicit / single-line body)
  int r=0,               //  Result-integer
      l=a.size(),        //  Size of the List
      i=l,j,k,           //  Index-integers
      s;                 //  Temp sum-integer
  for(;i-->0;)           //  Loop (2) from `l` down to 0 (inclusive)
    for(j=l;--j>1;       //   Inner loop (3) from `l-1` down to 1 (inclusive)
        r=               //     After every iteration: change `r` to:
          s>r?           //      If the temp-sum is larger than the current `r`:
           s             //       Set `r` to the temp-sum
          :              //      Else:
           r)            //       Leave `r` the same
      for(s=0,           //    Reset the temp-sum to 0
          k=i;k<j;)      //    Inner loop (4) from `i` to `j` (exclusive)
        s+=(long)a.get(k++);
                         //     Add the number at index `k` in the List to this temp-sum
                         //    End of inner loop (4) (implicit / single-line body)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  System.out.print(r);   //  Print the result to STDOUT
}                        // End of method

```

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