title: Tips for golfing in Japt

text:
# Question
Title: Tips for golfing in Japt
Now that I'm thoroughly addicted to Code Golf, it's probably about time that I try to pick up a few golfing languages.

Given that I play almost exclusively in JavaScript, Japt seems like the logical language to start with. I'll be diving into the documentation at the next opportunity I get but, in the meantime, please post any tips you have for Japt in the answers below.

As I'm a beginner in Japt and golfing languages in general, if you could "translate" your tips to JavaScript, where possible, that would be a big help in helping me get to grips with things.

# Answer
> 12 votes
## Moving from JavaScript to Japt

As you may know, Japt is simply a shortened, extended version of JavaScript. I created Japt because I was tired of long property names, like `String.fromCharCode(x)` and `Math.floor(x)`, and the tediousness of doing things such as creating a range. Here's the bare minimum you need to know when going from JavaScript to Japt:

* Japt is a *transpiled* language; Japt code is *transpiled* to JavaScript and then run as JS. (I guess you could say *compiled*, but transpiled sounds more hipster. Disclaimer: I know absolutely nothing about being hipster)
* All entries are full programs by default. The input is implicitly parsed, and the first six inputs are put into the variables `U`, `V`, `W`, `X`, `Y`, and `Z`; the full array is stored in `N`. The result of the last expression is automatically printed.
* All uppercase letters are variables, and stay the same when transpiled. Most have preset values, which you can find in the "Variables" section of the Japt docs (at the interpreter).
* All lowercase letters are prototype functions, or *methods*. Japt adds the methods `a`-`z` (and `à`-`ÿ`) on numbers, strings, and arrays. When you use one of these letters, Japt fills in the `.` and `(`; `Uc` in Japt is equivalent to `U.c(` in JavaScript, which could mean ceil, charCodeAt, or concat, depending on the type of `U`. This is where most of Japt's power comes from; you can find full lists of these methods under the "\_____ functions" sections of the Japt docs (at the interpreter).
* A space represents `)`, and `)` represents `))`. This is because when I first designed Japt, I wanted to save as many bytes as possible, and that's how I first thought of doing this. (Though `Us w n` does look better than `Us)w)n)`, IMHO.)
* A function is denoted as `ABC{...}`, where the `ABC` can be any string of variables. Functions work for the most part as they do in JS, the main difference being the last expression is automatically returned (rather than having to use `return` or fancy ES6 parentheses).
* `'` denotes a single char string (i.e. `'a` is the same as `"a"`), and `#` takes the next char-code and becomes that number (`#e` is the same as `101`).
* Anything between dollar signs `$` stays the same during the transpilation process. You can use this to implement `for` loops, for example, since Japt doesn't have those, but I would suggest using other methods (such as `m` on strings and arrays, or `o` on numbers).
* Most other chars commonly used in JS — `""`, `0-9`, `(`, `+`, `=`, etc. — stay the same when transpiled (for the most part, anyway).

And that is all you need to know to write basic Japt code. Achieving maximum golf power in Japt requires more knowledge, but that can be found in other answers.

---

Here's a basic example. Say you have want to take a string of ASCII characters and replace each with its hexadecimal char code. Here's how you might do that in JavaScript:

```
U.split("").map(x=>x.charCodeAt(0).toString(16)).join("")

```

Now to convert to Japt. `.split("")` in JS is equivalent to `q""` in Japt, or even shorter, just `q`. `.join("")` is also just `q`, the difference being that the object is an array instead of a string. `.map(` is `m`, `.charCodeAt(` is `c`, and `.toString(` is `s`. So our Japt code might look like:

```
Uq mX{Xc0 s16} q

```

In Japt, though, `m` works as well on strings as it does on arrays, so we can remove both `q`s:

```
UmX{Xc0 s16}

```

Test it online! As you can see in the "JS code" box, this directly transpiles to:

```
U.m(function(X){return X.c(0).s(16)})

```

As you learn to work with Japt, you'll become less and less focused on converting back and forth from JavaScript and be able to code in Japt as its own language. Here's an explanation leaving out the JavaScript portion entirely:

```
UmX{Xc0 s16}
               // Implicit: U = input string
UmX{       }   // Take U, and replace each character X with the result of this function:
    Xc0        //   Take the char-code at index 0 in X (the first and only one).
        s16    //   Convert this to a hexadecimal string.
               // Implicit: output result of last expression

```

# Answer
> 8 votes
# Compressing String Arrays

> **UPDATE:** The tools featured in this tip have since be rewritten, improved and integrated into my Japt interpreter. For the best results it is recommended that you use that compressor over any of those linked below. I'll revisit this tip when I have some more time and rewrite it with the new compressor in mind.

## Introduction

If you have an array of strings in your code, the most obvious way to compress it would be to run each string through `Oc` individually. For the purposes of this tip, we'll be working with the array `["lollipop","marshmallow","nougat","oreo"]`, which weighs in at 42 bytes initially. Running each string through `Oc` gives us:

```
`[`lo¥ipop`,`Ú\hÚaow`,`Í`,`eo`]`
```

That's now 33 bytes, a decent saving.

---

## Step 1

**But**, we can do better. If we join the array to a newline separated string, we can get rid of the brackets, commas, and extraneous backticks and split on newline to get our array. Applying that to our example array gives us the following:

```
``lo¥ipop
Ú\hÚaow
Í
eo`·`
```

Down to 26 bytes now.

---

## Step 2

**But**, we can do better still! We could use a lowercase letter to delimit the strings instead of a newline, which might get included in the compression. `z` isn't used in any of our strings so let's drop that in, and see how we get on.

```
``lo¥ipopzÚ\hÚaowzÍzeo`qz`
```

Ah, nuts - no improvement there; our byte count has gone up by one! There might be another letter you could use but, depending on your strings, there could be quite a few to try - in our example there are 11: `b,c,d,f,j,k,q,v,x,y,z`. Trying each would be pretty tedious, which is where **this handy tool** comes in; feed it your newline separated strings and it will try to delimit the strings with each letter that's not contained in any of them and output:

* the shortest compressed string,
* the delimiter it uses, and
* its length.

Running our sample strings through it shows that `b` gives the best results:

```
``lo¥ipáæqrÚaowbÍÞo`qb`
```

And there you have it, we're down to just 24 bytes.

---

## Step 3

**But**, we can do *even* better! If the order of strings in your array doesn't matter, maybe there's a different permutation combined with a different delimiter that could work out even shorter. Trying each possibility is going to be much more tedious, though. With our 4 strings, there are 24 different permutations to try. With each of the 11 possible letters that becomes 264! That's where **this tool** comes into play. Again, feed it your newline separated strings and it will try every combination of every permutation and every delimiting letter, outputting:

* the order of the strings in the shortest compressed string,
* the compressed string,
* the delimiter it uses, and,
* its length.

Running our sample strings through it shows that `"nougat","oreo","lollipop","marshmallow"` with `b` as a delimiter gives the best results, with a final byte count of just 23:

```
``ÍÞo½o¥ipáæqrÚaow`qb`
```

---

## Bonus Tip: Integer Array Compression

You can apply the same principle to arrays of integers by first converting each to a higher base. Using this sample, 36 byte array:

```
`[588181,156859,595676,475330,680474]`
```

We can get that down to 29 bytes by first converting it to an array of base 32 strings and then running it through the first compression programme:

```
``huclt4p5r5ÛÊg62tkogq`qt mnH`
```

Or as low as 27 bytes using the second programme:

```
``4p5Ïcl5ÛÊg62tkogq`qt mnH`
```

You might be able to save another byte or 2 on top of that by moving the integer conversion into a method you're already running on the array.

---

## Notes

1. Don't forget to factor in the 1 or 2 extra bytes `q<letter>(<space>)` costs over `·`. Although, you may be able to use one of the Unicode shortcuts to get a byte back, depending on your delimiter ( is the same as `ql<space>`, for example).
2. A word of caution when using the last tool: the more strings you have, the more permutations there will be and the slower the programme will run, until it eventually craps out. As detailed above, with our 4 sample strings and 11 possible letters to try, there are 264 possible combinations, increase the number of strings by just 1 with the same 11 letters and we already have 1320 combinations to try. (You can use **this tool** to count the number of combinations, if you want).

---

## Credits

* Oliver for the inspiration to create the tools found in this tip.
* ETHproductions for proofreading.

# Answer
> 7 votes
## Compressing strings

Japt (currently) uses the shoco library for string compression. You can compress an arbitrary string using `Oc`, as long as it contains runs of lowercase letters:

```
Oc"Hello, World!"

```

This outputs `HÁM, WŽld!` (well, the `Ž` is technically an unprintable character). You can decompress this by wrapping it in backticks:

```
`HÁM, WŽld!`
```

Test it online!

Alternatively, you can use the `Od` function to decompress an arbitrary string. This isn't usually useful, but it has its purposes...

# Answer
> 6 votes
## Shortening Numbers With Char-Codes

In Japt, you can use `#`, followed by a character to create a char-code. This comes in handy when shortening longer numbers.

As @ETHproductions mentioned, this only works on three-digit runs in the range 100-255, unless you are willing to switch to UTF-8.

### Examples:

`123` can be shortened to `#{`

`101` can be shortened to `#e`

**You can even chain these together:**

`123101` can be shortened to `#{#e`

You can use `String.fromCharCode(123)` in JavaScript, or `123d` in Japt to find the appropriate character.

`String.fromCharCode(123)` returns `{`

# Answer
> 6 votes
# Quick tip: Empty array `[]`

Japt has a constant for an empty array: `A`. But, in order to access it, you must prepend a semicolon `;` to your programme to use Japt's alternative constants, otherwise `A` will be `10`. So using `;A` actually offers a 0 byte saving over `[]`, but *will* save you bytes if you need to assign your array to a variable (e.g., `A=[]`).

However, if (and only if) your programme is not taking any input, you can access the empty array with just 1 byte by using the `N` variable, which is the array of inputs - with no inputs, it would be empty. Try it out here.

This has also has the added benefit of allowing you to use the default constant values in your programme and, in some cases, can still save you bytes over using `;A` even when your programme is taking input thanks to the shortcuts for `s1` and `s2`.

# Answer
> 5 votes
## Evaluating JavaScript

Japt allows you to execute raw JavaScript by wrapping it around `$...$`.

For example, `$alert("hello world")$`

This can be shortened by taking advantage of Japt's auto-closing `$` and `)`.

`$alert("hello world")$` can be shortened to `$alert("hello world"`

### Compressing JavaScript

You can also compress JavaScript using `Ox`.

