title: Seeking Leapers

text:
# Question
Title: Seeking Leapers
I recently got a really weird irregular chess board. It's squares are all over the place and not even all connected. At least they're still laid out on a regular grid. I want to adapt the chess rules to be able to play on the board, but to start with, I need a piece that can actually go anywhere on the board, and it seems a leaper is my best bet for that.

Leapers are the fairy chess generalisation of knights. Leapers are parameterised by two integers **m** and **n** and can move **m** squares in one direction and then another **n** squares in either perpendicular direction. For the standard knight, we have **(m, n) = (2, 1)**. The entire move is considered a single jump such that none of the squares on the way to the target need to be empty or even exist.

## The Challenge

You're given a "chess board" in the form of a list of positive 2D integer coordinates which represent the squares that are part of the board. Your task is to find a leaper which, given enough moves, can reach any square on the board.

Let's look at some examples. The standard chessboard uses a regular grid of 8x8 squares (note that we don't distinguish between white and black squares for this challenge):

```
########
########
########
########
########
########
########
########

```

The standard knight can reach all of those, so `(2, 1)` would be a valid output. However, `(1, 1)` for example wouldn't be valid, since such a piece can only reach half of the squares no matter where it starts. `(1, 0)` on the other hand would also be a valid output, since all the squares are orthogonally connected.

Now if we have an irregular board like:

```
#   #
 # # #
  # # #
 # #
    #

```

Then possible solutions are `(1, 1)` and `(3, 1)`. We can also have a board with completely disconnected regions like:

```
#### ####
#### ####
#### ####
#### ####

```

The standard knight `(2, 1)` can still reach all of the squares here, which is in fact the only solution.

And finally, the following simple board cannot be completely reached by any leaper at all:

```
#
 ##

```

Note that the input format will not be as an ASCII representation but a list of coordinates instead. E.g. the second example above could be given as:

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

```

## Rules

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

The input coordinates can be taken in any convenient list format (flat list, list of pairs, list of complex integers, string with consistent separators, etc.).

The output should be the two integers **m** and **n** that identify the leaper if a solution exists (as two separate integers, a list, a string with non-numeric delimiter, etc.). If no solution exists, you may output any consistent value which cannot possibly be a valid leaper. This includes the pair of integers `(0, 0)` in your normal format, as well as anything that isn't a pair of non-negative integers.

Your program needs to handle any of the test cases **within a minute**. This is a somewhat fuzzy restriction, but use common sense: if it takes 2 minutes on your machine, I think we can assume that it might run within 1 on someone else's, but if it takes 20 that's less likely. It shouldn't be hard to solve each test case in a matter of seconds, so this rule only acts to rule out naive brute force.

Standard rules apply.

## Test Cases

Each test case is of the form `board => all valid leapers`. Remember that you only need to output one of those. If the list of leapers is empty, make sure to return something that *isn't* a valid leaper.

```
Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

```

As a special case, note that for a board consisting of only one cell, any leaper works, but your output must correspond to an actual leaper, so `[0, 0]` is not valid output.

# Answer
# Pyth, ~~41~~ 35

```
hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

