title: Minimal Centrosymmetrization

text:
# Question
Title: Minimal Centrosymmetrization
Topically related.

**Objective:** Given a matrix of positive integers \\$M\\$, output the smallest centrosymmetric matrix which contains \\$M\\$ (this matrix may contain non-positive integers as well).

A centrosymmetric matrix is a square matrix with rotational symmetry of order 2—i.e. it remains the same matrix after rotating it twice. For example, a centrosymmetric matrix has the top-left element the same as the bottom-right, and the element above the center the same as the one below the center. A useful visualization can be found here.

**More formally,** given a matrix \\$M\\$, produce a square matrix \\$N\\$ such that \\$N\\$ is centrosymmetric and \\$M\subseteq N\\$, and there is no other square matrix \\$K\\$ such that \\$\dim K\<\dim N\\$.

\\$A\\$ is a subset of \\$B\\$ (notation: \\$A\subseteq B\\$) if and only if each value \\$A\_{i,j}\\$ appears at index \\$B\_{i+i^\prime,j+j^\prime}\\$ for some pair of integers \\$(i^\prime, j^\prime)\\$.

*Note*: some matrices have multiple solutions (e.g. `[[3,3],[1,2]]` being solved as `[[2,1,0],[3,3,3],[0,1,2]]` or `[[3,3,3],[1,2,1],[3,3,3]]`); you must output at least one of the valid solutions.

## Test cases

```
input
example output

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

[[9]]
[[9]]

[[9, 10]]
[[9, 10],
 [10, 9]]

[[100, 200, 300]]
[[100, 200, 300],
 [  0,   0,   0],
 [300, 200, 100]]

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

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

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

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1]]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

```

# Answer
# Brachylog, 12 bytes

```
ṁ↔ᵐ↔?aaᵐ.&≜∧

```

Try it online!

Contrary to most Brachylog answers, this takes the input through the Output variable `.`, and outputs the result through the Input variable `?` (confusing, I know).

### Explanation

```
ṁ              We expect a square matrix
 ↔ᵐ↔?          When we reverse the rows and then the matrix, we get the initial matrix back
    ?a         Take an adfix (prefix or suffix) of that square matrix
      aᵐ       Take an adfix of each row of that adfix matrix
        .      It must be the input matrix
         &≜    Assign values to cells which are still variables (will assign 0)
           ∧   (disable implicit unification between the input and the output)

```

### 8 bytes, gives all valid matrices

Technically, this program also works:

`ṁ↔ᵐ↔?aaᵐ`

But this will leave as variables the cells which can take any value (they show as `_XXXXX`, which is an internal Prolog variable name). So technically this is even better than what is asked, but I guess it's not what the challenge asks for.
> 8 votes

# Answer
# JavaScript (ES6), ~~192~~ ~~180~~ 177 bytes

```
f=(m,v=[w=0],S=c=>v.some(c))=>S(Y=>S(X=>!m[w+1-Y]&!m[0][w+1-X]&!S(y=>S(x=>(k=(m[y-Y]||0)[x-X],g=y=>((r=a[y]=a[y]||[])[x]=r[x]||k|0)-k)(y)|g(w-y,x=w-x)),a=[])))?a:f(m,[...v,++w])

```

Try it online!

### Algorithm

Starting with \\$w=0\\$:

* We consider a square container matrix \\$M\\$ of width \\$w+1\\$.
* We consider each pair \\$(X,Y)\\$ such that the input matrix \\$m\\$ can fit within the container matrix when it's inserted at these coordinates.

Example:

$$\begin{align}w=2,&&(X,Y)=(0,1),&&m = \pmatrix{4,5,4\\1,2,3}\end{align}\\ M=\pmatrix{\color{gray}0,\color{gray}0,\color{gray}0\\4,5,4\\1,2,3}$$

* We test whether we can complete the matrix such that it's centrosymmetric.

Example:

$$M^\prime=\pmatrix{\color{blue}3,\color{blue}2,\color{blue}1\\4,5,4\\1,2,3}$$

* We increment \\$w\\$ until we find such a valid configuration.
> 4 votes

# Answer
# Python 2, ~~242~~ ~~227~~ 226 bytes

```
r=range
def f(m):
 w,h=len(m),len(m[0]);W=max(w,h)
 while 1:
	for x in r(1+W-w):
	 for y in r(1+W-h):
		n=n=eval(`[W*[0]]*W`);exec"for i in r(w):n[i+x][y:y+h]=m[i]\nN=n;n=[l[::-1]for l in n[::-1]]\n"*2
		if n==N:return n
	W+=1

```

Try it online!

---

Saved:

* -1 byte, thanks to Jonathan Frech
> 1 votes

# Answer
# Jelly, 27 bytes

```
oZ0ṁz0o⁸ṚUŻ€Z$2¡LÐ¡o⁸ṚU$ƑƇḢ

```

Try it online!

Newlines added to actual output over TIO for clarity.
> 1 votes

# Answer
# Clojure 254 bytes

```
(defn e[l m](let[a map v reverse r repeat t concat c count f #(v(a v %))h(fn[x](t(a #(t %(r(- l(c(first x)))0))x)(r(- l(c m))(r l 0))))k(fn[x](a(fn[v w](a #(if(= %2 0)%1 %2)v w))x(f x)))n(k(h m))o(k(h(f m)))z #(= %(f %))](if(z n)n(if(z o)o(e(inc l)m)))))

```

Jinkies, Scoob

Try it online!
> 1 votes

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


# Question
Title: Is 7 l8r than 9? (Is seven later than nine?)
This is a fairly simple code golf challenge. Your program, given an ASCII string, is to parse that string into two strings, which it will evaluate. If the second string is "later" than the first one, it will return a 1, if it is "earlier" than the first one, it will return a -1, and if they are the same, it will return 0. To clarify what "later" and "earlier" mean, let's take a look at ASCII character codes. You need to compare each character of the string, treating each of them as digits of a number. Later refers to a larger number, occurring after a smaller number. Strings will be formatted with a hyphen character to separate the two input groups.

Take a look at this example:

> `7-9` as an input should return `1`.
>
> `7` converts to ASCII code `55`, and `9` converts to ASCII code `57`.
>
> As `57` occurs numerically after `55`, `9` is later than `7`.

Another example:

> `LKzb-LKaj` as an input should return `-1`
>
> The ASCII code sequences for this are `76-75-122-98` and `76-75-97-106`

This is a code golf challenge, and byte count is how entries will be scored.

Any input from the 95 printable ASCII characters is accepted, excluding spaces, and hyphens for anything but separating the input. In addition, strings are not guaranteed to be the same length.

Good luck!

**EDIT:** To be more clear, each character is to be treated like a digit in a number. In the example `LKzb-LKaj`, though `j` is later than `b`, `z` is later than `a`, and since it is a more significant digit, it takes precedence. A string supplied will always be at minimum 3 characters, eliminating empty strings from the scope of this problem.

**EDIT:** Here are some more test cases, for your help:

* `A-9` -\> `-1`
* `11-Z` -\> `-1`
* `3h~J*-3h~J*` -\> `0`
* `Xv-Y0` -\> `1`

# Answer
> 10 votes
# Pyth - 11 bytes

Easy, uses `._` sign to get the sign and `C` to get char codes.

```
._-F_CMcz\-

```

Try it online here.

Test suite.

```
._               Sign of number
 -F              Fold subtraction (this finds difference of a tuple)
  _              Reverse list to get correct order of operands when subtracting
   CM            Map char, already treats strings as digits of base256 number
    c \-         Split by "-"
     z           Input

```

# Answer
> 7 votes
# CJam, 12 bytes

```
l'-/esfb~\-g

```

Try it online in the CJam interpreter.

### How it works

```
l   e# Read a line from STDIN.
'-/ e# Split it at spaces.
es  e# Push the current time (milliseconds since epoch).
fb  e# Consider each string as digits in base huge-number.
~\  e# Dump the results and reverse their order.
-g  e# Subtract and apply sign function.

```

# Answer
> 6 votes
# Java, ~~86~~ 118

```
int f(String...s){return(int)Math.signum((s=s[0].split("-"))[1].compareTo(s[0])*(s[0].length()==s[1].length()?1:-1));}

```

---

A very strange way of comparing strings. Made a quick fix so it passes additional test cases, will look for more golfiness later.

*Thanks to Vartan in comments for `signum` suggestion*

# Answer
> 4 votes
# Perl, 31 bytes

```
#!/usr/bin/perl -p
/-/;$_=($`.$'^$`)cmp($'.$`^$')

```

30 bytes + 1 byte for `-p`. Accepts input on STDIN.

## Explanation

When the operands to `cmp` have different lengths, like `chicken` and `egg`, they are aligned like this:

```
c  h  i  c  k  e  n
e  g  g  \0 \0 \0 \0

```

so that `egg` \> `chicken` (`\0` is a null byte). But we want them to be aligned like this:

```
c  h  i  c  k  e  n
\0 \0 \0 \0 e  g  g

```

so that `chicken` \> `egg`.

To do this, we concatenate them, once with `chicken` before `egg` and once with `egg` before `chicken`:

```
c  h  i  c  k  e  n  e  g  g
e  g  g  c  h  i  c  k  e  n

```

Now that our two strings are the same length, we remove the leading word using an XOR to get:

```
\0 \0 \0 \0 \0 \0 \0 e  g  g
\0 \0 \0 c  h  i  c  k  e  n

```

And *now* we can use `cmp` to find which came first. (There, I said it!)

# Answer
> 3 votes
## Python 2, 88 characters

```
a=raw_input().split('-');print-cmp(*(map(ord,s.rjust(max(map(len,a)),'\0'))for s in a))

```

`cmp` doesn't do the right thing when you have two different length strings, so I have to pad both of them with the null character (which `ord` converts to `0`) to handle that case. Unfortunately, that added about 35 characters, plus it's now two lines instead of one because I need both the length of the input and to iterate over it.

# Answer
> 2 votes
# R, 54 Bytes

This requires the pracma library. It splits the input string on the `-`. Right justifies the strings. Ranks them and does a diff.

So for 11-7 we end up with the strings "11" and " 7". The rank of these is \[2, 1\]. The difference is -1. For 3h~J\*-3h~J\* we get "3h~J\*" and "3h~J\*". The rank of these is \[1.5, 1.5\] with a diff of 0.

```
diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))

```

Test Examples

```
> diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))
1: LKzb-LKaj
3:
Read 2 items
[1] -1
> diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))
1: A-9
3:
Read 2 items
[1] -1
> diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))
1: 11-Z
3:
Read 2 items
[1] -1
> diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))
1: 3h~J*-3h~J*
3:
Read 2 items
[1] 0
> diff(rank(pracma::strjust(scan(,'',sep='-'),"right")))
1: Xv-Y0
3:
Read 2 items
[1] 1

```

# Answer
> 2 votes
# PERL, 46 36 Bytes

```
print$2cmp$1if"@ARGV"=~/(\S+)-(\S+)/

```

Converts the argv list into a string, splits by the hyphen into a left and right sided no spaces arg, then returns a cmp call.

# Answer
> 2 votes
# CoffeeScript, 143 140 139

```
f=(s)->[a,b]=((t=s.split '-').map (y)->Array((m=Math.max) 1, 1+(m ((l=(c)->c.length) t[0]),l t[1])-l y).join('\u0000')+y);`b<a?-1:(b>a?1:0)`

```

Here is a jsfiddle with the results (look in the console)

# Answer
> 1 votes
# perl5, 64

```
perl -aF- -pe '@f=map{length}@F;$_=$f[1]<=>$f[0]||$F[1]cmp$F[0]'

```

Just run it from the commandline. although it would look better with a new line but that costs 1 char.

```
perl -laF- -pe '@f=map{length}@F;$_=$f[1]<=>$f[0]||$F[1]cmp$F[0]'

```

This longer version handles mismatched lengths correctly.

# Answer
> 1 votes
# Python 3, 84 bytes

```
x,y=[int.from_bytes(i.encode(),"big")for i in input().split("-")];print((x<y)-(y<x))

```

Split the string input by `"-"`. Convert the unicode strings to bytes strings, then interpret these byte strings as big-endian integers. Finally do the comparison -- (un)fortunately `cmp` is no longer available in Python 3.

# Python 2, 69 bytes

```
print -cmp(*[int(i.encode("hex"),16)for i in raw_input().split("-")])

```

# Answer
> 1 votes
# Python 2, 79 bytes

Pretty simple solution, and it's easy to understand. Compares string lengths, then compares the strings lexigraphically.

**Try it here**

```
s,t=raw_input().split('-')
x,y=len(s),len(t)
print(x<y)*2-1if x-y else cmp(t,s)

```

# Answer
> 0 votes
# JavaScript ES6, 46 43 bytes

```
f=s=>((a=s.split('-'))[1]>a[0])-(a[1]<a[0])

```

# Answer
> 0 votes
# F#, 53

```
fun s->let[|a;b|]=s="";s.Split[|'-'|]in b.CompareTo a

```

This is in the form an anonymous function (lambda), so you have to paste it and provide the parameter directly after is (or, using the piping notation). For example (in FSI):