If there is a JavaScript function that you want to use, say `screen.width`, you can compress the string `"screen.width"` using `Oc`, then inserting the result in between Ox\`...\`

Note that you do not need closing quotes in Japt when it is not followed by anything else.

# Answer
> 5 votes
# Know the flags

As per the latest meta consensus (Dec 2017), command-line flags are no longer counted towards bytes. It's really a great news for Japt since it has many flags for extra treatment on input/output.

All available flags in Japt are described below, **in the order of evaluation**. The flags in the same group are exclusive to each other. Note that the flags in different groups can be used in combination, resulting in something like this :)

## `mdefæ`

The whole program is mapped over the first argument (`U`).

If more arguments are present, they are passed as-is (i.e. *not* pairwise mapped). Otherwise, the second argument is the index, and the third is the whole array, just like `U.m`. If `U` is a number, it is converted to range; if string, it's converted to array of chars and the results are joined together.

* `-m`: Applies the above and nothing else.
* `-d`: Returns `true` if some result is truthy, `false` otherwise.
* `-e`: Returns `true` if all results are truthy, `false` otherwise.
* `-f`: Returns the array of elements of `U` whose results are truthy.
* : Applies `-f` and returns its first element.

## `gh`

Takes an element at the specified index.

* `-g`: Takes first element (index 0).
* `-gX`: Takes the element at index `X` (can be any positive integer).
* `-h`: Takes last element.

##

Convert the result to boolean.

* `-!`: Apply boolean not.
* : Apply boolean not twice (returns the truthiness).

## `N`

Convert the result to number. The unary plus is used.

## `PRSQ`

Convert to string of some sort.

* `-P`: Join the array with `""`.
* `-R`: Join the array with `"\n"`.
* `-S`: Join the array with `" "`.
* `-Q`: Apply `JSON.stringify` (can be any object, not only an array). Example.

## `x`

Applies the function `x` to the output. (It's literally `x`, not "any single lowercase alphabet function".)

* Array: Sum.
* String: Trim from both ends.
* Number: Round to integer.

# Answer
> 4 votes
## Take advantage of preset variables

Variables `A`-`S` are preset to common values that take more than one byte to represent in Japt:

* `A`-`G` are `10`-`16`.
* `H` is `32`, `I` is `64`, `J` is `-1`, `L` is `100`.
* `K` is defined as `new Date()`, which you can manipulate in various ways.
* `M` and `O` are objects with various useful functions. You can learn more in the docs.
* `P` is the empty string, `Q` is a quote mark, `R` is a newlines, and `S` is a space.
* `T` is set to `0`, so you can use it as an accumulator if necessary.

---

If the first character in the program is a semicolon `;`, `A-L` are reset as follows:

* `A` is the empty array `[]`.
* `B` is `"ABCDEFGHIJKLMNOPQRSTUVWXYZ"`.
* `C` is `"abcdefghijklmnopqrstuvwxyz"`.
* `D` is `"QWERTYUIOP\nASDFGHJKL\nZXCVBNM"`.
* `E` is `"[a-z]"`, and `F` is `"[A-Za-z]"` (useful before I added these as regex features)
* `G` is `36`, `H` is `65`, and `I` is `91` (useful for alphabet ranges).
* `J` is a single comma; `L`, a single period.

Nowadays only `A`, `B`, `C`, and `D` from this list are really useful. I'm planning to add a better system which allows up to 256 two-byte variables, which will be preset to these values and a whole lot more.

# Answer
> 3 votes
## Unicode shortcuts

There are many common structures in Japt that just can't be stored in a single ASCII char, such as `qS`, `p2`, `mX{`, , etc. So to get around this, Japt has "Unicode shortcuts", which are characters in the range `\xA1`-`\xDE` (`¡`-`Þ`) which expand to these common structures. You can find a full list of these in the interpreter docs.

Additionally, `@` stands for `XYZ{`, and `_` stands for `Z{Z`, to help build functions. So let's golf our example program from another answer:

```
UmX{Xc0 s16}

```

Firstly, we can replace `X{X` with `_`, which gives us:

```
Um_c0 s16}

```

Then we can replace `m_` with `®` saving another byte:

```
U®c0 s16}

```

Or we could replace `X{` with `@`, which gives us:

```
Um@Xc0 s16}

```

This then allows us to use the `¡` shortcut to save two bytes:

```
¡Xc0 s16}

```

One of these two paths can be shortened 1 byte more than the other. Can you figure out which?

# Answer
> 3 votes
# Use auto-functions

You most likely already know that `@` and `_` are shortcuts for `XYZ{` and `Z{Z`, respectively (covered in the Unicode shortcuts answer). But sometimes you can make functions even shorter.

Suppose you had an array of characters and you wanted to map each character to its char-code. You could do this with either of these:

```
mX{Xc}
m_c}

```

But there's a better way. If a method or operator is the first item after another method or a `(`, it gets turned into a string. So these two lines are equivalent:

```
r'a'b  // Replace all "a"s with "b"s; transpiles to .r("a","b")
ra'b   // Does the same thing, 1 byte less; transpiles to the same thing

```

But how does that help with our functions? Well, most methods that accept functions, if given a string representing a method or operator, will interpret it as a function. Which means you can also do this:

```
m_c}  // Map each item to its char code
m'c   // Does the same thing, 1 byte less
mc    // Also does the same thing, 2 bytes less

```

I call these "auto-functions". There are several different varieties:

* `m@Xc}``mc`
* `m@Xc1}``mc1`
* `m@X+1}``m+1`
* `m@1+X}``m!+1`
* `m@2pX}``m!p2`

Hopefully you get the idea. To swap the arguments, just prefix the method or operator with `!`.

# Answer
> 3 votes
# Implicit Variable Assignment

Whenever you start a new line in Japt the result of the previous line is automatically assigned to one of the input variables (`U`-`Z`), with the first line being `U`, the second `V`, and so on.

Let's take an example: say you wanted to create 2 arrays to work with, one containing the numbers 1-10 and the other containing their squares. The long way to do this would be like so:

```
U=Aõ V=Um² [do something with the arrays]

```

Using automatic variable assignment, though, that can be shortened to:

```
Aõ
Um²
[do something with the arrays]

```

We've saved 4 bytes there. But, in this instance, we can save one more byte because the array of 1-10 is assigned to `U` and `U` can be omitted in certain scenarios:

```
Aõ
m²
[do something with the arrays]

```

## Caution

One thing to be careful of with this tip is that you don't overwrite any input variables you might need later on in your programme. This can be avoided by leaving one or more empty lines at the start of it. In the following example, the 2 arrays will be assigned to the variables `V` & `W`, instead of `U` & `V`:

```

Aõ
Vm²
[do something with the arrays]
```

# Answer
> 3 votes
# Know the Javascript

Since any Japt code runs as transpiled JS, good understanding of JS operators and built-in methods helps a lot in golfing pieces of Japt code.

### Relevant JS tips

```
[]Vm@...
...

```
* Short-circuiting
* Splitting with numbers
    + This can be generalized to any method that accepts strings but not numbers. A number passed there will implicitly cast to a string, often saving a byte (e.g. `0` over `'0`).

### Relevant JS built-in functions

Closely look at what parameters are passed to function arguments.

For string methods, it's good to know how the behaviors differ between passing a string or regex with or without `g` flag.

# Answer
> 3 votes
# Use multiple lines when necessary

For most not-too-hard challenges, you can express the solution in just one line of Japt, as a sequence of applying built-in functions. But more complex ones will require to use looping constructs, recursion, or reusing large chunks of code. This is where multi-line programming comes in.

## Remove closing parens

**Task**: Given an array of numbers, pair each element with the index squared, and sort it by the sum.

`[5,1,17,9,3] => [[5,0],[1,1],[17,4],[9,9],[3,16]] => [[1,1],[5,0],[9,9],[3,16],[17,4]]`

One-line solution is `íUm@Yp2})ñx`, but `})` costs two bytes (and there is no one-byte shortcut). You can remove `})` by simply moving the trailing `ñx` to the next line, so the code looks like this:

```
íUm@Yp2
ñx

```

and the transpiled JS becomes:

```
U = U.í(U.m(function(X, Y, Z) { return Y.p(2) })); U.ñ("x")

```

You can clearly see this does the same thing as the one-line solution, just assigning the intermediate result back to `U`.

## Recurse with implicit arguments

The recursion function `ß` takes all of `UVWXYZ` as implicit parameter, if not specified. `U` is obviously the main input, but you can use any of `VWXYZ` to keep track of other values you need. For example, you can do something like the following:

```
(modify input and implicit assign to U)
(modify V and implicit assign to V)
(test something and call ß without arguments; U and V are passed automatically)

```

Alternatively, if all you want is a temporary variable, you can use inline assignment, like `(T=...)`, as the variable `T` (0) is rarely used as-is.

## Reuse a long function

For this, I don't think I can come up with a good example task, so I'll reference the only solution this tip was used, and just outline some general ideas.

* In order to reuse a function, you need to store it in a variable. Starting a line with the function-opener `{`, `@` or `_` does the job. Alternatively, you can also do something like `(T=@...})` to embed the function assignment inside a more complex line.
* It's actually not trivial to call the stored function. Suppose `V` is a function and we want to call `V(U)` in JS. `VU` does not work since it simply means `V,U`. `V(U` doesn't either; it's `V,(U)`. Even the function methods aren't helpful very much. The best way we found is:
    + `[U]xV` (map and sum) if the result is number
    + `UmV` if `U` is a single char and `V` returns a string, or
    + `$V($U` or `[U]mV g` in general.
* However, mapping or looping with it is rather easy. To map over an array, use `UmV`. To find the first integer that satisfies `V`, use `Va`.

# Answer
> 2 votes
# Fun with Auto-Functions

As a follow-up to ETH's general tip on auto-functions, this tip will provide a few specific examples of byte saving tricks you can achieve with them, which I'll add to as I think of more.

---

## Get the largest integer in an array.

Assume we have the array `[3,1,4,2]` assigned to variable `U` and we ant to retrieve the largest number from it. We *could* do it in 4 bytes by sorting the array and then popping the last element:

```
Un o

```

The downside to that is that we've modified the original array; `U` is now `[1,2,3]` which may not always be desirable. Luckily, there's a way of doing it without modifying the array that's also one byte shorter:

```
Urw

```

What we've done there is reduced the array using the `w` method, which, when used on an integer returns the larger of the integer and the method's argument (e.g., `2w5` returns `5`). So the above is the equivalent of `UrÈwY` or `UrXY{XwY}`. Note, though, that this tip won't work in the case of *all* the integers in the array being negative.

# Answer
> 2 votes
## When *not* to use `í`

`í` is a useful built-in that pairs (or `zip`s) two arrays or strings, and optionally maps each pair through a function. However, it currently has a few minor issues when given uneven arrays or strings:

* If the first array has more items than the second, the non-existent items in the second will be given as `undefined`.
* If the second array has more items than the first, it will stop processing at the end of the first array.

This can make it difficult to, say, compare two uneven strings and take the char with the higher code point from each pair. Even if you know that `U` is going to be the longer one, it still takes far to many bytes to solve this simple task:

```
UíUç hV @[XY]n o

```

What you could do instead would be to take input as an array of two strings, *transpose* the array with `y`, and then map each row to the correct result:

```
Uy m_q n o

```

This has the advantage of always padding the shorter string with spaces, making it a piece of cake to go through the entirety of both strings.

Real-life examples: ,

# Answer
> 2 votes
# Generate the ASCII Range

> Update: Japt now has a constant for the ASCII range; the alternative value for `E`, accessible with `;`. See this tip for more on Japt's constants.

While Japt doesn't (yet) have a built-in for the ASCII range, you can generate an array of characters in just 5 bytes:

```
95odH

```

Try it

---

## How It Works

`95o` creates the range `[0,95)` with each element being passed through the auto-function `d` which, when used on a number, returns the character at that codepoint. Pass a number as an argument to the `d` method, in this case `H`, the Japt constant for 32, and it will be added to the original number before being converted.

An equivalent solution in JavaScript would be:

```
[...Array(95)].map((_,x)=>String.fromCharCode(x+32))

```

---

## Random Characters

To get a random character in the ASCII range, use `ö` instead, which returns a random number from the range `[0,X)`, where `X` is the number it is run on.

```
95ö dH

```

Or, to get an array of multiple random characters, pass the number of characters you need as an argument of `ö`. The following will return 10 characters:

```
95öA mdH

```

# Answer
> 1 votes
## Remove unnecessary structural chars