```

Exits on error if there are no valid leapers, giving the empty string if STDERR is ignored.

Try it here or run a Test Suite

Saved 6 bytes thanks to isaacg! Basically just finds all leaper candidates by selecting each valid leaper from the first tile to each other tile. Then for each of these, it makes all eight configurations of `[x, y]` offsets that the leaper could take. It then finds all moves starting from the first tile that follow after the move, and discards those that are not in the input. It keeps doing this until the result doesn't change. If this final list is the same as the input then the leaper was valid.

The standard chess board took the longest when I was testing, it took about 3 seconds on my not very impressive computer.
> 12 votes

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


# Question
Title: How can I score challenges with variable problem sizes?
> There is fairly strong support on meta for challenge-writing questions to be on topic on main, provided these questions are specific and answerable. However, we don't have any such questions yet, so I figured I'd test the waters. This question is probably entering good subjective, bad subjective territory, but I think that's likely what challenge-writing questions will have to be. To ensure that they still generate high-quality content, please don't just post wild speculative ideas in the answers. Explain why they avoid the problems mentioned below, or ideally point to existing challenges which have successfully used the suggested technique in the past.

For certain optimisation challenges, a free parameter in setting the challenge is the size of the problem to be optimised. By "optimisation challenge" I don't mean things like our genre, where answers are usually required to be exact/optimal, and the challenge is scored either on a fixed problem size or on the largest problem size that can be handled in a fixed amount of time. I mean specifically challenges where suboptimal solutions to the underlying problem are allowed and even likely, and the goal is to do as well as possible.

For the sake of definiteness, consider busy beaver challenges, although in principle this applies to other challenge types without known optimal solutions as well (I'm just using busy beavers here because they exacerbate the problems mentioned below). Say, I wanted to make a challenge about finding the busiest Brainfuck beaver. The free parameter in busy beaver problems is the size of the code. I can't set the challenge without making reference to the code size in some way. In a way, each value of the problem-size parameter `N` gives a separate (increasingly difficult) challenge. My main question is how I can make such a challenge work without running into balancing problems.

The obvious solution is to fix `N`: "Find a terminating Brainfuck program with `N` bytes of source code which prints as many characters as possible/runs for as many ticks as possible." This has massive balancing issues: if I pick the size too small, someone might quickly find *the* busiest beaver and the challenge is over. If I pick the size too large, the optimal solution will print an astronomical amount of characters before terminating, which means that it will likely be trivial to find such programs and the challenge becomes a chore/exercise in patience — this also leaves the territory where busy beavers can be found programmatically, and instead people would need to start proving their results formally which a lot of people might not consider very fun. Of course, this problem is more pronounced in busy beaver challenges than other types, due to the growth of the optimal solutions, but it applies to other challenges nevertheless.

The next option would to leave `N` unconstrained and make it part of the scoring via some function. Even for "normal" challenges getting the balance of combined scores right is incredibly difficult, but in the case of busy beavers it's actually fundamentally impossible, due to the fact that optimal solutions grow faster with `N` than any computable function. That means I can always beat the best existing answer by going to a sufficiently large `N` where I can easily find a program that runs for so long that I can get a better score without much effort.

I have also considered setting a fixed `N` and allowing people to also submit beavers for larger `N` which will be used as successive tie breakers. This has a similar problem, in that someone can just "happen to find an equally good busy beaver" for a `N`, thereby creating a tie and then just submitting pretty much anything for the next `N` where finding a large score is easier (even if finding the optimal score gets harder). In these cases, how would you deal with multiple people using the same solution? Forbidding it would also be weird in case it's optimal.

Maybe one could strike a middle ground, by making an educated guess at a reasonable `N` and then asking for busy beavers for all sizes within (say) 5 bytes of `N`, so that there's some leeway in both directions (and then you combine the ~10 scores into a single one by one technique or another). This doesn't feel quite satisfactory either because my initial guess for `N` could still be widely off the range that makes for interesting challenges.

**TL;DR:** in cases where the challenge is to (suboptimally solve and) optimise a problem whose size is variable, how do I incorporate the size into the challenge? Ideally I would want people to be able to work with a value of `N` that is near the upper end of the range of tractable sizes. But just in case it turns out that optimal solutions are possible for that `N`, it would be great if solutions for slightly larger `N` would start to weigh in, such that the challenge could continue with a more interesting problem size.

# Answer
> 3 votes
# Find the next N

The challenge would indicate an `N` that submissions should start at.

Then, people would submit answers at the current `N`. If a given submission is proven to be optimal, then `N` is increased by 1, and the process repeats.

There are several ways to score this:

1. Score the best submission at the current `N`
2. Give a point to the best submission at the current `N`, plus a point for each optimal solution
3. Same as #2, but also give a point to the person that proved that a given submission was optimal.

# Answer
> 1 votes
# Give points for solutions within a bounded N

Allow `N` to be within a fixed bounds. The lower bound should exclude obviously trivial answers, and that the higher bound shouldn't be too far from the lower bound.

Then, give 1 point for each person that has the best solution for each `N` within the bounds. If higher `N` means that the solution is harder, then give N points to them. (or some formula based on N).

This method is similar to how AZsPCs does it, but partial points aren't given.

---
Tags: challenge-writing
---


# Question
Title: Can I string all my cords and adapters together?
Suppose one day you are digging through your big box of unused computer cords and adapters (USB to USB mini, VGA to DVI, etc.). There are tangled cords everywhere making quite a mess, and you wonder if you could simplify things by attaching all the cords together in one long strand, and then just rolling it up.

The question is, is it possible to connect all of your cords and adapters in one long line like this? It's obviously not always possible, e.g. if you only had two cords with completely different plugs, they could not be connected together. But if you had a third cord that can connect to both of them, then you could string all your cords together.

You don't care about what type of plugs are on the ends of the all-cord strand. They don't need to plug into one another to form a loop. You only want to know if making the all-cord strand is possible, and if it is, how to do it.

# Challenge

Write a program or function that takes in a multiline string where every line depicts one of the cords you own. A cord is made up of one or more dashes (`-`), with a plug on either end. A plug is always one of the 8 characters `()[]{}<>`.

So these are some valid cords:

```
>->
(--[
}-{
<-----]
(---)

```

But these are not:

```
-->
(--
)--
[{
---

```

When connecting cords, only plugs with the exact same bracket type can be connected together.

So these are some valid cord connections:

```
...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...

```

And these are invalid:

```
...---()---...
...---)(---...
...---{]---...
...---{[---...
...---><---...
...--->)---...

```

If all the cords in the input can be rearranged and attached together in one long strand, then output that strand to stdout on one line (with an optional trailing newline). When there are multiple solutions you can choose any one of them to output. If making a single strand is not possible, then output nothing (or output an empty string with an optional trailing newline).

---

For example, if the input is

```
[-->
{---]
>----{

```

the output could be

```
[-->>----{{---]

```

where all the cords are strung together.

However if the input were

```
[-->
{---]

```

the cords cannot be connected so there would be no output.

---

Note that cords can be flipped around as much necessary to make connections. e.g. `[-->` and `<--]` are effectively the same cord because they can make the same type of connections. Some outputs may depend on flipping the input cords.

---

For example

```
(-[
}--]

```

could have output

```
(-[[--{

```

where the second cord is flipped, or

```
}--]]-)

```

where the first cord is flipped.

(Note that in general flipping the entire output is valid because it's the same as initially flipping every cord individually.)

---

The lengths of the cords in the output should of course match the lengths of the corresponding input cords. But the cords may be reordered and flipped around as much as you want in order to make the all-cord strand. The input will always contain at least one cord.

**The shortest code in bytes wins.**

# Test Cases

Cases with output:

```
[-->
{---]
>----{
gives
[-->>----{{---]
or
[---}}----<<--]

(-[
}--]
gives
(-[[--{
or
}--]]-)

(-)
gives
(-)

[--{
gives
[--{
or
}--]

[-]
]-[
gives
[-]]-[
or
]-[[-]

[----->
)------------[
{--<
}---)
could give
[----->>--}}---))------------[
or
>--}}---))------------[[----->
or
}---))------------[[----->>--}
or
{--<<-----]]------------((---{
etc.

>-->
>->
>--->
could give
>-->>->>--->
or
>--->>-->>->
or
>->>-->>--->
or
<--<<---<<-<
etc.

(-]
]->
>-}
}-)
)-[
[-<
<-{
{-(
could give
(-]]->>-}}-))-[[-<<-{{-(
or
{-((-]]->>-}}-))-[[-<<-{
or
<-{{-((-]]->>-}}-))-[[->
etc.

```

Cases without output:

```
[-->
{---]

[-]
[-]

(-]
]->
}-)

>->
>-->
]---]

[-------------------]
]-------------------[
[-----------------]
[-----------------]

{--[
]--}

```

# Answer
> 10 votes
# Unreadable, 3924 bytes

This is the first time I implemented somewhat of a call-stack-like structure in Unreadable.

(The first version of this was over 5300 bytes, just to give an idea of how much I golfed this.)

> '"""""'""'""""""'""""""'"""'""'""'""'""'""'""'"""""""'"""'""""""'""'"""'""""""""""'""""'""""'""""'""""""'""'""'""'""'""'""'"""""""'"""'"""""'"""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""'""'""'"""""""'"""'""""""""""'""""""""'"""'"""'""""'""""""'""'""'""'""'"""'"""""""'""'""'"""""""'"""'""""""'""'"""""""'"""'""'"""""""'""'"""""""'"""'"""""'""""""'""'"""'"""""""'"""""""'"""'""""'""""""'""'""'""'"""""""'"""'"""""""""'""""""'""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'"""'"""""""""'""""""'""'"""'""""""""'"""""""'""'"""'"""""""""'""""""'""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'"""'"""""""""'""""""'""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'"""'"""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'"""'""""""""'""""""""'"""""""'"""""""'"""'""'""'"""""""'"""""""'"""'""'""'"""""""'"""""""'"""'""'""'"""""""'"""""""'"""'""""""""'"""""""'"""""""'"""'""'"""""""'"""""""'"""'""""""'"""'""'""'"""""""'"""'""""""'""'""'""'"""""""'"""'"""""""'""""""""'"""""""'"""'""""""""""'""""""'"""""""'"""'""""""""'""""""'""'""'""'"""'""""""'""""""'""'"""'""'"""""""'"""'"""'"""""'"""""""'""'""'""'"""'""""'""""'""""""'""'""'"""'""""""'"""'"""'"""""'"""""""'""""""'"""'""'""'""'""'""'"""""""'"""'"""""""""'"""""""'""'""'""'""'"""""""'"""'"""'""""""'""'""'"""'""""""""'"""'"""""""""'"""""""'""'""'"""'""""""'""'""'""'"""'""""""""'"""'""""'""""'""""""'"""'"""""""'"""""""'""'"""'"""""'"""""""'""""""'"""'""'""'""'""'""'"""""""'"""'"""""""""'"""""""'""'""'""'""'"""""""'"""'"""'"""""""""'"""""""""'"""""""'""""""""'"""""""'""'"""'""""'""""'""""""'""""""""'"""'"""""""'""'""'"""""""'""""""""'"""""""'""'"""'""""""'""'""'"""'""'"""""""'"""""""'"""'"""""""""'"""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""""""'""""""""'"""'""""""""'"""""""'""""""""'"""'""""""""'"""'"""'"""'""""""'"""'""""""""'""""""'""'""'"""'""""""'"""""""'""'"""'"""""""'"""'"""'"""""""""'"""""""'""'""'"""'""""""'""""""'""'"""'""'"""""""'""'"""'""""""'"""""""'"""'""""""'"""""""""'"""""""'""""""""'"""""""'"""'""'""'""'""'""'"""""""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'"""'"""'"""""""""'""""""'"""'"""""""'""""""'""'"""'""""""""'"""""""'""'"""'""""""'""'""'""'""'"""""""'"""'""""""'"""""""""'"""""""'""'""'""'"""""""'"""'""'""'""'""'""'""'""'""'""'"""""""'"""'""""""""'"""""""'"""'""""""""'"""'""""""'""'""'""'"""'""""""""'"""'"""""""""'"""""""'"""'"""""'""""""""'"""""""'""""""'"""'""'"""""""'"""'""""'""""'"'"""""""'"""""""'"""""""'"""'"""""'""'""""""'""'"""""""'"""""""'"""'""""""""'"""""""'""'"""""""'"""""""'"""'"'"""""""'""'""'""'""'"""'"'"""""""'""'""'"""""""'"""""""'"""'"""

## Explanation

Consider this example input:

```
>--{
[---}

```

Throughout most of the execution, the tape is laid out as follows:

* Cells 0 to 5 are locations for various variables.
* Cell 6 onwards contain all information about the set of cables in your box:
* The remaining cells after the “zero terminator” contain the stack. Each “stackframe” is a single cell that points to the first cell of a cable (the “start plug” cell). In the above example, when the program decides it has found a solution, the stack will contain 6 (referring to `>--{`, the first cable) and 21 (referring to `{---]`, the mirror of the second cable).

The program proceeds in three main stages:

1. Read the entire input and generate the above structure, including all the mirrored cables.
2. Try out all combinations (but stop if a solution is found).
3. If a solution was found, output it.

The first stage (read input and generate cables structure) only uses cells #1 (which I’ll call `p`) and #2 (which I’ll call `ch`) and operates in a while loop as follows:

* While condition: increment `p` by 6, read the next character (start plug) into cell `*p`, and check that it isn’t `-1` (EOF).
* Read subsequent characters into `*(p+2)`, and count them in `*(p+1)`, until we encounter anything other than `-` (hyphen). At that point, `*(p+1)` will contain the number of hyphens (cable length) and `*(p+2)` the last non-hyphen character (the end plug). (We also copy the hyphen characters to cell #5 so we can access this ASCII code later in the output stage.)
* In a while loop, find the mirror plug and store it at `*(p+3)`, then increment `p` by 2, until `*p` is zero. The loop looks like this in pseudocode:

```
while (ch = *p) {
    *(p+3) = (ch -= 40) ? (ch -= 1) ? (ch -= 19) ? (ch -= 31) ? ch-32 ? *p-2 : *p+2 : *p+2 : *p+2 : *p-1 : *p+1
    p += 2
}

```
* This loop will always perform two iterations (the start plug and end plug) and store the results in the fourth and sixth cell of this cable. Now, if you paid attention, you realize that the sixth cell is indeed the correct location for the mirrored end plug, but the mirrored start plug is in the cell labeled “boolean indicating original cable”. This is OK because we only need this cell to be a non-zero value.
* Since `p` has just been incremented a total of 4, it’s now pointing at the cell labeled “boolean indicating cable is in use”. Set `*(p+3)` to the value of `*(p-1)`. This puts the mirrored start plug in the right place.
* Read (and discard) one more character (which we expect to be a newline, but the program doesn’t check for that).

`p` initially starts out at 0 but is incremented by 6 inside the while condition, thus the cable data starts at cell #6. `p` is incremented by 4 inside the loop body, and thus a total of 10 for each cable, which is exactly what we need.

During the second stage, cells #0–4 are occupied by variables that I’ll call `a`, `p`, `q`, `m`, and `notdone`. (Cell #5 still remembers the ASCII code of the hyphen.)

To get ready for stage 2, we need to set `*p` back to 0 (the cell labeled “zero terminator”) so that it can act as the terminator for the list of cables; we also set `q` (which is our stack pointer) to `p+1` (i.e. the cell after the “zero terminator”; this is where the stack starts); `*q` to 1 (the first item on the stack; why 1 will become apparent later); and `notdone` to 1. All this is done in a single statement:

```
*p = (notdone = *(q = p+1) = 1)-1

```

The second stage is also a while loop. Its condition is simply `notdone`. In each iteration of that while loop, any one of the following four things could happen:

1. We find that all cables are marked “in use”. This means we’ve found a solution (which is represented by the current stack contents).
2. We can advance `*q` to another eligible cable (which we promptly mark as “in use” along with its twin) and then recurse (i.e. create a new stackframe).
3. We cannot advance `*q` because no further eligible cable exists, so we need to backtrack (remove a stackframe and mark the previous cable and its twin as no longer “in use”).
4. We cannot advance `*q` because no further eligible cable exists and we cannot backtrack because we have reached the bottom of the stack. This means there is no solution.

The loop body checks for each of these four conditions in this order. Here are the details:

1. Set `m` and `p` to 1 and in a while loop, increment `p` by 5 (thus iterating through the cables) and check if `*(p+4)` (“in use”) is set. If it isn’t, set `m` to 0. At the end of that loop, `m` tells us if all the cables are in use. If so, set `notdone` to 0 to terminate the main loop. Otherwise, continue at step 2 below.
2. Set `p` to `*q` (the cable at the top of the stack) and in a while loop similar to the above, increment `p` by 5 to iterate through the cables. Starting at `*q` ensures we only consider those that we haven’t already considered before; however, remember that the initial value for a new stackframe is 1, so the first cable looked at is the one at cell 6, which is indeed the first cable.

For each cable, we need to check `*(p+4)` to ensure that it’s not already in use, and also that *either* `*(q-1)` is zero (meaning we’re at the bottom of the stack, so there’s no constraint on the start plug), *or* `*p` (the cable’s start plug) is equal to `*(*(q-1)+2)` (the end plug of the cable just below on the stack). We check for equality by setting `a` to `*(*(q-1)+2)` and `m` to `*p+1` and then decrementing both in a while loop. The `+1` is because `m` is decremented inside the while condition, so it is decremented once more than `a`. If `a` is zero at the end of this, the two plugs are equal.

Thus, if either `*(q-1)` was zero or the equality comparison succeeded, the cable is eligible. Set `*q` to `p` to replace the cable at the top of the stack with the new one; set `m` to the same to indicate that we found a matching cable; and then decrement `p`. That decrement is a little trick to cause the while loop (iterating through the cables) to terminate early; it will increment `p` by 5 again, thus taking it to the cell containing this cable’s “in use” flag, and we know that’s zero because we just checked that. Finally, after the cable-iterating while loop, we check if `m` is non-zero. If so, we found a matching cable and `p` is pointing at the “in-use” flag for that matching cable. Set it to 1 to mark it as in use. Also set `*(*(p-1) ? p+5 : p-5)` to 1 to mark its twin as in use. Finally, increment `q` and set the new `*q` to 1 to create a new stackframe.
3. If, after the cable-iterating while loop, we find `m` to be zero, there are no more matching cables, so we need to backtrack. Decrement `q` to move down the stack and check if it’s still pointing at a cable (a non-zero value). If so, mark that cable and its twin as no longer in use. (We store the value of `*q` in `p` to make this expression shorter in code.)
4. If, after decrementing `q`, we find that it points at a zero value, then that is the “zero terminator”, which means we’ve underrun the stack. We conclude that there is no solution. We set `notdone` to 0 to terminate the main loop.

The third stage is the output stage. There are two things that can happen:

* the main loop found a solution that we need to output, or
* the main loop concluded there is no solution and we output nothing.

Conveniently, if there was *no* solution, `p` is zero because we set it to the value of `*q` before checking that for zero; and if there *was* a solution, `p` is pointing at the “zero terminator” because it just iterated through the cables, so we can now use `p` to iterate through the stack. So just iterate through the stack, outputting for each cable the start plug (`*(*p)`), the hyphens (by decrementing `*(*p+1)` in a while loop; and using the hyphen ASCII code stored in cell #5), and the end plug (`*(*p+2)`). Never mind that this destroys the cable-length information; we don’t need that anymore.

# Answer
> 3 votes
# CJam, 67

```
qN%e!{_,2,m*\f{.{_{"()[]{}<>--"_@#1^=}%W%?}_2ew{~\W=#}%0-{;}&}~}%1<

```

Try it online

Note: the link is using the latest code from the repository (pushed but not yet released), as it contains a bug fix.

**Explanation:**

The program simply tries all permutations and all orientations of the cords.

```
qN%             read the input and split into lines
e!              generate all permutations
{…}%            map each permutation of cords
  _,            get the number of cords (n)
  2,m*          generate all patterns of n bits (cartesian power of [0 1])
  \f{…}         for each bit pattern and the cord permutation
    .{…}        apply the block to each bit and cord (flipping cords for bit 0)
      _         duplicate the cord
      {…}%      map each character of the cord
        "…"_    push the string of all the plugs (and 2 dashes) and duplicate it
        @#      get the index of the character in the string
        1^      XOR with 1
        =       get the character at this new index (plugs get toggled)
      W%        reverse the cord
                 the stack now has the bit, the original cord and the flipped cord
      ?         if the bit is 1, use the original cord, else use the flipped one
    _           duplicate the array of cords
    2ew         get all pairs of adjacent cords
    {…}%        map each pair of cords
      ~\        dump the 2 cords on the stack and swap them
      W=        get the right plug of the first cord
      #         find its position in the second cord (if 0, we have a match)
    0-          remove all the zeros
    {…}&        if the array is not empty (i.e. we have a mismatch)
      ;         pop the array of cords
  ~             dump all the results for this permutation on the stack
                 (to avoid nested arrays)
1<              get the first result (if any) from the array of all results

```

# Answer
> 2 votes
# JavaScript (ES6), 206

Recursive function

```
f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a

```

*More readable*

```
f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>
  l[0]?
  l.some((b,i)=>
     r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])]
     .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)
     &&(l=[...l],l[i]=r,f(l))
    )?r:''
 :a

```

**Test**

```
f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a

console.log=(...x)=>O.textContent+=x+'\n'

;[
 //OK
 ['[-->','{---]','>----{']
,['(-[','}--]']
,['(-)']
,['[--{']
,['[-]',']-[']
,['[----->',')------------[','{--<','}---)']
,['>-->','>->','>--->']
,['(-]',']->','>-}','}-)',')-[','[-<','<-{','{-(']
 //KO
,['[-->','{---]']
,['[-]','[-]']
,['(-]',']->','}-)']
,['>->','>-->',']---]']
,['[-------]',']-------[','[-------]','[---------]'] // shortened a little,
,['{--[',']--}']
].forEach(t=>{
  console.log(t+' : "'+f(t)+'"\n')
})
```

```
<pre id=O></pre>
```

# Answer
> 1 votes
# Javascript, 800 Bytes

Far from an optimized solution, but here's a quick hack together in javascript (no fancy ecma5 or anything, because I don't know it).

```
function a(r){function t(r,t){var n=r.slice();return n.splice(t,1),n}function n(r){var t,n={"[":"]","]":"[",">":"<","<":">","(":")",")":"(","{":"}","}":"{"},e=r.split("").reverse();for(t=0;t<e.length;t++)n.hasOwnProperty(e[t])&&(e[t]=n[e[t]]);return e.join("")}function e(r,t){return r.unshift(t),r}var h,u,f=[];if(1==r.length)return r[0];for(h=0;h<r.length;h++){var l=r[h],i=t(r,h),c=l.charAt(0),g=l.charAt(l.length-1);for(u=0;u<i.length;u++){var o=i[u],s=o.charAt(0),p=o.charAt(o.length-1);c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o)),o=n(o),s=o.charAt(0),p=o.charAt(o.length-1),c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o))}}if(f.length<1)return!1;for(h=0;h<f.length;h++){if(1===f[h].length)return f[h][0];f[h]=a(f[h])}for(h=0;h<f.length;h++)if(f[h]!==!1)return f[h];return!1}
```

Ungolfed, here it is... I'm sure at least 2 for loops are unnecessary here and that checking for a single element input at the top and a single element match at the bottom is stanky... but it seems to work and processes the test inputs.

```
function a(inputs)
{
 var i, ii, matches = [];
 if (inputs.length == 1) {
  return inputs[0];
 }
 // For each of the elements in inputs (e1)
 for (i = 0; i < inputs.length; i++) {
  var e1 = inputs[i],
   others = except(inputs,i),
   e1s = e1.charAt(0),
   e1e = e1.charAt(e1.length-1);
  // Compare to each of the other elements in inputs (e2)
  for (ii = 0; ii < others.length; ii++) {
   // get the start and end of the elements to compare (e1s,e1e,e2s,e2e)
   var e2 = others[ii],
    e2s = e2.charAt(0),
    e2e = e2.charAt(e2.length-1);
   // if any of them match up (e1s == e2e || e1s == e2s || e1e == e2s || e1e = e2e)
   // Make a new array of inputs containing the joined elements (as a single element) and all other elements which might join with them
   if (e1s == e2e) {
    matches.push(addTo(except(others,ii),e2+e1));
   }
   if (e1e == e2s) {
    matches.push(addTo(except(others,ii),e1+e2));
   }
   e2 = flip(e2);
   e2s = e2.charAt(0);
   e2e = e2.charAt(e2.length-1);
   if (e1s == e2e) {
    matches.push(addTo(except(others,ii),e2+e1));
   }
   if (e1e == e2s) {
    matches.push(addTo(except(others,ii),e1+e2));
   }
  }
 }

 if (matches.length < 1) {
  return false;
 }

 for (i = 0; i < matches.length; i++) {
  if (matches[i].length  === 1) {
   return matches[i][0];
  } else {
   matches[i] = a(matches[i]);
  }
 };

 for (i = 0; i < matches.length; i++) {
  if (matches[i] !== false) {
   return matches[i];
  }
 };

 return false;

 function except(list,idx)
 {
  var newList = list.slice();
  newList.splice(idx,1);
  return newList;
 }
 function flip(s) {
  var replacements = {
   '[':']',
   ']':'[',
   '>':'<',
   '<':'>',
   '(':')',
   ')':'(',
   '{':'}',
   '}':'{'
  }, i, a = s.split('').reverse();
  for (i = 0; i < a.length; i++) {
   if (replacements.hasOwnProperty(a[i])) {
    a[i] = replacements[a[i]];
   }
  }

  return a.join('');
 }
 function addTo(arr,newEl)
 {
  arr.unshift(newEl);
  return arr;
 }
}
```

# Answer
> 1 votes
# Python 3, 217 bytes

```
from itertools import*
a='()[]{}<>'
all(any(c[-1]!=d[0]for c,d in zip(q,q[1:]))or print(''.join(q))for p in permutations(open(0))for q in product(*[(c[:-1],a[a.find(c[-2])^1]+c[-3:0:-1]+a[a.find(c[0])^1])for c in p]))

```

(Demo on Ideone)

# Answer
> 0 votes
# Python 3.5, 448 432 427 424 286 311 bytes:

(*+25 since there was a bug where the output may be longer than it should be for some inputs*)

```
def g3(z):
 B=z.split();M='i[::-1].translate({41:40,40:41,125:123,123:125,62:60,60:62,93:91,91:93})';f=B+[eval(M)for i in B if eval(M)not in B];d=[f.pop(0)]
 for h in d:
  try:[d.append([f.pop(f.index(c))for c in f if h[-1]==c[0]][0])if len(d)<len(B)else E]
  except:break
 return''.join(d)if len(d)>=len(B)else''

```

Works perfectly! *except* for inputs with 7 or more values. It takes a **long** time for those, most likely because it must go through all those permutations of the input plus the input *reversed*. I will try to fix this if and when I can, but for now, this seems to be good enough. All is good now! If *only* I could somehow use that `try-except` block in list comprehension, it could be a little shorter, and look **much** nicer. Nonetheless, it now works for **all** the test cases, and, best of all, it uses *no* imports! :)

Try it online! (Ideone) (284 bytes here)

(Tip: To try it, just select "fork", and then input your choices, *space-separated*, and select "run")

# Explanation

Basically, what's happening is...

1. A list, `B`, is created from the input by splitting it at the whitespace into its component "cords".
2. `M` is a string I created which, when evaluated, returns a list based on `B` which contains all the cords, but this time *backwards*.
3. The list created from `M` is ultimately concatenated with `B` itself to create a list, `f`, with all possible orientations of the "cords".
4. Another list, `d` is created, which will be initialized with the first value (value `f[0]`) of `f`.
5. Finally, all the values in `d` are iterated through, and each value's last character is compared with the first character of each element in `f`, and when a match is found, that character is popped (or removed) and returned from list `f`. This happens until a `IndexError` is raised, or the length of list `d` exceeds `B` and a `NameError` is raised after the call to `E`,both of which are handled, and then list `d`'s contents are joined into a string and returned as long as the length of list `d` is more than or equal to the length of list `B`. Otherwise, an empty string is returned (`''`), since `d` not being the same length as `B` signifies that all the "cords" in list `B` cannot be joined into one long "cord".

# Answer
> 0 votes
# Lua, 477 bytes

```
function r(s)return s:reverse():gsub("[()%[%]{}<>]",{["("]=")",[")"]="(",["["]="]",["]"]="[",["{"]="}",["}"]="{",["<"]=">",[">"]="<"})end
function a(c,b)for i, v in next,b do
m=c:sub(-1,-1)n=v:sub(1,1)o=r(c):sub(-1,-1)p=r(v):sub(1,1)l=table.remove(b,i)if m==n then
return a(c..v,b)elseif o==n then
return a(r(c)..v,b)elseif m==p then
return a(c..r(v),b)elseif o==p then
return a(r(c)..r(v),b)end
table.insert(b,i,l)end
return#b>0 and""or c
end
print(a(table.remove(arg,1),arg))

```

Accepts cords as command line arguments

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


title: Identify the Conic Section

text:
# Question
Title: Identify the Conic Section
Given 5 distinct points on a two-dimensional plane, determine the type of conic section formed by the points. The output shall be one of `circle`, `hyperbola`, `ellipse`, or `parabola`.

### Rules

* The points will be in general linear position, meaning that no three points are collinear, and thus the conic passing through them will be unique.
* The coordinates of the 5 points will be decimal numbers between -10 and 10, inclusive.
* The precision for the decimal/float values should be the precision of your language's native float/decimal type. If your language/data type is arbitrary-precision, you may use 12 digits after the decimal point as the maximum required precision, rounding toward zero (e.g. `1.0000000000005 == 1.000000000000`).
* Capitalization of the output does not matter.
* Outputting `ellipse` when the conic section is actually a circle is not allowed. All circles are ellipses, but you must output the most specific one.

On floating point inaccuracies and precision:

> I'm trying to make this as simple as possible, so that issues with floating point inaccuracies don't get in the way. The goal is, if the data type was "magical infinite precision value" instead of float/double, then everything would work perfectly. But, since "magical infinite precision value" doesn't exist, you write code that assumes that your values are infinite precision, and any issues that crop up as a result of floating point inaccuracies are features, not bugs.

### Test Cases

```
(0, 0), (1, 5), (2, 3), (4, 8), (9, 2) => hyperbola
(1.2, 5.3), (4.1, 5.6), (9.1, 2.5), (0, 1), (4.2, 0) => ellipse
(5, 0), (4, 3), (3, 4), (0, 5), (0, -5) => circle
(1, 0), (0, 1), (2, 1), (3, 4), (4, 9) => parabola

```

# Answer
# Matlab, 154 bytes

```
p=input();c=null([p.^2 prod(p,2) p 1+p(:,1)*0]),s={'circle' 'ellipse' 'parabola' 'hyperbola'};s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

```

Saved some bytes thanks to Suever's suggestions.

Takes input as `[x1 y1;x2 y2;x3 y3; etc]`. This used a Vandermonde matrix, and finds the basis of its null space, which will always be a single vector. Then it calculates the discriminant and uses it to make an index between 1 and 4 which is used to get the string.

Ungolfed:

```
p=input();
c=null([p.^2 prod(p')' p ones(length(p),1)]);
s={'circle' 'ellipse' 'parabola' 'hyperbola'};
s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

```

The `sign(...)` part calculates the discriminant, giving 1 if it's positive (hyperbola), -1 if it's negative (ellipse), and 0 if it's 0 (parabola). The `max(...)` subtracts 1 away if it is a circle. Matlab arrays are one-indexed, so add 3 to give values 1, 2, 3, 4, and use that to index the array of conic section names.
> 1 votes

# Answer
# JavaScript (ES6), 316 ~~323 347~~

```
p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'

```

Any language better suited for handling matrix and determinant should score better (APL, J, CJAM, Jelly)

References: General form of a conic, Five points determine a conic, System of linear equations, Determinant

In the cartesian plane, the general equation of a conic is

```
A*x*x + B*x*y + C*y*y + D*x + E*y + F = 0

```

having A or B or C not equal to 0 (otherwise it's a straight line)

A ... F are six unknowns to be found. With five pairs of (x,y) we can build a linear system with five equations, and scaling remove one dimension. That is, we can set one of A,B or C to 1 if it's not 0 (and we know that at least one is not 0).

I build and try to solve 3 systems: first trying A=1. If not solvable then B=1, then C. (There could be a better way, but that's my best at the time)

Having the values of A,B,C we can classify the conic looking at the discriminant `d=B*B-4*A*C`

* d == 0 -\> parabola
* d \> 0 -\> hyperbola
* d \< 0 -\> ellipse, particularly (A == C and B == 0) -\> circle

**Less golfed**

```
F=p=>(
  // Recursive function to find determinant of a square matrix
  D=m=>m[1]
    ?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0)
    :m,
  // Try 3 linear systems, coefficients in Q
  // Five equation made from the paramaters in p
  // And a first equation with coefficient like k,0,0,0,0,0,1 (example for A)
  [1,2,4].some(
    x => (
      // matrix to calc the determinant, last coefficient is missing at this stage
      Q = [
        [x&1, x&2, x&4, 0,0,0] // first one is different
        // all other equations built from the params
        ,...p.map( ([x,y]) => [x*x, x*y, y*y, x, y, 1] )
      ],
      d = D(Q), // here d is the determinant
      d && ( // if solvable  then d != 0
        // add missing last coefficient to Q
        // must be != 0 for the first row, must be 0 for the other
        Q.map( r=> (r.push(x), x=0) ),
        // solve the system (Cramer's rule), I get all values for A...F but I just care of a,b,c
        [a,b,c] = Q.map((v,i)=>D(Q.map(r=>(r=[...r],r[i]=r.pop(),r))) / d),
        d = b*b - 4*a*c, // now reuse d for discriminant
        d = d<0 ? !b&c==a ? 'Circle' : 'Ellipse' // now reuse d for end result
        : d ? 'Hyperbola' : 'Parabola'
      ) // exit .some if not 0
    ), d // .some exit with true, the result is in d
  )
)

```

**Test**

```
F=p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'

console.log=(...x)=>O.textContent+=x+'\n'

;[
 [[0, 0], [1, 5], [2, 3], [4, 8], [9, 2]]
,[[1.2, 5.3],[4.1, 5.6], [9.1, 2.5], [0, 1], [4.2, 0]]
,[[5, 0], [4, 3], [3, 4], [0, 5], [0, -5]]
,[[1, 0], [0, 1], [2, 1], [3, 4], [4, 9]]
].forEach(t=>console.log(t.join`|`+' => '+F(t)))
```

```
<pre id=O></pre>
```
> 13 votes

# Answer
# Python - 234 bytes

```
import numpy as n
x=input()
d=[n.linalg.det(n.delete(n.array([[i*i,i*j,j*j,i,j,1]for i,j in x]),k,1))for k in range(6)]
t=d[1]**2-4*d[0]*d[2]
print"hyperbola"if t>0else"parabola"if t==0else"circle"if d[1]==0and d[0]==d[2]else"ellipse"

```

I never print `circle` or `parabola` because `t` and `d[1]` never hit exactly `0`, but OP said that was okay.
> 1 votes

# Answer
# C, 500

My JavaScript answer ported to C. Just to see if it can be done.

Usage: read 10 values from standard input

> echo 1 0 0 1 2 1 3 4 4 9 | conic

Output:

> Parabola

Test (ideone)

```
double D(m,k)double*m;{double t=0;for(int s=1,b=1,x=0;x<6;x++,b+=b)k&b||(t+=s*m[x]*(k+b>62?1:D(m+6,k+b)),s=-s);return t;}i,u,h;double m[36],*t=m+6,w[6],s[3],b,d;main(){for(;i++<5;*t++=d*d,*t++=d*b,*t++=b*b,*t++=d,*t++=b,*t++=1)scanf("%lf%lf",&d,&b);for(u=4;u;u/=2)for(m[0]=u&1,m[1]=u&2,m[2]=u&4,d=D(m,0),h=0;d&&h<3;h++){for(i=0;i<6;i++)w[i]=m[i*6+h],m[i*6+h]=i?0:u;s[h]=D(m,0)/d;for(;i--;)m[i*6+h]=w[i];}b=s[1];d=b*b-4*s[0]*s[2];puts(d?d<0?!b&(s[2]==s[0])?"Circle":"Ellipse":"Hyperbola":"Parabola");}

```

**Less golfed**

```
// Calc determinant of a matrix of side d
// In the golfed code, d is fix to 6
double D(m, d, k)
double*m;
{
    int s = 1, b = 1, x = 0;
    double t = 0;
    for (; x < d; x++, b += b)
        k&b || (
            t += s*m[x] *(k+b+1==1<<d? 1: D(  m + d, d, k + b)), s = -s
        );
    return t;
}

double m[36],d, *t = m + 6, w[6], s[3], a, b, c;
i,u,h;
main()
{
    for (; i++ < 5; )
    {
        scanf("%lf%lf", &a, &b);
        *t++ = a*a, *t++ = a*b, *t++ = b*b, *t++ = a, *t++ = b, *t++ = 1;
    }
    for (u = 4; u; u /= 2)
    {
        m[0] = u & 1, m[1] = u & 2, m[2] = u & 4;
        d = D(m, 6, 0);
        if (d)
            for (h = 0; h < 3; h++)
            {
                for (i = 0; i < 6; i++)
                    w[i] = m[i * 6 + h],
                    m[i * 6 + h] = i ? 0 : u;
                s[h] = D(m, 6, 0)/d;
                for (; i--; )
                    m[i * 6 + h] = w[i];
            }
    }
    a = s[0], b = s[1], c = s[2];
    d = b*b - 4 * a * c;
    puts(d ? d < 0 ? !b&(c == a) ? "Circle" : "Ellipse" : "Hyperbola" : "Parabola");
}

```
> 1 votes

# Answer
## Sage, 247 bytes

```
def f(p):
 for i in[1,2,4]:
  z=[i&1,i&2,i&4,0,0,0]
  M=matrix([z]+[[x*x,x*y,y*y,x,y,1]for x,y in p])
  try:A,B,C=(M\vector(z))[:3]
  except:continue
  d=B*B-4*A*C
  return['parabola','hyperbola','circle','ellipse'][[d==0,d>0,d<0and B==0and A==C,d<0].index(1)]

```

Try it online

This function takes an iterable of `(x,y)` pairs as input, tries computing the discriminant of each of the 3 possible linear systems (`A=1`, `B=1`, and `C=1`), and outputs the type of conic section based on the values of the discriminant, `A`, `B`, and `C`.

There's probably some more golfing to be done, but I'm rusty with Sage and sleepy right now, so I'll work on it more in the morning.
> 1 votes

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


# Question
Title: Federal income tax calculator for procrastinators
Today is Tax Day!

Oops.

Well, today is tax day if you are a resident of Maine or Massachusetts.

So you're probably still completing your return and need a calculator for when you get to Line 44.

Given an input of taxable income (US$, accurate to 2 decimal places) and a string representing filing status, output the amount of tax (also US$ to 2 decimal places).

Filing status will be one of `S`, `MFJ`, `QW`, `MFS`, or `HH` for Single, Married Filing Jointly, Qualified Widow(er), Married Filing Separately or Head of Household, respectively.

### Example Inputs:

```
0.00 S
10000.00 MFJ
100000.00 MFS
1000000.00 QW

```

### Example Outputs corresponding to above inputs:

```
0.00
1000.00
21525.75
341915.90

```

---

# Summary of tax tables.

### Married Filing Jointly and Qualified Widow(er)

> `Income Interval Tax
>  [ $0, $18450] 10%
>  ( $18450, $74900] $1845 + 15% of the excess over $18450
>  ( $74900, $151200] $10312.50 + 25% of the excess over $74900
>  ($151200, $230450] $29387.50 + 28% of the excess over $151200
>  ($230450, $411500] $51577.50 + 33% of the excess over $230450
>  ($411500, $464850] $111324 + 35% of the excess over $411500
>  ($464850, $∞] $129996.50 + 39.6% of the excess over $464850`

### Head of Household

> `Income Interval Tax
>  [ $0, $13150] 10%
>  ( $13150, $50200] $1315 + 15% of the excess over $13150
>  ( $50200, $129600] $6872.50 + 25% of the excess over $50200
>  ($129600, $209850] $26722.50 + 28% of the excess over $129600
>  ($209850, $411500] $49192.50 + 33% of the excess over $209850
>  ($411500, $439000] $115737 + 35% of the excess over $411500
>  ($439000, $∞] $125362 + 39.6% of the excess over $439000`

### Single

> `Income Interval Tax
>  [ $0, $9225] 10%
>  ( $9225, $37450] $922.50 + 15% of the excess over $9225
>  ( $37450, $90750] $5156.25 + 25% of the excess over $37450
>  ( $90750, $189300] $18481.25 + 28% of the excess over $90750
>  ($189300, $411500] $46075.25 + 33% of the excess over $189300
>  ($411500, $413200] $119401.25 + 35% of the excess over $411500
>  ($413200, $∞] $119996.25 + 39.6% of the excess over $413200`

### Married Filing Separately

> `Income Interval Tax
>  [ $0, $9225] 10%
>  ( $9225, $37450] $922.50 + 15% of the excess over $9225
>  ( $37450, $75600] $5156.25 + 25% of the excess over $37450
>  ( $75600, $115225] $14693.75 + 28% of the excess over $75600
>  ($115225, $205750] $25788.75 + 33% of the excess over $115225
>  ($205750, $232425] $55662 + 35% of the excess over $205750
>  ($232425, $∞] $64998.25 + 39.6% of the excess over $232425`

# Answer
## Python 3, ~~427~~ ~~382~~ ~~317~~ ~~309~~ ~~308~~ 275 bytes

*-45 bytes by figuring ternary expression out (wow that's a long line); thanks Maltysen*

*-65 bytes, now with iteration for DRYer code!*

*-8 bytes by in-lining tuple variables; thanks Majora*

*-1 byte by using a dict rather than ternary chain; thanks again Maltysen*

*-33 bytes by reusing `MFS` step as half of `MFJ`/`QW` and calculating tax an order of magnitude larger; thanks Neil*

```
def f(i,s):
 t=i;k={'MFS':(9225,28225,38150,39625,90525,26675),'S':(9225,28225,53300,98550,222200,1700),'HH':(13150,37050,79400,80250,201650,27500)}
 for x in range(6):
  i-=k[s][x]if s in k else k['MFS'][x]*2
  if i>0:t+=(.5,1,.3,.5,.2,.46)[x]*i
 return'{:.2f}'.format(t*.1)

```

If I had been thinking I would have made the function signature `t(a,x)`, but I guess I'll stick with `f`unction(`i`ncome, `s`tatus).

When code is barely undertstood by the writer, is that when you win at golf?
> 5 votes

# Answer
## JavaScript (ES6), 223 bytes

```
(i,s)=>(({MFS:a=[x=9225,y=28225,38150,39625,90525,26675],S:[x,y,53300,98550,222200,1700],HH:[13150,37050,79400,80250,201650,27500]}[s]||a.map(b=>b*2)).reduce((t,b,j)=>t+((i-=b)>0&&i*[.5,1,.3,.5,.2,.46][j]),i)*.1).toFixed(2)

```

Basically a port of CAD97's Python answer, but I saved 4 bytes by multiplying the tax by 10 during the calculation and 11 bytes by reducing the duplication in the tax bands.
> 1 votes

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


# Question
Title: Are there More Hard Objects or Soft Objects
*Tangentially inspired by the opening to the What-If book.*

The input is a rectangle of spaces as a string, list of string, etc., with objects made of `#`'s inside:

```
########
#      #
########

   ###        ####
   ###        ####
   ###

```

The objects will always be non-intersecting, non-touching, rectangles. A soft object is defined as an object that isn't filled up with `#`'s in the middle and is only a border, a hard object is one that is filled up. An object with width or height `<=2` is considered hard. All objects are either hard or soft.

If there are more hard objects in the input, output `"Hard"`, if more soft, output `"Soft"`, if they are equal, output `"Equal"`.

This is , so shortest code in **bytes** wins!

# Test Cases

**These cases aren't full inputs, but rather what each object should be characterized as.** The actual input will be like the ascii-art at the top of the question.

## Hard

```
#

####

##
##

##########
##########
##########

```

## Soft

```
###
# #
###

###################
#                 #
#                 #
#                 #
###################

####
#  #
#  #
#  #
#  #
#  #
#  #
#  #
####

```

## Actual Test Cases

```
########
#      #
########

   ###        ####
   ###        ####
   ###

Hard

###
###
###

###################
#                 #
#                 #
#                 #
###################

Equal

   ######
   #    #
   ######
          ###
   ##  #  # #
          ###

 ########
 #      #
 ########

Soft

```

# Answer
> 8 votes
# MATL, ~~105~~ ~~104~~ ~~58~~ ~~50~~ 49 bytes

*Thanks to @Neil for a suggestion that allowed me to remove 46 bytes!*

```
2\TTYaEq4:HeqgEqZ+K/Zot0>+ss'Soft Hard Equal'Ybw)

```

Input is a 2D char array, with rows separated by `;`. The example in the challenge is

```
['########          ';'#      #          ';'########          ';'                  ';'   ###        ####';'   ###        ####';'   ###            ']

```

Here's another example:

```
['###                ';'###                ';'###                ';'                   ';'###################';'#                 #';'#                 #';'#                 #';'###################']

```

This corresponds to

```
###
###
###

###################
#                 #
#                 #
#                 #
###################

```

and thus should give `'Equal'`.

As a third example, corresponding to `'Soft'`,

```
['   ######    ';'   #    #    ';'   ######    ';'          ###';'   ##  #  # #';'          ###';'             ';'             ';' ########    ';' #      #    ';' ########    ']

```

that is,

```
   ######
   #    #
   ######
          ###
   ##  #  # #
          ###

 ########
 #      #
 ########

```

**Try it online!**

### Explanation

This uses 2D convolution to detect shapes. The input is converted to a 2D array with `1` indicating `#` and `-1` for space; and is padded with a frame of `-1` values. This assures that shapes at the edge of the original field are also detected.

A *soft object* is detected by the mask

```
 1   1
 1  -1

```

which corresponds to the object's upper-left corner with one empty interior point. Note that the convolution inverts the mask, so it is defined as `[-1 1; 1 1]` in the code. The number *S* of positions in which the convolution equals `4` is the total number of soft objects.

An *object* (soft or hard) is detected by the mask

```
-1  -1
-1   1

```

which correponds to the object's upper-left corner together with some empty exterior points. This mask is the negated version of the previous one, so the previous convolution result can be reused. Specifically, the number *T* of positions in which that result equals `-4` is the total number of objects.

The number *H* of hard objects is *T**S*. The output string is determined by the sign of *S**H* = 2\**S**T*.

```
2\                 % Input. Modulo 2: '#' gives 1, ' ' gives 0
TTYa               % Add a frame of zeros
Eq                 % Convert 0 to -1
4:HeqgEq           % Generate mask [-1 1; 1 1], for soft objects
Z+                 % 2D convolution, preserving size
K/Zo               % Divide by 4 and round towards 0. Gives 1 or -1 for 4 or -4
t0>                % Duplicate. 1 for positive entries (soft objects), 0 otherwise
+                  % Add. This corresponds to the factor 2 that multiplies number S
ss                 % Sum of 2D array. Gives 2*S-T
'Soft Hard Equal'  % Push this string
Yb                 % Split by spaces. Gives cell array
w)                 % Swap. Apply (modular) index to select one string

```

# Answer
> 6 votes
# JavaScript (ES6), ~~123~~ ~~121~~ 118 bytes

```
s=>s.replace(/#+/g,(m,i)=>s[i+l]>" "?0:n+=!m[1]|s[i-l+1]==s[i-l]||-1,n=l=~s.search`
|$`)|n>l?"Hard":n<l?"Soft":"Equal"

```

*Saved 2 bytes thanks to @edc65!*

Takes input as a multiline string padded with spaces to form a grid.

## Explanation / Test

~~Very close to MATL length!~~ Basically, it searches for the top line of `#`s of each object, and if the length of the top line is less than 2 or the first 2 characters below the top line are the same, it is hard, otherwise soft.

```
var solution =

s=>
  s.replace(/#+/g,(m,i)=>        // for each run of consecutive # characters
    s[i+l]>" "?                  // if the position above the match contains a #
      0                          // do nothing (this object has already been counted)
    :n+=                         // add 1 to the counter (hard) if
      !m[1]                      // the match is only 1 # wide
      |s[i-l+1]==s[i-l]          // or the characters below are the same
      ||-1,                      // else decrement the counter (soft)
    n=                           // n = counter, hard objects increase n, soft decrease
    l=~s.search`\n|$`            // l = (negative) line length
  )
  |n>l?"Hard":n<l?"Soft":"Equal" // return the result string

// Test
document.write("<pre>" + [`

########
#      #
########

   ###        ####
   ###        ####
   ###

`,`

###
###
###

###################
#                 #
#                 #
#                 #
###################

`,`

   ######
   #    #
   ######
          ###
   ##  #  # #
          ###

 ########
 #      #
 ########

`,`

########
#      #
########

   ###        ####
   # #        ####
   ###

`,`

########
#      #
########

   ###  ###   ####
   ###  # #   ####
   ###  ###

`,`

#

`,`

##

`,`

#
#

`,`

###
# #
###

`].map((test) => solution(test.slice(2, -2))).join("\n")
)
```

# Answer
> 4 votes
# Jelly, ~~50~~ ~~49~~ ~~46~~ ~~43~~ ~~38~~ ~~34~~ ~~33~~ 32 bytes

```
Ḥ+ḊZ
>⁶ÇÇFµċ7_ċ4$Ṡị“¤Ỵf“¢*ɦ“¡⁺ƒ»

```

Try it online! or verify all test cases.

### Background

There are **16** different **2×2** patterns of blocks and spaces:

```
|  |  |  | #|  | #| #|# | #|# |# |##|# |##|##|##|
|  | #|# |  |##| #|# |  |##| #|# |  |##| #|# |##|

```

Of these, since two objects will never touch,

```
| #|# |
|# | #|

```

will never occur in the input, leaving us with **14** possible patterns.

Assigning  a value of **0** and `#` a value of **1**, we can encode a **2×2** pattern

```
|ab|
|cd|

```

as **2(2a + c) + (2b + d) = 4a + 2b + 2c + d**, leaving the following values for the **14** patterns.

```
|  |  |  | #|  | #|# | #|# |##|# |##|##|##|
|  | #|# |  |##| #|  |##|# |  |##| #|# |##|
  0  1  2  2  3  3  4  5  6  6  7  7  8  9

```

For partial **2×1**, **1×2** or **1×1** patterns at the lower and/or right border, we'll treat them as if the were padded with spaces, encoding them as **4a + 2b**, **4a + 2c** and **4a**, respectively.

This way, each object (soft or hard) will have exactly one **4** pattern (its lower right corner); each soft object will have exactly two **7** patterns (its lower left and its upper right corner).

Thus, subtracting the amount of **4** patterns from the number of **7** patterns encountered in the input will yield **(s + h) - 2s = h - s := d**, where **h** and **s** are the amount of hard and soft objects they form.

We print *Hard* if **d \> 0**, *Soft* if **d \< 0** and *Equal* if **d = 0**.

### How it works

```
Ḥ+ḊZ                         Helper link. Input: M (n×m matrix)

Ḥ                            Unhalve; multiply all entries of M by 2.
  Ḋ                          Dequeue; remove the first row of M.
 +                           Perform vectorized addition.
                             This returns 2 * M[i] + M[i + 1] for each row M[i].
                             Since the M[n] is unpaired, + will not affect it,
                             as if M[n + 1] were a zero vector.
   Z                         Zip; transpose rows with columns.

>⁶ÇÇFµċ7_ċ4$Ṡị“¤Ỵf“¢*ɦ“¡⁺ƒ»  Main link. Input: G (character grid)

>⁶                           Compare each character with ' ', yielding 1 for '#'
                             and 0 for ' '.
  Ç                          Call the helper link.
                             This will compute (2a + c) for each pattern, which is
                             equal to (2b + d) for the pattern to its left.
   Ç                         This yields 2(2a + c) + (2b + d) for each pattern.
    F                        Flatten; collect all encoded patterns in a flat list.

     µ                       Begin a new, monadic link. Argument: A (list)
      ċ7                     Count the amount of 7's.
         ċ4$                 Count the amount of 4's.
        _                    Subtract the latter from the former.
            Ṡ                Yield the sign (1, -1 or 0) of the difference.
              “¤Ỵf“¢*ɦ“¡⁺ƒ»  Yield ['Hard', 'Soft', Equal'] by indexing into a
                             built-in dictionary.
             ị               Retrieve the string at the corresponding index.

```

# Answer
> 1 votes
# Julia, ~~99~~ ~~95~~ 93 bytes

```
~=t->2t'+[t[2:end,:];0t[1,:]]'
!x=("Hard","Equal","Soft")[sign(~~(x.>32)∩(4,7)-5.5|>sum)+2]

```

`!` expects a two-dimensional Char array as argument. Try it online!

### How it works

This uses almost exactly the same idea as my Jelly answer, with one improvement:

Instead of counting the amount of **4**'s and **7**'s, we remove all other numbers, then subtract **5.5** to map **(4, 7)** to **(-1.5, 1.5)**. This way, the sign of the sum of the resulting differences determines the correct output.

# Answer
> 0 votes
# TSQL, ~~328~~ 249 bytes

Declaring variables and test data:

```
DECLARE @l int = 20
DECLARE @ varchar(max)=''
SELECT @+=LEFT(x + replicate(' ', @l), @l)
FROM (values
(' xxxx'),
(' xxxx'),
(' xxxx'),
('x'),
(''),
('xxx'),
('x x  xxx'),
('xxx  x x'),
('     xxx    ')) x(x)

```

Code:

```
SELECT substring('Soft EqualHard',sign(sum(iif(substring(@,N,@l+2)like'xx'+replicate('_', @l-2)+'x ',-1,1)))*5+6,5)FROM(SELECT row_number()OVER(ORDER BY Type)N FROM sys.all_objects)x WHERE n<=len(@)AND' x'=substring(@,N-1,2)AND''=substring(@,N-@l,1)

```

Code deflated:

```
SELECT
  substring('Soft EqualHard',
    sign(sum(iif(substring(@,N,@l+2)like'xx'+replicate('_', @l-2)+'x ',-1,1)))*5+6,5)
FROM(SELECT row_number()OVER(ORDER BY Type)N FROM sys.all_objects)x
WHERE n<=len(@)AND' x'=substring(@,N-1,2)AND''=substring(@,N-@l,1)

```

Explaination:

Script is scanning the text for the pattern:

```
      space
space x

```

Each of those is the start of a box

For those positions, the script is then checking for the pattern, don't need to check for first x:

```
  x
x space

```

When that exists it is a soft object, otherwise it is a hard object.

---
Tags: code-golf, ascii-art, counting
---


# Question
Title: Solve a quadratic equation using Vieta's formulas
# Exposition

Your mathematics teacher is a big fan of Vieta's formulas, and he believes that you should use them to solve quadratic equations. Given the equation

```
ax^2 + bx + c = 0

```

the product of its roots is `c/a`, and their sum is `-b/a`. When all of `a`, `b` and `c` are nonzero integers, **assuming the roots are rational numbers**, it's enough to try all possible numbers in the form

```
r1 = ±s/t

```

where `s` is a divisor of `abs(c)`, and `t` is a divisor of `abs(a)`. For each such `r1`, plug it into `ax^2 + bx + c`, and see whether the result is 0. If yes, then `r1` is a root. The second root is `-b/a-r1` or `(c/a)/r1` \- you can choose whatever formula you like.

Your teacher decided to give you many exercises, and he expects you to describe how you used Vieta's formulas to solve each one. Each exercise looks like this (example):

```
9x^2+12x+4=0

```

Write a subroutine or a program that gets an exercise as input, and outputs your alleged "solving process" to appease your teacher.

---

# Input

Since you will feed the exercise to your program manually, format it in any convenient form. For example, use space-separated values on `stdin`:

```
9 12 4

```

or call a function with 3 parameters:

```
SolveExercise(9, 12, 4);

```

or parse the exercise literally:

```
9x^2+12x+4=0

```

Your output should be formatted as described below. Use the standard output device or return it as a string from your subroutine.

# Output (example)

```
x = 1? 9x^2+12x+4 = 25
x = 2? 9x^2+12x+4 = 64
x = 1/3? 9x^2+12x+4 = 9
x = 2/3? 9x^2+12x+4 = 16
... (as many or as few failed attempts as you like)
x = -2/3? 9x^2+12x+4 = 0
r1 = -2/3
r2 = -12/9-(-2/3) = -2/3

```

Alternatively, the last line can be:

```
r2 = 4/9/(-2/3) = -2/3

```

---

Some additional notes:

* The minimum number of line-breaks in the output is as described in the example (trailing line-break is not required). Additional line-breaks are permitted.
* All coefficients in input are integers in the range \[-9999...9999\], none can be equal to 0
* All roots are rational numbers, and should be output as such - e.g. `0.66666667` is not equal to `2/3` and so is incorrect
* In the final expressions for `r1` and `r2`, integers should be output as such, e.g. `-99/1` is unacceptable, and should be output as `-99`; in other places in the output, denominator equal to ±1 is acceptable
* Reduced form for rational numbers is not required - e.g. `2/4` is a good substitute for `1/2`, even though it's ugly, even for roots `r1` and `r2`
* Parentheses in the output are sometimes required by rules of mathematics, e.g. in the expression `12/9/(2/3)`. When precedence rules of mathematics permit omission of parentheses, they are not required, e.g. `-12/9--2/3`. Superfluous parentheses are permitted: `4-(2)` is OK, even though it's ugly
* There should be at least one case (input) for which your program tries 3 or more *non-integer* values for `r1`; however, it's allowed to "guess the right answer" almost always on the first try
* All trial values for `r1` must be rational numbers `±s/t`, where `s` and `t` are constrained as described above

---

# Test cases

1. Input

```
x^2-x-2=0

```

or

```
1 -1 -2

```

Possible output

```
x=1? x^2-x-2=-2
x=-1? x^2-x-2=0
r1=-1
r2=-2/1/-1=2

```
2. Input

```
-x^2+2x-1=0

```

or

```
-1, 2x, -1

```

Possible output

```
x=1? -x^2+2x-1=0
r1=1
r2=-2/-1-1=1

```
3. Input

```
7x^2-316x+924=0

```

or

```
X(7, -316, 924);

```

Possible output (a divisor of 924 is 42, which solves the equation by "luck")

```
x=42? 7x^2-316x+924=0
r1=42
r2=316/7-42=22/7

```
4. Input

```
6x^2-35x-6=0

```

or

```
[6 -35 -6]

```

Possible output (even though your program may "know" that 6 is a root, it decides to show some failed trials)

```
x=1/2? 6x^2-35x-6=-88/4
x=1/3? 6x^2-35x-6=-153/9
x=3/2? 6x^2-35x-6=-180/4
x=6/1? 6x^2-35x-6=0
r1=6
r2=35/6-6=-1/6

```

Alternative versions for the last line:

```
r2=--35/6-6=-1/6
r2=-6/6/6=-1/6

```
5. Impossible input (no rational solutions)

```
x^2+5x+1=0

```
6. Impossible input (zero coefficient)

```
x^2-1=0

```

# Answer
> 1 votes
# Python - ~~202~~ 200 bytes

*2 bytes saved thanks to @FryAmTheEggman.*

```
from fractions import*;f=Fraction
lambda a,b,c:"\n".join(["x=%s?%dx^2+%dx+%d=%s"%(i,a,b,c,a*i*i+b*i+c)for i in[f(1,a),f(-1,a),f(c,a)]]+["r%d=%s"%((3-i)/2,f(i*(b*b-4*a*c)**.5-b)/f(2*a))for i in[1,-1]])

```

# Answer
> 1 votes
# JavaScript (ES6), 373

```
(a,b,c,z='',A=Math.abs,M=(c,x,a)=>'-+'[c>0|0]+(x&&a<2?x:a+x),G=(a,b)=>b?G(b,a%b):a,O=(n,d,g=G(n,d))=>(g=d*g<0?-g:g)-d?n/g+'/'+d/g:n/d,e=M(a,'x^2',o=A(a))+M(b,'x',A(b))+M(c,'',q=A(c)),K=s=>(z+=`
x=${s}/${t}? ${e}=`+(v=a*s*s+b*s*t+c*t*t)+(v?'':`
r1=${O(s,t)}
r2=(${c}/${a})/(${s}/${t})=`+O(c*t,s*a)),v))=>{for(s=0;++s<=q;)for(t=0;++t<=o;)if(!(q%s||o%t||K(-s)&&K(s)))return z}

```

**Test**

```
f=(a,b,c,z='',A=Math.abs,M=(c,x,a)=>'-+'[c>0|0]+(x&&a<2?x:a+x),G=(a,b)=>b?G(b,a%b):a,O=(n,d,g=G(n,d))=>(g=d*g<0?-g:g)-d?n/g+'/'+d/g:n/d,e=M(a,'x^2',o=A(a))+M(b,'x',A(b))+M(c,'',q=A(c)),K=s=>(z+=`
x=${s}/${t}? ${e}=`+(v=a*s*s+b*s*t+c*t*t)+(v?'':`
r1=${O(s,t)}
r2=(${c}/${a})/(${s}/${t})=`+O(c*t,s*a)),v))=>{for(s=0;++s<=q;)for(t=0;++t<=o;)if(!(q%s||o%t||K(-s)&&K(s)))return z}

// Less golfed
U=(a,b,c,
   // locals
   z='',
   A=Math.abs,
   M=(c,x,a)=>'-+'[c>0|0]+(x&&a<2?x:a+x),
   G=(a,b)=>b?G(b,a%b):a, // GCD
   O=(n,d,g=G(n,d))=>(g=d*g<0?-g:g)-d?n/g+'/'+d/g:n/d, // output a fraction
   o=A(a),q=A(c),
   e=M(a,'x^2',o)+M(b,'x',A(b))+M(c,'',q), // espression from coefficients
   K=s=>( // check & output a candidate solution
      z+=`\nx=${s}/${t}? ${e}=`+(v=a*s*s+b*s*t+c*t*t)+(v?'':`
r1=${O(s,t)}
r2=(${c}/${a})/(${s}/${t})=`+O(c*t,s*a)),v
  )
)=>{
  for(s=0;++s<=q;)
    for(t=0;++t<=o;)
      if(!(q%s||o%t||K(-s)&&K(s)))
        return z
}

console.log=x=>O.textContent+=x+'\n'

// Test
console.log(f(9,12,4))
console.log(f(1,-1,-2))
console.log(f(-1,2,-1))
console.log(f(7,-316,924))
console.log(f(6,-35,-6))
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
## Mathematica, 236 Bytes

I'm sure there's a way to shorten this further, but this was my first attempt at learning the language.

**Golfed**

```
s=Input[];f[x_]:=#3 x^2+#1 x+#2&@@s;t=Drop[Z1,1];r=Catch[Do[Print[StringForm["x=``? ``=``",y,f[x],f[y]]];If[f[y]==0,Throw[y]],{y,(Flatten[Outer[Divide,#1,#2]]&@@(Join[#,-#]&/@Divisors[#]&[t]))}]]StringForm["r1=``\nr2=``",r, #1/#2/r&@@t]

```

**Ungolfed with comments**

```
(*Get coefficients in list {B,C,A}*)
s=Input[];

(*Create the function*)
f[x_]:=#3 x^2+#1 x+#2&@@s;

(*Take C and A*)
t=Drop[Z1,1];

(*Get a list of all positive and negative divisors for C and A, then use those to get all possible permutations for R=S/T as given in the challenge*)
(*Print out each attempt at finding a root. If one is found, exit the loop and return it*)

r=Catch[Do[Print[StringForm["x=``? ``=``",y,f[x],f[y]]];If[f[y]==0,Throw[y]],{y,(Flatten[Outer[Divide,#1,#2]]&@@(Join[#,-#]&/@Divisors[#]&[t]))}]];

(*Print the roots using (c/a)/r1 *)
StringForm["r1=``\nr2= ``",r, #1/#2/r&@@t]

```

Coefficients must be entered in the (convenient) form {B,C,A}.

---
Tags: code-golf, arithmetic, rational-numbers
---


title: Make a better score than my students!

text:
# Question
Title: Make a better score than my students!
For the last day of the semester, I decided to have some fun with my students and I showed them Code Golf... poor guys, they're addicted now.

The goal was to compete against the other students to solve those problems with what would be very usual rules for you. They had to use C# (because it's the language they are learning right now) so please do the same.

The length of each method must be the shortest **including the method signature**!

# Tasks

Write functions that do the following:

1. **Input:** `string`, `int`.
**Output:** `string`.
**Description:** the output string repeats the input string as many times as the input int.
**Example:** `a("Hi", 5)` returns `"HiHiHiHiHi"`.
2. **Input:** `int`.
**Output:** `int`.
**Description:** the output is the quantity of prime numbers lower or equal to the input.
**Example:** `b(10)` returns `4`. `b(100)` returns `25`.
3. **Input:** `object[]`.
**Output:** `object[]`.
**Description:** returns the input without the `null` values.
**Example:** `c(new object[] { "Hello", 42, null, new Program(), null, null, false })` returns an array containing `[Hello, 42, Program instance, false]`.
4. **Input:** `int`.
**Output:** `int`.
**Description:** the output is the sum of all the integers from 1 to int input.
**Example:** `d(4)` returns `10` (because 1 + 2 + 3 + 4 = 10).
5. **Input:** `char`.
**Output:** `char`.
**Description:** the output is the input char with the other case. non-letters don't need to be checked.
**Example:** `e('a')` returns `'A'`. `e('A')` returns `'a'`. `e('-')` may have unexpected results.
6. **Input:** `string`, `int`.
**Output:** `bool`.
**Description:** true if and only if the length of the input string is a multiple of the input int.
**Example:** `f("Programmer", 5)` returns `true`. `f("Programming", 5)` returns `false`.
7. **Input:** `string`.
**Output:** `boolean`.
**Description:** true if and only if the input string is a palindrome.
**Example:** `g("level")` returns `true`. `g('label')` returns `false`.

# Their solutions

I took the best of each task that they presented to me.

1. 64
2. 135
3. 105
4. 30
5. 71
6. 45
7. 83

Total: 533

(I will write their complete answers when the challenge is over).

# Your rules

* Use C# to be evaluated equally to my students.
* Write each task on a separate line **with the method signature** (`string a(string s,int i)`), it is part of the answer.
* Write your best score for each task so we know what score matches what task.
* Write the sum of all task scores in the title of your answer.
* The shortest overall score wins, but honorary mention may be awarded to the lowest score of a given task.

*Note:* It is not impossible that many of you have the same answer, my students did without cheating. Please consider that someont who has the same answer as you may simply have taken the same path and did not steal your idea.

---

**FAQ:**

* **Why should people here use C#? It's not the best language for code golfing !**
I know, but I would like to have some examples from pros like you to show them what a real golfer would do in their shoes.

# Answer
# Score: 387

1. `string a(string s,int n){return string.Join(s,new string[n+1]);}` (64)
2. `int b(int n){bool p=true;for(int i=2;i<n;i++)if(n%i<1)p=false;return n<2?0:b(n-1)+(p?1:0);}` (91)
3. `object[]c(object[]l){return l.Where(x=>x!=null).ToArray();}` (59)
4. `int d(int n){return(n+1)*n/2;}` (30)
5. `char e(char c){return(char)(c<97?c+32:c-32);}` (45)
6. `bool f(string s,int n){return s.Length%n<1;}` (44)
7. `bool g(string s){return s.SequenceEqual(s.Reverse());}` (54)

Total: 387
> 2 votes

---
Tags: code-golf, c#, multiple-holes
---


title: Winnable Solitaire Mancala Boards

text:
# Question
Title: Winnable Solitaire Mancala Boards
Mancala is the name of a family of board games that usually involve a series of cups filled with beads that the players manipulate. This challenge will use a specific rule set for a solitaire variant of the game.

The board consists of a "basket" at one end, followed by an infinite number of cups, numbered starting from 1. Some of the cups will have some number of beads in them. If the `n`th cup has exactly `n` beads in it, you may "sow" the beads from it. Sowing means to take all `n` beads out of the cup, then deposit them one at a time in each cup towards the basket. The last bead will go into the basket. The player wins when all of the beads on the board are in the basket.

Clearly, there are many boards which are not winnable, such as if there is exactly one bead in the second cup. There are no legal plays because all the cups with 0 beads cannot be sown, and the second cup does not have enough beads to be sown. This is obviously no fun, so your task will be to create winnable boards.

### Task

Given a positive integer representing a number of beads output a list of non-negative integers representing the number of beads that should be put in each cup to make a winnable board as described above. This list should not contain any trailing zeroes.

For any given number of beads, there is always exactly one winnable board configuration.

### Demonstration

This is a demonstration of how to play the winnable board for and input of 4. The winnable board is `[0, 1, 3]`. We start with the only available move, sowing the beads from the third cup to get `[1, 2, 0]`. Now we actually have a choice, but the only correct one is sowing the first cup, getting: `[0, 2, 0]`. Then we sow the second cup yielding `[1, 0, 0]` and finally we sow the first cup again to get all empty cups.

### Test cases:

```
1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]

```

Big thanks to PeterTaylor for coming up with a program to generate test cases!

# Answer
## CJam (21 bytes)

```
M{_0+0#_Wa*\)+.+}ri*`

```

Online demo

### Explanation

I independently derived the "unplaying" technique mentioned in this paper. We prove by induction that there is exactly one winning board for a given number of beads.

Base case: with 0 beads, the only winning board is the empty one.

Inductive step: if we sow from cup `k` then at the next move cup `k` will be empty and every cup nearer the basket will contain at least one bead. Therefore we can find the unique winning board with `n` beads from the winning board with `n-1` beads by looking for the lowest numbered empty cup, taking one bead from the basket and one from each cup below that empty cup, and placing them all in the empty cup.

### Dissection

```
M           e# Start with an empty board
{           e# Loop
  _0+0#     e#   Find position of first 0 (appending to ensure that there is one)
  _Wa*      e#   Make array of that many [-1]s
  \)+       e#   Append the index plus 1 (since board is 1-indexed)
  .+        e#   Pointwise addition
}
ri*         e# Read integer from stdin and execute loop that many times
`           e# Format for display

```
> 5 votes

# Answer
# Python, 42 41 bytes

```
m=lambda n,i=2:n*[1]and[n%i]+m(n-n%i,i+1)

```
> 9 votes

# Answer
## JavaScript (ES6), ~~63~~ 37 bytes

```
f=(n,d=2)=>n?[n%d,...f(n-n%d,d+1)]:[]

```

Port of @orlp's Python answer. Explanation: Consider the total number of beads in the `i`th and higher cups. Each play from one of these cups will remove `i` beads from that total. (For instance, if `i` is 3, and you play from the fifth cup, you reduce the number of beads in that cup by five, but you also add one to both the fourth and the third cups.) The total must therefore be a multiple of `i`. Now the `i-1`th cup cannot contain `i` or more beads, so in order for it to leave a multiple of `i` it must contain the remainder of the beads modulo `i`.

Previous explanation (from @xnor's link): The naive approach is the "reverse playing" technique. This uses the observation that making a play empties a cup, so reverse playing collects a bead from each cup and puts them in the first empty cup, like so (63 bytes):

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

```

Now, just consider the first `i` cups. In the case that one of them is empty, reverse playing will add `1` to the total number of beads in those cups, while in the case that none of them is empty, reverse playing will subtract `i` from the total, however this is equivalent to adding `1` modulo `i+1`. After `n` reverse plays the sum of the beads in the first `i` cups will therefore be equivalent to `n` modulo `i+1`, or put it another way, the number of beads in the `i`th cup will be equivalent to `n` minus the sum of the beads in the preceding cups, modulo `i+1`. Now for the `i`th cup to be playable the number of beads cannot exceed `i`, so in fact it will equal the number of remaining beads modulo `i+1`. (Note that I use `d=i+1` as it uses fewer bytes.)
> 4 votes

# Answer
# Ruby, 36 bytes

A port of @orlp's answer because it's far too genius for me to think of anything better.

```
m=->n,i=2{n>0?[n%i]+m[n-n%i,i+1]:[]}

```
> 2 votes

---
Tags: code-golf, game, board-game
---


title: Home improvement for the Minotaur

text:
# Question
Title: Home improvement for the Minotaur
# Home improvement for the Minotaur

The cretan labyrinth is quite easy to draw. Just start with a symmetric shape (here in red). Let us call all the endpoints of those lines 'nodes'. Then you begin drawing the arches (black): The first one alway begins in the top middle node and connects to the node next to it on the right side, then the two nodes closest to the previous arch are connected. This is repeated untill all nodes are covered.

Now we can generalize this concept: We can easily generate new initial patterns by adding more `L` shapes. I enumerated the initial shapes as follows:

The most left pattern will produce a *cretan labyrinth of degree 0*. The next one will create a *cretan labyrinth of degree 1* (the original one) etc.

# Task

Given a nonnegative integer `n`, your program should output the ascii representation of a cretan labyrinth of degree `n`, that is shown in the following examples. Trailing spaces/newlines do not matter. You have to include a short explanation of how your code works.

# Examples

The output for the original cretan labyrith (degree 1) is following:

```
+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ |
              +---------------+

```

Initial pattern:

```
+ | | | +
--+ | +--
----+----
--+ | +--
+ | | | +

```

The cretian labyrinth of degree 0 should look like so:

```
+-------------+
| +---------+ |
| | +-----+ | |
| | | +-+ | | |
| | + | + | | |
| +---+---+ | |
+---+ | +---+ |
      +-------+

```

Initial pattern:

```
+ | +
--+--
+ | +

```

# Answer
> 10 votes
# Perl 5, 349 bytes

```
say$p="| "x$_,"+","-"x(16*$n-4*$_+13),"+ $p"for 0..4*($n=pop)+3;say$p="| "x(3*$n+2),"+ | ","| "x2x$n,"+ $p|";$p=~s/..//,$q="-"x(4*$_-1),say"$p+$q+ ","| "x(2*$n-2*$_+1),"+$q+ $p|"for 1..$n;$p=~s/..//;say$p,("+---"."-"x4x$n)x2,"+ $p|";$p=~s/..//,$q="-"x(4*$n+3)."-"x4x$_,say"$p+$q+ | ","| "x2x($n-abs$_),"+$q+ $p|"for-$n..$n;say" "x(8*$n+6),"+----$q+"

```

(Pass *n* as a command line argument.)

Computes the maze line-by-line in six sections:

* first 4n + 4 lines,
* next line (the only line with no `-`),
* next n lines,
* next line (the line at the middle of the initial pattern),
* next 2n + 1 lines,
* final line (the line with leading spaces).

# Answer
> 6 votes
# Python 3.5, 703 695 676 648 587 581 542 535 500 486 462 431 423 411 bytes:

(*Thanks to @flawr for advice on saving 55 bytes (486 -\> 431)!*)

```
def j(r):R=range;Z=zip;B=r+r+2;P,M='+-';X='| ';q=[*Z(R(0,B-1,2),R(B-1,0,-2))];L=r+1;A=2+r;print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))

```

Not very much of a contender for the title, but I still gave it a shot, and it works perfectly. I will try to shorten it more over time where I can, but for now, I love it and could not be happier.

Try it online! (Ideone) (May look a little bit different on here because of apparent online compiler limitations. However, it's still very much the same.)

# Explanation:

For the purposes of this explanation, let's assume that the above function was executed with the input, `r`, being equal to `1`. That being said, basically what's happening, step-by-step, is...

1. `q=[*Z(R(0,B-1,2),R(B-1,0,-2))]`

A zip object, `q`, is created with 2 range objects, one consisting of every second integer in the range `0=>r+r+1` and another consisting of every second integer in the range `r+r+1=>0`. This is because every starting pattern of a cretan labyrinth of a specific degree will always have an even number of `-` in each line. For instance, for a cretan labyrinth of degree `1`, `r+r+1` equals `3`, and thus, its pattern will always start with `0` dashes, followed by another line with `4` (2+2) dashes. This zip object will be used for the first `r+1` lines of the labyrinth's pattern.

**Note:** The *only* reason `q` is a list and separated from the rest is because `q` is referenced a few times and subscripted, and to save a lot of repetition and allow subscripting, I simply created a zip object `q` in the form of a list.
2. `print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))`

This is the last step, in which the labyrinth is built and put together. Here, three lists, the first consisting of the top `4*r+1` lines of the labyrinth, the second consisting of the middle `3*r+3` lines of the labyrinth, and the last list consisting of the very last line of the labyrinth are joined together, with line breaks (`\n`) into one long string. Finally, this one huge string consisting of the entire labyrinth is printed out. Let us go more in depth into what these 2 lists and 1 string actually contain:

* The 1st list, in which another zipped object is used in list comprehension to create each line one by one, with leading `|`or `+` symbols, an odd number of dashes in the range `0=>4*(r+1)`, trailing `|` or `+` symbols, and then a newline (`\n`). In the case of a degree `1` labyrinth, this list returns:

    ```
    +-----------------------------+
    | +-------------------------+ |
    | | +---------------------+ | |
    | | | +-----------------+ | | |
    | | | | +-------------+ | | | |
    | | | | | +---------+ | | | | |
    | | | | | | +-----+ | | | | | |
    | | | | | | | +-+ | | | | | | |

    ```
    * The 2nd list, which consists of a zip object containing 4 lists, and each list corresponds to the number of leading/trailing `|` symbols, the number of `+` symbols, the number of dashes, and finally, the last list, which contains the first `r+1` lines of the pattern created according to zip object `q`, the line in the middle of the pattern (the one with no `|`), and the last `r+2` lines of the symmetrical pattern. In this specific case, the last list used in this list's zip object would return:

    ```
    + | | | +
    --+ | +--
    ----+----
    --+ | +--
    + | | | +
    --+ | +--  <- Last line created especially for use in the middle of the labyrinth itself.

    ```

    And therefore, in the case of a 1 degree labyrinth, this entire list would return:

    ```
    | | | | | + | | | + | | | | | |
    | | | | +---+ | +---+ | | | | |
    | | | +-------+-------+ | | | |
    | | +-------+ | +-------+ | | |
    | +-------+ | | | +-------+ | |
    +-----------+ | +-----------+ | <- Here is where the extra line of the pattern is used.

    ```
    * This final list, in which the last line is created. Here, the first segment (the one before the first space) length of the last line of list `P` number of spaces are created. Then, the length of the last segment (the ending segment) of the same line + 4 number of dashes are added, all of which are preceded and followed by a single `+` symbol. In the case of a degree 1 labyrinth, this last list returns:

    ```
                  +---------------+

    ```

After joining all this together, this step finally returns the completed labyrinth. In the case of a 1 degree labyrinth, it would finally return this:

```
+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ |
              +---------------+

```

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


title: Autocomplete the input

text:
# Question
Title: Autocomplete the input
**Pre-Note**
Because of popular demand, and to avoid disqualifying certain languages, the dictionary can now be provided as input parameter.

# Intro

Given a dictionary of words, you should write an autocomplete program or function.

# Autocompletion

*"Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing."* (Wikipedia)
Autocompletion is oftenly used to reduce the time needed for typing sentences. After typing a single character, the program will start guessing what the user is trying to say. In this challenge we will simulate the behaviour of autocompleting words.
If the program encounters a word it doesn't know, and no matching autocompletion words can be found, it will assume that the user is trying to type a word the program doesn't know. Good autocompletion software will own and edit a custom dictionary of words, but for the sakes of complexity that's not part of this challenge.

# Input

Your program/function will take at least a single parameter of input. This parameter can either be a string or an array of characters, and will consist of lowercase characters `[a-z]`.
Optionally, your program/function will take a second parameter containing a dictionary of words. More info on this in the paragraph **Dictionary**.

# Output

You should print or return an array of autocompleted words. For each character in the input, an autocompletion should be added to the output array.
The autocompletions will be taken from the provided dictionary. If a word doesn't exist in the dictionary, it will alphabetically search for the next word matching your characters. If no matching word is found, the input will be returned (see test cases)

# Dictionary

If you choose to read the dictionary from a file, the file structure should be your list of words, seperated by newlines.
If you choose to submit the dictionary of words as a parameter of a function call, it should be structured as an ordered list of strings; `['cat', 'cake', ...]`.
The input is always fully lowercase and sorted alphabetically.

# Test case

`a.txt` content:

```
alpha
calf
cave
coax
code
codegimmick
codegolf
cool
gamma

```

Test cases:

```
"codegolf"                  // ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"]
"alpaca"                    // ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"]
["t", "h", "i", "s"]        // ["t", "th", "thi", "this"]
("catses", ["cake","cats"]) // ["cake", "cake", "cats", "cats", "catse", "catses"]

```

This is code-golf, shortest code in bytes wins

# Answer
## Pyth, ~~22~~ 13 bytes

```
mhf!xTd+Qd._z

```

```
m         _z  map over prefixes of second input...
 hf    +Qd    find the first element in (dictionary+word) which...
   !xTd       ... starts with k

```

Sample run:

```
llama@llama:~$ pyth -c 'mhf!xTd+Qd._z'
['alpha', 'calf', 'cave', 'coax', 'code', 'codegimmick', 'codegolf', 'cool', 'gamma']
codegolf
['calf', 'coax', 'code', 'code', 'codegimmick', 'codegolf', 'codegolf', 'codegolf']

```

Thanks to @FryAmTheEggman for 4 bytes!
> 1 votes

# Answer
# JavaScript (ES6), 56

Input: array of characters, array of words
Output: array

```
(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

```

**Test**

```
f=(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

dict=['alpha','calf','cave','coax','code','codegimmick','codegolf','cool','gamma']

console.log=x=>O.textContent+=x+'\n'

;[['c','o','d','e','g','o','l','f'],['a','l','p','a','c','a'],['t','h','i','s']]
.forEach(t=>console.log(t+' -> '+f(t,dict)))
```

```
<pre id=O></pre>
```
> 1 votes

# Answer
# Mathematica, ~~108~~ 89 bytes

```
Select[Append[#2,c=b~StringTake~a],StringStartsQ@c][[1]]~Table~{a,StringLength[b=""<>#]}&

```

No, it isn't very pretty.
> 0 votes

# Answer
# JavaScript (ES6 / Node.js), 94 bytes

```
s=>s.map(c=>(d.match(`\\b${p+=c}.*`)||p)+"",p="",d=require("fs").readFileSync("a.txt","utf8"))

```

Anonymous function that takes an array of characters.

Or **52 bytes** in **JavaScript (ES6)** with passing the dictionary as a string:

```
d=>s=>s.map(c=>(d.match(`\\b${p+=c}.*`)||p)+"",p="")

```
> 0 votes

# Answer
# Python 3, 94 bytes

```
s=""
for c in input():s+=c;print(next((o for o in open("a.txt")if o.startswith(s)),s).strip())

```
> 0 votes

# Answer
# Javascript ES6, ~~80~~ 77 chars

```
(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])

```

Test:

```
d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])
;[
f("cat", ["cat"])[0] === "cat",
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]

```

Can reduce 4 chars (73 in total) if return array of single-element arrays:

```
(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)

```

Test:

```
d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)
;[
// f("cat", ["cat"])[0] === "cat", // will be failed
f("cat", ["cat"])[0][0] === "cat", // ok
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]
[false, true, true, true, true]

```
> 0 votes

---
Tags: code-golf
---