```
> "7-9" |> fun s->let[|a;b|]=s="";s.Split[|'-'|]in b.CompareTo a
1
> "abc-abc" |> fun s->let[|a;b|]=s="";s.Split[|'-'|]in b.CompareTo a
0
> "LKzb-LKaj" |> fun s->let[|a;b|]=s="";s.Split[|'-'|]in b.CompareTo a
-1

```

# Answer
> 0 votes
# Ruby, 59 bytes

```
a,b=gets.chomp.split ?-
p (b.size<=>a.size).nonzero?||b<=>a

```

# Answer
> 0 votes
# 05AB1E, ~~12~~ ~~11~~ 9 bytes

```
'-¡₄ö¥0.S

```

Try it online or verify all test cases.

**Explanation:**

```
'-¡          # Split the (implicit) input on '-'
             #  i.e. 'LKzb-LKaj' → ['LKzb','LKaj']
   ₄ö        # Convert both parts to a Base-1000 number
             #  i.e. ['LKzb','LKaj'] → [21020061037,21020036045]
     ¥       # Push the deltas (subtraction between each sub sequential pair) of the list
             #  i.e. [21020061037,21020036045] → [-24992]
      0.S    # Get the sign [1 for a>0; -1 for a<0; 0 for a==0] (and output implicitly)
             #  i.e. [-24992] → [-1]

```

---
Tags: code-golf, string, arithmetic
---


title: number decomposition

text:
# Question
Title: number decomposition
It's been a while since I posted here, so here we go another day another challenge.

# Challenge :

Given a number(*`n`*) split it into it's prime factors.

---

# Input :

A positive non-zero integer greater than 2.

---

# Output :

Decompose the number into it's prime factors and return the number of occurances of each prime in it.

---

## Ouput format :

You can choose Any valid output format.

---

# Example :

```
n = 86240
              v------------------------------- number of times it occurs in n
output : [[2, 5], [5, 1], [7, 2], [11, 1]]
           ^-------------------------------- prime number

n = 7775460
                           v--------------- 5 only occurs once in 7775460 so we don't need to write any power
output : [[2, 2], [3, 3], [5], [7], [11, 2], [17]]
            ^--------------------------------- same as first example

```

# Note :

* Prime factors have to be in either ascending order or descending order.
* You may choose to either write 1 as power or note

# Winning criterion :

This is so shortest code in bytes for each programming language wins

# Answer
# Jelly, 2 bytes

Built in command =)

```
ÆF

```

Try it online!

---

# Brachylog, 10 bytes

```
ḋ≡ᵍ⟨h≡l⟩ᵐ

```

-1 bytes thanks to Erik the Outgolfer

Try it online!
> 1 votes

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


# Question
Title: Is the matrix centrosymmetric... and so is the code?
## Defintion

A centrosymmetric matrix is a square matrix that is symmetric about its center. More rigorously, a matrix \\$A\\$ of size \\$n \times n\\$ is centrosymmetric if, for any \\$i,\\: j \in (\[1, n\] \cap \mathbb{Z})\\$ the following relation is satisfied: $$A\_{i,\\:j}=A\_{n+1-i,\\:n+1-j}$$

## Examples of such matrices

Here is an illustration of the symmetry of a matrices like these (borrowed from the aforementioned Wikipedia article):

An even-side-length (\\$4\times 4\\$) centrosymmetric matrix:

$$\left(\begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 8 & 7 & 6 & 5 \\ 4 & 3 & 2 & 1\end{matrix}\right)$$

And an odd-side-length (\\$3\times 3\\$) one:

$$\left(\begin{matrix} 1 & 2 & 3 \\ 5 & 6 & 5 \\ 3 & 2 & 1\end{matrix}\right)$$

## Task and Specs

Given a square matrix of size at least \\$2\\$, output one of two distinct and consistent values, deciding whether the matrix is centrosymmetric or not. You can assume that the matrix will consist entirely of positive integers.

**However, your code must also be centrosymmetric.** That is, it must be a program / function (or equivalents) consisting of \\$n\\$ lines, each of which containing \\$n\\$ **bytes** in your language's encoding, and must satisfy the definition given above, but with bytes instead of positive integers. Your submission's score will be the value of \\$n\\$, with a lower \\$n\\$ being better.

You can take input and provide output through any standard method and in any reasonable format, while taking note that these loopholes are forbidden by default. You may (optionally) choose to take the size, \\$n\\$, as input too (unless you take input as a 1D list, in which case you may only take \\$n^2\\$ as additional input).

## Test cases

Truthy:

```
[[1, 2], [2, 1]]
[[1, 2, 3], [5, 6, 5], [3, 2, 1]]
[[10, 5, 30], [2, 6, 2], [30, 5, 10]]
[[100, 100, 100], [100, 50, 100], [100, 100, 100]]
[[1, 2, 3, 4], [5, 6, 7, 8], [8, 7, 6, 5], [4, 3, 2, 1]]
[[3, 4, 5, 6, 7], [5, 6, 7, 8, 9], [3, 2, 10, 2, 3], [9, 8, 7, 6, 5], [7, 6, 5, 4, 3]]

```

Falsy:

```
[[1, 2], [1, 2]]
[[1, 2, 10], [5, 6, 5], [11, 2, 1]]
[[14, 5, 32], [2, 6, 2], [30, 5, 16]]
[[19, 19, 19], [40, 50, 4], [19, 19, 19]]
[[1, 2, 20, 4], [7, 6, 7, 8], [8, 7, 6, 6], [3, 3, 2, 1]]
[[3, 4, 5, 6, 7], [5, 6, 7, 8, 9], [4, 5, 10, 4, 5], [5, 6, 7, 8, 9], [3, 4, 5, 6, 7]]

```

# Answer
# JavaScript (ES6), size ~~12~~ ~~11~~ 9

All versions return **false** for centrosymmetric or **true** for non-centrosymmetric.

---

## 1-dimensional array + length, size 9 (89 bytes)

Takes input in currying syntax `(length)(array)`, where *array* is 1-dimensional.

```
w=>a=> //
a.some //
(v=>v- //
a[--w])//
/////////
//)]w--[a
// -v>=v(
// emos.a
// >=a>=w

```

Try it online!

---

## Matrix + width, size 11 (131 bytes)

Takes input in currying syntax `(width)(matrix)`.

```
/**/w=>a=>a
.some(r=>r.
some(v=>v-a
[y][w-++x],
x=!y--),y=w
);'*/'/*';)
w=y,)--y!=x
,]x++-w[]y[
a-v>=v(emos
.r>=r(emos.
a>=a>=w/**/

```

Try it online!

### Payload

```
w => a => a.some(r => r.some(v => v - a[y][w - ++x], x = !y--), y = w)

```

### Container

```
/**/CODE;'*/'/*';EDOC/**/

```

---

## Matrix only, size 12 (155 bytes)

This is my original solution, which computes the width of the matrix by itself.

```
/**/a=>a[w=a
.length-1,s=
'some']((r,y
)=>r[s]((v,x
)=>v-a[w-y][
w-x]))////*/
/*////))]x-w
[]y-w[a-v>=)
x,v((]s[r>=)
y,r((]'emos'
=s,1-htgnel.
a=w[a>=a/**/

```

Try it online!

### How?

We need a few critical tokens that cannot be split:

* `some`
* `length`
* `)=>`

Line-feeds may be inserted almost anywhere else.

The unrolled payload code reads as:

```
a => a[w = a.length - 1, s = 'some']((r, y) => r[s]((v, x) => v - a[w - y][w - x]))

```

and is wrapped inside the following structure:

```
/**/CODE////*/

```

which, once reversed, becomes a valid block comment:

```
/*////EDOC/**/

```
> 20 votes

# Answer
# Jelly, score 2

```
⁼Ṛ
Ṛ⁼

```

Try it online!

Takes input as a flattened square matrix (vector of size \\$n^2\\$).
> 18 votes

# Answer
# Befunge-93, size 24

```
   &:00p110p920p::*:v
vp01:+1g01-1pg02g01&_v#<
>00g`#v_>:           1$^
v2p011<  v:g00p029p01< @
>0g1+20p^>*:#v_1# .#<@ .
v+1g00gg02g01<$ >1+10pv0
>:10g-\88++20g -g-     |
vg02p011_v#`g00g01-1  <1
>1+20p   >:   ^ ^      <

<      ^ ^   :>   p02+1>
1<  1-10g00g`#v_110p20gv
|     -g- g02++88\-g01:>
0vp01+1> $<10g20gg00g1+v
. @<#. #1_v#:*>^p02+1g0>
@ <10p920p00g:v  <110p2v
^$1           :>_v#`g00>
<#v_&10g20gp1-10g1+:10pv
   v:*::p029p011p00:&

```

Try it online!

**Input:** `n`, followed by the elements of the array, all separated by spaces. NOTE: you may need to use a different interpreter if you have a large enough input.

I'm sure there's a better way to do this, I just wanted to try this in Befunge. The actual code portion is the top half.

## How?

The code is divided into two main sections, the **initialization** and the **verification**.

**Initialization:**

```
   &:00p110p920p::*:v
vp01:+1g01-1pg02g01&_v#<
>00g`#v_>:           1$^

```

This section of the code writes the input matrix right below the code as ASCII characters. Both this and the next section use the three cells at the top left of the code as data. They are stored as `n, i, j`.

**Verification:**

```
                     v
                     1
v2p011<  v:g00p029p01< @
>0g1+20p^>*:#v_1# .#<@ .
v+1g00gg02g01<$ >1+10pv0
>:10g-\88++20g -g-     |
vg02p011_v#`g00g01-1  <1
>1+20p   >:   ^ ^      <

```

This sections checks every index \\$i, j\\$ \[1-indexed\] against the condition \\$ A\_{i, j} = A\_{n+1-i, n+1-j} \\$. However, we have a problem: we have \\$j\\$ offset by \\$8\\$. To fix that, the following formulae are used:

\\$ i' = (n + 1) - i \\$

\\$ j' = n + 1 - (j - 8) + 8 = (n + 1) + (8 + 8) - j\\$

The other portions of code are unread garbage to make it centrosymmetric.
> 16 votes

# Answer
# Haskell, \\$n = 8\\$

*No comments!*

Takes input as a 1-D list

```
s a b=
    a/=b
f =s<*>
 reverse
esrever
 >*<s= f
b=/a
  =b a s

```

Try it online!

# \\$n= 10\\$

Takes input as a 2-D matrix

```
r =reverse
s a b=a/=b
f   =s<*>r
c  =concat
g =  f<$>c
c>$<f  = g
tacnoc=  c
r>*<s=   f
b=/a=b a s
esrever= r

```

Try it online!

Thanks to potato44 for all their help in chat. And Lynn for golfing off a row.

## Explanation

The general idea here is a simple one, we `concat` the list and compare it to it's reverse. However since we want to be centrosymmetric we have to tread carefully. First we write the code as we would normally:

```
g=((==)<*>reverse).concat