By structural chars, I mean `{}`, `()`, `$`, even `"` and ```. You can typically remove these chars whenever they occur right at the end of a program (e.g. `UmX{Xc +"; "} -> UmX{Xc +";` ).

Additionally, you can remove parens or spaces whenever they appear in the following places:

* Up against a semicolon `;` (or the end of the program);
* To the right of `{` (and by extension, `@`) or `[`, or the left of `]` or `}`.

Also, commas are very rarely needed to separate arguments. If you write `AB`, for example, Japt knows you mean `A` and `B` separately. You only really need a comma to separate two numerical literals, such as `Us2,5`.

Finally, if there's a `U` at the start of a program or after a `{` or `;`, followed by a method call (lowercase letter or related Unicode shortcut) or any binary operator excluding `+` and `-` (`*`, `&`, `==`, etc.), you can remove the `U` to save a byte and Japt will insert it for you.

# Answer
> 1 votes
# Modify the Last Element in An Array

Sometimes you may need to modify the last element in an array so here's an explanation of a short way of doing that. We'll be working with the array `[2,4,8,32]` assigned to input variable `U` and dividing the last integer (`32`) by 2.

The obvious way to achieve this would be with this 9 byte solution (Demo):

```
UhJUgJ /2

```
* `hnx` sets the element at index `n` to `x`.
* `gn` returns the the element at index `n`.
* `J` is the Japt constant for `-1`, which, thanks to Japt's support for negative index, allows us to work with the last element in an array; handy when you don't know the size of the array.
* And `/2` is simply division by 2.

So the above sets the element at index `-1` in the array to the element at index `-1` in the array divided by 2. Or in JavaScript: `U[3]=U[3]/2`. When you write it out like that, it seems a far too long-winded way of going about it. Luckily, there *is* a shorter way; we could pop the last element from the array, modify it and push it back to the array. Performing each of those operations individually would take more than 9 bytes but we can do them all at once for just 7 bytes, a 2 bytes saving (Demo)

```
UpUo /2

```

Translated to JS, it's the equivalent of:

```
U.push(U.pop()/2)&&U

```

---
Tags: code-golf, tips
---


title: Find the sum of closest distances

text:
# Question
Title: Find the sum of closest distances
For this task your code should take two sorted arrays of integers X and Y as input. It should compute the sum of the absolute distances between each integer in X and its closest number in Y.

Examples:

```
X = (1 5,9)
Y = (3,4,7)

```

The distance is 2 + 1 + 2.

```
X = (1,2,3)
Y = (0,8)

```

The distance is 1 + 2 + 3.

Your code can take input in any way that is convenient.

The main restriction is that **your code must run in linear time in the sum of the length of the two arrays.**. (You can assume that adding two integers takes constant time.)

# Answer
# Haskell, ~~70~~ 64 bytes

```
a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_<-d,a%c>a%e=x#d|1>0=a%c+b#y
_#_=0

```

Try it online!

## Explanation

First we define `(%)` to be the absolute difference between two numbers. Then we define `(#)` to be the interesting function. In the first line we match when both lists are non-empty:

```
x@(a:b)#(c:d:e)

```

On our first case from here we bind `d` to `e:_` with `e:_<-d`. This ensures that `d` is non-empty and sets it's first element to `e`.

Then if the second element of \\$Y\\$ (`e`) is closer than the first (`c`) to the first element of \\$X\\$ (`a`), we return `x#d` removing the first element of \\$Y\\$ and calling again with the same \\$X\\$.

If we match the pattern but don't pass the condition we do:

```
a%c+b#y

```

Which, removes the first item of \\$X\\$ and adds the absolute difference of it from the first element of \\$X\\$ to the remaining result.

Lastly if we don't match the pattern we return \\$0\\$. Not matching the pattern means that \\$X\\$ must be empty because \\$Y\\$ cannot be empty.

This algorithm has order notation \\$O(|X|+|Y|)\\$.

# Haskell, 34 bytes

Here's how I would do it in \\$O(\left|X\right|\times\left|Y\right|)\\$ time:

```
x#y=sum[minimum$abs.(z-)<$>y|z<-x]

```

Try it online!
> 6 votes

# Answer
# Python 2, ~~124~~ 120 bytes

```
X,Y=input()
i=j=s=0
while i<len(X):
 v=abs(Y[j]-X[i])
 if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1
 else:s+=v;i+=1
print s

```

Try it online!

Saved 4 bytes by moving to program versus function.

Meeting the time-complexity constraint is possible because both lists are sorted. Note that each time around the loop, either `i` is incremented or `j` is incremented. Thus the loop is executed at most `len(X)+len(Y)` times.
> 2 votes

# Answer
## C (gcc), 82 bytes

```
n;f(x,y,a,b)int*x,*y;{for(n=0;a;)--b&&*x*2-*y>y[1]?++y:(++b,--a,n+=abs(*x++-*y));}

```

This takes input as two integer arrays and their lengths (since C has no way to get their length otherwise). This can be shown to run in `O(a+b)` because either `a` or `b` is decremented on each iteration of the loop, which terminates when `a` reaches `0` (and `b` cannot be decremented below `0`).

Try it online!

```
n;                     // define sum as an integer
f(x,y,a,b)             // function taking two arrays and two lengths
int*x,*y;              // use k&r style definitions to shorten function declaration
{
 for(n=0;              // initialize sum to 0
 a;)                   // keep looping until x (the first array) runs out
                       // we'll decrement a/b every time we increment x/y respectively
 --b&&                 // if y has ≥1 elements left (b>1, but decrements in-place)...
 *x*2-*y>y[1]?         // ... and x - y > [next y] - x, but rearranged for brevity...
 ++y:                  // increment y (we already decremented b earlier);
 (++b,                 // otherwise, undo the in-place decrement of b from before...
 --a,n+=abs(*x++-*y))  // decrement a instead, add |x-y| to n, and then increment x
;}

```

Some notes:

* Instead of indexing into the arrays, incrementing the pointers and dereferencing directly saves enough bytes for it to be worth it (`*x` vs `x[a]` and `y[1]` vs `y[b+1]`).
* The `--b&&` condition checks for `b>1` in a roundabout way - if `b` is `1`, it will evaluate to zero. Since this modifies `b`, we don't need to change it in the first branch of the ternary (which advances `y`), but we do need to change it back in the second (which advances `x`).
* No `return` statement is needed, because black magic. (I *think* it's because the last statement to be evaluated will always be the `n+=...` expression, which uses the same register as the one used for return values.)
> 1 votes

# Answer
# Ruby, 88 bytes

```
->(p,q){a=q.each_cons(2).map{|a|a.sum/a.size}
x=a[0]
p.sum{|n|x=a.pop if n>x
(n-x).abs}}

```

Try it online!

Also, for fun, a shorter anonymous function that doesn't quite meet the complexity restrictions:

```
->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}

```
> 0 votes

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

```
x=>g=(y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?g(y,i+!t,j+t)+!t*(d>0?d:-d):0

```
* It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
    + `x`, `y` are passed by reference, which do not copy the content
* `1/v` is falsy if `x[i]` is out of range, truthy otherwise
* `t` -\> `d>y[j+1]-v` -\> `v+v>y[j]+y[j+1]` is false as long as following conditions meet. And which means `y[j]` is the number closest to `v` in `y`
    + `v` is less than `(y[j]+y[j+1])/2`, or
    + `y[j+1]` is out of range, which would convert to `NaN`, and compare to `NaN` yield `false`
        - that's why we cannot flip the `>` sign to save 1 more byte
* `t` is always a boolean value, and `*` convert it to `0`/`1` before calculating

Try it online!
> 0 votes

# Answer
# Mathematica, 40 bytes

```
x = {1, 5, 9};
y = {3, 4, 7};

Norm[Flatten[Nearest[y] /@ x] - x]

```

If you must create a full program, with inputs:

```
f[x_,y_]:= Norm[Flatten[Nearest[y] /@ x] - x]

```

Here's the timing for up to 1,000,000 points (sampled every 10,000) for `y`:

Close to linear.
> 0 votes

---
Tags: code-golf, restricted-complexity
---


title: Find the Fibonacci Patterns

text:
# Question
Title: Find the Fibonacci Patterns
You are probably familiar with the Fibonacci sequence where the first two terms are `0, 1` (or sometimes `1, 1`) and every term after that is the sum of the previous two. It starts like this:

`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...`

Sometimes, the sequence contains numbers that have a particular pattern that I find interesting: the difference between any pair of adjacent digits is the same as any other pair. For instance, in the sequence starting with `0, 1`, the 18th term is `987`. `9-8=1` and `8-7=1`. I am mildly satisfied.

**Challenge**

Given two initial values `F(0)` and `F(1)`, output every number in the sequence generated by `F(n) = F(n-1) + F(n-2)` that meets the following criteria:

* The difference between any pair of adjacent digits is the same as any other pair
* It is as least three digits long (1 and 2 digit numbers are not interesting for this pattern)

**Input**

* Two non-negative integers less than 10\**10 (10 billion)

**Output**

* All integers that are less than 10\**10 and meet the criteria in the Challenge section
* It is acceptable to output digits greater than 10\**10 but it is not a requirement
* Given that repeated digits meet the pattern (e.g. `777`), it is possible that there are infinite numbers that meet the criteria but your program is not required to output forever
* If no such integers exist, output whatever you want so long as it's not a number (nothing, null, empty array, error message, sad face, etc.)
* If a number matching the pattern appears more than once in the sequence, you can output it once or as many times as it occurs
* If any input meets the criteria, it should be included in the output

**Rules**

**Examples / Test Cases**

```
Input , Output
[1,10] , []

[0,1] , [987]
[2,1] , [123]
[2,3] , [987]

[61,86] , [147]
[75,90] , [420]
[34,74] , [1234]
[59,81] , [2468]
[84,85] , [7531]

[19,46] , [111]
[60,81] , [222]
[41,42] , [333]
[13,81] , [444]
[31,50] , [555]
[15,42] , [666]
[94,99] , [777]
[72,66] , [888]
[3189,826] , [888888888]

[15,3] , [159,258]
[22,51] , [321,1357]
[74,85] , [159,4444]
[27,31] , [147,11111]

[123,0] , [123,123,123,246,369]
[111,0] , [111,111,111,222,333,555,888]
[111,222] , [111,222,333,555,888]

[33345,692] , [987654321]
[3894621507,5981921703] , [9876543210]
[765432099,111111111] , [111111111,876543210,987654321]

[1976,123] , [123, 2222, 4321, 6543, 45678]

```

# Answer
> 10 votes
# MATL, 14 bytes

*Thanks to Emigna for pointing out a mistake, now corrected*

```
`yVdd~?yD]wy+T

```

Infinite loop that outputs the numbers as they are found.

**Try it online!** Note that in the online interpreter the results are displayed after the 1-minute time-out.

### Explanation

Let `F(n)` and `F(n+1)` denote two generic consecutive terms of the Fibonacci sequence. Each iteration of the loop starts with the stack containing `F(n)`, `F(n+1)` for some `n`.

```
`         % Do...while
  y       %   Duplicate from below. Takes the two inputs F(0), F(1) (implicitly)
          %   in the first iteration
          %   STACK: F(n), F(n+1), F(n)
  V       %   Convert to string. Let the digits of F(n) be '3579' for example
          %   STACK: F(n), F(n+1), '3579'
  d       %   Consecutive differences (of ASCII codes)
          %   STACK: F(n), F(n+1), [2 2 2]
  d       %   Consecutive differences
          %   STACK: F(n), F(n+1),  [0 0]
  ~       %   Logical negate, element-wise
          %   STACK: F(n), F(n+1), [1 1]
  ?       %   If top of the stack is non-empty and only contains non-zero entries
          %   (this is the case for digits '3579', but not for '3578' or '33')
          %   STACK: F(n), F(n+1)
    y     %     Duplicate from below
          %     STACK: F(n), F(n+1), F(n)
    D     %     Display immediately. This prints the copy of F(n)
          %     STACK: F(n), F(n+1)
  ]       %   End
  w       %   Swap
          %   STACK: F(n+1), F(n)
  y       %   Duplicate from below
          %   STACK: F(n+1), F(n), F(n+1)
  +       %   Add. Note that F(n)+F(n+1) is F(n+2)
          %   STACK: F(n+1), F(n+2)
  T       %   Push true. This will be used as loop condition
          %   STACK: F(n+1), F(n+2), true
          % End (implicit). The top of the stack is consumed as loop condition.
          % Since it is true, a new iteration will begin, with the stack
          % containing F(n+1), F(n+2)

```

# Answer
> 6 votes
# 05AB1E, ~~17~~ ~~16~~ 15 bytes

```
тFÂ2£O¸«}ʒS¥¥_W

```

Try it online!

**Explanation**

```
                  # implicitly input list of F(0) and F(1)
тF      }         # 100 times do:
  Â               # bifurcate current list
   2£             # take the first 2 items
     O            # sum
      ¸«          # append to list
         ʒ        # filter, keep only elements that are true after:
          S¥¥     # delta's of delta's of digits
             _    # logically negate each
              W   # min

```

# Answer
> 5 votes
# JavaScript (ES6), ~~85~~ ~~84~~ 81 bytes

```
f=(p,q,a=[])=>p|q?f(q,p+q,![...p+''].some(x=d=n=>r=d-(d=x-(x=n)))/r?[...a,p]:a):a

```

Try it online!

### Testing adjacent digits

```
![...p + ''].some(x = d = n => r = d - (d = x - (x = n))) / r

```

Both **x** and **d** are initialized to an anonymous function, which forces `NaN` for all arithmetic operations they're involved in. The first iteration of `some()` always gives `(d = [function] - n) === NaN` and `(r = [function] - d) === NaN` (falsy). On the second iteration, we have `d = x - n` (an integer) and `(r = NaN - d) === NaN` (falsy again). Starting from the third iteration, **r** is set to an integer which is non-zero if the difference between digit #3 and digit #2 is not equal to the difference between digit #2 and digit #1.

The number **p** is meeting the required criteria if and only if `some()` is falsy (all adjacent digits have the same difference) and the final value of **r** is **0** (there were at least 3 iterations). This gives `!false / 0 === true / 0 === Infinity` (truthy).

We may otherwise have:

* `!true / r` with **r \> 0** or **r \< 0**, which gives `false / r === 0` (falsy)
* `!false / NaN`, which gives `true / NaN === NaN` (falsy)

### Halting condition

The recursion stops when `p | q` evaluates to **0**. This is guaranteed to happen when both **p** and **q** reach values around **1025** which are 84-bit long. Because JS has 52 bits of mantissa, the last 32 bits are zeroed. So, the 32-bit bitwise OR evaluates to **0**.

Due to the fast growing rate of the sequence, this happens rather quickly.

# Answer
> 4 votes
# Octave, ~~91~~ ~~90~~ 83 bytes

Saved 7 bytes thanks to Luis Mendo!

```
@(t)eval"for i=3:99,if~diff(diff(+num2str(t(1))))disp(t(1))end,t=[t(2) sum(t)];end"

```

Try it online!

Well, it works!

`eval` with for loop inside to save a few bytes. Skipping colons and semicolons to save a few. Uses the fact that a vector is considered truthy iff all elements are non-zero to save `any` or `all`.

Other than that, it's pretty much a straight forward implementation of Fibonacci.

# Answer
> 4 votes
# Jelly,  ~~20 19~~ 18 bytes

```
>ȷ2ȧDIEƊ
+ƝḢ;Ɗȷ¡ÇƇ

```

Try it online!

`+ƝḢ;Ɗȷ¡` produces the first thousand (`ȷ`) terms in the series which will always be sufficient. I think there is probably a shorter way to do this. `+ȷ¡` gets close but only works if the first term is zero.

I am assuming we can take in the two numbers in reverse which allows one byte to `DIE`.

If we aren't required to output either of the inputs:

### Jelly, 15 bytes

```
>ȷ2ȧDIEƊ
+ṄÇ¡ß@

```

Try it online!

# Answer
> 4 votes
# Java 8, ~~151~~ ~~144~~ ~~140~~ ~~136~~ 130 bytes

```
(a,b)->{for(long n,m,d,p;;System.out.print(m>99&p==d?m+" ":""),m=a+b,a=b,b=m)for(m=n=a,d=p=10;n>9&d==p|p>9;d=n%10-(n/=10)%10)p=d;}

```

Infinite loop outputting the numbers when it finds them.
Try it online (times out after 60 sec).

**136 bytes** version with added 1010 limit (`a<1e10`):

```
(a,b)->{for(long n,m,d,p;a<1e10;System.out.print(m>99&p==d?m+" ":""),m=a+b,a=b,b=m)for(m=n=a,d=p=10;n>9&d==p|p>9;d=n%10-(n/=10)%10)p=d;}

```

Try it online.

**Explanation:**

```
(a,b)->{         // Method with two long parameters and no return-type
  for(long n,m,  //  Temp numbers
           d,p;  //  Current and previous differences
      a<1e10;    //  Loop as long as `a` is still below 10^10
      ;          //    After every iteration:
       System.out.print(
                 //     Print:
        m>99     //      If the number has at least three digits,
        &p==d?   //      and the previous and current differences are still the same
         m+" "   //       Print the current number with a space delimiter
        :        //      Else:
         ""),    //       Print nothing
                 //     Go to the next Fibonacci iteration by:
       m=a+b,    //      Setting the temp-number `m` to `a+b`
       a=b,      //      Replacing `a` with `b`
       b=m)      //      And then setting `b` to the temp number `m`
    for(m=n=a,   //   Set both `m` and `n` to `a`
        d=p=10;  //   Set both `d` and `p` to 10
        n>9      //   Inner loop as long as `n` has at least two digits,
        &d==p    //   and `p` and `d` are still the same,
         |p>9    //   or `p` is still 10
        ;        //     After every iteration:
         d=n%10-(n/=10)%10)
                 //      Set `d` to the difference between the last two digits of `n`
                 //      And integer-divide `n` by 10 at the same time
      p=d;}      //    Set the previous difference `p` to `d`

```

# Answer
> 2 votes
# Python 2, ~~102~~ 98 bytes

```
f=lambda x,y:x<1e10and[x]*(len(set(int(a)-int(b)for a,b in zip(`x`,`x`[1:])))<2<99<x)+f(y,x+y)or[]

```

Try it online!

Thx for 4 bytes from ovs

# Answer
> 2 votes
# CJam, 55 bytes

```
q~{1$_99>"_`2\ew{{-}*}%""3,"?~_(+="0$p"*~;_@+_11_#<}g;;

```

Try it online!

My first CJam submission, not very short but a lot of fun. Any suggestions are welcome!

# Answer
> 2 votes
# Haskell, 105 bytes

```
u%v|let s=u:scanl(+)v s=[n|n<-s,d<-[f(-).map fromEnum.show$n],length d>1,and$f(==)d]
f g=zipWith g=<<tail

```

Defines the operator `(%)` which returns an infinite list with all the solutions. To actually see the result on *stdout* we need to disable buffering (or run it in `ghci` or with `runhaskell`), try it online!

### Explanation/Ungolfed

The function `f` is just a helper function that expects a binary function and a list, it applies the function `g` to all adjacent pairs. It's essentially the same as:

```
adjacent g xs = zipWith (tail xs) xs

```

The operator `(%)` is just a list comprehension that does some filtering (making sure that there are at least 3 digits & that the adjacent digits have the same distance):

```
u % v
  -- recursively define s as the "Fibonacci sequence" with f(0) = u and f(1) = v
  | let sequence = u : scanl (+) v sequence
  -- take all numbers from that sequence using the filters below
  = [ number | number <- sequence
  -- convert to string, get the ASCII codepoints and build a list of the adjacent differences
        , let differences = adjacent (-) . map fromEnum . show $ number
  -- numbers with > 3 digits have >= 2 adjacent digits (or rather differences of digits)
        , length differences > 1
  -- make sure all of these are equal by comparing them and reducing with logical and
        , and $ adjacent (==) differences
    ]

```

# Answer
> 2 votes
# Stax, ~~26~~ 24 bytes

```
Ç╕SôεPN^:·░ßⁿ {@ÿ}Ü╫╣1╣X

```

Run and debug it

**Explanation**

```
E{b+}99*L{E%2>|cd_E:-u%1=!C_Qf    # Full program, unpacked, implicit input
E                                 # Push all elements from array onto stack.
 {b+}99*L                         # Generate the first 99 numbers of the  Fibonacci sequence given the input
         {                   f    # Loop through all Fibonacci elements
          E                       # Array of decimal digit
           %2>                    # Does the array have at least 3 digits
              |c                  # Assume Truthy past this point
                d                 # discard top of stack
                 _E               # Copy the current element of the Fibonacci sequence and Digitize it
                  :-              # Pairwise difference of array.
                    :u            # Is there exactly 1 unique number
                        !C        # Flip the comparison, if truthy proceed
                          _Q      # Copy the current element of the Fibonacci sequence and Peek and print with a newline.

```

Not as short as I would like it and can probably be golfed a bit more, but it works.

# Answer
> 1 votes
# Ruby, 79 bytes

```
->a,b{loop{a>99&&!(a.digits.each_cons(2).map{|a,b|a-b}|[])[1]&&p(a);a,b=b,a+b}}

```

Try it online!

# Answer
> 1 votes
# Julia 0.6, ~~86~~ 81 bytes

```
a<b=b>=0&&((n->n>99&&2>endof(∪(diff(digits(n))))&&println(n)).([a,b]);a+b<a+2b)

```

Try it online!

Pretty straightforward - check if input has at least 3 digits (`n>99`), then take the difference between each digit pair in the number (`diff(digits(n))`), check that the length of (`endof`) a unique set of () those differences is 1 (i.e. all the differences are the same), and if so print the number. Do that for both the given numbers, then recursively call the function with the next two numbers.

~~(Unfortunately, it looks like `±` has higher precedence than `+`, or else the final call could have been `a+b±a+2b`, saving 3 bytes.)~~ Now overloads the `<` operator, thus saving on both the operator bytes and the precedence brackets. (Can't use `<` in our code though, so just rearranged `endof(...)<2` to `2>endof(...)`).

If some extraneous output is allowed, we can save 2 bytes using `@show` instead of `println`, printing `n = 987` instead of just `987`. We could even use `dump` for 1 byte lower than that, but `dump` prints the type information along with the value, so output will be `Int64 987` instead of just `987`.

---
Tags: code-golf, fibonacci
---


# Question
Title: Schläfli Convex Regular Polytope Interpreter
**Background**

The Schläfli Symbol is a notation of the form {p,q,r,...} that defines regular polytopes and tessellations.

The Schläfli symbol is a recursive description, starting with a p-sided regular polygon as {p}. For example, {3} is an equilateral triangle, {4} is a square and so on.

A regular polyhedron that has q regular p-sided polygon faces around each vertex is represented by {p,q}. For example, the cube has 3 squares around each vertex and is represented by {4,3}.

A regular 4-dimensional polytope, with r {p,q} regular polyhedral cells around each edge is represented by {p,q,r}. For example a tesseract, {4,3,3}, has 3 cubes, {4,3}, around an edge.

In general a regular polytope {p,q,r,...,y,z} has z {p,q,r,...,y} facets around every peak, where a peak is a vertex in a polyhedron, an edge in a 4-polytope, a face in a 5-polytope, a cell in a 6-polytope, and an (n-3)-face in an n-polytope.

A regular polytope has a regular vertex figure. The vertex figure of a regular polytope {p,q,r,...y,z} is {q,r,...y,z}.

Regular polytopes can have star polygon elements, like the pentagram, with symbol {5/2}, represented by the vertices of a pentagon but connected alternately.

The Schläfli symbol can represent a finite convex polyhedron, an infinite tessellation of Euclidean space, or an infinite tessellation of hyperbolic space, depending on the angle defect of the construction. A positive angle defect allows the vertex figure to fold into a higher dimension and loops back into itself as a polytope. A zero angle defect tessellates space of the same dimension as the facets. A negative angle defect cannot exist in ordinary space, but can be constructed in hyperbolic space.

**Competition**

Your goal is to create a program which when passed a Schläfli Symbol will return a complete description of a convex polytope. This is only a subset of the Schläfli Symbols, but it is the simplest one, I believe even without the other possibilities this will be a very difficult task, and polytopes are the starting point for tessellations. The rules of this question were designed with the idea of this result being an API, and I have not been able to locate any such program on the internet.

Your program must accomplish all of the following.

* The program must be able to generate any finite dimensional regular convex polytope. In 2 dimensions this includes n-gons. In 3 dimensions these are the platonic solids, in 4 dimensions this includes the tesseract, the orthoplex and a few others)
* The program must either (a) place a point on the origin, or (b) ensure that the average of all points is the origin. Orientation does not matter. Overall size does not matter.
* The program must provide a **complete** description meaning that for a 4-dimensional object, the program will return/print the vertices, edges, faces, and polyhedra. The order these are reported does not matter. For polyhedra, this is the information you would need in order to render the object.

You do *not* need to handle:

* Tesselations
* Hyperbolic Geometry
* Fractional Schläfli symbols (non-convex)
* Embedded Schläfli Symbols (non-uniform tilings)

If asked to do any of these things you can return an error.

Example: Cube

Input:

```
4 3

```

Output:

```
Vertices
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Edges (These are the vertex pairs that make up the edges)
0 1
0 2
0 4
1 3
1 5
2 3
2 6
3 7
4 5
4 6
5 7
6 7

Faces (These are the squares which are the faces of the cube)
0 1 3 2
0 1 5 4
0 2 6 4
6 7 5 4
7 6 2 3
7 5 1 3

```

I had some ideas for how this algorithm could work and be very recursive, but thus far I've failed, but if you are looking for inspiration check out: https://en.wikipedia.org/wiki/Euler\_characteristic

As an example of working out the number of vertices, edges and faces, Consider the cube which is {4,3}. If we look at the initial 4, then it has 4 edges and 4 vertices. Now if we look at the next 3, we know that 3 edges meet at each vertex, each edge connects to 2 vertices, 2 faces meet at each edge, each face connects to 4 edges(because of the square sides), and we have the Euler Characteristic formula.

E = 3/2 V

E = 4/2 F

V - E + F = 2

Which gives E=12, V=8, F=6.

# Scoring

In order to keep the question on topic, this has been revised to Code Golf. Shortest code wins.

A github has been created for this question

# Answer
> 2 votes
# Python

Here's a recursive program without any special cases. Ignoring blank lines and comments, it's less than ~~100~~ 90 lines, including a gratuitous check of Euler's formula at the end. Excluding the definitions of ad-hoc math functions (which could probably be provided by a library) and i/o, the polytope generation is 50 lines of code. And it even does the star polytopes!

The output polytope will have edge length 1 and will be in canonical position and orientation, in the following sense:

* the first vertex is the origin,
* the first edge lies along the +x axis,
* the first face is in the +y half-plane of the xy plane,
* the first 3-cell is in the +z half-space of the xyz space, etc.

Other than that, the output lists are in no particular order. (Well, actually, that's not *entirely* true-- they'll actually come out roughly in order starting from the first element and expanding outwards.)

There's no checking for invalid schlafli symbol; if you give it one, the program will probably go off the rails (endless loop, stack overflow, or just garbage out).

If you ask for an infinite planar tiling such as {4,4} or {3,6} or {6,3}, the program will actually start generating the tiling, but it will go forever until it runs out of space, never finishing nor producing output. This would not be too hard to fix (just put a limit on the number of elements to generate; the result should be a fairly coherent region of the infinite picture, since elements are generated in roughly breadth-first-search order).

## The code

```
#!/usr/bin/python3
# (works with python2 or python3)

#
# schlafli_interpreter.py
# Author: Don Hatch
# For: https://codegolf.stackexchange.com/questions/114280/schl%C3%A4fli-convex-regular-polytope-interpreter
#
# Print the vertex coords and per-element (edges, faces, etc.) vertex index
# lists of a regular polytope, given by its schlafli symbol {p,q,r,...}.
# The output polytope will have edge length 1 and will be in canonical position
# and orientation, in the following sense:
#  - the first vertex is the origin,
#  - the first edge lies along the +x axis,
#  - the first face is in the +y half-plane of the xy plane,
#  - the first 3-cell is in the +z half-space of the xyz space, etc.
# Other than that, the output lists are in no particular order.
#

import sys
from math import *

# vector minus vector.
def vmv(a,b): return [x-y for x,y in zip(a,b)]
# matrix minus matrix.
def mmm(m0,m1): return [vmv(row0,row1) for row0,row1 in zip(m0,m1)]
# scalar times vector.
def sxv(s,v): return [s*x for x in v]
# scalar times matrix.
def sxm(s,m): return [sxv(s,row) for row in m]
# vector dot product.
def dot(a,b): return sum(x*y for x,y in zip(a,b))
# matrix outer product of two vectors; that is, if a,b are column vectors: a*b^T
def outer(a,b): return [sxv(x,b) for x in a]
# vector length squared.
def length2(v): return dot(v,v)
# distance between two vectors, squared.
def dist2(a,b): return length2(vmv(a,b))
# matrix times vector, homogeneous (i.e. input vector ends with an implicit 1).
def mxvhomo(m,v): return [dot(row,v+[1]) for row in m]
# Pad a square matrix (rotation/reflection) with an extra column of 0's on the
# right (translation).
def makehomo(m): return [row+[0] for row in m]
# Expand dimensionality of homogeneous transform matrix by 1.
def expandhomo(m): return ([row[:-1]+[0,row[-1]] for row in m]
                         + [[0]*len(m)+[1,0]])
# identity matrix
def identity(dim): return [[(1 if i==j else 0) for j in range(dim)]
                                               for i in range(dim)]
# https://en.wikipedia.org/wiki/Householder_transformation. v must be unit.
# Not homogeneous (makehomo the result if you want that).
def householderReflection(v): return mmm(identity(len(v)), sxm(2, outer(v,v)))

def sinAndCosHalfDihedralAngle(schlafli):
  # note, cos(pi/q)**2 generally has a nicer expression with no trig and often
  # no radicals, see http://www.maths.manchester.ac.uk/~cds/articles/trig.pdf
  ss = 0
  for q in schlafli: ss = cos(pi/q)**2 / (1 - ss)
  if abs(1-ss) < 1e-9: ss = 1  # prevent glitch in planar tiling cases
  return sqrt(ss), sqrt(1 - ss)

# Calculate a set of generators of the symmetry group of a {p,q,r,...} with
# edge length 1.
# Each generator is a dim x (dim+1) matrix where the square part is the initial
# orthogonal rotation/reflection and the final column is the final translation.
def calcSymmetryGenerators(schlafli):
  dim = len(schlafli) + 1
  if dim == 1: return [[[-1,1]]]  # one generator: reflect about x=.5
  facetGenerators = calcSymmetryGenerators(schlafli[:-1])
  # Start with facet generators, expanding each homogeneous matrix to full
  # dimensionality (i.e. from its previous size dim-1 x dim to dim x dim+1).
  generators = [expandhomo(gen) for gen in facetGenerators]
  # Final generator will reflect the first facet across the hyperplane
  # spanned by the first ridge and the entire polytope's center,
  # taking the first facet to a second facet also containing that ridge.
  # v = unit vector normal to that bisecting hyperplane
  #   = [0,...,0,-sin(dihedralAngle/2),cos(dihedralAngle/2)]
  s,c = sinAndCosHalfDihedralAngle(schlafli)
  v = [0]*(dim-2) + [-s,c]
  generators.append(makehomo(householderReflection(v)))
  return generators

# Key for comparing coords with roundoff error.  Makes sure the formatted
# numbers are not very close to 0, to avoid them coming out as "-0" or "1e-16".
# This isn't reliable in general, but it suffices for this application
# (except for very large {p}, no doubt).
def vert2key(vert): return ' '.join(['%.9g'%(x+.123) for x in vert])

# Returns a pair verts,edgesEtc where edgesEtc is [edges,faces,...]
def regular_polytope(schlafli):
  dim = len(schlafli) + 1
  if dim == 1: return [[0],[1]],[]

  gens = calcSymmetryGenerators(schlafli)

  facetVerts,facetEdgesEtc = regular_polytope(schlafli[:-1])

  # First get all the verts, and make a multiplication table.
  # Start with the verts of the first facet (padded to full dimensionality),
  # so indices will match up.
  verts = [facetVert+[0] for facetVert in facetVerts]
  vert2index = dict([[vert2key(vert),i] for i,vert in enumerate(verts)])
  multiplicationTable = []
  iVert = 0
  while iVert < len(verts):  # while verts is growing
    multiplicationTable.append([None] * len(gens))
    for iGen in range(len(gens)):
      newVert = mxvhomo(gens[iGen], verts[iVert])
      newVertKey = vert2key(newVert)
      if newVertKey not in vert2index:
        vert2index[newVertKey] = len(verts)
        verts.append(newVert)
      multiplicationTable[iVert][iGen] = vert2index[newVertKey]
    iVert += 1

  # The higher-level elements of each dimension are found by transforming
  # the facet's elements of that dimension.  Start by augmenting facetEdgesEtc
  # by adding one more list representing the entire facet.
  facetEdgesEtc.append([tuple(range(len(facetVerts)))])
  edgesEtc = []
  for facetElementsOfSomeDimension in facetEdgesEtc:
    elts = facetElementsOfSomeDimension[:]
    elt2index = dict([[elt,i] for i,elt in enumerate(elts)])
    iElt = 0
    while iElt < len(elts):  # while elts is growing
      for iGen in range(len(gens)):
        newElt = tuple(sorted([multiplicationTable[iVert][iGen]
                               for iVert in elts[iElt]]))
        if newElt not in elt2index:
          elt2index[newElt] = len(elts)
          elts.append(newElt)
      iElt += 1
    edgesEtc.append(elts)

  return verts,edgesEtc

# So input numbers can be like any of "8", "2.5", "7/3"
def parseNumberOrFraction(s):
  tokens = s.split('/')
  return float(tokens[0])/float(tokens[1]) if len(tokens)==2 else float(s)

if __name__ == '__main__':
  if sys.stdin.isatty():
    sys.stderr.write("Enter schlafli symbol (space-separated numbers or fractions): ")
    sys.stderr.flush()
  schlafli = [parseNumberOrFraction(token) for token in sys.stdin.readline().split()]
  verts,edgesEtc = regular_polytope(schlafli)

  # Hacky polishing of any integers or half-integers give or take rounding error.
  def fudge(x): return round(2*x)/2 if abs(2*x-round(2*x))<1e-9 else x

  print(repr(len(verts))+' Vertices:')
  for v in verts: print(' '.join([repr(fudge(x)) for x in v]))
  for eltDim in range(1,len(edgesEtc)+1):
    print("")
    elts = edgesEtc[eltDim-1]
    print(repr(len(elts))+' '+('Edges' if eltDim==1
                          else 'Faces' if eltDim==2
                          else repr(eltDim)+'-cells')+" ("+repr(len(elts[0]))+" vertices each):")
    for elt in elts: print(' '.join([repr(i) for i in elt]))

  # Assert the generalization of Euler's formula: N0-N1+N2-... = 1+(-1)**(dim-1).
  N = [len(elts) for elts in [verts]+edgesEtc]
  eulerCharacteristic = sum((-1)**i * N[i] for i in range(len(N)))
  print("Euler characteristic: "+repr(eulerCharacteristic))
  if 2.5 not in schlafli: assert eulerCharacteristic == 1 + (-1)**len(schlafli)

```

## Trying it out on some cases

Input (cube):

```
4 3

```

Output:

```
8 Vertices:
0.0 0.0 0.0
1.0 0.0 0.0
0.0 1.0 0.0
1.0 1.0 0.0
0.0 0.0 1.0
1.0 0.0 1.0
0.0 1.0 1.0
1.0 1.0 1.0

12 Edges (2 vertices each):
0 1
0 2
1 3
2 3
0 4
1 5
4 5
2 6
4 6
3 7
5 7
6 7

6 Faces (4 vertices each):
0 1 2 3
0 1 4 5
0 2 4 6
1 3 5 7
2 3 6 7
4 5 6 7

```

Input from a unix command shell (120-cell polychoron):

```
$ echo "5 3 3" | ./schlafli_interpreter.py | grep ":"

```

Output:

```
600 Vertices:
1200 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):

```

Input (10-dimensional cross polytope):

```
$ echo "3 3 3 3 3 3 3 3 4" | ./schlafli_interpreter.py | grep ":"

```

Output:

```
20 Vertices:
180 Edges (2 vertices each):
960 Faces (3 vertices each):
3360 3-cells (4 vertices each):
8064 4-cells (5 vertices each):
13440 5-cells (6 vertices each):
15360 6-cells (7 vertices each):
11520 7-cells (8 vertices each):
5120 8-cells (9 vertices each):
1024 9-cells (10 vertices each):

```

Input (15-dimensional simplex):

```
$ echo "3 3 3 3 3 3 3 3 3 3 3 3 3 3" | ./schlafli_interpreter.py | grep ":"

16 Vertices:
120 Edges (2 vertices each):
560 Faces (3 vertices each):
1820 3-cells (4 vertices each):
4368 4-cells (5 vertices each):
8008 5-cells (6 vertices each):
11440 6-cells (7 vertices each):
12870 7-cells (8 vertices each):
11440 8-cells (9 vertices each):
8008 9-cells (10 vertices each):
4368 10-cells (11 vertices each):
1820 11-cells (12 vertices each):
560 12-cells (13 vertices each):
120 13-cells (14 vertices each):
16 14-cells (15 vertices each):

```

## Star polytopes

Ha, and it just naturally does star polytopes too! I didn't even need to try :-) Except that the bit about Euler's formula at the end fails, since that formula isn't valid for star polytopes.

Input (small stellated dodecahedron):

```
5/2 5

```

Output:

```
12 Vertices:
0.0 0.0 0.0
1.0 0.0 0.0
0.8090169943749473 0.5877852522924732 0.0
0.19098300562505266 0.5877852522924732 0.0
0.5 -0.36327126400268034 0.0
0.8090169943749473 -0.2628655560595667 0.5257311121191336
0.19098300562505266 -0.2628655560595667 0.5257311121191336
0.5 0.162459848116453 -0.3249196962329062
0.5 0.6881909602355867 0.5257311121191336
0.0 0.32491969623290623 0.5257311121191336
0.5 0.1624598481164533 0.8506508083520398
1.0 0.32491969623290623 0.5257311121191336

30 Edges (2 vertices each):
0 1
0 2
1 3
2 4
3 4
0 5
1 6
5 7
6 7
0 8
2 9
7 8
7 9
1 8
0 10
3 11
5 9
4 10
7 11
4 9
2 5
1 10
4 11
6 11
6 8
3 10
3 6
2 10
9 11
5 8

12 Faces (5 vertices each):
0 1 2 3 4
0 1 5 6 7
0 2 7 8 9
1 3 7 8 11
0 4 5 9 10
2 4 5 7 11
1 4 6 10 11
0 3 6 8 10
3 4 6 7 9
2 3 9 10 11
1 2 5 8 10
5 6 8 9 11
Traceback (most recent call last):
  File "./schlafli_interpreter.py", line 185, in <module>
    assert sum((-1)**i * N[i] for i in range(len(N))) == 1 + (-1)**len(schlafli)
AssertionError

```

Input (great stellated 120-cell):

```
$ echo "5/2 3 5" | ./schlafli_interpreter.py | grep ":"

```

Output:

```
120 Vertices:
720 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):

```

# Answer
> 14 votes
# Ruby

**Background**

There are three families of regular polytope extending into infinite dimensions:

* the simplexes, of which the tetrahedron is a member (I will often refer to them here as hypertetrahedra, though the term simplex is more correct.) Their schlafi symbols are of the form `{3,3,...,3,3}`
* the n-cubes, of which the cube is a member. Their schlafi symbols are of the form `{4,3,...,3,3}`
* the orthoplexes, of which the octahedron is a member (I will often refer to them here as hyperoctahedra) Their schlafi symbols are of the form `{3,3,...,3,4}`

There is one further infinite family of regular polytopes, symbol `{m}`, that of the 2 dimensional polygons, which may have any number of edges m.

In addition to this, there are just five other special cases of regular polytope: the 3-dimensional icosahedron `{3,5}` and dodecahedron `{5,3}`; their 4-dimensional analogues the 600-cell `{3,3,5}` and 120-cell `{5,3,3}`; and one other 4 dimensional polytope, the 24-cell `{3,4,3}` (whose closest analogues in 3 dimensions are the cuboctahedron and its dual the rhombic dodecahedron.)

# Main function

Below is the main `polytope` function that interprets the schlafi symbol. It expects an array of numbers, and returns an array containing a bunch of arrays as follows:

* An array of all vertices, each expressed as an n-element array of coordinates (where n is the number of dimensions)
* An array of all edges, each expressed as a 2-element of vertex indices
* An array of all faces, each expressed as an m-element of vertex indices (where m is the number of vertices per face)

and so on as appropriate for the number of dimensions.

It calculates 2d polytopes itself, calls functions for the 3 infinite dimensional families, and uses lookup tables for the five special cases. It expects to find the functions and tables declared above it.

```
include Math

#code in subsequent sections of this answer should be inserted here

polytope=->schl{
  if schl.size==1                                #if a single digit calculate and return a polygon
    return [(1..schl[0]).map{|i|[sin(PI*2*i/schl[0]),cos(PI*2*i/schl[0])]},(1..schl[0]).map{|i|[i%schl[0],(i+1)%schl[0]]}]
  elsif  i=[[3,5],[5,3]].index(schl)             #if a 3d special, lookup from tables
    return [[vv,ee,ff],[uu,aa,bb]][i]
  elsif i=[[3,3,5],[5,3,3],[3,4,3]].index(schl)  #if a 4d special. lookup fromm tables
    return [[v,e,f,g],[u,x,y,z],[o,p,q,r]][i]
  elsif schl.size==schl.count(3)                 #if all threes, call tetr for a hypertetrahedron
    return tetr[schl.size+1]
  elsif schl.size-1==schl.count(3)               #if all except one number 3
    return cube[schl.size+1] if schl[0]==4       #and the 1st digit is 4, call cube for a hypercube
    return octa[schl.size+1] if schl[-1]==4      #and the last digit is 4, call octa for a hyperoctahedron
  end
  return "error"                                 #in any other case return an error
}

```

# Functions for the tetrahedron, cube and octahedron families

https://en.wikipedia.org/wiki/Simplex

https://en.wikipedia.org/wiki/5-cell (4d simplex)

http://mathworld.wolfram.com/Simplex.html

**Tetrahedron family explanation - coordinates**

an n-dimensional simplex/hypertetrahedron has n+1 points. It is very easy to give the vertices of the n-dimensional simplex in n+1 dimensions.

Thus `(1,0,0),(0,1,0),(0,0,1)` describes a 2d triangle embedded in 3 dimensions and `(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)` describes a 3d tetrahedron embedded in 4 dimensions. This is easily verified by confirming that all distances between vertices are sqrt(2).

Various complicated algorithms are given on the internet for finding the vertices for the n-dimensional simplex in n-dimensional space. I found a remarkably simple one in Will Jagy's comments on this answer https://mathoverflow.net/a/38725 . The last point lies on the line `p=q=...=x=y=z` at a distance of sqrt(2) from the others. Thus the triangle above can be converted to a tetrahedron by addition of a point at either `(-1/3,-1/3,-1/3)` or `(1,1,1)`. These 2 possible values of the coordinates for the last point are given by `(1-(1+n)**0.5)/n` and `(1+(1+n)**0.5)/n`

As the question says the size of the n-tope does not matter, I prefer to multiply through by n and use the coordinates `(n,0,0..0)` up to `(0..0,0,n)` with the final point at `(t,t,..,t,t)` where t = `1-(1+n)**0.5` for simplicity.

As the centre of this tetrahedron is not at the origin, a correction to all coordinates must be done by the line `s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)}` which finds how far the centre is from the origin and subtracts it. I have kept this as a separate operation. However I have used `s[i]+=n` where `s[i]=n` would do, to allude to the fact that when the array is initialised by `s=[0]*n` we could put the correct offset in here instead and do the centring correction at the outset rather than the end.

**Tetrahedron family explanation - graph topology**

The graph of the simplex is the complete graph: every vertex is connected exactly once to every other vertex. If we have an n simplex, we can remove any vertex to give an n-1 simplex, down to the point where we have a triangle or even an edge.

Therefore we have a total of 2\**(n+1) items to catalogue, each represented by a binary number. This ranges from all `0`s for nothingness, through one `1` for a vertex and two `1`s for an edge, up to all `1`s for the complete polytope.

We set up an array of empty arrays to store the elements of each size. Then we loop from zero to (2\**n+1) to generate each of the possible subsets of vertices, and store them in the array according to the size of each subset.

We are not interested in anything smaller than an edge (a vertex or a zero) nor in the complete polytope (as the complete cube is not given in the example in the question), so we return `tg[2..n]` to remove these unwanted elements. Before returning, we tack \[tv\] containing the vertex coordinates onto the beginning.

**code**

```
tetr=->n{

  #Tetrahedron Family Vertices
  tv=(0..n).map{|i|
    s=[0]*n
    if i==n
      s.map!{(1-(1+n)**0.5)}
    else
      s[i]+=n
    end
    s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)}
  s}

  #Tetrahedron Family Graph
  tg=(0..n+1).map{[]}
  (2**(n+1)).times{|i|
    s=[]
    (n+1).times{|j|s<<j if i>>j&1==1}
    tg[s.size]<<s
  }

