问:
Caveman Duels (or: Me poke you with sharp stick)

Caveman mad. Other caveman take stick but stick was for me. Caveman fight!

Description

Caveman need sharp stick to stab other caveman. Other caveman also try to stab with sharp stick. Caveman can sharpen stick, poke with stick, or block poky sticks.

If caveman poke other caveman with sharp stick, other caveman run away and me victory. But if other caveman smartly blocking when me poking, nothing happen except my stick become blunt and me need to sharpen again.

Caveman lazy. Also, caveman dumb. Caveman no know what to do, so caveman need fancy techno computer program to tell caveman what to do.

Input

Your program's input will be a history of the events that have happened, where S stands for sharpen (i.e. the caveman sharpened his stick), P stands for poke, and B stands for block. The input will be a history of both sides (you and the opponent), so your and the opponent's moves will be separated with a comma (,).

Example input:

```<code>SPB,SBB
</code>```

This means that the player sharpened his/her stick, then poked, then blocked, and the opponent sharpened, then blocked, then blocked again.

You will receive no input on turn 1.

Output

The output is very similar to the input (because the caveman is not very smart). Your program should output S to sharpen, P for poke, and B for block. Only the first character of output will be taken into account, and any other input will be treated as a B (block) command.

S: sharpen

When sharpening, the caveman's stick's sharpness goes up by 1 and the stick gets 1 extra poke. Each poke reduces the stick's sharpness by 1, and if the stick's sharpness is 0, it's too dull to poke with. Sharpness starts at 0. If sharpness gets to 5, the stick is a sword! (See below.)

If the opponent pokes while you are sharpening (and they have a sharpness > 0), the opponent wins!

P: poke

When poking, the caveman's stick's sharpness goes down by 1 and you poke your opponent! If your opponent is sharpening, you win! If the opponent is poking, your stick hits your opponent's stick and they both get duller (by 1 "sharpness unit"). If the opponent is blocking, nothing happens except that your stick becomes duller.

If you poke when your stick's sharpness is 5 or greater, your stick becomes a sword and you always win! (Unless your opponent also has a sword and also chose P; in that case, they both become duller, and may revert to sticks if their sharpness falls below 5.)

You cannot poke with a sharpness of 0. If you do, nothing will happen.

B: block

When you block, nothing happens when your opponent pokes. If your opponent is not poking, block does nothing.

Blocking does not protect against a sword, even if you also have one!

Rules and constraints

Additional rules are:

Your program can read and write files in its own folder (no stealing!) if you want to save data, but you can't access anything outside of it (and cavemen don't have internet connection out in the wilderness).

Important note on files: If you save files, remember to save them in the directory players/YourBotsName/somefile.foo! The current working directory for your program will not be your program's!