```

Now in order for our reverse lines to also be valid Haskell we need the left hand side of our equations to look like a function definition `tacnoc.)esrever>*<)==((` doesn't.

The first step to fixing this is disposing of parentheses.

```
s a b=a==b
f=s<*>reverse
g=f.concat

```

However we have some new problems now. Both `.` and `==` when reversed are the same, so our reversed lines attempt to redefine the operators (`<*>` reversed is `>*<` so we are fine on that front). `.` can be replaced with `<$>` since functions are functors. And we can replace `==` with `/=`, which negates our output, but that is still within the specs. Now we have

```
s a b=a/=b
f=s<*>reverse
g=f<$>concat

```

In order to trim down our line length we alias `concat` and `reverse`.

```
r=reverse
s a b=a/=b
f=s<*>r
c=concat
g=f<$>c

```

Now we just finish this by making everything centrosymmetric and square.

The shorter 1-D version works in much the same way except since there is no need to `concat` we can save two lines by removing it.
> 16 votes

# Answer
# Python 2, size 10 (109 bytes)

```
def f(a):#
 return(a#
==[r[::-1#
]for r in#
a[::-1]])#
#)]]1-::[a
#ni r rof]
#1-::[r[==
#a(nruter
#:)a(f fed

```

Try it online!

### Previous Python 2, size 14 (209 bytes)

```
lambda a:all(#
a[i][j]==a[-i#
-1][-j-1]for #
i in range(  #
len(a))for j #
in range(len(#
a)))         #
#         )))a
#(nel(egnar ni
# j rof))a(nel
#  (egnar ni i
# rof]1-j-[]1-
#i-[a==]j[]i[a
#(lla:a adbmal

```

Try it online!
> 9 votes

# Answer
# Pyth, size 6 (41 bytes)

```
q_M_QQ
q.q

   q.q
QQ_M_q

```

Try it here

### Explanation

The first line reverses the input and each row, and checks if we're left with a copy of the input.
The `.q` in the second line exits the program, so everything after that, as well as the `q` before it, is a no-op.
> 8 votes

# Answer
# APL (Dyalog Unicode), score ~~7~~ ~~6~~ ~~5~~ 4

Full program. Prompts for matrix expression from stdin. Prints a 1 or a 0 and then throws a consistent error. No comments!

```
r←,⎕
r≡⌽r
r⌽≡r
⎕,←r

```

Try it online!

prompt for expression and evaluate it
`,` ravel (flatten) it
`r←` store the result in `r` (for **r**avelled)

`⌽r` mirror `r`
`r≡` implicitly print whether `r` is identical to that

depth of `r` (gives 1)
`r⌽` use `r` to rotate that
 (this will always cause a `RANK ERROR` and quit because a matrix is not permitted as left argument to )
> 8 votes

# Answer
# Perl 6, size ~~9 8~~ 7

```
{.flat#
#}talf.
#  ],R[
eq # qe
[R,]  #
.flat}#
#talf.{

```

Try it online!

~~`reverse` is the bottleneck here. I've changed it to the technically longer, but much more splittable `[*-1 X-^*]`.~~ Okay, I've changed it to `[R,]` after seeing Brad Gilbert's answer to another question.

The flattened code is `{.flat eq [R,] .flat}`.

Edit: Damn, I've realised I don't even *need* to flatten the first list, but attempts at shortening it to a size 6 have failed with just *one* byte too many to fit...

```
{@_#}_@
eq#<<|
[R,] #
# ],R[
|<<#qe
@_}#_@{

```

:(

Though if we take it as a one dimensional array, it's easy to fit it in a size 6.

```
{$_# }
eq #_$
[R,] #
# ],R[
$_# qe
} #_${

```

Try it online!
> 7 votes

# Answer
# Wolfram Language (Mathematica) (REPL only), size 8 (71 bytes)

```
f=#[[c=-
1;;1;;-1
,c]]==#&
(*
      *(
&#==]]c,
1-;;1;;1
-=c[[#=f

```

Returns `True` for centrosymmetric input, and `False` otherwise.

On Mathematica REPL, lines with syntax errors are ignored (with a thick red bar appearing on the side of the screen). Here, only the first three lines, `f=#[[c=-1;;1;;-1,c]]==#&`, are executed.

This code captures the function in the name `f`.

Sadly, the built-in `PalindromeQ` is too long.
> 6 votes

# Answer
# Japt, size ~~9~~ 4 (11 bytes)

```
UªSê

êSªU

```

Try it online!

Takes one-dimensional input, checks if it is a palindrome. If you want, you can fill the two empty lines for some ascii art.
The old two-dimensional version, rotates the input twice and checks if it's equal to the original:

```
W=U  I
Wz2;II
Vc)eUc
cUe)cV
II;2zW
I  U=W

```

Try it online!
> 5 votes

# Answer
# Pyt, size 1

Try it online!

Checks if the input (in the form of concatenated rows) is a palindrome.
> 5 votes

# Answer
# Husk, size 3

```
Ṡ=↔
=↔=
↔=Ṡ

```

Try it online! Input as 1D-List. Each line defines a function, but only the one on the first line is called.

`Ṡ=↔` is a palindrome tests which checks whether the input equals (`=`) its reverse ().

---

## Husk, size 4

```
Ṡ=↔Σ
Σ↔=Ṡ
Ṡ=↔Σ
Σ↔=Ṡ

```

Try it online! For input as 2D-matrix, we concatenate (`Σ`) the list of lists before checking that it is a palindrome.
> 4 votes

# Answer
# MATL, score 4

```
t,!P
]=%?
?%=]
P!,t

```

Input has the format `[1 2; 2 1]`, using `;` as row separator.

Output is via STDERR (allowed by default):

* For centrosymmetric input a consistent error error is produced. With the current Linux and Octave versions in TIO the following STDERR output is produced (disregarding the final lines that start with `Real time: ...`):

```
octave: X11 DISPLAY environment variable not set
octave: disabling GUI features
Python 2.7.15 (default, May 16 2018, 17:50:09)
[GCC 8.1.1 20180502 (Red Hat 8.1.1-1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> >>> /usr/include/c++/8/bits/basic_string.h:1048: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::reference std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator[](std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::reference = char&; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]: Assertion '__pos <= size()' failed.
panic: Aborted -- stopping myself...

```

The error may be different depending on the Linux and Octave versions, but will be consistent across inputs.
* For non-centrosymmetric input no error is produced, and the STDERR output on TIO is

```
octave: X11 DISPLAY environment variable not set
octave: disabling GUI features
Python 2.7.15 (default, May 16 2018, 17:50:09)
[GCC 8.1.1 20180502 (Red Hat 8.1.1-1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> >>>

```

Try it online! Or verify all test cases:

* Centrosymmetric: , , , , , .
* Non-centrosymmetric: , , , , , .

Check that the program is centrosymmetric.

### Explanation

`%` is the comment symbol, which causes the rest of the line o be ignored. Newlines are also ignored. So the code is just

```
t,!P]=?P!,t

```

which does the following:

```
t       % Input, implicit. Duplicate
,       % Do twice
  !     %   Transpose
  P     %   Flip vertically
]       % End
=       % Compare element-wise
?       % If all comparisons gave true
  P     %   Implicit input. Transpose. Actually, since there is no more input, an
        %   error is prand the program exits. The rest of the code is not executed,
        %   and will be described in parentheses
  !     %   (Transpose)
  ,     %   (Do twice)
    t   %     (Duplicate)
        %   (End, implicit)
        % (End, implicit)

```
> 3 votes

# Answer
# Haskell, size ~~11~~, ~~10~~, ~~9~~, 8

Takes the input as a 2D list! (Credit to Ørjan Johansen)

```
r= --r}-
 reverse
(==)<*>
 r.map{-
-{pam.r
 >*<)==(
esrever
-}r-- =r

```
> 3 votes

# Answer
# C# (.NET Core), score 13 11 10

```
l=>a=>a.//
Where((e//
,i)=>e!=//
a[l-i-1]//
).Any()///
///()ynA.)
//]1-i-l[a
//=!e>=)i,
//e((erehW
//.a>=a>=l

```

Try it online!

Takes input as 1D array and n2 as length; returns `false` for centrosymmetric and `true` for non-centrosymmetric. This version uses `System.Linq` but I don't know how to fit it in the code submission due to the particular requirements of the challenge. Unrolled code:

```
l => a => a.Where((e,i) => e != a[l-i-1]).Any()

```

Following is my previous submission that does not use LINQ:

# C# (.NET Core), score 16 15 13

```
l=>a=>{/////*
var r=1<2;for
(int i=0;i<l;
)r&=a[i]==a[l
-i++-1];
return r;}
     /*/
   };r nruter
     ;]1-++i-
l[a==]i[a=&r)
;l<i;0=i tni(
rof;2<1=r rav
*/////{>=a>=l

```

Try it online!

Unrolled code:

```
l => a =>
{
    var r = 1<2;
    for (int i = 0; i < l;)
        r &= a[i] == a[l-i++-1];
    return r;
}

```
> 2 votes

# Answer
# Python 2, size 8

```
i=input#
a=i()###
a[::-1##
]!=a<_##
##_<a=!]
##1-::[a
###)(i=a
#tupni=i

```

Try it online!

Takes input as a 1D list of concatenated rows (of length \\$n^2\\$) and outputs via exit code (0 for symmetric inputs, 1 otherwise).

The list is simply checked to be a palindrome. If it is, the comparison chain `a[::-1]!=a<_` fails at the `!=` step and short-circuits; otherwise the unknown variable `_` gets evaluated, crashing the program.
> 2 votes

# Answer
# , size 9

```
   #)x-))
#(nacs-<x
#(ver(yna
#       #
#       #
#       #
any(rev(#
x<-scan(#
))-x)#

```

Try it online!

The last three lines are the actual program that takes a 1D array as input and checks if it's equal to its reverse. Truthy value: FALSE, Falsy value: TRUE.

```
any(rev(x<-scan())-x)

```

## \+ pryr, size 9

```
pryr::f(#
any(rev(#
x)-x))#

  #))x-)x
#(ver(yna
#(f::ryrp

```

Try it online!
> 2 votes

# Answer
# Ruby, score ~~9~~ 8

```
->z{z==#
z.######
reverse#
}#######
#######}
#esrever
######.z
#==z{z>-

```

Try it online!

A lambda taking a flattened matrix as input. Returns true for centrosymmetric, false otherwise.

-1 thanks to Mr.XCoder,

Unpacked:

```
->z{
  z == z.reverse
}

```
> 2 votes

# Answer
# 05AB1E, size 3 (11 bytes)

```
ÂQq

qQÂ

```

Input as a single list.
Try it online.

I guess this one doesn't count.. ;p

```
ÂQ
qâ

```

Input as a single list.
Try it online.

**Explanation:**

```
Â         # Bifurcate this list (short for DR: Duplicate & Reverse copy)
 Q        # Check if the input-list and the reversed list are equal
  q       # Terminate the program
   qQâ    # No-ops

```

---

**Some size 3 (11 bytes) alternatives:**

```
R€R
QqQ
R€R

```

Matrix as input.
Try it online.

```
RQ
 q
 QR

```

Single list as input.
Try it online.
> 2 votes

# Answer
# Clean, size 9

Thanks to Ørjan Johansen!

```
import //
 StdEnv//
r=reverse
?m=m==r//
    m
//r==m=m?
esrever=r
//vnEdtS
// tropmi

```

Try it online!

# Clean, size 10

```
import/*//
*/StdEnv//
r =reverse
?m      //
 =m==r m//
//m r==m=
//      m?
esrever= r
//vnEdtS/*
//*/tropmi

```

Try it online!
> 2 votes

# Answer
# C (gcc), 12 x 12

```
C(e,n,t,r)//
int*e;{for//
(r=t=0;e[t//
];r|=e[t]^//
e[~t+++n])//
;n=!!!!r;}//
//};r!!!!=n;
//)]n+++t~[e
//^]t[e=|r;]
//t[e;0=t=r(
//rof{;e*tni
//)r,t,n,e(C

```

Try it online!
> 1 votes

# Answer
# Stax, n = 3

```
$cr
=q=
rc$

```

Run and debug it

Explanation:

```
$cr =q= rc$ Full program, implicit input
$           Flatten
 cr         Copy and reverse
    =       Compare to original
     q      Print result
      =     Silently error because there is only one item on stack
        rc$ Not executed

```

3 is the best possible because I need at least three commands: Copy, reverse, and compare

### Stax, n = 4

```
Mrxr
M=qX
Xq=M
rxrM

```

Run and debug it

Explanation:

```
Mrxr M=qX Xq=M rxrM Full program, implicit input
Mr                  Transpose and reverse
  x                 Push input again
   r M              Reverse and transpose
      =             Compare
       qX Xq        Print result twice and save to X
            =       Silently error because there is only one item on stack
             M rxrM Not executed

```
> 1 votes

# Answer
# \>\<\>, Size 6

```
!/l2(\
s\?\ ?
/{=/ ;
: /={/
? \?\s
\(2l/!

```

Try it online!

(It turns out it's a pain passing multiple value to -v in tio)

Input is taken as a one dimensional array as the initial stack state with -v. Exits with no output if the matrix is centrosymmetric, exits with an error (prints "Something smells fishy...") if not.

```
l2(    Checks if the length of the stack is less than 2
?;     Exits cleanly if so

{=     Checks if the first and last elements are equal
?\s    Causes an error ('s' is not a valid instruction) if not

```

I wasn't entirely happy with this output format, so here's a size 7 one which outputs 1 for true, and 0 for false.

```
!/l2(\\
 ?   ?0
 =;n1/n
;{   {;
n/1n;=
0?   ?
\\(2l/!

```

Try it online!
> 1 votes

# Answer
# Japt, size 2 (5 bytes)

```
ê"
"ê

```

Try it
> 1 votes

# Answer
# Java 10, size 13 (181 bytes)

```
a->{var r///*
=1>0;for(int
l=a.length,i=
0;i<l;)r&=a[i
]==a[l-++i];
return r;}
     /*/
   };r nruter
 ;]i++-l[a==]
i[a=&r);l<i;0
=i,htgnel.a=l
 tni(rof;0>1=
*///r rav{>-a

```

Try it online.

Inspired by *@Charlie*'s C# answer.

**Golfed explanation:**

```
a->{var r=1>0;for(int l=a.length,i=0;i<l;)r&=a[i]==a[l-++i];return r;}

a->{                    //  Method with byte-array parameter and boolean return-type
  var r=1>0;            //  Result-boolean, starting at true
  for(int l=a.length,   //  The length of the input-array
      i=0;i<l;)         //  Loop `i` in the range [0, length)
    r&=                 //   Bitwise-AND the result-boolean with:
       a[i]             //    Whether the current item
           ==a[l-++i];  //    equals the opposite item
  return r;}            //  Return the result

```
> 1 votes

# Answer
# C (gcc), score 11

Takes a list of int and n as arguments. Returns n as truthy value, 0 as falsy.

```
/*//};n=l;k
--*==++l*=*
n);l>k;n*n+
l=k(rof{;l*
tni)n,l(f;k
*/*/////*/*
k;f(l,n)int
*l;{for(k=l
+n*n;k>l;)n
*=*l++==*--
k;l=n;}//*/

```

Try it online!
> 1 votes

# Answer
# Javascript ES6, size 8:

```
/***/a=>
""+a==a.
reverse(
)/////*/
/*/////)
(esrever
.a==a+""
>=a/***/

```

# Javascript ES6, size 7 (is it valid?):

```
a=>""+a
==a.//=
reverse
`     `
esrever
=//.a==
a+"">=a

```

### Test:

```
<script>
f=

a=>""+a
==a.//=
reverse
`     `
esrever
=//.a==
a+"">=a
</script>

<script>
console.log([
  [1, 2, 2, 1],
  [1, 2, 3, 5, 6, 5, 3, 2, 1],
  [10, 5, 30, 2, 6, 2, 30, 5, 10],
  [100, 100, 100, 100, 50, 100, 100, 100, 100],
  [1, 2, 3, 4, 5, 6, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1],
  [3, 4, 5, 6, 7, 5, 6, 7, 8, 9, 3, 2, 10, 2, 3, 9, 8, 7, 6, 5, 7, 6, 5, 4, 3],
].every(f))

console.log([
  [1, 2, 1, 2],
  [1, 2, 10, 5, 6, 5, 11, 2, 1],
  [14, 5, 32, 2, 6, 2, 30, 5, 16],
  [19, 19, 19, 40, 50, 4, 19, 19, 19],
  [1, 2, 20, 4, 7, 6, 7, 8, 8, 7, 6, 6, 3, 3, 2, 1],
  [3, 4, 5, 6, 7, 5, 6, 7, 8, 9, 4, 5, 10, 4, 5, 5, 6, 7, 8, 9, 3, 4, 5, 6, 7],
].every(x=>!f(x)))
</script>
```

or with lambda saved to variable named `a`:

```
a=

a=>""+a
==a.//=
reverse
`     `
esrever
=//.a==
a+"">=a

console.log([
  [1, 2, 2, 1],
  [1, 2, 3, 5, 6, 5, 3, 2, 1],
  [10, 5, 30, 2, 6, 2, 30, 5, 10],
  [100, 100, 100, 100, 50, 100, 100, 100, 100],
  [1, 2, 3, 4, 5, 6, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1],
  [3, 4, 5, 6, 7, 5, 6, 7, 8, 9, 3, 2, 10, 2, 3, 9, 8, 7, 6, 5, 7, 6, 5, 4, 3],
].every(a))

console.log([
  [1, 2, 1, 2],
  [1, 2, 10, 5, 6, 5, 11, 2, 1],
  [14, 5, 32, 2, 6, 2, 30, 5, 16],
  [19, 19, 19, 40, 50, 4, 19, 19, 19],
  [1, 2, 20, 4, 7, 6, 7, 8, 8, 7, 6, 6, 3, 3, 2, 1],
  [3, 4, 5, 6, 7, 5, 6, 7, 8, 9, 4, 5, 10, 4, 5, 5, 6, 7, 8, 9, 3, 4, 5, 6, 7],
].every(x=>!a(x)))
```
> 0 votes

# Answer
# Clojure, Size 9

```
#(= %(;;;
reverse;;
(map;;;;;
reverse;;
%)));)))%
;;esrever
;;;;;pam(
;;esrever
;;;(% =(#

```

Try it online!
> 0 votes

---
Tags: code-challenge, array, decision-problem, matrix, source-layout
---


title: Fewest operations to 100

text:
# Question
Title: Fewest operations to 100
# Overview

Given a list of digits, find the fewest operations to make 100

# Input

A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus (+) or minus (-) operators may be added between each so that the total sum is equal to 100.

# Output

The number of operators added, followed by the full sequence of digits and operators. The two can be separated by a space, tab, or new line sequence.

# Examples

**valid**

Input: `123456789`
Output: `3 123–45–67+89`

**Invalid**
Input: `123456789`
Output:
`6
1+2+34-5+67-8+9`
(There are ways of solving this with fewer operations)

# Answer
> 10 votes
## JavaScript (ES6), ~~153~~ 176 bytes

*EDIT: In non-strict mode, JS interprets 0-prefixed numerical expressions as octal (e.g. `017` is parsed as 15 in decimal). This is a fixed version that supports leading zeros.*

```
let f =

s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))
```

# Answer
> 5 votes
# MATL, ~~37~~ 36 bytes

```
n'+-'OhZ^!t2\s&SZ)"G@!vXzU100=?@z3M.

```

The test case takes about 6 seconds in TIO.

**Try it online!**

### How it works

```
n        % Implicitly input a string. Number of elements, say k
'+-'     % Push this string
Oh       % Append char 0. This is treated like ' ' (space)
Z^       % Cartesian power of the three-char string '+- ' raised to k.
         % Gives a matrix where each row is a Cartesian k-tuple
!        % Transpose
t        % Duplicate
2\       % Modulo 2. This turns '+' and '-' into 1, and ' ' into 0
s        % Sum of each column: number of '+' and '-' symbols
&S       % Sort and push the indices of the sorting
Z)       % Apply as column indices. This sorts the columns (k-tuples)
         % by the number of '+' and '-' they contain
"        % For each column, i.e. each k-tuple formed by '+', '-' and ' '
  G      %   Push input string again
  @!     %   Push k-tuple as row vector (string)
  v      %   Concatenate vertically into a 2×k char array
  Xz     %   Remove space (and char 0). Gives a string as result. In this
         %   process, the 2×k array is linearized in column major order
         %   (down, then across). So the '+' and '-' signs are between
         %   digits of the input, or at the end
  U      %   Convert to number. This performs the operation determined by
         %   by the '+' and '-' signs and returns the result. A trailing
         %   '+' or '-' sign makes the input invalid, which causes an
         %   empty result
  100=   %   Is it equal to 100?
  ?      %   If so
    @    %     Push current k-tuple
    z    %     Number of nonzeros, i.e. of '+' and '-' signs
    3M   %     Push linearized string without spaces again
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicitly dispplay stack

```

# Answer
> 3 votes
# Jelly, 32 bytes

```
L’⁾+_ṗż@€
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L

```

A full program which displays using the Jelly operators (`_` instead of `-`).

*Note:* To show `-` in the output instead of `_` (not a requirement) add `⁾_-y` between `F` and  (`⁾_-` is a character pair literal `['_','-']` and `y` is the dyadic "translate" atom).

### How?

```
L’⁾+_ṗż@€ - Link 1, form all sums from a partition: list of lists of characters
                                     e.g. ["12","345","67"]
L         - length                        3
 ’        - decremented                   2
  ⁾+_     - literal ['+','_']
     ṗ    - Cartesian power               ["++","+_","_+","__"]
      ż@€ - zip for €ach (swap @rguments) ["12+345+67","12+345_67","12_345+67","12_345_67"]

ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L - Main link: list of characters
ŒṖ                     - all partitions
  Ç€                   - call the last link (1) as a monad for €ach
    Ẏ                  - tighten (flatten by 1 level)
     µ     µÐf         - filter keep if:
      F                -   flatten
       V               -   evaluate as Jelly code (perform the sum)
         ȷ2            -   literal 100
        =              -   equal?
               Þ       - sort by:
              L        -  length
                Ḣ      - head
                 F     - flatten
                  Ṅ    - print that and a newline
                   ḟ³  - filter out the characters from the input
                     L - length (number of operators)
                       - implicit print

```

**Try it online!**

# Answer
> 3 votes
# PHP, ~~166~~ 171 bytes

```
for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=sprintf("%2d $s",strlen($s)-$e))for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

```

Run as pipe with `-nR` or test it online.

uses formatted numbers to sort the results --\>
may print leading blanks (and may fail for input with more than 99 digits; increase the number at `%2d` to fix).

**no more than 10 digits, 161 bytes**

```
for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=(strlen($s)-$e)." $s")for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

```

**breakdown**

```
for(;$n<3**$e=strlen($x=$argn); # loop $n up
    eval("return $s;")-100?:        # 2. evaluate term, if 100 then
                                    # prepend number of operations, add to results
        $r[]=sprintf("%2d $s",strlen($s)-$e)
)
                                # 1. create term
    for($i=0,$s="",$k=$n++;         # init variables, increment $n
        a&$c=$x[$i];$k/=3)          # loop through digits/operator index
        $s.="+-"[$i++?$k%3:2].$c;   # prepend operator for base-3 digit (nothing for 2)
echo min($r);                   # print lowest result

```

# Answer
> 3 votes
# \[Python 2\], ~~164~~ 158 bytes

```
from itertools import*
f=lambda N:min((len(s)-len(N),s)for s in(''.join(sum(zip(N,p+('',)),()))for p in product(('+','-',''),repeat=len(N)-1))if eval(s)==100)

```

Try it online!

Take N as a string of digits; returns a tuple (numOps, expressionString).

Basically the same approach as others; uses itertools.product to construct the individual "cases" e.g. for N=='1322', a "case" would be `('-','','+')`, and would evaluate '1-32+2'.

Throws an ValueError if the input is invalid (but I think OP gauranteed no invalid inputs).

# Answer
> 3 votes
# Brachylog, 36 bytes

```
~cịᵐ{|ṅ}ᵐ{+100&{ℕṫ,"+"↻|ṫ}ᵐcbE&kl;E}

```

Try it online!

More than half of this is to get the output format right though. The actual core logic is only:

# 15 bytes

```
~cịᵐ{|ṅ}ᵐ.+100∧

```

Try it online!

This returns a list like \[123,–45,–67,89\]. The expression is the sum of the elements, and the number of operators is 1 less than the length of the list.

`~cLhℕ∧100~+L` almost works for 12 bytes (Try it online!) - but it's too slow to handle full 9 digit input on TIO, and more importantly, it fails for inputs like `10808` \- Brachylog is too smart to split numbers to have leading zeros, so doesn't see the \[108, -08\] partition.

# Answer
> 2 votes
# Python 2, ~~256~~ ~~230~~ ~~208~~ ~~205~~ ~~172~~ ~~171~~ ~~170~~ 165 bytes, iterative method

* **33** thanks to Chas Brown
* One saved byte when replacing `len(a)` by `w`
* One saved byte when replacing `z-=1;d=z` by `d=z=z-1`

```
q=[];a=input()
w=len(a);z=n=3**w
while z-n/3:
 d=z=z-1;j=0;b=''
 while d:r=d%3;d/=3;b+=a[j]+chr(r+43)*(d>0!=r-1);j+=1
 if eval(b)==100:q+=[(len(b)-w,b)]
print min(q)

```

Try it online!

**Little explanation** Using the representation in base 3, the code interleaves the digits with the operators {'+','-',concatenation} according to all possible combinations.

# Python 2, 167 bytes, recursive method

```
def f(s):
 if len(s)==1:return[s]
 b=s[0];q=[]
 for z in f(s[1:]):q+=[b+'+'+z,b+'-'+z,b+z]
 return q
a=input()
print min((len(x)-len(a),x)for x in f(a)if eval(x)==100)

```

Try it online!

**Some outputs**

```
"399299"    --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111"   --> (3, '1+111-1-11')

```

# Answer
> 2 votes
# Mathematica, 136 ~~146~~ ~~149~~ ~~156~~ ~~165~~ ~~166~~ bytes

```
#&@@Sort[{StringLength@#-e+9!(ToExpression@#-100)^2,#}&/@StringJoin/@(Riffle[b,#]&)/@Tuples[{"","+","-"},(e=Length[b=Characters@#])-1]]&

```

Returns `{3, 123-45-67+89}` for example.

The test case takes about 0.09 seconds to complete.

# Answer
> 1 votes
# Haskell, ~~180~~ 178 bytes

```
m#[a]=[[a]]
m#(b:r)|s<-m#r=m(b:)=<<[s,m('+':)s,m('-':)s]
o '-'=(-)
o _=(+)
(p:r)?a|[(b,s)]<-lex r=s?o p a(read b)
_?a=a
g s=minimum[(sum[1|c<-t,c<'0'],t)|t<-map#s,('+':t)?0==100]

```

Try it online! Usage: `g "123456789"` yields `(3,"123-45-67+89")`.

`#` builds a list of all possible terms, `?` evaluates a term and `g` filters those terms which evaluate to 100 and returns the one with the minimal number of operands.

# Answer
> 0 votes
# Jelly, 27 bytes

```
L’““+“_”ṗ⁸żF¥ⱮV⁼ȷ2ƊƇLÞḢṄḟ⁸L

```

Try it online!

Can't say I didn't take a few hints from Jonathan Allan's older answer. ;-)

Compared to his answer, this one is just two bytes shorter (30), not five, if we make the comparison fair due to language updates:

```
L’““+“_”ṗ⁸żF¥Ð€V⁼ȷ2$$ÐfLÞḢṄḟ⁸L

```

If we compare the other way (newer version instead of older), the difference is the same (his becomes 29 bytes, seen below):

```
ŒṖżⱮL’⁾+_ṗƲ$€ẎFV=ȷ2ƲƇLÞḢFṄḟ³L

```

---
Tags: code-golf, integer, integer-partitions, expression-building
---


title: Generate a grid of sums

text:
# Question
Title: Generate a grid of sums
Generate a 7 by 7 grid, filled with random numbers. However, in cells with an odd row and column number (starting at 0), you must use the sum of the surrounding cells. Here's a small example with a 3 by 3 grid (sum-square bolded):

```
2 2  2
2 **16** 2
2 2  2
```

And here's an example 7 by 7 grid:

```
6 5  4 3  7 2  5
6 **43** 3 **50** 8 **43** 8
4 7  8 8  9 3  1
4 **36** 1 **43** 6 **40** 5
3 3  6 1  4 7  5
4 **35** 3 **45** 9 **42** 1
2 6  8 6  8 5  3
```

## Rules

* Numbers that are not sums must always be between 1 and 9 inclusive.
* Grid must be randomly generated. For each non-sum, every digit must have an equal chance of appearing, regardless of which cell it is in.
* Numbers must be aligned. This means that either the first or last digit of each number in a column must line up vertically. (You may assume that the middle numbers will always be two digits.)
* Surrounding cells includes diagonals. Therefore, each sum square will have eight numbers surrounding it, which you must add.
* Shortest code wins, since this is .

# Answer
> 15 votes
## APL, ~~53 49 43 42 40 39~~ 36

I managed to replicate J's `;.` in APL, and used Gareth's approach, saving 13 chars.

```
{×5⌷⍵:5⌷⍵⋄+/⍵}¨3,⌿3,/×∘?∘9¨∘.∨⍨9⍴0 1

```

Sample run:

```
      {×5⌷⍵:5⌷⍵⋄+/⍵}¨3,⌿3,/×∘?∘9¨∘.∨⍨9⍴0 1
9  9 6  1 7  5 6
7 55 5 39 9 54 9
9  8 2  1 8  1 9
2 43 8 41 6 42 5
7  3 4  4 8  3 2
2 29 1 26 2 35 8
6  4 2  3 2  3 7

```

---

Explanation:

* `∘.∨⍨9⍴0 1` generates a bit mask.
* `×∘?∘9¨` multiplies each bit by a random value from 1 to 9 inclusive, generating a masked grid of random numbers.
* `3,⌿3,/` uses what can only be described as hackery to return all 3 by 3 overlapping boxes in the masked array. These are also flattened in the process.
* `{×5⌷⍵:5⌷⍵⋄+/⍵}¨` iterates over the array, assigning each element to . For each iteration, it takes the fifth (middle, remembering that APL indexing is 1-based), and returns its sign. In this case this is equivalent to testing if the number is greater than 0. If this returns 1 (for true), then return that element. Otherwise, return the sum of the elements in the flattened 3 by 3 box. It uses the `:⋄` ternary operator, which is the equivalent of `?:` in many languages.

# Answer
> 12 votes
## J, 63 61 59 55 52 51 49 47 39 37 characters

```
3 3(4&{+4{*|+/)@,;._3(**1+?)+./~9$0 9

```

With thanks to Volatility for his 10 character saving.

Explanation (each step will have different random numbers...):

Generate the mask for generating the random numbers (uses `$`:

```
   9 9$9$0 9
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0
0 9 0 9 0 9 0 9 0

```

Now we have a hook. This is actually a happy accident from when I was whittling down an earlier version. It was meant to be transpose `|:` and OR `+.` with the original. It made sense since I was using ones and zeroes at the time, but now I have nines and zeroes. It just so happens that it works in the same way with the GCD meaning of `+.`. Lucky for me. :-)

```
   (+.|:)9 9$9$0 9
0 9 0 9 0 9 0 9 0
9 9 9 9 9 9 9 9 9
0 9 0 9 0 9 0 9 0
9 9 9 9 9 9 9 9 9
0 9 0 9 0 9 0 9 0
9 9 9 9 9 9 9 9 9
0 9 0 9 0 9 0 9 0
9 9 9 9 9 9 9 9 9
0 9 0 9 0 9 0 9 0

```

So, now that we have a grid of 9s and 0s we want to generate some random numbers. `?` generates a random number from 0 up to (but not including) a given number. Given a list it will generate one random number in this way for each member of the list. So in this case it will generate a number from 0 to 8 for every 9 in the table and a floating point number from 0 to 1 for each 0.

```
   ?(+.|:)9 9$9$0 9
 0.832573 7 0.926379 7 0.775468 6 0.535925 3  0.828123
        7 0        5 5        4 3        4 5         4
0.0944584 2 0.840913 2 0.990768 1 0.853054 3  0.881741
        3 8        7 0        8 3        3 4         8
 0.641563 4 0.699892 7 0.498026 1 0.438401 6  0.417791
        6 8        7 5        2 3        6 6         3
 0.753671 6 0.487016 4 0.886369 7 0.489956 5  0.902991
        3 4        7 8        1 4        8 0         8
0.0833539 4 0.311055 4 0.200411 6 0.247177 5 0.0464731

```

But we want numbers from 1 to 9 not 0 to 8. So we add 1.

```
   (1+?)(+.|:)9 9$9$0 9
 1.4139 4  1.7547 7 1.67065 4 1.52987 1 1.96275
      2 8       2 4       3 9       6 9       9
1.15202 7 1.11341 5  1.0836 1 1.24713 2 1.13858
      9 3       3 2       4 7       3 8       6
1.06383 9 1.67909 4 1.09801 8  1.4805 6  1.0171
      9 5       5 5       9 5       9 4       3
1.22819 1 1.85259 4 1.95632 6 1.33034 3 1.39417
      4 2       5 1       3 7       2 5       6
1.06572 5  1.9942 5 1.78341 5 1.16516 6 1.37087

```

This is very nice but we've lost the zeroes that I want, so we'll multiply it by the original mask after turning all the nines into ones. I do this by checking if the value is greater than 1. That gives us: `(1&<*1+?)`.
There are a couple of things going on here:

* We've created a fork which allows us to pack a lot of work into very few characters.
* We've bonded (`&`) the 1 to the `<` verb.

So all combined the `(1&<*1+?)` is generating random numbers, and zeroing all the numbers which where generated by zeroes in the original grid.

```
   (1&<*1+?)(+.|:)9 9$9$0 9
0 3 0 2 0 7 0 1 0
9 5 2 7 7 1 4 5 7
0 6 0 8 0 3 0 1 0
4 8 7 5 9 7 7 9 4
0 9 0 6 0 9 0 9 0
6 1 2 1 4 6 8 9 4
0 3 0 8 0 6 0 6 0
2 5 2 2 2 2 3 9 3
0 9 0 3 0 5 0 3 0

```

The next bit is the (in my opinion, anyway :-) clever bit.
The cut `;.` verb has a form `x u;._3 y` which cuts the input into boxes described by `x`, and then applies the verb `u` to them. In this case we have `3 3(4&{++/*0=4&{)@,;._3`.

* The `3 3` is describing the boxes we want - 3x3.
* The `(4&{++/*0=4&{)@,` is a verb train which describes what we want to do to each box.

To demonstrate the `;.` verb I'll use `<` to show each box:

```
   3 3(<);._3(1&<*1+?)(+.|:)9 9$9$0 9
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 8 0│8 0 7│0 7 0│7 0 4│0 4 0│4 0 3│0 3 0│
│9 1 3│1 3 2│3 2 3│2 3 8│3 8 5│8 5 5│5 5 9│
│0 6 0│6 0 1│0 1 0│1 0 2│0 2 0│2 0 4│0 4 0│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│9 1 3│1 3 2│3 2 3│2 3 8│3 8 5│8 5 5│5 5 9│
│0 6 0│6 0 1│0 1 0│1 0 2│0 2 0│2 0 4│0 4 0│
│7 1 6│1 6 7│6 7 1│7 1 2│1 2 1│2 1 6│1 6 1│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0 6 0│6 0 1│0 1 0│1 0 2│0 2 0│2 0 4│0 4 0│
│7 1 6│1 6 7│6 7 1│7 1 2│1 2 1│2 1 6│1 6 1│
│0 7 0│7 0 5│0 5 0│5 0 9│0 9 0│9 0 7│0 7 0│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│7 1 6│1 6 7│6 7 1│7 1 2│1 2 1│2 1 6│1 6 1│
│0 7 0│7 0 5│0 5 0│5 0 9│0 9 0│9 0 7│0 7 0│
│7 9 9│9 9 7│9 7 1│7 1 9│1 9 4│9 4 9│4 9 5│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0 7 0│7 0 5│0 5 0│5 0 9│0 9 0│9 0 7│0 7 0│
│7 9 9│9 9 7│9 7 1│7 1 9│1 9 4│9 4 9│4 9 5│
│0 3 0│3 0 2│0 2 0│2 0 7│0 7 0│7 0 9│0 9 0│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│7 9 9│9 9 7│9 7 1│7 1 9│1 9 4│9 4 9│4 9 5│
│0 3 0│3 0 2│0 2 0│2 0 7│0 7 0│7 0 9│0 9 0│
│3 1 6│1 6 1│6 1 7│1 7 6│7 6 8│6 8 9│8 9 9│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0 3 0│3 0 2│0 2 0│2 0 7│0 7 0│7 0 9│0 9 0│
│3 1 6│1 6 1│6 1 7│1 7 6│7 6 8│6 8 9│8 9 9│
│0 9 0│9 0 3│0 3 0│3 0 4│0 4 0│4 0 3│0 3 0│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┘

```

Some things to notice:

* The boxes overlap - the second and third columns in the top left box are the first and second in the box to the right of it.
* There are 7x7 boxes. That's why we had a 9x9 grid initially.
* Each place we require a sum has a `0` at the box's centre.

Now we just need to either pass the value at the centre back (if it's non-zero) or sum the numbers in the 3x3 box (if the centre is zero).
To do this we need easy access to the centre number. `,` helps here. It turns the 3x3 grid into a list of 9 items with the centre number at number 4.
`4&{` will use `{` to pull out the centre value and then compare it with 0: `0=4&{`. This returns a `0` or `1` for true or false, which we then multiply by the sum `+/`. If it was zero at the centre we now have our sum as required. If it was not we have zero, so to finish off we just add the centre value `4&{+`.
This gives the verb train `(4&{++/*0=4&{)@,`

```
   3 3(4&{++/*0=4&{)@,;._3(1&<*1+?)(+.|:)9 9$9$0 9
2  6 9  3 7  9 7
3 47 6 51 5 49 5
3  9 9  6 6  2 8
7 48 6 47 1 37 5
5  4 5  7 7  2 6
5 35 3 49 8 51 9
1  6 6  6 7  4 8

```

# Answer
> 5 votes
# Ruby (135 characters)

```
a=(0..48).map{rand(9)+1}
([0,0,j=8]*3).each{|l|a[j]=[0,1,6,7,8].inject{|s,e|s+a[j+e]+a[j-e]};j+=l+2}
a.each_slice(7){|r|puts"%-3s"*7%r}

```

# Sample output

```
2  1  6  9  4  5  1
9  34 4  37 2  31 3
7  2  3  1  8  1  7
5  42 4  40 2  47 9
3  9  9  4  9  4  7
3  44 4  41 2  47 4
6  9  1  5  7  6  8

```

---

# Breakdown

It's not too obvious how this works, so here's a quick breakdown. **NOTE:** You can probably skip some of these steps and jump to shorter versions more quickly, but I think it's educational enough to see different ways I shaved off characters, especially by spotting patterns in literals to turn 2-digit numbers into 1-digit versions.

## Naive version

Unlike the other Ruby solutions that rely on a two-dimensional array, you can (eventually) get a shorter version by starting with a 1-dimensional array and working with offset values, since the patterns repeat.

```
ary=(0..48).map { rand(9) + 1 }

offsets = [-8,-7,-6,-1,1,6,7,8]

3.times do |i|
  [8,10,12].each do |j|
    ary[j + 14*i] = ary.values_at(*offsets.map { |e| j+14*i + e }).inject(:+)
  end
end

ary.each.with_index do |e,i|
  $> << ("%-3s" % e)
  $> << ?\n if i % 7==6
end

```

The key principle here is that we're working at index positions 8, 10, 12, just offset by multiples of 14. Positions 8, 10 and 12 are the centers of the 3x3 grids that we're summing up. In the sample output, 34 is position 8, 42 is position 8 + 14\*1, etc. We replace position 8 with 34 by positions offset from position 8 by `[-8,-7,-6,-1,1,6,7,8]` — in other words `34 = sum(ary[8-8], ary[8-7], ..., ary[8+8])`. This same principle holds for all the values of `[8 + 14*i, 10 + 14*i, 12 + 14*i]`, since the pattern repeats.

## Optimising it

First, some quick optimisations:

* Instead of `3.times { ... }`, and calculating `j + 14*i` each time, "inline" the positions `[8,10,12,22,24,26,36,38,40]`.
* The `offsets` array is used once, so replace the variable with the literal.
* Replace `do ... end` with `{...}` and switch around the printing to `$> << foo`. (There's a trick here involving `puts nil` and `() == nil`.)
* Shorter variable names.

The code after this is **177** characters:

```
a=(0..48).map{rand(9)+1}
[8,10,12,22,24,26,36,38,40].each{|j|a[j]=a.values_at(*[-8,-7,-6,-1,1,6,7,8].map{|e|j+e}).inject(:+)}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

For the next reduction, note that the `inject` doesn't need the offsets array to be in order. We can either have `[-8,-7,-6,-1,1,6,7,8]` or some other ordering, since addition is commutative.

So first pair up the positives and the negatives to get `[1,-1,6,-6,7,-7,8,-8]`.

Now you can shorten

```
[1,-1,6,-6,7,-7,8,-8].map { |e| j+e }.inject(:+)

```

to

```
[1,6,7,8].flat_map { |e| [j+e, j-e] }

```

This results in

```
a=(0..48).map{rand(9)+1}
[8,10,12,22,24,26,36,38,40].each{|j|a[j]=a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+)}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

which is **176** characters.

## Shift by 8 and move to differences

The two-character literal values seem like they can be shortened away, so take `[8,10,12,22,24,26,36,38,40]` and shift everything down by `8`, updating `j` at the start of the loop. (Note that `+=8` avoids needing to update the offset values of `1,6,7,8`.)

```
a=(0..48).map{rand(9)+1}
[0,2,4,14,16,18,28,30,32].each{|j|j+=8;a[j]=a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+)}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

This is 179, which is bigger, but the `j+=8` can actually be removed.

First change

```
[0,2,4,14,16,18,28,30,32]

```

to an array of differences:

```
[2,2,10,2,2,10,2,2]

```

and cumulatively add these values to an initial `j=8`. This will eventually cover the same values. (We could probably skip straight to this instead of shifting by 8 first.)

Note that we'll also add a dummy value of `9999` to the end of the differences array, and add to `j` at the *end*, not the *start* of the loop. The justification is that `2,2,10,2,2,10,2,2` looks *awfully* close to being the same 3 numbers repeated 3 times, and by computing `j+difference` at the end of the loop, the final value of `9999` won't actually affect the output, since there isn't a `a[j]` call where `j` is some value over `10000`.

```
a=(0..48).map{rand(9)+1}
j=8
[2,2,10,2,2,10,2,2,9999].each{|l|a[j]=a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+);j+=l}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

With this differences array, the `j+=8` is now just `j=8`, of course, since otherwise we'd repeatedly add `8` too many. We've also changed the block variable from `j` to `l`.

So since the `9999` element has no effect on the output, we can change it to `10` and shorten the array.

```
a=(0..48).map{rand(9)+1}
j=8
([2,2,10]*3).each{|l|a[j]=a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+);j+=l}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

This is **170** characters.

But now the `j=8` looks a bit clunky, and you can save 2 characters by shifting `[2,2,10]` down by 2 to conveniently get an `8` you can use for assignment. This also needs `j+=l` to become `j+=l+2`.

```
a=(0..48).map{rand(9)+1}
([0,0,j=8]*3).each{|l|a[j]=a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+);j+=l+2}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

This is **169** characters. A round-about way to squeeze 7 characters, but it's neat.

## Final tweaks

The `values_at` call is actually sort of redundant, and we can inline an `Array#[]` call. So

```
a.values_at(*[1,6,7,8].flat_map{|e|[j+e,j-e]}).inject(:+)

```

becomes

```
[1,6,7,8].flat_map{|e|[a[j+e],a[j-e]]}.inject(:+)

```

You can also spot that `flat_map` \+ `j+e/j-e` \+ `inject` can be reduced to a more direct summation with an initial `0` in the array.

This leaves you with **152** characters:

```
a=(0..48).map{rand(9)+1}
([0,0,j=8]*3).each{|l|a[j]=[0,1,6,7,8].inject{|s,e|s+a[j+e]+a[j-e]};j+=l+2}
a.map.with_index{|e,i|$><<"%-3s"%e<<(?\nif i%7==6)}

```

Finally:

* `map.with_index` can become `each_slice`.
* Change the printing approach.

**135**:

```
a=(0..48).map{rand(9)+1}
([0,0,j=8]*3).each{|l|a[j]=[0,1,6,7,8].inject{|s,e|s+a[j+e]+a[j-e]};j+=l+2}
a.each_slice(7){|r|puts"%-3s"*7%r}

```

# Answer
> 3 votes
**Python, 132**

This doesn't technically satisfy the rules, because the last digits of each number are aligned rather than the first. But I thought I'd share anyway:

```
import numpy
G=numpy.random.randint(1,10,(7,7))
G[1::2,1::2]=sum(G[i:6+i:2,j:6+j:2]for i in[0,1,2]for j in[0,1,2]if i&j!=1)
print G

```

Sample output:

```
[[ 8  9  8  3  8  5  8]
 [ 6 53  4 45  8 53  8]
 [ 8  2  8  1  5  3  8]
 [ 2 40  6 34  1 32  7]
 [ 4  1  9  1  3  3  2]
 [ 4 35  7 35  6 31  1]
 [ 1  7  2  5  2  8  6]]

```

# Answer
> 3 votes
## GolfScript (79 78 72 70 68 66 65 60 chars)

```
56,{13%5<,~9rand)}%9/`{>3<zip`{>3<(*(+(\{+}*or' '}+7,%n}+7,/

```

NB This contains a literal tab, which Markdown may well break.

The clever bit is due to Gareth: see his J solution.

Online demo

# Answer
> 3 votes
**Mathematica, 108**

```
s=#-1;;#+1&;g=1+8~RandomInteger~{7,7};Column/@
ReplacePart[g,{i_?EvenQ,j_?EvenQ}:>g〚s@i,s@j〛~Total~2-g〚i,j〛]

```

For prettier output `Column/@` can be replaced with `TableForm@` at a cost of 2 characters.

# Answer
> 3 votes
### R: 114 characters

```
a=array(sample(1:9,49,r=T),c(7,7))
for(i in 2*1:3){for(j in 2*1:3)a[i,j]=sum(a[(i-1):(i+1),(j-1):(j+1)])-a[i,j]}
a

```

First line create a 7 by 7 array filled with randomly chosen numbers from 1 to 9 (uniform distribution with replacement, hence `r=T` which stands for `replace=TRUE`). Second line, compute sums of 3 by 3 grids, substract center and replace it with the result. Third line print the resulting grid (by default, matrix and array columns are right aligned).

Example output:

```
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    8    5    6    4    3    2    2
[2,]    1   37    6   41    7   38    8
[3,]    5    3    3    3    9    4    3
[4,]    4   31    3   41    3   44    9
[5,]    3    5    5    9    6    7    3
[6,]    3   32    2   40    4   37    5
[7,]    8    2    4    1    9    1    2

```

# Answer
> 2 votes
# J, 67 65 bytes

A naïve and verbose solution in J. It is a straightforward implementation of the task.

```
(+/^:_"2((,&.>/@(<:,],>:)"0)&.>m){0 m}a)(m=.{;~1 3 5)}a=.>:?7 7$9

```

First I create a 7 x 7 array of integers between 1 and 9. In fact J's ? verb generates numbers up to its argument, that's why we need to increment each element, \>: in J

```
a=.>:?7 7$9

```

```
2 8 7 4 4 5 1
4 5 4 1 6 7 9
3 8 3 6 5 3 3
6 8 6 3 7 7 1
7 7 4 4 5 9 9
2 3 6 5 2 2 9
2 2 6 8 8 1 3

```

I prepare a mask to be used for zeroing of the odd row/col cells, a pairs of odd row/column indices:

```
m=.{;~1 3 5
┌───┬───┬───┐
│1 1│1 3│1 5│
├───┼───┼───┤
│3 1│3 3│3 5│
├───┼───┼───┤
│5 1│5 3│5 5│
└───┴───┴───┘

```

The Catalogue verb { combines items from the atoms inside the boxed list

```
┌─────┬─────┐
│1 3 5│1 3 5│
└─────┴─────┘

```

to form a catalogue, the 3x3 table of the pairs above

Then I prepare a table of row/col indices to be used for selection of each of the 3x3 subarrays.

```
s=.(,&.>/@(<:,],>:)"0)&.>m
┌─────────────┬─────────────┬─────────────┐
│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│
││0 1 2│0 1 2│││0 1 2│2 3 4│││0 1 2│4 5 6││
│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│
├─────────────┼─────────────┼─────────────┤
│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│
││2 3 4│0 1 2│││2 3 4│2 3 4│││2 3 4│4 5 6││
│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│
├─────────────┼─────────────┼─────────────┤
│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│
││4 5 6│0 1 2│││4 5 6│2 3 4│││4 5 6│4 5 6││
│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│
└─────────────┴─────────────┴─────────────┘

```

For each pair in the m array I make a pair of triplets, centered around each number of the m pair:

```
        ┌─────┬─────┐
 1 3 -> │0 1 2│2 3 4│
        └─────┴─────┘

```

These pairs of triplets are used by the J From verb {, which can select multiple rows and columns simultaneously. 0 1 2 / 2 3 4 means that I select rows 0, 1 and 2 together with columns 2, 3 and 4, thus selecting the second 3x3 subarray on the top.

Finally, I can use the 7x7 array and the masks to achieve the task: First I use m as a mask to set the corresponding elements to 0:

```
0 m}a

```

Then I take all the 3x3 subarrays using s as a selector and find their sums:

```
+/^:_"2 s{0 m}a

```

Then I put these numbers back into the starting array.

```
 (+/^:_"2 s{0 m}a)m}a

```

```
2  8 7  4 4  5 1
4 39 4 39 6 36 9
3  8 3  6 5  3 3
6 44 6 40 7 42 1
7  7 4  4 5  9 9
2 36 6 43 2 46 9
2  2 6  8 8  1 3

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Unicode), ~~32~~ ~~31~~ 30 bytesSBCS

-1 byte thanks to @jslip

```
|a-m×+/+/⊢⌺3 3⊢a←?9⌈m←∘.⍱⍨2|⍳7

```

Try it online!

# Answer
> 1 votes
## Ruby, 207

I shall present my solution first (as I always do):

```
a=Array.new(7){Array.new(7){rand(9)+1}}
s=[-1,0,1]
s=s.product s
s.slice!4
r=[1,3,5]
r.product(r).map{|x|u=0
s.map{|y|u+=a[x[0]+y[0]][x[1]+y[1]]}
a[x[0]][x[1]]=u}
puts a.map{|x|x.map{|y|y.to_s.ljust 3}.join

```

# Answer
> 1 votes
### Ruby, 150 characters

```
v=(a=0..6).map{a.map{rand(9)+1}}
(o=[1,3,5]).map{|i|o.map{|j|v[i][j]=0
(d=[0,-1,1]).map{|r|d.map{|c|v[i][j]+=v[i+r][j+c]}}}}
puts v.map{|r|"%-3d"*7%r}

```

if the left justification requirement justification is just that `ljust` would have to be used... well, no. I love Ruby's formatting capabilities.

Do not use `Array.new(7){...}`. `(0..6).map{...}` is both shorter and more readable *and* you get an assignable range for free.

Line #3 inspired by Doorknob's solution.

# Answer
> 1 votes
### GolfScript, 87 chars

```
49,{.1&\7/1&!|9rand)*}%.7/{[..1>@0\+]zip{{+}*}%);}:^%zip{^~}%]zip{.0=!=}%{'  '+3<}%7/n*

```

There are too many zips in there... (see online)

```
3  9  9  3  3  9  8
6  46 2  50 3  39 8
7  3  7  2  4  7  3
8  33 9  51 8  49 5
4  3  9  9  3  9  2
1  45 9  41 6  33 2
4  3  6  1  6  1  4

```

# Answer
> 1 votes
### J, 58/64/67 characters

```
0j_1":(7$0,:7$0 1){"0 1 |:>v;v-~7 7{.0,.0,3+/\"1]3+/\v=.1+?7 7$9

```

While the specification requires the numbers to be left-aligned, there is no requirement to use the decimal notation, so I guess this is valid output:

```
1.0e0 8.0e0 9.0e0 6.0e0 2.0e0 9.0e0 6.0e0
6.0e0 3.9e1 8.0e0 4.0e1 2.0e0 3.8e1 4.0e0
1.0e0 4.0e0 2.0e0 8.0e0 3.0e0 9.0e0 3.0e0
2.0e0 2.4e1 5.0e0 4.1e1 9.0e0 4.7e1 8.0e0
1.0e0 3.0e0 6.0e0 5.0e0 3.0e0 5.0e0 7.0e0
4.0e0 3.0e1 1.0e0 2.3e1 1.0e0 3.1e1 1.0e0
6.0e0 5.0e0 4.0e0 2.0e0 1.0e0 5.0e0 8.0e0

```

If right alignment instead of left alignmnent is acceptable, we're at **58 characters**

```
(7$0,:7$0 1){"0 1 |:>v;v-~7 7{.0,.0,3+/\"1]3+/\v=.1+?7 7$9

```

J's `":` (format) has three formatting modes:

* right-aligned with n digits or with shrink-wrap (default display)
* left-aligned scientific notation with n digits and m characters total
* shrinkwrap boxed display with (left/center/right)-(top/middle/bottom) alignment (below, 69 characters)

The most verbose but also most versatile and the only one able to produce the output as per the example is the `8!:2` formatting foreign, which takes a formatting string as its left argument. Also **67 characters**:

```
'l3.'8!:2(7$0,:7$0 1){"0 1 |:>v;v-~7 7{.0,.0,3+/\"1]3+/\v=.1+?7 7$9

```

Here is the boxed format:

```
 0 0":<"0(7$0,:7$0 1){"0 1 |:>v;v-~7 7{.0,.0,3+/\"1]3+/\v=.1+?7 7$9

 ┌─┬──┬─┬──┬─┬──┬─┐
 │2│6 │5│7 │5│7 │6│
 ├─┼──┼─┼──┼─┼──┼─┤
 │8│40│4│35│9│49│6│
 ├─┼──┼─┼──┼─┼──┼─┤
 │6│7 │2│2 │1│9 │6│
 ├─┼──┼─┼──┼─┼──┼─┤
 │8│41│9│35│3│45│7│
 ├─┼──┼─┼──┼─┼──┼─┤
 │3│1 │5│6 │7│8 │4│
 ├─┼──┼─┼──┼─┼──┼─┤
 │7│37│4│45│6│48│8│
 ├─┼──┼─┼──┼─┼──┼─┤
 │8│4 │5│4 │8│1 │6│
 └─┴──┴─┴──┴─┴──┴─┘

```

# Answer
> 1 votes
## Perl, 117 characters

```
print$_,++$j%7?$":$/for map{++$i/7&$i%7&1?
eval join"+",@x[map{$i+$_,$i-$_}1,6,7,8]:" $_"}@x=map{1+int rand 9}$i--..48

```

This is one of those Perl scripts where all but one of the for loops have been collapsed into `map` calls so that everything can be done in a single statement. Global variables also make some important appearances in this one. I guess what I'm trying to say here is, this program is a bit gross.

Wait, it gets worse: There's a known bug in the script! It has less than a one-in-a-million chance of getting triggered, though, so I haven't gotten around to fixing it yet.

# Answer
> 1 votes
## *Mathematica*, 106 / 100

I came up with something very similar to ssch's code, before seeing it. I am borrowing his idea of using `Column`. With ASCII only, **106**:

```
s=#-1;;#+1&
a=8~RandomInteger~{7,7}+1
a[[##]]=a[[s@#,s@#2]]~Total~2-a[[##]];&@@@{2,4,6}~Tuples~2
Column/@a

```

With Unicode characters (as used by ssch), **100**:

```
s=#-1;;#+1&
a=8~RandomInteger~{7,7}+1
a〚##〛=a〚s@#,s@#2〛~Total~2-a〚##〛;&@@@{2,4,6}~Tuples~2
Column/@a

```

# Answer
> 1 votes
# Powershell, ~~149~~ 148 bytes

*-1 byte thanks to @AdmBorkBork. It's cool!*

```
$i=-1
($a=(,1*8+0,1*3)*3+,1*7|%{$_*(1+(Random 9))})|?{++$i;!$_}|%{6..8+1|%{$_,-$_}|%{$a[$i]+=$a[$i+$_]}}
-join($a|%{if(!(++$i%7)){"
"};'{0,3}'-f$_})

```

Explanation:

```
$i=-1                       # let $i store -1
($a=                        # let $a is array of random numbers with zero holes
    (,1*8+0,1*3)*3+,1*7|    # the one-dimension array equals
                            # 1 1 1 1 1 1 1
                            # 1 0 1 0 1 0 1
                            # 1 1 1 1 1 1 1
                            # 1 0 1 0 1 0 1
                            # 1 1 1 1 1 1 1
                            # 1 0 1 0 1 0 1
                            # 1 1 1 1 1 1 1
    %{                      # for each element
        $_*(1+(Random 9))   # multiply 0 or 1 element to random digit from 1 to 9
    }                       # now $a stores values like (* is a random digit from 1 to 9)
                            # * * * * * * *
                            # * 0 * 0 * 0 *
                            # * * * * * * *
                            # * 0 * 0 * 0 *
                            # * * * * * * *
                            # * 0 * 0 * 0 *
                            # * * * * * * *
)|?{++$i;!$_                # calc index $i and passthru values == 0 only
}|%{                        # for each zero value cell with index $i
    6..8+1|%{               # offsets for the surrounding cells
                            #  .  .  .
                            #  .  x +1
                            # +6 +7 +8
        $_,-$_              # add the mirror offsets
                            # -8 -7 -6
                            # -1  x +1
                            # +6 +7 +8
    }|%{                    # for each offset
        $a[$i]+=$a[$i+$_]   # add surrounding values to the cell
    }
}
                            # display the $a
-join(
    $a|%{                   # for each value of $a
        if(!(++$i%7)){"`n"} # line break for each 7 cells
        '{0,3}'-f$_         # formatted value of $a with width = 3 char and align right
    }
)                           # join all values to string

```

# Answer
> 1 votes
# Excel VBA, 74 bytes

VBE immediate function that outputs to `[B2:H9]`.

```
[B2:H9]="=IF(ISODD(ROW()*COLUMN()),SUM(A1:C1,A2,C2,A3:C3),INT(RAND()*8)+1)

```

# Sample Output

# Answer
> 0 votes
# Mathematica ~~142 151 172~~ 179

**Code**

```
z = (m = RandomInteger[{1, 9}, {7, 7}]; s = SparseArray; o = OddQ; e = EvenQ; i = {1, 1, 1};
(m + ArrayPad[ListCorrelate[{i, i, i}, m] s[{{i_, j_} /; o@i \[And] o@j -> 1}, {5, 5}], 1]
- 2 m s[{{i_, j_} /; e@i \[And] e@j -> 1}, {7, 7}]) // Grid)

```

**Usage**

```
z

```

# Answer
> 0 votes
# Julia 0.6, 127 (89) bytes

```
x=rand(1:9,7,7);[x[i,j]=sum(!(0==k==l)*x[i+k,j+l]for k=-1:1,l=-1:1)for i=2:2:7,j=2:2:7]
Base.showarray(STDOUT,x,1<1;header=1<1)

```

Try it online!

**89** bytes using native display, which might be admissible if additional lines can be printed:

```
7×7 Array{Int64,2}:
6   6  8   2  3   2  3
7  44  5  33  4  23  5
3   8  1   9  1   3  2
4  41  2  37  5  22  2
7   8  8   8  3   4  2
9  53  6  44  7  36  3
7   7  1   9  2   6  9

```

# Answer
> 0 votes
# Java 10, ~~262~~ ~~260~~ ~~248~~ 239 bytes

```
v->{int a[][]=new int[7][7],i=49,j,k;for(;i-->0;)a[i/7][i%7]+=Math.random()*9+1;var r="";for(;++i<7;r+="\n")for(j=0;j<7;r+=(k=a[i][j])>9|j++%2<1?k+" ":k+"  ")if(i*j%2>0)for(a[i][j]=k=0;k<9;k++)a[i][j]+=k!=4?a[i+k/3-1][j+k%3-1]:0;return r;}

```

-12 bytes thanks to *@ceilingcat*.

**Explanation:**

Try it here.

```
v->{                        // Method with empty unused parameter and String return-type
  int a[][]=new int[7][7],  //  Integer-matrix with 7x7 zeroes
      i=49,j,k;             //  Index integers (`i` starting at 49)
  for(;i-->0;)              //  Loop `i` in the range (49, 0]:
    a[i/7][j%7]+=Math.random()*9+1;
                            //   Fill the current cell with a random 1..9 integer
  var r="";                 //  Result-String, starting empty
  for(;++i<7;               //  Loop `i` in the range [0, 7):
      r+="\n")              //    After every iteration: append a new-line to the result
    for(j=0;j<7;            //   Inner loop `j` in the range [0, 7):
        r+=                 //     After every iteration: append the result-String with:
           (k=a[i][j])>9    //      If the current number has 2 digits,
           |j++%2<1?        //      or it's an even column (indices 0/2/4/6)
            k+" "           //       Append the current number appended with one space
           :                //      Else:
            k+"  ")         //       Append the current number appended with two spaces
      if(i*j%2>1)           //    If both indexes `i` and `j` are odd
        for(a[i][j]=k=0;    //     Reset both the current item and index `k` to 0
            k<9;k++)        //     Inner loop `k` in the range [0, 9):
          a[i][j]+=         //      Sum the item at location `i,j` with:
           k!=4?            //       If `k` is not 4 (the current item itself)
            a[i+k/3-1][j+k%3-1]
                            //        Sum it with the numbers surrounding it
           :                //       Else:
            0;              //        Leave it the same by adding 0
  return r;}                //  Return the result-String

```

---
Tags: code-golf, number, generation, grid
---


title: When in Rome, Count as Romans do?

text:
# Question
Title: When in Rome, Count as Romans do?
# Background

This challenge is inspired by this website, which published the following diagram:

This diagram shows us that the longest Roman Numeral expression under 250 is that of 188, which requires 9 numerals to express.

# Challenge

The standard symbols used to express most Roman Numerals are the following: {`I`, `V`, `X`, `L`, `C`, `D`, `M`}, where the characters' numeric values are `M`=1000, `D`=500, `C`=100, `L`=50, `X`=10, `V`=5, `I`=1.

In this challenge, your goal is to, given an positive integer *n*, compute the number of valid Roman Numeral representations that can be composed through concatenating *n* of the standard symbols.

Then, your program must output the result of this computation!

**Input**: A positive integer *n*.

**Output**: The number of valid roman numeral expressions of length *n*.

# Rules for Roman Numeral Expressions

Roman Numerals originally only had "additive" pairing, meaning that numerals were always written in descending order, and the sum of the values of all the numerals was the value of the number.

Later on, subtractive pairing, the use of placing a smaller numeral in front of a larger in order to subtract the smaller from the larger, became commonplace to shorten Roman Numeral expressions. Subtractive pairs cannot be chained, like in the following invalid expression: `IXL`.

The following are the modern day rules for additive and subtractive pairing.

1. Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.
2. I can only be placed before V or X in a subtractive pair.
3. X can only be placed before L or C in a subtractive pair.
4. C can only be placed before D or M in a subtractive pair.
5. Other than subtractive pairs, numerals must be in descending order (meaning that if you drop the leading numeral of each subtractive pair, then the numerals will be in descending order).
6. M, C, and X cannot be equalled or exceeded by smaller denominations.
7. D, L, and V can each only appear once.
8. Only M can be repeated 4 or more times.

# Further Notes

* We will not be using the *bar* notation; rather, we will simply add more *M*s to express any number.
* These are the **only** rules that we will follow for our roman numerals. That means that odd expressions, such as `IVI`, will also be considered valid in our system.
* Also remember that we are not counting the number of numbers that have expressions of length *n*, since some numbers have multiple expressions. Instead, we are solely counting the number of valid expressions.

# Test Cases

`1``7`

`2``31`

`3``105`

I checked the above by hand, so please make sure to double check the test cases, and add more if you can!

# Winning Criteria

This is a challenge, so have fun! I will only accept solutions that can handle at least inputs from 1 through 9. Any more is bonus!

# Edit

As requested by commenters, find below, or at this pastebin link, the 105 combos I counted for *n*=3

> III IVI IXI IXV IXX VII XII XIV XIX XVI XXI XXV XXX XLI XLV XLX XCI XCV XCX XCL XCC LII LIV LIX LVI LXI LXV LXX CII CIV CIX CVI CXI CXV CXX CXL CXC CLI CLV CLX CCI CCV CCX CCL CCC CDI CDV CDX CDL CDC CMI CMV CMX CML CMC CMD CMM DII DIV DIX DVI DXI DXV DXX DXL DXC DLI DLV DLX DCI DCV DCX DCL DCC MII MIV MIX MVI MXI MXV MXX MXL MXC MLI MLV MLX MCI MCV MCX MCL MCC MCD MCM MDI MDV MDX MDL MDC MMI MMV MMX MML MMC MMD MMM

# Edit 2:

Use the following non-golfed code, as courtesy of Jonathan Allan to check your results.

# Edit 3:

I apologize for all of the errors in this challenge. I'll make sure to do a better job next time!

# Answer
> 3 votes
# Retina, 111 bytes

```
~(`.+
*$(CM)CDXCXCXCXLIXIXIXIVII
.(.)
.+¶$$&$¶$$&$1$¶$$&$&¶L`.{0,$+}\b¶D`¶
¶$
¶.+¶$$&$¶$$&I¶L`[A-Z]{$+}\b¶D`¶.+

```

Try it online! This is a complete rewrite as I misunderstood rule 1. to mean that you could only use one each of subtractive `I`, `X` and `C`. Explanation: The first part of the script expands the input into a string of `CM` pairs followed by the other possible subtractive pairs. Each pair is optional, and the first character of each pair is also optional within the pair. The third stage then expands the list of pairs into a list of Retina commands that take the input and create three copies with the option of the second or both characters from the pair, then trims and deduplicates the results. The final stage then appends code to perform the final tasks: first to expand the input to possibly add a final `I`, then to filter out results of the wrong length, then to deduplicate the results, and finally to count the results. The resulting Retina script is then evaluated.

Note: In theory 15 bytes could be saved from the end of the 4th line but this makes the script too slow to demonstrate on TIO even for `n=1`.

# Answer
> 5 votes
# Python 2, ~~177 168~~ 162 bytes

```
import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

```

Try it online!

I'm pretty new, help me golf this! This checks for actual roman numerals, the regex needs to be adjusted to account for the odd cases such as `IVI`

**-9 bytes** thanks to @Dead Possum!

**-6 bytes** thanks to @ovs

# Answer
> 3 votes
# JavaScript (ES7), 133 bytes

***Edit**: Fixed to match the results returned by Jonathan Allan's code, which was given as a reference implementation by the OP.*

---

```
n=>[...Array(m=k=7**n)].reduce(s=>s+/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test((--k+m).toString(7).replace(/0[62]|2[34]|4[51]/g,s=>s[1])),0)

```

Try it online!

### How?

1) We generate all numbers of \\$N\\$ digits in base 7 with an extra leading \\$1\\$:

```
[...Array(m = k = 7 ** n)].reduce(s => … (--k + m).toString(7) …, 0)

```

From now on, each digit will be interpreted as a Roman numeral symbol:

$$\begin{array}{}0\longleftrightarrow \text{I}, & 1\longleftrightarrow \text{M}, & 2\longleftrightarrow \text{X}, & 3\longleftrightarrow \text{L},\\ 4\longleftrightarrow \text{C}, & 5\longleftrightarrow \text{D}, & 6\longleftrightarrow \text{V} \end{array}$$

2) We replace all valid subtractive pairs of the form `AB` with `B`:

```
.replace(/0[62]|2[34]|4[51]/g, s => s[1]))  // in the code
.replace(/I[VX]|X[LC]|C[DM]/g, s => s[1]))  // with Roman symbols

```

**Examples:**

* `XLIXIV` becomes `LXV`
* `XIIV` becomes `XIV`, leaving a `I` that will make the next test fail
* `IC` remains unchanged, which also leaves an invalid `I` in place

3) We check that the remaining symbols are in the correct order and do not appear more times than they're allowed to:

```
/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test(…)  // in the code
/^M*D?C{0,3}L?X{0,3}V?I{0,3}$/.test(…)  // with Roman symbols

```

# Answer
> 0 votes
# C, 150 123 bytes

I didn't read the description closely enough, so this produces the number of standard Roman numerals (where expressions like `IVI` aren't counted). Since I put some effort into it, I thought I would share anyway.

```
#define F(X) for(X=10;X--;)
x[]={0,1,2,3,2,1,2,3,4,2};f(i,o,a,b,c){for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];return o;}

```

Original (150 bytes):

```
#define F(X) for(X=10;X--;)
i,o,a,b,c,x[]={0,1,2,3,2,1,2,3,4,2};main(){scanf("%i",&i);for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];printf("%i\n",o);}

```

---
Tags: code-golf, roman-numerals
---


title: A knight's graph on an N-by-N board

text:
# Question
Title: A knight's graph on an N-by-N board
In chess, a knight can only move to the positions marked with X relative to its current position, marked with ♞:

---

A Knight's Graph is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.

The graph looks like this for a standard 8-by-8 board.

---

### Challenge:

Given an integer **N**, where **3 ≤ N ≤ 8**, output an **N-by-N** matrix representing a board, where the number of possible moves from each position is shown. For **N = 8**, the output will be a matrix showing the values of each vertex in the graph above.

The output format is flexible. List of lists or even a flattened list etc. are accepted formats.

---

### Complete set of test cases:

```
--- N = 3 ---
2 2 2
2 0 2
2 2 2
--- N = 4 ---
2 3 3 2
3 4 4 3
3 4 4 3
2 3 3 2
--- N = 5 ---
2 3 4 3 2
3 4 6 4 3
4 6 8 6 4
3 4 6 4 3
2 3 4 3 2
--- N = 6 ---
2 3 4 4 3 2
3 4 6 6 4 3
4 6 8 8 6 4
4 6 8 8 6 4
3 4 6 6 4 3
2 3 4 4 3 2
--- N = 7 ---
2 3 4 4 4 3 2
3 4 6 6 6 4 3
4 6 8 8 8 6 4
4 6 8 8 8 6 4
4 6 8 8 8 6 4
3 4 6 6 6 4 3
2 3 4 4 4 3 2
--- N = 8 ---
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

```

---

This is so the shortest solution in each language wins. **Explanations are encouraged!**

# Answer
# MATL, ~~17~~ 16 bytes

```
t&l[2K0]B2:&ZvZ+

```

Try it online!

*(-1 byte thanks to @Luis Mendo.)*

The main part of the code is creating a matrix \\$ K \\$ for convolution:

$$ \mathbf{K} = \begin{pmatrix}0&1&0&1&0\\1&0&0&0&1\\0&0&0&0&0\\1&0&0&0&1\\0&1&0&1&0\end{pmatrix} $$

(Relative to the centre of the matrix, each 1 is a valid knight's move.)

`t&l` \- Form a nxn matrix of all 1s (where n is the input). Let this be M.

`[2K0]` \- Push an array containing \[2, 4, 0\] on stack

`B` \- Convert all to binary, padding with 0s as needed

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

```

`2:&Zv` \- Mirror that on both dimensions, without repeating the final row/column ("symmetric range indexing"). This gives us the required matrix K.

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

```

`Z+` \- Perform 2D convolution of K over the earlier matrix M (`conv2(M, K, 'same')`), summing up the 1s at legal knight move targets for each position

Result matrix is displayed implicitly.
> 13 votes

# Answer
# Python 2, 81 bytes

```
lambda n:[sum(2==abs((i/n-k/n)*(i%n-k%n))for k in range(n*n))for i in range(n*n)]

```

Try it online!
> 12 votes

# Answer
# JavaScript (ES6), 88 bytes

Returns a string.

```
n=>(g=k=>--k?[n>3?'-2344-6-6'[(h=k=>k*2<n?~k:k-n)(k%n)*h(k/n|0)]||8:k-4&&2]+g(k):2)(n*n)

```

Try it online!

## How?

### Special case: \\$n=3\\$

We fill each cell with \\$2\\$, except the center one which is set to \\$0\\$:

$$\pmatrix{2 & 2 & 2\\ 2 & 0 & 2\\ 2 & 2 & 2}$$

### Other cases: \\$3\<n\le 8\\$

For each cell \\$(x,y)\\$ with \\$0\le x\<n\\$ and \\$0\le y\<n\\$, we compute a lookup index \\$i\_{x,y}\\$ defined as:

$$i\_{x,y}=\min(x+1,n-x)\times \min(y+1,n-y)$$

For \\$n=8\\$, this gives:

$$\pmatrix{1 & 2 & 3 & 4 & 4 & 3 & 2 & 1\\ 2 & 4 & 6 & 8 & 8 & 6 & 4 & 2\\ 3 & 6 & 9 & 12 & 12 & 9 & 6 & 3\\ 4 & 8 & 12 & 16 & 16 & 12 & 8 & 4\\ 4 & 8 & 12 & 16 & 16 & 12 & 8 & 4\\ 3 & 6 & 9 & 12 & 12 & 9 & 6 & 3\\ 2 & 4 & 6 & 8 & 8 & 6 & 4 & 2\\ 1 & 2 & 3 & 4 & 4 & 3 & 2 & 1}$$

The lookup table \\$T\\$ is defined as:

$$T = \[0,2,3,4,4,0,6,0,6\]$$

where \\$0\\$ represents an unused slot.

We set each cell \\$(x,y)\\$ to:

$$\begin{cases}T(i\_{x,y})&\text{if }i\_{x,y} \le 8\\8&\text{otherwise}\end{cases}$$

---

# JavaScript (ES7), 107 bytes

A naive implementation which actually tries all moves.

```
n=>[...10**n-1+''].map((_,y,a)=>a.map((k,x)=>~[...b=i='01344310'].map(v=>k-=!a[x-v+2]|!a[y-b[i++&7]+2])+k))

```

Try it online!
> 8 votes

# Answer
# Jelly,  ~~23 22 14~~  10 bytes

```
²ḶdðạP€ċ2)

```

A monadic link yielding a flat list - uses the idea first used by KSab in their Python answer \- knight's moves have "sides" 1 and 2, the only factors of 2.

**Try it online!** (footer calls the program's only Link and then formats the result as a grid)

Alternatively, also for 10 bytes, `²Ḷdðạ²§ċ5)` (knight's moves are all of the possible moves with distance \\$\sqrt{5}\\$)

### How?

```
²ḶdðạP€ċ2) - Link: integer, n (any non-negative) e.g. 8
²          - square n                                 64
 Ḷ         - lowered range                            [0,    1,    2,    3,    4,    5,    6,    7,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,   38,   39,   40,   41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,   55,   56,   57,   58,   59,   60,   61,   62,   63]
  d        - divmod (vectorises) i.e. x->[x//n,x%n]   [[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[3,7],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7]]
   ð     ) - new dyadic chain for each - call that L ( & e.g. R = [1,2] representing the "2nd row, 3rd column" ...-^ )
    ạ      -   absolute difference (vectorises)       [[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[0,2],[0,1],[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[2,1],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[3,2],[3,1],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[4,2],[4,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,2],[5,1],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[6,2],[6,1],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5]]
     P€    -   product of €ach                        [2,    1,    0,    1,    2,    3,    4,    5,    0,    0,    0,    0,    0,    0,    0,    0,    2,    1,    0,    1,    2,    3,    4,    5,    4,    2,    0,    2,    4,    6,    8,    10,   6,    3,    0,    3,    6,    9,    12,   15,   8,    4,    0,    4,    8,    12,   16,   20,   10,   5,    0,    5,    10,   15,   20,   25,   12,   6,    0,    6,    12,   18,   24,   30]
       ċ2  -   count 2s                          6:    ^-...1                  ^-...2                                                                  ^-...3                  ^-...4                        ^-...5      ^-...6
           - )                                                                                v-...that goes here
           -   ->                                  -> [2,    3,    4,    4,    4,    4,    3,    2,    3,    4,    6,    6,    6,    6,    4,    3,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    3,    4,    6,    6,    6,    6,    4,    3,    2,    3,    4,    4,    4,    4,    3,    2]

```

---

**Previous 22 byter**

```
2RżN$Œp;U$+,ḟ€³R¤Ẉ¬Sðþ

```

A full program (due to `³`).

**Try it online!** (footer calls the program's only Link and then formats the result as a grid)

Finds all moves and counts those which land on the board ~~probably~~ *definitely* beatable by calculating (maybe beatable by changing the "land on the board" logic).
> 6 votes

# Answer
# APL (Dyalog Classic), 18 bytes

```
+/+/2=×/¨|∘.-⍨⍳2⍴⎕

```

Try it online!

evaluated input N

`2⍴⎕` two copies of N

`⍳2⍴⎕` the indices of an N×N matrix - a matrix of length-2 vectors

`∘.-⍨` subtract each pair of indices from each other pair, get an N×N×N×N array

`|` absolute value

`×/¨` product each

`2=` where are the 2s? return a boolean (0/1) matrix

Note that a knight moves ±1 on one axis and ±2 on the other, so the absolute value of the product of those steps is 2. As 2 can't be factored in any other way, this is valid only for knight moves.

`+/+/` sum along the last dimension, twice
> 4 votes

# Answer
# Brachylog, 65 40 33 bytes

This breaks down for N bigger then 9. So I'm happy N can be only go to 8 =)

```
⟦₅⟨∋≡∋⟩ᶠ;?z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ

```
* -25 bytes by switching to KSab's formula
* -7 bytes by flattening the array thanks to sundar

Try it online!

---

# Brachylog, 44 36 bytes

This one also works for number higher then 9

```
gP&⟦₅⟨∋≡∋⟩ᶠ;z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ

```
* -8 bytes by flattening the array thanks to sundar

Try it online!
> 3 votes

# Answer
# RAD, ~~51~~ ~~46~~ 39 bytes

```
{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵

```

Try it online!

## How?

Counts the number of valid knight moves for each square by seeing which knight moves would land on the board:

```
{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵
 +/                                     - The number of ...
                            ∊,W         - ... in-bounds ...
        (⊖,⊢)(⊢,-)(⍳2)(1¯2)             - ... knight movements ...
   (⍵∘+¨                   )            - ... from ...
{                              }¨¨W←⍳⍵⍵ - ... each square

```
> 3 votes

# Answer
# Python 2, ~~114~~ ~~103~~ 92 bytes

```
lambda n:[sum((d*c>d)+(d*c>c)for d in(y%n,n-y%n-1)for c in(y/n,n-y/n-1))for y in range(n*n)]

```

Try it online!
> 2 votes

# Answer
# Retina, 161 bytes

```
.+
*
L$`_
$=
(?<=(¶)_+¶_+)?(?=(?<=(¶)_*¶_*)__)?(?<=(¶)__+)?(?=(?<=(¶)_*)___)?_(?=(?<=___)_*(¶))?(?=__+(¶))?(?=(?<=__)_*¶_*(¶))?(?=_+¶_+(¶))?
$.($1$2$3$4$5$6$7$8)

```

Try it online! Link includes test cases. Explanation:

```
.+
*

```

Convert to unary.

```
L$`_
$=

```

List the value once for each `_` in the value, i.e. create a square.

```
(?<=(¶)_+¶_+)?
(?=(?<=(¶)_*¶_*)__)?
(?<=(¶)__+)?
(?=(?<=(¶)_*)___)?
_
(?=(?<=___)_*(¶))?
(?=__+(¶))?
(?=(?<=__)_*¶_*(¶))?
(?=_+¶_+(¶))?

```

Starting at the `_` in the middle of the regex, try to match enough context to determine whether each of the eight knight's moves is possible. Each pattern captures a single character if the match succeeds. I tried using named groups so that the number of captures directly equals the desired result but that cost 15 bytes.

```
$.($1$2$3$4$5$6$7$8)

```

Concatenate all the successful captures and take the length.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 34 bytes

Yet another Mathematica built-in.

```
VertexDegree@KnightTourGraph[#,#]&

```

Returns a flattened list.

Try it online!
> 2 votes

# Answer
# C (gcc), 133 125 bytes

This solution should work on any size board.

```
#define T(x,y)(x<3?x:2)*(y<3?y:2)/2+
a,b;f(i){for(a=i--;a--;)for(b=i+1;b--;)printf("%i ",T(a,b)T(i-a,b)T(a,i-b)T(i-a,i-b)0);}

```

Try it online!
> 1 votes

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