return [tv]+tg[2..n]}

cube=->n{

  #Cube Family Vertices
  cv=(0..2**n-1).map{|i|s=[];n.times{|j|s<<(i>>j&1)*2-1};s}

  #Cube Family Graph
  cg=(0..n+1).map{[]}
  (3**n).times{|i|                         #for each point
    s=[]
    cv.size.times{|j|                      #and each vertex
      t=true                               #assume vertex goes with point
      n.times{|k|                          #and each pair of opposite sides
        t&&= (i/(3**k)%3-1)*cv[j][k]!=-1   #if the vertex has kingsmove distance >1 from point it does not belong
      }
      s<<j if t                            #add the vertex if it belongs
    }
    cg[log2(s.size)+1]<<s if s.size > 0
  }

return [cv]+cg[2..n]}

octa=->n{

  #Octahedron Family Vertices
  ov=(0..n*2-1).map{|i|s=[0]*n;s[i/2]=(-1)**i;s}

  #Octahedron Family Graph
  og=(0..n).map{[]}
  (3**n).times{|i|                         #for each point
    s=[]
    ov.size.times{|j|                      #and each vertex
      n.times{|k|                          #and each pair of opposite sides
        s<<j if (i/(3**k)%3-1)*ov[j][k]==1 #if the vertex is located in the side corresponding to the point, add the vertex to the list
      }
    }
    og[s.size]<<s
  }

return [ov]+og[2..n]}