Cavemen are fair: One program can not have code specific for another program, and programs can not help each other. (You may have multiple programs, but they can't interact with each other in any way.)

The caveman judge is not patient. If the cavemen take more than 100 turns each to decide a winner, the judge gets bored and both cavemen lose.

If your program breaks a rule or doesn't follow the specification, the program is disqualified, removed from playerlist.txt, and all duels restart from the beginning. If your program is disqualified, the caveman leader (me!) will comment on your program's post and explain why. If you aren't breaking any rules, your program will be added to the leaderboard. (If your program is not on the leaderboard, there is no explanatory comment on your post, and you posted your program before the "Last updated" time below, tell the caveman leader! Maybe he forgot it.)

In your post, please include:

A name.

A shell command to run your program (ex. java MyBot.java, ruby MyBot.rb, python3 MyBot.py, etc.).

Note: input will be appended to this as a command line argument.

The cavemen use Ubuntu 14.04, so make sure your code works (freely) on it.

A version number, if your code works differently on different versions of your chosen language.

Your code (obviously).

How to compile the code, if necessary.

Controller code / testing, example bot

The caveman leader wrote the control code in C++, and posted it on a Github repo. You can run and test your program there.

A very, very simple program (1 line!) is also posted in the answers below.

Scoring and leaderboard

Scoring is easy. Whichever caveman wins gets a point. The caveman with the most points after 3 duels against every other caveman becomes the new caveman leader!

```<code>150     Watson
147     SpeculativeSylwester
146     Gruntt
141     BashMagnon
126     ChargerMan
125     PrisonRules
124     ViceLeader
122     MultiMarkov
122     CaveDoctor
120     RegExMan
120     Hodor
117     FancyTechnoAlgorithm
116     Semipatient
113     Watcher
108     BobCaves
105     MinimaxMan
104     Oracle
102     MaybeMarkov
97      Nash
95      Sicillian
95      Feint
95      Basilisk
94      SharpMan
93      Darwin
91      Nigel
91      JavaMan
88      Entertainer
88      CarefulBot
85      CaveMonkey
84      SSBBP
82      SirPokealot
79      MasterPoker
77      Unpredictable
76      IllogicalCaveman
75      SharpenBlockPoke
75      HuddleWolfWithStick
72      WoodenShield
68      PokeBackBot
68      PatientBlacksmith
66      PatientWolf
58      MonteCarloMan
58      BlindFury
56      BinaryCaveman
55      PokeBot
55      CavekidBlocks
53      Swordmaster
53      Blocker
52      NakedEarlyNerd
52      ModestCaveman
50      LatePokeBot
40      Trickster
39      SwordLover
38      ForeignCaveman
36      Swordsmith *
28      Touche
27      WantASword
27      FoolMeOnce
24      PeriodicalCavemanCicada
11      Aichmophobic
</code>```

(this leaderboard was auto-magically generated)

Players marked with a * threw some kind of error or exception at some point; these players also have a comment on their posts.

Players who could not be included in the tests for any reason (these players will have a comment on their posts explaining the problem): Monkey, Elephant, FacileFibonacci, StudiousSylwester.

Last updated: Aug 3 00:15 (UTC).

答:
Deep Thoughts, C

Caveman code. Caveman think. Caveman do.

```<code>// DeepThoughts.c
#include <stdio.h>  // Me need for plan
#include <string.h> // Me need for memory

// Me count sharps. If me still here, pokes no work
int is_pointy(char *past){
    int pointy = 0;     // Stick dull
    while(*past){
        switch(*past ++){
            case 'S': pointy ++; break;
            case 'P': if(pointy > 0) pointy --;
        }
    }
    return pointy;
}

// Me brain
int main(int argc, char *argv[]){
    int me_pointy = 0;  // Is 0, stick dull. Is 5, has sword
    int you_pointy = 0; // Same to you
    int me_last;        // Me last plan
    int you_last;       // Same to you
    char *you;          // You past
    int when;           // Time
    int me_plan;        // Me deep thought

    // Me remember
    if(argc > 1){
        you = strchr(argv[1], ',');     // Me find you past in me arg
        *you ++ = 0;
        when = strlen(argv[1]);         // Time is passing
        me_pointy = is_pointy(argv[1]); // Me look at me past
        you_pointy = is_pointy(you);    // Same to you
        me_last = argv[1][when - 1];    // Why me do that?
        you_last = you[when - 1];       // Same to you
    }

    // Me has deep thoughts. Me make plan
    if(me_pointy >= 5) me_plan = 'P';       // Me has sword
    else if(you_pointy == 0) me_plan = 'S'; // Me safe. You stick dull
    else if(when == 1) me_plan = 'P';       // Me shoot first (more thought)
    else if(me_pointy == 1 && when < 42) me_plan = 'B';  // Me try for sharper (deeper thought)
    else if(me_pointy > 0) me_plan = 'P';   // Me stick not dull
    else if(me_last == 'P') me_plan = 'B';  // Me in trouble
    else me_plan = 'S';                     // Me cross toes

    // Me do plan
    putchar(me_plan);
    return 0;
}
</code>```

Me do testing. More thoughts better.

Body:
Deep Thoughts, C

Caveman code. Caveman think. Caveman do.

// DeepThoughts.c
#include <stdio.h>  // Me need for plan
#include <string.h> // Me need for memory

// Me count sharps. If me still here, pokes no work
int is_pointy(char *past){
    int pointy = 0;     // Stick dull
    while(*past){
        switch(*past ++){
            case 'S': pointy ++; break;
            case 'P': if(pointy > 0) pointy --;
        }
    }
    return pointy;
}

// Me brain
int main(int argc, char *argv[]){
    int me_pointy = 0;  // Is 0, stick dull. Is 5, has sword
    int you_pointy = 0; // Same to you
    int me_last;        // Me last plan
    int you_last;       // Same to you
    char *you;          // You past
    int when;           // Time
    int me_plan;        // Me deep thought

    // Me remember
    if(argc > 1){
        you = strchr(argv[1], ',');     // Me find you past in me arg
        *you ++ = 0;
        when = strlen(argv[1]);         // Time is passing
        me_pointy = is_pointy(argv[1]); // Me look at me past
        you_pointy = is_pointy(you);    // Same to you
        me_last = argv[1][when - 1];    // Why me do that?
        you_last = you[when - 1];       // Same to you
    }

    // Me has deep thoughts. Me make plan
    if(me_pointy >= 5) me_plan = 'P';       // Me has sword
    else if(you_pointy == 0) me_plan = 'S'; // Me safe. You stick dull
    else if(when == 1) me_plan = 'P';       // Me shoot first (more thought)
    else if(me_pointy == 1 && when < 42) me_plan = 'B';  // Me try for sharper (deeper thought)
    else if(me_pointy > 0) me_plan = 'P';   // Me stick not dull
    else if(me_last == 'P') me_plan = 'B';  // Me in trouble
    else me_plan = 'S';                     // Me cross toes

    // Me do plan
    putchar(me_plan);
    return 0;
}

Me do testing. More thoughts better.


问:
Is this number a prime?
Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

Task

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

Input

If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

For scoring purposes, submit the program that corresponds to the input 1.

Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Additional rules

This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

Unless they have been overruled earlier, all standard code-golf rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
Unipants' Golfing Language, <s>53</s> 47 bytes

```<code>i$cu^d^-l_u^^/%cu%?%d%:_?coc$d$$:__^d^-:_u?cuo:
</code>```

Try it online!

(It has been implemented as a standard example in the interpreter.)

ContentLicense: CC BY-SA 3.0

Title: Is this number a prime?

Body:
Unipants' Golfing Language, <s>53</s> 47 bytes

i$cu^d^-l_u^^/%cu%?%d%:_?coc$d$$:__^d^-:_u?cuo:

Try it online!

(It has been implemented as a standard example in the interpreter.)


问:
Josephus problem with three inputs
There's a question on this site that is similar to this question, but I have added a twist.

You have three inputs, the number of people in the circle n, the k-th person counted out at each step, and the q-th person that survives. The people in the circle are numbered 1 to n.

For example, in a circle of 20 people, the 20th person to survive is the very first person removed, the 19th survivor is the second person removed and so on. Normally, the Josephus problem is to determine the last person removed, here called the first survivor.

Write the shortest program or function that, with those three inputs, returns the number of the q-th person to survive.

If there are any issues with clarity, please let me know.

Some examples:

```<code>>>> josephus(20, 3, 9)
4
>>> josephus(4, 3, 1)
1
>>> josephus(100, 9, 12)
46
</code>```

Edit: Assume all inputs are valid. That is no one will ask for 0 or any negative numbers and no one will ask for the 20th survivor in a circle of 5 people (that is, 1 ≤ q ≤ n)

Edit: I'll accept an answer at midnight UTC+7 at the start of December 2.

答:
PHP, 71 bytes

Based off of @Sherlock9's answers. See his Python answer for the algorithm.

```<code>function a($n,$k,$q){for($r=($k-1)%$q;$q<$n;$r=($r+$k)%++$q);echo$r+1;}
</code>```

Alternatively, here is my original naive approach without the algorithm. This uses an array to mark which people are found.

91 bytes

```<code>function a($n,$k,$q){for($r=--$i;$q<=$n;++$i%$k||$c[$r]=$q++)while($c[$r=++$r%$n]);echo$r;}
</code>```

Title: Josephus problem with three inputs

Body:
PHP, 71 bytes

Based off of @Sherlock9's answers. See his Python answer for the algorithm.

function a($n,$k,$q){for($r=($k-1)%$q;$q<$n;$r=($r+$k)%++$q);echo$r+1;}

Alternatively, here is my original naive approach without the algorithm. This uses an array to mark which people are found.

91 bytes

function a($n,$k,$q){for($r=--$i;$q<=$n;++$i%$k||$c[$r]=$q++)while($c[$r=++$r%$n]);echo$r;}


问:
Convert to Roman Numeral!
Your task is to convert a given positive integer from Arabic numeral to Roman numeral.

Things get difficult when you count to 4000.

The romans did this by adding a line above a symbol to multiply that symbol by 1 000. However, overlines aren't exactly displayable in ASCII. Also, there are double overlines to multiply a symbol by 1 000 000, and then triple overline to multiply a symbol by 1 000 000 000, etc...

Therefore, I decided to use parentheses to replace overlines.

The symbols can be individually placed in parentheses. For example, both (VI) and (V)(I) are valid representations of 6 000. (V)M is also a valid representation of 6000.

(I) is a valid way to represent 1 000.

Testcases

```<code>Input: 1
Output: I
Input: 2
Output: II
Input: 3
Output: III
Input: 4
Output: IV
Input: 15
Output: XV
Input: 40
Output: XL
Input: 60
Output: LX
Input: 67
Output: LXVII
Input: 400
Output: CD
Input: 666
Output: DCLXVI
Input: 3000
Output: MMM
Input: 3999
Output: MMMCMXCIX
Input: 4000
Output: M(V)
Input: 4999
Output: M(V)CMXCIX
Input: 6000
Output: (VI)
Input: 6000000
Output: ((VI))
Input: 6006000
Output: ((VI)VI)
Input: 6666666666
Output: (((VI)DCLXVI)DCLXVI)DCLXVI
</code>```

Scoring

This is code-golf. Shortest code in bytes win.

答:
R, 134

```<code>m=1000;x=scan();while(x[1]>=m)x=c(floor(x[1]/m),x[1]%%m,x[-1]);cat(rep("(",length(x)),sep="");cat(as.character(as.roman(x)),sep=")")
</code>```

It's pretty much not the best option, but I think the idea should go pretty similar to this.

Title: Convert to Roman Numeral!

Body:
R, 134

m=1000;x=scan();while(x[1]>=m)x=c(floor(x[1]/m),x[1]%%m,x[-1]);cat(rep("(",length(x)),sep="");cat(as.character(as.roman(x)),sep=")")

It's pretty much not the best option, but I think the idea should go pretty similar to this.


问:
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):