```

**cube and octahedron families explanation - coordinates**

The n-cube has `2**n` vertices, each represented by an array of n `1`s and `-1`s (all possibilities are allowed.) We iterate through indexes `0` to `2**n-1` of the list of all vertices, and build an array for each vertex by iterating through the bits of the index and adding `-1`or `1` to the array (least significant bit to most significant bit.) Thus Binary `1101` becomes the 4d point `[1,-1,1,1]`.

The n-octahedron or n-orthoplex has `2n` vertices, with all coordinates zero except one, which an be `1` or `-1`. The order of the vertices in the array generated is `[[1,0,0..],[-1,0,0..],[0,1,0..],[0,-1,0..],[0,0,1..],[0,0,-1..]...]`. Note that as the octahedron is the dual of the cube, the vertices of the octahedron are defined by the centres of the faces of the cube that surrounds it.

**cube and octahedron families explanation - graph topology**

Some inspiration was taken from Hypercube sides and the fact that the hyperoctahedron is the dual of the hypercube.

For the n-cube, there are `3**n` items to catalogue. For example, the 3 cube has `3**3` = 27 elements. This can be seen by studying a rubik's cube, which has 1 centre, 6 faces, 12 edges and 8 vertices for a total of 27. We iterate through -1,0 and -1 in all dimensions defining an n-cube of sidelength 2x2x2.. and return all vertices that are NOT on the opposite side of the cube. Thus the centrepoint of the cube returns all 2\**n vertices, and moving one unit away from the centre along any axis reduces the number of vertices by half.

As with the tetrahedron family, we start by generating an empty array of arrays and populate it according to the number of vertices per element. Note that because the number of vertices varies as 2\**n as we go up through edges, faces, cubes, etc, we use `log2(s.size)+1` instead of simply `s.size`. Again, we have to remove the hypercube itself and all elements with less than 2 vertices before returning from the function.

The octahedron/orthoplex family are the duals of the cube family, therefore again there are `3**n` items to catalogue. Here we iterate through `-1,0,1` for all the dimensions and if the nonzero coordinate of a vertex is equal to the corresponding coordinate of the point, the vertex is added to the list corresponding to that point. Thus an edge corresponds to a point with two nonzero coordinates, a triangle to a point with 3 nonzero coordinates and a tetrahedron to a point with 4 nonzero contacts (in 4d space.)

The resulting arrays of vertex for each point are stored in a large array as for the other cases, and we have to remove any elements with less than 2 vertices before returning. But in this case we do not have to remove the complete parent n-tope because the algorithm does not record it.

The implementations of the code for the cube were designed to be as similar as possible. While this has a certain elegance, it is likely that more efficient algorithms based on the same principles could be devised.

https://en.wikipedia.org/wiki/Hypercube

http://mathworld.wolfram.com/Hypercube.html

https://en.wikipedia.org/wiki/Cross-polytope

http://mathworld.wolfram.com/CrossPolytope.html

# Code for generating tables for the 3d special cases

An orientation with the icosahedron / dodecahedron oriented with the fivefold symmetry axis parallel to the last dimension was used, as it made for the most consistent labelling of the parts. The numbering of vertices and faces for the icosahedron is per the diagram in the code comments, and reversed for the dodecahedron.

According to https://en.wikipedia.org/wiki/Regular\_icosahedron the latitude of the 10 non-polar vertices of the icosahedron is +/-arctan(1/2) The coordinates of the first 10 vertices of the icosahedron are calculated from this, on two circles of radius 2 at distance +/-2 from the xy plane. This makes the overall radius of the circumsphere sqrt(5) so the last 2 vertices are at (0,0,+/-sqrt(2)).

The coordinates of the vertices of the dodecahedron are calculated by summing the coordinates of the three icosahedron vertices that surround them.

```
=begin
TABLE NAMES      vertices     edges      faces
icosahedron      vv           ee         ff
dodecahedron     uu           aa         bb

    10
    / \   / \   / \   / \   / \
   /10 \ /12 \ /14 \ /16 \ /18 \
   -----1-----3-----5-----7-----9
   \ 0 / \ 2 / \ 4 / \ 6 / \ 8 / \
    \ / 1 \ / 3 \ / 5 \ / 7 \ / 9 \
     0-----2-----4-----6-----8-----
      \11 / \13 / \15 / \17 / \19 /
       \ /   \ /   \ /   \ /   \ /
       11
=end

vv=[];ee=[];ff=[]
10.times{|i|
  vv[i]=[2*sin(PI/5*i),2*cos(PI/5*i),(-1)**i]
  ee[i]=[i,(i+1)%10];ee[i+10]=[i,(i+2)%10];ee[i+20]=[i,11-i%2]
  ff[i]=[(i-1)%10,i,(i+1)%10];ff[i+10]=[(i-1)%10,10+i%2,(i+1)%10]

}
vv+=[[0,0,-5**0.5],[0,0,5**0.5]]

uu=[];aa=[];bb=[]
10.times{|i|
  uu[i]=(0..2).map{|j|vv[ff[i][0]][j]+vv[ff[i][1]][j]+vv[ff[i][2]][j]}
  uu[i+10]=(0..2).map{|j|vv[ff[i+10][0]][j]+vv[ff[i+10][1]][j]+vv[ff[i+10][2]][j]}
  aa[i]=[i,(i+1)%10];aa[i+10]=[i,(i+10)%10];aa[i+20]=[(i-1)%10+10,(i+1)%10+10]
  bb[i]=[(i-1)%10+10,(i-1)%10,i,(i+1)%10,(i+1)%10+10]
}
bb+=[[10,12,14,16,18],[11,13,15,17,19]]

```

# Code for generating the tables for the 4d special cases

This is a bit of a hack. This code takes a few seconds to run. It would be better to store the output in a file and load it in as required.

The list of 120 vertex coordinates for the 600cell is from http://mathworld.wolfram.com/600-Cell.html . The 24 vertex coordinates which do not feature a golden ratio form the vertices of a 24-cell. Wikipedia has the same scheme but has an error in the relative scale of these 24 coordinates and the other 96.

```
#TABLE NAMES                           vertices     edges      faces   cells
#600 cell (analogue of icosahedron)    v            e          f       g
#120 cell (analogue of dodecahedron)   u            x          y       z
#24 cell                               o            p          q       r

#600-CELL

# 120 vertices of 600cell. First 24 are also vertices of 24-cell

v=[[2,0,0,0],[0,2,0,0],[0,0,2,0],[0,0,0,2],[-2,0,0,0],[0,-2,0,0],[0,0,-2,0],[0,0,0,-2]]+

(0..15).map{|j|[(-1)**(j/8),(-1)**(j/4),(-1)**(j/2),(-1)**j]}+

(0..95).map{|i|j=i/12
   a,b,c,d=1.618*(-1)**(j/4),(-1)**(j/2),0.618*(-1)**j,0
   h=[[a,b,c,d],[b,a,d,c],[c,d,a,b],[d,c,b,a]][i%12/3]
   (i%3).times{h[0],h[1],h[2]=h[1],h[2],h[0]}
h}

#720 edges of 600cell. Identified by minimum distance of 2/phi between them