```<code>########
########
########
########
########
########
########
########
</code>```

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:

```<code>#   #
 # # #
  # # #
 # #
    #
</code>```

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

```<code>#### ####
#### ####
#### ####
#### ####
</code>```

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:

```<code>#
 ##
</code>```

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:

```<code>[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]
</code>```

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 code-golf 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.

```<code>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]]
</code>```

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.

答:
Pyth, 41 35

```<code>hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt
</code>```

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.

Title: Seeking Leapers

Body:
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.

<a href="http://pyth.herokuapp.com/?code=hfqQu%40%2BG%2BVM%2as_BM%2aF_BMTGQ%5DhQ%29maVhQdt&input=%5B%5B1%2C+1%5D%2C+%5B1%2C+2%5D%2C+%5B1%2C+3%5D%2C+%5B1%2C+4%5D%2C+%5B1%2C+5%5D%2C+%5B1%2C+6%5D%2C+%5B1%2C+7%5D%2C+%5B1%2C+8%5D%2C+%5B2%2C+1%5D%2C+%5B2%2C+2%5D%2C+%5B2%2C+3%5D%2C+%5B2%2C+4%5D%2C+%5B2%2C+5%5D%2C+%5B2%2C+6%5D%2C+%5B2%2C+7%5D%2C+%5B2%2C+8%5D%2C+%5B3%2C+1%5D%2C+%5B3%2C+2%5D%2C+%5B3%2C+3%5D%2C+%5B3%2C+4%5D%2C+%5B3%2C+5%5D%2C+%5B3%2C+6%5D%2C+%5B3%2C+7%5D%2C+%5B3%2C+8%5D%2C+%5B4%2C+1%5D%2C+%5B4%2C+2%5D%2C+%5B4%2C+3%5D%2C+%5B4%2C+4%5D%2C+%5B4%2C+5%5D%2C+%5B4%2C+6%5D%2C+%5B4%2C+7%5D%2C+%5B4%2C+8%5D%2C+%5B5%2C+1%5D%2C+%5B5%2C+2%5D%2C+%5B5%2C+3%5D%2C+%5B5%2C+4%5D%2C+%5B5%2C+5%5D%2C+%5B5%2C+6%5D%2C+%5B5%2C+7%5D%2C+%5B5%2C+8%5D%2C+%5B6%2C+1%5D%2C+%5B6%2C+2%5D%2C+%5B6%2C+3%5D%2C+%5B6%2C+4%5D%2C+%5B6%2C+5%5D%2C+%5B6%2C+6%5D%2C+%5B6%2C+7%5D%2C+%5B6%2C+8%5D%2C+%5B7%2C+1%5D%2C+%5B7%2C+2%5D%2C+%5B7%2C+3%5D%2C+%5B7%2C+4%5D%2C+%5B7%2C+5%5D%2C+%5B7%2C+6%5D%2C+%5B7%2C+7%5D%2C+%5B7%2C+8%5D%2C+%5B8%2C+1%5D%2C+%5B8%2C+2%5D%2C+%5B8%2C+3%5D%2C+%5B8%2C+4%5D%2C+%5B8%2C+5%5D%2C+%5B8%2C+6%5D%2C+%5B8%2C+7%5D%2C+%5B8%2C+8%5D%5D&debug=0" rel="nofollow noreferrer">Try it here or run a <a href="http://pyth.herokuapp.com/?code=hfqQu%40%2BG%2BVM%2as_BM%2aF_BMTGQ%5DhQ%29maVhQdt&test_suite=1&test_suite_input=%5B%5B1%2C+1%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+1%5D%2C+%5B1%2C+2%5D%5D%0A%5B%5B1%2C+1%5D%2C+%5B12%2C+35%5D%5D%0A%5B%5B1%2C+1%5D%2C+%5B1%2C+2%5D%2C+%5B2%2C+1%5D%2C+%5B2%2C+2%5D%2C+%5B6%2C+1%5D%2C+%5B6%2C+2%5D%2C+%5B6%2C+3%5D%2C+%5B6%2C+4%5D%2C+%5B7%2C+1%5D%2C+%5B7%2C+2%5D%2C+%5B7%2C+3%5D%2C+%5B7%2C+4%5D%2C+%5B8%2C+1%5D%2C+%5B8%2C+2%5D%2C+%5B8%2C+3%5D%2C+%5B8%2C+4%5D%2C+%5B9%2C+1%5D%2C+%5B9%2C+2%5D%2C+%5B9%2C+3%5D%2C+%5B9%2C+4%5D%5D%0A%5B%5B1%2C+1%5D%2C+%5B1%2C+2%5D%2C+%5B1%2C+3%5D%2C+%5B1%2C+4%5D%2C+%5B1%2C+5%5D%2C+%5B1%2C+6%5D%2C+%5B2%2C+1%5D%2C+%5B2%2C+2%5D%2C+%5B2%2C+3%5D%2C+%5B2%2C+4%5D%2C+%5B2%2C+5%5D%2C+%5B2%2C+6%5D%2C+%5B3%2C+1%5D%2C+%5B3%2C+2%5D%2C+%5B3%2C+5%5D%2C+%5B3%2C+6%5D%2C+%5B4%2C+1%5D%2C+%5B4%2C+2%5D%2C+%5B4%2C+5%5D%2C+%5B4%2C+6%5D%2C+%5B5%2C+1%5D%2C+%5B5%2C+2%5D%2C+%5B5%2C+3%5D%2C+%5B5%2C+4%5D%2C+%5B5%2C+5%5D%2C+%5B5%2C+6%5D%2C+%5B6%2C+1%5D%2C+%5B6%2C+2%5D%2C+%5B6%2C+3%5D%2C+%5B6%2C+4%5D%2C+%5B6%2C+5%5D%2C+%5B6%2C+6%5D%5D%0A%5B%5B2%2C+2%5D%2C+%5B2%2C+4%5D%2C+%5B2%2C+6%5D%2C+%5B2%2C+8%5D%2C+%5B4%2C+2%5D%2C+%5B4%2C+4%5D%2C+%5B4%2C+6%5D%2C+%5B4%2C+8%5D%2C+%5B6%2C+2%5D%2C+%5B6%2C+4%5D%2C+%5B6%2C+6%5D%2C+%5B6%2C+8%5D%2C+%5B8%2C+2%5D%2C+%5B8%2C+4%5D%2C+%5B8%2C+6%5D%2C+%5B8%2C+8%5D%5D%0A%5B%5B1%2C+1%5D%2C+%5B1%2C+2%5D%2C+%5B1%2C+3%5D%2C+%5B1%2C+4%5D%2C+%5B2%2C+1%5D%2C+%5B2%2C+2%5D%2C+%5B2%2C+3%5D%2C+%5B2%2C+4%5D%2C+%5B3%2C+1%5D%2C+%5B3%2C+2%5D%2C+%5B3%2C+3%5D%2C+%5B3%2C+4%5D%2C+%5B4%2C+1%5D%2C+%5B4%2C+2%5D%2C+%5B4%2C+3%5D%2C+%5B4%2C+4%5D%2C+%5B6%2C+1%5D%2C+%5B6%2C+2%5D%2C+%5B6%2C+3%5D%2C+%5B6%2C+4%5D%2C+%5B7%2C+1%5D%2C+%5B7%2C+2%5D%2C+%5B7%2C+3%5D%2C+%5B7%2C+4%5D%2C+%5B8%2C+1%5D%2C+%5B8%2C+2%5D%2C+%5B8%2C+3%5D%2C+%5B8%2C+4%5D%2C+%5B9%2C+1%5D%2C+%5B9%2C+2%5D%2C+%5B9%2C+3%5D%2C+%5B9%2C+4%5D%5D&debug=0" rel="nofollow noreferrer">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.