e=[]
120.times{|i|120.times{|j|
  e<<[i,j]  if i<j && ((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2+(v[i][2]-v[j][2])**2+(v[i][3]-v[j][3])**2)**0.5<1.3
}}

#1200 faces of 600cell.
#If 2 edges share a common vertex and the other 2 vertices form an edge in the list, it is a valid triangle.

f=[]
720.times{|i|720.times{|j|
  f<< [e[i][0],e[i][1],e[j][1]] if i<j && e[i][0]==e[j][0] && e.index([e[i][1],e[j][1]])
}}

#600 cells of 600cell.
#If 2 triangles share a common edge and the other 2 vertices form an edge in the list, it is a valid tetrahedron.

g=[]
1200.times{|i|1200.times{|j|
  g<< [f[i][0],f[i][1],f[i][2],f[j][2]] if i<j && f[i][0]==f[j][0] && f[i][1]==f[j][1] && e.index([f[i][2],f[j][2]])

}}

#120 CELL (dual of 600 cell)

#600 vertices of 120cell, correspond to the centres of the cells of the 600cell
u=g.map{|i|s=[0,0,0,0];i.each{|j|4.times{|k|s[k]+=v[j][k]/4.0}};s}

#1200 edges of 120cell at centres of faces of 600-cell. Search for pairs of tetrahedra with common face
x=f.map{|i|s=[];600.times{|j|s<<j if i==(i & g[j])};s}

#720 pentagonal faces, surrounding edges of 600-cell. Search for sets of 5 tetrahedra with common edge
y=e.map{|i|s=[];600.times{|j|s<<j if i==(i & g[j])};s}

#120 dodecahedral cells surrounding vertices of 600-cell. Search for sets of 20 tetrahedra with common vertex
z=(0..119).map{|i|s=[];600.times{|j|s<<j if [i]==([i] & g[j])};s}

#24-CELL
#24 vertices, a subset of the 600cell
o=v[0..23]

#96 edges, length 2, found by minimum distances between vertices
p=[]
24.times{|i|24.times{|j|
  p<<[i,j]  if i<j && ((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2+(v[i][2]-v[j][2])**2+(v[i][3]-v[j][3])**2)**0.5<2.1
}}

#96 triangles
#If 2 edges share a common vertex and the other 2 vertices form an edge in the list, it is a valid triangle.
q=[]
96.times{|i|96.times{|j|
  q<< [p[i][0],p[i][1],p[j][1]] if i<j && p[i][0]==p[j][0] && p.index([p[i][1],p[j][1]])
}}

#24 cells. Calculates the centre of the cell and the 6 vertices nearest it
r=(0..23).map{|i|a,b=(-1)**i,(-1)**(i/2)
    c=[[a,b,0,0],[a,0,b,0],[a,0,0,b],[0,a,b,0],[0,a,0,b],[0,0,a,b]][i/4]
    s=[]
    24.times{|j|t=v[j]
    s<<j if (c[0]-t[0])**2+(c[1]-t[1])**2+(c[2]-t[2])**2+(c[3]-t[3])**2<=2
    }
s}

```

https://en.wikipedia.org/wiki/600-cell

http://mathworld.wolfram.com/600-Cell.html

https://en.wikipedia.org/wiki/120-cell

http://mathworld.wolfram.com/120-Cell.html

https://en.wikipedia.org/wiki/24-cell

http://mathworld.wolfram.com/24-Cell.html

# Example of use and output

```
cell24 = polytope[[3,4,3]]

puts "vertices"
cell24[0].each{|i|p i}
puts "edges"
cell24[1].each{|i|p i}
puts "faces"
cell24[2].each{|i|p i}
puts "cells"
cell24[3].each{|i|p i}

vertices
[2, 0, 0, 0]
[0, 2, 0, 0]
[0, 0, 2, 0]
[0, 0, 0, 2]
[-2, 0, 0, 0]
[0, -2, 0, 0]
[0, 0, -2, 0]
[0, 0, 0, -2]
[1, 1, 1, 1]
[1, 1, 1, -1]
[1, 1, -1, 1]
[1, 1, -1, -1]
[1, -1, 1, 1]
[1, -1, 1, -1]
[1, -1, -1, 1]
[1, -1, -1, -1]
[-1, 1, 1, 1]
[-1, 1, 1, -1]
[-1, 1, -1, 1]
[-1, 1, -1, -1]
[-1, -1, 1, 1]
[-1, -1, 1, -1]
[-1, -1, -1, 1]
[-1, -1, -1, -1]
edges
[0, 8]
[0, 9]
[0, 10]
[0, 11]
[0, 12]
[0, 13]
[0, 14]
[0, 15]
[1, 8]
[1, 9]
[1, 10]
[1, 11]
[1, 16]
[1, 17]
[1, 18]
[1, 19]
[2, 8]
[2, 9]
[2, 12]
[2, 13]
[2, 16]
[2, 17]
[2, 20]
[2, 21]
[3, 8]
[3, 10]
[3, 12]
[3, 14]
[3, 16]
[3, 18]
[3, 20]
[3, 22]
[4, 16]
[4, 17]
[4, 18]
[4, 19]
[4, 20]
[4, 21]
[4, 22]
[4, 23]
[5, 12]
[5, 13]
[5, 14]
[5, 15]
[5, 20]
[5, 21]
[5, 22]
[5, 23]
[6, 10]
[6, 11]
[6, 14]
[6, 15]
[6, 18]
[6, 19]
[6, 22]
[6, 23]
[7, 9]
[7, 11]
[7, 13]
[7, 15]
[7, 17]
[7, 19]
[7, 21]
[7, 23]
[8, 9]
[8, 10]
[8, 12]
[8, 16]
[9, 11]
[9, 13]
[9, 17]
[10, 11]
[10, 14]
[10, 18]
[11, 15]
[11, 19]
[12, 13]
[12, 14]
[12, 20]
[13, 15]
[13, 21]
[14, 15]
[14, 22]
[15, 23]
[16, 17]
[16, 18]
[16, 20]
[17, 19]
[17, 21]
[18, 19]
[18, 22]
[19, 23]
[20, 21]
[20, 22]
[21, 23]
[22, 23]
faces
[0, 8, 9]
[0, 8, 10]
[0, 8, 12]
[0, 9, 11]
[0, 9, 13]
[0, 10, 11]
[0, 10, 14]
[0, 11, 15]
[0, 12, 13]
[0, 12, 14]
[0, 13, 15]
[0, 14, 15]
[1, 8, 9]
[1, 8, 10]
[1, 8, 16]
[1, 9, 11]
[1, 9, 17]
[1, 10, 11]
[1, 10, 18]
[1, 11, 19]
[1, 16, 17]
[1, 16, 18]
[1, 17, 19]
[1, 18, 19]
[2, 8, 9]
[2, 8, 12]
[2, 8, 16]
[2, 9, 13]
[2, 9, 17]
[2, 12, 13]
[2, 12, 20]
[2, 13, 21]
[2, 16, 17]
[2, 16, 20]
[2, 17, 21]
[2, 20, 21]
[3, 8, 10]
[3, 8, 12]
[3, 8, 16]
[3, 10, 14]
[3, 10, 18]
[3, 12, 14]
[3, 12, 20]
[3, 14, 22]
[3, 16, 18]
[3, 16, 20]
[3, 18, 22]
[3, 20, 22]
[4, 16, 17]
[4, 16, 18]
[4, 16, 20]
[4, 17, 19]
[4, 17, 21]
[4, 18, 19]
[4, 18, 22]
[4, 19, 23]
[4, 20, 21]
[4, 20, 22]
[4, 21, 23]
[4, 22, 23]
[5, 12, 13]
[5, 12, 14]
[5, 12, 20]
[5, 13, 15]
[5, 13, 21]
[5, 14, 15]
[5, 14, 22]
[5, 15, 23]
[5, 20, 21]
[5, 20, 22]
[5, 21, 23]
[5, 22, 23]
[6, 10, 11]
[6, 10, 14]
[6, 10, 18]
[6, 11, 15]
[6, 11, 19]
[6, 14, 15]
[6, 14, 22]
[6, 15, 23]
[6, 18, 19]
[6, 18, 22]
[6, 19, 23]
[6, 22, 23]
[7, 9, 11]
[7, 9, 13]
[7, 9, 17]
[7, 11, 15]
[7, 11, 19]
[7, 13, 15]
[7, 13, 21]
[7, 15, 23]
[7, 17, 19]
[7, 17, 21]
[7, 19, 23]
[7, 21, 23]
cells
[0, 1, 8, 9, 10, 11]
[1, 4, 16, 17, 18, 19]
[0, 5, 12, 13, 14, 15]
[4, 5, 20, 21, 22, 23]
[0, 2, 8, 9, 12, 13]
[2, 4, 16, 17, 20, 21]
[0, 6, 10, 11, 14, 15]
[4, 6, 18, 19, 22, 23]
[0, 3, 8, 10, 12, 14]
[3, 4, 16, 18, 20, 22]
[0, 7, 9, 11, 13, 15]
[4, 7, 17, 19, 21, 23]
[1, 2, 8, 9, 16, 17]
[2, 5, 12, 13, 20, 21]
[1, 6, 10, 11, 18, 19]
[5, 6, 14, 15, 22, 23]
[1, 3, 8, 10, 16, 18]
[3, 5, 12, 14, 20, 22]
[1, 7, 9, 11, 17, 19]
[5, 7, 13, 15, 21, 23]
[2, 3, 8, 12, 16, 20]
[3, 6, 10, 14, 18, 22]
[2, 7, 9, 13, 17, 21]
[6, 7, 11, 15, 19, 23]

```

---
Tags: code-golf, math, geometry
---


title: 2D Array Middle Point

text:
# Question
Title: 2D Array Middle Point
Given dimensions of a 2D array, except **1xn**, that results in an odd number of elements, find the midpoint index.

Example: Input is **3x5**, representing the 2D array

> \[0,0\] \[0,1\] \[0,2\] \[0,3\] \[0,4\]
>
> \[1,0\] \[1,1\] \[1,2\] \[1,3\] \[1,4\]
>
> \[2,0\] \[2,1\] \[2,2\] \[2,3\] \[2,4\]

The midpoint index is **\[1,2\]**

### Input

> **3**
>
> **5**

### Output

> **1 , 2**

### Rules

* Standard code-golf rules, fewest bytes wins
* Either full program or function is permitted
* When input is either **1xn** or the corresponding array would have an even number of elements, *output must be* **\[0,0\]**
* **nx1** should be treated like any other array

# Answer
> 4 votes
# APL (Dyalog Classic), ~~20~~ ~~19~~ ~~15~~ 13 bytes

```
⌊÷∘2×2|×/×1≠⊃

```

Try it online!

# Answer
> 4 votes
# Japt, 11 bytes

My first (somewhat) serious Japt submission! Any help is appreciated, I think ~10 bytes or even less may be possible. Saved 4 bytes thanks to Shaggy!

```
£ÎÉ©Ueu)*Xz

```

Try it here!

### How it works

*Slightly outdated.*

```
£eu *UÎ>1 *Xz – Full program.
£             – For each X of the input array.
          *Xz – Multiply floor(X/2) by the truth value of:
 eu           – Are both numbers odd? And...
    *UÎ>1     – Is the initial element greater than 1?
              – Implicit output to STDOUT.

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 23 bytesSBCS

Anonymous prefix function. Takes rows,columns as right argument.

```
{0::0 0⋄÷∘÷@0⌽¨⍨.5×⍵-1}

```

Try it online!

`{``}` "dfn";  is right argument (rightmost letter of Greek alphabet).

`0::` if any error happens:

`0 0` return `[0,0]`

now try:

`⍵-1` right argument minus 1

`.5×` multiply by a half

`⌽¨⍨` rotate each by itself (this errors on non-integers)

`÷∘÷@0` reciprocal of reciprocal at position 0 (this errors when the first coordinate is 0)

# Answer
> 3 votes
# 05AB1E, ~~9~~ 8 bytes

Saved 1 byte thanks to *Mr. Xcoder* (remove `D`)

```
¬≠*ÉP*;ï

```

Try it online! or as a Test Suite

**Explanation**

```
¬≠*       # multiply the input by its first value falsified
   ÉP*    # multiply the input by the product of the results values' oddness
      ;   # divide by 2
       ï  # convert to int

```

# Answer
> 3 votes
# Japt, ~~24~~ 16 bytes

*-8 bytes saved thanks to @Shaggy*

```
Neu ©UÉ?Nmz :2ÆT

```

Try it online!

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

*Saved 1 byte thanks to @Neil*

Takes the dimensions in currying syntax `(w)(h)`.

```
w=>h=>w&h&w>1?[h>>1,w>>1]:[0,0]

```

Try it online!

---

# Original version, 32 bytes

Takes the dimensions in currying syntax `(w)(h)`.

```
w=>h=>w*h&!!--w?[h>>1,w/2]:[0,0]

```

Try it online!

### How?

We want to test whether both \\$w\\$ and \\$h\\$ are odd, which is true if and only if \\$w\times h\\$ is odd. We also want to make sure that \\$w\\$ is not equal to \\$1\\$, which means that \\$w-1\\$ is not equal to \\$0\\$. We can merge both tests into:

```
w * h & !!--w

```

If this test passes, we know that \\$w\\$ was odd and is now even (since it was decremented), so we can divide it by \\$2\\$ with a standard division. For \\$h\\$, we use a bitwise shift instead because it's still odd.

# Answer
> 2 votes
# Perl 6, ~~42~~ 39 bytes

```
{(^$^a X ^$^b)[$b-1&&$a*$b%2&&$a*$b/2]}

```

Try it online!

Anonymous code block that returns a list of two integers.

### Explanation:

```
{                                     }  # Anonymous code block
 (^$^a X ^$^b)   # Cross product of the two ranges, basically the flattened 2D array
              [                      ] # Get the element at
                            &&$a*$b/2    # Midpoint of the array
                     $a*$b%2             # If the numbers are odd
               $b-1&&                    # And the second element is not 1
                                        # Else the 0th element, which is 0,0

```

# Answer
> 2 votes
# Jelly, 10 bytes

This confused me :p

```
:2×Ḃ_ỊḢ$PƲ

```

A monadic link accepting a list of the dimensions returning a list of the middle-indices or `[0,0]` in the special-cases.

**Try it online!**

### How?

```
:2×Ḃ_ỊḢ$PƲ - Link: list of dimension lengths        e.g.  [19,12]  or  [19,13]  or  [1,19]  or  [19,1]
:2        - integer divide by two (gets middle indices)   [9,6]         [9,6]       [0,9]       [9,0]
        Ʋ - last four links as a monad:
   Ḃ      -   bit (n%2) (of the input)                    [1,0]         [1,1]       [1,1]       [1,1]
       $  -   last two links as a monad (of the input):
     Ị    -     insignificant? (abs(n)<=1)                [0,0]         [0,0]       [1,0]       [0,1]
      Ḣ   -     head                                      0             0           1           0
    _     -   subtract (vectorises)                       [1,0]         [1,1]       [0,0]       [1,1]
       P  -   product                                     0             1           0           1
  ×       - multiply (vectorises)                         [0,0]         [9,6]       [0,0]       [9,0]

```

# Answer
> 2 votes
# Haskell, 46 42 bytes

```
x%y|odd$x*y,x>1=(`div`2)<$>[x,y]|1<2=[0,0]

```

Try it online!

*EDIT: -4 bytes thanks to a trick from Arnauld's answer.*

# Answer
> 1 votes
# Julia 0.6, 28 27 bytes

```
x\y=x&y&1&(x>1)*[x÷2,y÷2]

```

Try it online!

*(-1 byte thanks to Jo King.)*

Explanation:

`x\y` \- define an operator instead of a function, to save bytes
`x&y&1` \- check that both inputs are odd.
`&(x>1)` \- and that the first input is not 1
`*` \- the result of the above checks is 0 or 1, multiply that with:
`[x÷2,y÷2]` \- `÷` is integer division, so here for odd numbers gives `(n-1)/2` i.e. the middle index. So this forms a vector of the two middle indices (which might be made `[0, 0]` if any of the previous checks fail).

# Answer
> 1 votes
# Jelly, 11 bytes

*Ugh. Waaaaaaaay too long!*

```
:2×ḂẠ$×Ḣn1Ɗ

```

Try it online!

### Alternative, 11 bytes

```
ḷ/>1×ḂẠ$×:2

```

Try it online!

# Answer
> 1 votes
# Lua, 77 bytes

```
x,y=...f=math.floor print((x%2==1 and y%2==1)and f(x/2)..","..f(y/2)or "0,0")

```

Try it online!

not the smallest language but submission for practicing :)