问:
In-between fractions

In-between fractions

The challenge:

You will need to create code that takes atleast 3 inputs; 2 integers and "a fraction representation" - whichever type suits your language for representing the fraction increments) ie. If you choose string the input would be "1/4" or you could choose 2 extra integer inputs or a tuple or w/e.

Input can be anywhere reasonable (STDIN, function arguments, from a file, etc.), and so can output (STDOUT, function return value, to a file, etc.)

Rules:

The input "fraction" will always be a valid fraction, less than 1; example "1/4"

The second input integer will always have a higher value than the first integer. I.E the first input integer will always have a lower value than the second.

The input integers can be negative.

Outputted fractions should be reduced as much as possible (simplified)

The code will need to output every "fraction step" between the 2 numbers in increments of the input fraction.

The code should be a program or function as stated here

Example 1:

Input: -2,3,"1/2"

Output:

```<code> -2
 -3/2
 -1
 -1/2
  0
  1/2
  1
  3/2
  2
  5/2
  3
</code>```

Example 2:

Input: 1,2,"2/3"

Output:

```<code>1
5/3
2
</code>```

or

```<code>1
4/3
2
</code>```

Note: Counting can start from either direction (thank you @Mego)

This is code-golf, so the shortest answer in bytes wins.

答:
Julia, 14 bytes

```<code>f(a,b,c)=a:c:b
</code>```

This is similar to the Mathematica answer, except that Julia's ranges are already in the desired format, so it is even shorter. Also returns a collection of numbers. Example output:

```<code>11-element StepRange{Rational{Int64},Rational{Int64}}:
 -3//1,-5//2,-2//1,-3//2,-1//1,-1//2,0//1,1//2,1//1,3//2,2//1
</code>```

Note that the integers are displayed with 1 in the denominator, and a double-slash is used for fractions. To get the output exactly as defined in the question requires some more code:

```<code>f(a,b,c)=map(x->println(x.num,x.den<2?"":"/$(x.den)"),a:c:b)
</code>```

Title: In-between fractions

Body:
Julia, 14 bytes

f(a,b,c)=a:c:b

This is similar to the Mathematica answer, except that Julia's ranges are already in the desired format, so it is even shorter. Also returns a collection of numbers. Example output:

11-element StepRange{Rational{Int64},Rational{Int64}}:
 -3//1,-5//2,-2//1,-3//2,-1//1,-1//2,0//1,1//2,1//1,3//2,2//1

Note that the integers are displayed with 1 in the denominator, and a double-slash is used for fractions. To get the output exactly as defined in the question requires some more code:

f(a,b,c)=map(x->println(x.num,x.den<2?"":"/$(x.den)"),a:c:b)


问:
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 fastest-code 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.

答:
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.


答:
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:

Score the best submission at the current N

Give a point to the best submission at the current N, plus a point for each optimal solution

Same as #2, but also give a point to the person that proved that a given submission was optimal.