# Answer
> 1 votes
# Rust, 42 bytes

```
|w,h|if w>1&&w*h%2>0{(w/2,h/2)}else{(0,0)}

```

Try it online!

# Answer
> 1 votes
# , ~~38~~ ~~29~~ 28 bytes

An extra byte removed thanks to @Guiseppe

```
(i=scan()-1)/2*!any(i%%2,!i)

```

Try it online!

Get the input, subtract 1 store in `i` and divide by 2 and multiply by not any evens or 0's in `i`

# Answer
> 0 votes
# Python 2, 39 bytes

-2 bytes thanks to ovs

```
lambda a,b:[0,a/2,0,b/2][a>1==a*b%2::2]

```

Try it online!

# Answer
> 0 votes
# Python 2, ~~43~~ 41 bytes

```
lambda a,b:((0,0),(a/2,b/2))[a*b%2*(a>1)]

```

Try it online!

No rocket science here.

-2 with thanks to @MrXcoder and @Emigna

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


# Question
Title: Find the minimum cost matching between arrays of integers
Consider two sorted arrays of integers \\$X\\$ and \\$Y\\$ of size \\$m\\$ and \\$n\\$ respectively with \\$m \< n\\$. For example \\$ X = (1,4)\\$, \\$Y = (2,10,11)\\$.

We say that a matching is some way of pairing each element of \\$X\\$ with an element of \\$Y\\$ in such a way that no two elements of \\$X\\$ are paired with the same element of \\$Y\\$. The cost of a matching is just the sum of the absolute values of the differences in the pairs.

For example, with \\$X = (7,11)\\$, \\$Y = (2,10,11)\\$ we can make the pairs \\$(7,2), (11,10)\\$ which then has cost \\$5+1 = 6\\$. If we had made the pairs \\$(7,10), (11,11)\\$ the cost would have been \\$3+0 = 3\\$. If we had made the pairs \\$(7,11), (11,10)\\$ the cost would have been \\$4+1 = 5\\$.

As another example take \\$X = (7,11,14)\\$, \\$Y = (2,10,11,18)\\$. We can make the pairs \\$(7,2), (11,10), (14,11)\\$ for a cost of \\$9\\$. The pairs \\$(7,10), (11,11), (14,18)\\$ cost \\$7\\$.

The task is to write code that, given two sorted arrays of integers \\$X\\$ and \\$Y\\$, computes a minimum cost matching.

## Test cases

```
[1, 4],      [2, 10, 11]     => [[1, 2], [4, 10]]
[7, 11],     [2, 10, 11]     => [[7, 10], [11, 11]]
[7, 11, 14], [2, 10, 11, 18] => [[7, 10], [11, 11], [14, 18]]

```

# Answer
> 4 votes
# Jelly, ~~15 14 12~~ 11 bytes

```
Œ!ż€IASƊÞḢṁ

```

Try it online!

* -1 byte thanks to Jonathan Allan
* -1 byte thanks to Mr. Xcoder
* -2 bytes thanks to an anonymous editor

Brute force. Takes input as \\$Y\\$ then \\$X\\$.

```
Œ!ż€IASƊÞḢṁ
Œ!                 All permutations of Y.
  ż€               Zip each of the permutations with X.

       ƊÞ          Sort by:
    I              Difference of each pair.
     A             Absolute value.
      S            Sum.
         Ḣ         Take the first matching.
          ṁ        Mold the result like X. Keeps only values up to the length
                   of X which removes unpaired values from Y.

```

# Answer
> 4 votes
# Brachylog, 16 bytes

```
∧≜I&pᵐz₀.-ᵐȧᵐ+I∧

```

Try it online!

### Explanation

```
∧
 ≜I                   Take an integer I = 0, 1, -1, 2, -2, 3, -3, …
   &pᵐ                Permute each sublist
      z₀.             Zip the sublists together. The result of the zip is the output
         -ᵐȧᵐ         Absolute differences of each pair
             +I       The sum of these differences must be I
               ∧

```

Since we unify `I` to an integer at the very beginning, we try things from small values of `I` to large values of `I`, which means the first time it will succeed will necessarily be for the pairing with smallest absolute differences.

# Answer
> 3 votes
## Haskell, ~~78~~ ~~77~~ 76 bytes

```
import Data.Lists
(argmin(sum.map(abs.uncurry(-))).).(.permutations).map.zip

```

TIO doesn't have `Data.Lists`, so no link.

Basically the same algorithm as seen in @dylnan's answer.

Edit: -1 byte thanks to @BMO.

# Answer
> 2 votes
# JavaScript (ES7), 121 bytes

Takes the 2 arrays in currying syntax `(x)(y)`.

```
x=>y=>(m=P=(b,[x,...a],s=0,o=[])=>1/x?b.map((v,i)=>P(b.filter(_=>i--),a,s+(x-v)**2,[[x,v],...o])):m<s||(r=o,m=s))(y,x)&&r

```

Try it online!

# Answer
> 2 votes
# , 24 bytes

```
[,.[-[:,@:(0{]#~1>])"1-/

```

Try it online!

## Explanation/Demonstration:

A dyadic verb, `x f y`

`-/` finds the differences

```
 7 11 14 -/ 2 10 11 18
 5 _3 _4 _11
 9  1  0  _7
12  4  3  _4

```

`(0{]#~1>])"1` for each row keep only the non-positive values and take the first one:

```
   7 11 14 ([:(0{]#~1>])"1-/) 2 10 11 18
_3 0 _4

```

`[:,@:` flattens the list (to match the shape of the left argument)

`[-` subtract the min. differences from the left argument

```
    7 11 14 ([-[:,@:(0{]#~1>])"1-/) 2 10 11 18
10
11
18

```

`[,.` stitch them to the left argument:

```
   7 11 14 ([,.[-[:,@:(0{]#~1>])"1-/) 2 10 11 18
 7 10
11 11
14 18

```

# Answer
> 1 votes
# MATL, 16 bytes

```
yn&Y@yy&1ZP&X<Y)

```

Inputs are `X`, then `Y`.

The matching is output with the first values of each pair (that is, `X`) in the first line, and the second values of each pair in the second line.

Try it online! Or verify all test cases.

### Explanation

```
y       % Implicit inputs: X, Y. Duplicate from below
        % STACK: [7 11], [2 10 11], [7 11]
n       % Number of elements
        % STACK: [7 11], [2 10 11], 2
&Y@     % Variations without repetition
        % STACK: [7 11], [2 10; 2 11; 10 2; 10 11; 11 2; 11 10]
yy      % Duplicate top two elements
        % STACK: [7 11], [2 10; ...; 11 10], [7 11], [2 10; ...; 11 10]
&1ZP    % Compute cityblock distance between rows of the two input matrices
        % STACK: [7 11], [2 10;...; 11 10], [6 5 12 3 13 5]
&X<     % Argmin (first index of occurrences of the minimum)
        % STACK: [7 11], [2 10; 2 11; 10 2; 10 11; 11 2; 11 10], 4
Y)      % Row indexing. Implicit display
        % STACK: [7 11], 10 11]

```

# Answer
> 1 votes
# Octave, 66 bytes

```
@(X,Y)[X;C([~,r]=min(sum(abs(X-(C=perms(Y)(:,1:numel(X)))),2)),:)]

```

Anonymous function that takes row vectors `X`, `Y` as inputs and outputs a 2-row matrix where each column is a pair of the matching.

**Try it online!**

# Answer
> 1 votes
# Pyth, 18 bytes

```
t#h.msaMbm.T,dvz.p

```

Try it here!

# Answer
> 1 votes
# Pyth, 16 bytes

```
hosaMNCM*.pQ.cEl

```

Try it online here, or verify all test cases at once here.

```
hosaMNCM*.pQ.cEl   Implicit: Q=evaluated 1st input, E=evaluated 2nd input
               l   Length of 1st input (trailing Q inferred)
            .cE    All combinations of 2nd input of the above length
         .pQ       All permutations of 1st input
        *          Cartesian product
      CM           Transpose each of the above
 o                 Order the above using:
   aMN               Take the absolute difference of each pair
  s                  ... and take their sum
h                  Take the first element of the sorted list, implicit print

```

# Answer
> 1 votes
# Jelly, (10?) 12 bytes

10 bytes if just the elements of Y are required (see comments) - not sure if it's allowed by spec yet though (and maybe it shouldn't be since other answers already implement this detail).
This may be achieved by removing the trailing `⁸ż`.

```
Lœc@ạS¥Þ⁸Ḣ⁸ż

```

A dyadic link accepting X on the left and Y on the right.
(`œc⁹L¤ạS¥ÞḢż@` and the 10 byte `œc⁹L¤ạS¥ÞḢ` do the same with Y on the left and X on the right).

**Try it online!**

### How?

```
Lœc@ạS¥Þ⁸Ḣ⁸ż - Link: sorted list of integers X, sorted list of integers Y
L            - length
   @         - with swapped arguments:
 œc          -   combinations (chosen as if picked left-to-right
             -      e.g. [2,5,7,9] œc 2 -> [[2,5],[2,7],[2,9],[5,7],[5,9],[7,9]] )
        ⁸    - chain's left argument (to be on right of the following...)
       Þ     -   sort by:
      ¥      -     last two links as a dyad:
    ạ        -       absolute difference (vectorises)
     S       -       sum
         Ḣ   - head (since sorted this is just the first minimal choices from Y)
          ⁸  - chain's left argument
           ż - zip with (the chosen Y elements)

```

# Answer
> 1 votes
# JavaScript (ES7), 100 bytes

New here; any tips/corrections would be appreciated! A previous attempt overlooked complications with sorting an array containing a `NaN` value, so hopefully I haven't missed anything this time.

```
(x,y,q=Infinity)=>y.map((u,j)=>(p=0,s=x.map((t,i)=>(u=y[i+j],p+=(t-u)**2,[t,u])),p)<q&&(q=p,r=s))&&r

```

Expects two arguments as *X*, *Y*, respectively. Try it online!

Appears to be similar to @Arnauld's solution

# Explanation

Relies on the fact that given *X*, *Y* are sorted, there exists a solution of minimum cost matches where if all pairs are arranged to preserve the order of elements of *X*, all *Y* elements in the arrangement also preserve their order.

```
(x, y, q = Infinity) =>
    y.map((u, j) =>                   // iterate over indices of y
        (
            p=0,
            s=x.map((t, i) => (       // map each element of x to...
                    u = y[i+j],       // an element of y offset by j
                    p += (t-u)**2,    // accumulate the square of the difference
                    [t, u]            // new element of s
                )),
            p
        ) < q                         // if accumulated cost less than previous cost...
                                      // (if p is NaN, any comparison will return false and short circuit)
        && (q=p, r=s)                 // save cost, pair values respectively
    ) && r                            // return lowest-cost pairs

```

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