Title: How can I score challenges with variable problem sizes?

Body:
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 fastest-code 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.


问:
Linear Independence
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0,  a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

```<code>[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
</code>```

答:
Python 2 with NumPy - <s>85</s> <s>112</s> <s>103</s> 102 bytes

import numpy
x=input(i)
try:print reduce(lambda a,b:a*b,numpy.linalg.eigvals(x))
except:print(x==[])|0
```

Hopefully can get a few off, FGITW.

Title: Linear Independence

Body:
Python 2 with NumPy - <s>85</s> <s>112</s> <s>103</s> 102 bytes

import numpy
x=input(i)
try:print reduce(lambda a,b:a*b,numpy.linalg.eigvals(x))
except:print(x==[])|0

Hopefully can get a few off, FGITW.


答:
R, <s>72</s> 60 bytes

function(x,m,n)!is.null(x)&&all(pracma::rref(x)==diag(,m,n))
```

This is a function that accepts the vectors as columns in a matrix as well as the dimensions of the matrix and returns a logical. To call it, assign it to a variable. It requires the pracma package to be installed but it doesn't have to be imported.

The actual checking for linear independence is done by row reducing the matrix to echelon form and checking whether that's equal to an identity matrix of matching dimension. We just need a special case for when the input is empty.

Saved 12 bytes with help from Luis Mendo!

Title: Linear Independence

Body:
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0,  a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

```<code>[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
</code>```

Body:
R, <s>72</s> 60 bytes

function(x,m,n)!is.null(x)&&all(pracma::rref(x)==diag(,m,n))

This is a function that accepts the vectors as columns in a matrix as well as the dimensions of the matrix and returns a logical. To call it, assign it to a variable. It requires the pracma package to be installed but it doesn't have to be imported.

The actual checking for linear independence is done by row reducing the matrix to echelon form and checking whether that's equal to an identity matrix of matching dimension. We just need a special case for when the input is empty.

Saved 12 bytes with help from Luis Mendo!


问:
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.

Tax will be calculated according to the official tables in IRS Revenue Procedure 2014-61, section .01 Tax Rate Tables, Tables 1-4.  I have added these tables at the bottom of the question.

You may choose whatever rounding method you like, as long as the result is accurate to 2 decimal places.

Example Inputs:

```<code>0.00 S
10000.00 MFJ
100000.00 MFS
1000000.00 QW
</code>```

Example Outputs corresponding to above inputs:

```<code>0.00
1000.00
21525.75
341915.90
</code>```

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

答:
Python 3, <s>427</s> <s>382</s> <s>317</s> <s>309</s> <s>308</s> 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 function(income, status).

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

Body:
Python 3, <s>427</s> <s>382</s> <s>317</s> <s>309</s> <s>308</s> 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 function(income, status).

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


答:
Octave, <s>32</s> 27 bytes

Thanks to @Suever for removing 5 bytes!

```<code>@(x)~numel(x)|any(rref(x)')
</code>```

The code defines an anonymous function. To call it assign it to a variable or use ans. The result is a non-empty array, which in Octave is truthy if all its entries are nonzero.

Try all test cases online.

This is based on the reduced row echelon form of a matrix. A non-empty matrix is full-rank iff each row of its reduced row echelon form contains at least one non-zero entry. This is checked by condition any(rref(x)', where ' can be used to transpose instead of .' because the entries are not complex. The empty matrix is dealt with separately by the condition ~numel(x) (which is the same as isempty(x) but shorter).

Title: Linear Independence

Body:
Octave, <s>32</s> 27 bytes

Thanks to @Suever for removing 5 bytes!

@(x)~numel(x)|any(rref(x)')

The code defines an anonymous function. To call it assign it to a variable or use ans. The result is a non-empty array, which in Octave is truthy if all its entries are nonzero.

Try all test cases online.

This is based on the reduced row echelon form of a matrix. A non-empty matrix is full-rank iff each row of its reduced row echelon form contains at least one non-zero entry. This is checked by condition any(rref(x)', where ' can be used to transpose instead of .' because the entries are not complex. The empty matrix is dealt with separately by the condition ~numel(x) (which is the same as isempty(x) but shorter).


问:
A Numpad's Knight Numbers
For the non-zero digits on a standard numpad

```<code>789
456
123
</code>```

consider placing a chess knight at any digit and moving it around with any number of normal L-shaped jumps, tracing out a positive decimal integer. What positive integers can be expressed in such a way?

One of them is 38, since the knight could start on the 3 and move left and up to the 8. 381 and 383 are also possible.

3 itself is possible if no jumps are taken (which is allowed). 5 is as well, but no other digits can be reached from the 5, so it is the only number where the digit 5 appears.

Write a program or function that takes in a positive decimal integer (you may take it as a string if desired) and prints or returns a truthy value if the number can be expressed by a knight on a numpad in the way described, but otherwise outputs a falsy value.

The shortest code in bytes wins. Tiebreaker is earlier answer

Examples

Truthy:

```<code>1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 18, 38, 61, 81, 294, 349, 381, 383, 729, 767, 38183, 38383, 18349276, 183492761, 618349276
</code>```

Falsy:

```<code>10, 11, 50, 53, 55, 65, 95, 100, 180, 182, 184, 185, 186, 187, 188, 189, 209, 305, 2009, 5030, 3838384, 4838383, 183492760
</code>```

答:
C, <s>85</s> 81 bytes

Golfed:

i;f(char*b){i=*b++-49;return*b?(*b=="8749x7214"[i]||*b=="6983x1632"[i])&&f(b):1;}
```
<p>Old non-recursive version (85 bytes):</p>
<pre class="lang-c prettyprint-override"><code>i;f(char*b){for(;(i=*b++-49),*b&&*b=="8749x7214"[i]||*b=="6983x1632"[i];);return!*b;}
</code>```

Old code with white-space and main program:

i;
f(char*b){
    for (; (i=*b++-49), *b     // i = index of digit + 1 in following arrays
        &&*b=="8749x7214"[i]   // 1st possible jump for 1..9
        ||*b=="6983x1632"[i];  // 2nd possible jump for 1..9
    );
    return !*b;
}

main(){
    char b[16];
    while(scanf("%s", b) == 1) printf("%d",f(b));
    return 0;
}
```

This accepts space-delimited numbers via standard input and outputs 0 if not-numpad-knight, or 1 otherwise.

The new 81-byte recursive version shaves 4 bytes.

Title: A Numpad's Knight Numbers

Body:
C, <s>85</s> 81 bytes

Golfed:

i;f(char*b){i=*b++-49;return*b?(*b=="8749x7214"[i]||*b=="6983x1632"[i])&&f(b):1;}

Old non-recursive version (85 bytes):

i;f(char*b){for(;(i=*b++-49),*b&&*b=="8749x7214"[i]||*b=="6983x1632"[i];);return!*b;}

Old code with white-space and main program:

i;
f(char*b){
    for (; (i=*b++-49), *b     // i = index of digit + 1 in following arrays
        &&*b=="8749x7214"[i]   // 1st possible jump for 1..9
        ||*b=="6983x1632"[i];  // 2nd possible jump for 1..9
    );
    return !*b;
}

main(){
    char b[16];
    while(scanf("%s", b) == 1) printf("%d",f(b));
    return 0;
}

This accepts space-delimited numbers via standard input and outputs 0 if not-numpad-knight, or 1 otherwise.

The new 81-byte recursive version shaves 4 bytes.


问:
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:

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

But these are not:

```<code>-->
(--
)--
[{
---
</code>```

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

So these are some valid cord connections:

```<code>...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...
</code>```

And these are invalid:

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

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

```<code>[-->
{---]
>----{
</code>```

the output could be

```<code>[-->>----{{---]
</code>```

where all the cords are strung together.

However if the input were

```<code>[-->
{---]
</code>```

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

```<code>(-[
}--]
</code>```

could have output

```<code>(-[[--{
</code>```

where the second cord is flipped, or

```<code>}--]]-)
</code>```

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:

```<code>[-->
{---]
>----{
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.
</code>```

Cases without output:

```<code>[-->
{---]

[-]
[-]

(-]
]->
}-)

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

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

{--[
]--}
</code>```

Body:
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:

Read the entire input and generate the above structure, including all the mirrored cables.

Try out all combinations (but stop if a solution is found).

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:

We find that all cables are marked “in use”. This means we’ve found a solution (which is represented by the current stack contents).

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).

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”).

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:

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.

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.

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.)

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.


答:
Mathematica - 29 bytes

```<code>#=={}||Det[#.Transpose@#]!=0&
</code>```

Uses the property that the product of the eigenvalues of matrix A is equal to the determinant of A.

Sample

```<code>#=={}||Det[#.Transpose@#]!=0&@{{1,2,3},{1,3,5},{0,0,0}}
>>  False
</code>```

Title: Linear Independence

Body:
Mathematica - 29 bytes

#=={}||Det[#.Transpose@#]!=0&

Uses the property that the product of the eigenvalues of matrix A is equal to the determinant of A.

Sample

#=={}||Det[#.Transpose@#]!=0&@{{1,2,3},{1,3,5},{0,0,0}}
>>  False


问:
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:

```<code>########
#      #
########

   ###        ####
   ###        ####
   ###
</code>```

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 code-golf, 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

```<code>#

####

##
##

##########
##########
##########
</code>```

Soft

```<code>###
# #
###

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

####
#  #
#  #
#  #
#  #
#  #
#  #
#  #
####
</code>```

Actual Test Cases

```<code>########
#      #
########

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

Hard

###
###
###

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

Equal

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

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

Soft
</code>```

答:
Julia, <s>99</s> <s>95</s> 93 bytes

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

! 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.


问:
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

```<code>(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
</code>```

答:
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.

Title: Identify the Conic Section

Body:
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)]

<a href="http://sagecell.sagemath.org/?z=eJxFUs1ugzAMvlfqO_jUBOYioHRa0VKp9NwnyDgwSLVIjKKQVtCnX5zSDmTZsf19_kkadYYz74N8uYDzxYAG3ckEU8xKcsFdSL1KUK9SJxnG9JcUOInfyho9cnkv36QcwxHHcMLJyYgTJiWxOcvxQV8GBLFmyg9Y4FHw09dN1fZi-D0IZL7xjGqsVW_z-tJZ3V0VuRpRhMU6Cw_hkY5G2avpJOsrU31f2ooh-5l6ZWa71qZulTNU2-p-UKyUshEixmbv5DOuugYKdyZ9EOJIvjLSXaNGngSuh-XCqsEOIIAxxmOEOEDgCcKWdIqwIZ0hfJDeIaQBiD28elgueBK5tG30SIwIGr37ZLLTyBM54uQRT6kEUcwdO4LtXDWbq20Qshn0BK-3HvMYl2rOkCdvOusn1FHtPOK1N8ZoWLqhuhoUXZEfPBr6VttWd2rg_kW4jwLoNk9boeRHDmfEx4L_HKFuVcvJmp290Z11b8u7PMMfioGfWw==&lang=sage" rel="nofollow noreferrer">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.


问:
Subsequence Substitution
Most languages come with a built-in to search a string for all occurrences of a given substring and replace those with another. I don't know of any language that generalises this concept to (not necessarily contiguous) subsequences. So that's your task in this challenge.

The input will consist of three strings A, B and C, where B and C are guaranteed to be of the same length. If B appears as a subsequence in A it should be replaced with C. Here is a simple example:

```<code>A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345
</code>```

It would be processed like this:

```<code>abcdefghijklmnopqrstuvwxyz
      ||      |   ||
abcdef12ijklmn3pqr45uvwxyz
</code>```

If there are several ways to find B as a subsequence, you should greedily replace the left-most one:

```<code>A: abcdeedcba
B: ada
C: BOB

Result:   BbcOeedcbB
and NOT:  BbcdeeOcbB
</code>```

The same applies if B could be found in multiple disjoint places:

```<code>A: abcdeedcbaabcde
B: ed
C: 12

Result:   abcd1e2cbaabcde
and NOT:  abcd112cbaabc2e (or similar)
</code>```

When B does not appear in A, you should output A unchanged.

Rules

As stated above, take three strings A, B and C as input and replace the left-most occurrence of B as a subsequence in A with C, if there is any.

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.

You may take the three strings in any consistent order which you should specify in your answer. You may assume that B and C have the same length. All strings will only contain alphanumeric characters.

Standard code-golf rules apply.

Test Cases

Each test case is four lines: A, B, C followed by the result.

```<code>abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44
</code>```

Leaderboard

The Stack Snippet at the bottom of this post generates leaderboards from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

/* Configuration */

var QUESTION_ID = 77719; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery(''+lang+'').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
Java 7, 102 bytes

```<code>void L(char[]s,char[]l,char[]r){for(int x=0,y=0;x<s.length&&y<l.length;x++)if(s[x]==l[y])s[x]=r[y++];}
</code>```

Detailed try here

```<code>// String, Lookup, Replacement
void L(char[]s, char[]l, char[]r)
{
    for(int x=0, y=0; x < s.length && y < l.length; x++)
        if(s[x] == l[y])
            s[x] = r[y++];
}
</code>```

Title: Subsequence Substitution

Body:
Java 7, 102 bytes

void L(char[]s,char[]l,char[]r){for(int x=0,y=0;x<s.length&&y<l.length;x++)if(s[x]==l[y])s[x]=r[y++];}

Detailed try here

// String, Lookup, Replacement
void L(char[]s, char[]l, char[]r)
{
    for(int x=0, y=0; x < s.length && y < l.length; x++)
        if(s[x] == l[y])
            s[x] = r[y++];
}


Title: Federal income tax calculator for procrastinators

Body:
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.

Tax will be calculated according to the official tables in IRS Revenue Procedure 2014-61, section .01 Tax Rate Tables, Tables 1-4.  I have added these tables at the bottom of the question.

You may choose whatever rounding method you like, as long as the result is accurate to 2 decimal places.

Example Inputs:

```<code>0.00 S
10000.00 MFJ
100000.00 MFS
1000000.00 QW
</code>```

Example Outputs corresponding to above inputs:

```<code>0.00
1000.00
21525.75
341915.90
</code>```

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

Body:
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.


答:
Matlab - <s>19</s> 16 bytes

```<code>@(A)det(A*A')>.5
</code>```

If the product of the matrix and its transpose is singular, then the rows of the matrix are linearly dependent. The determinant is non-negative, and since the entries are integral (thank you Alex A.), the determinant is integral and can be compared to .5.

It would have been nice to just do @(A)~det(A*A'), but unfortunately det can give almost-zero for singular matrices.

Try it on ideone

Title: Linear Independence

Body:
Matlab - <s>19</s> 16 bytes

@(A)det(A*A')>.5

If the product of the matrix and its transpose is singular, then the rows of the matrix are linearly dependent. The determinant is non-negative, and since the entries are integral (thank you Alex A.), the determinant is integral and can be compared to .5.

It would have been nice to just do @(A)~det(A*A'), but unfortunately det can give almost-zero for singular matrices.

Try it on ideone